Введение в параллельные алгоритмы: Введение © Якобовский М.В. 3. Производительность одного вычислительного ядра (Gflops) Тактовая частота процессора (GHz).


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Интернет Университет
Суперкомпьютерных технологий
Введение
Учебный курс
пведение в параллельные
алгоритмы
Якобовский М.В., проф., д.ф.
м.н.
Институт прикладной математики
им. М.В.Келдыша РАН, Москва
Цель курса
Знакомство с методами разработки
параллельных алгоритмов
Изучение свойств программ, выполняющихся на
многопроцессорных вычислительных системах
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Производительность процессора
�� &#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;&#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
100
200
300
400
500
600
700
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
CPU(Gflops)
кратный рост
Производительность
одного вычислительного ядра (
flops
Тактовая
частота
процессора
(GHz)
�� &#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;&#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
Частота (
GHz)
Ядро(
Gflops)
Число операций, выполняемых
процессорным ядром за один такт
�� &#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;&#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
Gflops/GHz
Некоторые системы
top500.org
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Суперкомпьютер
Cores
Rmax
Tflops
Rpeak
Tflops
Power
Процессор
Sunway
TaihuLight
10
649
600
93
014
125
436
15
37
Sunway SW26010
260C

1.45GHz
K computer

705 024
10 510
12 280
12.66
SPARC64
VIIIfx
8C

2GHz
Tianhe
2 (MilkyWay
2)
120
000
33
862
54
902
17
81
Intel Xeon E5
2692v2
12C

2.2GHz
Intel Xeon Phi 31S1P
57

1.1GHz
Sequoia,
BlueGene
1
72 864
16 325
20
132

7.89
Power BQC
16C

1.60
GHz
Lomonosov
42
688

102
962

Xeon E5
2697v3
14C

2.6GHz
Время мощных вычислительных систем, имеющих в
своем составе только один процессор прошло
Вычислительная мощность суперкомпьютеров
огромна, но:
Она образована суммой мощностей множества
исполнительных устройств
На протяжении многих лет увеличение
производительность компьютера автоматически
означало снижение времени работы
существующих программ. Теперь это не так:
Последовательные программы не могут
работать на суперкомпьютерах
быстрее,
чем на
однопроцессорных (одноядерных) компьютерах
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
IBM PowerPC® A2 1.6 GHz, 16 cores per node
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Robert W. Wisniewski. BlueGene/Q:
Architecture, CoDesign; Path to
Exascale / Blue Gene Supercomputer
Research, January 25, 2012
Использование мощностей суперкомпьютеров
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Не конкретизировано
Исследования
Использование
суперкомпьютеров
�� &#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;&#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Не конкретизировано
Исследования
�� &#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;&#x/BBo;&#xx [1;.9;͒ ;.0;ʘ ;ȁ.;ᄥ&#x 24.;ᅲ&#x ]/S;&#xubty;&#xpe /;oot;r /;&#xType;&#x /Pa;&#xgina;&#xtion;&#x 000;Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Использование мощностей суперкомпьютеров
Прикладные исследования
Industry
Фундаментальные исследования
Области применения многопроцессорных
систем
сокращение времени решения вычислительно
сложных задач
сокращение времени обработки больших
объемов данных
решение задач реального времени
4) создание систем высокой надежности
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Задачи большого вызова
Вычислительная газовая динамика:
Создание летательных аппаратов, эффективных автомобильных
Предсказания погоды, и глобальных климатических изменений
Оптимизация нефтедобычи
Молекулярная динамика:
Создание материалов с заданными свойствами
Разработка новых лекарственных соединений
Сверхпроводимость, Свойства веществ в экстремальных состояниях, …
Символьные вычисления
Распознавание речи
Компьютерное зрение
Изучение сложных систем
Автономные системы управления
Квантовая хромодинамика и теория конденсированных сред
Управляемый термоядерный синтез, Геном человека,
http://en.wikipedia.org/wiki/Grand_Challenge
��Москва, 2016 г.
��13 &#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;&#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Дозвуковая аэродинамическая труба Т
104, ЦАГИ
Скорость потока
120 м/с
Диаметр сопла 7 м
Длина рабочей части 13 м
Мощность вентилятора
28.4
МВт
http://www.tsagi.ru/rus/base/t104
Суперкомпьютер СКИФ МГУ
«ЧЕБЫШЁВ»
Пиковая производительность 60
TFlop
Мощность комплекса
0.72
МВт
http://parallel.ru/cluster/skif_msu.html
��Москва, 2016 г.
��14 &#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;&#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;Введение в параллельные алгоритмы: Введение © Якобовский М.В.
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Круг рассматриваемых систем
Системы на основе объединенных сетью
типовых вычислительных узлов
системы с
распределенной оперативной памятью
Системы с доступом всех процессоров к общей
оперативной памяти
Графические ускорители
ПЛИС
Нейрокомпьютеры
Другие
процессор
память
сеть
процессор
память
��17 &#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;&#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;Введение в параллельные алгоритмы: Введение © Якобовский М.В.
��Москва, 2016 г.
Оптический векторно
матричный умножитель
8·10
операций умножения и сложения в секунду (8
TMips
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Д.Колисниченко
. Оптические процессоры. /
http
://
dkws
narod
linux
etc
optical
cpu
html
Энергопотребление процессора составляет 40 Вт (5 мВт на 1 млрд. операций в секунду)

гига
тера
пета
экса
Вычислительные системы
многопроцессорные
Автоматическое создание параллельных
программ невозможно
Необходимо знать существующие и развивать
новые параллельные методы решения задач
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Некоторые из принципов фон Неймана
Принцип последовательного программного
управления
Программа состоит из набора команд, которые
выполняются процессором друг за другом в
определенной последовательности
Принцип адресуемости памяти
Память состоит из пронумерованных ячеек
Процессору в произвольный момент времени доступна
любая ячейка
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Уточнение круга рассматриваемых алгоритмов
Слабо взаимодействующие последовательные
процессы
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
��21 &#x/MCI; 36;&#x 000;&#x/MCI; 36;&#x 000;Вычисления
Вычисления
Взаимодействие
Отличие от систем фон Неймана
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
��22 &#x/MCI; 42;&#x 000;&#x/MCI; 42;&#x 000;Принцип последовательного
программного управления
Программа состоит из набора команд,
которые выполняются процессором друг за
другом в определенной последовательности
Принцип адресуемости памяти
Память состоит из пронумерованных ячеек
Процессору в произвольный момент
времени доступна любая ячейка
Вычисления
Взаимодействие
Характеристика необходимых знаний и
умений
Для успешного освоения основного
материала курса необходимо:
Знание основ программирования
Общее представление об архитектуре
вычислительных систем фон Неймана
Умение оценивать вычислительную сложность
простых алгоритмов
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Характеристика необходимых знаний и
умений
Для выполнения практических заданий
необходимы навыки разработки простых
параллельных программ, например:
на основе
MPI
для систем с распределенной
памятью
на основе
OpenMP
или стандарта
Posix
для
систем с общей памятью
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Содержание курса
Средства описания параллельных
алгоритмов
Методы построения параллельных
алгоритмов
Параллельные алгоритмы сортировки данных
Параллельные алгоритмы генерации
псевдослучайных чисел
Динамическая балансировка загрузки
процессоров
Параллельные алгоритмы решения систем
линейных уравнений
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Средства описания параллельных алгоритмов
Приложение, выполняющееся на
вычислительной системе с распределенной
памятью
Передача сообщений
Приложение, выполняющееся на
вычислительной системе с общей памятью
Семафоры
Нити
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Методы построения параллельных алгоритмов
Виды параллелизма
Метод сдваивания
Геометрический параллелизм
Метод коллективного решения
Конвейерный параллелизм
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Динамическая балансировка загрузки процессоров
Общий взгляд на классификацию методов
балансировки загрузки процессоров
Задачи, требующие применения методов
динамической балансировки загрузки
Пример простого алгоритма динамической
балансировки загрузки
Статическая
Динамическая
диффузная
Динамическая
не зависит от времени
меняется медленно
меняется значительно

непрогнозируемо
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
100
200
300
400
500
600
Эффективность
сетка
1000
1000
Заключение
Время однопроцессорных вычислительных систем
прошло
Не только суперкомпьютеры, но и современные
персональные компьютеры, ноутбуки, планшеты, мобильные
телефоны, основаны на многопроцессорных, многоядерных и
других технологиях, предполагающих одновременное
выполнение множества инструкций
Для их полноценного использования необходимо понимание
основ параллельных архитектур и умение создавать
логически простые, но эффективные алгоритмы
(на что и направлен курс)
��Москва, 2016 г.
��32 &#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;&#x/BBo;&#xx [2;9.3; ;.7;̄ ;ֈ.;E ;#.9;ࡲ ;&#x]/Su; typ; /F;&#xoote;&#xr /T;&#xype ;&#x/Pag;&#xinat;&#xion ;Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Литература…
Якобовский М.В.
Введение в параллельные методы решения задач:
Учебное пособие /
Предисл
.: В. А. Садовничий.
М.: Издательство
Московского университета, 2012.
328 с.,
илл
.
(Серия
«Суперкомпьютерное образование»), ISBN 978
211
06382
Лацис А.О.
Параллельная обработка данных.
М.: Академия, 2010 г.
336 стр. ISBN

7695
5951
Якобовский М.В.
http://lira.imamod.ru
Воеводин В.В., Воеводин Вл.В.
Параллельные вычисления.
СПб.:
БХВ
Петербург
, 2002.
Грегори Р.
Эндрюс
Основы многопоточного, параллельного и
распределенного программирования. "Вильямс ", 2003
Языки
програмирования
. Редактор
Ф.Женюи
. Перевод с англ.
В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972
Э.
Дейкстра
.
Взаимодействие последовательных процессов.
http://khpi
iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Литература…
Учебные курсы Интернет Университета Информационных технологий
Гергель В.П.
Теория и практика параллельных вычислений.
http://www.intuit.ru/department/calculate/paralltp/

Лекции в форме
видео
конференций
Гергель В.П.
Основы параллельных вычислений.
http://www.hpcu.ru/courses/15/
Немнюгин С.А.
Основы параллельного программирования с использованием
MPI .

http://www.hpcu.ru/courses/14/
Крюков В.А., Бахтин В.А.
Параллельное программирование с
OpenMP
.
http://www.hpcu.ru/courses/16/
Дополнительные учебные курсы:
Воеводин В.В.
Вычислительная математика и структура алгоритмов.
http://www.intuit.ru/department/calculate/calcalgo/

��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Литература
Ресурсы
http://top500.org
http://supercomputers.ru
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Вопросы для обсуждения
Какие классы задач решаются с применением
многопроцессорных систем и суперкомпьютеров?
Какие факторы препятствуют эффективному
использованию многопроцессорных систем?
В чем качественное отличие многопроцессорных
систем от систем архитектуры фон Неймана?
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.
Якобовский М.В.
, профессор, д.ф.
м.н., зав. сектором
«Программного обеспечения многопроцессорных систем
и вычислительных сетей» Института прикладной
математики им. М.В.Келдыша Российской академии наук
mail
[email protected]
web
http
//lira
imamod
Контакты
��Москва, 2016 г.
��Введение в параллельные алгоритмы: Введение © Якобовский М.В.

Приложенные файлы

  • pdf 8217149
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий