1631124688-fb0b2564726fdb4c51612f2aa6ab974b (В. П. Ильин - Лекции)

ЧИСЛЕННЫЙ АНАЛИЗПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВВ. П. ИльинИнститут вычислительной математикии математической геофизики СО РАННовосибирский государственный университетМеханико-математический факультет НГУ4-й курсФевраль – май 2019 г.СОДЕРЖАНИЕ1. Введение, задачи и цели курса.2. История параллельных вычислений.3. Архитектуры многопроцессорных ЭВМ.4. Принципы параллельного программирования.5. Критерии эффективности параллелизма.6. Распараллеливание векторно-матричныхопераций.7. Параллельные методы решения СЛАУ.8.

Явные и неявные методы решенияэволюционных задач.9. Методы декомпозиции областей.2ЗАДАЧИ И ЦЕЛИРАСПАРАЛЛЕЛИВАНИЯ ВЫЧИСЛЕНИЙ1. Высокопроизводительные вычисления длярешения задач математического моделирования.2. Технологические стадии крупномасштабногокомпьютерного эксперимента3. Архитектуры многопроцессорыхвычислительных систем (МВС)4. Принципы и технологии параллельногопрограммирования.5. Инструменты гибридного программированияна МВС с распределенной и иерархическойпамятью.3ИСТОРИЯ ПЕРВЫХ ОТКРЫТИЙБлез Паскаль – автор первой работающей машины (1642 г.)50 моделей, 8 существуют сейчас, 1943 г. – 300-летие;Вильям Шиккард (Тюбинген) – открытие 1957 г. – письмаИ. Кеплеру (1624) с эскизом “часов для счета” (1960 г. –реализация действующей модели);примерно в 1968 г.

обнаружены рукописи с эскизомЛеонардо да Винчи с эскизом 13-разрядногосуммирующего устройства;1670 г. – описание “арифметического инструмента”Лейбница;1820 г. – патент Карла Томаса на арифмометр;1882 г. – доклад П. Л. Чебышева в Париже о счетноймашине с умножением и делением;Чарльз Бэббидж (1791–1871 гг.) – предтеча ЭВМ(разностная и аналитическая машины, 1843 г.);Ада Лавлейс – первый в мире программист.ИСТОРИЯ: ПЕРВЫЕ ЭВМ1. Электромеханические релейные машиныМАРК1 (1944 г.) – Говард Айкен, IBM;Ц-36 (1941г.) – Конрад Цузе (Берлин)2. Аналоговые вычислительные машины (АВМ),электрические сетки3.

ЭНИАК (1942) – Дж. Атанасов, Дж. фонНейман4. “ Машина Алана Тюринга” (1936 г.)5. ЮНИВАК (1951 г.) – 1-я коммерческая ЭВМ6. МЭСМ (1950 г.) – С. А. Лебедев, Киев7. БЭСМ (1952 г.) – ИТМиВТ АН СССР, МоскваГОНКА ПОКОЛЕНИЙ ЭВМ1. Первые советские ЭВМ (1952-1954):СТРЕЛА, КИЕВ, МИНСК, УРАЛЭлектронные лампы → транзисторы → ИС → БИСБЭСМ-4, М-20, М-220, РАЗДАН, БЭСМ-6(В. А. Мельников),ЕС ЭВМ (НИИЦЭВТ), IBM-360, IBM-3702. Пионерские суперкомпьютерыCRAY-1 (1976), Сайбер (1981), ИЛЛИАК- IV (1975),ЭЛЬБРУС-1 (1979), ЕС-1766 (1984) , ПС-20003. Персональные компьютеры на СБИС6МНОГОПРОЦЕССОРНЫЕ ВЫЧИСЛИТЕЛЬНЫЕСИСТЕМЫ (МВС)• Гига → терра → пета → экза (1018 )• 2008 – начало петафлопсной эры• закон Мура: ускорение в 1000 раз за 11 лет• экзафлопс: сотни миллионов ядер, 1018 байт памяти• десятки мегаватт, площадь 2 стадиона• графические ускорители (GPGPU), ПЛИС (FPGA)• гетерогенная архитектура:• кластер: многопроцессорные узлы с распределенной памятью• несколько многоядерных процессоров (CPU) с общейпамятью• несколько сверхбыстрых GPU• супербыстрые регистры с векторизацией (система AVX)• многоуровневая память (в том числе кэш)• ТОР-500, ТОР-507ПАМЯТЬ И КОММУНИКАЦИИ• Общая (shared) память – одно адресное поле для всехпроцессорных элементов,• Распределенная (distributed) – локальное адресноепространство для каждого процессора,• UMA (uniform memory access) – память с одинаковымвременем и шириной доступа, как правило, для общей памяти,• NUMA – память с неоднородным доступом,• CACHE – небольшая быстрая “колопроцессорная” память ,временно копируемая в других устройствах памяти.Коммуникации “процессор – процесор” и “процессор – память”,коммутаторы, общие шины и сети с разными топологиями(звезда, кольцо, дерево, гиперкуб, n-мерная сетка).ТИПЫ ВЫЧИСЛЕНИЙ• Многоядерный процессор (multi-core) – много ядер наодном кристалле;• Симметричный мультипроцессор (SMP) – многоодинаковых процессоров с общей памятью, соединенных сней общей шиной, из-за возможных конфликтов памятиP ≤ 32;• Распределенные вычисления (concurrent, parallel ,distributed) – наиболее масштабируемые;• Кластеры, MPP (massively parallel processor,суперкомпьютер, обычно более 100 процессоров сосверхбыстрым интерконнектом) вычислительные сети (gridcomputing) – связь через Интернет с интеграцией ресурсовдля больших задач;• Векторные процессоры (CPU), SIMD, AVX.9ПОСТПЕТАФЛОПСНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ• 2008 г.

– начало петафлопсной эры;• закон Мура: ускорение в 1000 раз за 11лет;• экзафлопс: сотни миллионов ядер, 1018 1 байт памяти;• десятки мегаватт, площадь 2 стадиона;• графические ускорители (GPGPU), ПЛИС (FPGA);• Гетерогенная архитектура:• кластер: многопроцессорные узлы с распределеннойпамятью,• несколько многоядерных процессоров (CPU) с общейпамятью,• несколько сверхбыстрых GPU,• супербыстрые регистры с векторизацией (система AVX),• многоуровневая память (в том числе кэш).10КРИТЕРИИ ЭФФЕКТИВНОСТИ РАСПАРАЛЛЕЛИВАНИЯАЛГОРИТМОВКоэффициент ускорения: SP (A) = T1 (A)/Tp(A).Эффективность использования: EP (A) = Sp(A)/P.Линейное ускорение: SP (A) ≈ P, Ep (A) ≈ 1нормально: Ep = 0.3 + 0.8, иногда Ep > 1.Масштабированное ускорениесильное:с увеличением числа вычислительных устройств времярешения фиксированной задачи обратнопропорционально убывает;слабое:с одинаковым пропорциональным увеличениемколичества вычислительных устройств и ресурсоемкостизадачи (число степеней свободы) время решенияостанется постоянным.Времена выполнения операций:T = Ta + Tc , Ta = τa Na , Tc = τ0 N0 + τc Nc , τa τc τ011ОЦЕНКИ ПРОИЗВОДИТЕЛЬНОСТИ МВСЗакон Амдаля (для фиксированной задачи):S = 1/(1 − Θ + Θ/Sp ) ≤ 1/(1 − Θ)S – коэффициент ускорения времени решения всей задачи,Sp – коэффициент ускорения параллелизуемой части задачиΘ – относительная доля параллелизуемой части.12Пример: если нераспараллеливаемая часть составляет 10 %(Θ = 0.9), то S ≤ 10 независимо от количествавычислительных устройств.Закон Густафсона (объем вычислений растет линейнос увеличением числа процессоров, т.

е. все устройствазагружены): S = 1 − −Θ + ΘSp .13НЕЗАВИСИМОСТЬ ДАННЫХУсловия Бернштейна для распараллеливанияпрограммных сегментовIj ∩ Oi = 0, Ii ∩ Oj = 0, Oi ∩ Oi = 0,где Ij и Oi – входные и выходные данные для Pi и Pj .Классификация Флинна для МВС:SISD – single - instruction - single - dataSIMD – single - instruction - multiple - dataMISD – multiple - instruction - single - dataMIMD – multiple - instruction - multiple - dataПараллелизм на уровне задач:декомпозиция задач на подзадачи, с их разделеннымили кооперативным вычислением.Аппаратная битовая поддержка вычисленийSingle precision – 32 бита (4 байта, ε ≈ 10−7 )Double precision – 64 бита (8 байтов, ε ≈ 1015 )14ЭНЕРГОЗАТРАТНОСТЬ КОММУНИКАЦИЙP = CV 2 FP – выделяемая мощностьC – емкость (пропорциональна числу транзисторов)V – электрическое напряжениеF – тактовая частота.Проблема охлаждения (воздушное или жидкостное).Прогнозы электрозатратности экзафлопсника:пессимистическая – 100 мвтоптимистическая – 20 мвтАктуальная математическая задача:конструировать алгоритмы с малыми коммуникациями.15ПАРАЛЛЕЛЬНОЕ ПРОГРАМИРОВАНИЕ• Алгоритмические языки: С, С++, FORTRAN 90,PYTHON• “Параллельные” языки (Chapel, X10)• Cистемы передачи сообщений Message PassingInterface (MPI процессы)• Многопотоковые вычисления (multi-thread) надобщей памятью• Конвейеризация операций (Advanced VectorExtension (AVX))• Гибридное программирование• CUDA – (General Purpose Graphic Processor Units(GPGPU))• Parallel Virtual Machine (PVM)16СУММА И МЕТОД СДВАИВАНИЯВычисления суммы σ =NPai или произведения p =NQaii=0i=0T1 = Nτa , P = N/2 : Tp = ra log2 N, Sp =Nlog2 NN = 1014 : Sp ≈ 100, Ep ≈ 0.2PN − mP : Tp = (m + log2 P)τa , Sp = P 1 + log2 PN17РАСПАРАЛЛЕЛИВАНИЕ ВЕКТОРНО-МАТРИЧНЫХОПЕРАЦИЙалгебраические объекты:x, y , z ∈ RN ,A, B, C ∈ RN,M ,x = {xi },A = {ai,j : i − 1, ..., N;a, b, c − скалярыj = 1, ..., M}блочные матрицы:A = {Ak,l },A ∈ RNk ,Ml , k = 1, ..., K ;l = 1, ..., Lвекторно-матричные операции:x = y + az = {xi = yi + azi ,N = qP,q = 1, ...

:i = 1, ..., N}Tp = P,Ep = 1,A = bB + cC = {ai,j = bbi,j + cci,j }18ПЕРЕМНОЖЕНИЕ МАТРИЦA = BC = {ai,j =NXbi,k ck,j }k−1A = BC = {Ak,l =MXBk,m Cm,l },m=1K = L = M,>∈ RNk NmBk,m Cm,lРазреженные строчные форматы CSR - CompressedSparsce Row: хранятся ненулевые элементыai,j1 , ai,j2 , ..., ai,jN , а также номера jk для столбцов этихэлементов,Ni – количествоненулевых элементов в i-й строке,PNNNZ = i−1 Ni – общее число ненулевых элементовГИГАФЛОП ПРОТИВ ГИГАБАЙТА В СЕКУНДУ20БАЗОВЫЕ БИБЛИОТЕКИ ЛИНЕЙНОЙ АЛГЕБРЫBLAS - Basic Linear Algebra Subroutines - содержитосновные операции над векторами и матрицамиHPL - High-Performance Linpack - основной тест длясоставления списка Top500 - списка из 500 самых мощныхсуперкомпьютеров мираLapack - Linear Algebra Package - пакет для решенияплотных систем уравнений и задачи о наименьшихквадратахДоступны на сайте netlib.org в виде кодов на Фортране иСи21УРОВНИ ПАРАЛЛЕЛИЗМА1.

Физический (ядра/вычислительные модули процессора)2. Виртуальный физический (hyperthreading/гиперсрединг)3. Системный (операционная система)4. ПрограммныйИнженер-программист ВСЕГДА программирует толькопрограммный уровень, а производительность зависит отвсех уровней.Ищите слово AFFINITY - это средство управления связямимежду всеми уровнями параллелизма22DAG подходDAG - Directed Acyclic Graph - направленный граф безцикловОчень удачный подход в задачах линейной алгебрыХорошая масштабируемость в середине алгоритмаДинамическое распределение задачДинамическое изменение размера подзадачИщите подходящий для вашей задачи способпараллелизации23ПАРАЛЛЕЛЬНЫЕ АДГОРИТМЫ РЕШЕНИЯТРЁХДИАГОНАЛЬНЫХ СЛАУ(Av )i ≡ −ai vi−1 + bi vi − ci vi+1 = fi ,a1 = cN = 0,i = 1, .

. . , N;метод прогонки:vi = βi vi+1 + zi ,i = N, N − 1, . . . , 1,cifi + ai zi−1, zi =, i = 1, 2, . . . , N;bi − ai βi−1bi − ai βi−1встречная прогонкаβi =β̂i = ai dˆi , ẑi = dˆi (fi + ci ẑi+1 ),dˆi = (bi − ci β̂i+1 )−1 , i = N, N − 1, . . . , 1,vi = β̂i vi−1 + ẑi , i = 1, 2, . . .

, N.24(1)(2)(3)(4)МЕТОД ПРОГОНКИПрямая прогонкаМетод встречных прогонокОбратная прогонка25МЕТОД ВСТРЕЧНЫХ ПРОГОНОКvi0 −1 = βi0 −1 vi0 + zi0 −1 ,vi0 +1 = β̂i0 +1 vi0 + zi0 +1fi0 + ai0 zi0 −1 + ci0 ẑi0 −1,(5)bi0 − ai0 βi0 − ci0 βi0 +1= di0 −1 (fi0 −1 + ci0 −1 vi0 + ai0 −1 zi0 −2 ),= dˆi0 +1 (fi0 +1 + ai0 +1 vi0 + ci0 +1 ẑi0 +2 ).vi0 =zi0 −1 = vi0 −1ẑi0 +1 = vi0 +126МЕТОД РЕДУКЦИИ ТРЕХДИАГОНАЛЬНЫХ,ИЛИ ТРЕХТОЧЕЧНЫХ, СЛАУ27МЕТОД РЕДУКЦИИv̄k = ṽk + vik v̌k + vik−1 v̂k ,(6)cik −1, v̌i = βi v̌i+1 ,v̌ik −1 =bik −1 − aik −1 · βik −2aik−1 +1i = ik −2, .