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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Московский государственный университет имени М.В.ЛомоносоваФакультет Вычислительной математики и кибернетикиСУПЕРКОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕВМК МГУ, 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 иличто-то иное).

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций