Intel® Cilk TM Plus Введение Лекция 2. Многопоточный параллелизм – от OpenMP к Intel® Cilk TM Plus Немнюгин Сергей Андреевич

2 Содержание 1.Многопоточное программирование. 2.Программирование с OpenMP. 3.Модель программирования Intel® Cilk TM Plus.

3 Многопоточная программа

4 Поток (нить) представляет собой последовательный поток управления (последовательность команд) в рамках одной программы. При создании процесса порождается главный поток, выполняющий инициализацию процесса. Он же начинает выполнение команд. Поток и процесс соотносятся следующим образом: с процессом ассоциирован главный поток, инициализирующий выполнение команд процесса; любой поток может порождать в рамках одного процесса другие потоки; каждый поток имеет собственный стек; потоки, соответствующие одному процессу, имеют общие сегменты кода и данных.

5 Конкуренция за ресурсы и параллельное исполнение Конкуренция за ресурсы (видимый параллелизм) Реальный параллелизм Поток 1

6 Для реализации реального параллелизма требуется соответствующая архитектура – многоядерная или многопроцессорная с общей памятью. При разработке многопоточных приложений возникают следующие проблемы: гонки за данными; блокировки; несбалансированность загрузки.

7 Гонки за данными (data races) Гонки за данными являются следствием зависимостей, когда несколько потоков модифицируют содержимое одной и той же области памяти. Наличие гонок за данными не всегда является очевидным. Они могут приводить к конфликтам двух типов: 1) конфликт «чтение-запись»; 2) конфликт «запись-запись». Борьба с гонками за данными: использование преимущественно локальных по отношению к потоку, а не разделяемых переменных; управление доступом к разделяемым переменным с помощью различных средств синхронизации (они могут быть реализованы с помощью семафоров, событий, критических секций, взаимных блокировок мьютексов).

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

9 Масштабируемость Число программных потоков должно совпадать с числом аппаратных потоков. Зависимость ускорения от числа потоков для теста на 2-ядерной архитектуре:

10 Программные инструменты реализации многопоточного параллелизма POSIX Threads низкоуровневые инструменты Windows API OpenMP высокоуровневые инструменты OpenCL Intel® Cilk TM Plus

11 Программирование с OpenMP (Open MultiProcessing)

12 Модель программы программа состоит из последовательных и параллельных секций; в начальный момент времени порождается основная нить, выполняющая последовательные секции программы; при входе в параллельную секцию программы выполняется операция fork, порождающая набор нитей; каждая нить имеет свой уникальный числовой идентификатор (0 для мастер-нити). Все параллельные нити исполняют один код; при выходе из параллельной секции выполняется операция join, завершающая выполнение всех нитей кроме главной.

13 OpenMP Pro возможность пошагового распараллеливания; переносимость; высокоуровневое программирование; поддержка языков Fortran и C/C++; поддержка модели параллелизма данных. Contra масштабируемость ограничена архитектурой исполнения; программист должен думать не только о том, ЧТО должно выполняться параллельно, но и КАК; побочные эффекты использования глобальных переменных.

14 Структура 1)Директивы компилятора - используются для создания потоков, распределения работы между потоками и их синхронизации. Директивы включаются в исходный текст программы. 2)Подпрограммы библиотеки времени выполнения - используются для установки и определения атрибутов потоков. Вызовы этих подпрограмм включаются в исходный текст программы. 3)Переменные окружения - используются для управления поведением параллельной программы.

15 Привязка к языкам Привязка к C/C++ В программах на языке C прагмы, имена функций и переменных окружения OpenMP начинаются с omp, omp_ или OMP_. Формат директивы: #pragma omp директива [оператор_1[, оператор_2, :]] В OpenMP-программе используется заголовочный файл omp.h. Привязка к языку Fortran В программах на языке Fortran директивы компилятора, имена подпрограмм и переменных окружения начинаются с OMP или OMP_. Формат директивы компилятора: {!|C|*}$OMP директива [оператор_1[, оператор_2, :]] Директива начинается в первой (фиксированный формат записи текста языка Fortran 77) или произвольной (свободный формат) позиции строки. Допускается продолжение директивы в следующей строке, в этом случае действует стандартное в данной версии языка правило для обозначения строки продолжения (непробельный символ в шестой позиции для фиксированного формата записи и амперсанд для свободного формата).

16 Пример #include "omp.h" #include double f(double x) { return 4.0 / (1 + x * x); } main () { const long N = ; long i; double h, sum, x; sum = 0; h = 1.0 / N; #pragma omp parallel shared(h) { #pragma omp for private(x) reduction(+:sum) for (i = 0; i < N; i++) { x = h * (i + 0.5); sum = sum + f(x); } printf("PI = %f\n", sum / N); }

17 Эффективность Эффективность приложения, распараллеленного с помощью OpenMP, зависит от баланса между выигрышем от распараллеливания и накладными расходами на организацию многопоточности, диспетчеризацию, синхронизацию и т.д. Накладные расходы parallel1.5 мкс (Intel ® Xeon 3Ггц) barrier1.0 schedule(static)1.l0 schedule(guided)6.0 schedule(dynamic)50.0 ordered0.5 single1.0 reduction2.5 Диспетчеризацией параллельной OpenMP-программы управляет программист с помощью оператора schedule. Поддерживаются три способа распределения работы между потоками: статический, динамический и «управляемый».

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

19 Модель программирования Intel® Cilk TM Plus основана на параллелизме задач. Программа пишется в семантике последовательного программирования. Фрагменты для распараллеливания расщепляются на подзадачи, связанные отношениями подчинения («родитель»-«потомок»). Такая реализация параллелизма иногда называется «fork-join». Программист, использующий Cilk TM Plus должен думать о том, что следует распараллелить, а не как. В этом – одно из отличий от OpenMP- программирования. Балансировкой занимается runtime-система. Балансировка выполняется методом захвата работы. Алгоритмы диспетчеризации таковы, что их эффективность, как правило, высока. Удобные средства работы с массивами (расширенная индексная нотация – аналог сечений массивов в языке Fortran). Удобное использование векторных расширений команд, векторизация функций.

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

21 Граф задач в Cilk-программе является динамическим – он создаётся и изменяется в процессе выполнения программы. «Ветви» - последовательные фрагменты кода. Исполняются в режимах «продолжения» и «порождения». Узлу порождения соответствуют 2 «наследника».

22 Векторные команды (SIMD)

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

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

25 В Intel® Cilk TM Plus сохраняется семантика последовательной программы. Программа может выполняться как в последовательном, так и в параллельном режимах. Параллельное выполнение возможно, если это допускает целевая платформа (достаточное количество ядер). Сериализация (выполнение программы в последовательном режиме) происходит, если степень параллелизма целевой платформы недостаточно велика. Сериализация также происходит при использовании заголовочного файла и при компиляции с соответствующим ключом: icc: -cilk-serialize icl: /Qcilk-serialize В Microsoft Visual Studio сериализовать Cilk-программу можно так: Properties C/C++ Language [Intel C++] Replace Intel Cilk Plus Keywords with Serial Equivalent

26