Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
| У цій статті відсутній , що має містити найважливіших аспектів статті. (вересень 2020) |
Паралелізм за задачами та паралелізм за даними
Щоб мати можливість використовувати паралелізм як такий в наявності мають бути програмні та апаратні засоби для забезпечення можливості одночасного виконання двох та більше завдань. Є два важливі типи паралельних обчислень:
-паралелізм за командами або їх сукупністю (задачами) – можливість одночасно виконувати різні команди (задачі) одночасно;
-паралелізм з даними – можливість виконувати одну і ту ж команду (задачу) з-над різними наборами даних одночасно.
Для нетривіальних проблем, важливо мати формалізовані концепції розподілу (декомпозиції) паралелізму, тому при розпаралелюванні обчислень використовують наступні концепції декомпозиції:
-розподіл за командами (задачами): розбиття алгоритму на незалежні задачі (без фокусування уваги на даних);
-розподіл за даними: розбиття набору даних на окремі частини, які можна опрацьовувати паралельно.
Розподіл за задачами спрощує алгоритм на функціонально незалежні частини, але виникають ситуації, коли задачі можуть бути залежні від інших задач:
-якщо вхідні (початкові) дані задачі В залежать від вихідних (кінцевих) даних задачі А, то задача В залежна від задачі А;
-задачі, що є незалежними (або залежності яких є завершеними) можуть бути виконані в будь-який час незалежно одна від одної для досягнення паралелізму;
Для опису зв’язків між задачами використовуються графи залежності за задачами (рисунок 1.1, а, б).
Для наочнішого прикладу розробимо граф залежності за задачами для випічки печива (рисунок 2.2).
Кожне завдання, яке не є залежним в графі залежностей може бути виконано паралельно (наприклад, розігрівання печі та купівля продуктів). Розподіл за даними застосовується або для результуючих даних, або для початкових.
Для більшості наукових та інженерних застосунків декомпозуються результуючі дані, наприклад:
- Кожен отриманий піксель зображення згортки отримується шляхом застосування фільтру до деякої області вхідних пікселів.
- Кожен отриманий елемент перемноження матриць, що отриманий множенням рядку на стовпчик вхідних матриць.
Дуже добре мати цикли, в яких за кожної ітерації обчислюється одне значення матриці чи масиву. Такі типи алгоритмів найкраще відповідають декомпозиції по результуючим даним.
Така методика застосовується кожного разу, коли алгоритм базується на функціях із відношенням один-до-одного чи багато-до-одного.
Декомпозиція по початковим даним подібна до попередньої, за винятком того, що вона буде корисною, коли алгоритм є функцією із відношенням один-до-багатьох, наприклад:
-Гістограма будується шляхом розміщення кожного початкового даного в один із фіксованого числа контейнерів.
-Функція пошуку може отримувати строку для пошуку як вхідні дані та здійснювати пошук у інших строках.
Вибір того, яким чином здійснювати декомпозицію поставленого завдання базується виключно на алгоритмі. Тим не менш, коли стає актуальною реалізація паралельного алгоритму, до уваги потрібно брати міркування як щодо програмної реалізації, так і щодо апаратного забезпечення цієї реалізації.
Апаратний та програмний паралелізм
В попередньому питанні було розглянуто поділ паралелізму подібно до моделі Флінна: за командами (задачами) та даними. В попередній темі (тема 2) була розглянута архітектура апаратних засобів для паралельних обчислень. Також існують програмні засоби, що дозволяють здійснювати паралельні обчислення. Як апаратні, так і програмні засоби можуть досягати паралелізму і за допомогою паралелізму по задачам, і за допомогою паралелізму по даним, за допомогою об’єднання цих підходів. В той же час самі апаратні та програмні засоби можуть використовуватись разом чи окремо (в рідкісних випадках).
Більшість 90’х років ХХ століття було витрачено на отримання центральних процесорів (CPU) з автоматичним використанням паралелізму на рівні інструкцій – Instruction Level Parallelism (ILP): декілька інструкцій (без залежностей) видаються та виконуються паралельно.
Паралелізм високого рівня автоматично важко досягнути без використання різноманітних програмних конструкцій, за допомогою яких апаратному забезпеченню вказується «місця», де будуть виконуватись паралельні обчислення. При паралельному програмуванні програміст повинен вибрати програмну модель та апаратне забезпечення, що підходять для вирішення наявної проблеми.
В загальному випадку одні апаратні засоби підходять для вирішення якихось типів паралельних обчислень краще, ніж інші (таблиця ).
| Тип апаратного забезпечення |
|---|
| Багатоядерні суперскалярні процесори (Multi-core superscalar processors) |
| Векторний (Vector ) або SIMD процесори |
| Багатоядерні SIMD процесори (Multi-core SIMD processors — GPU) |
Паралельне програмне і апаратне забезпечення
Стрімкого розвитку набули також і графічні процесори (англ. Graphic Processing Unit – GPU). GPU програми називаються ядрами, які описуються програмною моделлю під назвою Single Program Multiple Data (SPMD).
SPMD – Single-Program, Multiple Data – «одна програма – багато [потоків] даних»; архітектура SPMD — різновид архітектури MIMD.
SPMD виконує деяку кількість екземплярів однієї і тієї ж програми незалежно і кожен екземпляр опрацьовує різний набір даних.
Наведемо існуючі підходи для розробки паралельних програм:
— Бібліотеки передачі повідомлень: Message Passing Interface (MPI) — інтерфейс передачі повідомлень, де використовується архітектура SPMD на розподілених кластерах. — Бібліотеки потоків (нитей):
POSIX threads (pthreads) — стандарт POSIX реалізації нитей виконання, який визначає API для створення та керування ними. Використовується для реалізації SPMD архітектури на системах із єдиною спільною пам'яттю (shared-memory system).
— Набір директив компілятора та бібліотечних процедур:
Open Multi-Processing (OpenMP) — стандарт розпаралелювання програм, що описує сукупність директив компілятора, бібліотечних процедур та змінних оточення, які призначені для програмування багатопоточних застосунків на багатопроцесорних системах із єдиною спільною пам’яттю (shared-memory system).
•Робота ядер за архітектурами SPMD, SIMD та SIMT на GPU за допомогою програмно-апаратної архітектури CUDA, фреймворка OpenCL, інтерфейсу програмування застосунків DirectCompute.
Розглянемо приклад додавання векторів (Рисунок 3.1)
Поєднання SPMD із стрічковим розбиттям в циклі дозволяє перемножити копії програми виконуючи обрахунки над різними даними паралельно (рисунок 4.2)
В прикладі додавання векторів кожен кусок даних може бути обробленим як незалежний потік (нить – thread).
На сучасних CPU, накладні витрати на створення потоків (threads) настільки великі, що куски даних повинні бути великими. Зазвичай, на практиці це декілька потоків (threads) (кількість така ж, як кількість ядер CPU) і кожному приходиться опрацьовувати великий об'єм даних.
При програмуванні на GPU, накладні витрати на створення потоків (thread) незначні, тому можна створювати один потік (thread) на кожну ітерацію в циклі.
Порівняння затрат часу на операцію додавання векторів при використанні різних підходів та архітектур (Рисунок 5.3)
Кожен виконувач елемент (елементарний процесор) в моделі процесора SIMD – обробляє однакову команду з різною частиною набору даних одночасно. Одна команда (інструкція) видається на виконання одночасно багатьом АЛП (арифметико-логічний пристрій) – ALU. Мається на увазі, що число ALU є шириною SIMD пристрою.
SIMD процесори ефективні для даих паралельних алгоритмів. Вони зменшують об'єм потоку управління та команд апаратного забезпечення за рахунок ALU.
Апаратна реалізація SIMD моделі (Рисунок 6.4)
Одна команда, що поступає повинна бути виконана на всіх елементарних процесорах (processing elements – PE). Один потік (thread) виконується на кожному елементарному процесорі (processing element).
В прикладі додавання векторів SIMD пристрій з шириною в чотири може виконати чотири ітерації циклу відразу.
Всі наявні GPU базуються на SIMD апаратному виконанні:
•GPU апаратно неявно відображає кожен SPMD потік (thread) в SIMD «ядро». Програмісту не потрібно звертати увагу на правильність апаратної складової SPMD моделі, основним тут є продуктивність.
•Ця модель запуску потоків (threads) на SIMD апаратному забезпеченні називається SingleInstructionMultipleThreads (SIMT).
На завершення слід ще раз звернути увагу на відмінності підтримки паралелізму на CPU та GPU:
•На CPU апаратна підтримка атомарних операцій використовується для паралелізму. Атомарні операції дозволяють даним бути зчитаними і записаними без втручання зі сторони іншого потоку.
•GPU розглядається як спеціалізований обчислювальний пристрій, що є сопроцесором до CPU, володіє власною пам’яттю, володіє мможливістю паралельного виконання великої кількості окремих потоків (нитей). Деякі GPU підтримують загальносистемні атомарні операції, але з великим компромісом у продуктивності. Зазвичай код, який вимагає глобальної синхронізації не дуже добре підходить для GPU (чи його слід реорганізувати).
Примітки
- Жуков І., Корочкін О. Паралельні та розподілені обчислення – К. Корнійчук, 2005. – 226 с.
- P. Mehrotra and J. Van Rosendale. Programming distributed memory architectures. In Advances in Languages and Compilers for Parallel Computing. MIT Press, 1991
- Программирование на параллельных обчислювальних системах: Пер с англ. / Под ред. Р. Бэбба. М.: Мир, 1991.
Література
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U cij statti vidsutnij vstupnij rozdil sho maye mistiti viznachennya predmeta i stislij oglyad najvazhlivishih aspektiv statti Vi mozhete dopomogti proyektu napisavshi preambulu veresen 2020 Paralelizm za zadachami ta paralelizm za danimiShob mati mozhlivist vikoristovuvati paralelizm yak takij v nayavnosti mayut buti programni ta aparatni zasobi dlya zabezpechennya mozhlivosti odnochasnogo vikonannya dvoh ta bilshe zavdan Ye dva vazhlivi tipi paralelnih obchislen paralelizm za komandami abo yih sukupnistyu zadachami mozhlivist odnochasno vikonuvati rizni komandi zadachi odnochasno paralelizm z danimi mozhlivist vikonuvati odnu i tu zh komandu zadachu z nad riznimi naborami danih odnochasno Dlya netrivialnih problem vazhlivo mati formalizovani koncepciyi rozpodilu dekompoziciyi paralelizmu tomu pri rozparalelyuvanni obchislen vikoristovuyut nastupni koncepciyi dekompoziciyi rozpodil za komandami zadachami rozbittya algoritmu na nezalezhni zadachi bez fokusuvannya uvagi na danih rozpodil za danimi rozbittya naboru danih na okremi chastini yaki mozhna opracovuvati paralelno Rozpodil za zadachami sproshuye algoritm na funkcionalno nezalezhni chastini ale vinikayut situaciyi koli zadachi mozhut buti zalezhni vid inshih zadach yaksho vhidni pochatkovi dani zadachi V zalezhat vid vihidnih kincevih danih zadachi A to zadacha V zalezhna vid zadachi A zadachi sho ye nezalezhnimi abo zalezhnosti yakih ye zavershenimi mozhut buti vikonani v bud yakij chas nezalezhno odna vid odnoyi dlya dosyagnennya paralelizmu Dlya opisu zv yazkiv mizh zadachami vikoristovuyutsya grafi zalezhnosti za zadachami risunok 1 1 a b Risunok 1 Priklad grafiv zalezhnostej za zadachami Dlya naochnishogo prikladu rozrobimo graf zalezhnosti za zadachami dlya vipichki pechiva risunok 2 2 Risunok 2 2 Graf zalezhnosti za zadachami dlya vipichki pechiva Kozhne zavdannya yake ne ye zalezhnim v grafi zalezhnostej mozhe buti vikonano paralelno napriklad rozigrivannya pechi ta kupivlya produktiv Rozpodil za danimi zastosovuyetsya abo dlya rezultuyuchih danih abo dlya pochatkovih Dlya bilshosti naukovih ta inzhenernih zastosunkiv dekompozuyutsya rezultuyuchi dani napriklad Kozhen otrimanij piksel zobrazhennya zgortki otrimuyetsya shlyahom zastosuvannya filtru do deyakoyi oblasti vhidnih pikseliv Kozhen otrimanij element peremnozhennya matric sho otrimanij mnozhennyam ryadku na stovpchik vhidnih matric Duzhe dobre mati cikli v yakih za kozhnoyi iteraciyi obchislyuyetsya odne znachennya matrici chi masivu Taki tipi algoritmiv najkrashe vidpovidayut dekompoziciyi po rezultuyuchim danim Taka metodika zastosovuyetsya kozhnogo razu koli algoritm bazuyetsya na funkciyah iz vidnoshennyam odin do odnogo chi bagato do odnogo Dekompoziciya po pochatkovim danim podibna do poperednoyi za vinyatkom togo sho vona bude korisnoyu koli algoritm ye funkciyeyu iz vidnoshennyam odin do bagatoh napriklad Gistograma buduyetsya shlyahom rozmishennya kozhnogo pochatkovogo danogo v odin iz fiksovanogo chisla kontejneriv Funkciya poshuku mozhe otrimuvati stroku dlya poshuku yak vhidni dani ta zdijsnyuvati poshuk u inshih strokah Vibir togo yakim chinom zdijsnyuvati dekompoziciyu postavlenogo zavdannya bazuyetsya viklyuchno na algoritmi Tim ne mensh koli staye aktualnoyu realizaciya paralelnogo algoritmu do uvagi potribno brati mirkuvannya yak shodo programnoyi realizaciyi tak i shodo aparatnogo zabezpechennya ciyeyi realizaciyi Aparatnij ta programnij paralelizmV poperednomu pitanni bulo rozglyanuto podil paralelizmu podibno do modeli Flinna za komandami zadachami ta danimi V poperednij temi tema 2 bula rozglyanuta arhitektura aparatnih zasobiv dlya paralelnih obchislen Takozh isnuyut programni zasobi sho dozvolyayut zdijsnyuvati paralelni obchislennya Yak aparatni tak i programni zasobi mozhut dosyagati paralelizmu i za dopomogoyu paralelizmu po zadacham i za dopomogoyu paralelizmu po danim za dopomogoyu ob yednannya cih pidhodiv V toj zhe chas sami aparatni ta programni zasobi mozhut vikoristovuvatis razom chi okremo v ridkisnih vipadkah Bilshist 90 h rokiv HH stolittya bulo vitracheno na otrimannya centralnih procesoriv CPU z avtomatichnim vikoristannyam paralelizmu na rivni instrukcij Instruction Level Parallelism ILP dekilka instrukcij bez zalezhnostej vidayutsya ta vikonuyutsya paralelno Paralelizm visokogo rivnya avtomatichno vazhko dosyagnuti bez vikoristannya riznomanitnih programnih konstrukcij za dopomogoyu yakih aparatnomu zabezpechennyu vkazuyetsya miscya de budut vikonuvatis paralelni obchislennya Pri paralelnomu programuvanni programist povinen vibrati programnu model ta aparatne zabezpechennya sho pidhodyat dlya virishennya nayavnoyi problemi V zagalnomu vipadku odni aparatni zasobi pidhodyat dlya virishennya yakihos tipiv paralelnih obchislen krashe nizh inshi tablicya Tip aparatnogo zabezpechennyaBagatoyaderni superskalyarni procesori Multi core superscalar processors Vektornij Vector abo SIMD procesoriBagatoyaderni SIMD procesori Multi core SIMD processors GPU Paralelne programne i aparatne zabezpechennyaStrimkogo rozvitku nabuli takozh i grafichni procesori angl Graphic Processing Unit GPU GPU programi nazivayutsya yadrami yaki opisuyutsya programnoyu modellyu pid nazvoyu Single Program Multiple Data SPMD SPMD Single Program Multiple Data odna programa bagato potokiv danih arhitektura SPMD riznovid arhitekturi MIMD SPMD vikonuye deyaku kilkist ekzemplyariv odniyeyi i tiyeyi zh programi nezalezhno i kozhen ekzemplyar opracovuye riznij nabir danih Navedemo isnuyuchi pidhodi dlya rozrobki paralelnih program Biblioteki peredachi povidomlen Message Passing Interface MPI interfejs peredachi povidomlen de vikoristovuyetsya arhitektura SPMD na rozpodilenih klasterah Biblioteki potokiv nitej POSIX threads pthreads standart POSIX realizaciyi nitej vikonannya yakij viznachaye API dlya stvorennya ta keruvannya nimi Vikoristovuyetsya dlya realizaciyi SPMD arhitekturi na sistemah iz yedinoyu spilnoyu pam yattyu shared memory system Nabir direktiv kompilyatora ta bibliotechnih procedur Open Multi Processing OpenMP standart rozparalelyuvannya program sho opisuye sukupnist direktiv kompilyatora bibliotechnih procedur ta zminnih otochennya yaki priznacheni dlya programuvannya bagatopotochnih zastosunkiv na bagatoprocesornih sistemah iz yedinoyu spilnoyu pam yattyu shared memory system Robota yader za arhitekturami SPMD SIMD ta SIMT na GPU za dopomogoyu programno aparatnoyi arhitekturi CUDA frejmvorka OpenCL interfejsu programuvannya zastosunkiv DirectCompute Rozglyanemo priklad dodavannya vektoriv Risunok 3 1 Risunok 3 1 Poslidovnij variant dodavannya vektoriv Poyednannya SPMD iz strichkovim rozbittyam v cikli dozvolyaye peremnozhiti kopiyi programi vikonuyuchi obrahunki nad riznimi danimi paralelno risunok 4 2 Risunok 4 2 SPMD dodavannya vektoriv V prikladi dodavannya vektoriv kozhen kusok danih mozhe buti obroblenim yak nezalezhnij potik nit thread Na suchasnih CPU nakladni vitrati na stvorennya potokiv threads nastilki veliki sho kuski danih povinni buti velikimi Zazvichaj na praktici ce dekilka potokiv threads kilkist taka zh yak kilkist yader CPU i kozhnomu prihoditsya opracovuvati velikij ob yem danih Pri programuvanni na GPU nakladni vitrati na stvorennya potokiv thread neznachni tomu mozhna stvoryuvati odin potik thread na kozhnu iteraciyu v cikli Porivnyannya zatrat chasu na operaciyu dodavannya vektoriv pri vikoristanni riznih pidhodiv ta arhitektur Risunok 5 3 Risunok 5 3 Porivnyannya zatrat chasu na operaciyu dodavannya vektoriv Kozhen vikonuvach element elementarnij procesor v modeli procesora SIMD obroblyaye odnakovu komandu z riznoyu chastinoyu naboru danih odnochasno Odna komanda instrukciya vidayetsya na vikonannya odnochasno bagatom ALP arifmetiko logichnij pristrij ALU Mayetsya na uvazi sho chislo ALU ye shirinoyu SIMD pristroyu SIMD procesori efektivni dlya daih paralelnih algoritmiv Voni zmenshuyut ob yem potoku upravlinnya ta komand aparatnogo zabezpechennya za rahunok ALU Aparatna realizaciya SIMD modeli Risunok 6 4 Risunok 6 4 Aparatna realizaciya SIMD modeli Odna komanda sho postupaye povinna buti vikonana na vsih elementarnih procesorah processing elements PE Odin potik thread vikonuyetsya na kozhnomu elementarnomu procesori processing element V prikladi dodavannya vektoriv SIMD pristrij z shirinoyu v chotiri mozhe vikonati chotiri iteraciyi ciklu vidrazu Vsi nayavni GPU bazuyutsya na SIMD aparatnomu vikonanni GPU aparatno neyavno vidobrazhaye kozhen SPMD potik thread v SIMD yadro Programistu ne potribno zvertati uvagu na pravilnist aparatnoyi skladovoyi SPMD modeli osnovnim tut ye produktivnist Cya model zapusku potokiv threads na SIMD aparatnomu zabezpechenni nazivayetsya SingleInstructionMultipleThreads SIMT Na zavershennya slid she raz zvernuti uvagu na vidminnosti pidtrimki paralelizmu na CPU ta GPU Na CPU aparatna pidtrimka atomarnih operacij vikoristovuyetsya dlya paralelizmu Atomarni operaciyi dozvolyayut danim buti zchitanimi i zapisanimi bez vtruchannya zi storoni inshogo potoku GPU rozglyadayetsya yak specializovanij obchislyuvalnij pristrij sho ye soprocesorom do CPU volodiye vlasnoyu pam yattyu volodiye mmozhlivistyu paralelnogo vikonannya velikoyi kilkosti okremih potokiv nitej Deyaki GPU pidtrimuyut zagalnosistemni atomarni operaciyi ale z velikim kompromisom u produktivnosti Zazvichaj kod yakij vimagaye globalnoyi sinhronizaciyi ne duzhe dobre pidhodit dlya GPU chi jogo slid reorganizuvati PrimitkiZhukov I Korochkin O Paralelni ta rozpodileni obchislennya K Kornijchuk 2005 226 s P Mehrotra and J Van Rosendale Programming distributed memory architectures In Advances in Languages and Compilers for Parallel Computing MIT Press 1991 Programmirovanie na parallelnyh obchislyuvalnih sistemah Per s angl Pod red R Bebba M Mir 1991 Literatura