Відмінності між версіями «Паралельні обчислювальні системи»
Tenatin (обговорення • внесок) |
|||
| (не показано 3 проміжні версії ще одного учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | ''' | + | '''Паралельні обчислення'''— це форма обчислень, в яких кілька дій проводяться одночасно. Грунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших. |
| − | + | [[Файл:1suchasn.jpg|thumb|IBM's Blue Gene/P масивно паралельний суперкомп'ютер]] | |
| − | + | Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях, але зацікавлення ним зросло тільки недавно, через фізичні обмеження зростання частоти. Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки, паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | Паралельні комп'ютери можуть бути грубо класифіковані згідно з рівнем, на якому апаратне забезпечення підтримує паралелізм: багатоядерність, багатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також кластери, MPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач. | ||
| − | + | Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних, бо паралелізм додає кілька нових класів потенційних помилок, серед яких є найпоширеніною стан гонитви. Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала. | ||
| − | + | = Передумови = | |
| − | + | ||
| − | + | Традиційно, програми пишуться для послідовних обчислень. Для розв'язку задачі придумують алгоритм, який реалізовується в вигляді послідовності інструкцій. Ці інструкції виконуються процесором одного комп'ютера. В кожен момент часу може виконуватись тільки одна інструкція, після завершення її виконання починається виконання наступної. | |
| − | + | ||
| − | + | ||
| + | З іншого боку, в паралельному програмуванні одночасно використовують кілька обчислювальних елементів для розв'язання однієї задачі. Це уможливлюється розбиттям задачі на підзадачі, кожна з яких може бути вирішена незалежно. Процесорні елементи бувають різними та включають різні ресурси, як наприклад один комп'ютер з багатьма процесорами, кілька комп'ютерів з'єднаних в мережу, спеціалізоване апаратне забезпечення, чи будь-яку комбінацію вищепереліченого. | ||
| − | ' | + | Приріст частоти був основною причиною збільшення продуктивності комп'ютерів з середини 1980-тих до 2004. Час роботи програми дорівнює числу інструкцій, помноженому на середній час потрібний на виконання інструкції. Тому збільшення частоти зменшує час виконання всіх процесорно-залежних (тих в яких основним ресурсом виступає час процесора) програм. |
| − | + | ||
| − | + | Тим не менш, споживана потужність чіпа задається рівнянням P = C \times V^2 \times F, де P — потужність, C — ємність що змінюється за один такт процесора (пропорційне числу транзисторів, чиї напруга на яких змінюються), V — напруга, а F — тактова частота. Збільшення частоти збільшує потужність що використовується процестором. Збільшення споживаної потужності призвело до того, що в травні 2004 Intel відмінило розробку процесорів Tejas та Jayhawk, на які зазвичай посилаються як на знак кінця збільшення частоти, як домінуючої парадигми в комп'ютерній архітектурі. | |
| − | + | Закон Мура — це емпіричне спостереження про те, що щільність транзисторів в мікропроцесорах подвоюється кожних 18-24 місяці. Незважаючи на проблеми зі споживанням енергії, та постійні передбачення кінця, закон Мура все ще працює. З кінцем зростання частоти, ці додаткові станзистори (що вже не збільшують частоту) будуть використовуватись щоб додати додаткове апаратне забезпечення для паралельних обчислень. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | === Закони Амдала та Густафсона === | ||
| + | [[Файл:2suchasn.png|thumb|Графічне зображення закону Амдала. Прискорення програми при розпаралелюванні залежить від того яку частину програми можна виконувати паралельно. Наприклад, якщо 90% програми можна виконувати паралельно, теоретичним максимумом прискорення при запуску її на паралельній машині буде десятикратне, незалежно від того, скільки процесорів використовується.]] | ||
| − | + | [[Файл:3suchasn.png|thumb|Припустимо що задача має дві незалежні частити, A та B. B займає 25% часу обчислень. Доклавши певних зусиль програміст може зробити цю частину в п'ять разів швидшою, але це ненабагато зменшить час всього обчислення. Тим не менш, можливо для того щоб прискорити частину A вдвічі потрібно менше зусиль, але це прискорить виконання всієї програми набагато сильніше ніж оптимізація B, попри те, що B можна оптимізувати сильніше.]] | |
| + | Оптимальним прискоренням від розпаралелювання могло б бути лінійне — збільшення кількості процесорів вдвічі має вдвічі скорочувати час виконання. Наступне збільшення кількості процесорів вдвічі мало б знову прискорювати програму. Тим не менш, лиш кілька паралельних алгоритмів досягають такого прискорення. Більшість з них мають майже лінійне прискорення при для малого числа процесорів, яке сповільнюється до константи при великій кількості обчислювальних елементів. | ||
| − | + | Потенційне прискорення алгоритму при збільшенні числа процесорів задається законом Амдала, що вперше був сформульований Жене Амдалем у 1960тих.[11] Він стверджує, що невелика частина програми що не піддається паралелізації обмежить загальне прискорення від розпаралелювання. Будь-яка велика математична чи інженерна задача зазвичай буде складатись з кількох частин що можуть виконуватись паралельно, та кількох частин що виконуються тільки послідовно. Цей зв'язок задається рівнянням: | |
| − | + | ||
| − | + | S = \frac{1}{1 - P} | |
| − | + | ||
| + | Де S — прискорення програми (як відношення до її початкового часу роботи), а P — частка яку можна виконувати паралельно. Якщо послідовна частина програми виконується 10% всього часу роботи, ми не можемо прискоритись більш ніж в 10 разів, незалежно від того скільки процесорів застосуємо. Це ставить верхню межу корисності збільшення кількості обчислювальних елементів. «Коли задача не може розпаралелюватись через обмеження послідовної частини, прикладання додаткових зусиль не має ніякого ефекту для розкладу. Щоб виносити дитину потрібно дев'ять місяців, незалежно від того, скільки жінок цим займаються.» | ||
| − | + | Закон Густафсона це інший комп'ютерний закон, що сильно пов'язаний з законом Амдала. Його можна сформулювати так: | |
| − | + | S(P) = P - \alpha(P-1) \, | |
| − | + | ||
| + | де P це кількість процесорів, S — прискорення, а \alpha нерозпаралелювана частина процесу.[13]. Закон Амдала базується на припущенні того, що задача має фіксований розмір, і що розмір послідовної частини незалежний від кількості процесорів, в той час як закон Густафсона не робить таких припущень. | ||
| − | + | === Залежності === | |
| + | Розуміння залежностей даних дуже важливе для розробки паралельних алгоритмів. Жодна програма не може працювати швидше ніж найдовший ланцюг залежних обчислень (відомий як критичний шлях), так як обчислення що залежать від попередніх обчислень в ланцюгу мають виконуватись одне за одним. Тим не менш, більшість алгоритмів не складаються лиш з довгого ланцюга залежних обчислень; зазвичай є шанси виконувати незалежні обчислення паралельно. | ||
| − | + | Хай P_i та P_j — два фрагменти програми. Умови Бернштейна[14] описують коли вони паралельні та можуть виконуватись паралельно. Для P_i, хай I_i — вхідні змінні, а O_i — вихідні. Для P_j — аналогічно. P_i та P_j незалежні, коли вони задовольняють такі умови: | |
| + | I_j \cap O_i = \varnothing, \, | ||
| + | I_i \cap O_j = \varnothing, \, | ||
| + | O_i \cap O_j = \varnothing. \, | ||
| − | + | Порушення першої умови створює залежність потоку, результат роботи першої частини використовується другою. Друга умова представляє антизалежність, коли друга частина програми переписує змінну, що потрібна першій програмі. Третя, та остання умова представляє залежність виводів: коли дві частини програми записують дані в одну й ту ж змінну, кінцевий результат має отримуватись від частини, що логічно виконується останньою.[15] | |
| + | |||
| + | Давайте придумаємо деякі функції, що демонструють кілька типів залежностей: | ||
| + | |||
| + | 1: function Dep(a, b) | ||
| + | 2: c := a·b | ||
| + | 3: d := 2·c | ||
| + | |||
| + | Оператор 3 в Dep(a,b) не може бути виконаним перед (чи навіть одночасно з) оператором 2, бо операція 3 використовує результат роботи операції 2. Вона порушує умову 1, тому маємо залежність потоку. | ||
| + | |||
| + | 1: function NoDep(a, b) | ||
| + | 2: c := a·b | ||
| + | 3: d := 2·b | ||
| + | 4: e := a+b | ||
| + | |||
| + | В цьому прикладі між операціями немає залежностей, тому вони можуть виконуватись паралельно. | ||
| + | |||
| + | Умови Бернштейна не дозволяють ділити пам'ять між різними процесами. Тому, потрібне примусове впорядкування доступу до даних, як семафори, бар'єри, та інші методи синхронізації. | ||
| + | |||
| + | === Стан гонитви, взаємне виключення, синхронізація та паралельне сповільнення === | ||
| + | |||
| + | Підзадачі в паралельній програмі часто називають нитями. Деякі паралельні архітектури використовують менші, легші версії нитей, що називаються волокнами, в той час як інші використовують більші версії, що називаються процесами. Тим не менш, «ниті» зазвичай приймаються як загальний термін для підзадач. Ниті часто потребують зміни деяких змінних що діляться між ними. Інструкції між двома програмами можуть розшаровуватись в будь-якому порядку. Наприклад, хай маємо таку програму: | ||
| + | Нить A Нить B | ||
| + | 1A: Прочитати змінну V 1B: Прочитати змінну V | ||
| + | 2A: Додати 1 до змінної V 2B: Додати 1 до змінної V | ||
| + | 3A: Записати назад у змінну V 3B: Записати назад у змінну V | ||
| + | |||
| + | Якщо інструкція 1B виконається між 1A та 3A, чи якщо інструкція 1A виконається між 1B та 3B, програма буде продукувати неправильні дані. Це відоме як стан гонитви. Програміст має використовувати замок (lock) щоб створити взаємне виключення. Замок — це конструкція мови програмування, що дозволяє одній ниті отримати контроль над змінною і запобігти читанню чи запису в цю змінну від інших нитей, аж поки ця змінна не буде розблокована. Нить що створила замок може вільно виконувати свою критичну секцію (секцію програми що вимагає ексклюзивного доступу до певної змінної), і розблокувати дані коли секція закінчиться. Тому, щоб гарантувати правильне виконання, програма дана вище може бути переписата з використанням замків: | ||
| + | Нить A Нить B | ||
| + | 1A: Замкнути змінну V 1B: Замкнути змінну V | ||
| + | 2A: Прочитати змінну V 2B: Прочитати змінну V | ||
| + | 3A: Додати 1 до змінної V 3B: Додати 1 до змінної V | ||
| + | 4A Записати назад у змінну V 4B: Записати назад у змінну V | ||
| + | 5A: Розблокувати змінну V 5B: Розблокувати змінну V | ||
| + | |||
| + | Одна нить успішно заблокує змінну V, поки інша буде замкнена — не зможе продовжити роботу, поки V не розблокується. Це гарантуватиме правильне виконання програми. Замки необхідні щоб гарантувати коректне виконання програми, але можуть сильно її сповільнити. | ||
| + | |||
| + | Блокування багатьох змінних з використанням неатомарних замків створює можливість взаємного блокування. Атомарний замок замикає всі змінні за раз. Якщо він не може замкнути всі з них, він не замикає жодної. Якщо дві ниті потребують замкнути однакові дві змінні використовуючи неатомарні замки, можливий випадок коли одна нить замикає одну змінну, а інша другу. В такому випадку жодна з нитей не може продовжувати роботу, що приводить до взаємного блокування. | ||
| + | |||
| + | Багато паралельних програм вимагають того, щоб їхні підзадачі виконувались синхронно. Це потребує використання бар'єра. Бар'єри зазвичай реалізуються з використанням програмного замка. Один клас алгоритмів, що відомі під назвою беззамкові та беззупинкові алгоритми (англ. lack-free and wait-free algorithms), уникають використання замків та бар'єрів. Правда такий підхід зазвичай важко реалізувати і вимагає правильно сконструйованих структур даних. | ||
| + | |||
| + | Не кожне розпаралелювання спричинює прискорення. Загалом, коли задача розбивається на більше та більше нитей, ті ниті витрачають все більше і більше часу на комунікації між собою. Зрештою, час на комунікацію переважає час, що витрачається на розв'язання чадачі, і подальше розпаралелювання (поділ на ще більшу кількість нитей) скоріше збільшує аніж зменшує протяжність часу потрібного щоб закінчити роботу. Це відоме як паралельне сповільненя. | ||
| + | |||
| + | === Дрібнозернистий, крупнозернистий, та приголомшливий паралелізм === | ||
| + | |||
| + | Програми часто класифікуються відповідно до того, як часто їхні підзадачі мають синхронізуватись чи спілкуватись один з одним. Програма проявляє дрібнозернистий паралелізм якщо її підзадачі мають обмінюватись даними багато разів на секунду; вона проявляє крупнозернистий паралелізм, якщо вони не мусять обмінюватись даними багато разів на секунду, і вона проявляє приголомшливий паралелізм, якщо вони рідко, чи взагалі ніколи не мають обмінюватись даними. Приголомшливо паралельні програми вважаються такими що розпаралелюються найлегше. | ||
| + | |||
| + | === Моделі узгодженості === | ||
| + | |||
| + | Паралельні мови програмування та паралельні комп'ютери мають мати модель узгодженості (також відому як модель пам'яті). Модель узгодженості описує правила проведення різноманітних операцій з пам'яттю, та що ми отримуємо в результаті цих операцій. | ||
| + | |||
| + | Однією з перших моделей узгодженості була модель послідовної щільності Леслі Лампорта. Послідовна узгодженість — це властивість паралельної програми давати такий самий результат що і її послідовний аналог. Конкретніше, програма послідовно узгоджена, якщо "… результат будь-якого запуску такий самий, як був би якщо операції на кожному окремому процесорі виконувались так, ніби вони виконуються в певній послідовності заданій програмою.[16] | ||
| + | |||
| + | Транзакційна пам'ять це типовий приклад моделі узгодженості. Транзакційна пам'ять взяла у теорії баз даних принцип атомарної транзакції та застосувала його при доступі до пам'яті. | ||
| + | |||
| + | Математично, ці моделі можуть представлятись кількома способами. Мережі Петрі, що були вперше представлені Карлом Адамом Петрі у 1962-гому, були ранніми спробами систематизувати правила узгодженості моделей. На їхній основі побудована теорія потоків даних, а їхня архітектура була створена, щоб реалізувати ідеї цієї теорії фізично. Починаючи з кінця 1970-х, були розроблені числення процесів, такі як Числення Систем, що Спілкуються та Послідовні Процеси, що Спілкуюються, щоб уможливити алгебраїчне обгрунтування систем складених з взаємодіючих компонентів. Новіші доповнення до сім'ї числень процесів, такі як π-числення, додали можливість обгрунтування динамічних топологій. Такі логіки як TLA+, та математичні моделі такі як траси та діаграми подій актора, також були розвинені щоб описати поведінку конкурентних систем. | ||
| + | |||
| + | === Таксономія Флінна === | ||
| + | |||
| + | Майкл Дж. Флінн створив одну з найперших класифікацій систем паралельних (та послідовних) комп'ютерів та програм, що нині відома як Таксономія Флінна. Флінн поділяв програми та комп'ютерами залежно від того чи вони використовували один чи багато потоків команд, та чи команди оперували одним чи багатьма множинами даних. | ||
| + | |||
| + | Клас single-instruction-single-data (SISD) еквівалентний цілковито послідовній програмі. Single-instruction-multiple-data (SIMD) еквівалентний виконанню однієї та тієї ж операції повторювано над великим масивом даних. Це зазвичай відбувається у задачах обробки сигналів. Клас Multiple-instruction-single-data (MISD) використовується рідко. Поки придумувались архітектури, що стосуються цього класу (як наприклад систолічні масиви), з'явилось лише кілька програм, що підпадають під цей клас. Multiple-instruction-multiple-data (MIMD) найтиповіші представники паралельних програм. | ||
| + | |||
| + | Згідно з Девідом Паттерсоном, та Джоном Хеннесі, «Деякі машини є гібридами цих категорій, щоправда ця класична модель вижила через те, що вона проста, легка для розуміння, та дає гарне перше наближення. Вона також, можливо через її зрозумілість — найпоширеніша схема.» | ||
| + | |||
| + | = Рівні паралелізму = | ||
| + | |||
| + | === Паралелізм бітового рівня === | ||
| + | |||
| + | З винайденням у 1970-тих технології створення надвеликих інтегральних схем прискорення в комп'ютерній архітектурі відбувалось з допомогою подвоєння розміру машинного слова — кількості інформації, яку комп'ютер може обробляти за один цикл.[18] Збільшення розміру слова зменшує кількість інструкцій необхідних виконати операцію над даними чий розмір більший ніж розмір вхідного слова. Наприклад коли восьмибітний процесор має додати два шістнадцятирозрядні числа, процесор має спочатку додати 8 біт нижчого розряду з кожного числа, використовуючи стандартну інструкцію додавання, потім додати 8 бітів вищого розряду, використовуючи інструкцію додавання з переносом та біт переносу від виконання попереднього додавання. Тому восьмибітний процесор потребує дві інструкції для виконання однієї операції, в той час як шістнадцятибітний лиш одну. | ||
| + | |||
| + | Історично, чотирьохрозрядні процесори були замінені на восьмирозрядні, потім на шістнадцятирозрядні, потім на 32-х розрядні. Ця тенденція припинилась з введенням тридцятидвохрозрядних процесорів, які стали стандартом для персональних комп'ютерів на два десятиліття. Аж поки недавно (2003—2004), з винайденням архітектури x86-64, не з'явились 64-x розрядні процесори. | ||
| + | |||
| + | === Паралелізм рівня інструкцій === | ||
| + | [[Файл:4suchasn.png|thumb|Стандартний п'ятикроковий конверйєр в машині RISC (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back)]] | ||
| + | Комп'ютерна програма, по суті, є потоком інструкцій, що виконуються процесором. Іноді ці інструкції можна перевпорядкувати, та об'єднати в групи, які потім виконувати паралельно, без зміни результату роботи програми, що відомо як паралелізм на рівні інструкцій. Такий підхід до збільшення продуктивності обчислень переважав з середини 80-тих до середини 90-тих. | ||
| + | |||
| + | Сучасні процесори мають багатоетапні конвеєри команд. Кожен етап конвеєра відповідає іншій дії, що виконує процесор. Процесор що має конвеєр з N-ступенями, може одночасно обробляти N інструкцій, кожну на іншій стадії обробки. Класичним прикладом процесора з конвеєром є процесор архітектури RISC, що має п'ять етапів: завантаження інструкції, декодування, виконання, доступ до пам'яті, та запис результату. Процесор Pentium 4 має конвеєр з 35 етапами. | ||
| + | |||
| + | На додачу до паралелізму на рівні інструкцій деякі процесори можуть виконувати більш ніж одну інструкцію за раз. Вони відомі як суперскалярні процесори. Інструкції групуються разом, якщо між ними не існує залежності даних. Щоб реалізувати паралелізм на рівні інструкцій використовують алгоритми Scoreboarding та Tomasulo algorithm (який аналогічний до попереднього, проте використовує перейменування регістрів). | ||
| + | |||
| + | === Паралелізм даних === | ||
| + | [[Файл:5suchasn.png|thumb|Суперскалярний п'ятиетапний конвеєрний мікропроцесор, що здатен виконувати дві інструкції за цикл. Він може зберігати дві інструкції на кожній стадії конвеєра, таким чином загалом виконуючи десять інструкцій водночас.]] | ||
| + | Паралелізм даних — це паралелізм властивий циклам програм, які фокусуються на доставці даних різним обчислювальним вузлам для паралельної обробки. "Розпаралелювання циклів часто приводить до подібних (не обов'язково ідентичних) послідовностей операцій, чи обчислення функцій над елементами великих структур даних. Багато наукових, та інженерних програм проявляють паралелізм даних. | ||
| + | |||
| + | Циклічна залежність — залежність ітерації циклу, від результатів попередньої, чи кількох попередніх ітерацій. Циклічні залежності перешкоджають розпаралелюванню циклів. Розглянемо псевдокод, що обчислює кілька перших чисел фібоначчі: | ||
| + | |||
| + | Такий цикл не може бути розпаралелений, бо CUR залежить від себе (PREV2), та PREV1, які обчислюються в кожній ітерації. Тому, кожна ітерація залежить від результатів попередньої, вони не можуть виконуватись паралельно. Коли розмір задачі стає більшим, кількість доступних для розпаралелювання даних зазвичай теж зростає. | ||
| + | |||
| + | === Паралелізм задач === | ||
| + | |||
| + | Паралелізм задач — характеристика паралельної програми, яка полягає в тому, що «цілком різні обчислення можуть виконуватись над одими, чи різними даними». Це відрізняє паралелізм задач від паралелізму даних, при якому одне і те ж обчислення виконується над одними і тими ж даними. Паралелізм задач, зазвичай не зростає зі зростанням розміру задачі. | ||
| + | |||
| + | = Апаратне забезпечення = | ||
| + | |||
| + | === Пам'ять та комунікації === | ||
| + | [[Файл:6suchasn.png|thumb|Структура архітектури Non-Uniform Memory Access (NUMA). Процесори в одній директорії можуть отримати доступ до пам'яті тієї директорії за менший час ніж в інших директоріях.]] | ||
| + | Основною пам'яттю в паралельному комп'ютері є як спільна пам'ять (розподілена між всіма обчислювальними елементами в одному адресному просторі), чи розподілена пам'ять (в якій кожен обчислювальний елемент має свій власний локальний адресний простір).[23] Розподілена пам'ять відсилається до того факту, що пам'ять є логічно поділеною, хоча часто натякає і на те, що вона також розділена і фізично. Розподілена спільна пам'ять та віртуалізація пам'яті комбінують обидва підходи, де обчислювальний елемент має свою власну локальну пам'ять, та доступ до пам'яті інших процесорів. Доступ до локальної пам'яті зазвичай швидший ніж доступ до нелокальної. | ||
| + | |||
| + | Комп'ютерні архітектури в яких доступ до кожного елементу основної пам'яті займає однаковий час та трафік називаються системами з однорідним доступом до пам'яті Uniform Memory Access (UMA). Зазвичай, це досягається тільки з спільною пам'яттю, в якій пам'ять не є фізично розподілена. Система що не володіє такою властивістю називається архітектурою з неоднорідним доступом до пам'яті (Non-Uniform Memory Access (NUMA)). Системи з розподіленою пам'яттю мають неоднорідний доступ до пам'яті. | ||
| + | |||
| + | Комп'ютерні системи використовують маленькі, швидкі, кеш-пам'яті, що розміщуються близько до процесора, та зберігають тимчасові копії змінних пам'яті (як у фізичному, так і логічному смислах). Паралельні комп'ютери мають проблеми з кешами, що можуть зберігати одні і ті ж значення в кількох місцях, що створює можливості для неправильного виконання обчислень. Такі комп'ютери вимагають систему когеренції кешу (en:cache coherency), яка слідкує за кешованими змінними та вчасно очищує їх, забезпечуючи корректне виконання програми. Пронюхування шини (en:Bus shiffing) один з найзагальніших методів слідкування за тим, які змінні використовуються та які треба зачистити. Конструювання великих, продуктивних систем когеренції кешу є складною задачею з галузі комп'ютерних архітектур. В результаті, архітектури з спільною пам'яттю не маштабуються так добре, як з розподіленою пам'яттю.[23] | ||
| + | |||
| + | Комунікація між процесорами, та між процесорами та пам'яттю може бути реалізована апаратно кількома способами, включаючи спільну (мультипортову чи Мультиплексну (en:Multiplexing)) пам'ять, матричний перемикач (en:crossbar switch), спільну шину чи мережа однієї з тисяч топологій, включаючи зірку, кільце, дерево, гіперкуб, жирний гіперкуб (гіперкуб з більш ніж одним процесором у вершині), чи n-вимірну сітку. | ||
| + | |||
| + | Паралельні комп'ютери що базуються на зв'язаних мережах мають мати певну маршрутизацію щоб забезпечити передавання повідомлень між елементами що не є зв'язані напряму. Медіа що використовується для зв'язку процесорів часто буває ієрархічним у великих багатопроцесорних машинах. | ||
| + | |||
| + | === Види паралельних комп'ютерів === | ||
| + | |||
| + | Паралельні комп'ютери можна грубо класифікувати за рівнем, на якому апаратне забезпечення підтримує паралелізм. Така класифікація майже аналогічна відстані між основними обчислювальними елементами. | ||
| + | |||
| + | '''Багатоядерні обчислення''' | ||
| + | |||
| + | Багатоядерний процесор — це процесор, що містить кілька ядер. Ці процесори відрізняються від суперскалярних процесорів, які можуть виконувати кілька інструкцій за такт з одного потоку інструкцій (ниті); на відміну від багатоядерних, що можуть за такт виконувати кілька інструкцій з різних нитей. Кожне ядро багатоядерного процесора потенційно може бути суперскалярним, тобто виконувати по кілька інструкцій з одної ниті. | ||
| + | |||
| + | Синхронна багатонитевість (найвідомішою з яких є технологія HyperThreading від Intel) була ранньою формою псевдо-багатоядерності. Процесор, що здатен до синхронної багатонитевості має лиш одне ядро, але при простоях ядра (наприклад під час очікування підвантаження даних в стек), використовує це ядро для роботи з іншою ниттю. Мікропроцесор Cell від IBM, що створений для використання в консолях Sony PlayStation 3 є іншим прикладом багатоядерного процесора. | ||
| + | |||
| + | '''Симетрична багатопроцесорність''' | ||
| + | |||
| + | Симетричний мультипроцесор (SMP) це комп'ютерна система з багатьма ідентичними процесорами, що поділяють пам'ять, та з'єднуються через шину.[24] Шинна суперечка (en:Bus contention перешкоджає маштабуванню шинних архітектур. В результаті, SMP зазвичай не містить більше 32-x процесорів.[25] «Через малий розмір процесорів, та значне зменшення вимог до пропускної здатності шини, що досягається завдяки великим кешам, такі симетричні багатопроцесорні системи є дуже рентабельними за умови, що існує достатня кількість пропускної здатності у пам'яті». | ||
| + | |||
| + | '''Розподілені обчислення''' | ||
| + | |||
| + | Розподілений комп'ютер (також відомий як мультипроцесор з розподіленою пам'яттю) це комп'ютерна система з розподіленою пам'яттю, у якій обчислювальні елементи з'єднані мережею. Розподілені комп'ютери чудово маштабуються. | ||
| + | |||
| + | '''Кластерні обчислення''' | ||
| + | |||
| + | Кластер — це група слабо зв'язаних комп'ютерів, що тісно співпрацюють, так що в певною мірою, вони можуть розглядатись як один комп'ютер. Кластери складаються з багатьох окремих машин, з'єднаних мережею. І хоча машини в кластері не мають бути симетричними, якщо вони не є, то це ускладнює балансування навантаження. Найпоширенішим типом кластера є кластер Beowulf, який є кластером, реалізованим на багатьох ідентичних фабричних комп'ютерів з'єданих в локальну мережу TCP/IP Ethernet]. Вперше технологію Beowulf розробили Томас Стерлінг та Дональд Беккер. Більшість суперкомп'ютерів зі списку TOP500 є кластерами. | ||
| + | |||
| + | '''Масово паралельні обчислення''' | ||
| + | |||
| + | Масивно паралельний процесор (MPP) це один комп'ютер з багатьма процесорами з'єднаними в мережу. MPP мають багато спільного з кластерами, та MPP мають спеціалізовані з'єднувальні мережі (тоді як кластери використовують стороннє обладнання для мережі). MPP також в основному більші ніж кластери, зазвичай мають «набагато більше ніж 100 процесорів». В MPP, «кожен процесор має свою власну пам'ять та копію операційної системи з програмами. Кожна підсистема спілкується з іншою через високошвидкісне з'єднання.» | ||
| + | Blue Gene/L, має рейтинг четвертого найшвидшого суперкомп'ютера у світі, згідно з рейтингом TOP500 11/2008. Blue Gene/L масивно паралельний процесор. | ||
| + | |||
| + | '''Обчислення Ґрід''' | ||
| + | |||
| + | Обчислення Ґрід — найбільш розподілена форма паралельних обчислень. Вона використовує для розв'язання задачі зв'язані мережею Інтернет комп'ютери. Через низьку швидкість передачі даних, та відносно великий час доступу до даних в Інтернет, ґрід обчислення проводять тільки для проголомшливо паралельних задач. Створена багато застосувань ґрід системам, найвідомішими з яких є SETI@home та Folding@Home[31] | ||
| + | |||
| + | Більшість програм ґрід обчислень використовують проміжне програмне забезпечення, що слугує інтерфейсом між операційною системою, та програмою, та керує ресурсами мережі, і стандартизує інтерфейс. Найпоширенішим програмним забезпеченням цього типу є Berkeley Open Infrastructure for Network Computing (BOINC). Часто програми ґрід обчислень користуються «запасними циклами», виконуючи обчислення під час простою системи. Тому їхні реалізації під виглядом екранних заставок доволі поширені. | ||
| + | |||
| + | '''Спеціальні паралельні комп'ютери''' | ||
| + | |||
| + | У галузі паралельних обчислень є спеціальні паралельні пристрої, що займають свої ніші. І хоча вони не є предметно-орієнтованими, та все ж вони зазвичай застосовуються лише для певних класів паралельних задач. | ||
Поточна версія на 11:57, 19 листопада 2013
Паралельні обчислення— це форма обчислень, в яких кілька дій проводяться одночасно. Грунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.
Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях, але зацікавлення ним зросло тільки недавно, через фізичні обмеження зростання частоти. Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки, паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів.
Паралельні комп'ютери можуть бути грубо класифіковані згідно з рівнем, на якому апаратне забезпечення підтримує паралелізм: багатоядерність, багатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також кластери, MPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач.
Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних, бо паралелізм додає кілька нових класів потенційних помилок, серед яких є найпоширеніною стан гонитви. Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм.
Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала.
Передумови
Традиційно, програми пишуться для послідовних обчислень. Для розв'язку задачі придумують алгоритм, який реалізовується в вигляді послідовності інструкцій. Ці інструкції виконуються процесором одного комп'ютера. В кожен момент часу може виконуватись тільки одна інструкція, після завершення її виконання починається виконання наступної.
З іншого боку, в паралельному програмуванні одночасно використовують кілька обчислювальних елементів для розв'язання однієї задачі. Це уможливлюється розбиттям задачі на підзадачі, кожна з яких може бути вирішена незалежно. Процесорні елементи бувають різними та включають різні ресурси, як наприклад один комп'ютер з багатьма процесорами, кілька комп'ютерів з'єднаних в мережу, спеціалізоване апаратне забезпечення, чи будь-яку комбінацію вищепереліченого.
Приріст частоти був основною причиною збільшення продуктивності комп'ютерів з середини 1980-тих до 2004. Час роботи програми дорівнює числу інструкцій, помноженому на середній час потрібний на виконання інструкції. Тому збільшення частоти зменшує час виконання всіх процесорно-залежних (тих в яких основним ресурсом виступає час процесора) програм.
Тим не менш, споживана потужність чіпа задається рівнянням P = C \times V^2 \times F, де P — потужність, C — ємність що змінюється за один такт процесора (пропорційне числу транзисторів, чиї напруга на яких змінюються), V — напруга, а F — тактова частота. Збільшення частоти збільшує потужність що використовується процестором. Збільшення споживаної потужності призвело до того, що в травні 2004 Intel відмінило розробку процесорів Tejas та Jayhawk, на які зазвичай посилаються як на знак кінця збільшення частоти, як домінуючої парадигми в комп'ютерній архітектурі.
Закон Мура — це емпіричне спостереження про те, що щільність транзисторів в мікропроцесорах подвоюється кожних 18-24 місяці. Незважаючи на проблеми зі споживанням енергії, та постійні передбачення кінця, закон Мура все ще працює. З кінцем зростання частоти, ці додаткові станзистори (що вже не збільшують частоту) будуть використовуватись щоб додати додаткове апаратне забезпечення для паралельних обчислень.
Закони Амдала та Густафсона
Оптимальним прискоренням від розпаралелювання могло б бути лінійне — збільшення кількості процесорів вдвічі має вдвічі скорочувати час виконання. Наступне збільшення кількості процесорів вдвічі мало б знову прискорювати програму. Тим не менш, лиш кілька паралельних алгоритмів досягають такого прискорення. Більшість з них мають майже лінійне прискорення при для малого числа процесорів, яке сповільнюється до константи при великій кількості обчислювальних елементів.
Потенційне прискорення алгоритму при збільшенні числа процесорів задається законом Амдала, що вперше був сформульований Жене Амдалем у 1960тих.[11] Він стверджує, що невелика частина програми що не піддається паралелізації обмежить загальне прискорення від розпаралелювання. Будь-яка велика математична чи інженерна задача зазвичай буде складатись з кількох частин що можуть виконуватись паралельно, та кількох частин що виконуються тільки послідовно. Цей зв'язок задається рівнянням:
S = \frac{1}{1 - P}
Де S — прискорення програми (як відношення до її початкового часу роботи), а P — частка яку можна виконувати паралельно. Якщо послідовна частина програми виконується 10% всього часу роботи, ми не можемо прискоритись більш ніж в 10 разів, незалежно від того скільки процесорів застосуємо. Це ставить верхню межу корисності збільшення кількості обчислювальних елементів. «Коли задача не може розпаралелюватись через обмеження послідовної частини, прикладання додаткових зусиль не має ніякого ефекту для розкладу. Щоб виносити дитину потрібно дев'ять місяців, незалежно від того, скільки жінок цим займаються.»
Закон Густафсона це інший комп'ютерний закон, що сильно пов'язаний з законом Амдала. Його можна сформулювати так:
S(P) = P - \alpha(P-1) \,
де P це кількість процесорів, S — прискорення, а \alpha нерозпаралелювана частина процесу.[13]. Закон Амдала базується на припущенні того, що задача має фіксований розмір, і що розмір послідовної частини незалежний від кількості процесорів, в той час як закон Густафсона не робить таких припущень.
Залежності
Розуміння залежностей даних дуже важливе для розробки паралельних алгоритмів. Жодна програма не може працювати швидше ніж найдовший ланцюг залежних обчислень (відомий як критичний шлях), так як обчислення що залежать від попередніх обчислень в ланцюгу мають виконуватись одне за одним. Тим не менш, більшість алгоритмів не складаються лиш з довгого ланцюга залежних обчислень; зазвичай є шанси виконувати незалежні обчислення паралельно.
Хай P_i та P_j — два фрагменти програми. Умови Бернштейна[14] описують коли вони паралельні та можуть виконуватись паралельно. Для P_i, хай I_i — вхідні змінні, а O_i — вихідні. Для P_j — аналогічно. P_i та P_j незалежні, коли вони задовольняють такі умови:
I_j \cap O_i = \varnothing, \, I_i \cap O_j = \varnothing, \, O_i \cap O_j = \varnothing. \,
Порушення першої умови створює залежність потоку, результат роботи першої частини використовується другою. Друга умова представляє антизалежність, коли друга частина програми переписує змінну, що потрібна першій програмі. Третя, та остання умова представляє залежність виводів: коли дві частини програми записують дані в одну й ту ж змінну, кінцевий результат має отримуватись від частини, що логічно виконується останньою.[15]
Давайте придумаємо деякі функції, що демонструють кілька типів залежностей:
1: function Dep(a, b) 2: c := a·b 3: d := 2·c
Оператор 3 в Dep(a,b) не може бути виконаним перед (чи навіть одночасно з) оператором 2, бо операція 3 використовує результат роботи операції 2. Вона порушує умову 1, тому маємо залежність потоку.
1: function NoDep(a, b) 2: c := a·b 3: d := 2·b 4: e := a+b
В цьому прикладі між операціями немає залежностей, тому вони можуть виконуватись паралельно.
Умови Бернштейна не дозволяють ділити пам'ять між різними процесами. Тому, потрібне примусове впорядкування доступу до даних, як семафори, бар'єри, та інші методи синхронізації.
Стан гонитви, взаємне виключення, синхронізація та паралельне сповільнення
Підзадачі в паралельній програмі часто називають нитями. Деякі паралельні архітектури використовують менші, легші версії нитей, що називаються волокнами, в той час як інші використовують більші версії, що називаються процесами. Тим не менш, «ниті» зазвичай приймаються як загальний термін для підзадач. Ниті часто потребують зміни деяких змінних що діляться між ними. Інструкції між двома програмами можуть розшаровуватись в будь-якому порядку. Наприклад, хай маємо таку програму: Нить A Нить B 1A: Прочитати змінну V 1B: Прочитати змінну V 2A: Додати 1 до змінної V 2B: Додати 1 до змінної V 3A: Записати назад у змінну V 3B: Записати назад у змінну V
Якщо інструкція 1B виконається між 1A та 3A, чи якщо інструкція 1A виконається між 1B та 3B, програма буде продукувати неправильні дані. Це відоме як стан гонитви. Програміст має використовувати замок (lock) щоб створити взаємне виключення. Замок — це конструкція мови програмування, що дозволяє одній ниті отримати контроль над змінною і запобігти читанню чи запису в цю змінну від інших нитей, аж поки ця змінна не буде розблокована. Нить що створила замок може вільно виконувати свою критичну секцію (секцію програми що вимагає ексклюзивного доступу до певної змінної), і розблокувати дані коли секція закінчиться. Тому, щоб гарантувати правильне виконання, програма дана вище може бути переписата з використанням замків: Нить A Нить B 1A: Замкнути змінну V 1B: Замкнути змінну V 2A: Прочитати змінну V 2B: Прочитати змінну V 3A: Додати 1 до змінної V 3B: Додати 1 до змінної V 4A Записати назад у змінну V 4B: Записати назад у змінну V 5A: Розблокувати змінну V 5B: Розблокувати змінну V
Одна нить успішно заблокує змінну V, поки інша буде замкнена — не зможе продовжити роботу, поки V не розблокується. Це гарантуватиме правильне виконання програми. Замки необхідні щоб гарантувати коректне виконання програми, але можуть сильно її сповільнити.
Блокування багатьох змінних з використанням неатомарних замків створює можливість взаємного блокування. Атомарний замок замикає всі змінні за раз. Якщо він не може замкнути всі з них, він не замикає жодної. Якщо дві ниті потребують замкнути однакові дві змінні використовуючи неатомарні замки, можливий випадок коли одна нить замикає одну змінну, а інша другу. В такому випадку жодна з нитей не може продовжувати роботу, що приводить до взаємного блокування.
Багато паралельних програм вимагають того, щоб їхні підзадачі виконувались синхронно. Це потребує використання бар'єра. Бар'єри зазвичай реалізуються з використанням програмного замка. Один клас алгоритмів, що відомі під назвою беззамкові та беззупинкові алгоритми (англ. lack-free and wait-free algorithms), уникають використання замків та бар'єрів. Правда такий підхід зазвичай важко реалізувати і вимагає правильно сконструйованих структур даних.
Не кожне розпаралелювання спричинює прискорення. Загалом, коли задача розбивається на більше та більше нитей, ті ниті витрачають все більше і більше часу на комунікації між собою. Зрештою, час на комунікацію переважає час, що витрачається на розв'язання чадачі, і подальше розпаралелювання (поділ на ще більшу кількість нитей) скоріше збільшує аніж зменшує протяжність часу потрібного щоб закінчити роботу. Це відоме як паралельне сповільненя.
Дрібнозернистий, крупнозернистий, та приголомшливий паралелізм
Програми часто класифікуються відповідно до того, як часто їхні підзадачі мають синхронізуватись чи спілкуватись один з одним. Програма проявляє дрібнозернистий паралелізм якщо її підзадачі мають обмінюватись даними багато разів на секунду; вона проявляє крупнозернистий паралелізм, якщо вони не мусять обмінюватись даними багато разів на секунду, і вона проявляє приголомшливий паралелізм, якщо вони рідко, чи взагалі ніколи не мають обмінюватись даними. Приголомшливо паралельні програми вважаються такими що розпаралелюються найлегше.
Моделі узгодженості
Паралельні мови програмування та паралельні комп'ютери мають мати модель узгодженості (також відому як модель пам'яті). Модель узгодженості описує правила проведення різноманітних операцій з пам'яттю, та що ми отримуємо в результаті цих операцій.
Однією з перших моделей узгодженості була модель послідовної щільності Леслі Лампорта. Послідовна узгодженість — це властивість паралельної програми давати такий самий результат що і її послідовний аналог. Конкретніше, програма послідовно узгоджена, якщо "… результат будь-якого запуску такий самий, як був би якщо операції на кожному окремому процесорі виконувались так, ніби вони виконуються в певній послідовності заданій програмою.[16]
Транзакційна пам'ять це типовий приклад моделі узгодженості. Транзакційна пам'ять взяла у теорії баз даних принцип атомарної транзакції та застосувала його при доступі до пам'яті.
Математично, ці моделі можуть представлятись кількома способами. Мережі Петрі, що були вперше представлені Карлом Адамом Петрі у 1962-гому, були ранніми спробами систематизувати правила узгодженості моделей. На їхній основі побудована теорія потоків даних, а їхня архітектура була створена, щоб реалізувати ідеї цієї теорії фізично. Починаючи з кінця 1970-х, були розроблені числення процесів, такі як Числення Систем, що Спілкуються та Послідовні Процеси, що Спілкуюються, щоб уможливити алгебраїчне обгрунтування систем складених з взаємодіючих компонентів. Новіші доповнення до сім'ї числень процесів, такі як π-числення, додали можливість обгрунтування динамічних топологій. Такі логіки як TLA+, та математичні моделі такі як траси та діаграми подій актора, також були розвинені щоб описати поведінку конкурентних систем.
Таксономія Флінна
Майкл Дж. Флінн створив одну з найперших класифікацій систем паралельних (та послідовних) комп'ютерів та програм, що нині відома як Таксономія Флінна. Флінн поділяв програми та комп'ютерами залежно від того чи вони використовували один чи багато потоків команд, та чи команди оперували одним чи багатьма множинами даних.
Клас single-instruction-single-data (SISD) еквівалентний цілковито послідовній програмі. Single-instruction-multiple-data (SIMD) еквівалентний виконанню однієї та тієї ж операції повторювано над великим масивом даних. Це зазвичай відбувається у задачах обробки сигналів. Клас Multiple-instruction-single-data (MISD) використовується рідко. Поки придумувались архітектури, що стосуються цього класу (як наприклад систолічні масиви), з'явилось лише кілька програм, що підпадають під цей клас. Multiple-instruction-multiple-data (MIMD) найтиповіші представники паралельних програм.
Згідно з Девідом Паттерсоном, та Джоном Хеннесі, «Деякі машини є гібридами цих категорій, щоправда ця класична модель вижила через те, що вона проста, легка для розуміння, та дає гарне перше наближення. Вона також, можливо через її зрозумілість — найпоширеніша схема.»
Рівні паралелізму
Паралелізм бітового рівня
З винайденням у 1970-тих технології створення надвеликих інтегральних схем прискорення в комп'ютерній архітектурі відбувалось з допомогою подвоєння розміру машинного слова — кількості інформації, яку комп'ютер може обробляти за один цикл.[18] Збільшення розміру слова зменшує кількість інструкцій необхідних виконати операцію над даними чий розмір більший ніж розмір вхідного слова. Наприклад коли восьмибітний процесор має додати два шістнадцятирозрядні числа, процесор має спочатку додати 8 біт нижчого розряду з кожного числа, використовуючи стандартну інструкцію додавання, потім додати 8 бітів вищого розряду, використовуючи інструкцію додавання з переносом та біт переносу від виконання попереднього додавання. Тому восьмибітний процесор потребує дві інструкції для виконання однієї операції, в той час як шістнадцятибітний лиш одну.
Історично, чотирьохрозрядні процесори були замінені на восьмирозрядні, потім на шістнадцятирозрядні, потім на 32-х розрядні. Ця тенденція припинилась з введенням тридцятидвохрозрядних процесорів, які стали стандартом для персональних комп'ютерів на два десятиліття. Аж поки недавно (2003—2004), з винайденням архітектури x86-64, не з'явились 64-x розрядні процесори.
Паралелізм рівня інструкцій
Комп'ютерна програма, по суті, є потоком інструкцій, що виконуються процесором. Іноді ці інструкції можна перевпорядкувати, та об'єднати в групи, які потім виконувати паралельно, без зміни результату роботи програми, що відомо як паралелізм на рівні інструкцій. Такий підхід до збільшення продуктивності обчислень переважав з середини 80-тих до середини 90-тих.
Сучасні процесори мають багатоетапні конвеєри команд. Кожен етап конвеєра відповідає іншій дії, що виконує процесор. Процесор що має конвеєр з N-ступенями, може одночасно обробляти N інструкцій, кожну на іншій стадії обробки. Класичним прикладом процесора з конвеєром є процесор архітектури RISC, що має п'ять етапів: завантаження інструкції, декодування, виконання, доступ до пам'яті, та запис результату. Процесор Pentium 4 має конвеєр з 35 етапами.
На додачу до паралелізму на рівні інструкцій деякі процесори можуть виконувати більш ніж одну інструкцію за раз. Вони відомі як суперскалярні процесори. Інструкції групуються разом, якщо між ними не існує залежності даних. Щоб реалізувати паралелізм на рівні інструкцій використовують алгоритми Scoreboarding та Tomasulo algorithm (який аналогічний до попереднього, проте використовує перейменування регістрів).
Паралелізм даних
Паралелізм даних — це паралелізм властивий циклам програм, які фокусуються на доставці даних різним обчислювальним вузлам для паралельної обробки. "Розпаралелювання циклів часто приводить до подібних (не обов'язково ідентичних) послідовностей операцій, чи обчислення функцій над елементами великих структур даних. Багато наукових, та інженерних програм проявляють паралелізм даних.
Циклічна залежність — залежність ітерації циклу, від результатів попередньої, чи кількох попередніх ітерацій. Циклічні залежності перешкоджають розпаралелюванню циклів. Розглянемо псевдокод, що обчислює кілька перших чисел фібоначчі:
Такий цикл не може бути розпаралелений, бо CUR залежить від себе (PREV2), та PREV1, які обчислюються в кожній ітерації. Тому, кожна ітерація залежить від результатів попередньої, вони не можуть виконуватись паралельно. Коли розмір задачі стає більшим, кількість доступних для розпаралелювання даних зазвичай теж зростає.
Паралелізм задач
Паралелізм задач — характеристика паралельної програми, яка полягає в тому, що «цілком різні обчислення можуть виконуватись над одими, чи різними даними». Це відрізняє паралелізм задач від паралелізму даних, при якому одне і те ж обчислення виконується над одними і тими ж даними. Паралелізм задач, зазвичай не зростає зі зростанням розміру задачі.
Апаратне забезпечення
Пам'ять та комунікації
Основною пам'яттю в паралельному комп'ютері є як спільна пам'ять (розподілена між всіма обчислювальними елементами в одному адресному просторі), чи розподілена пам'ять (в якій кожен обчислювальний елемент має свій власний локальний адресний простір).[23] Розподілена пам'ять відсилається до того факту, що пам'ять є логічно поділеною, хоча часто натякає і на те, що вона також розділена і фізично. Розподілена спільна пам'ять та віртуалізація пам'яті комбінують обидва підходи, де обчислювальний елемент має свою власну локальну пам'ять, та доступ до пам'яті інших процесорів. Доступ до локальної пам'яті зазвичай швидший ніж доступ до нелокальної.
Комп'ютерні архітектури в яких доступ до кожного елементу основної пам'яті займає однаковий час та трафік називаються системами з однорідним доступом до пам'яті Uniform Memory Access (UMA). Зазвичай, це досягається тільки з спільною пам'яттю, в якій пам'ять не є фізично розподілена. Система що не володіє такою властивістю називається архітектурою з неоднорідним доступом до пам'яті (Non-Uniform Memory Access (NUMA)). Системи з розподіленою пам'яттю мають неоднорідний доступ до пам'яті.
Комп'ютерні системи використовують маленькі, швидкі, кеш-пам'яті, що розміщуються близько до процесора, та зберігають тимчасові копії змінних пам'яті (як у фізичному, так і логічному смислах). Паралельні комп'ютери мають проблеми з кешами, що можуть зберігати одні і ті ж значення в кількох місцях, що створює можливості для неправильного виконання обчислень. Такі комп'ютери вимагають систему когеренції кешу (en:cache coherency), яка слідкує за кешованими змінними та вчасно очищує їх, забезпечуючи корректне виконання програми. Пронюхування шини (en:Bus shiffing) один з найзагальніших методів слідкування за тим, які змінні використовуються та які треба зачистити. Конструювання великих, продуктивних систем когеренції кешу є складною задачею з галузі комп'ютерних архітектур. В результаті, архітектури з спільною пам'яттю не маштабуються так добре, як з розподіленою пам'яттю.[23]
Комунікація між процесорами, та між процесорами та пам'яттю може бути реалізована апаратно кількома способами, включаючи спільну (мультипортову чи Мультиплексну (en:Multiplexing)) пам'ять, матричний перемикач (en:crossbar switch), спільну шину чи мережа однієї з тисяч топологій, включаючи зірку, кільце, дерево, гіперкуб, жирний гіперкуб (гіперкуб з більш ніж одним процесором у вершині), чи n-вимірну сітку.
Паралельні комп'ютери що базуються на зв'язаних мережах мають мати певну маршрутизацію щоб забезпечити передавання повідомлень між елементами що не є зв'язані напряму. Медіа що використовується для зв'язку процесорів часто буває ієрархічним у великих багатопроцесорних машинах.
Види паралельних комп'ютерів
Паралельні комп'ютери можна грубо класифікувати за рівнем, на якому апаратне забезпечення підтримує паралелізм. Така класифікація майже аналогічна відстані між основними обчислювальними елементами.
Багатоядерні обчислення
Багатоядерний процесор — це процесор, що містить кілька ядер. Ці процесори відрізняються від суперскалярних процесорів, які можуть виконувати кілька інструкцій за такт з одного потоку інструкцій (ниті); на відміну від багатоядерних, що можуть за такт виконувати кілька інструкцій з різних нитей. Кожне ядро багатоядерного процесора потенційно може бути суперскалярним, тобто виконувати по кілька інструкцій з одної ниті.
Синхронна багатонитевість (найвідомішою з яких є технологія HyperThreading від Intel) була ранньою формою псевдо-багатоядерності. Процесор, що здатен до синхронної багатонитевості має лиш одне ядро, але при простоях ядра (наприклад під час очікування підвантаження даних в стек), використовує це ядро для роботи з іншою ниттю. Мікропроцесор Cell від IBM, що створений для використання в консолях Sony PlayStation 3 є іншим прикладом багатоядерного процесора.
Симетрична багатопроцесорність
Симетричний мультипроцесор (SMP) це комп'ютерна система з багатьма ідентичними процесорами, що поділяють пам'ять, та з'єднуються через шину.[24] Шинна суперечка (en:Bus contention перешкоджає маштабуванню шинних архітектур. В результаті, SMP зазвичай не містить більше 32-x процесорів.[25] «Через малий розмір процесорів, та значне зменшення вимог до пропускної здатності шини, що досягається завдяки великим кешам, такі симетричні багатопроцесорні системи є дуже рентабельними за умови, що існує достатня кількість пропускної здатності у пам'яті».
Розподілені обчислення
Розподілений комп'ютер (також відомий як мультипроцесор з розподіленою пам'яттю) це комп'ютерна система з розподіленою пам'яттю, у якій обчислювальні елементи з'єднані мережею. Розподілені комп'ютери чудово маштабуються.
Кластерні обчислення
Кластер — це група слабо зв'язаних комп'ютерів, що тісно співпрацюють, так що в певною мірою, вони можуть розглядатись як один комп'ютер. Кластери складаються з багатьох окремих машин, з'єднаних мережею. І хоча машини в кластері не мають бути симетричними, якщо вони не є, то це ускладнює балансування навантаження. Найпоширенішим типом кластера є кластер Beowulf, який є кластером, реалізованим на багатьох ідентичних фабричних комп'ютерів з'єданих в локальну мережу TCP/IP Ethernet]. Вперше технологію Beowulf розробили Томас Стерлінг та Дональд Беккер. Більшість суперкомп'ютерів зі списку TOP500 є кластерами.
Масово паралельні обчислення
Масивно паралельний процесор (MPP) це один комп'ютер з багатьма процесорами з'єднаними в мережу. MPP мають багато спільного з кластерами, та MPP мають спеціалізовані з'єднувальні мережі (тоді як кластери використовують стороннє обладнання для мережі). MPP також в основному більші ніж кластери, зазвичай мають «набагато більше ніж 100 процесорів». В MPP, «кожен процесор має свою власну пам'ять та копію операційної системи з програмами. Кожна підсистема спілкується з іншою через високошвидкісне з'єднання.» Blue Gene/L, має рейтинг четвертого найшвидшого суперкомп'ютера у світі, згідно з рейтингом TOP500 11/2008. Blue Gene/L масивно паралельний процесор.
Обчислення Ґрід
Обчислення Ґрід — найбільш розподілена форма паралельних обчислень. Вона використовує для розв'язання задачі зв'язані мережею Інтернет комп'ютери. Через низьку швидкість передачі даних, та відносно великий час доступу до даних в Інтернет, ґрід обчислення проводять тільки для проголомшливо паралельних задач. Створена багато застосувань ґрід системам, найвідомішими з яких є SETI@home та Folding@Home[31]
Більшість програм ґрід обчислень використовують проміжне програмне забезпечення, що слугує інтерфейсом між операційною системою, та програмою, та керує ресурсами мережі, і стандартизує інтерфейс. Найпоширенішим програмним забезпеченням цього типу є Berkeley Open Infrastructure for Network Computing (BOINC). Часто програми ґрід обчислень користуються «запасними циклами», виконуючи обчислення під час простою системи. Тому їхні реалізації під виглядом екранних заставок доволі поширені.
Спеціальні паралельні комп'ютери
У галузі паралельних обчислень є спеціальні паралельні пристрої, що займають свої ніші. І хоча вони не є предметно-орієнтованими, та все ж вони зазвичай застосовуються лише для певних класів паралельних задач.
