Коротка історія появи паралелізму в архітектурі ЕОМ

Сьогодні паралелізмом в архітектурі комп'ютерів уже мало кого здивуєш. Всі сучасні мікропроцесори, будь то Pentium III або PA-8700, MIPS R14000, Е2К або Power3 використовують той чи інший вид паралельної обробки. У ядрі Pentium 4 на різних стадіях виконання може одночасно перебувати до 126 мікрооперацій. На презентаціях нових чіпів і в прес-релізах корпорацій це підноситься як останнє слово техніки та передовий край науки, і це дійсно так, якщо розглядати реалізацію цих принципів у мініатюрних рамках одного кристала.

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

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

IBM 701 (1953), IBM 704 (1955): розрядно-паралельна пам'ять, розрядно-паралельна арифметика.

Всі самі перші комп'ютери (EDSAC, EDVAC, UNIVAC) мали розрядно-послідовну пам'ять, з якої слова зчитувалися послідовно біт за бітом. Першим комерційно доступним комп'ютером, що використовують розрядно-паралельну пам'ять (на CRT) і розрядно-паралельну арифметику, став IBM 701, а найбільшу популярність отримала модель IBM 704 (продано 150 екз.), в якій, крім сказаного, була вперше застосована пам'ять на феритових сердечниках і апаратне АУ з плаваючою точкою.

IBM 709 (1958): незалежні процесори введення/виводу.

Процесори перший комп'ютерів самі керували вводом/виводом. Однак швидкість роботи самого швидкого зовнішнього пристрою, а на ті часи це магнітна стрічка, була в 1000 разів менше швидкості процесора, тому під час операцій введення/виводу У 1958р. до комп'ютера IBM 704 приєднали 6 незалежних процесорів введення/виводу, які після отримання команд могли працювати паралельно з основним процесором, а сам комп'ютер перейменували на IBM 709. Дана модель вийшла напрочуд вдалою, тому що разом з модифікаціями було продано близько 400 екземплярів, причому останній був вимкнений в 1975 році - 20 років існування!

IBM STRETCH (1961): випереджаюче перегляд вперед, розшарування пам'яті.

В 1956 IBM підписує контракт з Лос-Аламоської наукової лабораторії на розробку комп'ютера STRETCH, що має дві принципово важливі особливості: випереджаюче перегляд вперед для вибірки команд і розшарування пам'яті на два банки для узгодження низькій швидкості вибірки з пам'яті і швидкості виконання операцій.

ATLAS (1963): конвеєр команд.

Вперше конвеєрний принцип виконання команд був використаний в машині ATLAS, розробленої в Манчестерському університеті. Виконання команд розбито на 4 стадії: вибірка команди, обчислення адреси операнда, вибірка операнда і виконання операції. Конвейеризації дозволила зменшити час виконання команд з 6 мкс до 1,6 мкс. Комп'ютер мав величезний вплив, як на архітектуру ЕОМ, так і на програмне забезпечення: у ньому вперше використана мультипрограмному ОС, заснована на використанні віртуальної пам'яті і системи переривань.

CDC 6600 (1964): незалежні функціональні пристрої.

Фірма Control Data Corporation (CDC) за безпосередньої участі одного з її засновників, Сеймура Р. Крея (Seymour R. Cray) випускає комп'ютер CDC-6600 -- перший комп'ютер, в якому використовувалося кілька незалежних функціональних пристроїв. Для порівняння з сьогоднішнім днем наведемо деякі параметри комп'ютера:

час такту 100нс,

продуктивність 2-3 млн. операцій в секунду,

оперативна пам'ять розбита на 32 банку за 4096 60-ти розрядних слів,

цикл пам'яті 1мкс,

10

Машина мала величезний успіх на науковому ринку, активно витісняючи машини фірми IBM.

CDC 7600 (1969): конвеєрні незалежні функціональні пристрої.

CDC випускає комп'ютер CDC-7600 з вісьмома незалежними конвеєрними функціональними пристроями - поєднання паралельної і конвеєрної обробки. Основні параметри:

такт 27,5 нс,

10-15 млн. опер/сек.,

8 конвеєрних ФУ,

2-х рівнева пам'ять.

ILLIAC IV (1974): матричні процесори.

Проект: 256 процесорних елементів (ПЕ) = 4 квадранта по 64ПЕ, можливість реконфігурації: 2 квадранта по 128ПЕ або 1 квадрант з 256ПЕ, такт 40нс, продуктивність 1Гфлоп;

роботи початі в 1967 році, до кінця 1971 виготовлена система з 1 квадранта, у 1974р. вона введена в експлуатацію, доведення велася до 1975 року;

центральна частина: пристрій керування (УУ) + матриця з 64 ПЕ;

УУ це проста ЕОМ з невеликою продуктивністю, що управляє матрицею ПЕ; все ПЕ матриці працювали в синхронному режимі, виконуючи в кожний момент часу одну і ту ж команду, що поступила від УУ, але над своїми даними;

ПЕ мав власну АЛП з повним набором команд, ОП - 2Кслова по 64 розряду, цикл пам'яті 350нс, кожен ПЕ мав безпосередній доступ тільки до своєї ОП;

мережа пересилання даних: двовимірний тор із зсувом на 1 по кордону по горизонталі;

Незважаючи на результат у порівнянні з проектом: вартість в 4 рази вище, зроблений лише 1 квадрант, такт 80нс, реальна произв-ть до 50Мфлоп - даний проект надав величезний вплив на архітектуру наступних машин, побудованих за схожим принципом, зокрема: PEPE, BSP, ICL DAP.        

CRAY 1   (1976): векторно-конвеєрні   процесори   

У 1972 році С. Крей залишає CDC і засновує свою компанію Cray   Research, що в 1976р. випускає перший векторно-конвеєрний комп'ютер   CRAY-1: час такту 12.5нс, 12 конвеєрних функціональних пристроїв, пікова   продуктивність 160 мільйонів операцій у секунду, оперативна пам'ять до   1Мслова (слово - 64 розряду), цикл пам'яті 50НС. Головним нововведенням є   введення векторних команд, що працюють з цілими масивами незалежних даних і   що дозволяють ефективно використовувати конвеєрні функціональні пристрої.     

Ієрархія пам'яті.

Ієрархія пам'яті пямого відношення до паралелізму не має, проте, безперечно, належить до тих особливостей архітектури комп'ютерів, які має величезне значення для підвищення їх продуктивності (згладжування різниці між швидкістю роботи процесора і часом вибірки з пам'яті). Основні рівні: регістри, кеш-пам'ять, оперативна пам'ять, дискова пам'ять. Час вибірки за рівнями пам'яті від дискової пам'яті до регістрів зменшується, вартість в перерахунку на 1 слово (байт) зростає. В даний час, подібна ієрархія підтримується навіть на персональних комп'ютерах.

А що ж зараз використовують у світі?

За яким же напрямках йде розвиток високопродуктивної обчислювальної техніки в даний час? Основних напрямків чотири.

1. Векторно-конвеєрні комп'ютери. Конвеєрні функціональні пристрої та набір векторних команд - це дві особливості таких машин. На відміну від традиційного підходу, векторні команди оперують цілими масивами незалежних даних, що дозволяє ефективно завантажувати доступні конвеєри, тобто команда виду A = B + C може означати складання двох масивів, а не двох чисел. Характерним представником даного напрямку є сімейство векторно-конвеєрних комп'ютерів CRAY куди входять, наприклад, CRAY EL, CRAY J90, CRAY T90 (у березні 2000 року американська компанія TERA перекупила підрозділ CRAY у компанії Silicon Graphics, Inc.).

2. Масивно-паралельні комп'ютери з розподіленою пам'яттю. Ідея побудови комп'ютерів цього класу тривіальна: візьмемо серійні мікропроцесори, забезпечимо кожен своєю локальною пам'яттю, з'єднаємо за допомогою деякої комунікаційної середовища - ось і все. Переваг у такої архітектури маса: якщо потрібна висока продуктивність, то можна додати ще процесорів, якщо обмежені фінанси або заздалегідь відома необхідна обчислювальна потужність, то легко підібрати оптимальну конфігурацію і т.п.

Однак є й вирішальний "мінус", що зводить багато "плюси" нанівець. Справа в тому, що міжпроцесорних взаємодія в комп'ютерах цього класу йде набагато повільніше, ніж відбувається локальна обробка даних самими процесорами. Саме тому написати ефективну програму для таких комп'ютерів дуже складно, а для деяких алгоритмів іноді просто неможливо. До даного класу можна віднести комп'ютери Intel Paragon, IBM SP1, Parsytec, в какой-то ступеня IBM SP2 і CRAY T3D/T3E, хоча в цих комп'ютерах вплив зазначеного мінуса значно послаблено. До цього ж класу можна віднести і мережі комп'ютерів, які все частіше розглядають як дешеву альтернативу вкрай дорогим суперкомп'ютерів.

3. Паралельні комп'ютери із загальною пам'яттю. Вся оперативна пам'ять таких комп'ютерів розділяється декількома однаковими процесорами. Це знімає проблеми попереднього класу, але додає нові - число процесорів, що мають доступ до загальної пам'яті, з чисто технічних причин не можна зробити великим. У даний напрямок входять багато сучасних багатопроцесорні SMP-комп'ютери або, наприклад, окремі вузли комп'ютерів HP Exemplar і Sun StarFire.

4. Останній напрямок, строго кажучи, не є самостійним, а швидше являє собою комбінації попередніх трьох. З декількох процесорів (традиційних або векторно-конвеєрних) і загальної для них пам'яті сформуємо обчислювальний вузол. Якщо отриманої обчислювальної потужності не достатньо, то об'єднаємо декілька вузлів високошвидкісними каналами. Подібну архітектуру називають кластерної, і за таким принципом побудовані CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, останні моделі IBM SP2 та інші. Саме цей напрямок є в даний час найбільш перспективним для конструювання комп'ютерів з рекордними показниками продуктивності.

Використання паралельних обчислювальних систем

До жаль чудеса в житті рідко трапляються. Гігантська продуктивність паралельних комп'ютерів і супер-ЕОМ з лишком компенсується складностями їх використання. Почнемо з найпростіших речей. У вас є програма і доступ, скажімо, до 256-процесорного комп'ютера. Що ви очікуєте? Та ясно що: ви цілком законно очікуєте, що програма буде виконуватися в 256 разів швидше, ніж на одному процесорі. А от саме цього, швидше за все, і не буде.

Закон Амдала і його наслідки

Припустимо, що у вашій програмі частка операцій, які потрібно виконувати послідовно, дорівнює f, де 0 <= f <= 1 (при цьому частка розуміється не по статичному числа рядків коду, а за кількістю операцій у процесі виконання). Крайні випадки в значеннях f відповідають повністю паралельним (f = 0) і повністю послідовним (f = 1) програмами. Так от, для того, щоб оцінити, яке прискорення S може бути отримано на комп'ютері з 'p' процесорів при даному значенні f, можна скористатися законом Амдала:

Якщо 9/10 програми виконується паралельно, а 1/10, як і раніше послідовно, то прискорення більше, ніж у 10 раз отримати в принципі неможливо незалежно від якості реалізації паралельної частини коду і кількості використовуваних процесорів (ясно, що 10 виходить тільки в тому випадку, коли час виконання паралельної частини дорівнює 0).

Подивимося на проблему з іншого боку: а яку ж частину коду треба прискорити (а значить і попередньо дослідити), щоб отримати задане прискорення? Відповідь можна знайти в слідстві із закону Амдала: для того щоб прискорити виконання програми в q разів необхідно прискорити не менше, ніж у q раз не менш, ніж (1-1/q)-у частину програми. Отже, якщо є бажання прискорити програму в 100 разів у порівнянні з її послідовним варіантом, то необхідно отримати не менше прискорення не менш, ніж на 99.99% коду, що майже завжди складає значну частину програми!

Звідси перший висновок - перш, ніж грунтовно переробляти код для переходу на паралельний комп'ютер (а будь-який суперкомп'ютер, зокрема, є таким) треба грунтовно подумати. Якщо оцінивши закладений у програмі алгоритм ви зрозуміли, що частка послідовних операцій велика, то на значне прискорення розраховувати явно не доводиться і потрібно думати про заміну окремих компонент алгоритму.

В ряді випадків послідовний характер алгоритму змінити не так складно. Припустимо, що в програмі є наступний фрагмент для обчислення суми n чисел:

s = 0

Do i = 1, n

s = s + a (i)

EndDo

(можна теж саме будь-якою іншою мовою)

За своєю природою він строго послідовний, тому що на i-й ітерації циклу потрібно результат з (i-1)-й і все ітерації виконуються одна за одною. Маємо 100% послідовних операцій, а значить і ніякого ефекту від використання паралельних комп'ютерів. Разом з тим, вихід очевидний. Оскільки в більшості реальних програм (питання: а чому в більшості, а не у всіх?) немає істотної різниці, в якому порядку складати числа, виберемо іншу схему складання. Спочатку знайдемо суму пар сусідніх елементів: a (1) + a (2), a (3) + a (4), a (5) + a (6) і т.д. Зауважимо, що при такій схемі всі пари можна складати одночасно! На наступних кроках будемо діяти абсолютно аналогічно, отримавши варіант паралельного алгоритму.

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

Але підемо далі і припустимо, що всі процесори однакові. Проблеми скінчилися? Знову ні! Процесори виконали свою роботу, але результат-то треба передати іншому для продовження процесу підсумовування ... а на передачу йде час ... і в цей час процесори знову простоюють ...

Словом, змусити паралельну обчислювальну систему або супер-ЕОМ працювати з максимальною ефективність на конкретній програмі це, прямо скажемо, завдання не з простих, оскільки необхідно ретельне узгодження структури програм і алгоритмів з особливостями архітектури паралельних обчислювальних систем.

Заключний питання. Як ви думаєте, чи вірно твердження: чим потужніший комп'ютер, тим швидше на ньому можна вирішити цю задачу?

Заключний відповідь. Ні, це не вірно. Це можна пояснити простим побутовим прикладом. Якщо один землекоп викопає яму 1м * 1м * 1м за 1 годину, то два таких же землекопа це зроблять за 30 хв - у це можна повірити. А за скільки часу цю роботу зроблять 60 землекопів? За 1 хвилину? Звичайно ж ні! Починаючи з деякого моменту вони будуть просто заважатиме один одному, не прискорюючи, а сповільнюючи процес. Так само і в комп'ютерах: якщо завдання занадто мала, то ми будемо довше займатися розподілом роботи, синхронізацією процесів, складанням результатів і т.п., ніж безпосередньо корисною працею.

Цілком ясно, що не все так просто ...

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://parallel.ru