Нижегородский государственный университет им. Н.И. Лобачевского Кустикова В.Д., кафедра математического обеспечения ЭВМ, факультет ВМК Параллельные численные методы При поддержке компании Intel Введение в технологию Intel® Cilk Plus

2 Содержание Технология Intel® Cilk Plus Терминология Основные компоненты Intel® Cilk Plus и модели исполнения: –Ключевые слова (keywords) –Гипер-объекты или преобразователи (reducers) –Специальное представление массивов (C/C++ Extensions for Array Notation (CEAN)) –Элементарные функции (elementary functions) Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

3 Технология Intel® Cilk Plus Intel® Cilk Plus – расширение языков C и C++, которое упрощает разработку приложений, параллельных по задачам и данным в системах с общей памятью. Разрабатывался с 1994г. в лаборатории Информатики MIT ( В 2009г. выкуплен компанией Intel. Разработчики Cilk Plus предоставляют средства для организации циклического и рекурсивного («разделяй и властвуй») параллелизма. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

4 Терминология Задача – отдельная функция или итерация цикла. Обработчик (worker) – поток операционной системы, который используется планировщиком Cilk Plus для исполнения задачи. Нить (strand) – набор инструкций, выполняемых последовательно. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

5 Основные компоненты Intel® Cilk Plus Ключевые слова (cilk_for, cilk_spawn, cilk_sync). Инструмент для организации параллелизма по задачам. Гипер-объекты или преобразователи (reducers). Устраняют конкуренцию за переменные, разделяемые между задачами, создавая представление этих переменных для каждой задачи и собирая их обратно в разделяемое значение по завершении всех задач. Специальное представление массивов (C/C++ Extensions for Array Notation (CEAN)). Данный компонент обеспечивает параллелизм по данным (векторизацию). Элементарные функции. Включают параллелизм по данным для всех функций и операций со специальными массивами или их частями. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

6 Подключение возможности использования средств Intel® Cilk Plus (1) Intel® Cilk Plus поддерживается компилятором Intel® Windows C/C++ Compiler. Чтобы применить указанный компилятор, в окне Solution Explorer выберите проект. Выполните команду контекстного меню Intel® Parallel ComposerUse Intel® C++…. В диалоговом окне Confirmation нажмите OK. Кликните правой кнопкой мыши по проекту, в контекстном меню выберите пункт Properties. Выполните команду Configuration PropertiesC/C++ Language. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

7 Подключение возможности использования средств Intel® Cilk Plus (2) Для свойств Disable Intel® Cilk Plus Keywords for Serial Semantics и Disable All Intel® Language Extensions установите значение No. В исходных кодах проекта необходимо подключить заголовочные файлы. Перечень подключаемых заголовочных файлов определяется компонентами, которые будут задействованы в разработке параллельной реализации. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

8 Установка количества обработчиков #include int main() { int numThreads = 4; char nt[3]; itoa(numThreads, nt, 10); __cilkrts_set_param("nworkers", nt); … return 0; } Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

КЛЮЧЕВЫЕ СЛОВА Основные компоненты Intel® Cilk Plus Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

10 Ключевое слово cilk_spawn (1) cilk_spawn –Конструкция, которая может быть использована непосредственно перед вызовом функции, чтобы указать системе, что данная функция может выполняться параллельно с вызывающей. –Вызвавшая функция называется родительской, а вызванная – дочерней. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

11 Ключевое слово cilk_spawn (2) Использование cilk_spawn: // func() возвращает значение типа type и // принимает на вход список аргументов args type var = cilk_spawn func(args); var = cilk_spawn func(args); // func() может возвращать void cilk_spawn func(args); Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

12 Ключевое слово cilk_spawn (3) Механизм исполнения cilk_spawn: –Рекомендация планировщику Cilk Plus выполнять нити вызванной и вызывающей функций параллельно. –Решение о запуске нового обработчика для выполнения вызываемой функции принимается динамически при условии, что в системе имеются свободные ядра. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

13 Ключевое слово cilk_sync cilk_sync –Точка синхронизации обработчиков. –Используется, когда дальнейшие вычисления в родительской функции невозможны без результатов дочерней. Использование cilk_sync: cilk_sync; Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

14 Пример на cilk_spawn и cilk_sync (1) do_init_stuff(); // выполнение нити 1 cilk_spawn func3(); // создание нити 3 do_more_stuff(); // выполнение нити 2 (прод. 1) cilk_sync; do_final_stuff(); // выполнение нити Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

15 Пример на cilk_spawn и cilk_sync (2) Планировщик принимает решение о создании потока динамически при наличии доступных ядер. Существует два возможных способа исполнения этих нитей: –Последовательное выполнение нитей одним обработчиком в порядке –Параллельное выполнение нитей 2 и 3 в разных обработчиках. Сначала выполняются инструкции нити 1 в исходном потоке, затем при вызове cilk_spawn создается новый обработчик. Нить 2 продолжает выполняться в исходном потоке, а нить 3 – в новом. По завершении нитей 2 и 3 начинает работать нить 4 в исходном потоке. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

16 Ключевое слово cilk_for (1) cilk_for –Конструкция, предназначенная для распараллеливания циклов с известным количеством повторений. –Требования к циклу: Независимость итераций по данным. Тело цикла не должно содержать операторов принудительного перехода (break, continue, return). Наличие только одной переменной-счетчика. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

17 Ключевое слово cilk_for (2) Использование cilk_for: cilk_for (int i = 0; i < 1000; ++i) { //… } Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

18 Пример использования cilk_for Умножение плотной матрицы на вектор: #include double dotProd(double *a, double *b, int n); void Multiplication(double *A, double *x, int n, double *b) { cilk_for (int i = 0; i < n; i++) { b[i] = dotProd(&(A[i * n]), x, n); } Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

19 Ключевое слово cilk_for (3) Механизм исполнения cilk_for: –В процессе компиляции тело цикла конвертируется в функцию, которая вызывается рекурсивно в соответствии со стратегией «разделяй и властвуй». void run_loop(first, last) { if (last - first) < grainsize) { for (int i = first; i < last; ++i) LOOP_BODY; } else { int mid = (last-first)/2; cilk_spawn run_loop(first, mid); run_loop(mid, last); } –Планировщик автоматически распределяет поддеревья рекурсии между обработчиками. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

20 Разница между использованием cilk_for и вызовом cilk_spawn в цикле (1) Диаграмма нитей при использовании конструкции cilk_for: Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

21 Разница между использованием cilk_for и вызовом cilk_spawn в цикле (2) Диаграмма нитей при многократном вызове cilk_spawn: Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

22 Разница между использованием cilk_for и вызовом cilk_spawn в цикле (3) Недостатки многократного вызова cilk_spawn: –Несбалансированность нагрузки между обработчиками, т.к. каждый дочерний обработчик выполняет только одну итерацию. –Накладные расходы на синхронизацию. Замечание: для циклов с небольшим количеством итераций и значительными вычислениями в теле цикла разница по времени работы практически не заметна. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

ПРЕОБРАЗОВАТЕЛИ (REDUCERS) Основные компоненты Intel® Cilk Plus Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

24 Гипер-объекты или преобразователи (reducers) Преобразователь (reducer) – это переменная, которая может быть безопасно использована несколькими нитями, запущенными параллельно в разных обработчиках. Свойства преобразователей: –Обеспечивают надежный доступ к нелокальным переменным без «гонок» данных. –Не требуют явного применения примитивов взаимной блокировки разделяемых переменных. –Сохраняется последовательная семантика кода. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

25 Пример #include cilk::reducer_opadd n(1); void compute() { n++; } int main(int argc, char* argv[]) { int k = 0; // нить 1 cilk_spawn compute(); // нить 2 n++; // нить 3 – продолжение 1 cilk_sync; return 0; // нить 4 } Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

26 Пример. Нити захватываются одним обработчиком cilk::reducer_opadd n(1); void compute() { n++; } int main(int argc, char* argv[]) { int k = 0; // нить 1 cilk_spawn compute(); // нить 2 n++; // нить 3 – продолжение 1 cilk_sync; return 0; // нить 4 } n = 1 n = 2 n = 3 Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

27 Пример. Параллельные нити выполняются разными обработчиками cilk::reducer_opadd n(1); void compute() { n++; } int main(int argc, char* argv[]) { int k = 0; // нить 1 cilk_spawn compute(); // нить 2 n++; // нить 3 – продолжение 1 cilk_sync; return 0; // нить 4 } n = 1 n = 2 n = 1 Захват, инициализация n = 0 n = 1 Совмещение, n = 3 Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

СПЕЦИАЛЬНОЕ ПРЕДСТАВЛЕНИЕ МАССИВОВ (CEAN) Основные компоненты Intel® Cilk Plus Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

29 Специальное представление массивов (C/C++ Extensions for Array Notation (CEAN)) Специальное представление массивов обеспечивает параллелизм по данным за счет векторизации (SIMD). x3x2x1x0 y3y2y1y0 x3 + y3x2 + y2x1 + y1x0 + y0 + = Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

30 Объявление массивов Массив фиксированной длины: int a[28]; // auto int b[28][35]; // auto int (*p2d)[28]; // heap void example(int a[28]); Массив переменной длины: int a[n]; // auto int b[n][m]; // auto int (*p2d)[n]; // heap void example(int n, int m, int a[n][m]); Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

31 Обращение к частям массива Обозначение массивов [ : : ] –: опционально (по умолчанию stride=1) –отсутствие : : означает length=1. –: выбирает все элементы в данном измерении. Примеры: A[:]// Все элементы вектора A B[3:45]// 45 элементов вектора B, начиная с 3-его C[:][5] // Столбец 5 матрицы C D[0:3:2]// Элементы 0, 2, 4 вектора D E[0:3][0:4]// 12 элементов с E[0][0] по E[2][3] (подматрица) Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

32 Пример работы с массивами (1) #include #define LEN 8 #define BEGIN 2 #define NUM 4 void main() { int a[LEN], b[NUM]; printf("Initial array state:\n"); for (int i = 0; i < LEN; i++) { a[i] = i + 1; printf("a[%d] = %d\n", i, a[i]); } Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

33 Пример работы с массивами (2) b[:] = a[BEGIN : NUM]; printf("Save part of the array to another array\n"); // 3, 4, 5, 6 for (int i = 0; i < NUM; i++) { printf("b[%d] = %d\n", i, b[i]); } a[BEGIN : NUM] = 1; printf("Array state after assignment:\n"); // 1, 2, 1, 1, 1, 1, 7, 8 for (int i = 0; i < LEN; i++) { printf("a[%d] = %d\n", i, a[i]); } Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

ЭЛЕМЕНТАРНЫЕ ФУНКЦИИ Основные компоненты Intel® Cilk Plus Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

35 Элементарные функции (1) Редукция: –суммирование (__sec_reduce_add(a[:])); –умножение (__sec_reduce_mul(a[:])); –поиск минимального / максимального элемента (__sec_reduce_min(a[:]) / __sec_reduce_max(a[:])) –др. Применение скалярных функций ко всем элементам массива: a[:] = sin(b[:]); a[:] = pow(b[:], c); // b[:] в степени c a[:] = pow(c, b[:]); // c в степени b[:] a[:] = foo(b[:], d[:]); // foo - пользовательская функция Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

36 Элементарные функции (2) Элементарные функции могут создаваться пользователем: // объявление функции __declspec (vector) double foo(double x, double y) { return x + y; } // вызов функции a[:] = foo(b[:],d[:]); Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

37 Пример использования элементарных функций Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus #include #define LEN 8 void main() { int a[LEN] printf("Initial array state:\n"); for (int i = 0; i < LEN; i++) { a[i] = i + 1; } int sum = __sec_reduce_add(a[:]); printf("Sum of all elements = %d\n", sum); }

38 Условные выражения Пример поэлементных операций: for (int i = 0; i < n; i++) { if (a[i] > b[i]) { c[i] = a[i] - b[i]; } else { d[i] = b[i] - a[i]; } Преобразованный цикл: c[0:n] = (a[0:n] > b[0:n]) ? a[0:n] - b[0:n] : c[0:n]; d[0:n] = (a[0:n]

39 Заключение Intel® Cilk Plus – средства написания параллельных приложений в последовательной семантике. В состав Intel® Cilk Plus входят средства по распараллеливанию рекурсивных («разделяй и властвуй») алгоритмов и циклических конструкций. Intel® Cilk Plus обеспечивает автоматическое распределение нагрузки. Intel® Cilk Plus предоставляет средства организации параллелизма по данным (CEAN). Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

40 Вопросы ??? Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus

41 Авторский коллектив Кустикова Валентина Дмитриевна, ассистент кафедры Математического обеспечения ЭВМ факультета ВМК ННГУ. Н.Новгород, 2011 г.Введение в технологию Intel® Cilk Plus