Паралельні та розподілені обчислювальні системи. Лекція 1

Содержание

Слайд 2

Предмет вивчення – паралельні та розподілені обчислення, що застосовуються для опрацювання

Предмет вивчення – паралельні та розподілені обчислення, що застосовуються для опрацювання

й подання даних електронно-обчислювальними методами.

Мета – засвоєння основних методів та алгоритмів організації паралельних та розподілених обчислень, принципів побудови відповідних обчислювальних систем, набуття початкових практичних навиків проектування таких засобів для розв'язання типових задач прикладної математики.

1. Вступ. Місце дисципліни в навчальній програмі.

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

Слайд 3

Кількість кредитів, відповідних ЕСТS: 5 кредитів Кількість змістових модулів: 3 модулів

Кількість кредитів, відповідних ЕСТS: 5 кредитів Кількість змістових модулів: 3 модулів Загальний

обсяг дисципліни – 150 годин.
Слайд 4

Є дуже широкою сферою діяльності: розробка числових методів, вивчення структурних властивостей

Є дуже широкою сферою діяльності: розробка числових методів, вивчення структурних властивостей

алгоритмів, створення нових мов програмування, конструювання унікальних технічних рішень тощо.

Легкодоступна для досліджень: досить мати базові знання, щоб можна було розвиватись самому і розвивати галузь

Є засобом розв’язання задач, які знаходяться на передовому фронті сучасної науки.

Технологія паралельних обчислень актуальна, бо…

1. Вступ. Місце дисципліни в навчальній програмі.

Слайд 5

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи. Звіт Джона фон

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи.

Звіт Джона фон Неймана,

1946 р.:

Комп'ютер складається з процесора, пам'яті і зовнішніх пристроїв.
Єдиним джерелом активності у комп'ютері є процесор, яким керує програма, що знаходиться в пам'яті.
Пам'ять комп'ютера складається з комірок, кожна з яких має свою унікальну адресу. Кожна з комірок зберігає команду програми або елемент даних.
У будь-який момент процесор виконує одну команду програми, адреса якої знаходиться в лічильнику команд.
Інформація надходить у процесор з пам'яті або від зовнішніх пристроїв. Перетворення інформації відбувається тільки в регістрах процесора.
Кожна команда програми містить такі розпорядження:
з яких комірок взяти інформацію;
які операції виконати з цією інформацією;
в які комірки пам'яті помістити отриманий результат;
як змінити вміст лічильника команд.
Процесор виконує команди програми відповідно до зміни вмісту лічильника команд, поки не дістане команду зупинитися.

базові принципи побудови «фон-нейманівської» ЕОМ

Слайд 6

3. Області застосування і задачі паралельної обробки Для яких задач є

3. Області застосування і задачі паралельної обробки

Для яких задач
є зміст

застосовувати паралельні обчислення?
Там, де треба забезпечити:
надвисоку швидкодію,
великий об’єм оперативної пам’яті,
велику кількість інформації, що передається,
обробку і зберігання великого об’єму інформації,
висока відмовостійкість.
Слайд 7

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи. Актуальні напрямки, в

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи.

Актуальні напрямки, в яких

необхідна паралелізація процесів:
чисельне розв’язання задач великої розмірності із багатьма змінними;
моделювання об’єктів і проведення аналізу поведінки складних систем різної природи;
управління складними промисловими та технологічними процесами в режимі реального часу і в умовах невизначеності;
обробка великих об’ємів інформації.

Distributed Computing: 30th International Symposium DISC 2016, Paris, France, September 27-29, 2016. Proceeding.

Слайд 8

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи. Сучасні задачі обчислювальних

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи.

Сучасні задачі обчислювальних систем:
генна

інженерія,
створення лікарських препаратів,
розрахунки в квантовій фізиці, хімії,
обробка даних прямих спостережень в астрофізиці,
моделювання клімату,
криптографія та шифрування,
моделювання економічних систем,
он-лайн ігри,
інтелектуальний аналіз даних,
соціальні мережі,
потік запитів в пошукових або клієнт-серверних системах та ін.
розрахунок та проектування електронних структур,
моделювання і прогнозування соціальних процесів,
3D анімація, рендерінг, обробка відео та аудіо.
Слайд 9

Рубін Ю.В., Белоус Л.Ф., Якуба А.А. Молекулярна і електронна структури фрагмента

Рубін Ю.В., Белоус Л.Ф., Якуба А.А. Молекулярна і електронна структури фрагмента

металізованої ДНК - пари аденін-тимін з іоном цинку
Afanasieva T.V., Koval I.F., Nakhodkin N.G. Адсорбцiя елементiв V групи та кисню на поверхнi Si(001)2х1
Кречкiвська О.М., Косач Д.А., Судаков О.О., Говорун Д.М. Неемпiричне квантово-хiмiчне дослiдження коплементарності основ ДНК iманентною фiзико-хiмiчною властивiстю самих основ.
Сахнiк А.М. Обчислення ab initio методами квантової хімії спектрів коливальних частот протонів, що беруть участь в утворенні водневих зв'язкiв між гуаніном та цитозином у їх кето-/ацето- та амiно-/iмiно-формах.
Залізняк М. Розрахунки прогнозу погоди
Довбешко Г. Молекулярна динаміка нуклеїнових кислот і протеїнів.
Казанцев А. М. Моделювання руху малих небесних тіл сонячної системи за довгий період часу з врахуванням релятивістських ефектів.

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи.

Слайд 10

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи. Стимули розвитку паралельних

2. Сучасні задачі обчислювальних систем. Проблеми та перспективи.

Стимули розвитку паралельних обчислень

та техніки для їх реалізації:
Слайд 11

3. Області застосування і задачі паралельної обробки Основна мета паралельних обчислень

3. Області застосування і задачі паралельної обробки

Основна мета паралельних обчислень –

зменшення часу рішення задачі (у випадку рішень в реальному часі або при необхідності дуже великого обсягу обчислень).
Ще:
• Забезпечити при розв’язання великих задач:
- збільшення деталізації;
- підвищення точності.
• Організувати велике інформаційне навантаження:
- розподілити вхідний потік запитів;
- розподілити місце збереження даних.
• Використовувати усі доступні вільні ресурси.
Задача паралельних обчислень - створення ресурсу паралелізму (одержання паралельного алгоритму) в процесах вирішення завдань і управління реалізацією цього паралелізму з метою досягнення найбільшої ефективності використання відповідної обчислювальної техніки.
Слайд 12

3. Області застосування і задачі паралельної обробки 1. Забезпечення надвисокої швидкодії

3. Області застосування і задачі паралельної обробки

1. Забезпечення надвисокої швидкодії –

складні, багатовимірні задачі, які необхідно розв’язати на протязі досить обмеженого часу.
Приклад: задачі прогнозу погоди.

Прогноз погоди з передбачуваністю 10 днів з 10-ти хвилинним кроком:
продуктивність системи 100 Mflops – витрачений час 107 секунд (~ 100 дн.).
продуктивність 1.7 Tflops – витрачений час 10 хв.

Слайд 13

3. Області застосування і задачі паралельної обробки 2. Необхідність великого об’єму

3. Області застосування і задачі паралельної обробки

2. Необхідність великого об’єму оперативної

пам’яті:
- багатовимірні задачі гідро- і газодинаміки з розрахунку течій з врахуванням різних фізичних і хімічних процесів. Розрахунок одного напрямку вимагає оперативної пам’яті понад 10 Гбайт),
- задачі квантової хімії.

Неемпіричні (Ab initio) розрахунки електронної структури молекул вимагають обчислювальних затрат, пропорційних N4 - N5, де N - кількість молекул.

Молекула кардіотрилу, 46 атомів, 464 = 4 477 456

Слайд 14

3. Області застосування і задачі паралельної обробки 3. Забезпечення передавання великої

3. Області застосування і задачі паралельної обробки

3. Забезпечення передавання великої кількості

інформації.
Приклад: задачі гідро- і газодинаміки із змінними граничними умовами, коли обчислювальний алгоритм постійно вимагає підведення нової інформації.
4. Збільшення деталізації і підвищення точності
Приклад: обчислення тривимірної структури білків з їх амінокислотних послідовностей / Ab initio (проект Розетта).
Слайд 15

3. Області застосування і задачі паралельної обробки Спеціальні проекти розподілених обчислень,

3. Області застосування і задачі паралельної обробки

Спеціальні проекти розподілених обчислень, створені

з метою вільними обчислювальними ресурсами звичайних комп'ютерів допомогти вченим світу вирішувати задачі в різноманітних областях науки і техніки.
В проекті беруть участь власники персональних комп'ютерів, на яких виконуються невеличкі порції-завдання (ПК належать особисто вам, або ви маєте згоду власника на запуск програм проектів на них!)
Програми є безкоштовними, компоненти, які виконують безпосередні розрахунки, базуються на відкритому коді. Участь у програмі безкоштовна та неоплатна.
Обчислення проводяться у фоновому режимі з мінімальним пріоритетом, займаючи 10-20 Мб пам'яті, тому не заважають нормальній роботі з комп'ютером.
Інтернет потрібен лише для отримання завдань і відправки результатів в автоматичному режимі без участі користувача.
Слайд 16

3. Області застосування і задачі паралельної обробки Категорії проектів:

3. Області застосування і задачі паралельної обробки

Категорії проектів:

Слайд 17

3. Області застосування і задачі паралельної обробки

3. Області застосування і задачі паралельної обробки

Слайд 18

Проект Folding@Home – проект розподілених обчислень, що проводиться під егідою Стенфордського

Проект Folding@Home – проект розподілених обчислень, що проводиться під егідою Стенфордського

університету.
В проекті беруть участь більш ніж 165 тис. власників персональних комп'ютерів. Загальна обчислювальна потужність близько 38 Pflops.
Суть проекту полягає в моделюванні процесу фолдінга (згортання у тривимірну структуру) білків з метою виявлення потенційних помилок у природній конформації (просторовому розміщення атомів у молекулі).
Помилки конформації спричиняють ряд клінічних синдромів, серед яких: хвороба Альцгеймера, хвороба Паркінсона, діабет типу II, склероз і деякі типи раку.

3. Області застосування і задачі паралельної обробки

Українська команда розподілених обчислень:

Слайд 19

Проблема «знайти» паралелелізм в послідовності вирішенні задачі. Необхідність перебудови традиційної послідовної


Проблема «знайти» паралелелізм в послідовності вирішенні задачі.
Необхідність перебудови традиційної послідовної

технології розв’язання задач на ЕОМ. Використовувані методи, алгоритми і системне програмне забезпечення повинні забезпечувати створення паралельних програм, організовувати синхронізацію тощо.
Не всі задачі можуть бути розпаралелені на конкретній архітектурі. Залежність ефективності паралелізму від характеристик паралельної обчислювальної системи на відміну від послідовної. Відтак перенесення паралельних алгоритмів і програм між різними типами систем деколи буває взагалі неможливим.

3. Області застосування і задачі паралельної обробки

Складність паралельних обчислень

Слайд 20

4. Короткий огляд сучасних обчислювальних систем. Суперкомп'ютер – обчислювальна машина, яка

4. Короткий огляд сучасних обчислювальних систем.

Суперкомп'ютер – обчислювальна машина, яка значно

перевищує за своїми технічними параметрами більшість існуючих комп'ютерів.
Кластер – група незалежних гетерогенних обчислювальних машин із типовими апаратними та програмними рішеннями, об'єднаних в локальну обчислювальну мережу, що використовуються спільно і працюють як єдиний обчислювальний ресурс.

Кластер Головної астрономічної
обсерваторії НАН України

Кластер Хемніцького технологічного університету (Німеччина)

Суперкомп’ютер Titan, Oak Ridge National Laboratory, (США)

Слайд 21

Флопс, FLOPS (FLoating-point Operations Per Second) – кількість операцій з плаваючою

Флопс, FLOPS (FLoating-point Operations Per Second) – кількість операцій з плаваючою

крапкою в секунду, яку виконує дана обчислювальна система.
IPS (Instruction Per Second) – швидкість виконання команд за одиницю часу, тобто, відношення кількості команд в програмі до часу її виконання.

Вимірювання обчислювальної потужності* комп'ютерів:

4. Короткий огляд сучасних обчислювальних систем.

Слайд 22

Вимірювання продуктивності комп'ютерів 4. Короткий огляд сучасних обчислювальних систем. Тестовий пакет

Вимірювання продуктивності комп'ютерів

4. Короткий огляд сучасних обчислювальних систем.

Тестовий пакет LINPACK - пакет фортран-програм

для рішення систем лінійних алгебраїчних рівнянь. Оцінює обчислювальну потужність системи. (Jack Dongarra, 1979)
Тестовий пакет «High Performance Conjugate Gradients» (HPCG) -  єдиний код для рішення спеціальних видів систем симетричних лінійних рівнянь за допомогою методу сполучених градієнтів (conjugate gradient method). Вимірює продуктивність системи: не тільки обчислювальну потужність, а й оптимальність балансу між обчислювальною потужністю, швидкістю роботи пам'яті і комунікаційних магістралей. (Jack Dongarra, 2012)
Слайд 23

Тор-1 на Червень 2018: Суперкомп’ютер Summit, розроблений ІВМ для Національної лабораторії

Тор-1 на Червень 2018: Суперкомп’ютер Summit, розроблений ІВМ для Національної лабораторії

Oak Ridge Департаменту енергетики США (ORNL)
ядер – 2 282 544 (IBM POWER9, NVIDIA Volta GV100),
реальна обчислювальна потужність – 122,3 Рflops на тесті LINPACK,
- 2,926 Рflops на тесті HPCG,
споживана енергія – 8 806 кВт,

4. Короткий огляд сучасних обчислювальних систем.

Слайд 24

Порівняємо (1946-2018 рр.) Кластер Tianhe-2 (MilkyWay-2), Китайський національний університет оборонних технологій,

Порівняємо (1946-2018 рр.)
Кластер Tianhe-2 (MilkyWay-2), Китайський національний університет оборонних технологій,

Top-1 2015:
ядер – 3 120 000,
реальна обч. потужність – 33,863 Рflops на тесті LINPACK,
енергоспоживання – 17 808 кВт,
складається з 170 шаф
займає площу - 720 м2.
Процесор Intel Core i7-975 XE 3,33 ГГц (2012 р.) – 53,28 Gflops (4 ядра).
Комп'ютер ENIAC (Electronic Numerical Integrator and Computer), 1946 р., маса 27 т:
енергоспоживання - 150 кВт,
реальна обч. потужність - 3000 оп./сек.

4. Короткий огляд сучасних обчислювальних систем.

Слайд 25

Список TOP10 найпотужніших обчислювальних систем у світі Червень 2015 рік Червень

Список TOP10 найпотужніших обчислювальних систем у світі

Червень 2015 рік

Червень 2019

рік

4. Короткий огляд сучасних обчислювальних систем.

Слайд 26

5. Поняття паралельних обчислень Паралельні обчислення – це: Паралельні обчислення –

5. Поняття паралельних обчислень

Паралельні обчислення – це:

Паралельні обчислення – це

обчислення, що підтримуються на математичному, алгоритмічному, програмному чи апаратному рівні (на всіх або декількох) і забезпечують можливість паралельного виконання задачі.

1) спосіб організації комп'ютерних обчислень, при якому програми розробляються, як набір взаємодіючих обчислювальних процесів, що працюють асинхронно і при цьому одночасно.
2) використання декількох або багатьох обчислювальних пристроїв для одночасного виконання різних частин однієї програми (одного проекту).
3) обчислення, які можна реалізувати на багатопроцесорних системах з використанням можливості одночасного виконання багатьох дій, породжуваних процесом вирішення однієї або багатьох завдань (Словник з кібернетики).
4) форма обчислень, в яких кілька дій проводяться одночасно (Вікіпедія).

Слайд 27

3. Поняття паралельних обчислень Паралельні обчислення Багатопроцесорні системи Паралельні обчислення Багатозадачні

3. Поняття паралельних обчислень

Паралельні обчислення

Багатопроцесорні системи

Паралельні обчислення

Багатозадачні режими

Паралельні обчислення

Одночасне виконання операцій

для вирішення спільного загального завдання
Слайд 28

3. Поняття паралельних обчислень Паралельні обчислення Розподілені обчислення Хмарні обчислення Розподілені

3. Поняття паралельних обчислень

Паралельні обчислення

Розподілені обчислення

Хмарні обчислення

Розподілені обчислення – технологія обробки

даних, в якій велике трудомістке завдання (в основному, обчислювальні задачі) розподіляється для виконання між кількома комп'ютерами, об'єднаних в паралельну обчислювальну систему локальною або глобальною мережею.

Хмарні обчислення – технологія обробки даних, в якій комп'ютерні ресурси і потужності надаються як інтернет-сервіс.

Слайд 29

3. Поняття паралельних обчислень Паралельні обчислення на мультипроцесорній системі: об’єднання спеціалізованих

3. Поняття паралельних обчислень

Паралельні обчислення на мультипроцесорній системі:
об’єднання спеціалізованих процесорів;
спеціальне програмне

забезпечення;
спільна пам’ять;
надшвидке з’єднання.

Розподілені обчислення на мультикомп’ютерній системі:
мережа універсальних (стандартних) комп’ютерів із високою швидкодією;
розподілена пам’ять (у кожного своя);
один або кілька керуючих вузлів.

Слайд 30

3. Поняття паралельних обчислень Паралельні завдання – завдання, що допускають одночасне

3. Поняття паралельних обчислень

Паралельні завдання – завдання, що допускають одночасне (НЕ

обов'язково незалежне) виконання.
Паралельний алгоритм – алгоритм, операції якого можуть виконуватися одночасно (не обов'язково незалежно); мається на увазі, що в явному або неявному вигляді вказані одночасно виконувані операції або набір операцій.
Паралельна програма – паралельний алгоритм, записаний в деякому середовищі програмування, орієнтованому на обчислювальні системи паралельної архітектури. Відповідно, техніка створення паралельних програм називається паралельним програмуванням (є підмножиною більш широкого поняття багатопотоковості - multithreading).
Паралельна система – це паралельна програма + паралельна архітектура. Паралельна програма невід’ємна від паралельної архітектури.
Слайд 31

3. Поняття паралельних обчислень Способи паралельної обробки: Чистий паралелізм – технологія,

3. Поняття паралельних обчислень

Способи паралельної обробки:
Чистий паралелізм – технологія, що забезпечує

виконання задач (фун-кцій) шляхом їх розбиття на підзадачі (підфункції) з одночасним виконанням останніх в часі. Характеризується повторним використанням однакових еле-ментів, об’єктів, модулів і дає прямопропорційне зростання продуктивності:
Конвеєризація – метод, що забезпечує сукупність різних дій за рахунок їх розбиття на підфункції зі зміщеним в часі виконанням – кожна мікрооперація задачі виділяється в окремий пристрій (крок або ступінь конвеєра), які розташовуються у порядку виконання відповідних операцій.
Слайд 32

3. Поняття паралельних обчислень Приклад: обчислення площі прямокутника.

3. Поняття паралельних обчислень

Приклад: обчислення площі прямокутника.