Cilk , Cilk ++ и Cilk Plus - это языки программирования общего назначения, предназначенные для многопоточных параллельных вычислений . Они основаны на языках программирования C и C ++ , которые расширяются конструкциями для выражения параллельных циклов и идиомы fork – join .
Парадигма | императивный ( процедурный ), структурированный , параллельный |
---|---|
Разработано | Лаборатория компьютерных наук Массачусетского технологического института |
Разработчик | Intel |
Впервые появился | 1994 г. |
Печатная дисциплина | статический , слабый , явный |
Веб-сайт | www |
Диалекты | |
Cilk ++, Cilk Plus | |
Под влиянием | |
C | |
Под влиянием | |
OpenMP 3.0 [1] |
Разработано | Intel |
---|---|
Разработчик | Intel |
Впервые появился | 2010 г. |
Стабильный выпуск | 1.2 / 9 сентября 2013 г . |
Расширения имени файла | (То же, что C или C ++) |
Веб-сайт | www |
Первоначально разработанный в 1990-х годах в Массачусетском технологическом институте (MIT) в группе Чарльза Э. Лейзерсона , Cilk позже был коммерциализирован как Cilk ++ дочерней компанией Cilk Arts. Впоследствии эта компания была приобретена Intel , которая увеличила совместимость с существующим кодом C и C ++, назвав результат Cilk Plus.
История
MIT Cilk
Язык программирования Cilk вырос из трех отдельных проектов Лаборатории компьютерных наук Массачусетского технологического института: [2]
- Теоретическая работа по планированию многопоточных приложений.
- StarTech - параллельная шахматная программа, созданная для работы на модели Connection Machine CM-5 компании Thinking Machines Corporation.
- PCM / Threaded-C - пакет на основе C для планирования потоков в стиле продолжения передачи на CM-5.
В апреле 1994 года три проекта были объединены и получили название «Силк». Название Cilk не является аббревиатурой, а является намеком на «хорошие потоки» ( шелк ) и язык программирования C. Компилятор Cilk-1 был выпущен в сентябре 1994 года.
Исходный язык Cilk был основан на ANSI C с добавлением специфичных для Cilk ключевых слов для обозначения параллелизма. Когда ключевые слова Cilk удаляются из исходного кода Cilk, результатом всегда должна быть допустимая программа на C, называемая последовательным исключением (или C elision ) полной программы Cilk, с той же семантикой, что и программа Cilk, работающая на одном процессоре. Несмотря на некоторые сходства, [ какой? ] Силк не имеет прямого отношения к Concurrent C от AT&T Bell Labs .
Cilk был реализован как переводчик на C, предназначенный для компилятора GNU C (GCC). Последняя версия, Cilk 5.4.6, доступна в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL), но больше не поддерживается. [3]
Демонстрацией возможностей Силка стала программа параллельной игры в шахматы Силкчесс, которая выиграла несколько компьютерных шахматных призов в 1990-х годах, включая Открытый чемпионат Нидерландов по компьютерным шахматам 1996 года. [4]
Cilk Arts и Cilk ++
До c. В 2006 году рынок Cilk был ограничен высокопроизводительными вычислениями. Появление многоядерных процессоров в массовых вычислениях означало, что ежегодно отгружаются сотни миллионов новых параллельных компьютеров. Компания Cilk Arts была создана, чтобы воспользоваться этой возможностью: в 2006 году Лейзерсон запустил Cilk Arts, чтобы создать и вывести на рынок современную версию Cilk, которая поддерживает коммерческие потребности нового поколения программистов. Компания завершила раунд венчурного финансирования Series A в октябре 2007 года, а ее продукт Cilk ++ 1.0 был выпущен в декабре 2008 года.
Cilk ++ отличается от Cilk несколькими способами: поддержка C ++, поддержка циклов и гиперобъектов - новая конструкция, предназначенная для решения проблем гонки данных, создаваемых параллельным доступом к глобальным переменным. Cilk ++ был проприетарным программным обеспечением . Как и его предшественник, он был реализован как компилятор Cilk-to-C ++. Он поддерживал компиляторы Microsoft и GNU.
Intel Cilk Plus
31 июля 2009 года Cilk Arts объявила на своем веб-сайте, что ее продукты и команда инженеров теперь являются частью Intel Corp. В начале 2010 года веб-сайт Cilk по адресу www.cilk.com
начал перенаправлять на веб-сайт Intel (с начала 2017 года исходный веб-сайт Cilk больше не разрешает хост). Intel и Cilk Arts интегрировали и усовершенствовали технологию, что привело к выпуску Intel Cilk Plus в сентябре 2010 года . [5] [6] Cilk Plus использует упрощения, предложенные Cilk Arts в Cilk ++, чтобы устранить необходимость в нескольких исходных ключевых словах Cilk, добавляя при этом возможность создания функций и работы с переменными, участвующими в операциях сокращения. Cilk Plus отличается от Cilk и Cilk ++ добавлением расширений массива, включением в коммерческий компилятор (от Intel) и совместимостью с существующими отладчиками. [7]
Cilk Plus был впервые реализован в компиляторе Intel C ++ с выпуском компилятора Intel в Intel Composer XE 2010. [ необходима ссылка ] Реализация с открытым исходным кодом (под лицензией BSD ) была внесена Intel в коллекцию компиляторов GNU (GCC), которая добавлена поддержка Cilk Plus в версии 4.9, [8] за исключением ключевого слова _Cilk_for , которое было добавлено в GCC 5.0. В феврале 2013 года Intel анонсировала форк Clang с поддержкой Cilk Plus. [9] Компилятор Intel, но не реализации с открытым исходным кодом, поставляется с детектором гонки и анализатором производительности.
Позже Intel прекратила его выпуск, порекомендовав пользователям перейти на использование OpenMP или собственной библиотеки Intel TBB для своих потребностей в параллельном программировании. [10]
Различия между версиями
В исходной реализации MIT Cilk фактически первое ключевое слово Cilk cilk
идентифицирует функцию, написанную на Cilk. Поскольку процедуры Cilk могут вызывать процедуры C напрямую, но процедуры C не могут напрямую вызывать или порождать процедуры Cilk, это ключевое слово необходимо, чтобы отличать код Cilk от кода C. Cilk Plus снимает это ограничение, а также cilk
ключевое слово, поэтому функции C и C ++ могут вызывать код Cilk Plus и наоборот.
Моральное устаревание
В мае 2017 года был выпущен GCC 7.1, в котором поддержка Cilk Plus была помечена как устаревшая. [11] В сентябре 2017 года сама Intel объявила, что прекращает поддержку Cilk Plus с выпуском Intel Software Development Tools 2018 года. [10] В мае 2018 года был выпущен GCC 8.1 с удаленной поддержкой Cilk Plus. [12]
Особенности языка
Принцип, лежащий в основе дизайна языка Cilk, заключается в том, что программист должен нести ответственность за выявление параллелизма, определение элементов, которые могут безопасно выполняться параллельно; затем его следует оставить на усмотрение среды выполнения, в частности, планировщика , чтобы решить во время выполнения, как на самом деле разделить работу между процессорами. Поскольку эти обязанности разделены, программа Cilk может работать без перезаписи на любом количестве процессоров, включая один.
Параллелизм задач: порождение и синхронизация
Основное дополнение Cilk к C - это два ключевых слова, которые вместе позволяют писать программы, параллельные задачам.
- В ключевое слово spawn перед вызовом функции ( spawn f (x) ), указывает, что вызов функции ( f (x) ) может безопасно выполняться параллельно с операторами, следующими за ним в вызывающей функции. Обратите внимание, что планировщик не обязан выполнять эту процедуру параллельно; ключевое слово просто предупреждает планировщик, что он может это сделать.
- А Оператор sync указывает, что выполнение текущей функции не может продолжаться, пока не будут завершены все ранее порожденные вызовы функций. Это пример барьерного метода.
(В Cilk Plus ключевые слова пишутся _Cilk_spawn и _Cilk_sync или cilk_spawn и cilk_sync, если включены заголовки Cilk Plus.)
Ниже представлена рекурсивная реализация функции Фибоначчи в Cilk с параллельными рекурсивными вызовами, которая демонстрирует порождение , и синхронизировать ключевые слова. Исходный Cilk требовал, чтобы любая функция, использующая их, была аннотирована cilk , которого нет в Cilk Plus. (Программный код Cilk не пронумерован; номера добавлены только для облегчения обсуждения.)
cilk int fib ( int n ) { if ( n < 2 ) { return n ; } else { int x , y ; x = создать fib ( n - 1 ); y = создать fib ( n - 2 ); синхронизация ; вернуть x + y ; }}
Если этот код был выполнен одним процессором, чтобы определить значение fib (2) , этот процессор создаст фрейм для fib (2) и выполняет строки с 1 по 5. В строке 6 он создает пробелы в кадре для хранения значений х и у . В строке 8 процессор должен приостановить текущий кадр, создать новый кадр для выполнения процедуры. fib (1) , выполните код этого кадра до тех пор, пока не дойдете до оператора возврата, а затем возобновите фрейм fib (2) со значением fib (1), помещенным в fib (2) 's x переменная. В следующей строке потребуется снова приостановить выполнение, чтобы выполнить fib (0) и поместите результат в fib (2) 's y переменная.
Однако, когда код выполняется на многопроцессорной машине, выполнение происходит иначе. Один процессор начинает выполнение fib (2) ; однако когда он достигает строки 8, ключевое слово spawn, изменяющее вызов fib (n-1) сообщает процессору, что он может безопасно передать задание второму процессору: этот второй процессор может создать кадр для fib (1) , выполнить его код и сохранить результат в фрейм fib (2) после его завершения; первый процессор продолжает выполнение кода fib (2) одновременно. Процессор не обязан назначать порожденную процедуру где-либо еще; если на машине всего два процессора, а второй все еще занят fib (1), когда процессор выполняет fib (2) переходит к вызову процедуры, первый процессор приостанавливает работу fib (2) и выполните fib (0) , как если бы он был единственным процессором. Конечно, если доступен другой процессор, он будет задействован, и все три процессора будут выполнять отдельные кадры одновременно.
(Предыдущее описание не совсем точное. Несмотря на то, что общая терминология для обсуждения Cilk относится к процессорам, принимающим решение передать работу другим процессорам, на самом деле именно планировщик назначает процедуры процессорам для выполнения, используя политику, называемую work- воровство , описанное позже.)
Если процессор, выполняющий fib (2) должен был выполнить строку 13 до того, как оба других процессора завершили свои кадры, это привело бы к неправильному результату или ошибке; fib (2) будет пытаться добавить значения, хранящиеся в х и y , но одно или оба этих значения будут отсутствовать. Это цель Ключевое слово sync , которое мы видим в строке 11: оно сообщает процессору, выполняющему фрейм, что он должен приостановить собственное выполнение до тех пор, пока все вызовы процедур, которые он порождал, не вернутся. Когда fib (2) может пройти мимо оператор синхронизации в строке 11, это может быть только потому, что fib (1) и fib (0) завершили и поместили свои результаты в х и y , что делает безопасным выполнение вычислений по этим результатам.
В приведенном выше примере кода используется синтаксис Cilk-5. Исходный Cilk (Cilk-1) использовал довольно другой синтаксис, который требовал программирования в явном стиле передачи продолжения , а примеры Фибоначчи выглядят следующим образом: [13]
поток fib ( cont int k , int n ) { если ( n < 2 ) { send_argument ( k , n ); } else { cont int x , y ; spawn_next сумма ( к , ? х , ? у ); создать fib ( x , n - 1 ); создать fib ( y , n - 2 ); } } сумма потока ( cont int k , int x , int y ) { send_argument ( k , x + y ); }
Внутри Рекурсивный случай fib , Ключевое слово spawn_next указывает на создание потока- преемника (в отличие от дочерних потоков, созданных spawn ), который выполняет Подпрограмма sum после ожидания переменных продолжениях и y заполняется рекурсивными вызовами. Базовый случай и сумма использовать send_argument (k, n) операция для установки их переменной продолжения k к значению n , эффективно «возвращая» значение потоку-преемнику.
Впускные отверстия
Два оставшихся ключевых слова Cilk немного более продвинуты и касаются использования входных отверстий . Обычно, когда порождается процедура Cilk, она может возвращать свои результаты родительской процедуре, только помещая эти результаты в переменную в родительском фрейме, поскольку мы присвоили результаты наших порожденных вызовов процедур в примере x
и y
.
Альтернативой является использование входного патрубка. Вход - это внутренняя функция процедуры Cilk, которая обрабатывает результаты вызова порожденной процедуры по мере их возврата. Одна из основных причин использования входов заключается в том, что все входы процедуры гарантированно работают атомарно по отношению друг к другу и к родительской процедуре, что позволяет избежать ошибок, которые могут возникнуть, если несколько процедур возврата попытаются обновить одни и те же переменные в родительский фрейм одновременно.
inlet
Ключевое слово идентифицирует функцию , определенную в порядке , в качестве входного отверстия.abort
Ключевое слово можно использовать только внутри впускного отверстия; он сообщает планировщику, что любые другие процедуры, порожденные родительской процедурой, можно безопасно прервать.
Входные отверстия были удалены, когда Cilk стал Cilk ++, и их нет в Cilk Plus.
Параллельные петли
Cilk ++ добавил дополнительную конструкцию, параллельный цикл, обозначенный cilk_for в Cilk Plus. Эти петли выглядят как
пустой цикл ( int * a , int n ){ #pragma cilk grainsize = 100 // необязательно cilk_for ( int i = 0 ; i < n ; i ++ ) { а [ я ] = е ( а [ я ]); }}
Это реализует идиому параллельной карты : тело цикла, здесь вызов f с последующим присвоением массиву a , выполняется для каждого значения я с нуля до п в неопределенном порядке. Необязательная прагма «размер зерна» определяет укрупнение : любой подмассив из ста или менее элементов обрабатывается последовательно. Хотя спецификация Cilk не определяет точное поведение конструкции, типичной реализацией является рекурсия «разделяй и властвуй» [14], как если бы программист написал
static void recursion ( int * a , int start , int end ) { if ( end - start <= 100 ) { // Здесь 100 - это размер зерна. для ( int я = начало ; я < конец ; я ++ ) { а [ я ] = е ( а [ я ]); } } еще { int midpoint = начало + ( конец - начало ) / 2 ; рекурсия cilk_spawn ( a , начало , середина ); рекурсия ( а , середина , конец ); cilk_sync ; } } void loop ( int * a , int n ) { рекурсия ( a , 0 , n ); }
Причины создания программы «разделяй и властвуй», а не очевидной альтернативы, цикла, который порождает тело цикла как функцию, лежат как в обработке размера зерна, так и в эффективности: выполнение всего порождения в одной задаче вызывает загрузку устранение узких мест. [15]
Обзор различных конструкций параллельного цикла на HPCwire показал, что cilk_for конструкция весьма общий характер , но отметил , что спецификация Cilk Plus не предусмотрено , что его итерации должны быть данные независимых от , так что компилятор не может автоматически векторизоватьcilk_for цикл. В обзоре также отмечен тот факт, что сокращения (например, суммы по массивам) требуют дополнительного кода. [14]
Редукторы и гиперобъекты
В Cilk ++ добавлен вид объектов, называемых гиперобъектами , которые позволяют нескольким цепям совместно использовать состояние без условий гонки и без использования явных блокировок. Каждая нить имеет вид гиперобъекта, который он может использовать и обновлять; когда потоки синхронизируются, представления объединяются способом, указанным программистом. [16]
Наиболее распространенным типом гиперобъектов является редуктор, который соответствует предложению редукции в OpenMP или алгебраическому понятию моноида . У каждого редуктора есть элемент идентичности и ассоциативная операция , объединяющая два значения. Типичный редуктор - это суммирование чисел: единичный элемент равен нулю, а операция ассоциативного сокращения вычисляет сумму. Этот редуктор встроен в Cilk ++ и Cilk Plus:
// Вычислить ∑ foo (i) для i от 0 до N, параллельно. cilk :: reducer_opadd < float > result ( 0 ); cilk_for ( int i = 0 ; i < N ; i ++ ) result + = foo ( i );
Другие редукторы могут использоваться для создания связанных списков или строк, а программисты могут определять собственные редукторы.
Ограничение гиперобъектов состоит в том, что они обеспечивают лишь ограниченную детерминированность . Burckhardt et al. укажите, что даже редуктор суммы может привести к недетерминированному поведению, показывая программу, которая может производить либо 1 или 2 в зависимости от порядка расписания: [17]
void add1 ( cilk :: reducer_opadd < int > & r ) { r ++ ; } // ... cilk :: reducer_opadd < int > r ( 0 ); cilk_spawn add1 ( r ); если ( г == 0 ) { г ++ ; } cilk_sync ; вывод ( r . get_value ());
Обозначение массива
Intel Cilk Plus добавляет нотацию для выражения высокоуровневых операций над целыми массивами или разделами массивов ; например, функция в стиле axpy, которая обычно записывается
// y ← α x + y void axpy ( int n , float alpha , const float * x , float * y ) { for ( int i = 0 ; i < n ; i ++ ) { y [ i ] + = alpha * х [ я ]; } }
может быть выражено в Cilk Plus как
y [0: n] + = альфа * x [0: n];
Эта нотация помогает компилятору эффективно векторизовать приложение. Intel Cilk Plus позволяет применять операции C / C ++ к нескольким элементам массива параллельно, а также предоставляет набор встроенных функций, которые можно использовать для выполнения векторизованных сдвигов, поворотов и сокращений. Аналогичная функциональность существует в Fortran 90 ; Cilk Plus отличается тем, что никогда не выделяет временные массивы, поэтому использование памяти легче предсказать.
Элементарные функции
В Cilk Plus элементарная функция - это обычная функция, которую можно вызывать либо для скалярных аргументов, либо для элементов массива параллельно. Они похожи на функции ядра OpenCL .
#pragma simd
Эта прагма дает компилятору разрешение на векторизацию цикла даже в тех случаях, когда автоматическая векторизация может завершиться неудачно. Это самый простой способ применить векторизацию вручную.
Работа-кража
Планировщик Cilk использует политику под названием «кража работы» для эффективного разделения выполнения процедуры между несколькими процессорами. Опять же, проще всего понять, если мы сначала посмотрим, как код Cilk выполняется на однопроцессорной машине.
Процессор поддерживает стек, в который он помещает каждый кадр, который он должен приостановить, чтобы обработать вызов процедуры. Если он выполняет fib (2) и встречает рекурсивный вызов fib (1) , он сохранит состояние fib (2) , включая его переменные и место, где код приостановил выполнение, и поместит это состояние в стек. Он не будет брать состояние приостановки из стека и возобновлять выполнение до тех пор, пока вызов процедуры, вызвавший приостановку, и все процедуры, вызываемые в свою очередь этой процедурой, не будут полностью выполнены.
Конечно, при использовании нескольких процессоров все меняется. У каждого процессора по-прежнему есть стек для хранения кадров, выполнение которых было приостановлено; однако эти стопки больше похожи на двухсторонние , в том смысле , что приостановленные состояния могут быть удалены с любого конца. Процессор по-прежнему может удалять состояния из своего собственного стека только с того же конца, на который он их помещает; однако любой процессор, который в настоящее время не работает (завершив свою работу или еще не назначенный), выберет другой процессор случайным образом через планировщик и попытается «украсть» работу с противоположного конца своего стека - приостановленные состояния, которые затем может начать исполнять процессор. Состояния, которые были украдены, - это состояния, из которых украденный процессор будет выполняться последним.
Смотрите также
- Grand Central Dispatch
- Коллекции Intel Concurrent (CnC)
- Строительные блоки Intel Parallel (PBB)
- Строительные блоки Intel Array (ArBB)
- Intel Parallel Studio
- NESL
- OpenMP
- Параллельные вычисления
- Система параллельного программирования Sieve C ++
- Строительные блоки с резьбой (TBB)
- Унифицированный параллельный C
Рекомендации
- ^ LaGrone, Джеймс; Арибуки, Айодунни; Аддисон, Коди; Чепмен, Барбара (2011). Реализация задач OpenMP во время выполнения . 7-й международный семинар по OpenMP. С. 165–178. CiteSeerX 10.1.1.221.2775 . DOI : 10.1007 / 978-3-642-21487-5_13 .
- ^ "Краткая история Силк
- ^ «Силк-проект» . MIT CSAIL. 8 октября 2010 . Проверено 25 января +2016 .
- ^ Leiserson, Charles E .; Plaat, Aske (1998). «Программирование параллельных приложений в Cilk» . Новости SIAM . 31 .
- ^ «Intel Flexes Parallel Programming Muscles» Архивировано 06 сентября 2010 г.на Wayback Machine , HPCwire (02 сентября 2010 г.). Проверено 14 сентября 2010.
- ^ «Parallel Studio 2011: теперь мы знаем, что случилось с Ct, Cilk ++ и RapidMind» , журнал доктора Добба (02.09.2010). Проверено 14 сентября 2010.
- ^ «Intel Cilk Plus: быстрый, простой и надежный способ улучшить многопоточную производительность» , Intel. Проверено 14 сентября 2010.
- ^ «GCC 4.9 Release Series Changes, New Features, and Fixes» , Free Software Foundation, Inc., дата обращения 29.06.2014.
- ^ Cilk Plus / LLVM
- ^ а б Хансан Б. (20 сентября 2017 г.). «Intel Cilk Plus устарел» . Форум Intel Cilk Plus .
- ^ «Серия выпусков GCC 7. Изменения, новые функции и исправления» . GCC, Коллекция компиляторов GNU .
- ^ «Серия выпусков GCC 8. Изменения, новые функции и исправления» . GCC, Коллекция компиляторов GNU .
- ^ Блюмофе, Роберт Д.; Joerg, Christopher F .; Kuszmaul, Bradley C .; Leiserson, Charles E .; Randall, Keith H .; Чжоу, Юли (1995). Cilk: эффективная многопоточная система выполнения (PDF) . Proc. ACM SIGPLAN Symp. Принципы и практика параллельного программирования . С. 207–216.
- ^ а б Вулф, Майкл (6 апреля 2015 г.). «Компиляторы и многое другое: прошлое, настоящее и будущее параллельных циклов» . HPCwire .
- ^ МакКул, Майкл; Рейндерс, Джеймс; Робисон, Арка (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир. п. 30.
- ^ Фриго, Маттео; Хальперн, Пабло; Leiserson, Charles E .; Левин-Берлин, Стивен (2009). Редукторы и другие гиперобъекты Cilk ++ (PDF) . Proc. Ежегодный симпозиум по параллелизму в алгоритмах и архитектурах (SPAA). ACM.
- ^ Буркхардт, Себастьян; Балдассин, Александро; Лейен, Даан (2010). Параллельное программирование с ревизиями и типами изоляции (PDF) . Proc. OOPSLA / SPLASH.
Внешние ссылки
- Официальный сайт Cilk Plus
- Сайт Cilk Project в Массачусетском технологическом институте
- Арч Д. Робисон, «Cilk Plus: языковая поддержка параллелизма потоков и векторов» и «Параллельное программирование с помощью Cilk Plus» , 16 июля 2012 г.