1 Методология императивного параллельного программирования ЛЕКЦИЯ 1 Калинина А.П.

2 СОДЕРЖАНИЕ Введение Методология императивного параллельного программирования: происхождение, теория и эволюция Методы и концепции. Синтаксис и семантика Языки параллельного программирования Класс задач Ускорение параллельной программы Закон Амдала

3 «СИСТЕМНЫЙ» ПОДХОД 1. Введение

4 Практическое параллельное программирование в системах с общей памятью Методология: императивное параллельное программирование Архитектурная платформа: SMP – система (система с общей памятью) Операционная платформа: Windows Язык и инструменты среды программирования: OpenMP (Intel C++), инструменты Intel (Thread Checker, Thread Profiler, VTune Performance Analyzer) OpenMP (Intel C++), инструменты Intel (Thread Checker, Thread Profiler, VTune Performance Analyzer) 1. Введение

5 Определение методологии Методология программирования – совокупность методов, применяемых в жизненном цикле программного обеспечения и объединенных общим философским подходом «Собрались однажды звери в лесу, чтобы строить мост через реку. Когда все обсудили, медведь спрашивает: вопросы есть? Осел: «А как будем строить – вдоль или поперек реки?» Анекдот о необходимости определяющих подходов [1] Методология как концентрация практического опыта Методология как концентрация практического опыта Алгоритмическое происхождение некоторых методологий Алгоритмическое происхождение некоторых методологий Методологии как результат отображения структур Методологии как результат отображения структур 1. Введение

6 «СИСТЕМНЫЙ ПОДХОД»: литература 1. И. Одинцов Профессиональное программирование. Системный подход. – «БХВ-Петербург» – 610 с. 2. Джин Бэкон, Тим Харрис Операционные системы. Параллельные и распределенные системы. – bhv «Питер» – 799 с education.ru/2006/reports/Kalinina.htm 1. Введение

7 «СИСТЕМНЫЙ» ПОДХОД: условия эффективного обучения Теория Теория Практические занятия Практические занятия Применение инструментов, которые будут диагностировать работу компьютера на низшем уровне Применение инструментов, которые будут диагностировать работу компьютера на низшем уровне 1.Введение

8 2. Методология императивного параллельного программирования: происхождение, теория и эволюция 2.1. Классификация по ядрам методологий 2.2. Некоторые методологии, поддерживающие параллелелизм (реализационная специфика) 2.3. Определение методологии императивного параллельного программирования 2.4. Простые примеры на основе OpenMP ( ) Происхождение, теория, эволюция

Классификация по ядрам методологий Методология императивного программирования Методология императивного программирования Методология объектно-ориентированного программирования Методология объектно-ориентированного программирования Методология функционального программирования Методология функционального программирования Методология логического программирования Методология логического программирования Методология программирования в ограничениях Методология программирования в ограничениях

Некоторые методологии, поддерживающие параллелелизм (реализационная специфика) Методология императивного параллельного программирования Методология императивного параллельного программирования Методология логического параллельного программирования Методология логического параллельного программирования Методология функционального программирования Методология функционального программирования

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

Простые примеры на основе OpenMP(1) Конструкция «параллельные секции»: параллельно, одновременно выполняются 2 цикла #pragma omp parallel sections { #pragma omp section for (i=0;i

Простые примеры на основе OpenMP(2) Параллельно выполняется каждая половина итераций каждого цикла; в конце каждого из них получается результирующее значение суммы (reduction), как сумма результатов каждого из параллельных вычислений #pragma omp parallel for reduction(+:sum_a) for (i=0;i

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

15 Пример многопроцессорной архитектуры с общей памятью(1) 2.5. Происхождение, теория, эволюция..

16 Пример многоядерной архитектуры с общей памятью(2) Intel® Core Duo Processor 2.5. Происхождение, теория, эволюция.. EXE Core FP Unit EXE Core FP Unit L2 Cache L1 Cache System Bus (667MHz, 5333MB/s) System Bus (667MHz, 5333MB/s)

17 Распределение процессов между модулями операционной системы: пример 2.5. Происхождение, теория, эволюция..

18 Параллельный язык программирования с поддержкой пользовательских потоков как потоков ядра 2.5. Происхождение, теория, эволюция...

19 3. Методы и концепции. Синтаксис и семантика 3.1. Методы и концепции 3.2. Модель вычислений параллельного программирования в контексте модели императивного программирования 3.3. Уровни параллелелизма 3.4. Взаимодействие параллельных процессов

Методы и концепции Метод синхронизации исполняемого кода Метод синхронизации исполняемого кода заключается в использовании специальных атомических операций для осуществления взаимодействия между одновременно исполняемыми фрагментами кода. заключается в использовании специальных атомических операций для осуществления взаимодействия между одновременно исполняемыми фрагментами кода. Метод поддерживается концепцией примитивов синхронизации Метод поддерживается концепцией примитивов синхронизации

Модель вычислений параллельного программирования в контексте модели императивного программирования Имеется несколько вычислителей, которые характеризуются наличием общих элементов состояния Имеется несколько вычислителей, которые характеризуются наличием общих элементов состояния Если на шаге вычислений с некоторым номером элемент состояния одного вычислителя принимал данное значение, то для любого другого вычислителя на шаге вычисления с тем же номером соответствующий элемент состояния также должен принимать данное значение Если на шаге вычислений с некоторым номером элемент состояния одного вычислителя принимал данное значение, то для любого другого вычислителя на шаге вычисления с тем же номером соответствующий элемент состояния также должен принимать данное значение Прямым аналогом оператора в данной методологии является процесс Прямым аналогом оператора в данной методологии является процесс Основное отличие этой методологии от императивной в том, что процессы могут выполняться параллельно. Основное отличие этой методологии от императивной в том, что процессы могут выполняться параллельно. Параллельная методология тесно привязана к платформе, на которой она реализуется Параллельная методология тесно привязана к платформе, на которой она реализуется Параллелизм может быть реализован как аппаратно на централизованной архитектуре, так и на распределенной Параллелизм может быть реализован как аппаратно на централизованной архитектуре, так и на распределенной 3. Методы и концепции. Синтаксис и семантика

Уровни параллелелизма В зависимости от уровня дробления выделяют следующие уровни параллелелизма: Параллелелизм на уровне микрокоманд Параллелелизм на уровне микрокоманд Параллелелизм на уровне операторов (кроме циклов) Параллелелизм на уровне операторов (кроме циклов) Параллелелизм на уровне циклов и итераций Параллелелизм на уровне циклов и итераций Параллелелизм на уровне подпрограмм, процедур и функций Параллелелизм на уровне подпрограмм, процедур и функций Параллелелизм на уровне потоков управления Параллелелизм на уровне потоков управления Параллелелизм на уровне процессов Параллелелизм на уровне процессов Параллелелизм на уровне приложений Параллелелизм на уровне приложений 3. Методы и концепции. Синтаксис и семантика

Взаимодействие параллельных процессов Семантическое представление взаимодействия параллельных процессов: Семантическое представление взаимодействия параллельных процессов: работа сети некоторых устройств, соединенных каналами, по которым текут данные работа сети некоторых устройств, соединенных каналами, по которым текут данные Каждый вычислитель производит типичные для его вычислительной модели операции: Каждый вычислитель производит типичные для его вычислительной модели операции: например, императивный вычислитель будет переходить из состояния в состояние например, императивный вычислитель будет переходить из состояния в состояние Когда процесс встречает инструкцию «принять значение из канала», он входит в состояние ожидания, когда канал пуст Когда процесс встречает инструкцию «принять значение из канала», он входит в состояние ожидания, когда канал пуст Как только в канале появляется значение, процесс его считывает и продолжает работу. Как только в канале появляется значение, процесс его считывает и продолжает работу. 3. Методы и концепции. Синтаксис и семантика

24 4. Языки параллельного программирования 4.1. Программирование на параллельном языке программирования 4.2. Программирование на широко распространенном языке программирования, который расширен распараллеливающими конструкциями 4.3. Программирование с использованием дополнительных указаний компилятору 4.4. Программирование на широко распространенном языке программирования с использованием коммуникационных библиотек 4.5. Средства автоматического распараллеливания последовательных программ такими инструментами, как компиляторы

Программирование на параллельном языке программирования Такие языки могут быть: Универсальными (например, Ada) Универсальными (например, Ada) Для конкретных типов компьютера, позволяющем эффективно транслировать программы на параллельном языке именно в эту архитектуру (например, язык Occam изначально разрабатывался для транспьютеров) Для конкретных типов компьютера, позволяющем эффективно транслировать программы на параллельном языке именно в эту архитектуру (например, язык Occam изначально разрабатывался для транспьютеров) 4. Языки параллельного программирования

Программирование на широко распространенном языке программирования, который расширен распараллеливающими конструкциями например C, C++, Pascal например C, C++, Pascal распараллеливающие конструкции на уровне языка программирования распараллеливающие конструкции на уровне языка программирования 4. Языки параллельного программирования

Программирование с использованием дополнительных указаний компилятору на уровне языка прагм на уровне языка прагм например, по стандарту OpenMP например, по стандарту OpenMP 4. Языки параллельного программирования

Программирование на широко распространенном языке программирования с использованием коммуникационных библиотек использование коммуникационных библиотек и интерфейса для организации межпроцессного взаимодействия использование коммуникационных библиотек и интерфейса для организации межпроцессного взаимодействия В этом случае конструкции параллелелизма вынесены с языкового уровня на уровень операционной системы В этом случае конструкции параллелелизма вынесены с языкового уровня на уровень операционной системы 4. Языки параллельного программирования

29 языки программирования, содержащие явные конструкции параллельного исполнения Algol-68(1968) Algol-68(1968) 1970 Concurrent Pascal(1972) 1970 Concurrent Pascal(1972) Modula-2(1978) GSP (1978) Modula-2(1978) GSP (1978) 1980 Edison (1980) Ada (1979, 1983) 1980 Edison (1980) Ada (1979, 1983) Occam(1982) Occam(1982) Concurrent Prolog(1983) Concurrent Prolog(1983) Linda(1985) Linda(1985) Oblig(1993) Oblig(1993) 4. Языки параллельного программирования

Класс задач Данная методология может очень эффективно применяться для обработки больших однородных массивов данных Данная методология может очень эффективно применяться для обработки больших однородных массивов данных Такие массивы часто встречаются в реализации вычислительных и статистических методов Такие массивы часто встречаются в реализации вычислительных и статистических методов Кроме того, методология параллельного программирования успешно применяется при моделировании, в операционных системах и системах реального времени Кроме того, методология параллельного программирования успешно применяется при моделировании, в операционных системах и системах реального времени

31 6. Ускорение параллельной программы Ускорением параллельной программы называется отношение времени работы последовательной, полностью оптимизированной программы, последовательной, полностью оптимизированной программы, к времени работы параллельной программы

32 7. Закон Амдала T(par) = T(for par)/N T(par) = T(for par)/N T(total) = T(seq) + T(for par) T(total) = T(seq) + T(for par) Закон Амдала для оценки ускорения параллельной программы Закон Амдала для оценки ускорения параллельной программы A = T(total)/( T(seq) + T(for par)/N) A = T(total)/( T(seq) + T(for par)/N) Реальное ускорение может быть меньше (более вероятно) и больше оценочного Реальное ускорение может быть меньше (более вероятно) и больше оценочного

33 Задание 1. Определить ускорение параллельной программы для примеров со слайдов 12, 13, открыв соответствующие проекты Генерацию параллельного кода можно включать – отключать с помощью вкладки Properties/C/C++/Language/Directive OpenMP Генерацию параллельного кода можно включать – отключать с помощью вкладки Properties/C/C++/Language/Directive OpenMP 2. Убедиться в правильной работе программы с помощью Tread Checker, для этого установив число итераций циклов N = 30 (Tread Checker резко замедляет время работы программы) 3. Убедиться в параллельной работе потоков с помощью Tread Profiler for OpenMP

34 Литература 1. И. Одинцов Профессиональное программирование. Системный подход. – «БХВ-Петербург» – 610 с. 2. Джин Бэкон, Тим Харрис Операционные системы. Параллельные и распределенные системы. – bhv «Питер» – 799 с.