Intel® CilkTM Plus – общая характеристика и ключевые слова

Презентацию к лекции Вы можете скачать здесь.

Intel® CilkTM Plus

Intel® CilkTM Plus поддерживается компиляторами:

Мультиплатформенность (Windows и Linux).

Ориентирован на "обычные" процессоры Intel, а также на ускоритель MIC (Many-Integrated-Core). GPGPU (графические ускорители) не поддерживаются.

Удобные средства работы с массивами (расширенная индексная нотация – аналог сечений массивов в языке Fortran).

Удобное использование векторных расширений команд, векторизация функций.

В Intel® CilkTM Plus сохраняется семантика последовательной программы.

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

Параллельное выполнение возможно, если это допускает целевая платформа (достаточное количество ядер).

Пример

#include <cilk/cilk.h>
 void sample_qsort(int * begin, int * end)
{
  if (begin != end) {
  --end;
  int * middle = std::partition(begin, end,
    std::bind2nd(std::less<int>(),*end));
  std::swap(*end, *middle); // pivot to middle
  cilk_spawn sample_qsort(begin, middle);
  sample_qsort(++middle, ++end); // Exclude pivot
  cilk_sync;
,     }
}

Модель программирования Intel® CilkTM Plus

Модель программирования Intel® CilkTM Plus основана на параллелизме задач.

Программа пишется в семантике последовательного программирования. Фрагменты для распараллеливания расщепляются на подзадачи, связанные отношениями подчинения ("родитель"-"потомок"). Такая реализация параллелизма иногда называется "fork-join".

Программист, использующий CilkTM Plus должен думать о том, что следует распараллелить, а не как. В этом – одно из отличий от OpenMP-программирования.

Балансировкой занимается runtime-система. Балансировка выполняется методом захвата работы. Алгоритмы диспетчеризации таковы, что их эффективность, как правило, высока.

Программист

Определяет и описывает потенциальный параллелизм.

Планировщик

Отображает его на реально существующую конфигурацию потоков.

Задачи связаны между собой отношениями подчинения. Конфигурацию приложения во время его выполнения можно изобразить в виде направленного ациклического графа (DAG).

Граф задач в Cilk-программе является динамическим – он создается и изменяется в процессе выполнения программы.

При выполнении параллельной Cilk-программы формируется очередь задач. Выполнением задач занимаются "исполнители" (workers). Это- потоки.

Их число задается с помощью переменной окружения CILK_NWORKERS:

export CILK_NWORKERS=4 (Linux/bash)

Распределение задач между потоками выполняется методом "захвата работы" – освободившийся поток выполняет очередную задачу.

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

Сериализация (выполнение программы в последовательном режиме) происходит, если степень параллелизма целевой платформы недостаточно велика.

Сериализация также происходит при использовании заголовочного файла <cilk/cilk_stub.h> и при компиляции с соответствующим ключом:

icc: -cilk-serialize
icl: /Qcilk-serialize

В Microsoft Visual Studio сериализовать Cilk-программу можно так:

Properties -> C/C++ -> Language [Intel C++] -> Replace Intel Cilk Plus Keywords with Serial Equivalent

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

Диспетчеризация основана на "жадных" (greedy) алгоритмах.

Структура Intel® CilkTM Plus

Ключевые слова (всего 3!):

Низкие накладные расходы.

Гиперобъекты (редукторы)

Редукторы – "параллельные" глобальные переменные, позволяющие избежать гонок за данными и блокировок.

Эффективное управление редукторами обеспечивается системой исполнения Cilk-программ

Функции прикладного программного интерфейса (API)

Расширенная индексная нотация

Отличает CilkTM Plus от CilkTM.

Удобная запись операций с массивами.

Более высокая эффективность операций с массивами (компилятор порождает исполняемый код, использующий векторные инструкции).

Сходство с сечениями массивов языка Fortran, при различии в синтаксисе и реализации.

if (a[:] > b[:]) {
c[:] = d[:] * e[:];
} else {
c[:] = d[:] * 2;
}

Элементные (векторные) функции

Элементные функции обеспечивают векторизацию вычисления математических функций.

Аргументы элементных функций – векторы значений.

Возвращается вектор результата, конформный векторному аргументу.

Пример:

__declspec (vector) double heat_distribution(
double XL, double YL, double t, double sigma, double time)
{
double time_sqrt = sqrt(time);
double d1 = (log(S/K)+r*time)/(sigma*time_sqrt)+0.5*sigma*time_sqrt;
double d2 = d1-(sigma*time_sqrt);
return S*N(d1) - K*exp(-t*r)*N(d2);

Директива SIMD

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

Используются векторные регистры (AVX) процессора.

Используется векторное расширение команд процессора SSE (Streaming SIMD Extension).

Компилятор генерирует векторизованный код.

Программист гарантирует корректность векторной семантики.

Циклы остаются без изменений.

Пример

void saxpy( float a, float x[], float y[], size_t n ) {
#pragma simd
    for( size_t i=0; i<n; ++i )
        y[i] += a*x[i];
}

Файл заголовков

#include <cilk/cilk.h>

Переменные окружения

Основная - CILK_NWORKERS (количество потоков).

Ключевые слова

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

cilk_spawn является псевдонимом для _Сilk_spawn.

Обозначает точку порождения. В этой точке создается новая задача, выполнение которой может быть продолжено данным потоком или захвачено другим (параллельным) потоком.

cilk_spawn является указанием системе исполнения на то, что данная функция может (но не обязана) выполняться параллельно с функцией, из которой она вызвана.

Синтаксис (допустим любой из трех):

cilk_spawn имя_функции_потомка()
type var = cilk_spawn имя_функции_потомка()
var = cilk_spawn имя_функции_потомка()

Допускается:

var = cilk_spawn (object.*pointer)(args);

cilk_spawn []{ g(f()); }();

cilk_spawn g(f());

Два последних варианта – в первом обе функции выполняются в потомке, во втором случае сначала выполняется f(), затем – потомок.

Порождение с использованием лямбда-выражения:

cilk_spawn []{
    for( int i=0; i<n; ++i ) 
        a[i] = 0;
} ();
...
cilk_sync; 

Не допускается:

g(cilk_spawn f());

Пример:

void floyd_warshall() {
  for (int k = 0; k < n; ++k) 
    for (int i = 0; i < n; ++i)
      cilk_spawn work(k,i);
}

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

cilk_sync является псевдонимом для _Cilk_sync.

Обозначает точку синхронизации. В этой точке выполнение задач синхронизируется (барьерная синхронизация).

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

Неявно точка синхронизации присутствует в конце каждой функции.

Пример:

public:
    CilkSpawnSum(int nThreads) : _nThreads(nThreads), result(0) {}
    virtual double FindSum(SimpleArray data) {
        for(int i=0; i<_nThreads; i++) {
            cilk_spawn _SumComputer(data, 
                i * data.GetSize() / _nThreads, 
                (i+1) * data.GetSize() / _nThreads);
        }
        cilk_sync;
        return result.get_value();
    }