Силк - Cilk

Силк, Cilk ++ и Силк Плюс находятся общее назначение языки программирования предназначен для многопоточный параллельные вычисления. Они основаны на C и C ++ языки программирования, которые они расширяют конструкциями для выражения параллельных циклов и fork – join идиома.

Первоначально разработанный в 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 года три проекта были объединены и получили название «Силк». Имя Силк - не аббревиатура, а намек на «красивые темы» (шелк ) и язык программирования C. Компилятор Cilk-1 был выпущен в сентябре 1994 года.

Первоначальный язык Cilk был основан на ANSI C, с добавлением специфичных для Cilk ключевых слов для обозначения параллелизма. Когда ключевые слова Cilk удаляются из исходного кода Cilk, результатом всегда должна быть действующая программа на C, называемая серийная элизия (или же C elision) полной программы Cilk с той же семантикой, что и программа Cilk, работающая на одном процессоре. Несмотря на некоторые сходства,^{[который? ]} Силк не имеет прямого отношения к AT&T Bell Labs ' Одновременный C.

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 в сентябре 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 объявила Лязг вилка с поддержкой Cilk Plus.^[9] Компилятор Intel, но не реализации с открытым исходным кодом, поставляется с детектор гонки и анализатор производительности.

Позже Intel прекратила его выпуск, порекомендовав пользователям перейти на использование либо OpenMP или же Собственная библиотека Intel TBB для их нужд параллельного программирования.^[10]

Различия между версиями

В исходной реализации MIT Cilk первое ключевое слово Cilk фактически шелк, который определяет функцию, написанную на Cilk. Поскольку процедуры Cilk могут вызывать процедуры C напрямую, но процедуры C не могут напрямую вызывать или порождать Cilk, это ключевое слово необходимо, чтобы отличать код Cilk от кода C. Cilk Plus снимает это ограничение, а также шелк ключевое слово, поэтому функции C и C ++ могут вызывать код Cilk Plus и наоборот.

Моральное устаревание

В мае 2017 года был выпущен GCC 7.1, в котором поддержка Cilk Plus была помечена как устаревшая.^[11] Сама Intel объявила в сентябре 2017 года о прекращении поддержки Cilk Plus с выпуском Intel Software Development Tools 2018 года.^[10] В мае 2018 года был выпущен GCC 8.1 с удаленной поддержкой Cilk Plus.^[12]

Особенности языка

Принцип, лежащий в основе дизайна языка Cilk, заключается в том, что программист должен нести ответственность за разоблачение параллелизм, определяющий элементы, которые можно безопасно выполнять параллельно; затем его следует оставить на усмотрение среды выполнения, особенно планировщик, чтобы решить во время выполнения, как на самом деле разделить работу между процессорами. Поскольку эти обязанности разделены, программа Cilk может работать без перезаписи на любом количестве процессоров, включая один.

Параллелизм задач: порождение и синхронизация

Основное дополнение Cilk к C - это два ключевых слова, которые вместе позволяют писать программы, параллельные задачам.

• В порождать ключевое слово перед вызовом функции (создать f (x)), указывает, что вызов функции (f (x)) может безопасно выполняться параллельно с операторами, следующими за ним в вызывающей функции. Обратите внимание, что планировщик не обязанный запустить эту процедуру параллельно; ключевое слово просто предупреждает планировщик, что он может это сделать.
• А синхронизировать указывает, что выполнение текущей функции не может продолжаться, пока не будут завершены все ранее порожденные вызовы функций. Это пример барьер метод.

(В Cilk Plus ключевые слова пишутся _Cilk_spawn и _Cilk_sync, или же cilk_spawn и cilk_sync если включены заголовки Cilk Plus.)

Ниже приводится рекурсивный реализация Фибоначчи функция в Cilk с параллельными рекурсивными вызовами, демонстрирующая порождать, и синхронизировать ключевые слова. Исходный Cilk требовал, чтобы любая функция, использующая их, была аннотирована шелк ключевое слово, которое отсутствует в Cilk Plus. (Программный код Cilk не пронумерован; номера добавлены только для облегчения обсуждения.)

 1 шелк int выдумать(int п) { 2     если (п < 2) { 3         возвращаться п; 4     } 5     еще { 6        int Икс, у; 7  8        Икс = порождать выдумать(п - 1); 9        у = порождать выдумать(п - 2);10 11        синхронизировать;12 13        возвращаться Икс + у;14     }15 }

Если этот код был выполнен Один процессор для определения стоимости фиб (2), этот процессор создаст Рамка за фиб (2)и выполнить строки с 1 по 5. В строке 6 будут созданы пробелы в кадре для хранения значений Икс и у. В строке 8 процессор должен приостановить текущий кадр, создать новый кадр для выполнения процедуры. фиб (1), выполните код этого кадра до тех пор, пока не дойдете до оператора возврата, а затем возобновите фиб (2) кадр со значением fib (1), помещенным в фиб (2)с Икс Переменная. В следующей строке потребуется снова приостановить выполнение, чтобы выполнить фиб (0) и поместите результат в фиб (2)с у Переменная.

Когда код выполняется на мультипроцессор машина, однако, исполнение протекает иначе. Один процессор начинает выполнение фиб (2); однако когда он достигает строки 8, порождать ключевое слово, изменяющее вызов фиб (п-1) сообщает процессору, что он может безопасно передать задание второму процессору: этот второй процессор может создать кадр для фиб (1), выполнить его код и сохранить результат в фиб (2)фрейм, когда он закончится; первый процессор продолжает выполнение кода фиб (2) в то же время. Процессор не обязан назначать порожденную процедуру где-либо еще; если на машине всего два процессора, а второй все еще занят фиб (1) когда процессор выполняет фиб (2) доходит до вызова процедуры, первый процессор приостановит фиб (2) и выполнить фиб (0) сам, как если бы это был единственный процессор. Конечно, если доступен другой процессор, он будет задействован, и все три процессора будут выполнять отдельные кадры одновременно.

(Предыдущее описание не совсем точное. Несмотря на то, что общая терминология для обсуждения Cilk относится к процессорам, принимающим решение передать работу другим процессорам, на самом деле именно планировщик назначает процедуры процессорам для выполнения, используя политику, называемую воровство, описано позже.)

Если процессор, выполняющий фиб (2) если бы строка 13 была выполнена до того, как оба других процессора завершили свои кадры, это привело бы к неверному результату или ошибке; фиб (2) будет пытаться добавить значения, хранящиеся в Икс и у, но одно или оба этих значения будут отсутствовать. Это цель синхронизировать ключевое слово, которое мы видим в строке 11: оно сообщает процессору, выполняющему кадр, о том, что он должен приостановить собственное выполнение до тех пор, пока все вызовы процедур, которые он порождал, не вернутся. Когда фиб (2) разрешено пройти мимо синхронизировать в строке 11, это может быть только потому, что фиб (1) и фиб (0) завершили и разместили свои результаты в Икс и у, что делает безопасным выполнение вычислений по этим результатам.

В приведенном выше примере кода используется синтаксис Cilk-5. Исходный Cilk (Cilk-1) использовал довольно другой синтаксис, который требовал программирования в явном виде. стиль передачи, а примеры Фибоначчи выглядят следующим образом:^[13]

нить выдумать(продолжение int k, int п){    если (п < 2) {        send_argument(k, п);    }    еще {        продолжение int Икс, у;        spawn_next сумма(k, ?Икс, ?у);        порождать выдумать(Икс, п - 1);        порождать выдумать(у, п - 2);    }}нить сумма(продолжение int k, int Икс, int у){     send_argument(k, Икс + у);}

Внутри выдуматьрекурсивный случай, spawn_next ключевое слово указывает на создание преемник нить (в отличие от ребенок темы, созданные порождать), который выполняет сумма подпрограмма после ожидания переменные продолжения Икс и у заполняться рекурсивными вызовами. Базовый случай и сумма использовать send_argument (k, n) операция по установке их переменной продолжения k к стоимости п, эффективно «возвращая» значение потоку-преемнику.

Входы

Два оставшихся ключевых слова Cilk немного более продвинуты и касаются использования входы. Обычно, когда порождается процедура Cilk, она может вернуть свои результаты родительской процедуре, только поместив эти результаты в переменную в родительском фрейме, поскольку мы присвоили результаты вызовов порожденных процедур в этом примере Икс и у.

Альтернативой является использование впускного отверстия. Вход - это внутренняя функция процедуры Cilk, которая обрабатывает результаты вызова порожденной процедуры по мере их возврата. Одна из основных причин использования входных отверстий заключается в том, что все входные отверстия процедуры гарантированно работают. атомарно в отношении друг друга и родительской процедуры, что позволяет избежать ошибок, которые могут возникнуть, если несколько возвращающих процедур попытаются обновить одни и те же переменные в родительском фрейме одновременно.

• В вход ключевое слово определяет функцию, определенную в процедуре как вход.
• В прервать ключевое слово может использоваться только внутри входа; он сообщает планировщику, что любые другие процедуры, порожденные родительской процедурой, можно безопасно прервать.

Впускные отверстия были удалены, когда Cilk стал Cilk ++, и их нет в Cilk Plus.

Параллельные петли

Cilk ++ добавил дополнительную конструкцию, параллельный цикл, обозначенный cilk_for в Силк Плюс. Эти петли выглядят как

1 пустота петля(int *а, int п)2 {3     #pragma cilk grainsize = 100 // необязательный4     cilk_for (int я = 0; я < п; я++) {5         а[я] = ж(а[я]);6     }7 }

Это реализует параллельная карта идиома: тело цикла, здесь вызов ж с последующим присвоением массиву а, выполняется для каждого значения я с нуля до п в неопределенном порядке. Необязательный «размер зерна» прагма определяет огрубение: любой подмассив из ста или менее элементов обрабатывается последовательно. Хотя спецификация Cilk не определяет точное поведение конструкции, типичная реализация представляет собой рекурсию «разделяй и властвуй»,^[14] как если бы программист написал

статический пустота рекурсия(int *а, int Начните, int конец){    если (конец - Начните <= 100) {  // Здесь 100 - размер зерна.        за (int я = Начните; я < конец; я++) {            а[я] = ж(а[я]);        }    }    еще {        int середина = Начните + (конец - Начните) / 2;        cilk_spawn рекурсия(а, Начните, середина);        рекурсия(а, середина, конец);        cilk_sync;    }}пустота петля(int *а, int п){    рекурсия(а, 0, п);}

Причины создания программы «разделяй и властвуй», а не очевидной альтернативы, цикла, который порождает тело цикла как функцию, лежат как в обработке размера зерна, так и в эффективности: выполнение всего порождения в одной задаче вызывает загрузку устранение узких мест.^[15]

Обзор различных конструкций параллельного цикла на HPCwire показал, что cilk_for конструкция будет довольно общей, но отметила, что спецификация Cilk Plus не оговаривала, что ее итерации должны быть независимыми от данных, поэтому компилятор не может автоматически векторизовать а cilk_for петля. В обзоре также отмечен тот факт, что сокращения (например, суммы по массивам) требуют дополнительного кода.^[14]

Редукторы и гиперобъекты

Cilk ++ добавил объект под названием гиперобъекты, что позволяет нескольким цепям совместно использовать состояние без условия гонки и без использования явных блокировок. Каждая нить имеет вид гиперобъекта, который он может использовать и обновлять; когда потоки синхронизируются, представления объединяются способом, указанным программистом.^[16]

Наиболее распространенный тип гиперобъекта - редуктор, который соответствует предложению редукции в OpenMP или к алгебраическому понятию моноид. Каждый редуктор имеет элемент идентичности и ассоциативная операция который сочетает в себе две ценности. Архетипический редуктор суммирование чисел: единичный элемент равен нулю, а ассоциативный уменьшать операция вычисляет сумму. Этот редуктор встроен в Cilk ++ и Cilk Plus:

// Вычислить ∑ foo (i) для i от 0 до N, параллельно.шелк::reducer_opadd<плавать> результат(0);cilk_for (int я = 0; я < N; я++)    результат += фу(я);

Другие редукторы могут быть использованы для построения связанные списки или строки, и программисты могут определять собственные редукторы.

Ограничение гиперобъектов состоит в том, что они предоставляют только ограниченное определенность. Буркхардт и другие. укажите, что даже редуктор сумм может привести к недетерминированному поведению, показывая программу, которая может производить либо 1 или же 2 в зависимости от порядка расписания:^[17]

пустота add1(шелк::reducer_opadd<int> &р) { р++; }// ...шелк::reducer_opadd<int> р(0);cilk_spawn add1(р);если (р == 0) { р++; }cilk_sync;выход(р.get_value());

Обозначение массива

Intel Cilk Plus добавляет нотацию для выражения высокого уровня операции над целыми массивами или же разделы массивов; например, Axpy функция в стиле, которая обычно пишется

 // y ← α x + y пустота Axpy(int п, плавать альфа, const плавать *Икс, плавать *у) {     за (int я = 0; я < п; я++) {         у[я] += альфа * Икс[я];     } }

может быть выражено в Cilk Plus как

y [0: n] + = альфа * x [0: n];

Эта нотация помогает компилятору эффективно векторизовать приложение. Intel Cilk Plus позволяет применять операции C / C ++ к нескольким элементам массива параллельно, а также предоставляет набор встроенных функций, которые можно использовать для выполнения векторизованных сдвигов, поворотов и сокращений. Аналогичная функциональность существует в Фортран 90; Cilk Plus отличается тем, что никогда не выделяет временные массивы, поэтому использование памяти легче предсказать.

Элементарные функции

В Cilk Plus элементарная функция - это обычная функция, которую можно вызывать либо для скалярных аргументов, либо для элементов массива параллельно. Они похожи на функции ядра OpenCL.

#pragma simd

Эта прагма дает компилятору разрешение на векторизацию цикла даже в тех случаях, когда автоматическая векторизация может дать сбой. Это самый простой способ применить векторизацию вручную.

Работа-кража

Планировщик Cilk использует политику под названием «кража работы» для эффективного разделения выполнения процедуры между несколькими процессорами. Опять же, проще всего понять, если мы сначала посмотрим, как код Cilk выполняется на однопроцессорной машине.

Процессор поддерживает куча на который он помещает каждый кадр, который он должен приостановить, чтобы обработать вызов процедуры. Если он выполняется фиб (2), и встречает рекурсивный вызов фиб (1), это спасет фиб (2)состояние, включая его переменные и место, где код приостановил выполнение, и помещает это состояние в стек. Он не будет брать приостановленное состояние из стека и возобновлять выполнение до тех пор, пока вызов процедуры, вызвавший приостановку, и все процедуры, вызываемые в свою очередь этой процедурой, не будут полностью выполнены.

Конечно, при использовании нескольких процессоров все меняется. У каждого процессора по-прежнему есть стек для хранения кадров, выполнение которых было приостановлено; однако эти стеки больше похожи на дек, при этом приостановленные состояния могут быть удалены с любого конца. Процессор может по-прежнему удалять состояния только из своего собственный укладывать с того же конца, на который они ставятся; однако любой процессор, который в настоящее время не работает (завершив свою работу или еще не назначенный), выберет другой процессор случайным образом через планировщик и попытается «украсть» работу с противоположного конца своего стека - приостановленные состояния, которые затем может начать исполнять процессор. Состояния, которые были украдены, - это состояния, из которых украденный процессор будет выполняться последним.

Смотрите также

• Grand Central Dispatch
• Коллекции Intel Concurrent (ЧПУ)
• Строительные блоки Intel Parallel (PBB)
  • Строительные блоки Intel Array (ArBB)
• Intel Parallel Studio
• NESL
• OpenMP
• Параллельные вычисления
• Система параллельного программирования Sieve C ++
• Заправка строительных блоков (TBB)
• Унифицированный параллельный C

Рекомендации

внешняя ссылка

• Официальный веб-сайт для Силк Плюс
• Сайт Cilk Project в Массачусетском технологическом институте
• Арч Д. Робисон, «Cilk Plus: языковая поддержка потокового и векторного параллелизма» и «Параллельное программирование с Cilk Plus», 16 июля 2012 г.