Класифікація паралельних комп'ютерних систем
Класифікація Шора
Одна з перших класифікацій комп'ютерних систем була запропонована Д. Шором на початку 70-х років. Вона цікава тим, що є спробою виділення типових способів компонування комп'ютерних систем на основі фіксованого числа базових блоків: пристрою керування, арифметико-логічного пристрою, пам'яті команд і пам'яті даних. Додатково передбачається, що вибірка з пам'яті даних може здійснюватися словами, тобто вибираються всі розряди одного слова, і/або бітовим шаром - по одному розряду з однієї і тієї ж позиції кожного слова (іноді ці два способи називають горизонтальною і вертикальною вибірками відповідно). Звичайно ж, при аналізі даної класифікації треба робити знижку на час і появи, оскільки передбачити велику різноманітність паралельних систем теперішнього часу тоді було у принципі неможливо. Отже, згідно з класифікацією Д. Шора, всі комп'ютери розбиваються на шість класів, перший з яких дістав назву машини І, другий - машини II, і т. д.
На поданих нижче рисунках позначено: ПІ - пам'ять команд (інструкцій), ПК - пристрій керування, АЛП - арифметико-логічний пристрій, ПД - пам'ять даних. Машина І - це комп'ютерна система, яка містить пристрій керування, арифметико-логічний пристрій, пам'ять команд і пам'ять даних із послівною вибіркою (рис. 1.1).
Рис. 1.1. Машина I
Зчитування даних здійснюється вибіркою всіх розрядів деякого слова для їх паралельної обробки в арифметико-логічному пристрої. Склад АЛП спеціально не вказується, що допускає наявність декількох функціональних пристроїв, в тому числі конвеєрного типу. За цими міркуваннями до даного класу потрапляють як класичні послідовні машини (ІВМ 701, PDP-11, VAX 11/780), так і конвеєрні скалярні (CDC 7600) і векторно-конвеєрні (CRAY-1).
Якщо в машині І здійснювати вибірку не по словах, а по одному розряду з усіх слів, то одержимо машину II (рис. 1.2). Слова в пам'яті даних, як і раніше, розташовуються горизонтально, але доступ до них здійснюється інакше. Якщо в машині І відбувається послідовна обробка слів при паралельній обробці розрядів, то в машині II - послідовна обробка бітових шарів при паралельній обробці множини слів.
Рис. 1.2. Машина II
Структура машини II лежить в основі асоціативних комп'ютерів (наприклад, так побудовано центральний процесор машини STARAN), причому фактично такі комп'ютери мають в складі арифметико-логічного пристрою множину порівняно простих операційних пристроїв порозрядної обробки даних. Іншим прикладом служить матрична система ICL DAP, яка може одночасно обробляти по одному розряду з 4096 слів.
Якщо об'єднати принципи побудови машин І і II, то одержимо машину III (рис. 1.3). Ця машина має два арифметико-логічні пристрої - горизонтальний і вертикальний, а також модифіковану пам'ять даних, яка забезпечує доступ як до слів, так і до бітових шарів. Вперше ідею побудови таких систем у 1960 році висунув У Шуман, що називав їх ортогональними (якщо пам'ять представляти як матрицю слів, то доступ до даних здійснюється в напрямі, "ортогональному" традиційному - не по словах (рядках), а по бітових шарах (стовпцях)). У принципі, як машину STARAN так і ICL DAP можна запрограмувати на виконання функцій машини III, але оскільки вони не мають окремих АЛП для обробки слів і бітових шарів, віднести їх до даного класу не можна. Повноправними представниками машин класу III є обчислювальні системи сімейства OMEN-60 фірми Sanders Associates, побудовані в прямій відповідності до концепції ортогональної машини.
Рис. 1.3. Машина III
Якщо в машині І збільшити кількість пар арифметико-логічний пристрій <==> пам'ять даних (іноді цю пару називають процесорним елементом), то одержимо машину IV (рис. 1.4). Єдиний пристрій керування видає команду за командою відразу всім процесорним елементам. З одного боку, відсутність з'єднань між процесорними елементами робить подальше нарощування 'їх числа відносно простим, але з іншого боку, сильно обмежує застосовність машин цього класу. Таку структуру має обчислювальна система РЕРЕ, яка об'єднує 288 процесорних елементів.
Рис. 1.4. Машина IV
Якщо ввести безпосередні лінійні зв'язки між сусідніми процесорними елементами машини IV, то одержимо структуру машини V (рис. 1.5). Будь-який процесорний елемент тепер може звертатися до даних як у своїй пам'яті, так і в пам'яті безпосередніх сусідів. Подібна структура характерна, наприклад, для класичної матричної багатопроцесорної системи ILLIAC IV.
Рис. 1.5. Машина V
Відмітимо, що у всіх машинах з 1-ї по V-у дотримана концепція розділення пам'яті даних і арифметико-логічних пристроїв, припускаючи наявність шини даних або якого-небудь комутуючого елемента між ними. Машина VI, названа матрицею з функціональною пам'яттю (або пам'яттю з вбудованого логікою), є іншим підходом, що передбачає розподіл логіки процесора по всьому запам'ятовувальному пристрою (рис.1.6). Прикладом можуть служити як прості асоціативні запам'ятовувальні пристрої, так і складні асоціативні процесори.
Рис. 1.4. Машина VI
Класифікація Фліна
Одну з перших практично корисних класифікацій паралельних комп'ютерних систем подав у 1966 році співробітник фірми IBM Майкл Флін, який зараз є професором Стенфордського університету (США). Його класифікація базується на оцінці потоку інформації, який поділено на потоки даних між основною пам'яттю та процесором, та потік команд, які виконує процесор. При цьому потік даних та команд може бути як одиничним, так і множинним. Згідно з М. Фліном, усі комп'ютерні системи поділяють так:
ОКОД - комп'ютерні системи з одиничним потоком команд та одиничним потоком даних (SISD - Single Instruction Single Data stream). МКОД - комп'ютерні системи з множинним потоком команд та одиничним потоком даних (MISD - Multiple Instruction Single Data stream). ОКМД - комп'ютерні системи з одиничним потоком команд та множинним потоком даних (SIMD - Single Instruction Multiply Data stream). МКМД - комп'ютерні системи з множинним потоком команд та множинним потоком даних (MIMD - Multiple Instruction Multiply Data stream).
Розглянемо запропоновану М. Фліном класифікацію детальніше. На поданих нижче малюнках позначено: ПК - пристрій керування, ПР - процесор, ПД - пам'ять даних.
До класу комп'ютерних систем з одиничним потоком команд та одиничним потоком даних належить, зокрема, комп'ютер з архітектурою Джона фон Неймана, яким, наприклад, є розповсюджений персональний комп'ютер. Структура цієї системи представлена на рис. 1.7а. Організація роботи комп'ютерних систем цього класу була розглянута в попередніх розділах книги.
Рис. 1.7. Структура комп'ютерної системи типу ОКОДа), МКОД b), ОКМД с), МКМД d)
Структура комп'ютерної системи з множинним потоком команд та одиничним потоком даних показана на рис. 1.7Ь. Комерційні універсальні комп'ютерні системи цього типу в наш час невідомі, проте вони можуть з'явитися у майбутньому. До цього типу систем з деякими умовностями можна віднести спеціалізовані потокові процесори, зокрема систолічні, які використовують, наприклад, при обробці зображень.
В комп'ютерній системі з одиничним потоком команд та множинним потоком даних (рис. 1.7 с) одночасно обробляється велика кількість даних. До цього класу, зокрема, належать раніше розглянуті векторні процесори. До комп'ютерних систем з одиничним потоком команд та множинним потоком даних можна віднести також апаратну підсистему процесорів Pentium, яка реалізовує технологію MMX опрацювання даних для графічної операційної системи Windows.
Характерним прикладом комп'ютерної системи з одиничним потоком команд та множинним потоком даних може служити система, яка складається з двох частин: зовнішнього комп'ютера з архітектурою Джона фон Неймана, який виконує роль пристрою керування, і масиву ідентичних синхронізованих елементарних процесорів, здатних одночасно виконувати ту ж саму дію над різними даними. Кожен процесор у масиві Має місцеву пам'ять невеликої ємності, де зберігаються дані, які обробляються паралельно.
З масивом процесорів з'єднано шину пам'яті зовнішнього комп'ютера таким чином, що він може довільно звернутися до кожного процесора масиву. Програма може виконуватися традиційно послідовно на зовнішньому комп'ютері, а її частина може паралельно виконуватися на масиві процесорів. У комп'ютерній системі з множинним потоком команд та множинним потоком даних кожен процесор оперує із своїм потоком команд та своїм потоком даних (рис.1.7d).
Як правило, окремі процесори багатопроцесорної системи є серійними пристроями, що дозволяє значно зменшити вартість проекту. У класі МКМД треба відрізняти сильно зв'язані системи, власне багатопроцесорні системи, від мереж комп'ютерів, тобто слабо зв'язаних систем; тобто багатопроцесорні системи та комп'ютерні мережі потрапляють до різних підкласів класу MIMD.
В 1978 році Д. Куком було запропоновано розширення класифікації Фліна. У своїй класифікації Д. Кук розділив потоки команд та даних на скалярні та векторні потоки. Комбінація цих потоків приводить в підсумку до 16 типів архітектури паралельних комп'ютерних систем.
Класифікація Хокні Р. Хокні - відомий англійський фахівець в області паралельних обчислювальних систем, розробив свій підхід до класифікації, введеної їм для систематизації комп'ютерів, що потрапляють в клас MIMD по систематиці Фліна.
Клас MIMD надзвичайно широкий, причому поряд з великим числом комп'ютерів він об'єднує безліч різних типів архітектур. Хокні, намагаючись систематизувати архітектури усередині цього класу, отримав ієрархічну структуру, представлену на рис.1.8.
Основна ідея класифікації полягає в наступному. Множинний потік команд може бути оброблений двома способами: або одним конвеєрним пристроєм обробки, що працює в режимі поділу часу для окремих потоків, або кожен потік обробляється своїм власним пристроєм. Перша можливість використовується в MIMD комп'ютерах, які називаються конвеєрними (наприклад, процесорні модулі в Denelcor HEP). Архітектури, використовують другу можливість, у свою чергу знову діляться на два класи: MIMD комп'ютери, в яких можливий прямий зв'язок кожного процесора з кожним, реалізований за допомогою перемикача; MIMD комп'ютери, в яких прямий зв'язок кожного процесора можливий тільки з найближчими сусідами по мережі, а взаємодія віддалених процесорів підтримується спеціальною системою маршрутизації через процесори-посередники. Далі, серед MIMD машин з перемикачем Хокні виділяють ті, в яких вся пам'ять розподілена серед процесорів як їх локальна пам'ять (наприклад, PASM, PRINGLE). У цьому випадку спілкування самих процесорів реалізується за допомогою дуже складного перемикача, що становить значну частину комп'ютера. Такі машини звуться MIMD машин з розподіленою пам'яттю. Якщо пам'ять це розподілений ресурс, доступний всім процесорам через перемикач, то такі MIMD є системами із загальною пам'яттю (CRAY X-MP, BBN Butterfly). Відповідно до типу перемикачів можна проводити класифікацію : простий перемикач, багатокаскадний перемикач, загальна шина.
Багато сучасних обчислювальних систем мають як загальну поділювану пам'ять, так і розподілену локальну. Такі системи автор розглядає як гібридні MIMD c перемикачем.
При розгляді MIMD машин з мережевою структурою вважається, що всі вони мають розподілену пам'ять, а подальша класифікація проводиться відповідно до топології мережі: зіркоподібні мережі (lCAP), регулярні решітки різної розмірності (Intel Paragon, CRAY T3D), гіперкуби (NCube, Intel iPCS ), мережі з ієрархічною структурою, такою, як дерева, піраміди, кластери (Cm *, CEDAR) і, нарешті, мережі, змінюючі свою конфігурацію.
Класифікація Скіллікорна У 1989 році була зроблена чергова спроба розширити класифікацію Флінна і, тим самим, подолати її недоліки. Д. Скіллікорн розробив підхід, придатний для опису властивостей багатопроцесорних систем і деяких нетрадиційних архітектур, зокрема dataflow і reduction machine.
Пропонується розглядати архітектуру будь-якого комп'ютера, як абстрактну структуру, що складається з чотирьох компонентів: