Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасно. Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.
Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях, але зацікавлення ним зросло тільки недавно, через фізичні обмеження зростання частоти.. Оскільки (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки, паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів.
Паралельні комп'ютери можуть бути грубо класифіковані згідно з рівнем, на якому апаратне забезпечення підтримує паралелізм: багатоядерність, багатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також кластери, MPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач.
Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних, бо паралелізм додає кілька нових класів потенційних помилок, серед яких найпоширенішою є стан гонитви. Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм.
Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала.
Передумови
Колись паралельне програмування було справою тільки тих одинаків, яких цікавили завдання для великих суперкомп'ютерів. Але тепер, коли звичайні додатки почали працювати на багатоядерних процесорах, паралельне програмування швидко стає технологією, яку повинен освоїти і вміти застосовувати будь-який професійний розробник ПЗ. Паралельне програмування може бути складним, але його легше зрозуміти, якщо рахувати не «важким», а просто «трохи іншим».
Традиційно, програми пишуться для послідовних обчислень. Для розв'язку задачі придумують алгоритм, який реалізовується в вигляді послідовності інструкцій. Ці інструкції виконуються одним процесором комп'ютера. У кожен момент часу може виконуватись тільки одна інструкція, після завершення її виконання починається виконання наступної.
З іншого боку, в паралельному програмуванні одночасно використовують кілька обчислювальних елементів для розв'язання однієї задачі. Це уможливлюється розбиттям задачі на підзадачі, кожна з яких може бути вирішена незалежно. Процесорні елементи бувають різними та включають різні ресурси, як наприклад один комп'ютер з багатьма процесорами, кілька з'єднаних у мережу комп'ютерів, спеціалізоване апаратне забезпечення, чи будь-яку комбінацію перерахованого вище.
був основним чинником збільшення продуктивності комп'ютерів з середини 1980-тих до 2004. Час роботи програми дорівнює числу інструкцій, помноженому на середній час виконання інструкції. Тому збільшення частоти зменшує час виконання всіх процесорно-залежних (коли основним ресурсом виступає час процесора) програм.
Тим не менш, чипу задається рівнянням P = C × V2 × F, де P — потужність, V — напруга живлення, C — ємність, що перезаряджається за один (пропорційна числу транзисторів, які перемикаються у цьому такті), а F — тактова частота. Збільшення частоти збільшує потужність, що використовується процесором. Збільшення споживаної потужності призвело до того, що в травні 2004 Intel відмінило розробку процесорів [en], на які зазвичай посилаються як на знак кінця збільшення частоти, як домінуючої парадигми в комп'ютерній архітектурі.
Закон Мура — це емпіричне спостереження про те, що щільність транзисторів в мікропроцесорах подвоюється кожних 18-24 місяці. Незважаючи на проблеми зі споживанням енергії та постійні передбачення кінця, закон Мура все ще працює. З кінцем зростання частоти, ці додаткові транзистори (що вже не збільшують частоту) будуть використовуватись щоб додати додаткове апаратне забезпечення для паралельних обчислень.
Закони Амдала та Густафсона
Оптимальним прискоренням від розпаралелювання могло б бути лінійне — збільшення кількості процесорів вдвічі має вдвічі скорочувати час виконання. Наступне збільшення кількості процесорів вдвічі мало б знову прискорювати програму. Тим не менш, лиш кілька паралельних алгоритмів досягають такого прискорення. Більшість з них мають майже лінійне прискорення при невеликій кількості процесорів, яке сповільнюється до константи при великій кількості обчислювальних елементів.
Потенційне прискорення алгоритму при збільшенні числа процесорів задається законом Амдала, що вперше був сформульований Джином Амдалем у 1960-тих. Він стверджує, що невелика частина програми що не піддається паралелізації обмежить загальне прискорення від розпаралелювання. Будь-яка велика математична чи інженерна задача зазвичай буде складатись з кількох частин що можуть виконуватись паралельно, та кількох частин що виконуються тільки послідовно. Цей зв'язок задається рівнянням:
Де — прискорення програми (як відношення до її початкового часу роботи), а — частка яку можна виконувати паралельно. Якщо послідовна частина програми виконується 10 % всього часу роботи, ми не можемо прискоритись більш ніж в 10 разів, незалежно від того скільки процесорів застосуємо. Це ставить верхню межу корисності збільшення кількості обчислювальних елементів. «Коли задача не може розпаралелюватись через обмеження послідовної частини, прикладання додаткових зусиль не має ніякого ефекту для розкладу. Щоб виносити дитину потрібно дев'ять місяців, незалежно від того, скільки жінок цим займаються.»
Закон Густафсона це інший комп'ютерний закон, що сильно пов'язаний з законом Амдала. Його можна сформулювати так:
де це кількість процесорів, — прискорення, а нерозпаралелювана частина процесу.. Закон Амдала базується на припущенні того, що задача має фіксований розмір, і що розмір послідовної частини незалежний від кількості процесорів, в той час як закон Густафсона не робить таких припущень.
Залежності
Розуміння залежностей даних дуже важливе для розробки паралельних алгоритмів. Жодна програма не може працювати швидше ніж найдовший ланцюг залежних обчислень (відомий як ), бо обчислення, що залежать від попередніх обчислень в ланцюгу мають виконуватись одне за одним. Тим не менш, більшість алгоритмів не складаються лиш з довгого ланцюга залежних обчислень; зазвичай є шанси виконувати незалежні обчислення паралельно.
Хай та — два фрагменти програми. Умови Бернштейна описують коли вони паралельні та можуть виконуватись паралельно. Для , хай — вхідні змінні, а — вихідні. Для — аналогічно. та незалежні, коли вони задовольняють такі умови:
Порушення першої умови створює залежність потоку, результат роботи першої частини використовується другою. Друга умова представляє антизалежність, коли друга частина програми переписує змінну, що потрібна першій програмі. Третя, та остання умова представляє залежність виводів: коли дві частини програми записують дані в одну й ту ж змінну, кінцевий результат має отримуватись від частини, що логічно виконується останньою.
Давайте придумаємо деякі функції, що демонструють кілька типів залежностей:
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), уникають використання замків та бар'єрів. Правда такий підхід зазвичай важко реалізувати і вимагає правильно сконструйованих структур даних.
Не кожне розпаралелювання спричинює прискорення. Загалом, коли задача розбивається на більше та більше ниток, ті нитки витрачають все більше і більше часу на комунікації між собою. Зрештою, час на комунікацію переважає час, що витрачається на розв'язання задачі, і подальше розпаралелювання (поділ на ще більшу кількість ниток) скоріше збільшує аніж зменшує протяжність часу потрібного щоб закінчити роботу. Це відоме як паралельне сповільнення.
Дрібнозернистий, крупнозернистий, та приголомшливий паралелізм
Програми часто класифікуються відповідно до того, як часто їхні підзадачі мають синхронізуватись чи спілкуватись один з одним. Програма проявляє дрібнозернистий паралелізм якщо її підзадачі мають обмінюватись даними багато разів на секунду; вона проявляє крупнозернистий паралелізм, якщо вони не мусять обмінюватись даними багато разів на секунду, і вона проявляє приголомшливий паралелізм, якщо вони рідко, чи взагалі ніколи не мають обмінюватись даними. Приголомшливо паралельні програми вважаються такими що розпаралелюються найлегше.
Моделі узгодженості
Паралельні мови програмування та паралельні комп'ютери мають мати модель узгодженості (також відому як модель пам'яті). Модель узгодженості описує правила проведення різноманітних операцій з пам'яттю, та що ми отримуємо в результаті цих операцій.
Однією з перших моделей узгодженості була модель послідовної щільності Леслі Лампорта. Послідовна узгодженість — це властивість паралельної програми давати такий самий результат що і її послідовний аналог. Конкретніше, програма послідовно узгоджена, якщо "… результат будь-якого запуску такий самий, як був би якщо операції на кожному окремому процесорі виконувались так, ніби вони виконуються в певній послідовності заданій програмою.
Транзакційна пам'ять це типовий приклад моделі узгодженості. Транзакційна пам'ять взяла у теорії баз даних принцип атомарної транзакції та застосувала його при доступі до пам'яті.
Математично, ці моделі можуть представлятись кількома способами. Мережі Петрі, що були вперше представлені Карлом Адамом Петрі у 1962-гому, були ранніми спробами систематизувати правила узгодженості моделей. На їхній основі побудована теорія потоків даних, а їхня архітектура була створена, щоб реалізувати ідеї цієї теорії фізично. Починаючи з кінця 1970-х, були розроблені , такі як та Послідовні Процеси, що Спілкуються, щоб уможливити алгебраїчне обґрунтування систем складених з взаємодіючих компонентів. Новіші доповнення до сім'ї числень процесів, такі як π-числення, додали можливість обґрунтування динамічних топологій. Такі логіки як , та математичні моделі такі як та , також були розвинені щоб описати поведінку конкурентних систем.
Таксономія Флінна
Майкл Дж. Флінн створив одну з найперших класифікацій систем паралельних (та послідовних) комп'ютерів та програм, що нині відома як Таксономія Флінна. Флінн поділяв програми та комп'ютерами залежно від того чи вони використовували один чи багато потоків команд, та чи команди оперували одним чи багатьма множинами даних.
Одиночний потік інструкцій Single Instruction | Множинний потік інструкцій Multiple Instruction | |
Одиночний потік даних Single Data | SISD | MISD |
Множинний потік даних Multiple Data | SIMD | MIMD |
Клас single-instruction-single-data (SISD) еквівалентний цілковито послідовній програмі. Single-instruction-multiple-data (SIMD) еквівалентний виконанню однієї та тієї ж операції повторювано над великим масивом даних. Це зазвичай відбувається у задачах обробки сигналів. Клас Multiple-instruction-single-data (MISD) використовується рідко. Поки придумувались архітектури, що стосуються цього класу (як наприклад систолічні масиви), з'явилось лише кілька програм, що підпадають під цей клас. Multiple-instruction-multiple-data (MIMD) найтиповіші представники паралельних програм.
Згідно з Девідом Паттерсоном та Джоном Геннесі, «Деякі машини є гібридами цих категорій, щоправда ця класична модель вижила через те, що вона проста, легка для розуміння, та дає гарне перше наближення. Вона також, можливо через її зрозумілість — найпоширеніша схема.»
Рівні паралелізму
Паралелізм бітового рівня
З винайденням у 1970-тих технології створення надвеликих інтегральних схем прискорення в комп'ютерній архітектурі відбувалось з допомогою подвоєння розміру машинного слова — кількості інформації, яку комп'ютер може обробляти за один цикл. Збільшення розміру слова зменшує кількість інструкцій необхідних виконати операцію над даними чий розмір більший ніж розмір вхідного слова. Наприклад коли восьмибітний процесор має додати два шістнадцятирозрядні числа, процесор має спочатку додати 8 біт нижчого розряду з кожного числа, використовуючи стандартну інструкцію додавання, потім додати 8 бітів вищого розряду, використовуючи інструкцію додавання з переносом та біт переносу від виконання попереднього додавання. Тому восьмибітний процесор потребує дві інструкції для виконання однієї операції, в той час як шістнадцятибітний лиш одну.
Історично, були замінені на восьмирозрядні, потім на шістнадцятирозрядні, потім на 32-х розрядні. Ця тенденція припинилась з введенням тридцятидвохрозрядних процесорів, які стали стандартом для персональних комп'ютерів на два десятиліття. Аж поки недавно (2003—2004), з винайденням архітектури x86-64, не з'явились 64-x розрядні процесори.
Паралелізм рівня інструкцій
Комп'ютерна програма, по суті, є потоком інструкцій, що виконуються процесором. Іноді ці інструкції можна перевпорядкувати, та об'єднати в групи, які потім виконувати паралельно, без зміни результату роботи програми, що відомо як паралелізм на рівні інструкцій. Такий підхід до збільшення продуктивності обчислень переважав з середини 80-тих до середини 90-тих.
Сучасні процесори мають багатоетапні конвеєри команд. Кожен етап конвеєра відповідає іншій дії, що виконує процесор. Процесор що має конвеєр з N-ступенями, може одночасно обробляти N інструкцій, кожну на іншій стадії обробки. Класичним прикладом процесора з конвеєром є процесор архітектури RISC, що має п'ять етапів: завантаження інструкції, декодування, виконання, доступ до пам'яті, та запис результату. Процесор Pentium 4 має конвеєр з 35 етапами.
На додачу до паралелізму на рівні інструкцій деякі процесори можуть виконувати більш ніж одну інструкцію за раз. Вони відомі як суперскалярні процесори. Інструкції групуються разом, якщо між ними не існує залежності даних. Щоб реалізувати паралелізм на рівні інструкцій використовують алгоритми та Tomasulo algorithm (який аналогічний до попереднього, проте використовує перейменування регістрів).
Паралелізм даних
Паралелізм даних — це паралелізм властивий циклам програм, які фокусуються на доставці даних різним обчислювальним вузлам для паралельної обробки. "Розпаралелювання циклів часто приводить до подібних (не обов'язково ідентичних) послідовностей операцій, чи обчислення функцій над елементами великих структур даних. Багато наукових, та інженерних програм проявляють паралелізм даних.
Циклічна залежність — залежність ітерації циклу, від результатів попередньої, чи кількох попередніх ітерацій. Циклічні залежності перешкоджають розпаралелюванню циклів. Розглянемо псевдокод, що обчислює кілька перших чисел фібоначчі:
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, які обчислюються в кожній ітерації. Тому, кожна ітерація залежить від результатів попередньої, вони не можуть виконуватись паралельно. Коли розмір задачі стає більшим, кількість доступних для розпаралелювання даних зазвичай теж зростає.
Паралелізм задач
Паралелізм задач — характеристика паралельної програми, яка полягає в тому, що «цілком різні обчислення можуть виконуватись над одними, чи різними даними». Це відрізняє паралелізм задач від паралелізму даних, при якому одне і те ж обчислення виконується над одними і тими ж даними. Паралелізм задач, зазвичай не зростає зі зростанням розміру задачі.
Апаратне забезпечення
Пам'ять та комунікації
Основною пам'яттю в паралельному комп'ютері є як спільна пам'ять (розподілена між всіма обчислювальними елементами в одному адресному просторі), чи (в якій кожен обчислювальний елемент має свій власний локальний адресний простір). Розподілена пам'ять відсилається до того факту, що пам'ять є логічно поділеною, хоча часто натякає і на те, що вона також розділена і фізично. та комбінують обидва підходи, де обчислювальний елемент має свою власну локальну пам'ять, та доступ до пам'яті інших процесорів. Доступ до локальної пам'яті зазвичай швидший ніж доступ до нелокальної.
Комп'ютерні архітектури в яких доступ до кожного елементу основної пам'яті займає однаковий час та трафік називаються системами з однорідним доступом до пам'яті (UMA). Зазвичай, це досягається тільки з спільною пам'яттю, в якій пам'ять не є фізично розподілена. Система що не володіє такою властивістю називається архітектурою з неоднорідним доступом до пам'яті (Non-Uniform Memory Access (NUMA)). Системи з розподіленою пам'яттю мають неоднорідний доступ до пам'яті.
Комп'ютерні системи використовують маленькі, швидкі, кеш-пам'яті, що розміщуються близько до процесора, та зберігають тимчасові копії змінних пам'яті (як у фізичному, так і логічному смислах). Паралельні комп'ютери мають проблеми з кешами, що можуть зберігати одні і ті ж значення в кількох місцях, що створює можливості для неправильного виконання обчислень. Такі комп'ютери вимагають систему когеренції кешу, яка слідкує за кешованими змінними та вчасно очищує їх, забезпечуючи коректне виконання програми. [en] один з найзагальніших методів слідкування за тим, які змінні використовуються та які треба зачистити. Конструювання великих, продуктивних систем когеренції кешу є складною задачею з галузі комп'ютерних архітектур. В результаті, архітектури з спільною пам'яттю не масштабуються так добре, як з розподіленою пам'яттю.
Комунікація між процесорами, та між процесорами та пам'яттю може бути реалізована апаратно кількома способами, включаючи спільну (мультипортову чи Мультиплексну) пам'ять, матричний перемикач, спільну шину чи мережа однієї з тисяч , включаючи зірку, кільце, дерево, гіперкуб, жирний гіперкуб (гіперкуб з більш ніж одним процесором у вершині), чи n-вимірну сітку.
Паралельні комп'ютери що базуються на зв'язаних мережах мають мати певну маршрутизацію щоб забезпечити передавання повідомлень між елементами що не є зв'язані напряму. Медіа що використовується для зв'язку процесорів часто буває ієрархічним у великих багатопроцесорних машинах.
Види паралельних комп'ютерів
Паралельні комп'ютери можна грубо класифікувати за рівнем, на якому апаратне забезпечення підтримує паралелізм. Така класифікація майже аналогічна відстані між основними обчислювальними елементами.
Багатоядерні обчислення
Багатоядерний процесор — це процесор, що містить кілька ядер. Ці процесори відрізняються від суперскалярних процесорів, які можуть виконувати кілька інструкцій за такт з одного потоку інструкцій (нитки); на відміну від багатоядерних, що можуть за такт виконувати кілька інструкцій з різних ниток. Кожне ядро багатоядерного процесора потенційно може бути суперскалярним, тобто виконувати по кілька інструкцій з одної нитки.
(найвідомішою з яких є технологія HyperThreading від Intel) була ранньою формою псевдо-багатоядерності. Процесор, що здатен до синхронної багатонитевості має лиш одне ядро, але при простоях ядра (наприклад під час очікування підвантаження даних в стек), використовує це ядро для роботи з іншою ниттю. від IBM, що створений для використання в консолях Sony PlayStation 3 є іншим прикладом багатоядерного процесора.
Симетрична багатопроцесорність
Симетричний мультипроцесор (SMP) це комп'ютерна система з багатьма ідентичними процесорами, що поділяють пам'ять, та з'єднуються через шину. [en] (англ. bus contention) перешкоджає масштабуванню шинних архітектур. В результаті, SMP зазвичай не містить більше 32-x процесорів. «Через малий розмір процесорів, та значне зменшення вимог до пропускної здатності шини, що досягається завдяки великим кешам, такі симетричні багатопроцесорні системи є дуже рентабельними за умови, що існує достатня кількість пропускної здатності у пам'яті».
Розподілені обчислення
Розподілений комп'ютер (також відомий як мультипроцесор з розподіленою пам'яттю) це комп'ютерна система з розподіленою пам'яттю, у якій обчислювальні елементи з'єднані мережею. Розподілені комп'ютери чудово масштабуються.
Кластерні обчислення
Кластер — це група слабо зв'язаних комп'ютерів, що тісно співпрацюють, так що в певною мірою, вони можуть розглядатись як один комп'ютер. Кластери складаються з багатьох окремих машин, з'єднаних мережею. І хоча машини в кластері не мають бути симетричними, якщо вони не є, то це ускладнює балансування навантаження. Найпоширенішим типом кластера є кластер 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
Більшість програм ґрід обчислень використовують проміжне програмне забезпечення, що слугує інтерфейсом між операційною системою, та програмою, та керує ресурсами мережі, і стандартизує інтерфейс. Найпоширенішим програмним забезпеченням цього типу є Berkeley Open Infrastructure for Network Computing (BOINC). Часто програми ґрід обчислень користуються «запасними циклами», виконуючи обчислення під час простою системи. Тому їхні реалізації під виглядом екранних заставок доволі поширені.
Спеціальні паралельні комп'ютери
У галузі паралельних обчислень є спеціальні паралельні пристрої, що займають свої ніші. І хоча вони не є предметно-орієнтованими, та все ж вони зазвичай застосовуються лише для певних класів паралельних задач.
- Обчислення загального призначення на графічних співпроцесорах (GPGPU)
Загальні обчислення на графічних процесорах це порівняно нова тенденція в комп'ютерній інженерії. Графічні процесори — допоміжні процесори, що були сильно оптимізовані для обчислень комп'ютерної графіки. Обчислення в комп'ютерній графіці це галузь, в якій панує паралелізм даних, зокрема операції з матрицями в лінійній алгебрі.
На початку, відеокарти використовували графічні API для виконання свої програм. Щоправда тепер з'явилось кілька нових мов програмування та платформ збудованих для виконання обчислень загального призначення на відеокартах як на середовищах CUDA для Nvidia так і на CMT для AMD. Іншими мовами для загальних обчислень на відеокартах є , , та . Nvidia також випустила спеціальні засоби для обчислень на своїх відеокартах серії Tesla.
Програмне забезпечення
Мови паралельного програмування
Паралельні мови програмування, бібліотеки, API і паралельні моделі програмування, були створені для програмування паралельних комп'ютерів. В цілому їх можна поділити на класи, засновані на припущеннях, основа яких лежить в будові, загальної пам'яті основної пам'яті, розподіленої пам'яті, або загальної розподіленої пам'яті. Однією з концепцій, які використовуються в програмах паралельного програмування, є [en], в якій одна частина програми зобов'язується поставити потрібні дані іншій частині програми в якийсь момент в майбутньому.
та також координують зусилля, щоби зробити директиви гібридного багатоядерного паралельного програмування (англ. hybrid multi-core parallel programming, HMPP) відкритим стандартом під назвою OpenHMPP. Модель програмування на основі директив OpenHMPP пропонує синтаксис ефективного розвантаження обчислень на апаратних прискорювачах і оптимізацію переміщення даних в/з апаратної пам'яті. Директиви OpenHMPP описують виклик віддалених процедур (англ. remote procedure call, RPC) на прискорювані (наприклад, ГП) або, в загальнішому випадку, на наборі ядер. Ці директиви роблять нотатки в коді C або Fortran для опису двох наборів функціональних можливостей: розвантаження процедур (що позначаються codelets) на віддалений пристрій, та оптимізацію передавання даних між основною пам'яттю ЦП та пам'яттю прискорювача.
Автоматичне розпаралелювання
Автоматичне розпаралелювання послідовної програми компілятором є святим граалем паралельних обчислень. Незважаючи на десятиліття роботи дослідниками компіляторів, автоматичне розпаралелювання має обмежений успіх.
Головні мови паралельного програмування залишаються або явно паралельними або (в кращому випадку), частково неявно паралельними, в яких програміст дає директиви для розпаралелювання компілятору. Повністю явно паралельні мови існують — [en], Parallel Haskell, [en], System C (для ПКВМ), , VHDL, і Verilog.
Контрольні точки програми
З ростом складності комп'ютерної системи середній наробіток між відмовами, як правило, зменшується. Контрольні точки програми — це метод, за допомогою якого комп'ютерна система робить «знімок» застосунку, — запис усіх поточних виділених ресурсів і станів змінних, схожий на [en]. Цю інформацію може бути використано для відновлення програми, якщо комп'ютер збійне. Контрольні точки програми дають змогу розпочати з останнього збереження, а не з самого початку. В той час як контрольні точки забезпечують переваги в різних ситуаціях, вони особливо корисні у високорозвинених паралельних системах з великим числом процесорів, використовуваних в області високопродуктивних обчислень.
Алгоритмічні методи
Оскільки паралельні комп'ютери стають все кращі і швидші, стає можливим вирішити проблеми, які раніше займали багато часу. Паралельні обчислення використовується в різних сферах життя, від біоінформатики (згортання білків і аналіз послідовності) до економіки (фінансової математики). Найбільш поширеними типами проблем, виявлених в паралельних обчислювальних є:
- щільна лінійна алгебра;
- розріджена лінійна алгебра;
- спектральні методи (такі як перетворення Кулі-Тьюки швидкого перетворення Фур'є);
- проблеми N-тіла (наприклад, Barnes-Hut моделювання);
- структуровані ґрід проблеми (наприклад, методи Латтісе Больцмана);
- неструктуровані ґрід проблеми (наприклад, знайти в аналізі кінцеві елементи);
- метод Монте Карло;
- комбінаційної логіки (такі як грцби криптографічні методи);
- графік обходу (наприклад, алгоритми сортування);
- динамічне програмування;
- метод гілок і меж;
- графові моделі (наприклад, виявлення прихованих марковських моделей і побудови мереж Байєса);
Відмовостійкість
Паралельні обчислення також можуть бути застосовані до проектування відмовостійких обчислювальних систем, зокрема, за допомогою Lockstep системи, що виконують ті ж операції паралельно. Це забезпечує надлишковість у разі падіння одного з компонентів і також дозволяє автоматично визначати та виправляти помилки якщо результати різняться. Ці методи можуть бути використані, щоб допомогти запобігти поодиноким подіям, які викликають тимчасові помилки. Хоча додаткові заходи можуть знадобитися у вбудованих або спеціалізованих системах, цей метод може забезпечити економічно ефективний підхід до досягнення п-модульної надмірності в комерційних системах.
Історія
Витоки істинної (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.
Див. також
Примітки
- 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» [ 9 грудня 2008 у Wayback Machine.] (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, компанії, що зазвичай асоціюється з позицією — „чим більша частота тим краще“, попереджують, що традиційні підходи до збільшення продуктивності через збільшення тактової частоти досягли своєї межі.»
- Patterson, David A. and John L. Hennessy (1998). Computer Organization and Design, Second Edition, Morgan Kaufmann Publishers, p. 715. .
- Barney, Blaise. Introduction to Parallel Computing. Lawrence Livermore National Laboratory. Архів оригіналу за 29 червня 2013. Процитовано 9 листопада 2007.
- Hennessy, John L. and David A. Patterson (2002). Computer Architecture: A Quantitative Approach. 3rd edition, Morgan Kaufmann, p. 43. .
- Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. .
- Flynn, Laurie J. «Intel Halts Development of 2 New Microprocessors». The New York Times, May 8, 2004. Retrieved on April 22, 2008.
- Moore, Gordon E. (1965). (PDF). . с. 4. Архів оригіналу (PDF) за 18 лютого 2008. Процитовано 11 листопада 2006.
- 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.
- Фред Брукс Міфічний людино-місяць. Розділ 2 — Міфічний людино-місяць.
- Reevaluating Amdahl's Law [ 27 вересня 2007 у Wayback Machine.] (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. .
- Lamport, Leslie (September 1979). «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs», IEEE Transactions on Computers, C-28,9, pp. 690-91.
- Patterson and Hennessy, p. 748.
- Culler, David E.; Jaswinder Pal Singh and Anoop Gupta (1999). Parallel Computer Architecture — A Hardware/Software Approach. Morgan Kaufmann Publishers, p. 15. .
- Culler et al. p. 15.
- Patt, Yale (April 2004). The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? [ 14 квітня 2008 у Wayback Machine.] (wmv). Distinguished Lecturer talk at Carnegie Mellon University. Retrieved on November 7, 2007.
- Culler et al. p. 124.
- Culler et al. p. 125.
- Patterson and Hennessy, p. 713.
- Hennessy and Patterson, p. 549.
- Patterson and Hennessy, p. 714.
- What is clustering? Webopedia computer dictionary.
- Beowulf definition. [ 2012-10-10 у Wayback Machine.] PC Magazine
- Architecture share for 06/2007 [ 14 листопада 2007 у Wayback Machine.]. TOP500 Supercomputing Sites. Clusters make up 74.60 % of the machines on the list. Retrieved on November 7, 2007.
- Hennessy and Patterson, p. 537.
- MPP Definition. [ 2013-05-11 у Wayback Machine.] PC Magazine. Retrieved on November 7, 2007.
- Kirkpatrick, Scott (January 31, 2003). «Computer Science: Rough Times Ahead». Science, Vol. 299. No. 5607, pp. 668 — 669. DOI: 10.1126/science.1081623
- Boggan, Sha'Kia and Daniel M. Pressel (August 2007). GPUs: An Emerging Platform for General-Purpose Computation (PDF). ARL-SR-154, U.S. Army Research Lab. Retrieved on November 7, 2007.
- Patterson and Hennessy, pp. 749–50: «Although successful in pushing several technologies useful in later projects, the ILLIAC IV failed as a computer. Costs escalated from the $8 million estimated in 1966 to $31 million by 1972, despite the construction of only a quarter of the planned machine . It was perhaps the most infamous of supercomputers. The project started in 1965 and ran its first real application in 1976.»
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Paralelni obchislennya ce forma obchislen v yakih kilka dij provodyatsya odnochasno Gruntuyutsya na tomu sho veliki zadachi mozhna rozdiliti na kilka menshih kozhnu z yakih mozhna rozv yazati nezalezhno vid inshih masovo paralelnij superkomp yuter IBM Blue Gene P Ye kilka riznih rivniv paralelnih obchislen bitovij instrukcij danih ta paralelizm zadach Paralelni obchislennya zastosovuyutsya vzhe protyagom bagatoh rokiv v osnovnomu v visokoproduktivnih obchislennyah ale zacikavlennya nim zroslo tilki nedavno cherez fizichni obmezhennya zrostannya chastoti Oskilki i vidpovidno vidilennya tepla komp yuterami stalo problemoyu v ostanni roki paralelne programuvannya staye dominuyuchoyu paradigmoyu v komp yuternij arhitekturi osnovnomu v formi bagatoyadernih procesoriv Paralelni komp yuteri mozhut buti grubo klasifikovani zgidno z rivnem na yakomu aparatne zabezpechennya pidtrimuye paralelizm bagatoyadernist bagatoprocesornist komp yuteri sho mayut bagato obchislyuvalnih elementiv v mezhah odnoyi mashini a takozh klasteri MPP ta grid sistemi sho vikoristovuyut bagato komp yuteriv dlya roboti nad odnim zavdannyam Specializovani paralelni arhitekturi inodi vikoristovuyutsya poryad z tradicijnimi procesorami dlya priskorennya osoblivih zadach Programi dlya paralelnih komp yuteriv pisati znachno skladnishe nizh dlya poslidovnih bo paralelizm dodaye kilka novih klasiv potencijnih pomilok sered yakih najposhirenishoyu ye stan gonitvi Komunikaciya ta sinhronizaciya procesiv zazvichaj odna z najbilshih pereshkod dlya dosyagnennya horoshoyi produktivnosti paralelnih program Maksimalnij mozhlivij pririst produktivnosti paralelnoyi programi viznachayetsya zakonom Amdala PeredumoviKolis paralelne programuvannya bulo spravoyu tilki tih odinakiv yakih cikavili zavdannya dlya velikih superkomp yuteriv Ale teper koli zvichajni dodatki pochali pracyuvati na bagatoyadernih procesorah paralelne programuvannya shvidko staye tehnologiyeyu yaku povinen osvoyiti i vmiti zastosovuvati bud yakij profesijnij rozrobnik PZ Paralelne programuvannya mozhe buti skladnim ale jogo legshe zrozumiti yaksho rahuvati ne vazhkim a prosto trohi inshim Tradicijno programi pishutsya dlya poslidovnih obchislen Dlya rozv yazku zadachi pridumuyut algoritm yakij realizovuyetsya v viglyadi poslidovnosti instrukcij Ci instrukciyi vikonuyutsya odnim procesorom komp yutera U kozhen moment chasu mozhe vikonuvatis tilki odna instrukciya pislya zavershennya yiyi vikonannya pochinayetsya vikonannya nastupnoyi Z inshogo boku v paralelnomu programuvanni odnochasno vikoristovuyut kilka obchislyuvalnih elementiv dlya rozv yazannya odniyeyi zadachi Ce umozhlivlyuyetsya rozbittyam zadachi na pidzadachi kozhna z yakih mozhe buti virishena nezalezhno Procesorni elementi buvayut riznimi ta vklyuchayut rizni resursi yak napriklad odin komp yuter z bagatma procesorami kilka z yednanih u merezhu komp yuteriv specializovane aparatne zabezpechennya chi bud yaku kombinaciyu pererahovanogo vishe buv osnovnim chinnikom zbilshennya produktivnosti komp yuteriv z seredini 1980 tih do 2004 Chas roboti programi dorivnyuye chislu instrukcij pomnozhenomu na serednij chas vikonannya instrukciyi Tomu zbilshennya chastoti zmenshuye chas vikonannya vsih procesorno zalezhnih koli osnovnim resursom vistupaye chas procesora program Tim ne mensh chipu zadayetsya rivnyannyam P C V2 F de P potuzhnist V napruga zhivlennya C yemnist sho perezaryadzhayetsya za odin proporcijna chislu tranzistoriv yaki peremikayutsya u comu takti a F taktova chastota Zbilshennya chastoti zbilshuye potuzhnist sho vikoristovuyetsya procesorom Zbilshennya spozhivanoyi potuzhnosti prizvelo do togo sho v travni 2004 Intel vidminilo rozrobku procesoriv en na yaki zazvichaj posilayutsya yak na znak kincya zbilshennya chastoti yak dominuyuchoyi paradigmi v komp yuternij arhitekturi Zakon Mura ce empirichne sposterezhennya pro te sho shilnist tranzistoriv v mikroprocesorah podvoyuyetsya kozhnih 18 24 misyaci Nezvazhayuchi na problemi zi spozhivannyam energiyi ta postijni peredbachennya kincya zakon Mura vse she pracyuye Z kincem zrostannya chastoti ci dodatkovi tranzistori sho vzhe ne zbilshuyut chastotu budut vikoristovuvatis shob dodati dodatkove aparatne zabezpechennya dlya paralelnih obchislen Zakoni Amdala ta Gustafsona Grafichne zobrazhennya zakonu Amdala Priskorennya programi pri rozparalelyuvanni zalezhit vid togo yaku chastinu programi mozhna vikonuvati paralelno Napriklad yaksho 90 programi mozhna vikonuvati paralelno teoretichnim maksimumom priskorennya pri zapusku yiyi na paralelnij mashini bude desyatikratne nezalezhno vid togo skilki procesoriv vikoristovuyetsya Optimalnim priskorennyam vid rozparalelyuvannya moglo b buti linijne zbilshennya kilkosti procesoriv vdvichi maye vdvichi skorochuvati chas vikonannya Nastupne zbilshennya kilkosti procesoriv vdvichi malo b znovu priskoryuvati programu Tim ne mensh lish kilka paralelnih algoritmiv dosyagayut takogo priskorennya Bilshist z nih mayut majzhe linijne priskorennya pri nevelikij kilkosti procesoriv yake spovilnyuyetsya do konstanti pri velikij kilkosti obchislyuvalnih elementiv Potencijne priskorennya algoritmu pri zbilshenni chisla procesoriv zadayetsya zakonom Amdala sho vpershe buv sformulovanij Dzhinom Amdalem u 1960 tih Vin stverdzhuye sho nevelika chastina programi sho ne piddayetsya paralelizaciyi obmezhit zagalne priskorennya vid rozparalelyuvannya Bud yaka velika matematichna chi inzhenerna zadacha zazvichaj bude skladatis z kilkoh chastin sho mozhut vikonuvatis paralelno ta kilkoh chastin sho vikonuyutsya tilki poslidovno Cej zv yazok zadayetsya rivnyannyam S 1 1 P displaystyle S frac 1 1 P De S displaystyle S priskorennya programi yak vidnoshennya do yiyi pochatkovogo chasu roboti a P displaystyle P chastka yaku mozhna vikonuvati paralelno Yaksho poslidovna chastina programi vikonuyetsya 10 vsogo chasu roboti mi ne mozhemo priskoritis bilsh nizh v 10 raziv nezalezhno vid togo skilki procesoriv zastosuyemo Ce stavit verhnyu mezhu korisnosti zbilshennya kilkosti obchislyuvalnih elementiv Koli zadacha ne mozhe rozparalelyuvatis cherez obmezhennya poslidovnoyi chastini prikladannya dodatkovih zusil ne maye niyakogo efektu dlya rozkladu Shob vinositi ditinu potribno dev yat misyaciv nezalezhno vid togo skilki zhinok cim zajmayutsya Zakon Gustafsona ce inshij komp yuternij zakon sho silno pov yazanij z zakonom Amdala Jogo mozhna sformulyuvati tak Pripustimo sho zadacha maye dvi nezalezhni chastini A ta B B zajmaye 25 chasu obchislen Doklavshi pevnih zusil programist mozhe zrobiti cyu chastinu v p yat raziv shvidshoyu ale ce nenabagato zmenshit chas vsogo obchislennya Tim ne mensh mozhlivo dlya togo shob priskoriti chastinu A vdvichi potribno menshe zusil ale ce priskorit vikonannya vsiyeyi programi nabagato silnishe nizh optimizaciya B popri te sho B mozhna optimizuvati silnishe S P P a P 1 displaystyle S P P alpha P 1 de P displaystyle P ce kilkist procesoriv S displaystyle S priskorennya a a displaystyle alpha nerozparalelyuvana chastina procesu Zakon Amdala bazuyetsya na pripushenni togo sho zadacha maye fiksovanij rozmir i sho rozmir poslidovnoyi chastini nezalezhnij vid kilkosti procesoriv v toj chas yak zakon Gustafsona ne robit takih pripushen Zalezhnosti Rozuminnya zalezhnostej danih duzhe vazhlive dlya rozrobki paralelnih algoritmiv Zhodna programa ne mozhe pracyuvati shvidshe nizh najdovshij lancyug zalezhnih obchislen vidomij yak bo obchislennya sho zalezhat vid poperednih obchislen v lancyugu mayut vikonuvatis odne za odnim Tim ne mensh bilshist algoritmiv ne skladayutsya lish z dovgogo lancyuga zalezhnih obchislen zazvichaj ye shansi vikonuvati nezalezhni obchislennya paralelno Haj P i displaystyle P i ta P j displaystyle P j dva fragmenti programi Umovi Bernshtejna opisuyut koli voni paralelni ta mozhut vikonuvatis paralelno Dlya P i displaystyle P i haj I i displaystyle I i vhidni zminni a O i displaystyle O i vihidni Dlya P j displaystyle P j analogichno P i displaystyle P i ta P j displaystyle P j nezalezhni koli voni zadovolnyayut taki umovi I j O i displaystyle I j cap O i varnothing I i O j displaystyle I i cap O j varnothing O i O j displaystyle O i cap O j varnothing Porushennya pershoyi umovi stvoryuye zalezhnist potoku rezultat roboti pershoyi chastini vikoristovuyetsya drugoyu Druga umova predstavlyaye antizalezhnist koli druga chastina programi perepisuye zminnu sho potribna pershij programi Tretya ta ostannya umova predstavlyaye zalezhnist vivodiv koli dvi chastini programi zapisuyut dani v odnu j tu zh zminnu kincevij rezultat maye otrimuvatis vid chastini sho logichno vikonuyetsya ostannoyu Davajte pridumayemo deyaki funkciyi sho demonstruyut kilka tipiv zalezhnostej 1 function Dep a b 2 c a b 3 d 2 c Operator 3 v Dep a b ne mozhe buti vikonanim pered chi navit odnochasno z operatorom 2 bo operaciya 3 vikoristovuye rezultat roboti operaciyi 2 Vona porushuye umovu 1 tomu mayemo zalezhnist potoku 1 function NoDep a b 2 c a b 3 d 2 b 4 e a b V comu prikladi mizh operaciyami nemaye zalezhnostej tomu voni mozhut vikonuvatis paralelno Umovi Bernshtejna ne dozvolyayut diliti pam yat mizh riznimi procesami Tomu potribne primusove vporyadkuvannya dostupu do danih yak semafori bar yeri ta inshi metodi sinhronizaciyi Stan gonitvi vzayemne viklyuchennya sinhronizaciya ta paralelne spovilnennya Pidzadachi v paralelnij programi chasto nazivayut nitkami Deyaki paralelni arhitekturi vikoristovuyut menshi legshi versiyi nitok sho nazivayutsya voloknami v toj chas yak inshi vikoristovuyut bilshi versiyi sho nazivayutsya procesami Tim ne mensh nitki zazvichaj prijmayutsya yak zagalnij termin dlya pidzadach Nitki chasto potrebuyut sinhronizaciyi napriklad dlya onovlennya deyakih zminnih sho dilyatsya mizh nimi Bez sinhronizaciyi instrukciyi dvoh nitok mozhut cherguvatisya u bud yakomu poryadku Napriklad haj mayemo taku programu Nit A Nit B 1A Prochitati zminnu V 1B Prochitati zminnu V 2A Dodati 1 do zminnoyi V 2B Dodati 1 do zminnoyi V 3A Zapisati nazad u zminnu V 3B Zapisati nazad u zminnu V Yaksho instrukciya 1B vikonayetsya mizh 1A ta 3A chi yaksho instrukciya 1A vikonayetsya mizh 1B ta 3B programa bude produkuvati nepravilni dani Ce vidome yak stan gonitvi Programist maye vikoristovuvati blokuvannya angl lock shob stvoriti vzayemne viklyuchennya Zamok ce konstrukciya movi programuvannya sho dozvolyaye odnij niti otrimati kontrol nad zminnoyu i zapobigti chitannyu chi zapisu v cyu zminnu vid inshih nitok azh poki cya zminna ne bude rozblokovana Nit sho stvorila zamok mozhe vilno vikonuvati svoyu kritichnu sekciyu sekciyu programi sho vimagaye eksklyuzivnogo dostupu do pevnoyi zminnoyi i rozblokuvati dani koli sekciya zakinchitsya Tomu shob garantuvati pravilne vikonannya programa dana vishe mozhe buti perepisana z vikoristannyam zamkiv Nit A Nit B 1A Zamknuti zminnu V 1B Zamknuti zminnu V 2A Prochitati zminnu V 2B Prochitati zminnu V 3A Dodati 1 do zminnoyi V 3B Dodati 1 do zminnoyi V 4A Zapisati nazad u zminnu V 4B Zapisati nazad u zminnu V 5A Rozblokuvati zminnu V 5B Rozblokuvati zminnu V Odna nit uspishno zablokuye zminnu V poki insha bude zamknena ne zmozhe prodovzhiti robotu poki V ne rozblokuyetsya Ce garantuvatime pravilne vikonannya programi Zamki neobhidni shob garantuvati korektne vikonannya programi ale mozhut silno yiyi spovilniti Blokuvannya bagatoh zminnih z vikoristannyam neatomarnih zamkiv stvoryuye mozhlivist vzayemnogo blokuvannya Atomarnij zamok zamikaye vsi zminni za raz Yaksho vin ne mozhe zamknuti vsi z nih vin ne zamikaye zhodnoyi Yaksho dvi niti potrebuyut zamknuti odnakovi dvi zminni vikoristovuyuchi neatomarni zamki mozhlivij vipadok koli odna nit zamikaye odnu zminnu a insha drugu V takomu vipadku zhodna z nitej ne mozhe prodovzhuvati robotu sho privodit do vzayemnogo blokuvannya Bagato paralelnih program vimagayut togo shob yihni pidzadachi vikonuvalis sinhronno Ce potrebuye vikoristannya bar yera Bar yeri zazvichaj realizuyutsya z vikoristannyam programnogo zamka Odin klas algoritmiv sho vidomi pid nazvoyu angl lack free and wait free algorithms unikayut vikoristannya zamkiv ta bar yeriv Pravda takij pidhid zazvichaj vazhko realizuvati i vimagaye pravilno skonstrujovanih struktur danih Ne kozhne rozparalelyuvannya sprichinyuye priskorennya Zagalom koli zadacha rozbivayetsya na bilshe ta bilshe nitok ti nitki vitrachayut vse bilshe i bilshe chasu na komunikaciyi mizh soboyu Zreshtoyu chas na komunikaciyu perevazhaye chas sho vitrachayetsya na rozv yazannya zadachi i podalshe rozparalelyuvannya podil na she bilshu kilkist nitok skorishe zbilshuye anizh zmenshuye protyazhnist chasu potribnogo shob zakinchiti robotu Ce vidome yak paralelne spovilnennya Dribnozernistij krupnozernistij ta prigolomshlivij paralelizm Programi chasto klasifikuyutsya vidpovidno do togo yak chasto yihni pidzadachi mayut sinhronizuvatis chi spilkuvatis odin z odnim Programa proyavlyaye dribnozernistij paralelizm yaksho yiyi pidzadachi mayut obminyuvatis danimi bagato raziv na sekundu vona proyavlyaye krupnozernistij paralelizm yaksho voni ne musyat obminyuvatis danimi bagato raziv na sekundu i vona proyavlyaye prigolomshlivij paralelizm yaksho voni ridko chi vzagali nikoli ne mayut obminyuvatis danimi Prigolomshlivo paralelni programi vvazhayutsya takimi sho rozparalelyuyutsya najlegshe Modeli uzgodzhenosti Dokladnishe Model uzgodzhenosti ta Model paralelnih obchislen Paralelni movi programuvannya ta paralelni komp yuteri mayut mati model uzgodzhenosti takozh vidomu yak model pam yati Model uzgodzhenosti opisuye pravila provedennya riznomanitnih operacij z pam yattyu ta sho mi otrimuyemo v rezultati cih operacij Odniyeyu z pershih modelej uzgodzhenosti bula model poslidovnoyi shilnosti Lesli Lamporta Poslidovna uzgodzhenist ce vlastivist paralelnoyi programi davati takij samij rezultat sho i yiyi poslidovnij analog Konkretnishe programa poslidovno uzgodzhena yaksho rezultat bud yakogo zapusku takij samij yak buv bi yaksho operaciyi na kozhnomu okremomu procesori vikonuvalis tak nibi voni vikonuyutsya v pevnij poslidovnosti zadanij programoyu Tranzakcijna pam yat ce tipovij priklad modeli uzgodzhenosti Tranzakcijna pam yat vzyala u teoriyi baz danih princip atomarnoyi tranzakciyi ta zastosuvala jogo pri dostupi do pam yati Matematichno ci modeli mozhut predstavlyatis kilkoma sposobami Merezhi Petri sho buli vpershe predstavleni Karlom Adamom Petri u 1962 gomu buli rannimi sprobami sistematizuvati pravila uzgodzhenosti modelej Na yihnij osnovi pobudovana teoriya potokiv danih a yihnya arhitektura bula stvorena shob realizuvati ideyi ciyeyi teoriyi fizichno Pochinayuchi z kincya 1970 h buli rozrobleni taki yak ta Poslidovni Procesi sho Spilkuyutsya shob umozhliviti algebrayichne obgruntuvannya sistem skladenih z vzayemodiyuchih komponentiv Novishi dopovnennya do sim yi chislen procesiv taki yak p chislennya dodali mozhlivist obgruntuvannya dinamichnih topologij Taki logiki yak ta matematichni modeli taki yak ta takozh buli rozvineni shob opisati povedinku konkurentnih sistem Taksonomiya Flinna Majkl Dzh Flinn stvoriv odnu z najpershih klasifikacij sistem paralelnih ta poslidovnih komp yuteriv ta program sho nini vidoma yak Taksonomiya Flinna Flinn podilyav programi ta komp yuterami zalezhno vid togo chi voni vikoristovuvali odin chi bagato potokiv komand ta chi komandi operuvali odnim chi bagatma mnozhinami danih Klasifikaciya Flinna Odinochnij potik instrukcij Single Instruction Mnozhinnij potik instrukcij Multiple Instruction Odinochnij potik danih Single Data SISD MISD Mnozhinnij potik danih Multiple Data SIMD MIMD Cej shablon pereglyanutiredaguvati Klas single instruction single data SISD ekvivalentnij cilkovito poslidovnij programi Single instruction multiple data SIMD ekvivalentnij vikonannyu odniyeyi ta tiyeyi zh operaciyi povtoryuvano nad velikim masivom danih Ce zazvichaj vidbuvayetsya u zadachah obrobki signaliv Klas Multiple instruction single data MISD vikoristovuyetsya ridko Poki pridumuvalis arhitekturi sho stosuyutsya cogo klasu yak napriklad sistolichni masivi z yavilos lishe kilka program sho pidpadayut pid cej klas Multiple instruction multiple data MIMD najtipovishi predstavniki paralelnih program Zgidno z Devidom Pattersonom ta Dzhonom Gennesi Deyaki mashini ye gibridami cih kategorij shopravda cya klasichna model vizhila cherez te sho vona prosta legka dlya rozuminnya ta daye garne pershe nablizhennya Vona takozh mozhlivo cherez yiyi zrozumilist najposhirenisha shema Rivni paralelizmuParalelizm bitovogo rivnya Dokladnishe Paralelizm bitovogo rivnya Z vinajdennyam u 1970 tih tehnologiyi stvorennya nadvelikih integralnih shem priskorennya v komp yuternij arhitekturi vidbuvalos z dopomogoyu podvoyennya rozmiru mashinnogo slova kilkosti informaciyi yaku komp yuter mozhe obroblyati za odin cikl Zbilshennya rozmiru slova zmenshuye kilkist instrukcij neobhidnih vikonati operaciyu nad danimi chij rozmir bilshij nizh rozmir vhidnogo slova Napriklad koli vosmibitnij procesor maye dodati dva shistnadcyatirozryadni chisla procesor maye spochatku dodati 8 bit nizhchogo rozryadu z kozhnogo chisla vikoristovuyuchi standartnu instrukciyu dodavannya potim dodati 8 bitiv vishogo rozryadu vikoristovuyuchi instrukciyu dodavannya z perenosom ta bit perenosu vid vikonannya poperednogo dodavannya Tomu vosmibitnij procesor potrebuye dvi instrukciyi dlya vikonannya odniyeyi operaciyi v toj chas yak shistnadcyatibitnij lish odnu Istorichno buli zamineni na vosmirozryadni potim na shistnadcyatirozryadni potim na 32 h rozryadni Cya tendenciya pripinilas z vvedennyam tridcyatidvohrozryadnih procesoriv yaki stali standartom dlya personalnih komp yuteriv na dva desyatilittya Azh poki nedavno 2003 2004 z vinajdennyam arhitekturi x86 64 ne z yavilis 64 x rozryadni procesori Paralelizm rivnya instrukcij Dokladnishe Paralelizm na rivni komand Standartnij p yatikrokovij konveyer v mashini RISC IF Instruction Fetch ID Instruction Decode EX Execute MEM Memory access WB Register write back Komp yuterna programa po suti ye potokom instrukcij sho vikonuyutsya procesorom Inodi ci instrukciyi mozhna perevporyadkuvati ta ob yednati v grupi yaki potim vikonuvati paralelno bez zmini rezultatu roboti programi sho vidomo yak paralelizm na rivni instrukcij Takij pidhid do zbilshennya produktivnosti obchislen perevazhav z seredini 80 tih do seredini 90 tih Suchasni procesori mayut bagatoetapni konveyeri komand Kozhen etap konveyera vidpovidaye inshij diyi sho vikonuye procesor Procesor sho maye konveyer z N stupenyami mozhe odnochasno obroblyati N instrukcij kozhnu na inshij stadiyi obrobki Klasichnim prikladom procesora z konveyerom ye procesor arhitekturi RISC sho maye p yat etapiv zavantazhennya instrukciyi dekoduvannya vikonannya dostup do pam yati ta zapis rezultatu Procesor Pentium 4 maye konveyer z 35 etapami Superskalyarnij p yatietapnij konveyernij mikroprocesor sho zdaten vikonuvati dvi instrukciyi za cikl Vin mozhe zberigati dvi instrukciyi na kozhnij stadiyi konveyera takim chinom zagalom vikonuyuchi desyat instrukcij vodnochas Na dodachu do paralelizmu na rivni instrukcij deyaki procesori mozhut vikonuvati bilsh nizh odnu instrukciyu za raz Voni vidomi yak superskalyarni procesori Instrukciyi grupuyutsya razom yaksho mizh nimi ne isnuye zalezhnosti danih Shob realizuvati paralelizm na rivni instrukcij vikoristovuyut algoritmi ta Tomasulo algorithm yakij analogichnij do poperednogo prote vikoristovuye perejmenuvannya registriv Paralelizm danih Dokladnishe Paralelizm danih Paralelizm danih ce paralelizm vlastivij ciklam program yaki fokusuyutsya na dostavci danih riznim obchislyuvalnim vuzlam dlya paralelnoyi obrobki Rozparalelyuvannya cikliv chasto privodit do podibnih ne obov yazkovo identichnih poslidovnostej operacij chi obchislennya funkcij nad elementami velikih struktur danih Bagato naukovih ta inzhenernih program proyavlyayut paralelizm danih Ciklichna zalezhnist zalezhnist iteraciyi ciklu vid rezultativ poperednoyi chi kilkoh poperednih iteracij Ciklichni zalezhnosti pereshkodzhayut rozparalelyuvannyu cikliv Rozglyanemo psevdokod sho obchislyuye kilka pershih chisel fibonachchi 1 PREV1 0 2 PREV2 1 4 do 5 CUR PREV1 PREV2 6 PREV1 PREV2 7 PREV2 CUR 8 while CUR lt 10 Takij cikl ne mozhe buti rozparalelenij bo CUR zalezhit vid sebe PREV2 ta PREV1 yaki obchislyuyutsya v kozhnij iteraciyi Tomu kozhna iteraciya zalezhit vid rezultativ poperednoyi voni ne mozhut vikonuvatis paralelno Koli rozmir zadachi staye bilshim kilkist dostupnih dlya rozparalelyuvannya danih zazvichaj tezh zrostaye Paralelizm zadach Dokladnishe Paralelizm zadach harakteristika paralelnoyi programi yaka polyagaye v tomu sho cilkom rizni obchislennya mozhut vikonuvatis nad odnimi chi riznimi danimi Ce vidriznyaye paralelizm zadach vid paralelizmu danih pri yakomu odne i te zh obchislennya vikonuyetsya nad odnimi i timi zh danimi Paralelizm zadach zazvichaj ne zrostaye zi zrostannyam rozmiru zadachi Aparatne zabezpechennyaPam yat ta komunikaciyi Osnovnoyu pam yattyu v paralelnomu komp yuteri ye yak spilna pam yat rozpodilena mizh vsima obchislyuvalnimi elementami v odnomu adresnomu prostori chi v yakij kozhen obchislyuvalnij element maye svij vlasnij lokalnij adresnij prostir Rozpodilena pam yat vidsilayetsya do togo faktu sho pam yat ye logichno podilenoyu hocha chasto natyakaye i na te sho vona takozh rozdilena i fizichno ta kombinuyut obidva pidhodi de obchislyuvalnij element maye svoyu vlasnu lokalnu pam yat ta dostup do pam yati inshih procesoriv Dostup do lokalnoyi pam yati zazvichaj shvidshij nizh dostup do nelokalnoyi Struktura arhitekturi Non Uniform Memory Access NUMA Procesori v odnij direktoriyi mozhut otrimati dostup do pam yati tiyeyi direktoriyi za menshij chas nizh v inshih direktoriyah Komp yuterni arhitekturi v yakih dostup do kozhnogo elementu osnovnoyi pam yati zajmaye odnakovij chas ta trafik nazivayutsya sistemami z odnoridnim dostupom do pam yati UMA Zazvichaj ce dosyagayetsya tilki z spilnoyu pam yattyu v yakij pam yat ne ye fizichno rozpodilena Sistema sho ne volodiye takoyu vlastivistyu nazivayetsya arhitekturoyu z neodnoridnim dostupom do pam yati Non Uniform Memory Access NUMA Sistemi z rozpodilenoyu pam yattyu mayut neodnoridnij dostup do pam yati Komp yuterni sistemi vikoristovuyut malenki shvidki kesh pam yati sho rozmishuyutsya blizko do procesora ta zberigayut timchasovi kopiyi zminnih pam yati yak u fizichnomu tak i logichnomu smislah Paralelni komp yuteri mayut problemi z keshami sho mozhut zberigati odni i ti zh znachennya v kilkoh miscyah sho stvoryuye mozhlivosti dlya nepravilnogo vikonannya obchislen Taki komp yuteri vimagayut sistemu kogerenciyi keshu yaka slidkuye za keshovanimi zminnimi ta vchasno ochishuye yih zabezpechuyuchi korektne vikonannya programi en odin z najzagalnishih metodiv slidkuvannya za tim yaki zminni vikoristovuyutsya ta yaki treba zachistiti Konstruyuvannya velikih produktivnih sistem kogerenciyi keshu ye skladnoyu zadacheyu z galuzi komp yuternih arhitektur V rezultati arhitekturi z spilnoyu pam yattyu ne masshtabuyutsya tak dobre yak z rozpodilenoyu pam yattyu Komunikaciya mizh procesorami ta mizh procesorami ta pam yattyu mozhe buti realizovana aparatno kilkoma sposobami vklyuchayuchi spilnu multiportovu chi Multipleksnu pam yat matrichnij peremikach spilnu shinu chi merezha odniyeyi z tisyach vklyuchayuchi zirku kilce derevo giperkub zhirnij giperkub giperkub z bilsh nizh odnim procesorom u vershini chi n vimirnu sitku Paralelni komp yuteri sho bazuyutsya na zv yazanih merezhah mayut mati pevnu marshrutizaciyu shob zabezpechiti peredavannya povidomlen mizh elementami sho ne ye zv yazani napryamu Media sho vikoristovuyetsya dlya zv yazku procesoriv chasto buvaye iyerarhichnim u velikih bagatoprocesornih mashinah Vidi paralelnih komp yuteriv Paralelni komp yuteri mozhna grubo klasifikuvati za rivnem na yakomu aparatne zabezpechennya pidtrimuye paralelizm Taka klasifikaciya majzhe analogichna vidstani mizh osnovnimi obchislyuvalnimi elementami Bagatoyaderni obchislennya Dokladnishe Bagatoyadernij procesor ce procesor sho mistit kilka yader Ci procesori vidriznyayutsya vid superskalyarnih procesoriv yaki mozhut vikonuvati kilka instrukcij za takt z odnogo potoku instrukcij nitki na vidminu vid bagatoyadernih sho mozhut za takt vikonuvati kilka instrukcij z riznih nitok Kozhne yadro bagatoyadernogo procesora potencijno mozhe buti superskalyarnim tobto vikonuvati po kilka instrukcij z odnoyi nitki najvidomishoyu z yakih ye tehnologiya HyperThreading vid Intel bula rannoyu formoyu psevdo bagatoyadernosti Procesor sho zdaten do sinhronnoyi bagatonitevosti maye lish odne yadro ale pri prostoyah yadra napriklad pid chas ochikuvannya pidvantazhennya danih v stek vikoristovuye ce yadro dlya roboti z inshoyu nittyu vid IBM sho stvorenij dlya vikoristannya v konsolyah Sony PlayStation 3 ye inshim prikladom bagatoyadernogo procesora Simetrichna bagatoprocesornist Dokladnishe Simetrichnij multiprocesor SMP ce komp yuterna sistema z bagatma identichnimi procesorami sho podilyayut pam yat ta z yednuyutsya cherez shinu en angl bus contention pereshkodzhaye masshtabuvannyu shinnih arhitektur V rezultati SMP zazvichaj ne mistit bilshe 32 x procesoriv Cherez malij rozmir procesoriv ta znachne zmenshennya vimog do propusknoyi zdatnosti shini sho dosyagayetsya zavdyaki velikim kesham taki simetrichni bagatoprocesorni sistemi ye duzhe rentabelnimi za umovi sho isnuye dostatnya kilkist propusknoyi zdatnosti u pam yati Rozpodileni obchislennya Dokladnishe Rozpodileni obchislennya Rozpodilenij komp yuter takozh vidomij yak multiprocesor z rozpodilenoyu pam yattyu ce komp yuterna sistema z rozpodilenoyu pam yattyu u yakij obchislyuvalni elementi z yednani merezheyu Rozpodileni komp yuteri chudovo masshtabuyutsya Klasterni obchislennya Dokladnishe Komp yuternij klaster Klaster Beowulf Klaster ce grupa slabo zv yazanih komp yuteriv sho tisno spivpracyuyut tak sho v pevnoyu miroyu voni mozhut rozglyadatis yak odin komp yuter Klasteri skladayutsya z bagatoh okremih mashin z yednanih merezheyu I hocha mashini v klasteri ne mayut buti simetrichnimi yaksho voni ne ye to ce uskladnyuye balansuvannya navantazhennya Najposhirenishim tipom klastera ye klaster Beowulf yakij ye klasterom realizovanim na bagatoh identichnih fabrichnih komp yuterah z yednanih v lokalnu merezhu TCP IP Ethernet Vpershe tehnologiyu Beowulf rozrobili ta Bilshist superkomp yuteriv zi spisku TOP500 ye klasterami Masovo paralelni obchislennya Dokladnishe Masovo paralelni obchislennya Masivno paralelnij procesor MPP ce odin komp yuter z bagatma procesorami z yednanimi v merezhu MPP mayut bagato spilnogo z klasterami ta MPP mayut specializovani z yednuvalni merezhi todi yak klasteri vikoristovuyut storonnye obladnannya dlya merezhi MPP takozh v osnovnomu bilshi nizh klasteri zazvichaj mayut nabagato bilshe nizh 100 procesoriv V MPP kozhen procesor maye svoyu vlasnu pam yat ta kopiyu operacijnoyi sistemi z programami Kozhna pidsistema spilkuyetsya z inshoyu cherez visokoshvidkisne z yednannya Shafka Blue Gene L sho maye rejting chetvertogo najshvidshogo superkomp yutera u sviti zgidno z rejtingom TOP500 11 2008 Blue Gene L masivno paralelnij procesor Blue Gene L maye rejting chetvertogo najshvidshogo superkomp yutera u sviti zgidno z rejtingom TOP500 11 2008 Blue Gene L masivno paralelnij procesor Obchislennya Grid Dokladnishe Grid merezhi Obchislennya Grid najbilsh rozpodilena forma paralelnih obchislen Vona vikoristovuye dlya rozv yazannya zadachi zv yazani merezheyu Internet komp yuteri Cherez nizku shvidkist peredachi danih ta vidnosno velikij chas dostupu do danih v Internet grid obchislennya provodyat tilki dlya prigolomshlivo paralelnih zadach najvidomishimi z yakih ye SETI home ta Folding Home Bilshist program grid obchislen vikoristovuyut promizhne programne zabezpechennya sho sluguye interfejsom mizh operacijnoyu sistemoyu ta programoyu ta keruye resursami merezhi i standartizuye interfejs Najposhirenishim programnim zabezpechennyam cogo tipu ye Berkeley Open Infrastructure for Network Computing BOINC Chasto programi grid obchislen koristuyutsya zapasnimi ciklami vikonuyuchi obchislennya pid chas prostoyu sistemi Tomu yihni realizaciyi pid viglyadom ekrannih zastavok dovoli poshireni Specialni paralelni komp yuteri U galuzi paralelnih obchislen ye specialni paralelni pristroyi sho zajmayut svoyi nishi I hocha voni ne ye predmetno oriyentovanimi ta vse zh voni zazvichaj zastosovuyutsya lishe dlya pevnih klasiv paralelnih zadach Obchislennya zagalnogo priznachennya na grafichnih spivprocesorah GPGPU Dokladnishe GPGPU Videokarta Nvidia Tesla Zagalni obchislennya na grafichnih procesorah ce porivnyano nova tendenciya v komp yuternij inzheneriyi Grafichni procesori dopomizhni procesori sho buli silno optimizovani dlya obchislen komp yuternoyi grafiki Obchislennya v komp yuternij grafici ce galuz v yakij panuye paralelizm danih zokrema operaciyi z matricyami v linijnij algebri Na pochatku videokarti vikoristovuvali grafichni API dlya vikonannya svoyi program Shopravda teper z yavilos kilka novih mov programuvannya ta platform zbudovanih dlya vikonannya obchislen zagalnogo priznachennya na videokartah yak na seredovishah CUDA dlya Nvidia tak i na CMT dlya AMD Inshimi movami dlya zagalnih obchislen na videokartah ye ta Nvidia takozh vipustila specialni zasobi dlya obchislen na svoyih videokartah seriyi Tesla Programne zabezpechennyaMovi paralelnogo programuvannya Dokladnishe Movi paralelnogo programuvannya Paralelni movi programuvannya biblioteki API i paralelni modeli programuvannya buli stvoreni dlya programuvannya paralelnih komp yuteriv V cilomu yih mozhna podiliti na klasi zasnovani na pripushennyah osnova yakih lezhit v budovi zagalnoyi pam yati osnovnoyi pam yati rozpodilenoyi pam yati abo zagalnoyi rozpodilenoyi pam yati Odniyeyu z koncepcij yaki vikoristovuyutsya v programah paralelnogo programuvannya ye en v yakij odna chastina programi zobov yazuyetsya postaviti potribni dani inshij chastini programi v yakijs moment v majbutnomu ta takozh koordinuyut zusillya shobi zrobiti direktivi gibridnogo bagatoyadernogo paralelnogo programuvannya angl hybrid multi core parallel programming HMPP vidkritim standartom pid nazvoyu OpenHMPP Model programuvannya na osnovi direktiv OpenHMPP proponuye sintaksis efektivnogo rozvantazhennya obchislen na aparatnih priskoryuvachah i optimizaciyu peremishennya danih v z aparatnoyi pam yati Direktivi OpenHMPP opisuyut viklik viddalenih procedur angl remote procedure call RPC na priskoryuvani napriklad GP abo v zagalnishomu vipadku na nabori yader Ci direktivi roblyat notatki v kodi C abo Fortran dlya opisu dvoh naboriv funkcionalnih mozhlivostej rozvantazhennya procedur sho poznachayutsya codelets na viddalenij pristrij ta optimizaciyu peredavannya danih mizh osnovnoyu pam yattyu CP ta pam yattyu priskoryuvacha Avtomatichne rozparalelyuvannya Dokladnishe Avtomatichne rozparalelyuvannya Avtomatichne rozparalelyuvannya poslidovnoyi programi kompilyatorom ye svyatim graalem paralelnih obchislen Nezvazhayuchi na desyatilittya roboti doslidnikami kompilyatoriv avtomatichne rozparalelyuvannya maye obmezhenij uspih Golovni movi paralelnogo programuvannya zalishayutsya abo yavno paralelnimi abo v krashomu vipadku chastkovo neyavno paralelnimi v yakih programist daye direktivi dlya rozparalelyuvannya kompilyatoru Povnistyu yavno paralelni movi isnuyut en Parallel Haskell en System C dlya PKVM VHDL i Verilog Kontrolni tochki programi Dokladnishe Kontrolni tochki programi Z rostom skladnosti komp yuternoyi sistemi serednij narobitok mizh vidmovami yak pravilo zmenshuyetsya Kontrolni tochki programi ce metod za dopomogoyu yakogo komp yuterna sistema robit znimok zastosunku zapis usih potochnih vidilenih resursiv i staniv zminnih shozhij na en Cyu informaciyu mozhe buti vikoristano dlya vidnovlennya programi yaksho komp yuter zbijne Kontrolni tochki programi dayut zmogu rozpochati z ostannogo zberezhennya a ne z samogo pochatku V toj chas yak kontrolni tochki zabezpechuyut perevagi v riznih situaciyah voni osoblivo korisni u visokorozvinenih paralelnih sistemah z velikim chislom procesoriv vikoristovuvanih v oblasti visokoproduktivnih obchislen Algoritmichni metodiOskilki paralelni komp yuteri stayut vse krashi i shvidshi staye mozhlivim virishiti problemi yaki ranishe zajmali bagato chasu Paralelni obchislennya vikoristovuyetsya v riznih sferah zhittya vid bioinformatiki zgortannya bilkiv i analiz poslidovnosti do ekonomiki finansovoyi matematiki Najbilsh poshirenimi tipami problem viyavlenih v paralelnih obchislyuvalnih ye shilna linijna algebra rozridzhena linijna algebra spektralni metodi taki yak peretvorennya Kuli Tyuki shvidkogo peretvorennya Fur ye problemi N tila napriklad Barnes Hut modelyuvannya strukturovani grid problemi napriklad metodi Lattise Bolcmana nestrukturovani grid problemi napriklad znajti v analizi kincevi elementi metod Monte Karlo kombinacijnoyi logiki taki yak grcbi kriptografichni metodi grafik obhodu napriklad algoritmi sortuvannya dinamichne programuvannya metod gilok i mezh grafovi modeli napriklad viyavlennya prihovanih markovskih modelej i pobudovi merezh Bajyesa VidmovostijkistDokladnishe Paralelni obchislennya takozh mozhut buti zastosovani do proektuvannya vidmovostijkih obchislyuvalnih sistem zokrema za dopomogoyu Lockstep sistemi sho vikonuyut ti zh operaciyi paralelno Ce zabezpechuye nadlishkovist u razi padinnya odnogo z komponentiv i takozh dozvolyaye avtomatichno viznachati ta vipravlyati pomilki yaksho rezultati riznyatsya Ci metodi mozhut buti vikoristani shob dopomogti zapobigti poodinokim podiyam yaki viklikayut timchasovi pomilki Hocha dodatkovi zahodi mozhut znadobitisya u vbudovanih abo specializovanih sistemah cej metod mozhe zabezpechiti ekonomichno efektivnij pidhid do dosyagnennya p modulnoyi nadmirnosti v komercijnih sistemah IstoriyaDokladnishe Istoriya obchislyuvalnoyi tehniki en Najsumnozvisnishij superkomp yuter Vitoki istinnoyi MIMD paralelnosti pishli vid Luyidzhi Federiko Menabrea i jogo Eskizu Vinajdenogo Charlzom Bebbidzhem U kvitni 1958 roku S Gill Ferranti obgovorili paralelne programuvannya i neobhidnist rozgaluzhennya i ochikuvannya Krim togo v 1958 roci doslidniki IBM Dzhon Kok i Daniel Slotnik vpershe obgovorili vikoristannya paralelizmu v chislennih rozrahunkah Burroughs Corporation predstavila D825 v 1962 roci chotiroh procesornij komp yuter vin nadavav dostup do 16 moduliv pam yati cherez komutator U 1967 roci Amdal i Slotnik opublikuvali diskusiyu pro mozhlivist paralelnoyi obrobki na konferenciyi Amerikanskoyi federaciyi tovaristv z obrobki informaciyi Same v hodi ciyeyi diskusiyi buv pridumanij zakon Amdalya shob viznachiti mezhu priskorennya zavdyaki paralelnosti U 1969 roci kompaniya Honeywell predstavila svoyu pershu Multics simetrichnu sistemu multimikrokontrollernu zdatnu pracyuvati do vosmi procesoriv paralelno Z 1970 h rokiv bagatoprocesornij proekt Universitetu Karnegi Mellona buv odnim z pershih multiprocesoriv z bilsh nizh kilkoma procesorami Istoriyu paralelnih komp yuteriv SIMD mozhna prostezhiti z 1970 h rokiv Motivaciyeyu rannih komp yuteriv SIMD buv amortizuvati zatrimku upravlinnya procesora kilkoma instrukciyami U 1964 roci Slotnik zaproponuvav buduvati MVS dlya Livermorskoyi nacionalnoyi laboratoriyi Jogo proekt buv profinansovanij VVS SShA Klyuchem do jogo konstrukciyi buv dosit visokij paralelizm azh do 256 procesoriv sho dozvolilo mashinam pracyuvati na velikih naborah danih v tomu sho piznishe bude vidome yak vektor obrobki Prote ILLIAC IV buv nazvanij samim sumnozvisnoyi superkomp yuteriv tomu sho proekt buv tilki na chvert zavershenij ale pishlo 11 rokiv i koshtuvav majzhe v chotiri razi bilshe pervisnoyi ocinki Koli vin nareshti gotovij do zapusku pershij realne zastosuvannya v 1976 roci vin progravav isnuyuchim komercijnim superkomp yuteram takim yak Cray 1 Div takozhModel paralelnih obchislenPrimitkiAlmasi G S and A Gottlieb 1989 Highly Parallel Computing Benjamin Cummings publishers Redwood City CA S V Adve et al Listopad 2008 Parallel Computing Research at Illinois The UPCRC Agenda 9 grudnya 2008 u Wayback Machine PDF Parallel Illinois University of Illinois at Urbana Champaign Osnovni tehnologiyi zbilshennya produktivnosti obchislen zbilshennya chastoti taktovogo generatora ta hitrishi prote vidpovidno nabagato skladnishi arhitekturi sogodni stikayutsya z tak zvanoyu stinoyu potuzhnosti Komp yuterna promislovist prijnyala fakt sho majbutni zrostannya produktivnosti obchislen budut pov yazani zi zrostannyam kilkosti procesoriv chi yader anizh zi sprobami zmusiti odne yadro pracyuvati shvidshe Asanovic et al Starij princip ekonomiyi Elektrika bezplatna tranzistori dorogi Novij princip ekonomiyi elektrika doroga ale tranzistori bezplatni Asanovic Krste et al Gruden 18 2006 The Landscape of Parallel Computing Research A View from Berkeley PDF University of California Berkeley Technical Report No UCB EECS 2006 183 Starij princip virishennya problem Zbilshennya taktovoyi chastoti osnovnij metod pokrashennya produktivnosti Novij princip Zbilshennya paralelizmu ce osnovnij metod zbilshennya produktivnosti procesora Navit predstavniki Intel kompaniyi sho zazvichaj asociyuyetsya z poziciyeyu chim bilsha chastota tim krashe poperedzhuyut sho tradicijni pidhodi do zbilshennya produktivnosti cherez zbilshennya taktovoyi chastoti dosyagli svoyeyi mezhi Patterson David A and John L Hennessy 1998 Computer Organization and Design Second Edition Morgan Kaufmann Publishers p 715 ISBN 1 55860 428 6 Barney Blaise Introduction to Parallel Computing Lawrence Livermore National Laboratory Arhiv originalu za 29 chervnya 2013 Procitovano 9 listopada 2007 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 Flynn Laurie J Intel Halts Development of 2 New Microprocessors The New York Times May 8 2004 Retrieved on April 22 2008 Moore Gordon E 1965 PDF s 4 Arhiv originalu PDF za 18 lyutogo 2008 Procitovano 11 listopada 2006 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 Fred Bruks Mifichnij lyudino misyac Rozdil 2 Mifichnij lyudino misyac ISBN 0 201 83595 9 Reevaluating Amdahl s Law 27 veresnya 2007 u Wayback Machine 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 Lamport Leslie September 1979 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs IEEE Transactions on Computers C 28 9 pp 690 91 Patterson and Hennessy p 748 Culler David E Jaswinder Pal Singh and Anoop Gupta 1999 Parallel Computer Architecture A Hardware Software Approach Morgan Kaufmann Publishers p 15 ISBN 1 55860 343 3 Culler et al p 15 Patt Yale April 2004 The Microprocessor Ten Years From Now What Are The Challenges How Do We Meet Them 14 kvitnya 2008 u Wayback Machine wmv Distinguished Lecturer talk at Carnegie Mellon University Retrieved on November 7 2007 Culler et al p 124 Culler et al p 125 Patterson and Hennessy p 713 Hennessy and Patterson p 549 Patterson and Hennessy p 714 What is clustering Webopedia computer dictionary Beowulf definition 2012 10 10 u Wayback Machine PC Magazine Architecture share for 06 2007 14 listopada 2007 u Wayback Machine TOP500 Supercomputing Sites Clusters make up 74 60 of the machines on the list Retrieved on November 7 2007 Hennessy and Patterson p 537 MPP Definition 2013 05 11 u Wayback Machine PC Magazine Retrieved on November 7 2007 Kirkpatrick Scott January 31 2003 Computer Science Rough Times Ahead Science Vol 299 No 5607 pp 668 669 DOI 10 1126 science 1081623 Boggan Sha Kia and Daniel M Pressel August 2007 GPUs An Emerging Platform for General Purpose Computation PDF ARL SR 154 U S Army Research Lab Retrieved on November 7 2007 Patterson and Hennessy pp 749 50 Although successful in pushing several technologies useful in later projects the ILLIAC IV failed as a computer Costs escalated from the 8 million estimated in 1966 to 31 million by 1972 despite the construction of only a quarter of the planned machine It was perhaps the most infamous of supercomputers The project started in 1965 and ran its first real application in 1976