Перегляд вихідного коду сторінки Паралельні обчислення

[[Файл:IBM Blue Gene P supercomputer.jpg|thumb|300px|[[Масово-паралельна архітектура|масово паралельний]] [[суперкомп'ютер]] IBM [[Blue Gene]]/P]]

'''Паралельні обчислення'''&nbsp;— це форма обчислень, в яких кілька дій проводяться одночасно<ref>Almasi, G.S. and A. Gottlieb (1989). [http://portal.acm.org/citation.cfm?id=1011116.1011127 ''Highly Parallel Computing'']. Benjamin-Cummings publishers, Redwood City, CA.</ref>. Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.

Є кілька різних рівнів паралельних обчислень: [[паралелізм бітового рівня|бітовий]], [[Паралелізм на рівні команд|інструкцій]], [[паралелізм даних|даних]] та [[Паралелізм завдань|паралелізм задач]]. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в [[високопродуктивні обчислення|високопродуктивних обчисленнях]], але зацікавлення ним зросло тільки недавно, через фізичні обмеження зростання [[частота процесора|частоти]].<ref>S.V. Adve et al. (Листопад 2008). [http://www.upcrc.illinois.edu/documents/UPCRC_Whitepaper.pdf «Parallel Computing Research at Illinois: The UPCRC Agenda»] {{Webarchive|url=https://web.archive.org/web/20081209154000/http://www.upcrc.illinois.edu/documents/UPCRC_Whitepaper.pdf |date=9 грудня 2008 }} (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. «Основні технології збільшення продуктивності обчислень&nbsp;— збільшення частоти тактового генератора, та хитріші, проте відповідно набагато складніші архітектури, сьогодні стикаються з так званою стіною потужності. Комп'ютерна промисловість прийняла факт, що майбутні зростання продуктивності обчислень будуть пов'язані зі зростанням кількості процесорів (чи ядер), аніж зі спробами змусити одне ядро працювати швидше».</ref>. Оскільки [[споживана потужність]] (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки,<ref>Asanovic et al. Старий принцип економії: Електрика безплатна, транзистори дорогі. Новий принцип економії: електрика дорога, але транзистори «безплатні».</ref> паралельне програмування стає домінуючою парадигмою в [[архітектура комп'ютера|комп'ютерній архітектурі]], основному в формі [[багатоядерний процесор|багатоядерних процесорів]].<ref name="View-Power">Asanovic, Krste et al. (Грудень 18, 2006). [http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf «The Landscape of Parallel Computing Research: A View from Berkeley»] (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. «Старий принцип вирішення проблем: Збільшення тактової частоти&nbsp;— основний метод покращення продуктивності. Новий принцип: Збільшення паралелізму це основний метод збільшення продуктивності процесора… Навіть представники Intel, компанії, що зазвичай асоціюється з позицією&nbsp;— „чим більша частота тим краще“, попереджують, що традиційні підходи до збільшення продуктивності через збільшення тактової частоти досягли своєї межі.»</ref>

Паралельні комп'ютери можуть бути грубо класифіковані згідно з рівнем, на якому апаратне забезпечення підтримує паралелізм: [[багатоядерність]], [[багатопроцесорність]]&nbsp;— комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також [[Комп'ютерний кластер|кластери]], [[Масово-паралельна архітектура|MPP]], та [[ґрід]]&nbsp;— системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач.

[[Паралельний алгоритм|Програми для паралельних комп'ютерів]] писати значно складніше, ніж для послідовних<ref>Patterson, David A. and John L. Hennessy (1998). ''Computer Organization and Design'', Second Edition, Morgan Kaufmann Publishers, p.&nbsp;715. ISBN 1-55860-428-6.</ref>, бо паралелізм додає кілька нових класів потенційних [[Баґ|помилок]], серед яких найпоширенішою є [[стан гонитви]]. Комунікація, та [[синхронізація процесів]] зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм.

Максимальний можливий приріст продуктивності паралельної програми визначається [[Закон Амдала|законом Амдала]].

== Передумови ==
Колись паралельне програмування було справою тільки тих одинаків, яких цікавили завдання для великих [[суперкомп'ютер]]ів. Але тепер, коли звичайні додатки почали працювати на [[Багатоядерний процесор|багатоядерних процесорах]], паралельне програмування швидко стає технологією, яку повинен освоїти і вміти застосовувати будь-який професійний розробник ПЗ. Паралельне програмування може бути складним, але його легше зрозуміти, якщо рахувати не «важким», а просто «трохи іншим».

Традиційно, програми пишуться для послідовних обчислень. Для розв'язку задачі придумують [[алгоритм]], який реалізовується в вигляді послідовності інструкцій. Ці інструкції виконуються одним [[процесор]]ом комп'ютера. У кожен момент часу може виконуватись тільки одна інструкція, після завершення її виконання починається виконання наступної.<ref name="llnltut">{{cite web|url=http://www.llnl.gov/computing/tutorials/parallel_comp/|title=Introduction to Parallel Computing|accessdate=2007-11-09|author=Barney, Blaise|publisher=Lawrence Livermore National Laboratory|archiveurl=https://www.webcitation.org/6HkQWt6d4?url=https://computing.llnl.gov/tutorials/parallel_comp/|archivedate=2013-06-29|deadurl=no}}</ref>

З іншого боку, в паралельному програмуванні одночасно використовують кілька обчислювальних елементів для розв'язання однієї задачі. Це уможливлюється розбиттям задачі на підзадачі, кожна з яких може бути вирішена незалежно. Процесорні елементи бувають різними та включають різні ресурси, як наприклад один комп'ютер з багатьма процесорами, кілька з'єднаних у мережу комп'ютерів, спеціалізоване апаратне забезпечення, чи будь-яку комбінацію перерахованого вище.<ref name="llnltut" />

[[Приріст частоти]] був основним чинником збільшення продуктивності комп'ютерів з середини 1980-тих до 2004. Час роботи програми дорівнює числу інструкцій, помноженому на середній час виконання інструкції. Тому збільшення частоти зменшує час виконання всіх процесорно-залежних (коли основним ресурсом виступає час процесора) програм.<ref>Hennessy, John L. and David A. Patterson (2002). ''Computer Architecture: A Quantitative Approach''. 3rd edition, Morgan Kaufmann, p.&nbsp;43. ISBN 1-55860-724-2.</ref>

Тим не менш, [[споживана потужність]] чипу задається рівнянням {{math|1=''P'' = ''C'' × ''V''{{sup|2}} × ''F''}}, де {{math|''P''}}&nbsp;— [[потужність]], {{math|''V''}}&nbsp;— [[напруга]] живлення, {{math|''C''}}&nbsp;— [[Ємність (електрика)|ємність]], що перезаряджається за один [[такт процесора]] (пропорційна числу [[транзистор]]ів, які перемикаються у цьому такті), а {{math|''F''}}&nbsp;— тактова частота.<ref>Rabaey, J. M. (1996). ''Digital Integrated Circuits''. Prentice Hall, p.&nbsp;235. ISBN 0-13-178609-1.</ref> Збільшення частоти збільшує потужність, що використовується процесором. Збільшення споживаної потужності призвело до того, що в травні 2004 [[Intel]] відмінило розробку процесорів {{Нп|Tejas та Jayhawk|||Tejas and Jayhawk}}, на які зазвичай посилаються як на знак кінця збільшення частоти, як домінуючої парадигми в комп'ютерній архітектурі.<ref>Flynn, Laurie J. [http://www.nytimes.com/2004/05/08/business/08chip.html?ex=1399348800&en=98cc44ca97b1a562&ei=5007 «Intel Halts Development of 2 New Microprocessors»]. ''The New York Times'', May 8, 2004. Retrieved on April 22, 2008.</ref>

[[Закон Мура]]&nbsp;— це емпіричне спостереження про те, що щільність транзисторів в мікропроцесорах подвоюється кожних 18-24 місяці.<ref name="Moore1965paper">{{cite web| first =Gordon E.| last =Moore| year =1965| url =ftp://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf| title =Cramming more components onto integrated circuits| format =PDF| pages =4| work =[[Electronics (magazine)|Electronics Magazine]]| accessdate =2006-11-11| archiveurl =https://web.archive.org/web/20080218224945/http://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf| archivedate =2008-02-18| deadurl =yes}}</ref> Незважаючи на проблеми зі споживанням енергії та постійні передбачення кінця, закон Мура все ще працює. З кінцем зростання частоти, ці додаткові транзистори (що вже не збільшують частоту) будуть використовуватись щоб додати додаткове апаратне забезпечення для паралельних обчислень.

=== Закони Амдала та Густафсона ===
[[Файл:Закон Амдала.svg|thumb|300px|Графічне зображення [[Закон Амдала|закону Амдала]]. Прискорення програми при розпаралелюванні залежить від того яку частину програми можна виконувати паралельно. Наприклад, якщо 90&nbsp;% програми можна виконувати паралельно, теоретичним максимумом прискорення при запуску її на паралельній машині буде десятикратне, незалежно від того, скільки процесорів використовується.]]

Оптимальним прискоренням від розпаралелювання могло б бути лінійне&nbsp;— збільшення кількості процесорів вдвічі має вдвічі скорочувати час виконання. Наступне збільшення кількості процесорів вдвічі мало б знову прискорювати програму. Тим не менш, лиш кілька [[перетинний алгоритм|паралельних алгоритмів]] досягають такого прискорення. Більшість з них мають майже лінійне прискорення при невеликій кількості процесорів, яке сповільнюється до константи при великій кількості обчислювальних елементів.

Потенційне прискорення алгоритму при збільшенні числа процесорів задається [[закон Амдала|законом Амдала]], що вперше був сформульований Джином Амдалем у 1960-тих.<ref>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.&nbsp;483-85.</ref> Він стверджує, що невелика частина програми що не піддається паралелізації обмежить загальне прискорення від розпаралелювання. Будь-яка велика математична чи інженерна задача зазвичай буде складатись з кількох частин що можуть виконуватись паралельно, та кількох частин що виконуються тільки послідовно. Цей зв'язок задається рівнянням:

: <math>S = \frac{1}{1 - P}</math>

Де <math>S</math>&nbsp;— прискорення програми (як відношення до її початкового часу роботи), а <math>P</math>&nbsp;— частка яку можна виконувати паралельно. Якщо послідовна частина програми виконується 10&nbsp;% всього часу роботи, ми не можемо прискоритись більш ніж в 10 разів, незалежно від того скільки процесорів застосуємо. Це ставить верхню межу корисності збільшення кількості обчислювальних елементів. «Коли задача не може розпаралелюватись через обмеження послідовної частини, прикладання додаткових зусиль не має ніякого ефекту для розкладу. Щоб виносити дитину потрібно дев'ять місяців, незалежно від того, скільки жінок цим займаються.»<ref>[[Фред Брукс]] ''[[Міфічний людино-місяць]]''. Розділ 2&nbsp;— Міфічний людино-місяць. ISBN 0-201-83595-9</ref>

[[Закон Густафсона]] це інший комп'ютерний закон, що сильно пов'язаний з законом Амдала. Його можна сформулювати так:

[[Файл:Оптимізація різних частин програми.svg|thumb|300px|Припустимо що задача має дві незалежні частини, A та B. B займає 25&nbsp;% часу обчислень. Доклавши певних зусиль програміст може зробити цю частину в п'ять разів швидшою, але це ненабагато зменшить час всього обчислення. Тим не менш, можливо для того щоб прискорити частину A вдвічі потрібно менше зусиль, але це прискорить виконання всієї програми набагато сильніше ніж оптимізація B, попри те, що B можна оптимізувати сильніше.]]

: <math> S(P) = P - \alpha(P-1) \, </math>

де <math>P</math> це кількість процесорів, <math>S</math>&nbsp;— прискорення, а <math>\alpha</math> нерозпаралелювана частина процесу.<ref>[http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html Reevaluating Amdahl's Law] {{Webarchive|url=https://web.archive.org/web/20070927040654/http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html |date=27 вересня 2007 }} (1988). [[Communications of the ACM]] 31(5), pp.&nbsp;532-33.</ref>. Закон Амдала базується на припущенні того, що задача має фіксований розмір, і що розмір послідовної частини незалежний від кількості процесорів, в той час як закон Густафсона не робить таких припущень.

=== Залежності ===
Розуміння залежностей даних дуже важливе для розробки [[паралельний алгоритм|паралельних алгоритмів]]. Жодна програма не може працювати швидше ніж найдовший ланцюг залежних обчислень (відомий як [[критичний шлях]]), бо обчислення, що залежать від попередніх обчислень в ланцюгу мають виконуватись одне за одним. Тим не менш, більшість алгоритмів не складаються лиш з довгого ланцюга залежних обчислень; зазвичай є шанси виконувати незалежні обчислення паралельно.

Хай <math>P_i</math> та <math>P_j</math>&nbsp;— два фрагменти програми. Умови Бернштейна<ref>Bernstein, A. J. (October 1966). «Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers». EC-15, pp.&nbsp;757-62.</ref> описують коли вони паралельні та можуть виконуватись паралельно. Для <math>P_i</math>, хай <math>I_i</math>&nbsp;— вхідні змінні, а <math>O_i</math>&nbsp;— вихідні. Для <math>P_j</math>&nbsp;— аналогічно. <math>P_i</math> та <math>P_j</math> незалежні, коли вони задовольняють такі умови:

* <math> I_j \cap O_i  =  \varnothing, \, </math>
* <math> I_i \cap O_j  =  \varnothing, \, </math>
* <math> O_i \cap O_j  = \varnothing. \, </math>

Порушення першої умови створює залежність потоку, результат роботи першої частини використовується другою. Друга умова представляє антизалежність, коли друга частина програми переписує змінну, що потрібна першій програмі. Третя, та остання умова представляє залежність виводів: коли дві частини програми записують дані в одну й ту ж змінну, кінцевий результат має отримуватись від частини, що логічно виконується останньою.<ref>Roosta, Seyed H. (2000). «Parallel processing and parallel algorithms: theory and computation». Springer, p.&nbsp;114. ISBN 0-387-98716-9.</ref>

Давайте придумаємо деякі функції, що демонструють кілька типів залежностей:

 1: function Dep(a, b)
 2:    c := a·b
 3:    d := 2·c

Оператор 3 в <code>Dep(a,b)</code> не може бути виконаним перед (чи навіть одночасно з) оператором&nbsp;2, бо операція&nbsp;3 використовує результат роботи операції&nbsp;2. Вона порушує умову&nbsp;1, тому маємо залежність потоку.

 1: function NoDep(a, b)
 2:      c := a·b
 3:      d := 2·b
 4:      e := a+b

В цьому прикладі між операціями немає залежностей, тому вони можуть виконуватись паралельно.

Умови Бернштейна не дозволяють ділити пам'ять між різними процесами. Тому, потрібне примусове впорядкування доступу до даних, як [[Семафор (програмування)|семафори]], [[Бар'єр (програмування)|бар'єри]], та інші [[синхронізація процесів|методи синхронізації]].

=== Стан гонитви, взаємне виключення, синхронізація та паралельне сповільнення ===
Підзадачі в паралельній програмі часто називають [[Нить|нитками]]. Деякі паралельні архітектури використовують менші, легші версії ниток, що називаються [[Волокно (програмування)|волокнами]], в той час як інші використовують більші версії, що називаються [[Процес (інформатика)|процесами]]. Тим не менш, «нитки» зазвичай приймаються як загальний термін для підзадач. Нитки часто потребують [[Синхронізація процесів|синхронізації]] , наприклад, для оновлення деяких [[змінна (програмування)|змінних]] що діляться між ними. Без синхронізації інструкції двох ниток можуть чергуватися у будь-якому порядку. Наприклад, хай маємо таку програму:

{| class="wikitable"
|-
|Нить A
|Нить B
|-
|1A: Прочитати змінну V
|1B: Прочитати змінну V
|-
|2A: Додати 1 до змінної V
|2B: Додати 1 до змінної V
|-
|3A: Записати назад у змінну V
|3B: Записати назад у змінну V
|}

Якщо інструкція 1B виконається між 1A та 3A, чи якщо інструкція 1A виконається між 1B та 3B, програма буде продукувати неправильні дані. Це відоме як [[стан гонитви]]. Програміст має використовувати [[Блокування (програмування)|блокування]] ({{lang-en|lock}}) щоб створити [[взаємне виключення]]. Замок&nbsp;— це [[Мовна конструкція (програмування)|конструкція мови]] програмування, що дозволяє одній ниті отримати контроль над змінною і запобігти читанню чи запису в цю змінну від інших ниток, аж поки ця змінна не буде розблокована. Нить що створила замок може вільно виконувати свою [[критична секція|критичну секцію]] (секцію програми що вимагає ексклюзивного доступу до певної змінної), і розблокувати дані коли секція закінчиться. Тому, щоб гарантувати правильне виконання, програма дана вище може бути переписана з використанням замків:

{| class="wikitable"
|-
|Нить 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, поки інша буде замкнена&nbsp;— не зможе продовжити роботу, поки V не розблокується. Це гарантуватиме правильне виконання програми. Замки необхідні щоб гарантувати коректне виконання програми, але можуть сильно її сповільнити.

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

Багато паралельних програм вимагають того, щоб їхні підзадачі [[синхронізація процесів|виконувались синхронно]]. Це потребує використання [[Бар'єр (програмування)|бар'єра]]. Бар'єри зазвичай реалізуються з використанням програмного замка. Один клас алгоритмів, що відомі під назвою [[беззамкові та беззупинкові алгоритми]] ({{lang-en|lack-free and wait-free algorithms}}), уникають використання замків та бар'єрів. Правда такий підхід зазвичай важко реалізувати і вимагає правильно сконструйованих структур даних.

Не кожне розпаралелювання спричинює прискорення. Загалом, коли задача розбивається на більше та більше ниток, ті нитки витрачають все більше і більше часу на комунікації між собою. Зрештою, час на комунікацію переважає час, що витрачається на розв'язання задачі, і подальше розпаралелювання (поділ на ще більшу кількість ниток) скоріше збільшує аніж зменшує протяжність часу потрібного щоб закінчити роботу. Це відоме як [[паралельне сповільнення]].

=== Дрібнозернистий, крупнозернистий, та [[приголомшливий паралелізм]] ===
Програми часто класифікуються відповідно до того, як часто їхні підзадачі мають синхронізуватись чи спілкуватись один з одним. Програма проявляє дрібнозернистий паралелізм якщо її підзадачі мають обмінюватись даними багато разів на секунду; вона проявляє крупнозернистий паралелізм, якщо вони не мусять обмінюватись даними багато разів на секунду, і вона проявляє приголомшливий паралелізм, якщо вони рідко, чи взагалі ніколи не мають обмінюватись даними. Приголомшливо паралельні програми вважаються такими що розпаралелюються найлегше.

=== Моделі узгодженості ===
{{Main|Модель узгодженості|Модель паралельних обчислень}}

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

Однією з перших моделей узгодженості була модель [[послідовна узгодженість|послідовної щільності]] [[Леслі Лампорт]]а. Послідовна узгодженість&nbsp;— це властивість паралельної програми давати такий самий результат що і її послідовний аналог. Конкретніше, програма послідовно узгоджена, якщо "…&nbsp;результат будь-якого запуску такий самий, як був би якщо операції на кожному окремому процесорі виконувались так, ніби вони виконуються в певній послідовності заданій програмою.<ref>Lamport, Leslie (September 1979). «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs», IEEE Transactions on Computers, C-28,9, pp.&nbsp;690-91.</ref>

[[Транзакційна пам'ять]] це типовий приклад моделі узгодженості. Транзакційна пам'ять взяла у теорії баз даних принцип [[транзакція|атомарної транзакції]] та застосувала його при доступі до пам'яті.

Математично, ці моделі можуть представлятись кількома способами. [[Мережа Петрі|Мережі Петрі]], що були вперше представлені Карлом Адамом Петрі у 1962-гому, були ранніми спробами систематизувати правила узгодженості моделей. На їхній основі побудована теорія потоків даних, а [[Архітектура потоків даних|їхня архітектура]] була створена, щоб реалізувати ідеї цієї теорії фізично. Починаючи з кінця 1970-х, були розроблені [[числення процесів]], такі як [[Числення Систем, що Спілкуються]] та [[Послідовні Процеси, що Спілкуюються|Послідовні Процеси, що Спілкуються]], щоб уможливити алгебраїчне обґрунтування систем складених з взаємодіючих компонентів. Новіші доповнення до сім'ї числень процесів, такі як [[пі-числення|π-числення]], додали можливість обґрунтування динамічних топологій. Такі логіки як [[Темпоральна логіка дій|TLA+]], та математичні моделі такі як [[теорія трас|траси]] та [[теорія моделі актора|діаграми подій актора]], також були розвинені щоб описати поведінку конкурентних систем.

=== Таксономія Флінна ===
Майкл Дж. Флінн створив одну з найперших класифікацій систем паралельних (та послідовних) комп'ютерів та програм, що нині відома як [[Таксономія Флінна]]. Флінн поділяв програми та комп'ютерами залежно від того чи вони використовували один чи багато потоків команд, та чи команди оперували одним чи багатьма множинами даних.

{{Таксономія Флінна}}

Клас single-instruction-single-data (SISD) еквівалентний цілковито послідовній програмі. Single-instruction-multiple-data (SIMD) еквівалентний виконанню однієї та тієї ж операції повторювано над великим масивом даних. Це зазвичай відбувається у задачах [[обробка сигналів|обробки сигналів]]. Клас Multiple-instruction-single-data (MISD) використовується рідко. Поки придумувались архітектури, що стосуються цього класу (як наприклад [[систолічні масиви]]), з'явилось лише кілька програм, що підпадають під цей клас. Multiple-instruction-multiple-data (MIMD) найтиповіші представники паралельних програм.

Згідно з Девідом Паттерсоном та Джоном Геннесі, «Деякі машини є гібридами цих категорій, щоправда ця класична модель вижила через те, що вона проста, легка для розуміння, та дає гарне перше наближення. Вона також, можливо через її зрозумілість&nbsp;— найпоширеніша схема.»<ref>Patterson and Hennessy, p.&nbsp;748.</ref>

== Рівні паралелізму ==

=== Паралелізм бітового рівня ===
{{main|Паралелізм бітового рівня}}

З винайденням у 1970-тих технології створення надвеликих [[інтегральна схема|інтегральних схем]] прискорення в комп'ютерній архітектурі відбувалось з допомогою подвоєння розміру [[машинне слово|машинного слова]]&nbsp;— кількості інформації, яку комп'ютер може обробляти за один цикл.<ref>Culler, David E.; Jaswinder Pal Singh and Anoop Gupta (1999). ''Parallel Computer Architecture&nbsp;— A Hardware/Software Approach''. Morgan Kaufmann Publishers, p.&nbsp;15. ISBN 1-55860-343-3.</ref> Збільшення розміру слова зменшує кількість інструкцій необхідних виконати операцію над даними чий розмір більший ніж розмір вхідного слова. Наприклад коли [[8 біт|восьмибітний процесор]] має додати два [[16 біт|шістнадцятирозрядні]] числа, процесор має спочатку додати 8&nbsp;біт нижчого розряду з кожного числа, використовуючи стандартну інструкцію додавання, потім додати 8 бітів вищого розряду, використовуючи інструкцію додавання з переносом та [[біт переносу]] від виконання попереднього додавання. Тому восьмибітний процесор потребує дві інструкції для виконання однієї операції, в той час як шістнадцятибітний лиш одну.

Історично, [[4 біти|чотирьохрозрядні процесори]] були замінені на [[8 біт|восьмирозрядні]], потім на [[16 біт|шістнадцятирозрядні]], потім на [[32 біти|32-х розрядні]]. Ця тенденція припинилась з введенням тридцятидвохрозрядних процесорів, які стали стандартом для персональних комп'ютерів на два десятиліття. Аж поки недавно (2003—2004), з винайденням архітектури [[x86-64]], не з'явились [[64 біти|64-x розрядні]] процесори.

=== Паралелізм рівня інструкцій ===
{{main|Паралелізм на рівні команд}}
[[Файл:Fivestagespipeline.png|thumb|300px|Стандартний п'ятикроковий конвеєр в машині [[RISC (процесор)|RISC]] (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back)]]
Комп'ютерна програма, по суті, є потоком інструкцій, що виконуються процесором. Іноді ці інструкції можна перевпорядкувати, та об'єднати в групи, які потім виконувати паралельно, без зміни результату роботи програми, що відомо як паралелізм на рівні інструкцій. Такий підхід до збільшення продуктивності обчислень переважав з середини 80-тих до середини 90-тих.<ref>Culler et al. p.&nbsp;15.</ref>

Сучасні процесори мають багатоетапні [[конвеєр команд|конвеєри команд]]. Кожен етап конвеєра відповідає іншій дії, що виконує процесор. Процесор що має конвеєр з N-ступенями, може одночасно обробляти N інструкцій, кожну на іншій стадії обробки. Класичним прикладом процесора з конвеєром є процесор архітектури [[RISC (процесор)|RISC]], що має п'ять етапів: завантаження інструкції, декодування, виконання, доступ до пам'яті, та запис результату. Процесор [[Pentium 4]] має конвеєр з 35 етапами.<ref>Patt, Yale (April 2004). [http://users.ece.utexas.edu/~patt/Videos/talk_videos/cmu_04-29-04.wmv The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them?] {{Webarchive|url=https://web.archive.org/web/20080414141000/http://users.ece.utexas.edu/~patt/Videos/talk_videos/cmu_04-29-04.wmv |date=14 квітня 2008 }} (wmv). Distinguished Lecturer talk at [[Carnegie Mellon University]]. Retrieved on November 7, 2007.</ref>

[[Файл:Superscalarpipeline.svg|thumb|300px|Суперскалярний п'ятиетапний конвеєрний мікропроцесор, що здатен виконувати дві інструкції за цикл. Він може зберігати дві інструкції на кожній стадії конвеєра, таким чином загалом виконуючи десять інструкцій водночас.]]

На додачу до паралелізму на рівні інструкцій деякі процесори можуть виконувати більш ніж одну інструкцію за раз. Вони відомі як [[суперскалярність|суперскалярні]] процесори. Інструкції групуються разом, якщо між ними не існує залежності даних. Щоб реалізувати паралелізм на рівні інструкцій використовують алгоритми [[Scoreboarding]] та [[Tomasulo algorithm]] (який аналогічний до попереднього, проте використовує [[перейменування регістрів]]).

=== Паралелізм даних ===
{{main|Паралелізм даних}}

Паралелізм даних&nbsp;— це паралелізм властивий [[цикл програми|циклам програм]], які фокусуються на доставці даних різним обчислювальним вузлам для паралельної обробки. "Розпаралелювання циклів часто приводить до подібних (не обов'язково ідентичних) послідовностей операцій, чи обчислення функцій над елементами великих структур даних.<ref name=Culler124>Culler et al. p.&nbsp;124.</ref> Багато наукових, та інженерних програм проявляють паралелізм даних.

Циклічна залежність&nbsp;— залежність ітерації циклу, від результатів попередньої, чи кількох попередніх ітерацій. Циклічні залежності перешкоджають розпаралелюванню циклів. Розглянемо [[псевдокод]], що обчислює кілька перших [[числа фібоначчі|чисел фібоначчі]]:

 1:    PREV1 := 0
 2:    PREV2 := 1
 4:    do:
 5:       CUR := PREV1 + PREV2
 6:       PREV1 := PREV2
 7:       PREV2 := CUR
 8:    while (CUR < 10)

Такий цикл не може бути розпаралелений, бо CUR залежить від себе (PREV2), та PREV1, які обчислюються в кожній ітерації. Тому, кожна ітерація залежить від результатів попередньої, вони не можуть виконуватись паралельно. Коли розмір задачі стає більшим, кількість доступних для розпаралелювання даних зазвичай теж зростає.<ref name=Culler125>Culler et al. p.&nbsp;125.</ref>

=== Паралелізм задач ===
{{main|Паралелізм задач}}
Паралелізм задач&nbsp;— характеристика паралельної програми, яка полягає в тому, що «цілком різні обчислення можуть виконуватись над одними, чи різними даними».<ref name=Culler124/> Це відрізняє паралелізм задач від паралелізму даних, при якому одне і те ж обчислення виконується над одними і тими ж даними. Паралелізм задач, зазвичай не зростає зі зростанням розміру задачі.<ref name=Culler125/>

== Апаратне забезпечення ==

=== Пам'ять та комунікації ===
Основною пам'яттю в паралельному комп'ютері є як [[спільна пам'ять]] (розподілена між всіма обчислювальними елементами в одному [[адресний простір|адресному просторі]]), чи [[розподілена пам'ять]] (в якій кожен обчислювальний елемент має свій власний локальний адресний простір).<ref name="PH713">Patterson and Hennessy, p.&nbsp;713.</ref> Розподілена пам'ять відсилається до того факту, що пам'ять є логічно поділеною, хоча часто натякає і на те, що вона також розділена і фізично. [[Розподілена спільна пам'ять]] та [[віртуалізація пам'яті]] комбінують обидва підходи, де обчислювальний елемент має свою власну локальну пам'ять, та доступ до пам'яті інших процесорів. Доступ до локальної пам'яті зазвичай швидший ніж доступ до нелокальної.

[[Файл:Numa.svg|right|thumbnail|400px|Структура архітектури [[Non-Uniform Memory Access]] (NUMA). Процесори в одній директорії можуть отримати доступ до пам'яті тієї директорії за менший час ніж в інших директоріях.]]

Комп'ютерні архітектури в яких доступ до кожного елементу основної пам'яті займає однаковий час та трафік називаються системами з однорідним доступом до пам'яті [[Uniform Memory Access]] (UMA). Зазвичай, це досягається тільки з спільною пам'яттю, в якій пам'ять не є фізично розподілена. Система що не володіє такою властивістю називається архітектурою з неоднорідним доступом до пам'яті ([[Non-Uniform Memory Access]] (NUMA)). Системи з розподіленою пам'яттю мають неоднорідний доступ до пам'яті.

Комп'ютерні системи використовують маленькі, швидкі, кеш-пам'яті, що розміщуються близько до процесора, та зберігають тимчасові копії змінних пам'яті (як у фізичному, так і логічному смислах). Паралельні комп'ютери мають проблеми з кешами, що можуть зберігати одні і ті ж значення в кількох місцях, що створює можливості для неправильного виконання обчислень. Такі комп'ютери вимагають систему [[когеренція кешу|когеренції кешу]], яка слідкує за кешованими змінними та вчасно очищує їх, забезпечуючи коректне виконання програми. {{нп|Пронюхування шини|||Bus sniffing}} один з найзагальніших методів слідкування за тим, які змінні використовуються та які треба зачистити. Конструювання великих, продуктивних систем когеренції кешу є складною задачею з галузі комп'ютерних архітектур. В результаті, архітектури з спільною пам'яттю не масштабуються так добре, як з розподіленою пам'яттю.<ref name=PH713/>

Комунікація між процесорами, та між процесорами та пам'яттю може бути реалізована апаратно кількома способами, включаючи спільну (мультипортову чи [[Мультиплексування|Мультиплексну]]) пам'ять, [[матричний перемикач]], спільну [[комп'ютерна шина|шину]] чи мережа однієї з тисяч [[мережна топологія|топологій]], включаючи зірку, кільце, дерево, [[Тесеракт|гіперкуб]], жирний гіперкуб (гіперкуб з більш ніж одним процесором у вершині), чи n-вимірну сітку.

Паралельні комп'ютери що базуються на зв'язаних мережах мають мати певну [[маршрутизація|маршрутизацію]] щоб забезпечити передавання повідомлень між елементами що не є зв'язані напряму. Медіа що використовується для зв'язку процесорів часто буває ієрархічним у великих багатопроцесорних машинах.

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

==== Багатоядерні обчислення ====
{{main|Багатоядерність (комп'ютери)}}
[[Багатоядерний процесор]]&nbsp;— це [[процесор]], що містить кілька ядер. Ці процесори відрізняються від суперскалярних процесорів, які можуть виконувати кілька інструкцій за такт з одного потоку інструкцій ([[нить|нитки]]); на відміну від багатоядерних, що можуть за такт виконувати кілька інструкцій з різних ниток. Кожне ядро багатоядерного процесора потенційно може бути суперскалярним, тобто виконувати по кілька інструкцій з одної нитки.

[[Синхронна багатонитевість]] (найвідомішою з яких є технологія [[HyperThreading]] від [[Intel]]) була ранньою формою псевдо-багатоядерності. Процесор, що здатен до синхронної багатонитевості має лиш одне ядро, але при простоях ядра (наприклад під час очікування підвантаження даних в стек), використовує це ядро для роботи з іншою ниттю. [[Мікропроцесор Cell]] від [[IBM]], що створений для використання в консолях [[Sony]] [[PlayStation 3]] є іншим прикладом багатоядерного процесора.

==== Симетрична багатопроцесорність ====
{{main|Симетрична багатопроцесорність}}

Симетричний мультипроцесор (SMP) це комп'ютерна система з багатьма ідентичними [[процесор]]ами, що поділяють [[оперативна пам'ять|пам'ять]], та з'єднуються через [[комп'ютерна шина|шину]].<ref name=HP549>Hennessy and Patterson, p.&nbsp;549.</ref> {{нп|Шинна суперечка|||Bus contention}} ({{lang-en|bus contention}}) перешкоджає масштабуванню шинних архітектур. В результаті, SMP зазвичай не містить більше 32-x процесорів.<ref>Patterson and Hennessy, p.&nbsp;714.</ref> «Через малий розмір процесорів, та значне зменшення вимог до пропускної здатності шини, що досягається завдяки великим кешам, такі симетричні багатопроцесорні системи є дуже рентабельними за умови, що існує достатня кількість пропускної здатності у пам'яті».<ref name=HP549/>

==== Розподілені обчислення ====
{{main|Розподілені обчислення}}
Розподілений комп'ютер (також відомий як мультипроцесор з розподіленою пам'яттю) це комп'ютерна система з розподіленою пам'яттю, у якій обчислювальні елементи з'єднані мережею. Розподілені комп'ютери чудово масштабуються.

===== Кластерні обчислення =====
{{main|Комп'ютерний кластер}}
[[Файл:Beowulf.jpg|right|thumbnail|upright|[[Кластер Beowulf]]]]

Кластер&nbsp;— це група слабо зв'язаних комп'ютерів, що тісно співпрацюють, так що в певною мірою, вони можуть розглядатись як один комп'ютер.<ref>[http://www.webopedia.com/TERM/c/clustering.html What is clustering?] Webopedia computer dictionary.</ref> Кластери складаються з багатьох окремих машин, з'єднаних мережею. І хоча машини в кластері не мають бути симетричними, якщо вони не є, то це ускладнює [[балансування навантаження]]. Найпоширенішим типом кластера є [[кластер Beowulf]], який є кластером, реалізованим на багатьох ідентичних фабричних комп'ютерах, з'єднаних в [[локальна мережа|локальну мережу]] [[TCP/IP]] [[Ethernet]].<ref>[http://www.pcmag.com/encyclopedia_term/0,2542,t=Beowulf&i=38548,00.asp Beowulf definition.] {{Webarchive|url=https://web.archive.org/web/20121010215231/http://www.pcmag.com/encyclopedia_term/0%2C2542%2Ct%3DBeowulf%26i%3D38548%2C00.asp |date=2012-10-10 }} ''PC Magazine''</ref> Вперше технологію Beowulf розробили [[Томас Стерлінг]] та [[Дональд Беккер]]. Більшість суперкомп'ютерів зі списку [[TOP500]] є кластерами.<ref>[http://www.top500.org/stats/list/29/archtype Architecture share for 06/2007] {{Webarchive|url=https://web.archive.org/web/20071114212716/http://www.top500.org/stats/list/29/archtype |date=14 листопада 2007 }}. TOP500 Supercomputing Sites. Clusters make up 74.60&nbsp;% of the machines on the list. Retrieved on November 7, 2007.</ref>

===== Масово-паралельні обчислення =====
{{main|Масово паралельні обчислення}}

Масивно паралельний процесор (MPP) це один комп'ютер з багатьма процесорами з'єднаними в мережу. MPP мають багато спільного з кластерами, та MPP мають спеціалізовані з'єднувальні мережі (тоді як кластери використовують стороннє обладнання для мережі). MPP також в основному більші ніж кластери, зазвичай мають «набагато більше ніж 100 процесорів».<ref>Hennessy and Patterson, p.&nbsp;537.</ref> В MPP, «кожен процесор має свою власну пам'ять та копію операційної системи з програмами. Кожна підсистема спілкується з іншою через високошвидкісне з'єднання.»<ref>[http://www.pcmag.com/encyclopedia_term/0,,t=mpp&i=47310,00.asp MPP Definition.] {{Webarchive|url=https://web.archive.org/web/20130511084523/http://www.pcmag.com/encyclopedia_term/0%2C%2Ct%3Dmpp%26i%3D47310%2C00.asp |date=2013-05-11 }} ''PC Magazine''. Retrieved on November 7, 2007.</ref>

[[Файл:BlueGeneL cabinet.jpg|right|thumbnail|upright|Шафка [[Blue Gene]]/L, що має рейтинг четвертого найшвидшого суперкомп'ютера у світі, згідно з рейтингом [[TOP500]] 11/2008. Blue Gene/L масивно паралельний процесор.]]

[[Blue Gene]]/L, має рейтинг четвертого найшвидшого суперкомп'ютера у світі, згідно з рейтингом [[TOP500]] 11/2008. Blue Gene/L масивно паралельний процесор.

===== Обчислення Ґрід =====
{{main|Ґрід мережі}}
Обчислення Ґрід&nbsp;— найбільш розподілена форма паралельних обчислень. Вона використовує для розв'язання задачі зв'язані мережею [[Інтернет]] комп'ютери. Через низьку швидкість передачі даних, та відносно великий [[час доступу]] до даних в Інтернет, ґрід обчислення проводять тільки для [[приголомшлива паралельність|приголомшливо паралельних]] задач. [[Список проектів з розподілених обчислень|Створена багато застосувань ґрід системам]], найвідомішими з яких є [[SETI@home]] та [[Folding@Home]]<ref>{{Cite news|url=https://www.science.org/doi/10.1126/science.1081623|title=Rough Times Ahead|first1=Scott|last1=Kirkpatrick|date=2003-01-31|pages=668–669|language=en|work=[[Science]]|volume=299|doi=10.1126/science.1081623|pmc=|pmid=|issue=5607|issn=0036-8075|access-date=2024-12-20}}</ref>

Більшість програм ґрід обчислень використовують проміжне програмне забезпечення, що слугує інтерфейсом між операційною системою, та програмою, та керує ресурсами мережі, і стандартизує інтерфейс. Найпоширенішим програмним забезпеченням цього типу є [[BOINC|Berkeley Open Infrastructure for Network Computing]] (BOINC). Часто програми ґрід обчислень користуються «запасними циклами», виконуючи обчислення під час простою системи. Тому їхні реалізації під виглядом екранних заставок доволі поширені.

==== Спеціальні паралельні комп'ютери ====
У галузі паралельних обчислень є спеціальні паралельні пристрої, що займають свої ніші. І хоча вони не є предметно-орієнтованими, та все ж вони зазвичай застосовуються лише для певних класів паралельних задач.

<!--
;Reconfigurable computing with field-programmable gate arrays
[[Reconfigurable computing]] is the use of a [[field-programmable gate array]] (FPGA) as a co-processor to a general-purpose computer. An FPGA is, in essence, a computer chip that can rewire itself for a given task.

FPGAs can be programmed with [[hardware description language]]s such as [[VHDL]] or [[Verilog]]. However, programming in these languages can be tedious. Several vendors have created [[C to HDL]] languages that attempt to emulate the syntax and/or semantics of the [[C programming language]], with which most programmers are familiar. The best known C to HDL languages are [[Mitrion-C]], [[Impulse C]], [[DIME-C]], and [[Handel-C]]. Specific subsets of [[SystemC]] based on C++ can also be used for this purpose.

AMD's decision to open its [[HyperTransport]] technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing.<ref name="DAmour">D'Amour, Michael R., Chief Operating Officer, [[DRC Computer Corporation]]. «Standard Reconfigurable Computing». Invited speaker at the University of Delaware, February 28, 2007.</ref> According to Michael R. D'Amour, Chief Operating Officer of [[DRC Computer Corporation]], «when we first walked into AMD, they called us 'the [[CPU socket|socket]] stealers.' Now they call us their partners.»<ref name="DAmour"/>

-->

;Обчислення загального призначення на графічних співпроцесорах (GPGPU)
{{main|GPGPU}}

[[Файл:NvidiaTesla.jpg|right|thumbnail|Відеокарта [[Nvidia Tesla]] ]]

Загальні обчислення на [[графічний процесор|графічних процесорах]] це порівняно нова тенденція в комп'ютерній інженерії. Графічні процесори&nbsp;— допоміжні процесори, що були сильно оптимізовані для обчислень [[комп'ютерна графіка|комп'ютерної графіки]].<ref>Boggan, Sha'Kia and Daniel M. Pressel (August 2007). [http://www.arl.army.mil/arlreports/2007/ARL-SR-154.pdf GPUs: An Emerging Platform for General-Purpose Computation] (PDF). ARL-SR-154, U.S. Army Research Lab. Retrieved on November 7, 2007.</ref> Обчислення в комп'ютерній графіці це галузь, в якій панує паралелізм даних, зокрема операції з [[матриця (математика)|матрицями]] в [[лінійна алгебра|лінійній алгебрі]].

На початку, відеокарти використовували графічні [[API]] для виконання свої програм. Щоправда тепер з'явилось кілька нових мов програмування та платформ збудованих для виконання обчислень загального призначення на відеокартах як на середовищах [[CUDA]] для [[Nvidia]] так і на [[Close to Metal|CMT]] для [[AMD]]. Іншими мовами для загальних обчислень на відеокартах є [[BrookGPU]], [[PeakStream]], та [[RapidMind]]. Nvidia також випустила спеціальні засоби для обчислень на своїх відеокартах серії [[Nvidia Tesla|Tesla]].

== Програмне забезпечення ==

=== Мови паралельного програмування ===
{{main article|Мови паралельного програмування}}
Паралельні мови програмування, бібліотеки, API і [[Модель паралельних обчислень|паралельні моделі]] програмування, були створені для програмування паралельних комп'ютерів. В цілому їх можна поділити на класи, засновані на припущеннях, основа яких лежить в будові, загальної пам'яті основної пам'яті, розподіленої пам'яті, або загальної розподіленої пам'яті. Однією з концепцій, які використовуються в програмах паралельного програмування, є {{нп|Майбутності та зобов'язання|концепція майбутності||Futures and promises}}, в якій одна частина програми зобов'язується поставити потрібні дані іншій частині програми в якийсь момент в майбутньому.

{{нпні|CAPS entreprise}} та&nbsp;{{нпні|Pathscale}} також координують зусилля, щоби зробити [[Директива (програмування)|директиви]] [[Гібридне багатоядерне паралельне програмування|гібридного багатоядерного паралельного програмування]] ({{lang-en|hybrid multi-core parallel programming, HMPP}}) відкритим стандартом під назвою [[OpenHMPP]]. Модель програмування на основі директив OpenHMPP пропонує синтаксис ефективного розвантаження обчислень на апаратних прискорювачах і оптимізацію переміщення даних в/з апаратної пам'яті. Директиви OpenHMPP описують [[виклик віддалених процедур]] ({{lang-en|remote procedure call, RPC}}) на прискорювані (наприклад, [[ГП]]) або, в загальнішому випадку, на наборі ядер. Ці директиви роблять нотатки в коді [[C (мова програмування)|C]] або [[Fortran]] для опису двох наборів функціональних можливостей: розвантаження процедур (що позначаються ''codelets'') на віддалений пристрій, та оптимізацію передавання даних між основною пам'яттю [[ЦП]] та пам'яттю прискорювача.

=== Автоматичне розпаралелювання ===
{{main article|Автоматичне розпаралелювання}}

Автоматичне розпаралелювання послідовної програми [[Компілятор|компілятором]] є [[Святий грааль|святим граалем]] паралельних обчислень. Незважаючи на десятиліття роботи дослідниками компіляторів, автоматичне розпаралелювання має обмежений успіх.

Головні мови паралельного програмування залишаються або явно паралельними або (в кращому випадку), частково неявно паралельними, в яких програміст дає директиви для розпаралелювання компілятору. Повністю явно паралельні мови існують&nbsp;— {{нп|SISAL|SISAL|en|SISAL}}, Parallel [[Haskell]], {{нп|SequenceL|SequenceL|en|SequenceL}}, [[SystemC|System C]] (для [[ПКВМ]]), {{нпні|Mitrion-C|Mitrion-C|en|Mitrion-C}}, [[VHDL]], і [[Verilog]].

=== Контрольні точки програми ===
{{main article|Контрольні точки програми}}

З ростом складності комп'ютерної системи [[середній наробіток між відмовами]], як правило, зменшується. [[Контрольні точки програми]]&nbsp;— це метод, за допомогою якого комп'ютерна система робить «знімок» застосунку,&nbsp;— запис усіх поточних виділених ресурсів і станів змінних, схожий на {{нп|дамп ядра|||Core dump}}. Цю інформацію може бути використано для відновлення програми, якщо комп'ютер збійне. Контрольні точки програми дають змогу розпочати з останнього збереження, а не з самого початку. В той час як контрольні точки забезпечують переваги в різних ситуаціях, вони особливо корисні у високорозвинених паралельних системах з великим числом процесорів, використовуваних в області [[Високопродуктивні обчислення|високопродуктивних обчислень]].

== Алгоритмічні методи ==
Оскільки паралельні комп'ютери стають все кращі і швидші, стає можливим вирішити проблеми, які раніше займали багато часу. Паралельні обчислення використовується в різних сферах життя, від біоінформатики (згортання білків і аналіз послідовності) до економіки (фінансової математики). Найбільш поширеними типами проблем, виявлених в паралельних обчислювальних є:<!--Note: do not add to or remove from this list. It is copied from the above source-->

* [[лінійна алгебра]]; 
* спектральні методи (такі як перетворення Кулі-Тьюки швидкого перетворення Фур'є);
* проблеми N-тіла (наприклад, Barnes-Hut моделювання);
* структуровані ґрід проблеми (наприклад, методи Латтісе Больцмана);
* неструктуровані ґрід проблеми (наприклад, знайти в аналізі кінцеві елементи);
* [[Метод Монте-Карло|метод Монте Карло]];
* [[комбінаційна логіка]] (такі як криптографічний [[метод «грубої сили»]] );
* графік обходу (наприклад, алгоритми сортування);
* [[динамічне програмування]];
* [[метод гілок і меж]];
* [[графові моделі]] (наприклад, виявлення прихованих марковських моделей і побудови мереж Байєса);

== Відмовостійкість ==
{{further|Відмовостійкі комп'ютерні системи}}Паралельні обчислення також можуть бути застосовані до проектування відмовостійких обчислювальних систем, зокрема, за допомогою Lockstep системи, що виконують ті ж операції паралельно.  Це забезпечує надлишковість у разі падіння одного з компонентів і також дозволяє автоматично визначати та виправляти помилки якщо результати різняться. Ці методи можуть бути використані, щоб допомогти запобігти поодиноким подіям, які викликають тимчасові помилки. Хоча додаткові заходи можуть знадобитися у вбудованих або спеціалізованих системах, цей метод може забезпечити економічно ефективний підхід до досягнення п-модульної надмірності в комерційних системах.

== Історія ==
{{main article|Історія обчислювальної техніки}}
[[Файл:ILLIAC_4_parallel_computer.jpg|міні|{{нп|ILLIAC IV}}, «Найсумнозвісніший суперкомп'ютер».<ref name="infamous">Patterson and Hennessy, pp.&nbsp;749–50: «Although successful in pushing several technologies useful in later projects, the ILLIAC IV failed as a computer. Costs escalated from the $8&nbsp;million estimated in 1966 to $31&nbsp;million by 1972, despite the construction of only a quarter of the planned machine&nbsp;. It was perhaps the most infamous of supercomputers. The project started in 1965 and ran its first real application in 1976.»</ref>]]
Витоки істинної (MIMD) паралельності пішли від [[Луїджі Федеріко Менабреа]] і його «Ескізу [[Аналітичний двигуна|Аналітичного двигуна]] Винайденого Чарльзом Беббіджем».

У квітні 1958 року С. Гілл (Ferranti) обговорили паралельне програмування і необхідність розгалуження і очікування. Крім того, в 1958 році дослідники IBM Джон Кок і Даніель Слотнік вперше обговорили використання паралелізму в численних розрахунках. Burroughs Corporation представила D825 в 1962 році, чотирьох процесорний комп'ютер, він надавав доступ до 16 модулів пам'яті через комутатор. У 1967 році Амдал і Слотнік опублікували дискусію про можливість паралельної обробки на конференції Американської федерації товариств з обробки інформації. Саме в ході цієї дискусії був придуманий закон Амдаля, щоб визначити межу прискорення завдяки паралельності.

У 1969 році компанія Honeywell представила свою першу Multics, симетричну систему, мультимікроконтроллерну, здатну працювати до восьми процесорів паралельно.  З 1970-х років багатопроцесорний проект Університету Карнегі-Меллона, був одним з перших мультипроцесорів з більш ніж кількома процесорами.

Історію паралельних комп'ютерів SIMD можна простежити з 1970-х років. Мотивацією ранніх комп'ютерів SIMD був амортизувати затримку управління процесора кількома інструкціями. У 1964 році Слотнік запропонував будувати МВС для Ліверморської національної лабораторії. Його проект був профінансований ВВС США. Ключем до його конструкції був досить високий паралелізм, аж до 256 процесорів, що дозволило машинам працювати на великих наборах даних в тому, що пізніше буде відоме як вектор обробки. Проте, ILLIAC IV був названий «самим сумнозвісної суперкомп'ютерів», тому що проект був тільки на чверть завершений, але пішло 11 років і коштував майже в чотири рази більше первісної оцінки. Коли він, нарешті, готовий до запуску (перший реальне застосування в 1976 році) він програвав існуючим комерційним суперкомп'ютерам, таким як Cray-1.

== Див. також ==
* [[Модель паралельних обчислень]]

== Примітки ==
{{reflist|2}}

{{Інформатика}}
{{Паралельні обчислення}}
{{Технології CPU}}

[[Категорія:Паралельні обчислення]]
[[Категорія:Конкурентні обчислення]]