Поточна версія сторінки поки не перевірялася
Поточна версія сторінки поки не перевірялася досвідченими учасниками і може значно відрізнятися від, перевіреної 5 жовтня 2014; перевірки вимагають.
паралельні обчислення - спосіб організації комп'ютерних обчислень, при якому програми розробляються як набір взаємодіючих обчислювальних процесів, що працюють паралельно (одночасно). Термін охоплює сукупність питань паралелізму в програмуванні, а також створення ефективно діючих апаратних реалізацій. Теорія паралельних обчислень становить розділ прикладної теорії алгоритмів.
Існують різні способи реалізації паралельних обчислень. Наприклад, кожен обчислювальний процес може бути реалізований у вигляді процесу операційної системи, або ж обчислювальні процеси можуть являти собою набір потоків виконання всередині одного процесу ОС. Паралельні програми можуть фізично виконуватися або послідовно на єдиному процесорі - перемежовуючи по черзі кроки виконання кожного обчислювального процесу, або паралельно - виділяючи кожному обчислювальному процесу один або кілька процесорів (що знаходяться поруч або розподілених в комп'ютерну мережу).
Основна складність при проектуванні паралельних програм - забезпечити правильну послідовність взаємодій між різними обчислювальними процесами, а також координацію ресурсів, що розділяються між процесами.
У деяких паралельних системах програмування передача даних між компонентами прихована від програміста (наприклад, за допомогою механізму обіцянок), тоді як в інших вона повинна вказуватися явно. Явні взаємодії можуть бути розділені на два типи:
Паралельні системи, засновані на обміні повідомленнями, часто більш прості для розуміння, ніж системи з пам'яттю, що, і зазвичай розглядаються як більш досконалий метод паралельного програмування. Існує великий вибір математичних теорій для вивчення і аналізу систем з передачею повідомлень, включаючи модель акторів і різні види обчислень процесів. Обмін повідомленнями може бути ефективно реалізований на симетричних мультипроцесорах як з розділяється когерентної пам'яттю, так і без неї.
У паралелізму з розподіленою пам'яттю і з передачею повідомлень різні характеристики продуктивності. Зазвичай (але не завжди), накладні витрати пам'яті на процес і часу на перемикання завдань у систем з передачею повідомлень нижче, проте передача самих повідомлень більш накладна, ніж виклики процедур. Ці відмінності часто перекриваються іншими факторами, що впливають на продуктивність.
Міністерство освіти і науки Російської Федерації
Федеральне агентство з освіти
Південно-Російський державний технічний університет
(Новочеркаський політехнічний інститут)
Шахтинський інститут (філія) ЮРГТУ (НПІ)
ЛЕКЦІЇ ПО ДИСЦИПЛІНИ
«ПАРАЛЕЛЬНІ ОБЧИСЛЕННЯ»
шахти- 2010
Вступ
Основні поняття
1. Загальні питання рішення "; великих завдань";
1.1 Сучасні завдання науки і техніки, що вимагають для вирішення суперкомп'ютери
1.2.2 Абстрактні моделі паралельних обчислень
1.2.3 Способи паралельної обробки даних, похибка обчислень
1.3 Поняття паралельного процесу і гранули розпаралелювання
1.4 Взаємодія паралельних процесів, синхронізація процесів
1.5 Можливе прискорення при паралельних обчисленнях (закон Амдаля)
2. Принципи побудови багатопроцесорних обчислювальних систем
2.1 Архітектура багатопроцесорних обчислювальних систем
2.2 Розподіл обчислень і даних в багатопроцесорних обчислювальних системах з розподіленою пам'яттю
2.3 Класифікація паралельних обчислювальних систем
2.4 Багатопроцесорні обчислювальні системи c розподіленою пам'яттю
2.4.1 Масивно-паралельні суперкомп'ютери серії Cry T3
2.4.2 Кластерні системи класу BEOWULF
висновок
Список літератури
Вступ
Ще на зорі комп'ютерної ери, приблизно в середині минулого століття, конструктори електронно-обчислювальних машин задумалися над можливістю застосування паралельних обчислень в комп'ютерах. Адже збільшення швидкодії тільки за рахунок вдосконалення електронних компонентів комп'ютера - досить дорогий спосіб, який, до того ж, стикається з обмеженнями, що накладаються фізичними законами. Так паралельна обробка даних і паралелізм команд були введені в конструкцію комп'ютерів і зараз будь-який користувач "; персональні виставки" ;, можливо, сам того не знаючи, працює на паралельному комп'ютері.
Однією з помітних тенденцій розвитку людства є бажання максимально строго моделювати процеси навколишньої дійсності з метою як поліпшення умов життя в сьогоденні, так і максимально достовірного передбачення майбутнього. Математичні методи і прийоми цифрового моделювання в багатьох випадках дозволяють вирішувати подібні проблеми, проте з плином часу має місце серйозне якісне і кількісне ускладнення технології вирішення завдань. У багатьох випадках обмеженням є недолік обчислювальних потужностей сучасних електронно-обчислювальних машинах, але значимість вирішуваних завдань залучили величезні фінансові ресурси в область створення надскладних електронно-обчислювальних машин.
З деяких пір підвищення швидкодії комп'ютерів традиційної (іменованої "; фон Неймановская";) архітектури стало надмірно дорого внаслідок технологічних обмежень при виробництві процесорів, тому розробники звернули увагу на інший шлях підвищення продуктивності - об'єднання електронно-обчислювальних машин в багатопроцесорні обчислювальні системи. При цьому окремі фрагменти програми паралельно (і одночасно) виконуються на різних процесорах, обмінюючись інформацією за допомогою внутрішньої комп'ютерної мережі.
Ідея об'єднання електронно-обчислювальних машин з метою підвищення, як продуктивності, так і надійності відомі з кінця п'ятдесятих років.
Вимоги отримати максимум продуктивності при мінімальній вартості привели до розробки багатопроцесорних обчислювальних комплексів; відомі системи такого роду, які об'єднують обчислювальні потужності тисяч окремих процесорів. Наступним етапом є спроби об'єднати мільйони різнорідних комп'ютерів планети в єдиний обчислювальний комплекс з величезною продуктивністю за допомогою мережі Internet. На сьогоднішній день застосування паралельних обчислювальних систем є стратегічним напрямком розвитку обчислювальної техніки. Розвиток "; заліза"; з необхідністю підкріплюються вдосконаленням алгоритмічної і програмної компонент - технологій паралельного програмування.
Метод розпаралелювання обчислень існує вже давно, організація спільного функціонування безлічі незалежних процесорів вимагає проведення серйозних теоретико-практичних досліджень, без яких складна і щодо дорога многопроцессорная установка часто не тільки не перевершує, а поступається по продуктивності традиційного комп'ютера.
Потенційна можливість розпаралелювання неоднакова для обчислювальних задач різного типу - вона значна для наукових програм, що містять багато циклів і тривалих обчислень і істотно менше для інженерних задач, для яких характерний розрахунок за емпіричними формулами.
Розглянемо два основних питання:
1. Багатопроцесорні обчислювальні системи - (масивно-паралельні суперкомп'ютери) Cray T3D (E) з кількістю процесорів від 40 до 2176. Це суперкомп'ютери з розподіленою пам'яттю на RISC-процесорах типу Alpha21164A, з топологією комунікаційної мережі - тривимірний тор, операційною системою UNIX з мікроядром і трансляторами для мов FORTRAN, HPF, C / C ++. Підтримувані моделі програмування: MPI, PVM, HPF.
2. Беовульф-кластери робочих станцій. Кластери робочих станцій - сукупність робочих станцій, з'єднаних в локальну мережу. Кластер - обчислювальна система з розподіленою пам'яттю і розподіленим управлінням. Кластерна система може володіти продуктивністю, порівнянної з продуктивністю суперкомп'ютерів. Кластери робочих станцій зазвичай називають Беовульф-кластерами (Beowulf cluster - за однойменним проектом), пов'язані локальною мережею Ethernet і використовують операційну систему Linux.
Основні поняття
Найбільш поширеною технологією програмування для кластерних систем і паралельних комп'ютерів з розподіленою пам'яттю в даний час є технологія MPI. Основним способом взаємодії паралельних процесів в таких системах є передача повідомлень один одному. Це і відображено в назві даної технології - Message Passing Interface (інтерфейс передачі повідомлень). Стандарт MPI фіксує інтерфейс, який повинен дотримуватися як системою програмування на кожній обчислювальної платформі, так і користувачем при створенні своїх програм. MPI підтримує роботу з мовами Фортран і Сі. Повна версія інтерфейсу містить опис більше 125 процедур і функцій.
Інтерфейс MPI підтримує створення паралельних програм в стилі MIMD (Multiple Instruction Multiple Data), що має на увазі об'єднання процесів з різними вихідними текстами. Однак писати і налагоджувати такі програми дуже складно, тому на практиці програмісти, набагато частіше використовують SPMD-модел' (Single Program Multiple Data) паралельного програмування, в рамках якої для всіх паралельних процесів використовується один і той же код. В даний час все більше і більше реалізацій MPI підтримують роботу з так званими "; нитками" ;.
Оскільки MPI є бібліотекою, то при компіляції програми необхідно прілінкованние відповідні бібліотечні модулі.
Після отримання здійсненного файлу необхідно запустити його на необхідній кількості процесорів. Після запуску одна і та ж програма буде виконуватися всіма запущеними процесами, результат виконання в залежності від системи буде видаватися на термінал або записуватися в файл.
MPI програма - це безліч паралельних взаємодіючих процесів. Всі процеси породжуються один раз, утворюючи паралельну частина програми. В ході виконання MPI-програми породження додаткових процесів або знищення існуючих не допускається (в подальших версіях MPI така можливість з'явилася). Кожен процес працює у своєму адресному просторі, ніяких загальних змінних або даних в MPI немає. Основним способом взаємодії між процесами є явна посилка повідомлень.
Для локалізації взаємодії паралельних процесів програми можна створювати групи процесів, надаючи їм окрему середу для спілкування - комунікатор. Склад утворених груп довільний. Групи можуть повністю збігатися, входити одна в іншу, не перетинатися або перетинатися частково. Процеси можуть взаємодіяти тільки всередині деякого комунікатора, повідомлення, відправлені в різних комунікаторах, не перетинаються і не заважають один одному. Комунікатори мають в мові Фортран тип integer (в мові Сі - зумовлений тип MPI Comm).
При старті програми завжди вважається, що всі породжені процеси працюють в рамках всеосяжного комунікатора. Цей комунікатор існує завжди і служить для взаємодії всіх запущених процесів MPI-програми. Всі взаємодії процесів протікають в рамках певного комунікатора, повідомлення, передані в різних комунікаторах, ніяк не заважають один одному.
Процесори з скороченим набором команд (RISC). В основі RISC-архітектури (RISC - Reduced Instruction Set Computer) процесора лежить ідея збільшення швидкості його роботи за рахунок спрощення набору команд.
Дослідження показали, що 33% команд типової програми складають пересилання даних, 20% - умовні розгалуження і ще 16% - арифметичні і логічні операції. У переважній більшості команд обчислення адреси може бути виконано швидко, за один цикл. Більш складні режими адресації використовуються приблизно в 18% випадків. Близько 75% операндів є скалярними, тобто змінними цілого, дійсного, символьного типу і т. Д., А решта є масивами і структурами. 80% скалярних змінних - локальні, а 90% структурних є глобальними. Таким чином, більшість операндів - це локальні операнди скалярних типів. Вони можуть зберігатися в регістрах.
Згідно зі статистикою, більша частина часу витрачається на обробку операторів "; виклик підпрограми"; і "; повернення з підпрограми" ;. При компіляції ці оператори породжують довгі послідовності машинних команд з великим числом звернень до пам'яті, тому навіть якщо частка цих операторів становить всього 15%, вони споживають основну частину процесорного часу. Тільки близько 1% підпрограм мають більш шести параметрів, а близько 7% підпрограм містять більше шести локальних змінних.
В результаті вивчення цієї статистики був зроблений висновок про те, що в типовій програмі домінують прості операції: арифметичні, логічні і пересилання даних. Домінують і прості режими адресації. Велика частина операндів - це скалярні локальні змінні. Одним з найважливіших ресурсів підвищення продуктивності є оптимізація зазначених операторів.
В основу RISC-архітектури покладено такі принципи та ідеї. Набір команд повинен бути обмеженим і включати тільки прості команди, час виконання яких після вибірки і декодування один такт або трохи більше. Використовується конвеєрна обробка. Прості RISC-команди допускають ефективну апаратну реалізацію, в той час як складні команди можуть бути реалізовані тільки засобами микропрограммирования. Конструкція пристрою управління в разі RISC-архітектури спрощується, і це дає можливість процесору працювати на великих тактових частотах. Використання простих команд дозволяє ефективно реалізувати і конвеєрну обробку даних, і виконання команд.
Складні команди RISC-процесором виконуються довше, але їх кількість відносно невелика. В RISC-процесорах невелике число команд адресується до пам'яті. Вибірка даних з оперативної пам'яті вимагає більш одного такту. Велика частина команд працює з операндами, що знаходяться в регістрах. Всі команди мають уніфікований формат і фіксовану довжину. Це спрощує і прискорює завантаження і декодування команд, оскільки, наприклад, код операції і поле адреси завжди знаходяться в одній і тій же позиції. Змінні і проміжні результати обчислень можуть зберігатися в регістрах. З урахуванням статистики використання змінних, більшу частину локальних змінних і параметрів процедур можна розмістити в регістрах. При виклику нової процедури вміст регістрів зазвичай переміщається в оперативну пам'ять, проте, якщо кількість регістрів досить велике, вдається уникнути значної частини тривалих операцій обміну з пам'яттю, замінивши їх операціями з регістрами. Завдяки спрощеній архітектурі RISC-процесора, на мікросхемі з'являється місце для розміщення додаткового набору регістрів.
В даний час обчислювальні системи з RISC-архітектурою займають лідируючі позиції на світовому комп'ютерному ринку робочих станцій і серверів. Розвиток RISC-архітектури пов'язане з розвитком компіляторів, які повинні ефективно використовувати переваги великого реєстрового файлу, конвейеризации і т. Д.
1. Загальні питання рішення "; великих завдань";
Під терміном "; великі завдання"; зазвичай розуміють проблеми, вирішення яких вимагає не тільки побудови складних математичних моделей, а й проведення величезного, на багато порядків перевищують характерні для програмованих електронно-обчислювальних машин, кількості обчислень. Тут застосовують з відповідними ресурсами електронно-обчислювальні машини - розмірами оперативної і зовнішньої пам'яті, швидкодією ліній передачі інформації та ін.
Верхня межа кількості обчислень для "; великих завдань"; визначається лише продуктивністю існуючих на даний момент обчислювальних систем. При "; прогоні"; обчислювальних задач в реальних умовах ставиться не питання "; вирішити задачу взагалі" ;, а "; вирішити за прийнятний час"; (Годинник / десятки годин).
1.1. Сучасні завдання науки і техніки, що вимагають
для вирішення суперкомп'ютери
Досить часто доводиться стикатися з такими завданнями, які, представляючи неабияку цінність для суспільства, не можуть бути вирішені за допомогою щодо повільних комп'ютерів офісного або домашнього класу. Єдина надія в цьому випадку покладається на комп'ютери з великим швидкодією, які прийнято називати суперкомпьютерами. Тільки машини такого класу можуть впоратися з обробкою великих обсягів інформації. Це можуть бути, наприклад, статистичні дані або результати метеорологічних спостережень, фінансова інформація. Іноді швидкість обробки має вирішальне значення. Як приклад можна привести складання прогнозу погоди і моделювання кліматичних змін. Чим раніше передбачене стихійне лихо, тим більше можливостей підготуватися до нього. Важливим завданням є моделювання лікарських засобів, розшифровка генома людини, томографія, в тому числі і медична, розвідка родовищ нафти і газу. Прикладів можна навести багато.
Моделювання процесів навколишньої дійсності з метою як поліпшення умов життя в сьогоденні, так і достовірного передбачення майбутнього, є однією з тенденцій розвитку людства. Математичні методи і прийоми цифрового моделювання в багатьох випадках дозволяють вирішувати подібні проблеми, проте з плином часу має місце ускладнення технології вирішення подібних завдань. У багатьох випадках обмеженням є недолік обчислювальних потужностей сучасних електронно-обчислювальних машин.
Вимоги отримати максимум продуктивності при мінімальній вартості привели до розробки багатопроцесорних обчислювальних комплексів; відомі системи такого роду, які об'єднують обчислювальні потужності тисяч окремих процесорів.
Нижче перераховані деякі області людської діяльності, що вимагають для свого рішення суперкомп'ютерних потужностей використовують паралельні обчислення:
Передбачення погоди, клімату і глобальних змін в атмосфері
Науки про матеріали
Побудова напівпровідникових приладів
надпровідність
Розробка фармацевтичних препаратів
генетика людини
Астрономія
Транспортні задачі великої розмірності
Гідро та газодинаміка
Керований термоядерний синтез
Розвідка нафти і газу
Обчислювальні завдання наук про світовому океані
Розпізнавання і синтез мови, розпізнавання зображень
Одна з найсерйозніших завдань - моделювання кліматичної системи і передбачення погоди. При цьому спільно чисельно вирішуються рівняння динаміки суцільного середовища і рівняння рівноважної термодинаміки. Для моделювання розвитку атмосферних процесів протягом 100 років і числі елементів дискретизації 2,6 × 106 (сітка з кроком 10 за широтою та довготою по всій поверхні Планети при 20 шарах по висоті, стан кожного елемента описується 10 компонентами) в будь-який момент часу стан земної атмосфери описується 2,6 × 107 числами. При кроці дискретизації по часу 10 хвилин за модельований проміжок часу необхідно визначити 5 × 104 ансамблів (тобто 1014 необхідних числових значень проміжних обчислень). При оцінці числа необхідних для отримання кожного проміжного результату обчислювальних операцій в 102 ÷ 103 загальне число необхідних для проведення чисельного експерименту з глобальною моделлю атмосфери обчислень з плаваючою точкою доходить до 1016 ÷ 1017.
Суперкомп'ютер з продуктивністю 1012 оп / сек при ідеальному випадку (повна завантаженість і ефективна алгоритмизация) буде виконувати такий експеримент протягом декількох годин; для проведення повного процесу моделювання необхідна багаторазова (десятки / сотні разів) прогін програми.
Проблема суперобчислень настільки важлива, що багато держав курирують роботи в області суперкомп'ютерних технологій.
Державна підтримка прямо пов'язана з тим, що незалежність в області виробництва і використання обчислювальної техніки відповідає інтересам національної безпеки, а науковий потенціал країни безпосередньо пов'язаний і великою мірою визначається рівнем розвитку обчислювальної техніки і математичного забезпечення.
З метою об'єктивності при порівнянні продуктивність супер-електронно-обчислювальних машин розраховується на основі виконання заздалегідь відомої тестової задачі ( "; бенчмарка" ;, від англ. Benchmark). Пікова продуктивність визначається максимальним числом операцій, яке може бути виконане за одиничне час при відсутності зв'язків між функціональними пристроями, характеризує потенційні можливості апаратури і не залежить від виконуваної програми.
Недоліком методу оцінки пікової продуктивності як числа виконуваних комп'ютером команд в одиницю часу (MIPS, Million Instruction Per Second) дає тільки загальне уявлення про швидкодію, тому що не враховує специфіку конкретних програм (важко передбачувано, в яке число і яких саме інструкцій процесора відобразиться призначена для користувача програма).
Необхідно відзначити, що існують аргументи проти широкого практичного застосування паралельних обчислень:
Паралельні обчислювальні системи надмірно дороги. За підтверджуваному практикою закону Гроша, продуктивність комп'ютера зростає пропорційно квадрату його вартості; в результаті набагато вигідніше отримати необхідну обчислювальну потужність придбанням одного продуктивного процесора, ніж використання декількох менш швидкодіючих процесорів.
Контраргумент. Зростання швидкодії послідовних електронно-обчислювальних машин не може тривати нескінченно, комп'ютери схильні до швидкого морального старіння та необхідні часті фінансові витрати на покупку нових моделей. Практика створення паралельних обчислювальних систем класу Beowulf ясно показала економічність саме цього шляху.
При організації паралелізму надмірно швидко ростуть втрати продуктивності. За гіпотезою Мінського (Marvin Minsky) досягається при використанні паралельної системи прискорення обчислень пропорційно двійкового логарифму від числа процесорів (при 1000 процесорах можливе прискорення виявляється рівним всього 10).
Контраргумент. Наведена оцінка прискорення вірна для розпаралелювання певних алгоритмів. Однак існує велика кількість завдань, при паралельному вирішенні яких досягається близьке до 100% використання всіх наявних процесорів паралельної обчислювальної системи.
Послідовні комп'ютери постійно удосконалюються. За широко відомому закону Мура складність послідовних мікропроцесорів зростає вдвічі кожні 18 місяців, тому необхідна продуктивність може бути досягнута і на "; звичайних"; послідовних комп'ютерах.
Контраргумент. Аналогічне розвиток властиво і паралельним системам.
Однак застосування паралелізму дозволяє отримувати необхідне прискорення обчислень без очікування розробки нових більш швидкодіючих процесорів. Ефективність паралелізму сильно залежить від характерних властивостей паралельних систем. Всі сучасні послідовні електронно-обчислювальні машини працюють у відповідність з класичною схемою фон-Неймана; паралельні системи відрізняються істотним різноманітністю архітектури і максимальний ефект від використання паралелізму може бути отриманий при повному використанні всіх особливостей апаратури (наслідок - перенесення паралельних алгоритмів і програм між різними типами систем скрутний, а іноді і неможливий).
Контраргумент. При реально наявному розмаїтті архітектур паралельних систем існують і певні "; усталені"; способи забезпечення паралелізму. Инвариантность створюваного програмного забезпечення забезпечується за допомогою використання стандартних програмних засобів підтримки паралельних обчислень (програмні бібліотеки PVM, MPI, DVM і ін.). PVM і MPI використовуються в суперкомп'ютерах Cray-T3.
За десятиліття експлуатації послідовних електронно-обчислювальних машинах накопичена величезна програмне забезпечення, орієнтоване на послідовні електронно-обчислювальні машини; переробка його для паралельних комп'ютерів практично нереальна.
Контраргумент. Якщо ці програми забезпечують рішення поставлених завдань, то їх переробка взагалі не потрібна. Однак якщо послідовні програми не дозволяють отримувати вирішення завдань за прийнятний час або ж виникає необхідність вирішення нових завдань, то необхідна розробка нового програмного забезпечення і воно спочатку може реалізовуватися в паралельному виконанні.
Існує обмеження на прискорення обчислення при паралельній реалізації алгоритму в порівнянні з послідовною.
Контраргумент. Справді, алгоритмів взагалі без (певної) частки послідовних обчислень не існує. Однак це суть властивість алгоритму і не має відношення до можливості паралельного рішення задачі взагалі. Необхідно навчитися застосовувати нові алгоритми, більш підходящі для вирішення завдань на паралельних системах.
Таким чином, на кожне критичне міркування проти використання паралельних обчислювальних технологій знаходиться більш-менш істотний контраргумент.
1.2 Паралельна обробка даних
1.2.1 Принципова можливість паралельної обробки
Практично всі розроблені до теперішнього часу алгоритми є послідовними. Наприклад, при обчисленні виразу a + b × c, спочатку необхідно виконати множення і тільки потім виконати складання. Якщо в електронно-обчислювальних машин присутні вузли додавання і множення, які можуть працювати одночасно, то в даному випадку вузол складання буде простоювати в очікуванні завершення роботи вузла множення. Можна довести твердження, що складається в тому, що можливо побудувати машину, яка заданий алгоритм буде обробляти паралельно.
Можна побудувати m процесорів, які при одночасній роботі видають потрібний результат за один-єдиний такт роботи обчислювача.
Такі "; багатопроцесорні"; машини теоретично можна побудувати для кожного конкретного алгоритму і, здавалося б, "; обійти"; послідовний характер алгоритмів. Однак не все так просто - конкретних алгоритмів нескінченно багато, тому розвинені вище абстрактні міркування мають не настільки прямий стосунок до практичної значущості. Їх розвиток переконало в самій можливості розпаралелювання, стало основою концепції необмеженого паралелізму, дало можливість розглядати із загальних позицій реалізацію так званих обчислювальних середовищ - багатопроцесорних систем, динамічно настроюються під конкретний алгоритм.
Надіслати свою хорошу роботу в базу знань просто. Використовуйте форму, розташовану нижче
Студенти, аспіранти, молоді вчені, які використовують базу знань в своє навчання і роботи, будуть вам дуже вдячні.
Розміщено на http://www.allbest.ru/
Розміщено на http://www.allbest.ru/
- Вступ
- 1. Актуальність теми
- 2. Збільшення кількості ядер
- 3. Технологія NVIDIA CUDA
- 4. Різниця між CPU і GPU
- висновок
- Вступ
- Розпаралелювання обчислень - це поділ великих завдань на більш маленькі, які можуть виконуватися одночасно. Зазвичай для паралельних обчислень потрібні деякі координовані дії. Паралельні обчислення бувають декількох форм (на рівні інструкцій, бітів, даних, завдань). Паралельні обчислення знаходили своє застосування протягом багатьох років в основному в високопродуктивних обчисленнях. Але ситуація останнім часом змінилася. З'явився попит на такі обчислення через фізичних обмежень зростання тактової частоти процесора. Паралельні обчислення стали домінуючою ідеєю в архітектурі комп'ютера. Вона придбала форму багатоядерних процесорів.
- Використання паралельних обчислювальних систем обумовлено стратегічними напрямами розвитку в комп'ютерній індустрії. Головною обставиною стало не тільки обмеження можливостей швидкодії машин, заснованих на послідовній логіці, як і наявністю завдань, для яких наявність обчислювальної техніки не є ще достатнім. До завдань даної категорії можна віднести моделювання динамічних процесів.
- Поява процесорів з декількома ядрами стало стрибком розвитку ефективних суперобчислень, які можуть похвалитися вищими показниками продуктивність / вартість, в порівнянні з системами на базі супер ЕОМ. Використання багатоядерних процесорів дає гнучку можливість, зокрема варіювання конфігурацій, а також масштабування потужності в обчислювальних системах - починаючи від PC, серверів, робочих станцій і закінчуючи кластерними системами.
- 1. Актуальність теми
- В останні роки з'явилася велика кількість дешевих кластерних паралельних обчислювальних систем, які привели до швидкого розвитку паралельних обчислювальних технологій, в тому числі і в області високопродуктивних обчислень. Більшість основних виробників мікропроцесорів стали переходити на багатоядерні архітектури, що вплинуло на зміну ситуації в області паралельних обчислювальних технологій. Зміна апаратної бази тягне за собою зміну побудов паралельних алгоритмів. Для реалізації в багатоядерних архітектур обчислювальних потрібні нові паралельні алгоритми, що враховують нові технології. Ефективність використання обчислювальних ресурсів буде залежати від якості власне паралельних додатків і спеціалізованих бібліотек, орієнтованих на багатоядерні архітектури.
- Застосування високопродуктивної техніки в моделюванні реальних технічних, економічних, та інших процесів, що описуються системами звичайних диференціальних рівнянь великої розмірності, не тільки виправдано, але й необхідно. Розпаралелювання обчислень в багатопроцесорних і паралельних структурах є ефективним способів підвищення продуктивності. Так що, застосування паралельних обчислювальних систем досить важливий напрям розвитку обчислювальної техніки.
2. Збільшення кількості ядер
Першим процесором для масового використання був POWER4 з двома ядрами PowerPC на одному кристалі. Випущений компанією IBM в 2001 році.
Виробники процесорів Intel, AMD, IBM, ARM визнали збільшення число ядер як один із пріоритетних напрямів збільшення продуктивності.
У 2011 році випустили в виробництво 8-ядерні процесори для домашніх PC, і 16-ядерні для серверних систем.
Є розробки процесорів з великою кількістю ядер (більше 20), які було застосовано в специфічних пристроях.
2-х ядерні процесори існували раніше, наприклад IBM PowerPC-970MP (G5Н). Але такі процесори застосовувалися у вузькому колі спеціалізованих завдань.
У квітні 2005 року AMD представила 2-ядерний процесор Opteron. архітектура AMD64. призначений для серверів. У травні 2005 року Intel представила процесор Pentium D. Архітектури x86-64. Став першим 2-х ядерним процесором для домашніх PC.
У березні 2010 року AMD представила 12-ядерні серійні серверні процесори Opteron 6100 (архітектура x86 / x86-64).
У серпні 2011 року AMD представила 16-ядерні серійні серверні процесори Opteron серії 6200. Процесор Interlagos в одному корпусі містить два 8-ядерних (4-модульних) чіпа і є сумісним з платформою AMD Opteron серії 6100 (Socket G34).
3. Технологія NVIDIA CUDA
Велика кількість паралельних обчислень пов'язано з тривимірними іграми. Паралельні векторні обчислення на універсальних пристроях з багатоядерними процесорами використовуються в 3D-графіці, досягаючи високої пікової продуктивності. Універсальним процесорам це не під силу. Максимальна швидкість досягається тільки в ряді зручних завдань, маючи деякі обмеження. Але все одно такі пристрої широко застосовуються в сферах, де спочатку не призначалися. Наприклад, процесор Cell, розробки альянсу Sony-Toshiba-IBM в ігровій приставці Sony PlayStation 3, або, сучасні відеокарти від компаній NVIDIA і AMD.
Ще кілька років тому почали з'являтися технології неграфічних розрахунків загального призначення GPGPU для 3D відеоприскорювачів. Сучасні відеочіпи мають сотні математичних виконавчих блоків, така міць може допомогти для значного прискорення безлічі обчислювально інтенсивних додатків. Нинішні покоління GPU мають гнучку архітектуру, яка разом з програмно-апаратними архітектурами і високорівневими мовами дає можливість робити їх набагато доступнішими.
Поява досить швидких і гнучких шейдерних програм зацікавило розробників створити GPGPU, які здатні виконувати сучасні відеочіпи. Розробники захотіли на GPU розраховувати не тільки зображення в ігрових і 3D додатках, але і застосовувати в інших областях паралельних обчислень. Для цього використовували API графічних бібліотек OpenGL і Direct3D. Дані в відеочіп передавалися в якості текстур, розрахункові програми містилися у вигляді шейдеров. Головним недоліком такого способу є значна складність програмування, низький обмін даними між GPU і CPU, і деякі інші обмеження.
Провідні виробники відеочіпів NVIDIA і AMD представили платформи для паралельних обчислень - CUDA і CTM, відповідно. У відкритих з'явилася апаратна підтримка прямого доступу до обчислювальних ресурсів. CUDA є розширенням мови програмування С. CTM більш схожий на віртуальну машину, Яка виконує тільки асемблерний код. Обидві платформи прибрали ограніченіz попередніх версій GPGPU, які використовували традиційний графічний конвеєр, ну і звичайно графічні бібліотеки Direct3D і Open GL.
OpenGL є більш портіруемость, а також універсальної через свою відкритість коду. Але вона не дозволять використовувати той же код на чіпах різних виробника. У таких методів багато недоліків, вони не зручні, і володіють малою гнучкістю. А також вони не дозволяють використовувати специфічні можливості деяких відеокарт, наприклад, швидка спільна пам'ять.
Саме це збагнув компанію NVIDIA випустити платформу CUDA - C-подібна мова програмування, наділений своїм компілятором, а також має в наборі бібліотеками для обчислень на GPU. Написання хорошого коду для відеочіпів дуже не проста заняття, але CUDA дає більше контролю над апаратними засобами відеокарти. CUDA з'явилася з відеокарт серії 8. З'явилася CUDA версії 2.0, яка підтримує розрахунки з подвійною точність в 32 і 64 бітних ОС Windows, Linux, MacOS X.
4. Різниця між CPU і GPU
Зростання тактової частоти закінчилося через високого енергоспоживання. Збільшення продуктивності відбувається за рахунок збільшення кількості ядер на одному чипі. На даний момент для домашніх користувачів продаються процесори до восьми ядер, і кількістю потоків до 16. У таких процесорах кожне ядро \u200b\u200bпрацює окремо.
Спеціальні векторні можливості (інструкції SSE) для 4-х компонентних (одинарна точність з плаваючою точкою) і 2-х компонентних (подвійна точність) векторів з'явилися в універсальних процесорах через виникнення високих вимог додатків, що працюють з графікою. Тому застосування GPU є більш вигідним, тому що вони заточені спочатку під такі завдання.
У чіпах NVIDIA основний блок - це мультипроцессор з 8-10 ядрами і близько сотнею ALU з декількома тисячами регістрів і великою загальною пам'яттю. Відеокарта має глобальну пам'ять з доступом з усіх мультипроцессоров, локальна пам'ять в кожному мультипроцесорі, а також є пам'ять для констант.
В GPU ядра є SIMD (одиночний потік команд, безліч потоків даних) ядрами. Ці ядра виконують одні і ті ж інструкції одночасно. Це і є стиль програмування графічних алгоритмів. Він специфічний, але дозволяє збільшити кількість обчислювальних блоків за рахунок своєї простоти.
Основні відмінності між архітектурою (GPU і CPU): ядра CPU виконують один потік послідовних інструкцій з максимальною продуктивністю, GPU виконує велике число паралельно виконуваних потоків інструкцій. Універсальні процесори націлені на досягнення високої продуктивності одного потоку команд, що обробляють числа з плаваючою точкою і без. Доступ до пам'яті випадковий.
Політика розробників CPU: домогтися виконання більшого числа інструкцій паралельно, для збільшення продуктивності. Тому, починаючи з процесорів Intel Pentium, з'явилася технологія суперскалярного виконання, яка представляє собою виконання 2-х інструкцій за такт, а процесор Pentium Pro відзначився позачергових виконанням інструкцій.
У відеочіпів робота простіша і распараллелена спочатку. Чіп приймає групу полігонів, всі необхідні операції, і видає пікселі. Обробка полігонів і пікселів незалежна незалежно один від одного. Тому в GPU таке велике у процесорів. Також сучасні GPU здатні виконати більше однієї інструкції за такт.
Інша відмінність CPU від GPU: принцип доступу до пам'яті. В GPU Він зв'язний і передбачувані, тому що якщо вважалися текстури, значить через деякий час настане черга сусідніх текстур. Тому організація пам'яті у відеокарти і центрального процесора різні. І відеочіпі з цієї причини не треба кеш-пам'ять великого розміру, А для текстур потрібні лише близько 128-256 кБ.
Робота з пам'яттю також різна. CPU мають вбудовані контролери пам'яті, у GPU зазвичай їх по кілька, аж до восьми 64-біт каналів. Крім того застосовується дуже швидка пам'ять, отже, пропускна здатність пам'яті вище, що є плюсом для паралельних розрахунків, які оперують з величезними потоками даних.
В CPU велику кількість транзисторів йде на буфери команд, апаратне передбачення розгалуження, величезні обсяги кеш-пам'яті. Всі ці блоки потрібні для прискорення нечисленних потоків команд. В GPU транзистори йдуть на масиви виконавчих блоків, що розділяється пам'ять малого обсягу, керуючі потоками блоки, контролери пам'яті. Все це не прискорює виконання окремих потоків, але дозволяє обробляти їх у величезній кількості одночасно.
Кешування. CPU використовує кеш для зменшення затримок доступу до пам'яті, наслідок чого, відбувається збільшення продуктивності. GPU використовує кеш для збільшення пропускної здатності. CPU знижує затримки доступу до пам'яті за рахунок великого кеша і пророкування розгалужень коду. Ці апаратні частини є великими ні чипі, отже, вони споживають багато енергії. GPU вирішують проблему затримки доступу до пам'яті в інший спосіб: виконання тисяч потоків одночасно. Коли один потік чекає дані, інший потік виконує обчислення без очікування і затримок.
Загалом можна зробити наступний висновок: відеочіпи призначені для паралельних обчислень з великим об'ємом даних і великим кількість арифметичних операцій.
5. Перше застосування розрахунків на графічних прискорювачах
Історія застосування чіпів для математичних розрахунків почалося давно. Найперші спроби були примітивними і використовували деякі функції з Z-буферизації і растеризації. Але з появою шейдеров почалося прискорення. У 2003р. на SIGGRAPH з'явилася нова секція під обчислення, і вона отримала GPGPU.
BrookGPU. Відомий компілятор мови програмування Brook. Є потоковим. Був спеціально розроблений для обчислень на GPU. Розробники використовували API: Direct3D або OpenGL. Це істотною обмежувало застосування GPU, тому що шейдери і текстури застосовувалися в 3D графіку, а фахівці з паралельного програмування нічого знати не зобов'язані. Вони використовують струму потоки і ядра. Brook зміг трохи допомогти в цій задачі. Розширення до мови С допомогли приховати від програмістів тривимірний API, і надати відеочіп як паралельного співпроцесора. Компілятор компілював код і прив'язував до бібліотеки DirectX, OpenGL або x86.
6. Області застосування паралельних розрахунків на графічних прискорювачах
Наведемо усереднені цифри приросту продуктивності обчислень, отримані дослідниками по всьому світу. При переході на GPU приріст продуктивності становить в середньому в 5-30 разів, а в деяких прикладах доходить і до 100 разів (як правило це код, який непридатний для розрахунків за допомогою SEE.
Ось деякі приклади прискорень:
· Флуоресцентна мікроскопія - в 12 разів;
· Молекулярна динаміка - у 8-16 разів;
· Електростатика (пряме і багаторівневе підсумовування Кулона) - в 40-120 разів і 7 разів.
ядро процесор графічний
висновок
У рефераті вдалося розглянути паралельні обчислення на багатоядерних процесорах, а також технології CUDA і CTM. Були розглянуті різниця між CPU і GPU, які були складності застосування відеокарт в паралельних обчисленнях без технології CUDA, розглянуті області застосування.
У рефераті не було розглянуло застосування паралельних обчислень в центральних процесорах з інтегрованим відеоядром. Це процесори фірми AMD серії А (AMD A10, AMD A8, AMD A6, AMD A4) і процесори фірми Intel серії i3 / i5 / i7 з вбудованим відеоядром HD Graphics.
Список використаної літератури
1. Сайт ixbt.com, власник Byrds Research and Publishing, Ltd
2. Сайт wikipedia.org, власник Фонд Вікімедіа
3. Сайт nvidia.ru, власник NVIDIA corporation
Розміщено на Allbest.ru
...подібні документи
Пакетний метод як основний засіб для досягнення комунікаційних операцій, його зміст і вимоги, що пред'являються. Оцінка трудомісткості операції передачі даних між двома вузлами кластера. Етапи розробки паралельних алгоритмів (розпаралелювання).
презентація, доданий 10.02.2014
Знайомство з історією розвитку багатопроцесорних комплексів і паралельних обчислень. Персональні комп'ютери як поширені однопроцесорні системи на платформі Intel або AMD, що працюють під управлінням одного користувача операційних систем.
презентація, доданий 22.02.2016
Класифікація паралельних обчислювальних систем. Істотні поняття і компоненти паралельних комп'ютерів, їх компоненти. Особливості класифікацій Хендер, Хокні, Флінна, Шора. Системи з розділяється і локальною пам'яттю. Способи поділу пам'яті.
курсова робота, доданий 18.07.2012
Математична основа паралельних обчислень. Властивості Parallel Computing Toolbox. Розробка паралельних додатків в Matlab. Приклади програмування паралельних завдань. Обчислення визначеного інтеграла. Послідовне і паралельне множення.
курсова робота, доданий 15.12.2010
Розвиток концепцій і можливостей ОС. Паралельні комп'ютерні системи та особливості їх ОС. Симетричні і асиметричні мультипроцесорні системи. Види серверів в клієнт-серверних системах. ОС для хмарних обчислень. Кластерні обчислювальні системи.
лекція, доданий 24.01.2014
Технологія розробки паралельних програм для багатопроцесорних обчислювальних систем зі спільною пам'яттю. Синтаксис, семантика і структура моделі OpenMP: директиви, процедури і змінні оточення. Розпаралелювання за даними і операціями, синхронізація.
презентація, доданий 10.02.2014
Паралельні обчислювальні системи, їх загальна характеристика та функціональні особливості, оцінка можливостей, внутрішня структура і взаємозв'язок елементів, типи: одно- і багатопроцесорні. Паралельна форма алгоритму, його уявлення і реалізація.
контрольна робота, доданий 02.06.2014
Переваги багатопроцесорних систем. Створення програми, що реалізує роботу мультипроцессорной системи із загальною пам'яттю по обробці різної кількості заявок, а також різної кількості процесорів. Моделі обчислень на векторних і матричних ЕОМ.
курсова робота, доданий 21.06.2013
Абстрактні моделі і способи паралельної обробки даних, допустима похибка обчислень. Поняття паралельного процесу, їх синхронізація і гранули розпаралелювання, визначення закону Амдаля. Архітектура багатопроцесорних обчислювальних систем.
дипломна робота, доданий 09.09.2010
Однопроцесорні обчислювальні системи не справляються з рішенням військово-прикладних задач в реальному часі, тому для підвищення продуктивності обчислювальних систем військового призначення використовуються багатопроцесорні обчислювальні системи (МВС).
транскрипт
1 Частина 3. Методи паралельних обчислень 6. Принципи розробки паралельних методів 6. Принципи розробки паралельних методів Моделювання паралельних програм Етапи розробки паралельних алгоритмів Поділ обчислень на незалежні частини Виділення інформаційних залежностей Масштабування набору підзадач Розподіл подзадач між процесорами Паралельне рішення гравітаційної задачі N тіл Поділ обчислень на незалежні частини Виділення інформаційних залежностей Масштабування і розподіл подзадач по процесорам Аналіз ефективності паралельних обчислень Короткий огляд розділу огляд літератури Контрольні питання Завдання і вправи Розробка алгоритмів (а особливо методів паралельних обчислень) для вирішення складних науково-технічних завдань часто є значною проблему. Для зниження складності даної теми залишимо осторонь математичні аспекти розробки та докази збіжності алгоритмів ці питання в тій чи іншій мірі вивчаються в ряді "класичних" математичних навчальних курсів. Тут же ми будемо вважати, що обчислювальні схеми вирішення завдань, що розглядаються далі в якості прикладів, вже відомі 1). З урахуванням висловлених припущень наступні дії для визначення ефективних способів організації паралельних обчислень можуть полягати в наступному: Виконати аналіз наявних обчислювальних схем і здійснити їх поділ (декомпозицію) на частини (підзадачі), які можуть бути реалізовані в значній мірі незалежно один від одного, Виділити для сформованого набору підзадач інформаційні взаємодії, які повинні здійснюватися в ході розв'язання вихідної поставленого завдання, Визначити необхідну (або доступну) для вирішення завдання обчислювальну систему і виконати розподіл має набору підзадач між процесорами системи. При найзагальнішому розгляді зрозуміло, що обсяг обчислень для кожного використовуваного процесора повинен бути приблизно однаковий це дозволить забезпечити рівномірну обчислювальну завантаження (балансування) процесорів. Крім того, також зрозуміло, що розподіл подзадач між процесорами має бути виконано таким чином, щоб наявність інформаційних зв'язків (комунікаційних взаємодій) між подзадачами було мінімальним. 1) Не дивлячись на те, що для багатьох науково-технічних завдань насправді відомі не тільки послідовні, але і паралельні методи розв'язання, дане припущення є, звичайно, дуже сильним, оскільки для нових виникаючих завдань, що вимагають для свого рішення великого обсягу обчислень, процес розробки алгоритмів становить істотну частину всіх виконуваних робіт.
2 Поділ обчислень на незалежні частини Виділення інформаційних залежностей Масштабування подзадач Розподіл подзадач між процесорами Рис Загальна схема розробки паралельних алгоритмів Після виконання всіх перерахованих етапів проектування можна оцінити ефективність розроблюваних паралельних методів для цього зазвичай визначаються значення показників якості породжуються паралельних обчислень (прискорення, ефективність, масштабованість) . За результатами проведеного аналізу може виявитися необхідним повторення окремих (в граничному випадку всіх) етапів розробки слід зазначити, що повернення до попередніх кроків розробки може відбуватися на будь-якій стадії проектування паралельних обчислювальних схем. В цьому відношенні часто виконуваних додатковим дією в поступовим зниженням дози проектування є коригування складу сформованого безлічі завдань після визначення наявної кількості процесорів підзадачі можу бути укрупнені (агреговані) при наявності малого числа процесорів або, навпаки, деталізовані в іншому випадку. В цілому, дані дії можуть бути визначені як масштабування розробляється алгоритму і виділені в якості окремого етапу проектування паралельних обчислень. Для застосування одержуваного в кінцевому підсумку паралельного методу необхідно виконати розробку програм для вирішення сформованого набору підзадач і розмістити розроблені програми по процесорах відповідно до обраної схеми розподілу підзадач. Для проведення обчислень програми запускаються на виконання (програми на стадії виконання зазвичай іменуються процесами), для реалізації інформаційних взаємодій програми повинні мати в своєму розпорядженні засоби обміну даними (канали передачі повідомлень). Слід зазначити, що кожен процесор зазвичай виділяється для вирішення однієї єдиної підзадачі, однак при наявності великої кількості підзадач або використанні обмеженого числа процесорів це правило може не дотримуватися і, в результаті, на процесорах може виконуватися одночасно кілька програм (процесів). Зокрема, при розробці та початкової перевірці паралельної програми для виконання всіх процесів може використовуватися один процесор (при розташуванні на одному процесорі процеси виконуються в режимі розподілу часу). Розглянувши уважно розроблену схему проектування і реалізації паралельних обчислень, можна відзначити, що даний підхід в значній мірі орієнтований на обчислювальні системи з розподіленою пам'яттю, коли необхідні інформаційні взаємодії реалізуються за допомогою передачі повідомлень по каналах зв'язку між процесорами. Проте, дана схема може бути використана без втрати будь-якої ефективності паралельних обчислень і для розробки паралельних методів для систем зі спільною пам'яттю в цьому випадку механізми передачі повідомлень для забезпечення інформаційних взаємодій повинні бути замінені операціями доступу до загальних (розділяються) змінним Моделювання паралельних програм Розглянута схема проектування та реалізації паралельних обчислень дає спосіб розуміння паралельних алгоритмів і програм. На стадії проектування паралельний метод може бути представлений у вигляді графа "підзадачі повідомлення", який являє собою не що інше, як укрупненное (агреговане) уявлення графа інформаційних залежностей (графа "операції-операнди" см. Розділ 2). Аналогічно на стадії виконання для опису паралельної програми може бути використана модель у вигляді графа "процеси канали", в якій замість подзадач використовується поняття процесів, а інформаційні залежності замінюються каналами 2
3 передачі повідомлень. На додаток, на цій моделі може бути показано розподіл процесів по процесорам обчислювальної системи, якщо кількість підзадач перевищує число процесорів см. Рис процес - канал - операції прийому (передачі) - вхідні (вихідні) канали для взаємодії процесів Рис Модель паралельної програми у вигляді графа "процеси-канали" Використання двох моделей паралельних обчислень 2) дозволяє краще розділити проблеми, які проявляються при розробці паралельних методів. Перша модель граф "підзадачі - повідомлення" дозволяє зосередитися на питаннях виділення підзадач однаковою обчислювальної складності, забезпечуючи при цьому низький рівень інформаційної залежності між подзадачами. Друга модель граф "процеси канали" концентрує увагу на питаннях розподілу підзадач по процесорам, забезпечуючи ще одну можливість зниження трудомісткості інформаційних взаємодій між подзадачами за рахунок розміщення на одних і тих же процесорах інтенсивно взаємодіючих процесів. Крім того, ця модель дозволяє краще аналізувати ефективність розробленого паралельного методу і забезпечує можливість більш адекватного опису процесу виконання паралельних обчислень. Дамо додаткові пояснення для використовуваних понять в моделі "процеси-канали": Під процесом в рамках даного навчального матеріалу будемо розуміти виконувану на процесорі програму, яка використовує для своєї роботи частина локальної пам'яті процесора і яка містить ряд операцій прийому / передачі даних для організації інформаційної взаємодії між виконуваними процесами паралельної програми, Канал передачі даних з логічної точки зору може розглядатися як черга повідомлень, в яку один або кілька процесів можуть відправляти пересилаються дані і з якої процес-адресат може витягувати повідомлення, що відправляються іншими процесами. У загальному випадку, можна вважати, що канали виникають динамічно в момент виконання першої операції прийому / передачі з каналом. За ступенем спільності, канал може відповідати одній або декільком командам прийому даних процесу-одержувача; аналогічно при передачі повідомлень канал може використовуватися однією або декількома командами передачі даних одного або декількох процесів. Для зниження складності моделювання та аналізу паралельних методів будемо припускати, що ємність каналів є необмеженою і, як результат, операції передачі даних виконуються практично без затримок простим копіюванням повідомлень в канал. З іншого боку, операції прийому повідомлень можуть призводити до затримок (блокувань), якщо запитувані з каналу дані ще не були відправлені процесами-джерелами повідомлень. Слід відзначити важливу гідність розглянутої моделі "процеси-канали" в цій моделі проводиться чіткий поділ локальних (виконуваних на окремому процесорі) обчислень і 2) У Foster (1995) розглядається тільки одна модель модель "завдання-канал" для опису паралельних обчислень, яка займає деяке проміжне положення в порівнянні з викладеними тут моделями. Так, в моделі "задачаканал" не враховується можливість використання одного процесора для вирішення декількох підзадач одночасно. 3
4 дій по організації інформаційної взаємодії одночасно виконуваних процесів. Такий підхід значно знижує складність аналізу ефективності паралельних методів і істотно спрощує проблеми розробки паралельних програм Етапи розробки паралельних алгоритмів Розглянемо більш докладно викладену вище методику розробки паралельних алгоритмів. Значною мірою ця методика спирається на підхід, вперше розглянутий в Foster (1995), і, як зазначалося раніше, включає етапи виділення підзадач, визначення інформаційних залежностей, масштабування і розподілу підзадач по процесорам обчислювальної системи (див. Рис. 6.1). Для демонстрації приводяться рекомендацій далі буде використовуватися навчальне завдання пошуку максимального значення серед елементів матриці A (таке завдання виникає, наприклад, при чисельному рішенні систем лінійних рівнянь для визначення провідного елементу методу Гаусса): y \u003d max a. 1 i, j N i j Таке завдання носить повністю ілюстративний характер, і після розгляду етапів розробки в решти розділу буде наведено більш повний приклад використання даної методики для розробки паралельних алгоритмів. Крім того, дана схема розробки буде застосована і при викладі всіх далі розглянутих методів паралельних обчислень Поділ обчислень на незалежні частини Вибір способу поділу обчислень на незалежні частини грунтується на аналізі обчислювальної схеми рішення вихідної задачі. Вимоги, яким повинен задовольняти обираний підхід, зазвичай складаються в забезпеченні рівного об'єму обчислень в виділяються підзадачі і мінімуму інформаційних залежностей між цими подзадачами (при інших рівних умовах потрібно віддавати перевагу рідкісним операціями передачі більшого розміру повідомлень в порівнянні з частими пересилками даних невеликого обсягу). У загальному випадку, проведення аналізу та виділення завдань являє собою досить складну проблему ситуацію допомагає вирішити існування двох найпоширеніших типів обчислювальних схем: а) б) Рис Поділ даних для матриці A: а) стрічкова схема, б) блокова схема Для великого класу задач обчислення зводяться до виконання однотипної обробки елемент елементів великого набору даних до такого виду завдань відносяться, наприклад, матричні обчислення, чисельні методи рішення рівнянь в приватних похідних і ін. в цьому випадку говорять, що існує паралелізм за даними, і виділення підзадач зводиться до поділу наявних даних . Так, наприклад, для нашої навчальної завдання пошуку максимального значення при формуванні подзадач вихідна матриця A може бути розділена на окремі рядки (або послідовні групи рядків) стрічкова схема поділу даних (див. Рис. 6.3) або на прямокутні набори елементів блокова схема поділу даних. Для великої кількості вирішуваних завдань поділ обчислень за даними призводить до породження одно-, дво- і три- вимірних наборів подзадач, для яких інформаційні зв'язки існують тільки між найближчими сусідами (такі схеми зазвичай іменуються сітками або гратами), 4
5 Рис Регулярні одно-, дво- і тривимірні структури базових подзадач після декомпозиції даних Для іншої частини завдань обчислення можуть складатися у виконанні різних операцій над одним і тим же набором даних в цьому випадку говорять про існування функціонального паралелізму (як приклади можна привести завдання обробки послідовності запитів до інформаційних баз даних, обчислення з одночасним застосуванням різних алгоритмів розрахунку і т.п.). Дуже часто функціональна декомпозиція може бути використана для організації конвеєрної обробки даних (так, наприклад, при виконанні будь-яких перетворень даних обчислення можуть бути зведені до функціональної послідовності введення, обробки і збереження даних). Важливе питання при виділенні подзадач полягає у виборі потрібного рівня декомпозиції обчислень. Формування максимально можливої \u200b\u200bкількості подзадач забезпечує використання гранично досяжного рівня паралелізму розв'язуваної задачі, проте ускладнює аналіз паралельних обчислень. Використання при декомпозиції обчислень тільки досить "великих" подзадач призводить до ясної схемою паралельних обчислень, однак може ускладнити ефективне використання чималої кількості процесорів. Можливе розумне поєднання цих двох підходів може полягати в використанні в якості конструктивних елементів декомпозиції тільки тих подзадач, для яких методи паралельних обчислень є відомими. Так, наприклад, при аналізі завдання матричного множення як подзадач можна використовувати методи скалярного твори векторів або алгоритми матрично-векторного твори. Подібний проміжний спосіб декомпозиції обчислень дозволить забезпечити і простоту подання обчислювальних схем, і ефективність паралельних розрахунків. Можливі підзадачі при такому підході будемо називати далі базовими, які можуть бути елементарними (неподільними), якщо не допускають подальшого поділу, або складовими в іншому випадку. Для даної навчальної задачі достатній рівень декомпозиції може складатися, наприклад, в поділі матриці A на безліч окремих рядків і отриманні на цій основі набору підзадач пошуку максимальних значень в окремих рядках; породжувана при цьому структура інформаційних зв'язків відповідає лінійному графу см. рис Для оцінки коректності етапу поділу обчислень на незалежні частини можна скористатися контрольним списком питань, запропонованих в Foster (1995): Виконана декомпозиція не збільшує обсяг обчислень і необхідний обсяг пам'яті? Чи можлива при обраному способі декомпозиції рівномірне завантаження всіх наявних процесорів? Чи достатньо виділених частин процесу обчислень для ефективного завантаження наявних процесорів (з урахуванням можливості збільшення їх кількості)? Виділення інформаційних залежностей При наявності обчислювальної схеми виконання завдання після виділення базових подзадач визначення інформаційних залежностей між подзадачами зазвичай не викликає великих труднощів. При цьому, однак, слід зазначити, що насправді етапи виділення підзадач і інформаційних залежностей досить складно піддаються поділу. Виділення подзадач має відбуватися з урахуванням виникаючих інформаційних зв'язків; після аналізу обсягу і частоти необхідних інформаційних обмінів між подзадачами може знадобитися повторення етапу поділу обчислень. При проведенні аналізу інформаційних залежностей між подзадачами слід розрізняти (кращі форми інформаційної взаємодії виділені підкресленням): Локальні і глобальні схеми передачі даних для локальних схем передачі даних в кожен момент часу виконуються тільки між невеликим числом подзадач (наявних, як 5
6 правило, на сусідніх процесорах), для глобальних операцій передачі даних в процесі комунікації беруть участь всі підзадачі, Структурні і довільні способи взаємодії для структурних способів організація взаємодій призводить до формування деяких стандартних схем комунікації (наприклад, у вигляді кільця, прямокутної решітки і т. д.), для довільних структур взаємодії схема виконуваних операцій передач даних не носить характер однорідності, Статичні або динамічні схеми передачі даних для статичних схем моменти і учасники інформаційної взаємодії фіксуються на етапах проектування і розробки паралельних програм, для динамічного варіанта взаємодії структура операції передачі даних визначається в ході виконуваних обчислень, Синхронні і асинхронні способи взаємодії для синхронних способів операції передачі даних виконуються тільки при готовності всіх учасників взаємодії і завершуються тільки після повного закінчення все х комунікаційних дій, при асинхронному виконанні операцій учасники взаємодії можуть не чекати повного завершення дій з передачі даних. Для представлених способів взаємодії досить складно виділити кращі форми організації передачі даних: синхронний варіант, як правило, більш простий для використання, в той час як асинхронний спосіб часто дозволяє істотно знизити часові затримки, викликані операціями інформаційної взаємодії. Як уже зазначалося в попередньому пункті, для навчальної завдання пошуку максимального значення при використанні в якості базових елементів подзадач пошуку максимальних значень в окремих рядках вихідної матриці A структура інформаційних зв'язків має вигляд, представлений на рис Рис Структура інформаційних зв'язків навчального завдання як і раніше, для оцінки правильності етапу виділення інформаційних залежностей можна скористатися контрольним списком питань, запропонованих в Foster (1995): чи відповідає обчислювальна складність подзадач інтенсивності їх інформаційних взаємодій? Чи є однаковою інтенсивність інформаційних взаємодій для різних підзадач? Чи є схема інформаційної взаємодії локальної? Чи не перешкоджає чи виявлена \u200b\u200bінформаційна залежність паралельного вирішення підзадач? Масштабування набору підзадач масштабування розробленої обчислювальної схеми паралельних обчислень проводиться в разі, якщо кількість наявних подзадач відрізняється від числа плануються до використання процесорів. Для скорочення кількості підзадач необхідно виконати укрупнення (агрегації) обчислень. Застосовувані тут правила збігаються з рекомендаціями початкового етапу виділення підзадач визначаються підзадачі, як і раніше, повинні мати однакову обчислювальну складність, а обсяг і інтенсивність інформаційних взаємодій між подзадачами повинні залишатися на мінімально-можливий рівень. Як результат, першими претендентами на об'єднання є підзадачі з високим ступенем інформаційної взаємозалежності. При недостатній кількості наявного набору підзадач для завантаження всіх доступних до використання процесорів необхідно виконати деталізацію (декомпозицію) обчислень. як 6
7 правило, проведення подібної декомпозиції не викликає будь-яких ускладнень, якщо для базових завдань методи паралельних обчислень є відомими. Виконання етапу масштабування обчислень має звестися, в кінцевому підсумку, до розробки правил агрегації і декомпозиції подзадач, які повинні параметрически залежати від числа процесорів, які застосовуються для обчислень. Для даної навчальної задачі пошуку максимального значення агрегація обчислень може складатися в об'єднанні окремих рядків в групи (стрічкова схема поділу матриці см. Рис. 6.3а), при декомпозиції подзадач рядки вихідної матриці A можуть розбиватися на кілька частин (блоків). Список контрольних питань, запропонований в Foster (1995) для оцінки правильності етапу масштабування, виглядає наступним чином: Чи не погіршиться локальність обчислень після масштабування наявного набору підзадач? Чи мають підзадачі після масштабування однакову обчислювальну і комунікаційну складність? Чи відповідає кількість завдань числу наявних процесорів? Залежать параметрически правила масштабування від кількості процесорів? Розподіл подзадач між процесорами Розподіл подзадач між процесорами є завершальним етапом розробки паралельного методу. Треба відзначити, що управління розподілом навантаження для процесорів можливо тільки для обчислювальних систем з розподіленою пам'яттю, для мультипроцессоров (систем зі спільною пам'яттю) розподіл навантаження зазвичай виконується операційною системою автоматично. Крім того, даний етап розподілу підзадач між процесорами є надлишковим, якщо кількість підзадач збігається з числом наявних процесорів, а топологія мережі передачі даних обчислювальної системи є повний граф (тобто, всі процесори пов'язані між собою прямими лініями зв'язку). Основний показник успішності виконання даного етапу ефективність використання процесорів, що визначається як відносна частка часу, протягом якого процесори використовувалися для обчислень, пов'язаних з рішенням вихідної задачі. Шляхи досягнення хороших результатів у цьому напрямку залишаються колишніми як і раніше, необхідно забезпечити рівномірний розподіл обчислювального навантаження між процесорами і мінімізувати кількість повідомлень, переданих між процесорами. Точно так же, як і на попередніх етапах проектування, оптимальне рішення проблеми розподілу підзадач між процесорами грунтується на аналізі інформаційної зв'язності графа "підзадачі - повідомлення". Так, зокрема, підзадачі, між якими є інформаційні взаємодії, доцільно розміщувати на процесорах, між якими існують прямі лінії передачі даних. Слід зазначити, що вимога мінімізації інформаційних обмінів між процесорами може суперечити умові рівномірного завантаження процесів. Так, ми можемо розмістити всі підзадачі на одному процесорі і повністю усунути межпроцессорную передачу повідомлень, проте, зрозуміло, завантаження більшості процесорів в цьому випадку буде мінімальною. Для нашої навчальної завдання пошуку максимального значення розподіл подзадач між процесорами не викликає будь-яких ускладнень достатньо лише забезпечити розміщення подзадач, між якими є інформаційні зв'язку, на процесорах, для яких існують прямі канали передачі даних. Оскільки структура інформаційної зв'язків навчального завдання має вигляд лінійного графа, виконання цієї вимоги може бути забезпечено практично при будь-якої топології мережі обчислювальної системи. Вирішення питань балансування обчислювального навантаження значно ускладнюється, якщо схема обчислень може змінюватися в ході виконання завдання. Причиною цього можуть бути, наприклад, неоднорідні сітки при вирішенні рівнянь в приватних похідних, розрідженість матриць і т.п. 3). Крім того, використовувані на етапах проектування оцінки обчислювальної складності рішення підзадач можуть мати наближений характер і, нарешті, кількість підзадач може змінюватися в ході обчислень. У таких ситуаціях може знадобитися перерозподіл базових подзадач між 3) Можна відзначити, що навіть для нашої простий навчального завдання може спостерігатися різна обчислювальна складність сформованих базових задач. Так, наприклад, кількість операцій при пошуку максимального значення для рядка, в якій максимальне значення має перший елемент, і рядки, в якій значення є впорядкованими за зростанням, буде відрізнятися в два рази. 7
8 процесорами вже безпосередньо в процесі виконання паралельної програми (або, як зазвичай кажуть, доведеться виконати динамічне балансування обчислювального навантаження). Дані питання є одними з найбільш складних (і найбільш цікавих) в області паралельних обчислень на жаль, розгляд даних питань виходить за рамки даного навчального матеріалу (додаткова інформація може бути отримана, наприклад, в Buyya (1999) і Wilkinson and Allen (1999)) . Як приклад дамо коротку характеристику широко використовуваного способу динамічного управління розподілом обчислювального навантаження, зазвичай іменується схемою "менеджер - виконавець" (manager-worker scheme). При використанні даного підходу передбачається, що підзадачі можуть виникати і завершуватися в ході обчислень, при цьому інформаційні взаємодії між подзадачами або повністю відсутній, або є мінімальними. Відповідно до даної схемою для управління розподілом навантаження в системі виділяється окремий процесор-менеджер, якому доступна інформація про всі наявні підзадача. Решта процесори системи є виконавцями, які для отримання обчислювального навантаження звертаються до процесора-менеджеру. Породжувані в ході обчислень нові підзадачі передаються назад процесору-менеджеру і можуть бути отримані для вирішення при наступних зверненнях процесорів-виконавців. Завершення обчислень відбувається в момент, коли процессориісполнітелі завершили рішення всіх переданих їм подзадач, а процесор-менеджер не має яких-небудь обчислювальних робіт для виконання. Запропонований в Foster (1995) перелік контрольних питань для перевірки етапу розподілу підзадач полягає в наступному: Чи не призводить розподіл кількох завдань на один процесор до зростання додаткових обчислювальних витрат? Чи існує необхідність динамічного балансування обчислень? Чи не є процесор-менеджер "вузьким" місцем при використанні схеми "менеджерісполнітель"? 6.3. Паралельне рішення гравітаційної задачі N тіл Багато обчислювальні завдання в галузі фізики зводяться до операцій обробки даних для кожної пари об'єктів наявної фізичної системи. Такою задачею є, зокрема, проблема, широко відома в літературі як гравітаційна завдання N тіл (або просто завдання N тіл) см., Наприклад, Andrews (2000) У найзагальнішому вигляді, завдання може бути описана наступним чином. Нехай дано велику кількість тіл (планет, зірок і т.д.), для кожного з яких відома маса, початкове положення і швидкість. Під дією гравітації положення тіл змінюється, і необхідну рішення задачі полягає в моделюванні динаміки зміни системи N тіл протягом деякого задається інтервалу часу. Для проведення такого моделювання заданий інтервал часу зазвичай розбивається на тимчасові відрізки невеликої тривалості і далі на кожному кроці моделювання обчислюються сили, що діють на кожне тіло, а потім оновлюються швидкості і положення тіл. Очевидний алгоритм вирішення задачі N тіл полягає в розгляді на кожному кроці моделювання всіх пар об'єктів фізичної системи і виконанні для кожної одержуваної пари всіх необхідних розрахунків. Як результат, при такому підході час виконання однієї ітерації моделювання становитиме 4) T \u003d τ N (N 1) / 2, 1 де τ є час Перевичісленіе параметрів однієї пари тел. Як випливає з наведеного опису, обчислювальна схема розглянутого алгоритму є порівняно простий, що дозволяє використовувати завдання N тіл в якості ще однієї наочної демонстрації застосування методики розробки паралельних алгоритмів. 4) Слід зазначити, що для вирішення завдання N тіл існує і більш ефективні послідовні алгоритми, проте їх вивчення може зажадати чималих зусиль. З урахуванням даної обставини для подальшого розгляду вибирається саме цей "очевидний" (але не найшвидший) метод, хоча, в загальному випадку, безумовно, для розпаралелювання слід вибирати найкращі схеми виконання розрахунків. 8
9 Поділ обчислень на незалежні частини Вибір способу поділу обчислень не викликає будь-яких ускладнень - очевидний підхід полягає у виборі в якості базової підзадачі всього набору обчислень, пов'язаних з обробкою даних одного будь-якого тіла фізичної системи Виділення інформаційних залежностей Виконання обчислень, пов'язаних з кожної підзадачею, стає можливим тільки в разі, коли в підзадача є дані (положення і швидкості пересування) про всі тілах наявної фізичної системи. Як результат, перед початком кожної ітерації моделювання кожна подзадача повинна отримати всі необхідні відомості від усіх інших подзадач системи. Така процедура передачі даних, як зазначалося в розділі 3, іменується операцією збору даних (single-node gather). У розглянутому алгоритмі дана операція повинна бути виконана для кожної підзадачі такий варіант передачі даних зазвичай іменується як операція узагальненого збору даних (multi-node gather or all gather). Визначення вимог до необхідних результатів інформаційного обміну не призводить до однозначного встановлення потрібного інформаційного обміну між подзадачами досягнення необхідних результатів може бути забезпечено за допомогою різних алгоритмів виконання операції узагальненого збору даних. Найбільш простий спосіб виконання необхідного інформаційного обміну полягає в реалізації послідовності кроків, на кожному з яких всі наявні підзадачі розбиваються попарно і обмін даними здійснюється між подзадачами утворилися пар. При належній організації попарного поділу подзадач (N-1) -кратноє повторення описаних дій призведе до повної реалізації необхідної операції збору даних. Розглянутий вище метод організації інформаційного обміну є досить трудомістким для збору всіх необхідних даних потрібно (N-1) ітерацій, на кожній з яких виконується одночасно (N / 2) операцій передачі даних. Для скорочення необхідної кількості ітерацій можна звернути увагу на факт, що після виконання першого кроку операції збору даних підзадачі будуть вже містити не тільки свої дані, але і дані підзадач, з якими вони утворювали пари. Як результат, на другий ітерації збору даних можна буде утворювати пари подзадач для обміну даними відразу про двох тілах фізичної системи тим самим, після завершення другої ітерації кожна подзадача буде містити відомості про чотирьох тілах системи і т.д. Як можна помітити, даний спосіб реалізації обмінів дозволяє завершити необхідну процедуру за log 2 N ітерацій. Слід зазначити, що при цьому обсяг даних, що пересилаються в кожної операції обміну подвоюється від ітерації до ітерації на першій ітерації між подзадачами пересилаються дані про один тілі системи, на другий ітерації про двох тілах і т.д. Використання розглянутого способу реалізації операції узагальненого збору даних призводить до визначення структури інформаційних зв'язків між подзадачами у вигляді N-мірного гіперкуба Масштабування і розподіл подзадач по процесорам Як правило, число тел фізичної системи N значно перевищує кількість процесорів p. Як результат, розглянуті раніше підзадачі слід укрупнити, об'єднавши в рамках однієї підзадачі обчислення для групи (N / p) тел. Після проведення подібної агрегації число подзадач і кількість процесорів буде збігатися, і при розподілі подзадач між процесорами залишиться лише забезпечити наявність прямих комунікаційних ліній між процесорами з подзадачами, між якими є інформаційні обміни при виконанні операції збору даних Аналіз ефективності паралельних обчислень Оцінимо ефективність розроблених способів паралельних обчислень для вирішення завдання N тіл. Оскільки запропоновані варіанти відрізняються тільки методами виконання інформаційних обмінів, для порівняння підходів досить визначити тривалість операції узагальненого збору даних. Використовуємо для оцінки часу передачі повідомлень модель, запропоновану Хокні (див. Розділ 3), тоді тривалість виконання операції збору даних для першого варіанту паралельних обчислень може бути виражена як 1 T p (comm) \u003d (p 1) (α + m (N / p) / β), де α, β є параметри моделі Хокні (латентність і пропускна здатність мережі передачі даних), а m задає обсяг даних, що пересилаються для одного тіла фізичної системи. 9
10 Для другого способу інформаційного обміну, як уже зазначалося раніше, обсяг даних, що пересилаються на різних ітераціях операції збору даних різниться. На першій ітерації обсяг повідомлень, що пересилаються становить (mn / p), на другій ітерації цей обсяг збільшується вдвічі і виявляється рівним 2 (mN / p) і т.д. У загальному випадку, для ітерації з номером i обсяг повідомлень оцінюється як 2 i-1 (mn / p). Як результат, тривалість виконання операції збору даних в цьому випадку може бути визначена за допомогою наступного виразу T 2 p log pi \u003d 1 i 1 (comm) \u003d (α + 2 m (N / p) / β) \u003d α log p + m (N / p) (p 1) / β. Порівняння отриманих виразів показує, що другий розроблений спосіб паралельних обчислень має істотно більш високу ефективність, несе менші комунікаційні витрати та допускає кращу масштабованість при збільшенні кількості використовуваних процесорів Короткий огляд розділу У розділі була розглянута методика розробки паралельних алгоритмів, запропонована в Foster (1995). Дана методика включає етапи виділення підзадач, визначення інформаційних залежностей, масштабування і розподілу підзадач по процесорам обчислювальної системи. При застосуванні методики передбачається, що обчислювальна схема вирішення даної задачі вже є відомою. Основні вимоги, які повинні бути забезпечені при розробці паралельних алгоритмів, складаються в забезпеченні рівномірного завантаження процесорів при низькому інформаційну взаємодію сформованого безлічі підзадач. Для опису одержуваних в ході розробки обчислювальних паралельних схем розглянуті дві моделі. Перша з них модель "підзадачі-повідомлення" може бути використана на стадії проектування паралельних алгоритмів, друга модель "процеси-канали" може бути застосована на стадії реалізації методів у вигляді паралельних програм. На завершення розділу показується застосування розглянутої методики розробки паралельних алгоритмів на прикладі рішення гравітаційної задачі N тіл Огляд літератури Розглянута в розділі методика розробки паралельних алгоритмів вперше була запропонована в Foster (1995). У цій роботі виклад методики проводиться більш детально; крім того, в роботі міститься кілька прикладів використання методики для розробки паралельних методів для вирішення ряду обчислювальних задач. Корисною при розгляді питань проектування та розробки паралельних алгоритмів може виявитися також робота Quinn (2004). Гравітаційна завдання N тіл більш детально розглядається в Andrews (2000) Контрольні питання 1. У чому полягають вихідні припущення для можливості застосування розглянутої в розділі методики розробки паралельних алгоритмів? 2. Які основні етапи проектування та розробки методів паралельних обчислень? 3. Як визначається модель "підзадачі-повідомлення"? 4. Як визначається модель "процеси-канали"? 5. Які основні вимоги повинні бути забезпечені при розробці паралельних алгоритмів? 6. У чому полягають основні дії на етапі виділення підзадач? 7. Які основні дії на етапі визначення інформаційних залежностей? 8. У чому полягають основні дії на етапі масштабування наявного набору підзадач? 9. У чому полягають основні дії на етапі розподілу підзадач по процесорам обчислювальної системи? 10. Як відбувається динамічне управління розподілом обчислювального навантаження за допомогою схеми "менеджер - виконавець"? 11. Який метод паралельних обчислень був розроблений для вирішення гравітаційної задачі N тіл? 10
11 12. Який спосіб виконання операції узагальненого збору даних є більш ефективним? 6.7. Завдання і вправи 1. Виконайте реалізацію каскадної схеми обчислення суми послідовності числових значень (див. Розділ 2) і порівняйте час виконання виконаної реалізації та функції MPI_Bcast бібліотеки MPI. 2. Виконайте реалізацію розглянутих способів виконання узагальненої операції збору даних і порівняйте час їх виконання. Зіставте отримані тимчасові характеристики з мають теоретичними оцінками. Виконайте порівняння з часом виконання функції MPI_Allgather бібліотеки MPI. 3. Розробіть схему паралельних обчислень, використовуючи розглянуту в розділі методику проектування і розробки паралельних методів: для завдання пошуку максимального значення серед мінімальних елементів рядків матриці (таке завдання має місце для вирішення матричних ігор) y \u003d max min a, 1 i N 1 j N ij (зверніть особливу увагу на ситуацію, коли число процесорів перевищує порядок матриці, тобто p\u003e n), для завдання обчислення певного інтеграла з використанням методу прямокутників b N 1 y \u003d f (x) dx h fi, ai \u003d 0 fi \u003d f (x), x \u003d ih, h \u003d (ba) / N. ii (опис методів інтегрування дано, наприклад, в Kahaner, Moler and Nash (1988)) 4. Виконайте реалізацію розроблених паралельних методів для задач п Розробіть схему паралельних обчислень для завдання множення матриці на вектор, використовуючи розглянуту в розділі методику проектування і розробки паралельних методів. Література Andrews, G. R. (2000). Foundations of Multithreaded, Parallel, and Distributed Programming .. Reading, MA: Addison-Wesley (російський переклад Ендрюс Г.Р. Основи многопоточного, паралельного і розподіленого програмування. М .: Видавничий дім "Вільямс", 2003) Bertsekas, DP, Tsitsiklis , JN (1989) Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Ed.) (1999). High Performance Cluster Computing. Volume1: Architectures and Systems. Volume 2: Programming and Applications. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Numerical Methods and Software. Prentice Hall (російський переклад Каханер Д., Моулер Л., Неш С. Чисельні методи та програмне забезпечення. М .: Мир, 2001) Foster, I. (1995). Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. New York, NY: McGraw-Hill. Wilkinson, B., Allen, M. (1999). Parallel programming. Prenrice Hall. 11
ГЛАВА 3 ПРИНЦИПИ РОЗРОБКИ ПАРАЛЕЛЬНИХ МЕТОДІВ Розробка алгоритмів (а особливо методів паралельних обчислень) для вирішення складних науково-технічних завдань часто є значною
Методи і алгоритми паралельних обчислень Проектування паралельних алгоритмів Кулаков Кирилл Александрович 2016 Петрозаводськ Цілі проектування Балансування навантаження Масштабованість Ефективність
Високопродуктивні обчислення Лекція 2. Оцінка максимально можливого паралелізму Забезпечення найкращих найкращого прискорення S T \u003d ефективності E \u003d 1 можливо не для всіх обчислювально T трудомістких
Лекції Лекція 1. Принципи побудови паралельних обчислювальних систем .............................. 23 Лекція 2. Моделювання і аналіз паралельних обчислень .. .... 49 Лекція 3. Оцінка комунікаційної
Нижегородський державний університет ім. М. І. Лобачевського Факультет Обчислювальної математики і кібернетики Освітній комплекс Введення в методи паралельного програмування Розділ 9. Паралельні
Проект комісії Президента з модернізації і технологічного розвитку економіки Росії «Створення системи підготовки висококваліфікованих кадрів в області суперкомп'ютерних технологій і спеціалізованого
Тема: Розпаралелювання виразів на прикладі арифметичних Основні характеристики складності і паралельності Що підлягає распараллеливанию? Завдання (декомпозиція на підзадачі меншої розмірності) 2Метод
ПИТАННЯ ДО ТЕСТУ З КУРСУ «ПАРАЛЕЛЬНІ ОБЧИСЛЮВАЛЬНІ СИСТЕМИ» 1. Принципи побудови паралельних обчислювальних систем (15) 1. Схеми багатопроцесорних систем з однорідним і неоднорідним доступом. 2.
Проектування паралельних алгоритмів Лекція 3.1 29.03.2012 Т.Ю.Лимарь 1 3.1 Методологія проектування Поділ Встановлення зв'язків Агрегирование Прив'язка до конкретної ЕОМ 29.03.2012 Т.Ю.Лимарь 2 3.1.1
Московський державний університет ім. М.В. Ломоносова Історія і методологія паралельного програмування 9. Проектування паралельних алгоритмів Розробники: Л.Б. Соколинский, д.ф.-м.н., професор
Федеральне агентство з освіти Нижегородський державний університет ім. Н.І. Лобачевського Національний проект «Освіта» Інноваційна освітня програма ННГУ. Освітньо-науковий
Нижегородський державний університет ім. М. І. Лобачевського Факультет обчислювальної математики і кібернетики Кафедра математичного забезпечення ЕОМ Лабораторія «Інформаційні технології» ItLab Практичний
Нижегородський державний університет ім. Н.І. Лобачевського - Національний дослідницький університет - Лекція. Моделювання паралельних обчислень Гергель В.П., декан ВМК ННДУ Суперкомп'ютерні
Алгоритми для паралельних обчислювальних систем 1. Типи паралелізму і методи синтезу паралельних алгоритмів. 2. Оцінка ефективності паралельних алгоритмів. 1. Типи паралелізму і методи синтезу паралельних
Суперкомп'ютерних КОНСОРЦІУМ УНІВЕРСИТЕТІВ РОСІЇ Проект Створення системи підготовки висококваліфікованих кадрів в області суперкомп'ютерних технологій і спеціалізованого програмного забезпечення
Оцінка ефективності паралельних алгоритмів Лекція 4. 29.03.2012 Т.Ю. Лимар 1 Введення Принциповий момент при розробці паралельних алгоритмів - аналіз ефективності використання паралелізму:
Оцінка ефективності паралельних алгоритмів Лекція 7 Т.Ю. Лимар Принциповий момент при розробці паралельних алгоритмів - аналіз ефективності використання паралелізму: Оцінка максимально можливого
Основні поняття ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ Паралельні обчислення (паралельна обробка) це використання декількох або багатьох обчислювальних пристроїв для одночасного виконання різних частин однієї
Математичні моделі і методи ефективного використання розподілених Цифрова обчислювальних 3D-медицина систем Тема Результати Підзаголовок в області комп'ютерної презентації графіки і геометричного
УДК 681.5 ПАРАЛЕЛЬНІ АЛГОРИТМИ ЧИСЕЛЬНОГО рішення задачі КОШІ ДЛЯ СЗДР Назарова І.А. Донецький національний технічний університет предложено Паралельні чісельні алгоритми однокроковіх методів для
ГЛАВА МОДЕЛЮВАННЯ І АНАЛІЗ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ При розробці паралельних алгоритмів розв'язання складних науково-технічних завдань принциповим моментом є аналіз ефективності використання паралелізму,
1. Цілі і завдання дисципліни: Суперкомп'ютерні технології і високопродуктивні обчислення з використанням багатопроцесорних обчислювальних систем (МВС) стають важливим чинником науково-технічного
Побудова статистичних моделей ефективності паралельних програм В.Н.Белецкій, С.А.Резнікова, А.А.Чемеріс Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України У статті розглянуто
Інформатика, управління, економіка ПРАЦІ МФТІ 2 \u200b\u200bТом 2, (5) УДК 59687 + 475 АС Хрітанков Московський фізико-технічний інститут (державний університет) Математична модель характеристик продуктивності
АЛГОРИТМИ БАЛАНСУВАННЯ ЗАВАНТАЖЕННЯ ПРОЦЕСОРІВ паралельної обчислювальної системи Бельков Д.В. Донецький національний технічний університет, м Донецьк кафедра обчислювальної математики і програмування
Обчислювальні машини і програмне забезпечення 681.3.06 П.А. Павлов ЕФЕКТИВНІСТЬ РАСПРЕДЁЛЕННИХ ОБЧИСЛЕНЬ В масштабується Масштабованість (scalability) є одним з найважливіших вимог
Метод Рітца Виділяють два основних типи методів вирішення варіаційних завдань. До першого типу відносяться методи, що зводять вихідну задачу до вирішення диференціальних рівнянь. Ці методи дуже добре розвинені
Діагональний МЕТОД МНОЖЕННЯ щільно матриць Князькова Т.В., к.т.н., доцент, ВятГУ, м Кіров Сьогодні з ростом потужностей обчислювальних систем і сучасних суперкомп'ютерів в широкому спектрі галузей економіки
Введення 1 Глава 1 Завдання 1.1 Розминка Перше завдання на написання програми, що використовує бібліотеку MPI, одне на всіх. 1.1.1 Обчислення числа π Обчислити число π за такою формулою: 1 + 1 dx 4 -1 + x
Лабораторна робота 4 Паралельна реалізація методу Якобі в тривимірній області Мета роботи: практичне освоєння методів розпаралелювання чисельних алгоритмів на регулярних сітках на прикладі реалізації
Р. І. Идрисов ВРЕМЕННАЯ розгортки ВНУТРІШНЬОГО ПОДАННЯ IR2 МОВИ SISAL 3.1 * На сьогоднішній день збільшення обчислювальних потужностей пов'язано вже не з прискоренням окремого, а з додаванням додаткових
Стратегія оптимізаційного дослідження і методи вирішення завдань статичної та динамічної оптимізації технологічних об'єктів Завдання статичної оптимізації технологічних об'єктів традиційно формулюються
ОРГАНІЗАЦІЯ ПАРАЛЕЛЬНИХ зернистий ОБЧИСЛЮВАЛЬНИХ ПРОЦЕСІВ (Отримання паралельних послідовностей зернистих обчислень) Наведемо приклади отримання паралельних алгоритмів, безлічі операцій яких
ПАРАЛЕЛЬНІ властивості алгоритму Паралельні комп'ютери (суперкомп'ютери) призначені для швидкого вирішення великих завдань. чим могутніше комп'ютер, Тим потенційно швидше можна вирішити на ньому завдання. Крім
Каляєв А.В. ПРОГРАМУВАННЯ ВІРТУАЛЬНИХ архітектури та ОРГАНІЗАЦІЯ структурно процедурних ОБЧИСЛЕНЬ В багатопроцесорноїсистеми з масовим паралелізмом 1 Анотація НДІ багатопроцесорних обчислювальних
Алгоритми паралельного множення матриць 1 Стрічкові алгоритми множення матриць В даних алгоритмах матриці розбиваються на безперервні послідовності рядків або стовпців (смуги). У найпростішому випадку
Розподіл пам'яті Розподіл пам'яті - це процес, в результаті якого окремих елементах вихідної програми ставляться у відповідність адреса, розмір і атрибути області пам'яті, необхідної для розміщення
РІШЕННЯ нелінійних рівнянь І СИСТЕМ нелінійних рівнянь .. РІШЕННЯ нелінійних рівнянь виду Чисельне рішення нелінійних алгебраїчних або трансцендентних рівнянь. полягає в знаходженні значень
«Алгебра та геометрія» 13. Системи лінійних алгебраїчних рівнянь (СЛАР). Теорема Кронекера-Капеллі. Загальне і приватне рішення СЛАР. 14. Криві другого порядку: еліпс, гіпербола, парабола, і їх властивості.
УДК 681.32 ПІДВИЩЕННЯ ПРОДУКТИВНОСТІ КЛАСТЕРІВ РОБОЧИХ СТАНЦІЙ З ВИКОРИСТАННЯМ віялові РОЗПОДІЛУ ДОДАТКОВИХ ЗАВДАНЬ НА простоювати устаткування 2012 В. М. Довгаль 1, С. Г. Спірін 2 1 професор
Граф алгоритму і паралельні обчислення. Внутрішній паралелізм програм. Лекція 3 12.04.2012 (С) Л.Б.Соколінскій 1 3.1 Внутрішній паралелізм Програма містить паралелізм, якщо деякі її частини (оператори)
Освіти та науки Росії Федерального державного БЮДЖЕТНА освітня установа вищої професійної освіти «САМАРСЬКИЙ ДЕРЖАВНИЙ АЕРОКОСМІЧНИЙ УНІВЕРСИТЕТ ІМЕНІ АКАДЕМІКА С.П.КОРОЛЬОВА
Лекція 5 5 Теорема існування та єдиності розв'язку задачі Коші для нормальної системи ОДУ Постановка завдання Завдання Коші для нормальної системи ОДУ x \u003d f (, x), () полягає у знаходженні рішення x \u003d
Нижегородський державний університет ім. М. І. Лобачевського Факультет Обчислювальної математики і кібернетики Освітній комплекс Введення в методи паралельного програмування Розділ 2. Моделювання
Глава 5. МЕТОДИ неявно перебір Розглянемо загальну постановку задачі дискретної оптимізації mi f (x), (5.) x D в якій -мірний шуканий вектор x належить кінцевому безлічі допустимих рішень D.
ЗМІСТ Введення .... 12 Ч а с т ь I. Основи розпаралелювання Лекція 1. Про постановку задачі розпаралелювання ... 17 1.1. Введення .... 17 1.2. Про деякі обчислювальних задачах .... 19 1.3. чисельний
УДК 68.3.06 ВИЗНАЧЕННЯ ЧИСЛА І ТОПОЛОГІЇ РОЗМІЩЕННЯ СТАНЦІЙ багатопроцесорних обчислювальних СИСТЕМИ А.В. Погрібний Інститут «Кібернетичний центр» ТПУ E-mail: [Email protected] Розглянуто завдання
Екстраполяціонного блокових однокрокових МЕТОДИ ЧИСЕЛЬНОГО високоточних рішення задачі КОШІ Кулаков В.В. Назарова І. О. Фельдман Л.П. Донецький національний технічний університет Розглядаються паралельні
Праці ІСА РАН, 2008. Т. 32 Про поняття продуктивності в розподілених обчислювальних системах М. А. Посипкін, А. С. Хрітанков Інститут системного аналізу Російської академії наук (ІСА РАН) В даній
2007 НАУКОВИЙ ВІСНИК МГТУ ГА 26 серія Радіофізика і радіотехніка УДК 6236: 6239 ОЦІНКА ДОЦІЛЬНОСТІ розпаралелювання ІНФОРМАЦІЙНО-ЗАЛЕЖНИХ ЗАВДАНЬ В ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ РН Акіншиної Стаття представлена
Максимальна розпаралелювання алгоритмів на основі концепції Q-детермінанта Валентина Миколаївна Алеева Південно-Уральський державний університет (НДУ) Новосібірcк, 2015 ВСТУП В доповіді розглядається
Міністерство освіти і науки Російської Федерації Нижегородський державний університет ім. Н.І. Лобачевського В.П. Гергель високопродуктивних обчислень ДЛЯ МНОГОПРОЦЕССОР- них багатоядерних
ЛК 1. Моделювання. 1. Основні поняття. 2 Принципи моделювання. 3 Властивості моделей 4 Класифікація методів моделювання. 5. Математичне моделювання 1. Основні поняття. моделювання заміщення
Федеральне агентство з освіти Державна освітній заклад вищої професійної освіти «Новосибірський державний університет» (НГУ) Факультет інформаційних технологій
Нижегородський державний університет ім. Н.І. Лобачевського Науково дослідний університет Створення навчальної бібліотеки паралельних методів Parlib Виконали: Козин Е.А. Кутлана М.В. Осокін
681.3.06 ПРОЕКТУВАННЯ СТРУКТУРИ ЛОКАЛЬНОЇ МЕРЕЖІ ДЛЯ розподілених обчислювальних СИСТЕМИ РЕАЛЬНОГО ЧАСУ А.В. Погрібний, Д.В. Погрібний Інститут «Кібернетичний центр» ТПУ E-mail: [Email protected]
ПАРАЛЕЛЬНІ АЛГОРИТМИ МЕТОДУ циклічних прогонки Головашкін Д.Л., Філатов М. В. Інститут систем обробки зображень РАН Самарський державний аерокосмічний університет Анотація Робота присвячена
УДК 519.856; 519.854; 519.85 СТАТИСТИЧЕСКИЙ ПОШУК СТРУКТУР ІНФОРМАЦІЙНО- ОБЧИСЛЮВАЛЬНОЇ МЕРЕЖІ В.В. Малигін Досліджено властивості збіжності функції оцінки структури інформаційно обчислювальної мережі. на
Побудова рекурсивно-паралельні алгоритми вирішення задач обчислювальної геометрії на основі стратегії «розподіляй і володарюй» В.Н. Терещенко В роботі розглядається один з підходів побудови ефективних
12.1. Введення-виведення за опитуванням готовності пристрою Готовність або неготовність зовнішнього пристрою до вводу-виводу перевіряється в регістрі стану зовнішнього пристрою Для програмно-керованого введення / виведення
Таксономія Флінна Кириллова Юлия 6057/2 22.11.11 Таксономія Флінна загальна класифікація архітектур ЕОМ за ознаками наявності паралелізму в потоках команд і даних. запропонована в 1972 р Майклом Флінном.
Лабораторна робота 4 Рішення завдання Пуассона методом Якобі в тривимірній області Мета - практичне освоєння методів розпаралелювання алгоритмів завдань, що вирішуються сітковими методами на прикладі рішення
Паралельні обчислення - спосіб організації комп'ютерних обчислень, при якому програми розробляються як набір взаємодіючих обчислювальних процесів, що працюють одночасно.
Існують різні способи реалізації паралельних обчислень: кожен обчислювальний процес може бути реалізований у вигляді процесу операційної системи, або ж обчислювальні процеси можуть являти собою набір потоків виконання всередині одного процесу. Потік (або правильніше потік виконання) - найменша одиниця обробки, виконання якої може бути призначено ядром операційної системи. Кілька потоків виконання можуть існувати в рамках одного і того ж процесу і спільно використовувати ресурси, такі як пам'ять, тоді як процеси не поділяють цих ресурсів. Паралельні програми можуть фізично виконуватися або послідовно на єдиному процесорі - перемежовуючи по черзі кроки виконання кожного обчислювального процесу, або паралельно - виділяючи кожному обчислювальному процесу один або кілька процесорів (що знаходяться поруч або розподілених в комп'ютерну мережу).
Основна складність при проектуванні паралельних програм - забезпечити правильну послідовність взаємодій між різними обчислювальними процесами, а також поділ таких ресурсів, як оперативна пам'ять або периферійні пристрої.
У деяких паралельних системах програмування передача даних між компонентами прихована від програміста, тоді як в інших вона повинна вказуватися явно. Явні взаємодії можуть бути розділені на два типи:
1. Взаємодія через пам'ять, що розділяється (наприклад, в Java або C #). Даний вид паралельного програмування зазвичай вимагає якоїсь форми захоплення управління для координації потоків між собою.
2. Взаємодія з допомогою передачі повідомлень. Обмін повідомленнями може відбуватися асинхронно, або з використанням методу «рандеву», при якому відправник блокований до тих пір, поки його повідомлення не буде доставлене. Асинхронна передача повідомлень може бути надійною (з гарантією доставки) або ненадійною. Паралельні системи, засновані на обміні повідомленнями, часто більш прості для розуміння, ніж системи з пам'яттю, що, і зазвичай розглядаються як більш досконалий метод паралельного програмування. Обмін повідомленнями може бути ефективно реалізований на симетричних мультипроцесорах як з розділяється когерентної пам'яттю, так і без неї.
Існує досить багато різних технологій паралельного програмування. Причому ці технології відрізняються не стільки мовами програмування, скільки архітектурними підходами до побудови паралельних систем. Наприклад, якісь технології припускають побудова паралельних рішень на основі декількох комп'ютерів (як одного, так і різних типів), Інші ж припускають саме роботу на одній машині з декількома процесорними ядрами. В даний час основними програмні інструменти створення паралельних програм є:
1. OpenMP використовується в паралельних системах із загальною пам'яттю (наприклад, сучасні комп'ютери з багатоядерними процесорами);
2. MPI (Message Passing Interface) є стандартом систем передачі повідомлень між паралельно виконуваними процесами, використовується при розробці програм для суперкомп'ютерів;
3. POSIX Threads є стандартом реалізації потоків виконання;
4. Операційна система Windows має вбудовану підтримку багатопотокових додатків для C ++ на рівні API;
5. PVM (Parallel Virtual Machine) дозволяє поєднувати різнорідні пов'язані мережею комп'ютери в загальний обчислювальний ресурс.
Системи на базі декількох комп'ютерів відносять до класу систем для розподілених обчислень. Подібні рішення використовуються досить давно. Найбільш яскравий приклад технології розподілених обчислень - MPI (Message Passing Interface - інтерфейс передачі повідомлень). MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для величезного числа комп'ютерних платформ. MPI надає програмісту єдиний механізм взаємодії гілок всередині паралельного додатка незалежно від машинної архітектури (однопроцесорні / багатопроцесорні із загальною / роздільною пам'яттю), взаємного розташування гілок (на одному процесорі або на різних).
Так як MPI призначений в першу чергу для систем з роздільною пам'яттю, то використання його для організації паралельного процесу в системі із загальною пам'яттю є вкрай складним недоцільним. Проте, нічого не заважає робити MPI-рішення для однієї машини.
А ось системи паралельного програмування для роботи на одній машині, почали розвиватися відносно недавно. Звичайно, це не принципово нові ідеї, але саме з приходом багатоядерних систем на ринок персональних комп'ютерів, мобільних пристроїв, такі технології як OpenMP отримали значний розвиток.
Дуже важливо, щоб технологія паралельного програмування підтримувала можливість робити програму паралельної поступово. Зрозуміло ідеальну паралельну програму слід відразу писати паралельної, можливо на якомусь функціональній мові, де питання розпаралелювання взагалі не варто. Але на практиці доводиться, поступово распараллеливать написану послідовну з метою підвищення швидкодії. В цьому випадку технологія OpenMP буде дуже вдалим вибором. Вона дозволяє, вибравши в додатку найбільш нужденні в паралелізації місця, в першу чергу зробити паралельними саме їх. Процес розробки паралельної версії можна переривати, випускати проміжні версії програми, повертатися до нього в міру необхідності. Саме тому зокрема технологія OpenMP стала досить популярною.
OpenMP (Open Multi-Processing) - це набір директив компілятора, бібліотечних процедур і змінних оточення, які призначені для програмування багатопотокових додатків на багатопроцесорних системах із загальною пам'яттю.
Розробку специфікації OpenMP ведуть кілька великих виробників обчислювальної техніки і програмного забезпечення, чия робота регулюється некомерційною організацією, званої OpenMP Architecture Review Board (ARB).
Перша версія з'явилася в 1997 році, призначалася для мови Fortran. Для С / С ++ версія розроблена в 1998 році. У 2008 році вийшла версія OpenMP 3.0. Інтерфейс OpenMP став однією з найбільш популярних технологій паралельного програмування. OpenMP успішно використовується як при програмуванні суперкомп'ютерних систем з великою кількістю процесорів, так і в настільних вашій системі або, наприклад, в Xbox 360.
OpenMP реалізує паралельні обчислення з допомогою многопоточности, в якій «головний» (master) потік створює набір підлеглих (slave) потоків і завдання розподіляється між ними. Передбачається, що потоки виконуються паралельно на машині з декількома процесорами (кількість процесорів не обов'язково має бути більше або дорівнює кількості потоків).
Завдання, що виконуються потоками паралельно, також як і дані, необхідні для виконання цих завдань, описуються за допомогою спеціальних директив препроцесора відповідної мови - прагм. Наприклад, ділянка коду на мові Fortran, який повинен виконуватися декількома потоками, кожен з яких має свою копію змінної N, передує наступній директивою:! $ OMP PARALLEL PRIVATE (N)
Кількість створених потоків може регулюватися як самою програмою за допомогою виклику бібліотечних процедур, так і ззовні, за допомогою змінних оточення.
Ключовими елементами OpenMP є
1. конструкції для створення потоків (директива parallel);
2. конструкції розподілу роботи між потоками (директиви DO / for і section);
3. конструкції для управління роботою з даними (вираження shared і private для визначення класу пам'яті змінних);
4. конструкції для синхронізації потоків (директиви critical, atomic і barrier);
5. процедури бібліотеки підтримки часу виконання (наприклад, omp_get_thread_num);
6. змінні оточення (наприклад, OMP_NUM_THREADS).
У OpenMP використовується модель паралельного виконання «розгалуження-злиття». Програма OpenMP починається як єдиний потік виконання, званий початковим потоком. Коли потік зустрічає паралельну конструкцію, він створює нову групу потоків, що складається з себе і деякого числа додаткових потоків, і стає головним у новій групі. Всі члени нової групи (включаючи головний) виконують код всередині паралельної конструкції. В кінці паралельної конструкції є неявний бар'єр. Після паралельної конструкції виконання призначеного для користувача коду продовжує тільки головний потік. В паралельний регіон можуть бути вкладені інші паралельні регіони, в яких кожен потік початкового регіону стає основним для своєї групи потоків. Вкладені регіони можуть в свою чергу включати регіони більш глибокого рівня вкладеності.
Число потоків в групі, що виконуються паралельно, можна контролювати декількома способами. Один з них - використання змінної оточення OMP_NUM_THREADS. Інший спосіб - виклик процедури omp_set_num_threads (). Ще один спосіб - використання виразу num_threads в поєднанні з директивою parallel.
У цій програмі два масиви (a і b) складаються паралельно десятьма потоками.
#include
#include
int main (int argc, char * argv)
float a [N], b [N], c [N];
omp_set_dynamic (0); // заборонити бібліотеці openmp міняти число потоків під час виконання
omp_set_num_threads (10); // встановити число потоків в 10
// инициализируем масиви
for (I \u003d 0; I< N; i++)
// обчислюємо суму масивів
#pragma omp parallel shared (a, b, c) private (i)
for (I \u003d 0; I< N; i++)
c [i] \u003d a [i] + b [i];
printf ( "% f \\ n", c);
Цю програму можна скомпілювати, використовуючи gcc-4.4 і новіші з прапором -fopenmp. Очевидно, якщо прибрати підключення заголовки omp.h, а також виклики функції настройки OpenMP, програму можливо скомпілювати на будь-якому компіляторі З як звичайну послідовну програму.
OpenMP підтримується багатьма сучасними компіляторами:
1. Компілятори Sun Studio підтримують офіційну специфікацію - OpenMP 2.5 - з поліпшеною продуктивністю під ОС Solaris; підтримка Linux запланована на наступний реліз.
2. Visual C ++ 2005 і вище підтримує OpenMP в редакціях Professional і Team System.
3. GCC 4.2 підтримує OpenMP, а деякі дистрибутиви (такі як Fedora Core 5 gcc) включили підтримку в свої версії GCC 4.1.
4. Intel C ++ Compiler, включаючи версію Intel Cluster OpenMP для програмування в системах з розподіленою пам'яттю.
Message Passing Interface (MPI, інтерфейс передачі повідомлень) - програмний інтерфейс (API) для передачі інформації, який дозволяє обмінюватися повідомленнями між процесами, які виконують одну задачу. Розроблено Вільямом Гроуппом, Евін ласки (англ.) І іншими.
MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для великого числа комп'ютерних платформ. Використовується при розробці програм для кластерів і суперкомп'ютерів. Основним засобом комунікації між процесами в MPI є передача повідомлень один одному. Стандартизацією MPI займається MPI Forum. У стандарті MPI описаний інтерфейс передачі повідомлень, який повинен підтримуватися як на платформі, так і в додатках користувача. В даний час існує велика кількість безкоштовних і комерційних реалізацій MPI. Існують реалізації для мов Фортран 77/90, Сі і Сі ++.
В першу чергу MPI орієнтований на системи з розподіленою пам'яттю, тобто коли витрати на передачу даних великі, в той час як OpenMP орієнтований на системи із загальною пам'яттю (багатоядерні із загальним Ешем). Обидві технології можуть використовуватися спільно, щоб оптимально використовувати в кластері багатоядерні системи.
Перша версія MPI розроблялася в 1993-1994 році, і MPI 1 вийшла в 1994.
Більшість сучасних реалізацій MPI підтримують версію 1.1. Стандарт MPI версії 2.0 підтримується більшістю сучасних реалізацій, але деякі функції можуть бути реалізовані не до кінця.
передача і отримання повідомлень між окремими процесами;
колективні взаємодії процесів;
взаємодії в групах процесів;
реалізація топологій процесів;
динамічне породження процесів і управління процесами;
односторонні комунікації (Get / Put);
паралельний введення і виведення;
розширені колективні операції (процеси можуть виконувати колективні операції не тільки всередині одного комунікатора, а й в рамках декількох комунікаторів).
Версія MPI 2.1 вийшла на початку вересня 2008 року.
Базовим механізмом зв'язку між MPI процесами є передача і прийом повідомлень. Повідомлення несе в собі дані, що передаються та інформацію, що дозволяє приймаючій стороні здійснювати їх вибірковий прийом:
1. відправник - ранг (номер в групі) відправника повідомлення;
2. одержувач - ранг одержувача;
3. ознака - може використовуватися для поділу різних видів повідомлень;
4. комунікатор - код групи процесів.
Операції прийому і передачі можуть бути блокує і не блокується. Для не блокують операцій визначені функції перевірки готовності і очікування виконання операції.
Іншим способом зв'язку є віддалений доступ до пам'яті (RMA), що дозволяє читати і змінювати область пам'яті віддаленого процесу. Локальний процес може переносити область пам'яті віддаленого процесу (всередині зазначеного процесами вікна) в свою пам'ять і назад, а також комбінувати дані, що передаються в віддалений процес з наявними в його пам'яті даними (наприклад, шляхом підсумовування). всі операції віддаленого доступу до пам'яті не блокуються, однак, до і після їх виконання необхідно викликати блокуються функції синхронізації.
Нижче наведено приклад програми обчислення числа π на мові C з використанням MPI:
// Підключення необхідних заголовків
#include
#include
// Підключення заголовки MPI
#include «mpi.h»
// Функція для проміжних обчислень
double f (double a)
return (4.0 / (1.0+ a * a));
// Головна функція програми
int main (int argc, char ** argv)
// Оголошення змінних
int done \u003d 0, n, myid, numprocs, I;
double PI25DT \u003d 3.141592653589793238462643;
double mypi, pi, h, sum, x;
double startwtime \u003d 0.0, endwtime;
char processor_name;
// Ініціалізація підсистеми MPI
MPI_Init (& argc, & argv);
// Отримати розмір комунікатора MPI_COMM_WORLD
// (загальне число процесів в рамках завдання)
MPI_Comm_size (MPI_COMM_WORLD, & numprocs);
// Отримати номер поточного процесу в рамках
// комунікатора MPI_COMM_WORLD
MPI_Comm_rank (MPI_COMM_WORLD, & myid);
MPI_Get_processor_name (processor_name, & namelen);
// Висновок номера потоку в загальному пулі
fprintf (stdout, "Process% d of% d is on% s \\ n", myid, numprocs, processor_name);
// кількість інтервалів
fprintf (stdout, "Enter the number of intervals: (0 quits)");
if (scanf ( "% d", & n)! \u003d 1)
fprintf (stdout, "No number entered; quitting \\ n");
MPI_Bcast (& n, 1, MPI_INT, 0, MPI_COMM_WORLD);
h \u003d 1.0 / (double) n;
// обраховування точки, закріпленої за процесом
for (I \u003d myid + 1; (I<= n) ; I += numprocs)
x \u003d h * ((double) I - 0.5);
// Скидання результатів з усіх процесів і складання
MPI_Reduce (& mypi, & pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
// Якщо це головний процес, висновок отриманого результату
printf ( "PI is approximately% .16f, Error is% .16f \\ n", pi, fabs (pi - PI25DT));
endwtime \u003d MPI_Wtime ();
printf ( "wall clock time \u003d% f \\ n", endwtime-startwtime);
// Звільнення підсистеми MPI
Найбільш поширеними реалізаціями MPI на сьогоднішній день є:
MPICH - найпоширеніша безкоштовна реалізація, працює на UNIX-системах і Windows NT
LAM / MPI - ще одна безкоштовна реалізація MPI. Підтримує гетерогенні конфігурації, LAM (http://www.lam-mpi.org) підтримує гетерогенні конфігурації, пакет Globus і задовольняє IMPI (Interoperable MPI).
Підтримуються різні комунікаційні системи (в тому числі Myrinet).
WMPI - реалізація MPI для Windows
MPI / PRO for Windows NT - комерційна реалізація для Windows NT
Intel MPI - комерційна реалізація для Windows / Linux
Microsoft MPI входить до складу Compute Cluster Pack SDK. Заснований на MPICH2, але включає додаткові засоби управління завданнями. Підтримується специфікація MPI-2.
HP-MPI - комерційна реалізація від HP
SGI MPT - платна бібліотека MPI від SGI
Mvapich - безкоштовна реалізація MPI для Infiniband
Open MPI - безкоштовна реалізація MPI, спадкоємець LAM / MPI
Oracle HPC ClusterTools - безкоштовна реалізація для Solaris SPARC / x86 і Linux на основі Open MPI
MPJ - MPI for Java
POSIX Threads - стандарт POSIX реалізації потоків виконання, що визначає API для створення і управління ними.
Бібліотеки, які реалізують цей стандарт (і функції цього стандарту), зазвичай називаються Pthreads (функції мають приставку «pthread_»). Хоча найбільш відомі варіанти для Unix-подібних операційних систем, таких як Linux або Solaris, але існує і реалізація для Microsoft Windows (Pthreads-w32)
Pthreads визначає набір типів і функцій на мові програмування Сі. Заголовки - pthread.h.
Типи даних:
1. pthread_t - дескриптор потоку;
2. pthread_attr_t - перелік атрибутів потоку.
Функції управління потоками:
1. pthread_create () - створення потоку;
2. pthread_exit () - завершення потоку (повинна викликатися функцією потоку при завершенні);
3. pthread_cancel () - скасування потоку;
4. pthread_join () - заблокувати виконання потоку до припинення іншого потоку, зазначеного у виклику функції;
5. pthread_detach () - звільнити ресурси займані потоком (якщо потік виконується, то звільнення ресурсів відбудеться після його завершення);
6. pthread_attr_init () - форматувати структуру атрибутів потоку;
7. pthread_attr_setdetachstate () - вказати системі, що після завершення потоку вона може автоматично звільнити ресурси, які займає потоком;
8. pthread_attr_destroy () - звільнити пам'ять від структури атрибутів потоку (знищити дескриптор).
Функції синхронізації потоків:
2. pthread_mutex_init (), pthread_mutex_destroy (), pthread_mutex_lock (), pthread_mutex_trylock (), pthread_mutex_unlock ();
3. pthread_cond_init (), pthread_cond_signal (), pthread_cond_wait ().
Приклад використання потоків на мові C:
#include
#include
#include
#include
static void wait_thread (void)
time_t start_time \u003d time (NULL);
while (time (NULL) \u003d\u003d start_time)
/ * Do nothing except chew CPU slices for up to one second. * /
static void * thread_func (void * vptr_args)
for (I \u003d 0; I< 20; i++)
fputs ( "b \\ n", stderr);
pthread_t thread;
if (pthread_create (& thread, NULL, thread_func, NULL)! \u003d 0)
return EXIT_FAILURE;
for (I \u003d 0; I< 20; i++)
if (pthread_join (thread, NULL)! \u003d 0)
return EXIT_FAILURE;
return EXIT_SUCCESS;
Представлена \u200b\u200bпрограма використовують два потоки, що друкують в консоль повідомлення, один, що друкує "a", другий - "b". Висновок повідомлень змішується в результаті перемикання виконання між потоками або одночасному виконанні на мультипроцесорних системах.
Програма на C створює один новий потік для друку "b", а основний потік друкує "a". Основний потік (після друку "aaaaa ....") Чекає завершення дочірнього потоку.
Контрольні питання
- Що таке паралельна програма?
- У чому відмінність між процесом і потоком виконання?
- Чи може програма створити 5 потоків при роботі на чотирьохядерним процесор?
- Які особливості паралельних програм з пам'яттю?
- Які існують програмні засоби для розробки паралельних програм?
- Чому велике поширення при створенні програм для ПК отримав саме OpenMP, а не, наприклад, MPI?