Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасноAlmasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA.. Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.
Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях, але зацікавлення ним зросло тільки недавно, через фізичні обмеження зростання частоти.S.V. Adve et al. (Листопад 2008). «Parallel Computing Research at Illinois: The UPCRC Agenda» (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. «Основні технології збільшення продуктивності обчислень — збільшення частоти тактового генератора, та хитріші, проте відповідно набагато складніші архітектури, сьогодні стикаються з так званою стіною потужності. Комп'ютерна промисловість прийняла факт, що майбутні зростання продуктивності обчислень будуть пов'язані зі зростанням кількості процесорів (чи ядер), аніж зі спробами змусити одне ядро працювати швидше».. Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки,Asanovic et al. Старий принцип економії: Електрика безплатна, транзистори дорогі. Новий принцип економії: електрика дорога, але транзистори «безплатні». паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів.Asanovic, Krste et al. (Грудень 18, 2006). «The Landscape of Parallel Computing Research: A View from Berkeley» (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. «Старий принцип вирішення проблем: Збільшення тактової частоти — основний метод покращення продуктивності. Новий принцип: Збільшення паралелізму це основний метод збільшення продуктивності процесора… Навіть представники Intel, компанії, що зазвичай асоціюється з позицією — „чим більша частота тим краще“, попереджують, що традиційні підходи до збільшення продуктивності через збільшення тактової частоти досягли своєї межі.»
Паралельні комп'ютери можуть бути грубо класифіковані згідно з рівнем, на якому апаратне забезпечення підтримує паралелізм: багатоядерність, багатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також кластери, MPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач.
Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовнихPatterson, David A. and John L. Hennessy (1998). Computer Organization and Design, Second Edition, Morgan Kaufmann Publishers, p. 715. ISBN 1-55860-428-6., бо паралелізм додає кілька нових класів потенційних помилок, серед яких найпоширенішою є стан гонитви. Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм.
Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала.
Передумови Колись паралельне програмування було справою тільки тих одинаків, яких цікавили завдання для великих суперкомп'ютерів. Але тепер, коли звичайні додатки почали працювати на багатоядерних процесорах, паралельне програмування швидко стає технологією, яку повинен освоїти і вміти застосовувати будь-який професійний розробник ПЗ. Паралельне програмування може бути складним, але його легше зрозуміти, якщо вважати не «важким», а просто «трохи іншим».
Традиційно, програми пишуться для послідовних обчислень. Для розв'язку задачі придумують алгоритм, який реалізовується в вигляді послідовності інструкцій. Ці інструкції виконуються одним процесором комп'ютера. У кожен момент часу може виконуватись тільки одна інструкція, після завершення її виконання починається виконання наступної.
З іншого боку, в паралельному програмуванні одночасно використовують кілька обчислювальних елементів для розв'язання однієї задачі. Це уможливлюється розбиттям задачі на підзадачі, кожна з яких може бути вирішена незалежно. Процесорні елементи бувають різними та включають різні ресурси, як наприклад один комп'ютер з багатьма процесорами, кілька з'єднаних у мережу комп'ютерів, спеціалізоване апаратне забезпечення, чи будь-яку комбінацію перерахованого вище.
Приріст частоти був основним чинником збільшення продуктивності комп'ютерів з середини 1980-тих до 2004. Час роботи програми дорівнює числу інструкцій, помноженому на середній час виконання інструкції. Тому збільшення частоти зменшує час виконання всіх процесорно-залежних (коли основним ресурсом виступає час процесора) програм.Hennessy, John L. and David A. Patterson (2002). Computer Architecture: A Quantitative Approach. 3rd edition, Morgan Kaufmann, p. 43. ISBN 1-55860-724-2.
Тим не менш, споживана потужність чипу задається рівнянням , де — потужність, — напруга живлення, — ємність, що перезаряджається за один такт процесора (пропорційна числу транзисторів, які перемикаються у цьому такті), а — тактова частота.Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. ISBN 0-13-178609-1. Збільшення частоти збільшує потужність, що використовується процесором. Збільшення споживаної потужності призвело до того, що в травні 2004 Intel відмінило розробку процесорів , на які зазвичай посилаються як на знак кінця збільшення частоти, як домінуючої парадигми в комп'ютерній архітектурі.Flynn, Laurie J. «Intel Halts Development of 2 New Microprocessors». The New York Times, May 8, 2004. Retrieved on April 22, 2008.
Закон Мура — це емпіричне спостереження про те, що щільність транзисторів в мікропроцесорах подвоюється кожних 18-24 місяці. Незважаючи на проблеми зі споживанням енергії та постійні передбачення кінця, закон Мура все ще працює. З кінцем зростання частоти, ці додаткові транзистори (що вже не збільшують частоту) будуть використовуватись щоб додати додаткове апаратне забезпечення для паралельних обчислень.
Закони Амдала та Густафсона
Оптимальним прискоренням від розпаралелювання могло б бути лінійне — збільшення кількості процесорів вдвічі має вдвічі скорочувати час виконання. Наступне збільшення кількості процесорів вдвічі мало б знову прискорювати програму. Тим не менш, лиш кілька паралельних алгоритмів досягають такого прискорення. Більшість з них мають майже лінійне прискорення при невеликій кількості процесорів, яке сповільнюється до константи при великій кількості обчислювальних елементів.
Потенційне прискорення алгоритму при збільшенні числа процесорів задається законом Амдала, що вперше був сформульований Джином Амдалем у 1960-тих.Amdahl, G. (April 1967) «The validity of the single processor approach to achieving large-scale computing capabilities». In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, pp. 483-85. Він стверджує, що невелика частина програми що не піддається паралелізації обмежить загальне прискорення від розпаралелювання. Будь-яка велика математична чи інженерна задача зазвичай буде складатись з кількох частин що можуть виконуватись паралельно, та кількох частин що виконуються тільки послідовно. Цей зв'язок задається рівнянням:
Де — прискорення програми (як відношення до її початкового часу роботи), а — частка яку можна виконувати паралельно. Якщо послідовна частина програми виконується 10 % всього часу роботи, ми не можемо прискоритись більш ніж в 10 разів, незалежно від того скільки процесорів застосуємо. Це ставить верхню межу корисності збільшення кількості обчислювальних елементів. «Коли задача не може розпаралелюватись через обмеження послідовної частини, прикладання додаткових зусиль не має ніякого ефекту для розкладу. Щоб виносити дитину потрібно дев'ять місяців, незалежно від того, скільки жінок цим займаються.»Фред Брукс Міфічний людино-місяць. Розділ 2 — Міфічний людино-місяць. ISBN 0-201-83595-9
Закон Густафсона це інший комп'ютерний закон, що сильно пов'язаний з законом Амдала. Його можна сформулювати так:
де це кількість процесорів, — прискорення, а нерозпаралелювана частина процесу.Reevaluating Amdahl's Law (1988). Communications of the ACM 31(5), pp. 532-33.. Закон Амдала базується на припущенні того, що задача має фіксований розмір, і що розмір послідовної частини незалежний від кількості процесорів, в той час як закон Густафсона не робить таких припущень.
Залежності Розуміння залежностей даних дуже важливе для розробки паралельних алгоритмів. Жодна програма не може працювати швидше ніж найдовший ланцюг залежних обчислень (відомий як критичний шлях), бо обчислення, що залежать від попередніх обчислень в ланцюгу мають виконуватись одне за одним. Тим не менш, більшість алгоритмів не складаються лиш з довгого ланцюга залежних обчислень; зазвичай є шанси виконувати незалежні обчислення паралельно.
Хай та — два фрагменти програми. Умови БернштейнаBernstein, A. J. (October 1966). «Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers». EC-15, pp. 757-62. описують коли вони паралельні та можуть виконуватись паралельно. Для , хай — вхідні змінні, а — вихідні. Для — аналогічно. та незалежні, коли вони задовольняють такі умови:
Порушення першої умови створює залежність потоку, результат роботи першої частини використовується другою. Друга умова представляє антизалежність, коли друга частина програми переписує змінну, що потрібна першій програмі. Третя, та остання умова представляє залежність виводів: коли дві частини програми записують дані в одну й ту ж змінну, кінцевий результат має отримуватись від частини, що логічно виконується останньою.Roosta, Seyed H. (2000). «Parallel processing and parallel algorithms: theory and computation». Springer, p. 114. ISBN 0-387-98716-9.
Давайте придумаємо деякі функції, що демонструють кілька типів залежностей:
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Нить B1A: Прочитати змінну V1B: Прочитати змінну V2A: Додати 1 до змінної V2B: Додати 1 до змінної V3A: Записати назад у змінну V3B: Записати назад у змінну V