Силк

Силк

Парадигма	императивный ( процедурный ), структурированный , параллельный
Разработано	Массачусетского технологического института Лаборатория компьютерных наук
Разработчик	Интел
Впервые появился	1994
Дисциплина набора текста	статический , слабый , явный
Веб-сайт	шелк .с .edu
Диалекты
Cilk++, Cilk Plus, OpenCilk
Под влиянием
С
Под влиянием
ОпенМП 3.0, Район ( Rust ) библиотека

OpenCilk

Разработано	С
Разработчик	С
Впервые появился	2020
Стабильная версия	2.0.1 / 3 сентября 2022 г ( 03.09.2022 )
ТЫ	Unix-подобный , macOS
Лицензия	С
Веб-сайт	www .opencilk .org

Не путать с SYCL .

СилкПлюс

Разработано	Интел
Разработчик	Интел
Впервые появился	2010
Стабильная версия	1.2 / 9 сентября 2013 г ( 09.09.2013 )
Расширения имен файлов	(То же самое, что C или C++)
Веб-сайт	http://cilkplus.org/

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

Первоначально разработанный в 1990-х годах в Массачусетском технологическом институте (MIT) группой Чарльза Лейзерсона , Cilk позже был коммерциализирован как Cilk++ дочерней компанией Cilk Arts. Впоследствии эта компания была приобретена Intel , которая повысила совместимость с существующим кодом C и C++, получив название Cilk Plus. После того, как Intel прекратила поддержку Cilk Plus в 2017 году, MIT снова разрабатывает Cilk в форме OpenCilk.

История

Статья MIT

Язык программирования Cilk вырос из трех отдельных проектов Лаборатории компьютерных наук Массачусетского технологического института:

• Теоретическая работа по планированию многопоточных приложений.
• StarTech - программа параллельных шахмат , созданная для работы на модели Connection Machine CM-5 компании Thinking Machines Corporation.
• PCM/Threaded-C - пакет на основе C для планирования потоков в стиле продолжения передачи на CM-5.

В апреле 1994 года три проекта были объединены и получили название «Cilk». Название Cilk — это не аббревиатура, а намек на «красивые нити» ( silk ) и язык программирования C. Компилятор Cilk-1 был выпущен в сентябре 1994 года.

Исходный язык Cilk был основан на ANSI C с добавлением специфичных для Cilk ключевых слов для обозначения параллелизма. Когда ключевые слова Cilk удаляются из исходного кода Cilk, результатом всегда должна быть допустимая программа C, называемая последовательной версией (или C elision ) полной программы Cilk, с той же семантикой, что и программа Cilk, работающая на одном процессоре. Несмотря на некоторые сходства, Cilk не имеет прямого отношения к Concurrent C от AT&T Bell Labs .

Cilk был реализован как транслятор на C, ориентированный на компилятор GNU C (GCC). Последняя версия, Cilk 5.4.6, доступна в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL), но больше не поддерживается.

Демонстрацией возможностей Силка стала программа параллельной игры в шахматы Cilkchess, которая выиграла несколько призов по компьютерным шахматам в 1990-х годах, включая Открытый чемпионат Голландии по компьютерным шахматам 1996 года.

Cilk Arts и Cilk++

До c. В 2006 году рынок Cilk был ограничен высокопроизводительными компьютерами. Появление многоядерных процессоров в массовых вычислениях означало, что ежегодно поставлялись сотни миллионов новых параллельных компьютеров. Cilk Arts была создана, чтобы извлечь выгоду из этой возможности: в 2006 году Лейзерсон запустил Cilk Arts, чтобы создать и вывести на рынок современную версию Cilk, которая поддерживает коммерческие потребности будущего поколения программистов. Компания завершила раунд венчурного финансирования серии A в октябре 2007 года, а ее продукт Cilk++ 1.0 был выпущен в декабре 2008 года.

Cilk++ отличается от Cilk по нескольким причинам: поддержка C++, поддержка циклов и гиперобъектов — новая конструкция, предназначенная для решения проблем гонки данных, возникающих при параллельном доступе к глобальным переменным. Cilk++ был проприетарным программным обеспечением . Как и его предшественник, он был реализован как компилятор Cilk-to-C++. Он поддерживал компиляторы Microsoft и GNU.

Intel Cilk Plus

31 июля 2009 года компания Cilk Arts объявила на своем веб-сайте, что ее продукты и команда разработчиков теперь являются частью корпорации Intel . В начале 2010 года веб-сайт Cilk по адресу www.cilk.comначалось перенаправление на веб-сайт Intel (по состоянию на начало 2017 года исходный веб-сайт Cilk больше не преобразуется в хост). Intel и Cilk Arts интегрировали и усовершенствовали эту технологию, в результате чего в сентябре 2010 года был выпущен Intel Cilk Plus . Cilk Plus использует упрощения, предложенные Cilk Arts в Cilk++, чтобы устранить необходимость в нескольких исходных ключевых словах Cilk, а также добавить возможность создавать функции и работать с переменными, участвующими в операциях сокращения. Cilk Plus отличается от Cilk и Cilk++ добавлением расширений массива, включением в коммерческий компилятор (от Intel) и совместимостью с существующими отладчиками.

Cilk Plus был впервые реализован в компиляторе Intel C++ с выпуском компилятора Intel в Intel Composer XE 2010. Реализация с открытым исходным кодом ( под лицензией BSD ) была предоставлена ​​Intel в коллекцию компиляторов GNU (GCC), которая обеспечила поддержку Cilk Plus в версии 4.9. за исключением Ключевое слово _Cilk_for , добавленное в GCC 5.0. В феврале 2013 года Intel анонсировала Clang форк с поддержкой Cilk Plus. Компилятор Intel, но не реализации с открытым исходным кодом, поставляется с детектором гонок и анализатором производительности.

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

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

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

Cilk

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

OpenCilk

После того, как Intel отказалась от поддержки Cilk Plus, MIT взялся за разработку Cilk в реализации OpenCilk, сосредоточившись на ответвлении LLVM/Clang, которое теперь называется «Tapir». OpenCilk по-прежнему в значительной степени совместим с Intel Cilk Plus. Его первая стабильная версия была выпущена в марте 2021 года.

Языковые особенности

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

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

См. также: Модель разветвления – соединения.

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

• The Ключевое слово 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  ; 
      } 
     Еще   { 
        интервал   х  ,   у  ; 

         x   =   спавн   фиб  (  n   -   1  ); 
         y   =   спавн   фиб  (  n   -   2  ); 

         синхронизировать  ; 

         вернуть   х   +   у  ; 
      } 
 } 

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

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

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

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

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

поток   fib  (  cont   int   k  ,   int   n  ) 
 { 
     if   (  n   <   2  )   { 
         send_argument  (  k  ,   n  ); 
      } 
     Еще   { 
         продолжение   int   x  ,   y  ; 
          spawn_next   sum  (  k  ,   ?  x  ,   ?  y  ); 
          спавн   фиб  (  x  ,   n   -   1  ); 
          спаун   фиб  (  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, которая обрабатывает результаты вызова порожденной процедуры по мере их возврата. Одна из основных причин использования входов заключается в том, что все входы процедуры гарантированно работают атомарно по отношению друг к другу и к родительской процедуре, что позволяет избежать ошибок, которые могут возникнуть, если несколько возвращающих процедур попытаются обновить одни и те же переменные в родительский фрейм одновременно.

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

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

Параллельные циклы

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

void   цикл  (  int   *  a  ,   int   n  ) 
 { 
     #pragma cilk зернистость = 100  // необязательный 
     cilk_for   (  int   i   =   0  ;   i   <   n  ;   i  ++  )   { 
         a  [  i  ]   =   f  (  a  [  i  ]); 
      } 
 } 

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

static   void   recursion  (  int   *  a  ,   int   start  ,   int   end  ) 
 { 
     if   (  end   -   start   <=   100  )   {    // 100 здесь — это размер зерна. 
          for   (  int   я   =   начало  ;   я   <   конец  ;   я  ++  )   { 
             а  [  я  ]   =   ж  (  а  [  я  ]); 
          } 
     } 
     else   { 
         int   Midpoint   =   начало   +   (  конец   -   начало  )   /   2  ; 
         cilk_spawn    рекурсия  (  a  ,   начало  ,   середина  ); 
          рекурсия  (  а  ,   середина  ,   конец  ); 
          цикл_синхронизация  ; 
      } 
 } 

 void   цикл  (  int   *  a  ,   int   n  ) 
 { 
     рекурсия  (  a  ,   0  ,   n  ); 
  } 

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

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

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

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

Наиболее распространенным типом гиперобъекта является редуктор, который соответствует предложению редукции в OpenMP или алгебраическому понятию моноида . Каждый редуктор имеет элемент идентификации и ассоциативную операцию , объединяющую два значения. Типичный редуктор — это суммирование чисел: единичный элемент равен нулю, а операция ассоциативного сокращения вычисляет сумму. Этот редуктор встроен в Cilk++ и Cilk Plus:

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

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

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

void   add1  (  cilk  ::  редуктор_opadd  <  int  >   &  r  )   {   r  ++  ;    } 
 // ... 
 cilk  ::  редуктор_opadd  <  int  >   r  (  0  ); 
  cilk_spawn   add1  (  р  ); 
  если   (  р   ==   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  ]   +=   альфа   *   х  [  я  ]; 
       } 
  } 

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

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

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

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

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

#pragma SIMD

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

Кража работы

Основная статья: Кража работы

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

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

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

См. также

• Гранд Центральная диспетчерская
• Intel Concurrent Collections (CnC)
• Параллельные строительные блоки Intel (PBB)
  • Строительные блоки массивов Intel (ArBB)
• Intel Параллельная Студия
• НЭСЛ
• OpenMP
• Параллельные вычисления
• Система параллельного программирования Sieve C++
• Строительные блоки резьбы (TBB)
• Унифицированный параллельный C

Внешние ссылки

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