Силк - Cilk

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

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

История

MIT Cilk

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

• Теоретическая работа по планированию многопоточных приложений.
• 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), но больше не поддерживается.

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

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 года . 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 или собственную библиотеку TBB Intel для своих потребностей в параллельном программировании.

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

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

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

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

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

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

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

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

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

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

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

cilk int fib(int n) {
    if (n < 2) {
        return n;
    }
    else {
       int x, y;

       x = spawn fib(n - 1);
       y = spawn fib(n - 2);

       sync;

       return x + y;
    }
}

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

Однако, когда код выполняется на многопроцессорной машине, выполнение происходит иначе. Один процессор запускает выполнение 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) будет пытаться добавить значения, хранящиеся в x и y , но одно или оба этих значения будут отсутствовать. Это цель ключевого слова sync , которое мы видим в строке 11: оно сообщает процессору, выполняющему фрейм, что он должен приостановить собственное выполнение до тех пор, пока все вызовы процедур, которые он порождал, не вернутся. Когда fib (2) разрешено пройти за оператором sync в строке 11, это может быть только потому, что fib (1) и fib (0) завершили и поместили свои результаты в x и y , что делает безопасным выполнение вычислений для этих полученные результаты.

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

thread fib(cont int k, int n)
{
    if (n < 2) {
        send_argument(k, n);
    }
    else {
        cont int x, y;
        spawn_next sum(k, ?x, ?y);
        spawn fib(x, n - 1);
        spawn fib(y, n - 2);
    }
}

thread sum(cont int k, int x, int y)
{
     send_argument(k, x + y);
}

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

Входы

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

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

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

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

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

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

void loop(int *a, int n)
{
    #pragma cilk grainsize = 100  // optional
    cilk_for (int i = 0; i < n; i++) {
        a[i] = f(a[i]);
    }
}

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

static void recursion(int *a, int start, int end)
{
    if (end - start <= 100) {  // The 100 here is the grainsize.
        for (int i = start; i < end; i++) {
            a[i] = f(a[i]);
        }
    }
    else {
        int midpoint = start + (end - start) / 2;
        cilk_spawn recursion(a, start, midpoint);
        recursion(a, midpoint, end);
        cilk_sync;
    }
}

void loop(int *a, int n)
{
    recursion(a, 0, n);
}

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

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

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

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

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

// Compute ∑ foo(i) for i from 0 to N, in parallel.
cilk::reducer_opadd<float> result(0);
cilk_for (int i = 0; i < N; i++)
    result += foo(i);

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

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

void add1(cilk::reducer_opadd<int> &r) { r++; }
// ...
cilk::reducer_opadd<int> r(0);
cilk_spawn add1(r);
if (r == 0) { r++; }
cilk_sync;
output(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 * x[i];
     }
 }

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

y[0:n] += alpha * 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

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

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

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