Параллельное программирование Малявко Александр Антонович Сайт: Лекции:28 часа Лабораторные работы:14 часов Расчетно-графическая работа + самостоятельная работа. Итоговая аттестация: зачет.

Литература: Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, Антонов А.С. Параллельное программирование с использованием технологии MPI. – М.: Изд-во МГУ, 2004 Антонов А.С. Параллельное программирование с использованием технологии OpenMP. – М.: Изд-во МГУ, Корнеев В.Д. Параллельное программирование в MPI. – Новосибирск: Изд-во ИВМ и МГ, Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. – Н.Новгород.: Изд-во ННГУ Малышкин В. Э. Корнеев В.Д. Параллельное программирование мультикомпьютеров : Новосибирск, 2006 Корнеев В.В. Вычислительные системы. – М.: Гелиос АРВ, 2004 Богачев К. Ю. Основы параллельных вычислений. – М., Изд-во МГУ, Немнюгин С. А. Стесик О. И. Параллельное программирование для многопроцессорных вычислительных систем. – СПб., 2002 Корнеев В. Д. Параллельное программирование кластеров : учеб. пособие, Новосибирск, Изд-во НГТУ, 2008.

Русскоязычные интернет-ресурсы:

Англоязычные интернет-ресурсы:

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

Большие задачи: Создание (моделирование) новых чипов. Геофизика, разведка полезных ископаемых. Предсказания погоды, климата и глобальных изменений в атмосфере. Мировой океан, гидросфера. Логистика и транспортные задачи большой размерности. Генетика (расшифровка генома), структурная биология. Разработка фармацевтических препаратов. Управляемый термоядерный синтез. Гидро- и газодинамика. Термодинамика, моделирование процессов горения и взрыва. Квантовая физика, обработка результатов экспериментов. Ядерная физика. Вооружения. Макрофизика, астрономия (обработка данных радио-, оптических, рентгеновских, гамма- … телескопов). Науки о материалах, сверхпроводимость, нанотехнологии, … Сейсмодинамика. Системы сгорания топлива. Распознавание и синтез речи, распознавание изображений. Веб-сервисы (поиск, облака, …). Криптоанализ. …

Параллелизм Лента бесконечна в обе стороны (полубесконечная – эквивалентна бесконечной, это доказано) На ленте – ячейки. В каждой ячейке может быть пусто, либо один из символов s i алфавита МТ (в пределе – 0,1) УУ имеет множество состояний { q 0, q 1, … }и набор правил. Правила работы МТ выглядят так: q tj s tj –> q tj+1 s tj+1 m где q tj и q tj+1 – состояния в моменты времени t j и t j+1 соответственно, s tj – символ в ячейке до момента t j (стирается машиной из ячейки) s tj+1 – символ в ячейке начиная с момента t j+1 (пишется машиной при выполнении действия по правилу) m – перемещение (на одну ячейку влево, на одну ячейку вправо или остаться на месте) Управляющее устройство Предельный случай отсутствия параллелизма: Машина Тьюринга

Другой крайний случай: предельный параллелизм. Пусть требуется вычислить значение: r = a + b * c Можно представить себе специализированное устройство, в котором для вычисления значения каждого двоичного разряда результата r используется схема, построенная на логических элементах И, ИЛИ и НЕ, реализующая логическую функцию: r i = F i (a 0, a 1, a 2, … a n, b 0, b 1, b 2, … b n, c 0, c 1, c 2, … c n ) Например: r 0 = (a 0 И НЕ(b 0 И с 0 )) ИЛИ (НЕ(a 0 ) И (b 0 И с 0 )) r 1 = ((a 1 И НЕ(b 1 И с 1 )) ИЛИ (НЕ(a 1 ) И (b 1 И с 1 )) И НЕ ((a 0 И b 0 ) ИЛИ (a 0 И с 0 ) ИЛИ (b 0 И c 0 )) ИЛИ ( …) r 2 = … …

Собственный (внутренний) параллелизм алгоритмов и программ Для оценки степени параллелизма, потенциально достижимой на практике, нужно определить понятие «гранулярности» - сложности элементарной операции, до которой возможно «дробить» процесс исполнения программы. В дальнейшем под гранулярностью (зернистостью) понимается уровень сложности примитивных операций, выполняемые существующими процессорами – сложение, умножение, … чисел. В качестве примера способа определения внутреннего параллелизма рассмотрим последовательность действий для вычисления значений корней полного квадратного уравнения ax 2 +bx+c=0, которая определяется формулами: x 1 = (–b+ (b2–4ac))/2a x 2 = (–b– (b2–4ac))/2a

действияДействиеПримечание Ввод a, b, cВвод-вывод не рассматривается при определении информационных зависимостей 0a22*aа2 – рабочая переменная 1a44*aа4 – рабочая переменная 2b_neg – bb_neg – рабочая переменная 3bbb*bbb – рабочая переменная 4ac4a4*caс4 – рабочая переменная 5p_sqrbb – a4p_sqr – рабочая переменная 6sqsqrt(p_sqr)sq – рабочая переменная, sqrt – операция вычисления квадратного корня 7w1b_neg + sqw1 – рабочая переменная 8w2b_neg – sqw2 – рабочая переменная 9root_1w1/a2root_1 – первый корень уравнения 10root_1w2/a2root_2 – второй корень уравнения

Граф информационных зависимостей

Ярусно-параллельная форма

Ширина и высота ЯПФ Ширина ярусно-параллельной формы – характеристика алгоритма, показывающая максимально возможное количество ветвей. –Для решения задачи распараллеливания могут быть использованы (в скобках – значения для рассмотренного примера): Максимальная ширина (4). Минимальная ширина (1). Средняя ширина (1.83). Высота ЯПФ (количество ее ярусов) – характеристика алгоритма, позволяющая оценить минимально возможное время его исполнения. –Для данного примера высота равна 6. –Отношение общего количества операций к высоте показывает максимально возможное ускорение исполнения параллельной программы по отношению к последовательной.

Алгоритм вычисления суммы N чисел Пусть необходимо вычислить сумму N чисел. Обычный алгоритм вообще не распараллеливается, т.е. имеет высоту, равную N (точнее – N-1): …

Другой алгоритм вычисления суммы N чисел Высота ~ log 2 (N) …

Проблемы использования ЯПФ В общем случае задача нахождения ЯПФ с минимальной высотой по-видимому алгоритмически неразрешима. Если построена ЯПФ с приемлемыми (хотя бы оценочно) шириной и высотой, то следующая задача – составление расписания выполнения операций на вычислительной системе с заданной архитектурой. Для реальных больших задач число вершин и дуг ЯПФ настолько велико, что для его хранения, анализа и обработки потребуется система значительно более мощная, чем требуемая для решения собственно задачи.

Что взамен ЯПФ? Известно соотношение: 90% времени выполняется 10% текста программы (реально для больших задач – 99.(9)%). Эти 10% текста – циклы. Распараллеливание циклов подразумевает большую степень гранулярности, чем пооперационное распараллеливание. Обычно гранулой при таком подходе является одна итерация распараллеливаемого цикла

Top 500 (ноябрь 2011) Место расположения, год, производительСуперкомпьютер К-во ядер Rmax (Gflops) Rpeak (GFlops) 1 RIKEN Advanced Institute for Compu- tational Science (AICS), Japan, 2011 K computer, SPARC64 VIIIfx 2.0GHz, Tofu interconnect National Supercomputing Center in Tianjin, China, 2010, NUDT NUDT TH MPP, X Ghz 6C, NVIDIA GPU, FT C DOE/SC/Oak Ridge National Laboratory, USA, 2009, Cray Inc.Cray XT5-HE Opteron 6-core 2.6 GHz National Supercomputing Centre in Shenzhen (NSCS), China, 2010, Dawning Dawning TC3600 Blade, Intel X5650, NVidia Tesla C2050 GPU GSIC Center, Tokyo Institute of Technology, Japan, 2010, NEC/HP HP ProLiant SL390s G7 Xeon 6C X5670, Nvidia GPU, Linux/Windows DOE/NNSA/LANL/SNL, 2011, USA Cray XE6, Opteron C 2.40GHz, Custom NASA/Ames Research Center/NAS, 2011, USA SGI Altix ICE 8200EX/8400EX, Xeon HT QC 3.0/Xeon 5570/ Ghz DOE/SC/LBNL/NERSC, 2010, USACray XE6 12-core 2.1 GHz Commissariat a l'Energie Atomique (CEA), France, 2010, Bull SABull bullx super-node S6010/S DOE/NNSA/LANL, USA, 2009, IBM BladeCenter QS22/LS21 Cluster, PowerXCell 8i 3.2 Ghz / Opteron DC 1.8 GHz, Voltaire Infiniband

Top 500 (ноябрь 2010) Место расположения, год, производительСуперкомпьютер К-во ядер Rmax (Gflops) Rpeak (GFlops) 1 National Supercomputing Center in Tianjin, China, 2010, NUDT NUDT TH MPP, X Ghz 6C, NVIDIA GPU, FT C DOE/SC/Oak Ridge National Laboratory, USA, 2009, Cray Inc.Cray XT5-HE Opteron 6-core 2.6 GHz National Supercomputing Centre in Shenzhen (NSCS), China, 2010, Dawning Dawning TC3600 Blade, Intel X5650, NVidia Tesla C2050 GPU GSIC Center, Tokyo Institute of Technology, Japan, 2010, NEC/HP HP ProLiant SL390s G7 Xeon 6C X5670, Nvidia GPU, Linux/Windows DOE/SC/LBNL/NERSCCray XE6 12-core 2.1 GHz Commissariat a l'Energie Atomique (CEA), France, 2010, Bull SABull bullx super-node S6010/S DOE/NNSA/LANL, USA, 2009, IBM BladeCenter QS22/LS21 Cluster, PowerXCell 8i 3.2 Ghz / Opteron DC 1.8 GHz, Voltaire Infiniband National Institute for Computational Sciences /University of Tennessee, USA, 2009, Cray Inc.Cray XT5-HE Opteron 6-core 2.6 GHz Forschungszentrum Juelich (FZJ), Germany, 2009, IBMBlue Gene/P Solution DOE/NNSA/LANL/SNL, USA, 2010, Cray Inc.Cray XE6 8-core 2.4 GHz

Россия в списке Top 500 за ноябрь 2011 года представлена так: Место расположения, год, производительСуперкомпьютер К-во ядер Rmax (Gflops) Rpeak (GFlops) 18 Moscow State University - Research Computing Center, 2011, T-Platforms T-Platforms T-Blade2/1.1, Xeon X5570/X GHz, Nvidia 2070 GPU, Infiniband QDR Joint Supercomputer Center, 2009, Hewlett-Packard Cluster Platform 3000 BL460c/BL2x220, Xeon 54xx 3 Ghz, Infiniband Kurchatov Institute Moscow, 2010, Hewlett-Packard Cluster Platform 3000 BL2x220, E54xx 3.0 Ghz, Infiniband South Ural State University, 2011, Self-made SKIF Aurora Platform - Intel Xeon X5680, Infiniband QDR Web Content Provider HP DL160 Cluster G6, Xeon E5645 6C 2.40 GHz, Gigabit Ethernet

Россия в списке Top 500 за июнь 2011 года была представлена так: Место расположения, год, производительСуперкомпьютер К-во ядер Rmax (Gflops) Rpeak (GFlops) 13 Moscow State University - Research Computing Center, 2011, T-Platforms T-Platforms T-Blade2/1.1, Xeon X5570/X GHz, Nvidia 2070 GPU, Infiniband QDR Joint Supercomputer Center, 2009, Hewlett-Packard Cluster Platform 3000 BL460c/BL2x220, Xeon 54xx 3 Ghz, Infiniband Kurchatov Institute Moscow, 2010, Hewlett-Packard Cluster Platform 3000 BL2x220, E54xx 3.0 Ghz, Infiniband South Ural State University, 2011, Self-made SKIF Aurora Platform - Intel Xeon X5680, Infiniband QDR Government, 2011, IBM BladeCenter HS22 Cluster, Xeon X56xx 2.53 GHz, GigEthernet ,488772,6 353 Moscow State University - Research Computing Center, 2008, SKIF/T- Platforms T-Platforms T60, Intel Quadcore 3Ghz, Infiniband DDR Government, 2011, IBMxSeries x3650M3, Xeon X56xx 2.53 GHz, GigE ,681729,1 397Government, 2010, IBM BladeCenter HS22 Cluster, Xeon QC GT 2.53 GHz, Infiniband ,349223,7 401Banking, 2011, IBM BladeCenter HS22 Cluster, Xeon X56xx 2.53 GHz, GigEthernet ,480150,4 402Banking, 2011, IBM BladeCenter HS22 Cluster, Xeon X56xx 2.53 GHz, GigEthernet ,480150,4 450 Tomsk State University, 2011, T- Platforms T-Platforms T-Blade 1.1/2.0, Xeon X5670 2,93 GHz, Infiniband Government, 2010, IBM xSeries x3650 Cluster Xeon QC GT 2.66 GHz, Infiniband ,646751

Статистика по странам Ноябрь 2010Ноябрь 2011 США США Китай Япония Япония Китай Франция Германия Германия Франция Великобритания Великобритания Южная Корея Канада Россия Россия Остальные (21 страна) Остальные (19 стран)

Как измеряется производительность: Выполняются тесты LINPACK – решение системы линейных алгебраических уравнений порядка n. Производительность: Rmax =2×( n 3 /3 + n 2 ) / t Здесь n – размерность системы линейных алгебраических уравнений (плотно заполненной), t – время выполнения теста. Пиковую производительность оценивают так: Rpeak =p / t i γ i Здесь: p – число процессоров или АЛУ; суммирование выполняется от 1 до k, где k число различных типов команд процессора; γ i – удельный вес команд i-го типа в программе; t i – время выполнения одной команды типа i. Обычно Rmax = (0,5 ÷0,95) × Rpeak.

Все суперкомпьютеры реализуют параллелизм при решении задач. Параллелизм: за и против. ПротивЗа 1Параллельные системы слишком дороги. В силу закона Гроша: P ~= S 2 гдеP – производительность компьютера, S – его стоимость. Поэтому ыгоднее приобрести один мощный компьютер, чем N менее производительных (пусть P1 – требуемая производительность компьютера, тогда его стоимость S1 = P1. Если этой же производительности удается достичь путем параллельного использования N компьютеров с производительностью P1/N, то их суммарная стоимость будет равна: N * P 1 /N, т.е. N*P 1 ) Рост быстродействия последовательных ЭВМ не может продолжаться бесконечно (потолок в настоящее время почти достигнут). Следовательно, добиваться дальнейшего увеличения вычислительной мощности можно только путем массового параллельного использования множества последовательных компьютеров. Закон Гроша сейчас практически не соответствует действительности, т.е. производительность растет быстрее, чем квадрат стоимости: P > S 2

Параллелизм: за и против. 2При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского достигаемое при использовании параллельной системы ускорение вычислений пропорционально двоичному логарифму от числа процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10). Приведенная оценка ускорения верна для распараллеливания далеко не всех алгоритмов. Существует большое количество задач, при параллельном решении которых достигается близкое к 100% использованию всех имеющихся процессоров параллельной вычислительной системы. 3Последовательные компьютеры постоянно совершенствуются. По широко известному и подтверждаемому практикой закону Мура (иллюстрация ниже) сложность, тесно связанная с быстродействием, последовательных микропроцессоров возрастает вдвое каждые 18 месяцев (быстродействие ЭВМ увеличивалось на порядок каждое 5-летие), поэтому необходимая производительность может быть достигнута и на последовательных компьютерах Аналогичное развитие свойственно и параллельным системам. Однако применение параллелизма позволяет получать необходимое ускорение вычислений без ожидания разработки новых более быстродействующих процессоров.

Параллелизм: за и против. 4Эффективность параллелизма сильно зависит характерных свойств параллельных систем. Все современные последовательные ЭВМ работают в соответствие с классической схемой фон- Неймана; параллельные системы отличаются существенным разнообразием архитектуры и максимальный эффект от использования параллелизма может быть получен при полном использовании всех особенностей аппаратуры (следствие – перенос параллельных алгоритмов и программ между разными типами систем затруднителен, а иногда и невозможен) При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные устоявшиеся способы обеспечения параллелизма (конвейерные вычисления, многопроцессорные системы и т.п.). Инвариантность создаваемого программного обеспечения обеспечивается при помощи использования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.)

Параллелизм: за и против. 5За десятилетия эксплуатации последовательных ЭВМ накоплено огромное программное обеспечение, ориентировано на последовательные ЭВМ; переработка его для параллельных компьютеров практически нереальна Если эти программы обеспечивают полное решение поставленных задач, то их переработка вообще не нужна. Однако если последовательные программы не позволяют получать решение задач за приемлемое время или же возникает необходимость решения новых задач, то необходима разработка нового программного обеспечения и оно изначально может реализовываться в параллельном исполнении Существует ограничение на ускорение вычисление при параллельной реализации алгоритма по сравнению с последовательной (закон Амдаля, приводится ниже) В самом деле, алгоритмов вообще без (определенной) доли последовательных вычислений не существует. Однако эта доля существенно зависит от искусства программиста и для действительно сложных задач обычно очень мала.