Программирование на Intel Cilk Plus

Программирование на Intel Cilk Plus

2-е издание, исправленное

Немнюгин С.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Программирование на Intel Cilk Plus/ С.А. Немнюгин - М.: Национальный Открытый Университет
“ИНТУИТ”, 2016

Курс представляет собой краткое введение в основы программирования на Intel® CilkTM Plus.
В курсе излагаются сведения о структуре Intel® CilkTM Plus и компонентах Cilk. Среди них
ключевые слова, расширенная индексная нотация, редукторы, элементные функции и т.д.
Рассматриваются вопросы диспетчеризации исполнения параллельной Cilk-программы, особенности
распараллеливания циклов и другие вопросы. Приводятся примеры.

(c) ООО “ИНТУИТ.РУ”, 2012-2016
(c) Немнюгин С.А., 2012-2016

3

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

В лекции описывается структура Intel® CilkTM Plus, разбирается назначение ключевых
слов языка: cilk_for, cilk_spawn и cilk_sync. Обсуждаются особенности
распараллеливания циклов.

Презентацию к лекции Вы можете скачать ссылка: здесь http://old.intuit.ru/department/se/printelcplus/1/01.zip.

Intel® CilkTM Plus

расширение языков C/C++ (ключевые слова, расширенная векторная нотация,
гиперобъекты, элементные функции);
обеспечивает эффективный и безопасный параллелизм типа “fork-join” (операция
порождения – spawn, гиперобъекты, диспетчеризация системой исполнения);
обеспечивает векторный параллелизм (векторизация операций с сечениями
массивов и элементных функций);
Fortran (в настоящее время) не поддерживается.

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

Intel (начиная с версии 12);
GCC (начиная с версии 4.7);
совместим с Microsoft Visual Studio.

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

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

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

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

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

4

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

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

Пример

#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-система. Балансировка выполняется методом
захвата работы. Алгоритмы диспетчеризации таковы, что их эффективность, как
правило, высока.

Программист

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

Планировщик

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

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

5

(DAG).

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

Ветви- последовательные фрагменты кода. Исполняются в режимах “продолжения” и
“порождения”

Узлу порождения соответствуют 2 “наследника”

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

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

export CILK_NWORKERS=4 (Linux/bash)

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

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

6

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

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

<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 Equivalen

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

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

7

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

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

cilk_spawn – порождение задачи;

cilk_for – распараллеливание цикла;

cilk_sync – синхронизация задач.

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

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

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

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

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

__cilkrts_set_param(“nworkers”, “4”)

__cilkrts_get_nworkers()

__cilkrts_get_total_workers()

__cilkrts_get_worker_number()

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

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

8

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

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

Сходство с сечениями массивов языка 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).

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

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

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

Пример

9

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 ) 

10