Лекция 1. Суперкомпьютерное моделирование. Структура алгоритмов (Электронные лекции)

Московский государственный университет имени М.В.ЛомоносоваФакультет Вычислительной математики и кибернетикиСУПЕРКОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕВМК МГУ, 2016Московский государственный университет имени М.В.ЛомоносоваФакультет Вычислительной математики и кибернетикиСУПЕРКОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕСТРУКТУРА АЛГОРИТМОВВл.В.ВоеводинЗав.кафедрой Суперкомпьютеров и квантовой информатики ВМК МГУЗам.директора НИВЦ МГУ,д.ф.-м.н., профессор, чл.-корр. РАНvoevodin@parallel.ruВМК МГУ, 2016Суперкомпьютер МГУ “Ломоносов”Суперкомпьютер МГУ “Ломоносов-2”Суперкомпьютерный центр МГУ сегодня:Пользователи: 2955Проекты: 880Факультеты / Институты МГУ: 21Институты РАН: 95Университеты России: 1021 стойка = 256 узлов: Intel Xeon (14c) + NVIDIA K40= 515 Tflop/sСуперкомпьютер “Ломоносов-2” (6 стоек) = 3 Pflop/sСтепень параллелизма200520162025104106109Суперкомпьютеры2-412-64104Серверы…14-8103ПК, ноутбуки…11-4102Планшеты, смартфоны…Суперкомпьютер Sunway TaihuLight System, Китай(#1 Top500 в 2016 г.)40 960 вычислительных узлов40 960 CPUs (SW26010, 260 cores)Всего: 10 649 600 ядер1,31 PBytes15,4 MW (6 Gflops/W)Производительность:Peak: 125,4 Pflop/sLinpack: 93 Pflop/s (74%)Тонкий анализ суперкомпьютерных приложений:динамика исполненияТонкий анализ суперкомпьютерных приложений:динамика исполненияТонкий анализ суперкомпьютерных приложений:динамика исполненияЭффективность суперкомпьютерных центров(простая оценка)Пиковая производительность ядра = 12 Gflops400 Mflops = 3,33%Усредненная производительность одного ядрасуперкомпьютера “Чебышев” за 3 дняХорошо ли мы знаем свойства, особенности,статические и динамические характеристикипараллельных алгоритмов?Хорошо ли мы знаем свойства, особенности,статические и динамические характеристикипараллельных алгоритмов?Насколько хорошо мы знаем архитектуру параллельныхкомпьютеров ?А должны ли мы думать об архитектуре?Да… К сожалению, Да…Поколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)Векторно-конвейерные компьютерыСередина 70-х годов.Особенности архитектуры: векторныефункциональные устройства, зацеплениефункциональных устройств, векторныекоманды в системе команд, векторныерегистры.Программирование: векторизация самыхвнутренних циклов.Суперкомпьютер Cray-1Поколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)Векторно-параллельные компьютерыНачало 80-х годов.Суперкомпьютер Cray X-MPОсобенности архитектуры: векторныефункциональные устройства, зацеплениефункциональных устройств, векторныекоманды в системе команд, векторныерегистры.Небольшое число процессоров объединяютсянад общей памятью.Программирование: векторизация самыхвнутренних циклов и распараллеливание навнешнем уровне, единое адресноепространство, локальные и глобальныепеременные.Суперкомпьютер Cray Y-MPПоколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)Массивно-параллельные компьютерыНачало 90-х годов.Особенности архитектуры: тысячипроцессоров объединяются с помощьюкоммуникационной сети по некоторойтопологии, распределенная память.Суперкомпьютер Cray T3DСуперкомпьютер Intel Paragon XPS140Программирование: обмен сообщениями,отсутствие единого адресного пространства,PVM, Message Passing Interface.Необходимость выделения массовогопараллелизма, явного распределения данных исогласования параллелизма с распределением.Поколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)Параллельные компьютеры с общейпамятьюСередина 90-х годов.Особенности архитектуры: сотни процессоровобъединяются над общей памятью.DEC AlphaServerСуперкомпьютер Sun StarFireПрограммирование: единое адресноепространство, локальные и глобальныепеременные, Linda, OpenMP.Поколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)Кластеры из узлов с общей памятьюНачало 2000-х.Суперкомпьютер МГУ “Чебышев”“K” суперкомпьютерОсобенности архитектуры: большое числомногопроцессорных узлов объединяютсявместе с помощью коммуникационной сети понекоторой топологии, распределенная память;в рамках каждого узла несколько(многоядерных) процессоров объединяютсянад общей памятью.Программирование: неоднородная схемаMPI+OpenMP;необходимость выделения массовогопараллелизма, явное распределение данных,обмен сообщениями на внешнем уровне;распараллеливание в едином адресномпространстве, локальные и глобальныепеременные на уровне узла с общей памятью.Поколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)Кластеры из узлов с общей памятью сускорителямиСередина 2000-х.Суперкомпьютер МГУ “Ломоносов”Особенности архитектуры: большое числомногопроцессорных узлов объединяютсявместе с помощью коммуникационной сети понекоторой топологии, распределенная память;в рамках каждого узла несколько(многоядерных) процессоров объединяютсянад общей памятью; на каждом узле несколькоускорителей (GPU, Phi).Программирование:MPI+OpenMP+OpenCL/CUDA;Суперкомпьютер Tianhe-2Поколения архитектур и парадигмы программирования(или как часто мы были вынуждены полностью переписывать приложения?)С 1976 года до наших дней:70-е – Векторизация циклов80-е – Распараллеливание циклов (внешних) + Векторизация (внутренних)90-е - MPIсередина 90-х - OpenMPМожно лисередина 2000-х - MPI+OpenMPвыполнить2010-е - CUDA, OpenCL, MPI+OpenMP+ускорители (GPU,XeonPhi)такойанализ…“раз и навсегда” ?Виден ли конец процессу переписывания программ?..Для каждого поколения компьютеров мы вынуждены:- Анализировать алгоритмы, чтобы понять, как их приспособить подновую компьютерную платформу ;- Описывать найденные свойства, чтобы получить эффективнуюреализацию для новой платформы.Что значит “выполнить анализ алгоритма”?Что мы должны найти в алгоритмах?“…выполнить анализ раз и навсегда…“ – какзаписать результаты?Что представляет “единое” / “универсальное”описание алгоритмов?Какие свойства алгоритмов нужно исследовать иописать чтобы получать эффективные реализациив будущем для будущих платформ?Слишком много “простых” вопросов…Хорошо ли мы знаем свойства, особенности,статические и динамические характеристикипараллельных алгоритмов?Какие свойства алгоритмов важны?На какие свойства алгоритмовнужно обращать внимание?И простые свойства могут быть важны…(объем входных/выходных данных)Нахождение транзитивного замыкания графа:На входе: n вершин, n-1 дуга.На выходе: n вершин, n(n-1)/2 дуга.Социальные сети: 108 вершин, 1011 дуг.И простые свойства могут быть важны…(объём входных/выходных данных)Нахождение транзитивного замыкания графа:На входе: n вершин, n-1 дуга.На выходе: n вершин, n(n-1)/2 дуга.Социальные сети: 108 вершин, 1011 дуг.Вычислительная мощность алгоритма =Число операцийОбъём данныхТест Linpack (решение линейной системы):  nПоэлементное сложение двух векторов:1/3Параллелизм бывает неудобным(Что нужно знать про алгоритмы)#pragma OpenMP parallel forfor( i = 1 ; i <= n ; ++i)for( j = 1 ; j <= m ; ++j)A[i][j] = (A[i][j] * A[i][j-1]) / 2 ;Параллелизм бывает неудобным(Что нужно знать про алгоритмы)#pragma OpenMP parallel forfor( i = 1 ; i <= n ; ++i)for( j = 1 ; j <= m ; ++j)A[i][j] = (A[i][j] * A[i][j-1]) / 2 ;for( i = 1 ; i <= n ; ++i)for( j = 1 ; j <= m ; ++j)A[i][j] = (A[i-1][j] * A[i][j-1]) / 2 ;Локальность определяет многое(Что нужно знать про алгоритмы)(a)(b)(c)(d)(e)(f)A[i] = B[i]*x + cA[i] = B[i]*x + C[i]A[i] = B[i]*X[i] + C[i]A[ind[i]] = B[ind[i]]*x+cA[ind[i]] = B[ind[i]]*x+C[ind[i]]A[ind[i]] = B[ind[i]]*X[ind[i]]+C[ind[i]]Какие свойства должны войти в “универсальное”(“полное”) описание алгоритмов?Описание алгоритмов(Что должно быть учтено в подобном описании?)Информационный граф ДетерминированностьВычислительное ядро Макроструктура Локальность вычисленийМасштабируемость Локальность данныхПроизводительностьМатематическое описаниеСвойства и особенностиЭффективностьКоммуникационный профильСложностьВычислительная мощностьРесурс параллелизмаВходные / Выходные данныеОписание алгоритмов(Что должно быть учтено в подобном описании?)Информационный граф ДетерминированностьВычислительное ядро Макроструктура Локальность вычисленийАлгоритмы:Масштабируемостьтеоретический потенциал Локальность данныхПроизводительностьМатематическое описаниеСвойства и особенности(машинно-независимые свойства)Алгоритмы:ЭффективностьКоммуникационный профильСложностьособенностиреализацииВычислительнаямощностьРесурс параллелизмаВходные / Выходные данныеОписание алгоритмов(на примере разложения Холецкого)Кратко о важномОписание алгоритмов(на примере разложения Холецкого)Общее описаниеМатематическое описаниеКомментарии к алгоритмуОписание алгоритмов(на примере разложения Холецкого)Вычислительное ядроПоследовательная сложностьДополнительная информацияБазовая схема реализацииОписание алгоритмов(на примере разложения Холецкого)Информационная структураИнформационная структура с указанием входных и выходных данныхОписание алгоритмов(на примере разложения Холецкого)Локальность данных (профиль работы с памятью)Описание алгоритмов(на примере разложения Холецкого)Масштабируемость (производительность) *Эффективность ** Масштабируемость, производительность, эффективность измерялись на суперкомпьютере МГУ “Ломоносов”.Описание алгоритмов(на примере разложения Холецкого)Динамические характеристики ** Динамические характеристики получены на суперкомпьютере МГУ “Ломоносов”.Это очень полезная информация об алгоритме,она действительно нужна.Но…Создание полного описания алгоритма это не сложно.Это очень сложно !Информационная структура: как получать, описывать,показывать… ?(сложности описания алгоритмов)- Как изобразить потенциально бесконечный граф ?- Как изобразить потенциально многомерный граф ?- Как показать зависимость структуры графа отразмера задачи ?Информационная структура: как получать, описывать,показывать… ?(сложности описания алгоритмов)Информационная структура: как получать, описывать,показывать… ?(сложности описания алгоритмов)Информационная структура: как получать, описывать,показывать… ?(сложности описания алгоритмов)Как выразить имеющийся параллелизм и показать возможный способпараллельного исполнения ?Информационная структура: как получать, описывать,показывать… ?(сложности описания алгоритмов)Шаг 1Шаг 2Шаг 4Шаг 5Цвета в ярусно-параллельной форме:Красный – слой выполняющихся операций; Зеленый – уже выполненные операции;Белый – операции должны выполниться позже.Шаг 3Потенциальный параллелизм: как находить, описывать,показывать… ?(сложности описания алгоритмов)init processE = E1  E2  …  EkMST(E) = MST(E1  E2  …  Ek) =compute MSTcompute MST= MST( MST(E1)  MST(E2)  …  MST(Ek))compute MSTsolve resultsexitМинимальное остовное дерево (MST)(ресурс “математического” параллелизма)…compute MSTПотенциальный параллелизм: как находить, описывать,показывать… ?(сложности описания алгоритмов)331122233…3……} |E|5555…5} |E|6666…6} |V|77777} |V|8888…8} |V|9999…9} |V|1} |V|2} |V|V – множество вершинE – множество дуг3333444455557777………3} |E|4} |E|5} |E|7} |V|Недетерминизм (нерегулярность)…12Минимальное остовное дерево(ресурс классического параллелизма)Следующая итерациявыход1011…Одна итерацияНедетерминизм (нерегулярность)1Структура алгоритмов: возможные варианты дляпараллельного кода(сложности описания алгоритмов)Предположим, что мы знаем потенциальный параллелизм алгоритма...Как выразить “потенциальную свободу” в выборе походящей формыдля параллельной программы ?Структура алгоритмов: возможные варианты дляпараллельного кода(сложности описания алгоритмов)Циклический профиль алгоритма / программыСамый внешний цикл (отмечен “1”) - параллельный.Можно ли сделать данный цикл самым внутренним, чтобы векторизовать?Структура алгоритмов: возможные варианты дляпараллельного кода(сложности описания алгоритмов)Эта последовательностьпреобразований делаетисходный внешний цикл(1) внутренним ипозволяет векторизоватьпрограмму (алгоритм).Как показать подобныйпотенциалпреобразований в общемслучае?Возможные источники несбалансированности:это важно, это нужно отметить(сложности описания алгоритмов)Баланс между арифметическими операциями +/- and * ;Баланс между арифметическими операциями и “чтениями/записями”;Возможные источники несбалансированности:это важно, это нужно отметить(сложности описания алгоритмов)Баланс между арифметическими операциями +/- and * ;Баланс между арифметическими операциями и “чтениями/записями”;Баланс в числе операций, которыемогут выполняться параллельно;Баланс между вычислительной и коммуникационной частями…Возможные источники недетерминизма:это важно, это нужно отметить(сложности описания алгоритмов)Структура входных данных (разреженные матрицы, графыпроизвольной структуры…);Итерационная природа алгоритмов;Датчики случайных чисел;Отсутствие повторяемости результатов из-за разного порядкавыполнения ассоциативных операций…Локальность данных: множество открытых вопросов(сложности описания алгоритмов)Как оценивать пространственную* и временную** локальность данныхв программе ?Как сравнивать пространственную и временную локальность данныхразных программ ?* Пространственная локальность данных – насколько близко друг к другу расположены последовательные обращения в память.** Временная локальность данных – насколько часто происходят обращения к одним и тем же данным.LinpackFFTRandom AccessЛокальность данных: множество открытых вопросов(сложности описания алгоритмов)Как оценивать пространственную и временную локальность данных впрограмме ?Как сравнивать пространственную и временную локальность данныхразных программ ?Можем ли мы предсказывать локальность данных в будущихреализациях, опираясь только на информацию об алгоритмах?Что означает “локальность алгоритма” ?Что означает “алгоритм обладает хорошей/плохой локальностью” ?В алгоритмах нет структур данных, а значит и понятие “локальность” кним напрямую не применимо! Вместе с этим, алгоритмы определяютсуть программ, где локальность уместна и важна.Коммуникационный профиль приложений(сложности описания алгоритмов)MPI_Reduce( buf, …)MPI_Reduce( buf, …)MPI_Reduce( buf, …)А что такое коммуникационный профиль приложений?Как его получить и описывать? (Scalasca, Vampir…)Все ли мы знаем о разложении Холецкого ?Да…Кажется, что Да…Фундаментальный вопрос:Что означает выполнить полное описание алгоритма?Пока ответа не знает никто...Разновидности одного алгоритма…(сложности описания алгоритмов)Алгоритмы и их реализацииAАЛГОРИТМЫПРОГРАММЫP1 P2 P3КОМПЬЮТЕРНЫЕ ПЛАТФОРМЫCДостаточно ли у нас информации об алгоритме A, чтобы создатьэффективную реализацию для платформы C?Можем ли мы использовать реализации P1, P2, P3 или мы должны создаватьеще одну реализацию P для платформы C?Элементы суперкомпьютерного кодизайнаСтруктура и свойства алгоритмов(от мобильных платформ до экзафлопсных суперкомпьютеров)Информационный граф ДетерминированностьВычислительное ядро Макроструктура Локальность вычисленийАлгоритмы:Масштабируемостьтеоретический потенциал Локальность данныхПроизводительностьМатематическое описаниеСвойства и особенности(машинно-независимые свойства)Алгоритмы:ЭффективностьКоммуникационный профильСложностьособенностиреализацииВычислительнаямощностьРесурс параллелизмаВходные / Выходные данныеAlgoWikihttp://AlgoWiki-Project.orgAlgoWikihttp://AlgoWiki-Project.orgAlgoWikiВнимание, зачетное задание!Описание структуры и особенностей алгоритма(ов).Формат: AlgoWiki.Алгоритмы – список будет представлен на Parallel.ru/SS16Описание алгоритмов необходимо выполнять по принятой в AlgoWikiструктуре.Регистрация на сайте для создания описания в формате AlgoWiki.Одно задание можно выполнять группой в два человека.Реализация: полностью собственная или обращение к библиотечнойфункции (Intel MKL, PETc, FFTW, ScaLAPACK).В любом случае, текст исследуемой программы должен бытьпредставлен в отчете.Компьютерная платформа может быть любой (Ломоносов, BlueGene иличто-то иное).