Огляд та оцінка необхідності використання паралельних та розподілених систем 2



Сторінка1/17
Дата конвертації11.03.2016
Розмір2.11 Mb.
  1   2   3   4   5   6   7   8   9   ...   17

ВСТУП
ОГЛЯД ТА ОЦІНКА НЕОБХІДНОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ ТА РОЗПОДІЛЕНИХ СИСТЕМ 2

РОЗДІЛ 1
Паралельні системи 3

[1].Класифікація паралельних систем 3

Паралельні обчислення в мікропроцесорах 3

Класифікація паралельних обчислювальних систем 7

[2].Моделювання та організація паралельних обчислень 15

Принципи побудови паралельних алгоритмів 15

Моделі паралельних обчислень 21

Інженерний підхід до організації паралельних обчислень 26

Метод організації складних паралельних обчислень з функціональним паралелізмом 30

Методи передачі даних 33

[3].Паралельні чисельні методи для рішення типових задач обчислювальної математики 35

Обчислення суми послідовності чисел 35

Множення матриці на вектор 42

Матричне множення 50

Сортування 56

[4].Моделі функціонування паралельних програм 67

Концепція процесу 68

Поняття ресурсу 69

Організація програм як системи процесів 70

Взаємодія і взаємовиключення процесів 74

Модель програми у вигляді дискретної системи 75

Модель програми у вигляді мережі Петрі 81

[5].Побудова оцінок ефективності та масштабування паралельних обчислень 85

Аналіз трудомісткості основних операцій передачі даних 91

Методи логічного представлення топології комунікаційного середовища 103

[6].Висновки 105

[7].Питання для самоконтролю 107

РОЗДІЛ 2
РОЗПОДІЛЕНІ СИСТЕМИ 109

1.Інтерфейси запуску та керування завданнями в Grid 139

2.Gridsphere та P-Grade 140

3.Lunarc Application Portal 141

4.BioSimGrid 142

5.Вимоги до архітектури комплексної системи віртуальних лабораторій в Grid-інфраструктурі 143

6.Архітектура системи 144

7.Авторизація 145

8.Зв'язок з програмним забезпеченням Grid. 146

[1].Інфраструктура Grid в НТУУ «КПІ» 148

[2].Завдання для індивідуальних досліджень з Державної програми „Створення національної Grid-інфраструктури для науки і освіти” 150

[3].Висновки 151

[4].Питання для самоконтролю 153

РОЗДІЛ 3
Технології організації сучасних розподілених процесів 154

[1]. Передумови переходу до сучасних технологій, орієнтованих на обробку великих масивів даних. 157

[2].Модель програмування MapReduce та платформа Hadoop 159

Огляд MapReduce 159

Реалізація 160

Огляд процессу виконання роботи 161

Структури даних майстра 163

Відмовостійкість 164

Платформа Apache Hadoop 164

Архітектура Hadoop 166

HDFS 166


Вузол NameNode 167

Вузол DataNode 168

[3].Tехнологія Dryad та система DryadLINQ 172

Програмування з LINQ 173

Виконуючий механізм 175

DryadLINQ Модель програмування 179

[4].Порівняння технологій високопродуктивної обробки даних 188

[5].Висновки 191

[6].Питання для самоконтролю 192

РОЗДІЛ 4
Хмарні обчислення 193

[1].Cloud Computing та Grid 193

[2].Основні характеристики хмарних обчислень 194

Масштабованість 194

Еластичність 195

Мультітенантність 195

Сплата за використання 195

Самообслуговування 196

[3].Технічні рішення Cloud Computing 196

[4].Архітектура Cloud Computing 197

[5].Хмарні хостинги, IaaS 198

Amazon EC2 199

Amazon Simple Storage Service (Amazon S3) 201

Microsoft Azure 202

[6].Хмарні контейнери, PaaS 205

Google App Engine 205

[7].Хмарні сервіси 207

Google Apps 208

[8].Відкриті технології Cloud Computing 210

[9].Перспективи розвитку хмарних обчилень та проект Flexcloud 211

[10].Висновки 212

[11].Питання для самоконтролю 214

Список літератури 215


ВСТУП
ОГЛЯД ТА ОЦІНКА НЕОБХІДНОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ ТА РОЗПОДІЛЕНИХ СИСТЕМ


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

дефіциту різноманітних обчислювальних ресурсів в глобальному середовищі;

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

Ефективним шляхом вирішення цих проблем є використання паралельних обчислень.

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

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

аналіз ефективності паралельних обчислень для оцінювання одержуваного прискорення, обчислень і ступеня використання всіх можливостей комп'ютерного устаткування при паралельних способах рішення задач;

створення і розвиток паралельних алгоритмів для вирішення прикладних завдань у різних практичних областях;

розробка паралельних програмних систем;

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


РОЗДІЛ 1
Паралельні системи

[1].Класифікація паралельних систем


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

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


Паралельні обчислення в мікропроцесорах


У 1965 році Гордон Мур зазначив, що кількість транзисторів, доступних для виробників напівпровідників, подвоюється приблизно кожні 18-24 місяці. Тепер цим спостереженням, відомим як закон Мура, керуються дизайнери комп'ютерів протягом останніх 40 років . Багато людей помилково вважають закон Мура передбаченням процесора зі зростаючою тактовою частотою, і це дійсно не важко зрозуміти, чому. Адже найбільш часто використовувана метрика вимірювання продуктивності обчислень - тактова частота процесора. За останні 40 років усе відбувалося саме за цим законом. Та хоча підвищення пропускної здатності та тактової частоти варто прагнути, розробникам можуть скористатися не такими очевидними перевагами використання багатьох транзисторів.

Наприклад, щоб забезпечити максимально ефективне використання ресурсів процесора, розробники використовують методи розпаралелювання на рівні інструкцій. Розпаралелювання на рівні інструкцій (instruction-level parallelism (ILP)), також відоме як динамічне, або невпорядковане виконання, дає процесору можливість реорганізувати чергу команд, щоб усунути зупинки в конвейєрі. Мета ILP-технології полягає у збільшенні числа команд, які виконуються процесором за один такт. Для того, щоб ILP-технологія була ефективною, повинні виконуватися багато незалежних інструкції. У разі виконання команд почергово залежності між інструкціями можуть призвести до обмеження і, відповідно, зменшення числа команд для паралельного виконання. Альтернативний підхід, який намагається зберегти повне навантаження на процесорні одиниці, це – зміна порядку виконання інструкцій так, щоб незалежні інструкції виконувалися одночасно. Це динамічне планування черги виконує сам процесор. Як тільки з`явилось відповідне програмне забезпечення, продуктивність прикладних програм зросла завдяки здатності одночасного виконання декількох задач. Серверне ПЗ сьогодні обов`язково підтримує множинні потоки чи процесори. Для підтримки розпаралелювання на рівні потоків було прийнято декілька підходів, як в плані програмного, так і апаратного забезпечення.

Один з підходів для отримання паралелізму у сучасному ПЗ - використання багатозадачних операцій системи чи системи з пріоритетним перериванням. Розподіл на часові слоти та багатопоточність дозволяє розробникам приховувати затримки пов`язані з вводом/виводом шляхом чегування виконання багатьох потоків. Але це модель не паралельного виконання. Тільки один потік інструкцій може оброблятися процесором в одній точці в один час. Багатопроцесорні системи дозволяють істинно паралельне виконання; кілька потоків або процесів, що працюють одночасно на декількох процесорах. Компроміс, досягнутий у цьому випадку, веде до збільшення загальної вартості системи. Розробники помітили, що при намаганні досягнути розпаралелювання на рівні потоків в багатьох випадках ресурси сучасних процесорів не використовувались на 100 відсотків. Для того, щоб оптимізувати цей підхід, необхідно спочатку розглянути більш детально, що являє собою потік виконання в програмі. Потік може бути визначений як основна одиниця навантаження на процесор. Він містить програмний лічильник, який вказує на поточну інструкцію в потоці, інформацію про стан процесора для даного потоку, також інші ресурси, такі як стек.

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

Однак для того, щоб визначити потік, потрібна тільки архітектура. Логічний процесор може бути створеним шляхом дублювання цієї просторової архітектури. Виконавчі ресурси потім розподіляються між різними логічними процесорами. Цей метод відомий як одночасна багатопоточність (Simultaneous Multi-Threading, або SMT). Реалізації SMT від Intel відома як технологія Hyper-Threading (HT). Технологія HT дозволяє одному процесору виступати з точки зору програмного забезпечення як декілька логічних процесорів. Це дозволяє операційним системам і програмам розпоряджатися декількома потоками для логічних процесорів так, немов вони працюють на багатопроцесорних системах. З точки зору мікроархітектури, інструкції від логічних процесорів є стійкими і виконуються одночасно на спільних ресурсах. Іншими словами, кілька потоків можуть бути заплановані для виконання, але так як ресурси спільні, то як і коли виконання двох потоків буде чергуватися залежить від мікроархітектури. Коли один потік зупиняється, іншому дозволяється виконуватись. Ці зупинки включають обробки невдалих запитів з кешу і неправильних прогнозів переходів.

Наступним логічним кроком після одночасної багатопоточності є багатоядерні процесори. Багатоядерні процесори використовують чіпи багатопроцесорної обробки (CMP). Замість того, щоб повторно використовувати обрані процесорні ресурси в одноядерному процесорі, розробники вирішили використати два чи більше обчислювальних ядра в одному процесорі. Ці ядра по суті два окремих процесори на одному кристалі. Обчислювальні ядра мають свої власні інструкції виконання і архітектурні ресурси. Залежно від конструкції, ці процесори можуть розділяти або не розділяти кеш-пам'ять. Крім того, ці окремі ядра можуть бути об'єднані з SMT, ефективно збільшуючи кількість логічних процесорів у два рази від кількості виконавчих ядер. Різні процесорні архітектури наведені на рис.1.1.




Рис. 1.1. Порівняння одноядерних, мультипроцесорних та багатоядерних архітектур


Класифікація паралельних обчислювальних систем


Одним з найбільш поширених способів класифікації ЕОМ є систематика Флінна (Flynn) (рис. 1.2), у рамках якої основна увага при аналізі архітектури обчислювальних систем приділяється способам взаємодії послідовностей (потоків) команд, що виконуються та обробляємих даних. В результаті такого підходу розрізняють наступні основні типи систем:

Single Instruction, Single Data (SISD) – системи, в яких існує одиночний потік команд і одиночний потік даних; до цього типа систем можно віднести звичайні послідовні ЕОМ;

Single Instruction, Multiple Data (SIMD) – системи з одиночним потоком команд і множинним потоком даних; подібний клас систем складають багатопроцесорні обчислювальні системи (БОС), в котрих у кожний момент часу може виконуватися одна й таж сама команда для обробки декількох інформаційних елементів;

Multiple Instruction, Single Data (MISD) – системи, в котрих існує множинний потік команд і одиночний потік даних; прикладом конкретних ЕОМ, відповідаючих даному типу обчислювальних систем, не існує; введення подібного класу робиться для повноти системи класифікації;

Multiple Instruction, Multiple Data (MIMD) – системи з множинним потоком команд і множинним потоком даних; до подібного класу систем відноситься більшість паралельних багатопроцесорних обчислювальних систем.

Рис. 1.2. Систематика Флінна

Варто відмітити, що хоча систематика Флінна широко використовується при конкретизації типів комп'ютерних систем, така класифікація призводить до того, що практично усі види паралельних систем (незважаючи на їх суттєву рознорідність) відносяться до однієї групи MIMD. Як результат, багатьома дослідниками робилися неодноразові спроби деталізації систематики Флінна. Так, наприклад, для класа MIMD запропонована практично загальновизнана структурна схема, в якій подальше розподілення типів багатопроцесорних систем базується на використовуваних способах організації оперативної пам'яті в цих системах (рис. 1.3). Даний підхід дозволяє розрізняти два важливих типа багатопроцесорних систем – мультипроцесори (системи з загальною розподіленою пам'яттю) і мультикомп'ютери (системи з розподіленою пам'яттю).

Рис. 1.3. Структура класа багатопроцесорних обчислювальних систем

Далі для мультипроцесорів враховується спосіб побудови загальної пам'яті. Можливий підхід – використання єдиної (централізованої) загальної пам'яті. Цей підхід забеспечує однорідний доступ до пам'яті (uniform memory access, UMA) і служить основою для побудови векторних суперкомп'ютерів (parallel vector processor, PVP) і симетричних мультипроцесорів (symmetric multiprocessor , SMP).

Загальний доступ до даних може здійснюватися і при фізично розподіленій пам'яті (при цьому тривалість доступу вже не буде однаковою для усіх елементов пам'яті), тобто пам'ять фізично розподілена, проте логічно загальнодоступна. Цей підхід називається неоднорідним доступом до пам'яті (non-uniform memory access, NUMA). Серед систем з таким типом пам'яті виділяють:



  1. системи, в яких для представлення даних використовується тільки локальна кеш пам'ять процесорів, що використовуються (cache-only memory architecture, COMA);

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

  3. системи, в яких забеспечується загальний доступ до локальнгої пам'яті різних процесорів без піддтримки на апаратному рівні когерентності кеша (non-cache coherent NUMA, NCC-NUMA).

Мультикомп'ютери вже не забезпечують загальний доступ до всієї пам'яті в системах (no-remote memory access, NORMA). Даний підхід використовується при побудові двох важливих типів багатопроцесорних обчислювальних систем – масивно-паралельні системи (massively parallel processor, MPP) і кластери (clusters).

Більш детальний опис властивостей різних видів мультипроцесорних систем та мультикомп'ютерів наведен в табл. 1.1 і в табл. 1.2 відповідно.

Таблиця 1.1

Опис властивостей мультипроцесорних систем



Симетричні мультипроцесорні системи – SMP

Архітектура

Система складається з декількох однорідних процесорів і масива загальної пам'яті. Всі процеси мають доступ до будь-якого місця пам'яті з однаковою швидкістю. Процесори підключені до пам'яті за допомогою загальної шини (базові 2-4 процесорні SMP-сервири) або crossbar-комутатора (HP 9000). Апаратно підтримується когерентність кешей.

Приклади

HP 9000 V-class, N-class; SMP-сервери і робочі станції на базі процесоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu та ін.).

Масштабованість

Наявність загальної пам'яті сильно спрощує взаємодію процесорів між собою, однак накладаються сильні обмеження на їх кількість. Для побудови масштабованих систем на базі SMP використовуються кластерні або NUMA-архітектури.

Операційна система

Вся система працює під управлінням єдиної ОС (зазвичай UNIX-подібній, проте для Intel-платформ підтримується Windows NT). ОС автоматично (в процесі роботи) розподіляє процеси по процесорам , проте інколи можлива й явна прив'язка.

Модель програмування

Програмування в моделі загальної пам'яті (POSIX threads, OpenMP). Для SMP-систем існують порівняно ефективні засоби автоматичного розпаралелювання.

Паралельні векторні системи – PVP

Архітектура

Основною ознакою PVP-систем є присутність спеціальних векторно-конвеєрних процесорів, в яких передбачені команди однотипної обробки векторів незалежних даних, які ефективно виконуються на конвеєрних функціональних пристроях.

Як правило, декілька таких процесорів (1-16) працюють одночасно над загальною пам'яттю (аналогічно SMP) у рамках багатопроцесорної конфігурації. Декілька таких вузлів можуть бути об'єднані за допомогою комутатора (аналогічно MPP).



Приклади

NEC SX-4/SX-5, лінія векторно-конвеєрних комп'ютерів CRAY: від CRAY-1, CRAY J90/T90, CRAY SV1, CRAY X1, серія Fujitsu VPP.

Модель програмування

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

Системи з неоднорідним доступом до пам'яті – NUMA

Архітектура

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

Приклади

HP 9000 V-classу SCA-конфігураціях, SGI Origin2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000, SNI RM600.

Масштабованість

Масштабування NUMA-систем обмежується об'ємом адресного простору, можливостями апаратури підтримки когерентності кешей і можливостями операційної системи по управлінню великою кількістю процесорів. В теперішній час максимальна кількість процесорів в NUMA-системах складає 256 (Origin2000).

Операційна система

Зазвичай уся система працює під управлінням єдиної ОС, як в SMP. Однак можливі також варіанти динамічного “підрозділення” системи, коли окремі “розділи” системи працюють під управлінням різних ОС (наприклад, Windows NT та UNIX у NUMA-Q 2000).

Модель програмування

Аналогічно SMP.

Таблиця 1.2

Опис властивостей мультикомп'ютерів

Масивно-паралельні системи – MPP

Архітектура

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

Приклади

IBM RS/6000 SP2, Intel PARAGON/ASCI Red, CRAY T3E, Hitachi SR8000, транспьютерні системи Parsytec.

Масштабованість

Загальна кількість процесорів у реальних системах досягає декількох тисяч (ASCI Red).

Операційна система

Повноцінна ОС працює тільки на управляючій машині, на кожному вузлі працює сильно урізаний варіант ОС, що забезпечую тільки роботу гілки паралельного виконання, що знаходиться в ньому. Приклад: Cray T3E.

Інший варіант, коли на кожному вузлі працює повноцінна UNIX-подібна ОС (варіант, близький до кластерного підходу). Приклад: IBM RS/6000 SP + ОС AIX, що встановлюється на кожному вузлі.



Модель програмування

Програмування в рамках моделі передачі повідомлень Message Passing Interface(MPI), Parallel Virtual Machine.

Кластерні системи

Архітектура

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

Для зв'язку вузлів використовується одна з стандартних технологій (Fast/Gigabit Ethernet, Myrinet) на базі шинної архітектури та комутатора.

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


Приклади

NT-кластерв NCSA, Beowulf-кластери.

Операційна система

Використовуються стандартні для робочих станцій ОС, частіше всього, вільно поширювальні – Linux/FreeBSD, разом з спеціальними засобами підтримки паралельного програмування та розподілення навантаження.

Модель програмування

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

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

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

  1   2   3   4   5   6   7   8   9   ...   17


База даних захищена авторським правом ©refs.in.ua 2016
звернутися до адміністрації

    Головна сторінка