СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Московский государственный университет им. М.В. Ломоносова Нижегородский государственный университет им. Н.И. Лобачевского - Национальный исследовательский университет - Всероссийская Молодежная школа по суперкомпьютерным технологиям Летняя сессия: «Суперкомпьютерное моделирование и визуализация в научных исследованиях»

Лекция. Гергель В.П., декан ВМК ННГУ Нижегородский государственный университет им. Н.И. Лобачевского - Национальный исследовательский университет - Модели и технологии программирования для высокопроизводительных вычислительных систем

Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 3 из 155 Суперкомпьютерные технологии являются базовой критической технологией, поскольку являются сегодня важнейшими во всем спектре технологий, которыми владеет человечество. Именно на их основе решаются наиболее трудные и ресурсоемкие междисциплинарные задачи современной науки, техники, промышленности и бизнеса Суперкомпьютерные технологии могут явиться сегодня локомотивом развития страны точно также, как в 30-х годах основой прогресса была авиация, в 40-х годах – атомное оружие, в х годах – ракетная техника и космос

Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 4 из 155 Модели параллельных вычислений –Показатели эффективности –Модель вычислений на основе графа информационных зависимостей –Оценки максимально-достижимого параллелизма Модели параллельных вычислительных систем –Мультипроцессоры и мультикомпьютеры –Модель разделенного глобально-адресуемого пространства –Оценка коммуникационной сложности алгоритмов Технологии параллельного программирования –Системы с распределенной памятью – технология MPI –Системы с общей памятью – технология OpenMP –Модель разделенного глобально-адресуемого пространства – язык Chapel Содержание

Модели параллельных вычислений Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма: –Оценка эффективности распараллеливания конкретных выбранных методов выполнения вычислений, –Оценка максимально возможного ускорения процесса решения рассматриваемой задачи (анализ всех возможных способов выполнения вычислений) Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 5 из 155

Ускорение (speedup) получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений, определяется величиной (величина n используется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи) Показатели эффективности параллельного алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 6 из 155

Эффективность (efficiency) использования параллельным алгоритмом процессоров при решении задачи определяется соотношением: (величина эффективности определяет среднюю долю времени выполнения параллельного алгоритма, в течение которого процессоры реально используются для решения задачи) Показатели эффективности параллельного алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 7 из 155

Замечания –Сверхлинейное (superlinear) ускорение S p (n)>p может иметь место в силу следующего ряда причин: неравноправность выполнения последовательной и параллельной программ (например, недостаток оперативной памяти), нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных, различие вычислительных схем последовательного и параллельного методов. –Показатели качества параллельных вычислений являются противоречивыми: попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) может привести к ухудшению ситуации по другому показателю. Показатели эффективности параллельного алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 8 из 155

Стоимость (cost) вычислений Стоимостно-оптимальный (cost-optimal) параллельный алгоритм - метод, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма. Показатели эффективности параллельного алгоритма Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 9 из 155

Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности Получение идеальных величин S p =p для ускорения и E p =1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач Оценка максимально достижимого параллелизма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 10 из 155

Закон Амдаля (Amdahl) Оценка максимально достижимого параллелизма Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены. Пусть f есть доля последовательных вычислений в применяемом алгоритме обработки данных. Ускорение процесса вычислений при использовании p процессоров ограничивается величиной: Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 11 из 155

Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах В наиболее простом виде модель основывается на предположениях: –время выполнения любых вычислительных операций является одинаковым и равняется 1, –передача данных между вычислительными устройствами выполняется мгновенно без каких-либо затрат времени. МОДЕЛИ ВЫЧИСЛЕНИЙ. Граф информационных зависимостей… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 12 из 155

Множество операций, выполняемые в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости могут быть представлены в виде ациклического ориентированного графа – множество вершин графа, представляющих выполняемые операции алгоритма, R – множество дуг графа; дуга r(i,j) принадлежит графу только если операция j использует результат выполнения операции i Вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода. – множество вершин графа без вершин ввода, – диаметр графа (длина максимального пути) МОДЕЛИ ВЫЧИСЛЕНИЙ. Граф информационных зависимостей… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 13 из 155

Пример: граф алгоритма вычисления площади прямоугольника, заданного координатами двух противолежащих углов МОДЕЛИ ВЫЧИСЛЕНИЙ. Граф информационных зависимостей… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 14 из 155

Операции алгоритма, между которыми нет пути в рамках выбранной схемы вычислений, могут быть выполнены параллельно Схемы вычислений обладают различными возможностями для распараллеливания, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма МОДЕЛИ ВЫЧИСЛЕНИЙ. Граф информационных зависимостей Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 15 из 155

Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание): –i - есть номер операции, –P i - есть номер процессора, –t i - есть время начала выполнения i-ой операции. Должны выполняться условия: –один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени: –к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены: МОДЕЛИ ВЫЧИСЛЕНИЙ. Схема параллельного выполнения алгоритма Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 16 из 155

Модель параллельного алгоритма: Время выполнения параллельного алгоритма с заданным расписанием: Время выполнения параллельного алгоритма с оптимальным расписанием: МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 17 из 155

Минимально возможное время решения задачи при заданном количестве процессоров (определение наилучшей вычислительной схемы): Оценка наиболее быстрого исполнения алгоритма (при использовании паракомпьютера – системы с неограниченным числом процессоров): МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 18 из 155

Время выполнения последовательного алгоритма для заданной вычислительной схемы: Время выполнения последовательного алгоритма: Время последовательного решения задачи: Подобные оценки необходимы для определения эффекта использования параллелизма МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 19 из 155

Теорема 1 Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма: МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 20 из 155

Теорема 2 Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением: где n есть количество вершин ввода в схеме алгоритма МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 21 из 155

Теорема 3 При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е. : МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 22 из 155

Теорема 4 Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма: МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 23 из 155

Теорема 5 Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T, можно достичь при количестве процессоров порядка p~T 1 /T, а именно: При меньшем количестве процессоров время выполнения алгоритма не может превышать более, чем в 2 раза, наилучшее время вычислений при имеющемся числе процессоров, т.е.: МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 24 из 155

Рекомендации –при выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (теорема 1), –для параллельного выполнения целесообразное количество процессоров определяется величиной p~T 1 /T (теорема 5), –время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5. МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 25 из 155

Строгая параллельная форма –Вершины графа помечаются одним из индексов 1,2,…,s, s

Каноническая параллельная форма –Максимальная длина пути для вершины i равна i-1 МОДЕЛИ ВЫЧИСЛЕНИЙ. Параллельные формы алгоритма… Такая форма существует и она единственна Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 27 из 155

Пример: Граф операции матричного умножения for (i=0; i

Задача нахождения частных сумм последовательности числовых значений (prefix sum problem): Задача вычисления общей суммы имеющегося набора значений: Пример: Вычисление частных сумм… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 29 из 155

Последовательный алгоритм суммирования элементов числового вектора Пример: Вычисление частных сумм… Данный " стандартный " алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 30 из 155

Пример: Вычисление частных сумм… Каскадная схема суммирования –V 2 = { (v i1,…,v ili ), 0ik, 1l i 2 -i n } есть вершины графа, –(v 01,…, v 0n ) есть операции ввода, –(v 11,…,v 1n/2 ) есть операции первой итерации и т.д., –R 2 = { (v i-1,2j-1 v ij ),(v i-1,2j v ij ), 1ik, 1l i 2 -i n } есть множество дуг графа. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 31 из 155

Пример: Вычисление частных сумм… Количество итераций каскадной схемы суммирования: Общее количество операций суммирования: При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным: Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 32 из 155

Показатели ускорения и эффективности каскадной схемы алгоритма суммирования: где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров. –время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера (теорема 2), –эффективность использования процессоров уменьшается при увеличении количества суммируемых значений: Пример: Вычисление частных сумм… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 33 из 155

Пример: Вычисление частных сумм… Модифицированная каскадная схема: –Все суммируемые значения подразделяются на (n/log 2 n) групп, в каждой из которых содержится (log 2 n) элементов; для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования; –На втором этапе для полученных (n/log 2 n) сумм отдельных групп применяется обычная каскадная схема: Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 34 из 155

Пример: Вычисление частных сумм… Для выполнения первого этапа требуется (log 2 n) выполнение параллельных операций при использовании p= (n/log 2 n) процессоров Для выполнения второго этапа необходимо log 2 (n/log 2 n)log 2 n параллельных операций для p=(n/log 2 n)/2 процессоров Время выполнения параллельного алгоритма составляет для p= (n/log 2 n) процессоров. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 35 из 155

С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями: Пример: Вычисление частных сумм… –По сравнению с обычной каскадной схемой ускорение уменьшилось в 2 раза, –Для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу: –Модифицированный каскадный алгоритм является стоимостно- оптимальным (стоимость вычислений пропорциональна времени выполнения последовательного алгоритма): Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 36 из 155

Вычисление всех частных сумм… –Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи обычного последовательного алгоритма суммирования при том же количестве операций –При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам. Пример: Вычисление частных сумм… Достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 37 из 155

Вычисление всех частных сумм… –Алгоритм, обеспечивающий получение результатов за log 2 n параллельных операций: Перед началом вычислений создается копия S вектора суммируемых значений (S=x), Далее на каждой итерации суммирования i, 1ilog 2 n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2 i-1 позиций (освобождающиеся при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q. Пример: Вычисление частных сумм… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 38 из 155

Вычисление всех частных сумм… Пример: Вычисление частных сумм… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 39 из 155

Вычисление всех частных сумм –Общее количество выполняемых алгоритмом скалярных операций определяется величиной: –Необходимое количество процессоров определяется количеством суммируемых значений: –Показатели ускорения и эффективности: Пример: Вычисление частных сумм Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 40 из 155

Закон Амдаля. Замечания –Доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания методов, –Эффект Амдаля Для большого ряда задач доля последовательных вычислений f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет увеличения вычислительной сложности решаемой задачи. В этом случае, ускорение S p = S p (n) является возрастающей функцией от параметра n. МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 41 из 155

Закон Густавсона – Барсиса… Оценим максимально достижимое ускорение исходя из имеющейся доли последовательных расчетов в выполняемых параллельных вычислениях : где (n) и (n) есть времена последовательной и параллельной частей выполняемых вычислений соответственно, т. е. С учетом введенной величины g можно получить что позволяет построить оценку для ускорения МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 42 из 155

Закон Густавсона - Барсиса Упрощение последней оценки для ускорения Оценку ускорения, получаемую в соответствии с законом Густавсона - Барсиса, еще называют ускорением масштабирования (scaled speedup), поскольку данная характеристика может показать, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач МОДЕЛИ ВЫЧИСЛЕНИЙ. Определение времени выполнения алгоритма Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 43 из 155

МОДЕЛИ ВЫЧИСЛЕНИЙ. Анализ масштабируемости параллельных вычислений... Параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 44 из 155

Накладные расходы (total overhead) появляются за счет необходимости организации взаимодействия процессоров, выполнения некоторых дополнительных действий, синхронизации параллельных вычислений и т.п. Новые выражения для времени параллельного решения задачи и получаемого при этом ускорения: Тогда эффективность использования процессоров можно выразить как МОДЕЛИ ВЫЧИСЛЕНИЙ. Анализ масштабируемости параллельных вычислений... Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 45 из 155

–Если сложность решаемой задачи является фиксированной (T 1 =const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T 0, –При фиксации числа процессоров эффективность использования процессоров можно улучшить путем повышения сложности решаемой задачи T 1, –При увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач. МОДЕЛИ ВЫЧИСЛЕНИЙ. Анализ масштабируемости параллельных вычислений... Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 46 из 155

–Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить –Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности (isoefficiency function). МОДЕЛИ ВЫЧИСЛЕНИЙ. Анализ масштабируемости параллельных вычислений Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 47 из 155

Пример: Вычисление числа … Значение числа может быть получено при помощи интеграла Для численного интегрирования применим метод прямоугольников Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 48 из 155

Распределим вычисления между p процессорами (циклическая схема) Получаемые на отдельных процессорах частные суммы должны быть просуммированы Пример: Вычисление числа … - Процессор 0 - Процессор 1 - Процессор 2 Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 49 из 155

Пример: Вычисление числа … Анализ эффективности… n – количество разбиений отрезка [0,1] Вычислительная сложность задачи W = T 1 = 6n Количество узлов сетки на отдельном процессоре m = n/p n/p + 1 Объем вычислений на отдельном процессоре W p = 6m = 6n/p + 6. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 50 из 155

Пример: Вычисление числа Анализ эффективности Время параллельного решения задачи T p = 6n/p log 2 p Ускорение Sp = T 1 / T p = 6n / (6n/p log 2 p) Эффективность Ep = 6n / (6n + 6p + plog 2 p) Функция изоэффективности W = K(pT p - W) = K(6p + plog 2 p) n = [K(6p + plog 2 p)]/6, (K=E/(1–E)) Ex.: E=0.5 при p=8 n= 12 при p=64 n=128 Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 51 из 155

Пример: Метод конечных разностей… Метод конечных разностей широко применяется для численного решения уравнений в частных производных (см. раздел 12) Рассмотрим схему (N = 2) X i,j t+1 =w(X i,j-1 t + X i,j+1 t + X i-1,j t + X i+1,j t )+(1–w) X i,j t Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 52 из 155

Каждый процессор проводит вычисления на прямоугольной подобласти с точками После выполнения каждой итерации расчета необходима синхронизация расчета Пример: Метод конечных разностей… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 53 из 155

Анализ эффективности W = T 1 = 6n 2 M (M – количество итераций) T p = 6n 2 M/p + M log 2 p Ускорение S p = T 1 / T p = 6n 2 / (6n 2 /p + log 2 p) Функция изоэффективности W = K(pT p - W) = K(plog 2 p) n 2 = [K(plog 2 p)]/6, (K=E/(1-E)) Пример: Метод конечных разностей Метод конечных разностей является более масштабируемым, чем метод прямоугольников Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 54 из 155

1. При разработке параллельных алгоритмов принципиальное значение имеет получение оценок: Максимально-возможного ускорения решения задачи, Ускорения, которое может быть получено для отдельных алгоритмов 2. Данные оценки могут быть получены на этапе исследования (разработки) алгоритмов 3. Основа для получения таких оценок – анализ графа информационных зависимостей задачи 4. Разработка параллельных алгоритмов может потребовать создания принципиально новых методов решения задач МОДЕЛИ ВЫЧИСЛЕНИЙ. Выводы Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 55 из 155

В. В. Воеводин, Вл. В. Воеводин. Параллельные вычисления. - СПб.: БХВ - Петербург, с. МОДЕЛИ ВЫЧИСЛЕНИЙ. Рекомендуемая литература Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 56 из 155

Модели параллельных вычислений Модели параллельных вычислительных систем Технологии параллельного программирования Содержание Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 57 из 155

Систематика Флинна (Flynn) –Классификация по способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных: SISD (Single Instruction, Single Data) SIMD (Single Instruction, Multiple Data) MISD (Multiple Instruction, Single Data) MIMD (Multiple Instruction, Multiple Data) Модели параллельных вычислительных систем… Практически все виды параллельных систем, несмотря на их существенную разнородность, относятся к одной группе MIMD Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 58 из 155

Детализация систематики Флинна… –Дальнейшее разделение типов многопроцессорных систем основывается на используемых способах организации оперативной памяти, –Позволяет различать два важных типа многопроцессорных систем: multiprocessors (мультипроцессоры или системы с общей разделяемой памятью), multicomputers (мультикомпьютеры или системы с распределенной памятью). Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 59 из 155

Детализация систематики Флинна… Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 60 из 155

Мультипроцессоры с использованием единой общей памяти (shared memory)… –Обеспечивается однородный доступ к памяти (uniform memory access or UMA), –Являются основой для построения: векторных параллельных процессоров (parallel vector processor or PVP). Примеры: Cray T90, симметричных мультипроцессоров (symmetric multiprocessor or SMP). Примеры: IBM eServer, Sun StarFire, HP Superdome, SGI Origin. Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 61 из 155

Мультипроцессоры с использованием единой общей памяти… Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 62 из 155

Мультипроцессоры с использованием единой общей памяти Проблемы: Доступ с разных процессоров к общим данным и обеспечение, в этой связи, однозначности (когерентности) содержимого разных кэшей (cache coherence problem), Необходимость синхронизации взаимодействия одновременно выполняемых потоков команд Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 63 из 155

Мультипроцессоры с использованием единой общей памяти… Проблема: Обеспечение однозначности (когерентности) содержимого разных кэшей (cache coherence problem) При изменении данных необходимо проверять наличие " старых " значений в кэш - памяти всех процессоров ( обеспечивается на аппаратном уровне, но становится сложным при большом количестве процессоров ) Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 64 из 155

Мультипроцессоры с использованием единой общей памяти… Проблема: Необходимость синхронизации взаимодействия одновременно выполняемых потоков команд… Пример: Пусть процессоры выполняют последовательность команд над общей переменной N (в скобках указывается значение этой переменной) Вариант исполнения 1 Вариант исполнения 2 Временная последовательность команд может быть различной – необходима синхронизация при использовании общих переменных ! N = N + 1 Печать N Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 65 из 155

Мультипроцессоры с использованием единой общей памяти… Проблема: Необходимость синхронизации взаимодействия одновременно выполняемых потоков команд… Рассмотренный пример может рассматриваться как проявление общей проблемы использования разделяемых ресурсов (общих данных, файлов, устройств и т.п.) Для организации разделения ресурсов между несколькими потоками команд необходимо иметь возможность: - определения доступности запрашиваемых ресурсов (ресурс свободен и может быть выделен для использования, ресурс уже занят одним из потоков и не может использоваться дополнительно каким-либо другим потоком); - выделения свободного ресурса одному из процессов, запросивших ресурс для использования; - приостановки (блокировки) потоков, выдавших запросы на ресурсы, занятые другими потоками. Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 66 из 155

Мультипроцессоры с использованием единой общей памяти Проблема: Необходимость синхронизации взаимодействия одновременно выполняемых потоков команд Доступ к общей переменной в рассмотренном примере в самом общем виде должен быть организован следующим образом: N = N + 1 Печать N Полное рассмотрение проблемы синхронизации будет выполнено позднее при изучении вопросов параллельного программирования для вычислительных систем с общей памятью Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 67 из 155

Мультипроцессоры с использованием физически распределенной памяти (distributed shared memory or DSM): –Неоднородный доступ к памяти (non-uniform memory access or NUMA), –Среди систем такого типа выделяют: cache-only memory architecture or COMA (системы KSR-1 и DDM), cache-coherent NUMA or CC-NUMA (системы SGI Origin 2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000), non-cache coherent NUMA or NCC-NUMA (система Cray T3E). Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 68 из 155

Мультипроцессоры с использованием физически распределенной памяти… Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 69 из 155

Мультипроцессоры с использованием физически распределенной памяти: –Упрощаются проблемы создания мультипроцессоров (известны примеры систем с несколькими тысячами процессоров), –Возникают проблемы эффективного использования распределенной памяти (время доступа к локальной и удаленной памяти может различаться на несколько порядков). Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 70 из 155

Мультипроцессоры с использованием физически распределенной памяти – разделенное глобально- адресуемое пространство (partitioned global address space, PGAS) Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 71 из 155

Мультикомпьютеры… –Не обеспечивают общий доступ ко всей имеющейся в системах памяти (no-remote memory access or NORMA), –Каждый процессор системы может использовать только свою локальную память, –Для доступа к данным, располагаемых на других процессорах, необходимо явно выполнить операции передачи сообщений (message passing operations). Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 72 из 155

Мультикомпьютеры… Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 73 из 155

Мультикомпьютеры Данный подход используется при построении двух важных типов многопроцессорных вычислительных систем: –массивно-параллельных систем (massively parallel processor or MPP), например: IBM RS/6000 SP2, Intel PARAGON, ASCI Red, транспьютерные системы Parsytec, –кластеров (clusters), например: AC3 Velocity и NCSA NT Supercluster. Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 74 из 155

Мультикомпьютеры. Кластеры… Кластер - множество отдельных компьютеров, объединенных в сеть, для которых при помощи специальных аппаратно-программных средств обеспечивается возможность унифицированного управления (single system image), надежного функционирования (availability) и эффективного использования (performance) Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 75 из 155

Мультикомпьютеры. Кластеры… Преимущества: –Могут быть образованы на базе уже существующих у потребителей отдельных компьютеров, либо же сконструированы из типовых компьютерных элементов; –Повышение вычислительной мощности отдельных процессоров позволяет строить кластеры из сравнительно небольшого количества отдельных компьютеров (lowly parallel processing), –Для параллельного выполнения в алгоритмах достаточно выделять только крупные независимые части расчетов (coarse granularity). Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 76 из 155

Мультикомпьютеры. Кластеры Недостатки: –Организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, –Дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ (низкая интенсивность потоков передачи данных) Модели параллельных вычислительных систем… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 77 из 155

Характеристика типовых схем коммуникации… При организации параллельных вычислений в мультикомпьютерах для взаимодействия, синхронизации и взаимоисключения параллельно выполняемых процессов используется передача данных между процессорами вычислительной среды Топология сети передачи данных - структура линий коммутации между процессорами вычислительной системы Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 78 из 155

Топология сети передачи данных… –полный граф (completely-connected graph or clique) – система, в которой между любой парой процессоров существует прямая линия связи, –линейка (linear array or farm) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними, Характеристика типовых схем коммуникации… Полный граф (completely- connected graph or clique ) Линейка (linear array or farm ) Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 79 из 155

Топология сети передачи данных… –кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки, –звезда (star) – система, в которой все процессоры имеют линии связи с некоторым управляющим процессором, Характеристика типовых схем коммуникации… Кольцо (ring ) Звезда (star ) Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 80 из 155

Топология сети передачи данных… –решетка (mesh) – система, в которой граф линий связи образует прямоугольную сетку, –гиперкуб (hypercube) – данная топология представляет частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора. Характеристика типовых схем коммуникации… Решетка (mesh) Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 81 из 155

Топология сети вычислительных кластеров Для построения кластерной системы во многих случаях используют коммутатор (switch), через который процессоры кластера соединяются между собой. Одновременность выполнения нескольких коммуникационных операций является ограниченной. Характеристика типовых схем коммуникации… В любой момент времени каждый процессор может принимать участие только в одной операции приема - передачи данных Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 82 из 155

Характеристики топологии сети… –диаметр – максимальное расстояние между двумя процессорами сети; характеризует максимально- необходимое время для передачи данных между процессорами, –связность (connectivity) – минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области, –ширина бинарного деления (bisection width) – минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера, –стоимость – общее количество линий передачи данных в многопроцессорной вычислительной системе. Характеристика типовых схем коммуникации… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 83 из 155

Характеристики топологии сети ТопологияДиаметрШирина бисекции СвязностьСтоимость Полный граф1p 2 /4(p-1)p(p-1)/2 Звезда211(p-1) Линейкаp-111(p-1) Кольцо22p Гиперкубlog 2 pp/2log 2 pp log 2 p/2 Решетка (N=2)42p Характеристика типовых схем коммуникации Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 84 из 155

Модель Хокни для оценки времени передачи данных: где - α - латентность сети передачи данных, - β - пропускная способность сети, - m – объем передаваемых данных Оценка трудоемкости операций передачи данных Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 85 из 155

Пример: Матричное умножение… Умножение матриц: или Задача умножения матриц может быть сведена к выполнению m·n независимых операций умножения строк матрицы A на столбцы матрицы B В основу организации параллельных вычислений может быть положен принцип распараллеливания по данным Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 86 из 155

Непрерывное (последовательное) распределение Способы распределения данных: ленточная схема горизонтальные полосы вертикальные полосы Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 87 из 155

Распределение данных – ленточная схема (разбиение матрицы A по строкам и матрицы B по столбцам) Базовая подзадача (агрегация) - процедура вычисления всех элементов одной из строк матрицы С (количество подзадач равно n) Параллельный алгоритм: ленточная схема… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 88 из 155

Общая схема алгоритма –Каждая подзадача содержит по одной строке матрицы А и одному столбцу матрицы В, –На каждой итерации проводится скалярное умножение содержащихся в подзадачах строк и столбцов, что приводит к получению соответствующих элементов результирующей матрицы С, –На каждой итерации каждая подзадача i, 0 i

Схема информационного взаимодействия Параллельный алгоритм: ленточная схема… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 90 из 155

Анализ эффективности –Общая оценка показателей ускорения и эффективности Параллельный алгоритм: ленточная схема… Разработанный способ параллельных вычислений позволяет достичь идеальных показателей ускорения и эффективности Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 91 из 155

Анализ эффективности ( уточненные оценки ) - Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет - Оценка трудоемкости выполняемых операций передачи данных может быть определена как Общее время выполнения параллельного алгоритма составляет Параллельный алгоритм: ленточная схема… (предполагается, что все операции передачи данных между процессорами в ходе одной итерации алгоритма могут быть выполнены параллельно) Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 92 из 155

Результаты вычислительных экспериментов –Сравнение теоретических оценок и экспериментальных данных Параллельный алгоритм: ленточная схема… Размер матрицы 2 процессора4 процессора8 процессоров МодельЭкспериментМодельЭкспериментМодельЭксперимент 500 0,8243 0,3758 0,4313 0,1555 0,2353 0, ,518225,44273,33492,26281,74360, ,913720,950311,127011,08045,73405, ,842945,743626,223621,600113,41449, ,137799,509751,040856,920325,992818, , ,923287, ,964244,677245,5482 Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 93 из 155

1. Основные типы параллельных вычислительных систем – мультипроцессоры и мультикомпьютеры 2. Ограниченность масштабирования SMP-узлов; возможность расширения количества процессоров на счет неоднородного доступа к памяти 3. Учет неоднородного доступа к памяти в модели разделенного глобально-адресуемого пространства (PGAS) 4. Основной способ построения мультикомпьютеров – кластеры, создаваемых на основе типовых процессоров и сетей передачи данных 5. Кластеры, как правило, имеют многоуровневую структуру построения – многоядерные процессоры, многопроцессорные узлы, многоуровневые сети передачи данных За пределами рассмотрения остались вопросы учета неоднородности вычислительных элементов (ускорители, графические процессоры и т.п.) МОДЕЛИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. Выводы Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 94 из 155

1. Patterson, D.A., Hennessy J.L. Computer Architecture: A Quantitative Approach. 2d ed. - San Francisco: Morgan Kaufmann А. В. Богданов, В. В. Корхов, В. В. Мареев, Е. Н. Станкова. Архитектуры и топологии многопроцессорных вычислительных систем. Курс лекций. М.: Интернет - университет информационных технологий, 2004 г. 3. В. П. Гергель. Теория и практика параллельных вычислений. – М.: Бином. Лаборатория знаний, Интернет - университет информационных технологий, – 424 с. МОДЕЛИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. Рекомендуемая литература Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 95 из 155

Модели параллельных вычислений Модели параллельных вычислительных систем Технологии параллельного программирования Содержание Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 96 из 155

Использование библиотек для существующих языков программирования – MPI для C и Fortran для систем с распределенной памятью Использование надъязыковых средств (директив, комментариев) - OpenMP для C и Fortran для систем с общей памятью Расширение существующих языков программирования – например, UPC Создание новых – параллельных – языков программирования – например, Chapel, X10, Fortress,… Подходы к разработке параллельных программ Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 97 из 155

Разработка параллельных программ для систем с распределенной памятью: MPI… –распределять вычислительную нагрузку, –организовать информационное взаимодействие (передачу данных) между процессорами. Решение всех перечисленных вопросов обеспечивает MPI - интерфейс передачи данных (message passing interface) В вычислительных системах с распределенной памятью процессоры работают независимо друг от друга. Для организации параллельных вычислений необходимо уметь: Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 98 из 155

В рамках MPI для решения задачи разрабатывается одна программа, она запускается на выполнение одновременно на всех имеющихся процессорах Для организации различных вычислений на разных процессорах: –Есть возможность подставлять разные данные для программы на разных процессорах, –Имеются средства для идентификации процессора, на котором выполняется программа Такой способ организации параллельных вычислений обычно именуется как модель "одна программа множество процессов" (single program multiple processes or SPMP) Разработка параллельных программ для систем с распределенной памятью: MPI… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 99 из 155

В MPI существует множество операций передачи данных: –Обеспечиваются разные способы пересылки данных, –Реализованы практически все основные коммуникационные операции. Эти возможности являются наиболее сильной стороной MPI (об этом, в частности, свидетельствует и само название MPI) Разработка параллельных программ для систем с распределенной памятью: MPI… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 100 из 155

Что означает MPI? MPI - это стандарт, которому должны удовлетворять средства организации передачи сообщений. MPI – это программные средства, которые обеспечивают возможность передачи сообщений и при этом соответствуют всем требованиям стандарта MPI: –программные средства должны быть организованы в виде библиотек программных модулей (библиотеки MPI), –должны быть доступны для наиболее широко используемых алгоритмических языков C и Fortran. Разработка параллельных программ для систем с распределенной памятью: MPI… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 101 из 155

Достоинства MPI MPI позволяет существенно снизить остроту проблемы переносимости параллельных программ между разными компьютерными системами. MPI содействует повышению эффективности параллельных вычислений - практически для каждого типа вычислительных систем существуют реализации библиотек MPI. MPI уменьшает сложность разработки параллельных программ: –большая часть основных операций передачи данных предусматривается стандартом MPI, –имеется большое количество библиотек параллельных методов, созданных с использованием MPI. Разработка параллельных программ для систем с распределенной памятью: MPI… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 102 из 155

MPI: основные понятия и определения… Понятие параллельной программы Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов: –Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP), –Процессы могут выполняться на разных процессорах; вместе с этим, на одном процессоре могут располагаться несколько процессов. Исходный программный код разрабатывается на алгоритмических языках C или Fortran с использованием библиотеки MPI. Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI программ. Все процессы программы последовательно перенумерованы. Номер процесса именуется рангом процесса. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 103 из 155

MPI: основные понятия и определения… В основу MPI положены четыре основные концепции: Операции передачи сообщения Типы данных, пересылаемых в сообщении Понятие коммуникатора (группы процессов) Понятие виртуальной топологии Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 104 из 155

MPI: основные понятия и определения… Операции передачи данных Основу MPI составляют операции передачи сообщений. Среди предусмотренных в составе MPI функций различаются: –парные (point-to-point) операции между двумя процессами, –коллективные (collective) коммуникационные действия для одновременного взаимодействия нескольких процессов. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 105 из 155

MPI: основные понятия и определения… Понятие коммуникаторов… Коммуникатор в MPI - специально создаваемый служебный объект, объединяющий в своем составе группу процессов и ряд дополнительных параметров (контекст): –парные операции передачи данных выполняются для процессов, принадлежащих одному и тому же коммуникатору, –Коллективные операции применяются одновременно для всех процессов коммуникатора. Указание используемого коммуникатора является обязательным для операций передачи данных в MPI. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 106 из 155

MPI: основные понятия и определения… Понятие коммуникаторов В ходе вычислений могут создаваться новые и удаляться существующие коммуникаторы. Один и тот же процесс может принадлежать разным коммуникаторам. Все имеющиеся в параллельной программе процессы входят в состав создаваемого по умолчанию коммуникатора с идентификатором MPI_COMM_WORLD. При необходимости передачи данных между процессами из разных групп необходимо создавать глобальный коммуникатор (intercommunicator). Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 107 из 155

MPI: основные понятия и определения… Типы данных При выполнении операций передачи сообщений для указания передаваемых или получаемых данных в функциях MPI необходимо указывать тип пересылаемых данных. MPI содержит большой набор базовых типов данных, во многом совпадающих с типами данных в алгоритмических языках C и Fortran. В MPI имеются возможности для создания новых производных типов данных для более точного и краткого описания содержимого пересылаемых сообщений. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 108 из 155

MPI: основные понятия и определения Виртуальные топологии Логическая топология линий связи между процессами имеет структуру полного графа (независимо от наличия реальных физических каналов связи между процессорами). В MPI имеется возможность представления множества процессов в виде решетки произвольной размерности. При этом, граничные процессы решеток могут быть объявлены соседними и, тем самым, на основе решеток могут быть определены структуры типа тор. В MPI имеются средства и для формирования логических (виртуальных) топологий любого требуемого типа. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 109 из 155

MPI: Пример программы #include " mpi.h " int main(int argc, char* argv[]) { int ProcNum, ProcRank, RecvRank; MPI_Status Status; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); if ( ProcRank != 0 ) // Действия для всех процессов, кроме процесса 0 MPI_Send(&ProcRank,1,MPI_INT,0,0,MPI_COMM_WORLD); else { // Действия для процесса 0 printf ("\n Hello from process %3d", ProcRank); for ( int i=1; i < ProcNum; i++ ) { MPI_Recv(&RecvRank, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &Status); printf("\n Hello from process %3d", RecvRank); } // Завершение работы MPI_Finalize(); return 0; } Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 110 из 155

MPI: Дополнительная информация 1. В. П. Гергель. Теория и практика параллельных вычислений. – М.: Бином. Лаборатория знаний, Интернет-университет информационных технологий, – 424 с. 2. А.С.Антонов. Параллельное программирование с использованием технологии MPI: Учебное пособие. - М.: Изд-во МГУ, с. 3. С.А.Немнюгин, О.Л.Стесик. Параллельное программирование для многопроцессорных вычислительных систем. - БХВ-Петербург, 2002, 400 с. Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 111 из 155

Интерфейс OpenMP задуман как стандарт параллельного программирования для многопроцессорных систем с общей памятью (SMP, ccNUMA, …) В общем вид системы с общей памятью описываются в виде модели параллельного компьютера с произвольным доступом к памяти (parallel random-access machine – PRAM) Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 112 из 155

Основы подхода Для указания возможности распараллеливания программист вносит в текст программы указания в виде директив или комментариев Исходный текст программы остается неизменным – компилятор может проигнорировать добавленные указания и построить, тем самым, обычную последовательную программу Компилятор, поддерживающий OpenMP, заменяет директивы параллелизма на некоторый дополнительный программный код (как правило, в виде обращений к процедурам какой-либо параллельной библиотеки) Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 113 из 155

Основания для достижения эффекта – разделяемые для параллельных процессов данные располагаются в общей памяти и для организации взаимодействия не требуется операций передачи сообщений. Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 114 из 155

Основания для достижения эффекта – разделяемые для параллельных процессов данные располагаются в общей памяти и для организации взаимодействия не требуется операций передачи сообщений. Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 115 из 155

Принцип организации параллелизма… Использование потоков (общее адресное пространство) Пульсирующий ("вилочный", fork-join) параллелизм Параллельные области Главный поток Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 116 из 155

Принцип организации параллелизма… При выполнении обычного кода (вне параллельных областей) программа выполняется одним потоком (master thread) При появлении директивы #parallel происходит создание команды (team) потоков для параллельного выполнения вычислений После выхода из области действия директивы #parallel происходит синхронизация, все потоки, кроме master, уничтожаются Продолжается последовательное выполнение кода (до очередного появления директивы #parallel) Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 117 из 155

Положительные стороны: Поэтапное (инкрементальное) распараллеливание –Можно распараллеливать последовательные программы поэтапно, не меняя их структуру Единственность разрабатываемого кода –Нет необходимости поддерживать последовательный и параллельный вариант программы, поскольку д ирективы игнорируются обычными компиляторами (в общем случае) Эффективность –Учет и использование возможностей систем с общей памятью Стандартизованность (переносимость), поддержка в наиболее распространенных языках (C, Fortran) и платформах (Windows, Unix) Разработка параллельных программ для систем с распределенной памятью: OpenMP… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 118 из 155

Пример – Сумма элементов вектора: #include #define NMAX 1000 main () { int i, sum; float a[NMAX]; #pragma omp parallel for shared(a) private(i,j,sum) { sum = 0; for (i=0; i

Дополнительная информация: 1. В. П. Гергель. Высокопроизводительные вычисления для многоядерных многопроцессорных систем. – (в печати) 2. А.С.Антонов. Параллельное программирование с использованием технологии OpenMP: Учебное пособие. - М.: Изд-во МГУ, с. 3. Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., and Melon, R.. Parallel Programming in OpenMP. San- Francisco, CA: Morgan Kaufmann Publishers., 2000 Разработка параллельных программ для систем с распределенной памятью: OpenMP Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 120 из 155

Программа HPCS: High Productivity Computing Systems (DARPA) – Цель: Повышение продуктивности в 10 раз к 2010 (Продуктивность=Производительность+Программируемость+Переносимость+Надежность) Phase II: Cray, IBM, Sun (July 2003 – June 2006) –Анализ существующих архитектур –Три новых языка программирования (Chapel, X10, Fortress) Phase III: Cray, IBM (July 2006 – 2010) –Реализация –Работа продолжена для всех предложенных языков Разработка параллельных программ для основе модели PGAS… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 121 из 155

Общая характеристика языков программы HPCS:… Новые объектно-ориентированные языки, поддерживающие широкий набор средств программирования, параллелизм и безопасность. Поддерживаются глобальное пространство имен, многопотоковость и явные механизмы для работы с локальностью. Имеются средства для распределения массивов по вычислительным узлам системы, а также для установления связи между потоками управления и данными, которые ими обрабатываются. Поддерживаются как параллелизм по данным, так параллелизм задач. Разработка параллельных программ для основе модели PGAS… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 122 из 155

Общая характеристика языков программы HPCS:… Управление локальностью Во всех трех языках обеспечивается доступ пользователей к виртуальным единицам локальности, называемых локалями (locale) в Chapel, регионами (region) в Fortress и участками (place) в X10. Каждое выполнение программы привязывается к некоторому набору таких единиц локальности, которые отображаются операционной системой на физические сущности, такие как вычислительные узлы. Это обеспечивает пользователей механизмом для (1) распределения коллекций данных по единицам локальности, (2) выравнивания различных коллекций данных и (3) установления связи между вычислительными потоками управления и данными, над которыми они работают. Разработка параллельных программ для основе модели PGAS… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 123 из 155

Общая характеристика языков программы HPCS:… В Fortress и X10 обеспечиваются обширные библиотеки встроенных распределений, а также имеется возможность порождения новых, определяемых пользователями распределений данных путем декомпозиции пространства индексов или комбинирования распределений в разных измерениях. В Chapel отсутствуют встроенные распределения, но обеспечивается обширная инфраструктура, которая поддерживает произвольные распределения данных, определяемые пользователями и являющиеся достаточно мощными для того, чтобы позволить работу с разреженными данными. Разработка параллельных программ для основе модели PGAS… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 124 из 155

Общая характеристика языков программы HPCS:… Многопотоковость (распараллеливание циклов). В Chapel различаются последовательные циклы «for» и параллельные циклы «forall», в которых итерации над элементами индексной области производятся без ограничений. За избежание зависимостей, приводящих к гонкам данных, отвечают пользователи. В Fortress цикл «for» по умолчанию является параллельным, так что, если итерации цикл выполняются над распределенным измерением массива, эти итерации будут группироваться по процессорам в соответствии с распределениями данных. В X10 различаются два вида параллельных циклов: цикл «foreach», который ограничен единственной единицей локальности, и цикл «ateach», позволяющий выполнять итерации над несколькими единицами локальности. Разработка параллельных программ для основе модели PGAS… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 125 из 155

Общая характеристика языков программы HPCS: Chapel - Fortress - X Разработка параллельных программ для основе модели PGAS Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 126 из 155

Анонс – программа «Hello, world» Быстрое прототипирование writeln(Hello, world); Структурное программирование def main() { writeln(Hello, world); } Приложение module HelloWorld { def main() { writeln(Hello, world); } Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 127 из 155

Общая характеристика: Синтаксис –Использование отдельных элементов C, C#, C++, Java, Ada, Perl,... Семантика –Императивный, блочно-структурированный, массивы –Объектно-ориентированное программирование (опционно) –Статический контроль типов Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 128 из 155

Элементы языка - Диапазоны: Синтаксис range-expr: [low].. [high] [by stride] Семантика Регулярная последовательность целых –stride > 0: low, low+stride, low+2*stride,... high –stride < 0: high, high+stride, high+2*stride,... low Примеры –1..6 by 2 // 1, 3, 5 –1..6 by -1 // 6, 5, 4, 3, 2, 1 –3.. by 3 // 3, 6, 9, 12,... Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 129 из 155

Элементы языка - Массивы: Синтаксис array-type: [ index-set-expr ] type Семантика Массив элементов, размер определяется множеством индексов Примеры –var A: [1..3] int, // Массив из 3 элементов B: [1..3, 1..5] real, // Двумерный массив C: [1..3][1..5] real; // Массив массивов Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 130 из 155

Элементы языка - Цикл: Синтаксис for-loop: for index-expr in iterator-expr { stmt-list } Семантика Выполнение тела цикла для каждого значения переменной цикла Примеры –var A: [1..3] string = (DO, RE, MI); –for i in 1..3 do write(A(i)); // DOREMI –for a in A { a += LA; write(a); } // DOLARELAMILA Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 131 из 155

Элементы языка - Условия: Условие if cond then computeA() else computeB(); Цикл while while cond { compute(); } Выбор select key { when value1 do compute1(); when value2 do compute2(); otherwise compute3(); } Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 132 из 155

Элементы языка - Функции: Пример def area(radius: real) return 3.14 * radius**2; writeln(area(2.0)); // Пример функции с значениями по умолчанию def writeCoord(x: real = 0.0, y: real = 0.0) { writeln((, x,,, y, )); } writeCoord(2.0); // (2.0, 0.0) writeCoord(y=2.0); // (0.0, 2.0) Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 133 из 155

Параллелизм задач: Оператор begin Синтаксис begin-stmt: begin stmt Семантика –Создает параллельную задачу для выполнения stmt –Выполнение программы-родителя не останавливается Пример begin writeln(hello world); writeln(good bye); Возможный вывод (1) hello world (2) good bye good bye hello world Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 134 из 155

Параллелизм задач: Тип sync Синтаксис sync-type: sync type Семантика –Переменные типа sync имеют два состояния – «full», «empty» –Запись в переменную типа sync переводит ее в состояние «full» –Чтение из переменной типа sync переводит в состояние «empty» Примеры ( 1) var lock$: sync bool; (2) var future$: sync real; lock$ = true; begin future$ = compute(); critical(); computeSomethingElse(); lock$; useComputeResults(future$); Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 135 из 155

Параллелизм задач: Оператор cobegin Синтаксис cobegin-stmt: cobegin { stmt-list } Семантика –Порождает параллельную задачу для каждого оператора stmt-list –Синхронизация при завершении блока Пример cobegin { consumer(1); consumer(2); producer(); } Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 136 из 155

Параллелизм задач: Оператор coforall Синтаксис coforall-loop: coforall index-expr in iterator-expr { stmt } Семантика –Порождает параллельных задач для каждой итерации цикла –Синхронизация при завершении цикла Пример (задача «производитель-потребитель») begin producer(); coforall i in 1..numConsumers { consumer(i); } Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 137 из 155

Параллелизм задач: Оператор atomic Синтаксис atomic-statement: atomic stmt Семантика Выполнение stmt как атомарной операции Пример atomic A(i) = A(i) + 1; Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 138 из 155

Массивы: Расширенные способы задания диапазонов var Dense: domain(2) = [1..10, 1..20], Strided: domain(2) = Dense by (2, 4), Sparse: subdomain(Dense) = genIndices(), Associative: domain(string) = readNames(), Opaque: domain(opaque); Разработка параллельных программ для основе модели PGAS: Chapel… Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 139 из 155

Массивы: Расширенные операции forall (i,j) in Sparse { DenseArr(i,j) += SparseArr(i,j); } Разработка параллельных программ для основе модели PGAS: Chapel… = Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 140 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Редукция данных: Операция reduce Синтаксис reduce-expr: reduce-op reduce iterator-expr Семантика Применяет для каждого элемента данных операцию reduce-op Пример total = + reduce A; bigDiff = max reduce [i in InnerD] abs(A(i)-B(i); Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 141 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Редукция данных : Операция scan Синтаксис scan-expr: scan-op scan iterator-expr Семантика Применяет для каждого элемента данных операцию reduce-op (с получением всех частных результатов) Пример var A, B, C: [1..5] int; A = 1; // A: B = + scan A; // B: B(3) = -B(3); // B: C = min scan B; // C: Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 142 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы: Понятие locale Определение –Представляет абстракцию вычислительного элемента –Содержит обрабатывающее устройство и память Свойства –Задачи, исполняемые на locale, имеют однородный доступ к локальной памяти –Доступ к памяти других locale происходит более медленно Пример locale – SMP, многоядерный процессор Перевод – locale, локал, исполнитель,… !? Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 143 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы Описание множества всех locale config const numLocales: int; const LocaleSpace: domain(1) = [0..numLocales-1]; const Locales: [LocaleSpace] locale; Определение множества locale при запуске prompt> a.out --numLocales=8 Определение топологии множества locale var TaskALocs = Locales[0..1]; var TaskBLocs = Locales[2..numLocales-1]; var Grid2D = Locales.reshape([1..2,1..4]); Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 144 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы: Операции Получение индекса locale def locale.id: int {... } Получение имени locale def locale.name: string {... } Получение количества ядер в locale def locale.numCores: int {... } Получение размера доступной памяти в locale def locale.physicalMemory(...) {... } Пример – получение размера всей памяти const totalSystemMemory = + reduce Locales.physicalMemory(); Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 145 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы: Связывание задач и locale Связывание задач и locale – операция on on-stmt: on expr { stmt } Семантика Выполнение stmt на locale, определяемый expr Пример var A: [LocaleSpace] int; coforall loc in Locales do on loc do A(loc.id) = compute(loc.id); Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 146 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы: Пример var x, y: real; // x и y на locale 0 on Locales(1) { // migrate task to locale 1 var z: real; // z на locale 1 z = x + y; // удаленный доступ к x и y on Locales(0) do // возврат на locale 0 z = x + y; // удаленный доступ к z // возврат на locale 1 on x do // переход на locale 0 z = x + y; // удаленный доступ к z // переход на locale 1 } // возврат на locale 0 Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 147 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы: Распределение данных Распределение диапазонов (данных) между множеством locale: пример const Dist = new dmap(new Cyclic(startIdx=(1,1))); varDom: domain(2) dmapped Dist = [1..4, 1..8]; Данные распределяются на решетке locale Имеется библиотека распределений Возможно создание новых распределений Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 148 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… Модель вычислительной системы: Распределение данных Распределение диапазонов осуществляется по единой схеме для всех типов диапазонов Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 149 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… NAG MG Stencil in Fortran+MPI Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 150 из 155

Разработка параллельных программ для основе модели PGAS: Chapel… NAG MG Stencil in Chapel def rprj3(S, R) { const Stencil = [-1..1, -1..1, -1..1], W: [0..3] real = (0.5, 0.25, 0.125, ), W3D = [(i,j,k) in Stencil] W((i!=0)+(j!=0)+(k!=0)); forall inds in S.domain do S(inds) = + reduce [offset in Stencil] (W3D(offset) * R(inds + offset*R.stride)); Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 151 из 155

Разработка параллельных программ для основе модели PGAS: Chapel Умножение матриц – ленточный алгоритм. Intel ®Core2 DUO 1.5GHz 1.5GHz 2.00 Gb RAM Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 152 из 155

ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. Выводы Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 153 из 155 Основные подходы: – Использование библиотек для существующих языков программирования, – Использование надъязыковых средств (директив, комментариев), – Расширение существующих языков программирования, – Создание новых параллельных языков программирования Основные технологии: – OpenMP для систем с общей памятью, – MPI для систем с распределенной памятью Активно развиваемое направление на основе модели распределенной глобально-адресуемого пространства

Контакты : Нижегородский университет Факультет вычислительной математики и кибернетики Гергель Виктор Павлович Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 154 из 155

СПАСИБО ЗА ВНИМАНИЕ Вопросы ? Москва, МГУ, Модели и технологии программирования для высокопроизводительных вычислительных систем 155 из 155