20160905_msu_yak_01a (Лекции)

Введениеhttp://lira.imamod.ru/msu201609/ПараллельныевысокопроизводительныевычисленияЯкобовский М.В., проф., д.ф.-м.н.СКИ МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, МоскваМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.1Цель курсаЗнакомство с методами разработкипараллельных алгоритмовИзучение свойств программ, выполняющихся намногопроцессорных вычислительных системахМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.2Производительность процессора700CPU(Gflops)600500400120 кратный рост300200100Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.201520142013201220112010200920082007200620052004200320022001200003Производительность и тактоваячастота процессорного ядра403530Частота (GHz)Ядро(Gflops)252015105Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.201520142013201220112010200920082007200620052004200320022001200004Число операций,выполняемых процессорнымядром за один такт181614Gflops/GHz12108642Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.201520142013201220112010200920082007200620052004200320022001200005Некоторые системы top500.orgСуперкомпьютерSunway TaihuLightK computerCoresRmaxTflopsRpeakTflopsPowerMWПроцессор10 649 60093 014125 43615.37Sunway SW26010260C1.45GHz705 02410 51012 28012.66SPARC64 VIIIfx8C2GHzIntel Xeon E5-2692v212C2.2GHzTianhe-2 (MilkyWay-2)3 120 00033 86254 90217.81Intel Xeon Phi 31S1P57C1.1GHzPower BQCSequoia, BlueGene/Q1 572 86416 32520 1327.8916C1.60GHzLomonosov 242 6882 1022 9621.08Xeon E5-2697v314C2.6GHzВремя мощных вычислительных систем, имеющих всвоем составе только один процессор прошлоМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.6Вычислительная мощность суперкомпьютеровогромна, но:– Она образована суммой мощностей множестваисполнительных устройствНа протяжении многих лет увеличениепроизводительность компьютера автоматическиозначало снижение времени работысуществующих программ.

Теперь это не так:– Последовательные программы не могутработать на суперкомпьютерах быстрее, чем наоднопроцессорных (одноядерных) компьютерахМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.7IBM PowerPC® A2 1.6 GHz, 16 cores per nodeRobert W. Wisniewski. BlueGene/Q:Architecture, CoDesign; Path toExascale / Blue Gene SupercomputerResearch, January 25, 2012Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.8Использование мощностей суперкомпьютеровНе конкретизированоИсследованияМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.9ИспользованиесуперкомпьютеровНе конкретизированоИсследованияМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.10Использование мощностей суперкомпьютеровФундаментальные исследованияПрикладные исследованияIndustryМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.11Области применения многопроцессорныхсистем1) сокращение времени решения вычислительносложных задач2) сокращение времени обработки большихобъемов данных3) решение задач реального времени4) создание систем высокой надежностиМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.12Задачи большого вызова(Kenneth G.

Wilson, Cornell University, 1987)Вычислительная газовая динамика:– Создание летательных аппаратов, эффективных автомобильных– Предсказания погоды, и глобальных климатических изменений– Оптимизация нефтедобычи, …Молекулярная динамика:– Создание материалов с заданными свойствами– Разработка новых лекарственных соединений– Сверхпроводимость, Свойства веществ в экстремальных состояниях, …Символьные вычисления––––Распознавание речиКомпьютерное зрениеИзучение сложных системАвтономные системы управленияКвантовая хромодинамика и теория конденсированных средУправляемый термоядерный синтез, Геном человека, …Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.13http://en.wikipedia.org/wiki/Grand_ChallengeДозвуковая аэродинамическая труба Т-104, ЦАГИСкорость потока 10–120 м/сДиаметр сопла 7 мДлина рабочей части 13 мМощность вентилятора28.4 МВтhttp://www.tsagi.ru/rus/base/t104•Суперкомпьютер СКИФ МГУ«ЧЕБЫШЁВ»Пиковая производительность 60 TFlop/s•Мощность комплекса 0.72 МВтhttp://parallel.ru/cluster/skif_msu.htmlМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.14Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.15Особенности моментаПотребность в суперкомпьютерах высокаЭффективность использования суперкомпьютеров низка:– Использование каждого ядра последовательной программойсоставляет проценты и доли процентов– Обмены, синхронизация и другие дополнительные операцииснижают эффективность параллельной программыЕсть минимальный объем вычислений на процессорноеядро, определяющий число используемых ядер За счет многопроцессорности сложно сокращать времямоделирования физического процесса, но можно повышатьсложность решаемых задач, например за счет увеличенияразмеров изучаемых объектов16Круг рассматриваемых системСистемы на основе объединенных сетьютиповых вычислительных узлов – системы сраспределенной оперативной памятьюпроцессорпамятьсетьСистемы с доступом всех процессоров к общейоперативной памятипроцессорГрафические ускорители ПЛИС Нейрокомпьютеры Другие …Москва, 2016 г.памятьПараллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.17Оптический векторно-матричный умножитель8·1012 операций умножения и сложения в секунду (8TMips)109 – гига1012 – тера1015 – пета1018 – эксаЭнергопотребление процессора составляет 40 Вт (5 мВт на 1 млрд.

операций в секунду)Д.Колисниченко. Оптические процессоры. /URL: http://dkws.narod.ru/linux/etc/optical/cpu.htmlМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.18Вычислительные системы - многопроцессорныеАвтоматическое создание параллельныхпрограмм невозможноНеобходимо знать существующие и развиватьновые параллельные методы решения задачМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.19Некоторые из принципов фон НейманаПринцип последовательного программногоуправления– Программа состоит из набора команд, которыевыполняются процессором друг за другом вопределенной последовательностиПринцип адресуемости памяти– Память состоит из пронумерованных ячеек– Процессору в произвольный момент времени доступналюбая ячейкаМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.20Уточнение круга рассматриваемых алгоритмовСлабо взаимодействующие последовательныепроцессыВычисленияВычисленияВзаимодействиеМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.21Отличие от систем фон НейманаПринцип последовательногопрограммного управленияПрограмма состоит из набора команд,которые выполняются процессором друг задругом в определенной последовательностиПринцип адресуемости памятиВычисленияПамять состоит из пронумерованных ячеекПроцессору в произвольный моментвремени доступна любая ячейкаВзаимодействиеМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.22Характеристика необходимых знаний иуменийДля успешного освоения основногоматериала курса необходимо:– Знание основ программирования– Общее представление об архитектуревычислительных систем фон Неймана– Умение оценивать вычислительную сложностьпростых алгоритмовМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.23Характеристика необходимых знаний иуменийДля выполнения практических заданийнеобходимы навыки разработки простыхпараллельных программ, например:– на основе MPI для систем с распределеннойпамятью– на основе OpenMP или стандарта Posix длясистем с общей памятьюМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.24Содержание курсаСредства описания параллельных алгоритмов Методы построения параллельных алгоритмов Параллельные алгоритмы сортировки данных Параллельные алгоритмы генерациипсевдослучайных чисел Динамическая балансировка загрузки процессоров Параллельные алгоритмы решения систем линейныхуравнений …Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.25Средства описания параллельных алгоритмовПриложение, выполняющееся навычислительной системе с распределеннойпамятью– Передача сообщенийПриложение, выполняющееся навычислительной системе с общей памятью– Семафоры– НитиМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.26Методы построения параллельных алгоритмовВиды параллелизма––––Метод сдваиванияГеометрический параллелизмМетод коллективного решенияКонвейерный параллелизмМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.27Динамическая балансировка загрузки процессоровОбщий взгляд на классификацию методовбалансировки загрузки процессоров Задачи, требующие применения методовдинамической балансировки загрузки Пример простого алгоритма динамическойбалансировки загрузкиДинамическаядиффузнаяСтатическаяДинамическая?Москва, 2016 г.Wij = WijWij ≈ Wij-1Wij ≠ Wij-1– не зависит от времени– меняется медленно– меняется значительнои непрогнозируемоПараллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.2829Эффективность100%сетка 1000x100090%80%70%60%50%40%30%20%10%0%010020030040050060030Основные мотивы возникновения курсаСложность создания параллельных алгоритмов ипрограмм:– Неадекватность алгоритмов архитектуре ЭВМ– Недетерминированность параллельных программ– Возможность возникновения тупиковТребует привлечения:– Апробированных, логически простых методов,гарантированно дающих положительный эффектМосква, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.31ЗаключениеВремя однопроцессорных вычислительных системпрошлоНе только суперкомпьютеры, но и современныеперсональные компьютеры, ноутбуки, планшеты, мобильныетелефоны, основаны на многопроцессорных, многоядерных идругих технологиях, предполагающих одновременноевыполнение множества инструкцийДля их полноценного использования необходимо пониманиеоснов параллельных архитектур и умение создаватьлогически простые, но эффективные алгоритмы(на что и направлен курс)Москва, 2016 г.Параллельные высокопроизводительные вычисления: Введение ©Якобовский М.В.32Литература…http://lira.imamod.ru/msu201609/ - ресурс курса Якобовский М.В.