Intel Cilk Plus

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:15, 1 июня 2016.
Intel Cilk Plus
Парадигма императивный, структурированный, параллельное программирование
Спроектировано Лаборатория CS в MIT
Первый   появившийся 1994
Печать дисциплины статическая
Лицензия открытый исходный код для оригинального Cilk проприетарная для Cilk++ и Intel Cilk Plus
Портал: http://cilk.com/
Диалект
Cilk, Cilk++
Под влиянием
С

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

Разрабатывался с 1994 года в лаборатории Информатики MIT. Основан на языке ANSI C, с добавлением небольшого количества ключевых слов Cilk. Позже был расширен на Си++, в виде Cilk++ — коммерческого продукта, разрабатываемого компанией Cilk Arts.

В 2009 году компанией Cilk Arts было объявлено о том, что все её продукты и сама команда разработчиков становятся частью корпорации Интел.

История

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

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

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

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

Особенности Cilk

  • Ключевые слова, добавленные в языки C/C++, чтобы указывать на параллельные задачи в приложении.
  • Механизм для устранения разногласий по общим переменным без блокировочным способом.
  • Директива компилятора #pragma simd, указывающая, что цикл содержит параллелизм данных и должен быть векторизован.
  • Дополнение к языкам C/C++, указывающее параллелизм данных для массивов или их участков.
  • Аннотация, указывающая, что функция может быть вызвана с массивом или его частью в качестве аргументов, так же как и со скалярными величинами.

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

Параллелизм задач: spawn и sync

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

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

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

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

 1 cilk int fib(int n)
 2 {
 3     if (n < 2) {
 4         return n;
 5     }
 6     else {
 7        int x, y;
 8  
 9        x = spawn fib(n - 1);
10        y = spawn fib(n - 2);
11  
12        sync;
13  
14        return x + y;
15     }
16 }

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

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

Если процессор выполняя fib(2) дойдет до строки 14 до того, как оба других процессора завершили свои кадры, то он сгенерирует неверный результат или ошибку; fib(2) будет пытаться сложить значения хранящиеся в x и y, но один из них или оба будут отсутствовать. Разрешить эту проблему - цель ключевого слова sync, которое использовано в строке 12. Это ключевое слово говорит процессору выполняющему кадр, что он должен приостановиться до тех пор, пока все порожденные им процедурные вызовы не будут завершены. Выполнение fib(2) может быть продолжено на операторе sync (строка 12) только после того, как fib(1) и fib(0) будут завершены, а их результаты сохранены в x и y, делая безопасной работу с этими переменными.

Захват работы (Work-stealing)

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

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

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

Ключевое слово Inlet

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

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

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

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

Наиболее распространённым типом гиперобъектов является редуктор, который соответствует описанию в 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);

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

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

void add1(cilk::reducer_opadd<int> &amp;r) { r++; }
// ...
cilk::reducer_opadd<int> r(0);
cilk_spawn add1(r);
if (r == 0) { r++; }
cilk_sync;
output(r.get_value());

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

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

void loop(int *a, int n)
{
    #pragma cilk grainsize = 100  /* опционально */
    cilk_for (int i = 0; i < n; i++) {
        a[i] = f(a[i]);
    }
}

Реализация параллельной идиомы: тело цикла это вызов f следующий за присвоением массиву a, выполняется для каждого i от нуля до n в неопределённом порядке. Дополнительная директива "grain size" работает так: работа не будет порождаться пока меньше чем 100 элементов потребуют обработки. Реализация рекурсии по принципу разделяй и властвуй:

static void recursion(int *a, int start, int end)
{
    if (end - start <= 100) {  // 100 это 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);
}

Массивы

Intel Cilk Plus добавляет обозначения, которые позволяют пользователям выражать высокоуровневые операции на массивах или их частях, например:

 // 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 отличается тем, что он никогда не выделяет временные массивы, таким образом использование памяти легче предугадывается.

#pragma simdt

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

References

  1. Оффициальный сайт Cilk Plus
  2. Сайт Cilk Project в MIT
  3. Intel Cilk Plus Developer Zone

Автор статьи: Фадеев П.В.