42 ПРИНЦИПИ ПАРАЛЕЛЬНОЇ ОБРОБКИ ІНФОРМАЦІЇ

В умовах постійно зростаючих вимог до продуктивності обчислювальної техніки все більш явними стають обмеження класичної фон-нейманівської архітектури. Подальший розвиток обчислювальної техніки зв'язаний з переходом до паралельних обчислень як у рамках однієї обчислювальної машини, так і шляхом створення багатопроцесорних систем і мереж, які об'єднують велику кількість окремих процесорів або окремих обчислювальних машин. Для такого підходу замість терміну «обчислювальна машина» більш підходить термін «обчислювальна система» (ОС). Головною особливістю такої системи є наявність у ній засобів, які реалізують паралельну обробку інформації.

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

Паралельна обробка інформації являє собою одночасне рішення двох або більшої кількості частин однієї й тієї ж програми двома чи більшою кількістю ЕОМ (процесорними елементами) обчислювальної системи. Реалізують три основних способи організації паралельної обробки:

1) суміщення у часі різноманітних етапів різних задач – це мульти-програмна обробка, яка широко використовується як у однопроцесорних ЕОМ, так і в складних ОС;

2) одночасне розв'язання різноманітних задач або частин однієї задачі (можливо тільки за наявності декількох обробляючих пристроїв);

3) конвеєрна обробка інформації.

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

Одним з найбільш розповсюджених типів паралелізму є паралелізм незалежних гілок. Суть його полягає у виділенні окремих незалежних частин великої задачі (гілок програми), які можуть виконуватись паралельно окремими обробляючими пристроями незалежно один від одного. Причому обробляючі пристрої ОС функціонують в однопрограмному режимі паралельної обробки інформації. Двома незалежними гілками програми визнаються гілки програми, що відповідають таким умовам:

• ні одна з вхідних для гілки програми величин не є вихідною величиною іншої програми (відсутність функціональних зв'язків);

• для двох гілок програми не повинен здійснюватись запис у одні й ті ж комірки пам'яті (відсутність зв'язку по оперативній пам'яті);

• умови виконання однієї гілки не залежать від результатів, що отримані під час виконання іншої гілки (незалежність по управлінню);

• обидві гілки повинні виконуватись у різних блоках програми (програмна незалежність).

Виділення незалежних гілок широко використовується під час паралельної обробки в задачах матричної алгебри, лінійного програмування, спектральної обробки сигналів, прямого та зворотного перетворення Фур'є та ін.

Методи та засоби реалізації паралелізму залежать від того, на якому рівні він повинен забеспечуватись. Зазвичай розрізняють такі рівні паралелізму:

• рівень завдань – декілька незалежних завдань одночасно виконуються на різних процесорах, які практично не взаємодіють один з одним. Цей рівень реалізується в ОС з множиною процесорів у багатозадачному режимі.

• рівень програм – частини однієї задачі виконуються множиною процесорів. Даний рівень досягається на паралельних ОС.

• рівень команд – виконання команди розділяється на фази, а фази декількох послідовних команд можуть бути перекриті за рахунок конвеєризації. Даний рівень використовується в ОС з одним процесором.

• рівень бітів (арифметичний рівень) – біти слова обробляються один за одним. Цей процес має назву біт-послідовна операція. Якщо біти слова обробляються одночасно, кажуть про біт-паралельну операцію. Даний рівень реалізується в звичайних і суперскалярних процесорах.

Паралелізм рівня завдання можливий між незалежними завданнями або їх фазами. Основним засобом реалізації паралелізму на рівні завдань є багатопроцесорні і багатомашинні обчислювальні системи, в яких завдання розподіляються за окремими процесорами або машинами. Однак, якщо кожне завдання трактувати як сукупність незалежних задач, реалізація даного рівня можлива і в рамках однопроцесорної ОС. У цьому випадку декілька завдань можуть одночасно знаходитись в основній пам’яті ОС, за умови, що в кожний момент виконується тільки одне з них. Коли завдання, яке виконується, потребує вводу/виводу, ця операція запускається, а до її завершення інші ресурси ОС передаються другому завданню. По завершенні вводу/виводу ресурси ОС повертаються до завдання, яке ініціювало цю операцію. В цьому випадку паралелізм забезпечується за рахунок того, що центральний процесор і система вводу/виводу функціонують одночасно і обслуговують різні завдання.

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

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

Загальна форма паралелізму на рівні програм організується розбиттям даних, які програмуються на підмножини. Цей розподіл називають декомпозицією області (domain decomposition), а паралелізм, який при цьому виникає, має назву паралелізму даних. Підмножини даних призначаються різним обчислювальним процесам, і цей процес має назву розподілення даних (data distribution). Процесори виділяються певним процесам або за ініціативою програми, або в процесі роботи операційною системою. На кожному процесорі може виконуватись більше одного процесу.

Паралелізм рівня команд. Паралелізм на рівні команд має місце, коли обробка декількох команд або виконання різних етапів однієї і тієї ж команди може перекриватись у часі. Розробники обчислювальної техніки ще здавна зверталися до методів, відомих під загальною назвою «поєднання операцій», при якому апаратура ОМ у будь-який момент часу виконує одночасно більше однієї операції. Цей загальний принцип включає два поняття: паралелізм і конвеєризацію. Хоча у них багато загального і їх часто важко розрізняти на практиці, ці терміни відображають два принципово різних підходи. 

У першому варіанті поєднання операцій досягається за рахунок того, що в складі обчислювальної системи окремі пристрої присутні в декількох копіях. Так, до складу процесора може входити декілька АЛП, і висока продуктивність забезпечується за рахунок одночасної роботи всіх цих АЛП. Другий підхід був розглянутий раніше.

Під час організації паралельного обчислювального процесу виникає задача вибору побудови розкладу. 

Розклад паралельних обчислювальних процесів визначає порядок виконання програми в ОС, включаючи розподіл частин програми по обробляючих пристроях (процесорах, ОМ), і служить основою алгоритмів планувальника операційної системи та різноманітних управляючих програм. Як критерії оптимальних розкладів для паралельної програми можна назвати:

• мінімізацію часу виконання програми;

• мінімізацію кількості потрібних пристроїв обробки; мінімізацію середнього часу закінчення виконання завдань; максимізацію завантаження пристроїв ОС;

• мінімізацію часу простоювання пристроїв.

Найчастіше використовують перший критерій.

42.2 Класифікація  архітектур  комп'ютерних систем

Існує декілька класифікацій архітектур комп'ютерних систем. Найбільш вдалою є класифікація М. Флінна.

42.2.1. Класифікація Флінна

Архітектурні особливості комп'ютерних систем описано з погляду потоку команд (інструкцій) та потоку даних. Такий підхід дає змогу відносити архітектури комп'ютерів до одного з чотирьох класів (табл. 42.1, рис. 42.1).

Класифікація здійснена з погляду не структури, а того, як у комп'ютері його машинні команди взаємодіють з даними. 

Таблиця 42.1 – Класифікація архітектур комп'ютерних систем

SISD (Single Instruction Stream/Single Data Stream) - одиничний потік команд і одиничний потік даних. Представник цього класу – класичний фон-нейманівський комп'ютер. Команди обробляються послідовно і кожна команда ініціює одну операцію з одним потоком даних. До цього класу комп'ютерів можна віднести також конвеєрні комп'ютери. Деякі спеціалісти вважають, що до SISD-систем можна віднести і векторно-конвеєрні ОС, якщо розглядати вектор як неподільний елемент даних для відповідної команди.

MISD (Multiple Instruction Stream/Single Data Stream) – множинний потік команд і одиничний потік даних. В архітектурі присутня множина процесорів, які обробляють один і той же потік даних. Ряд дослідників відносять до даного класу конвеєрні сиcтеми. Прийнято вважати, що доки даний клас незадіяний, однак може бути корисним для розробки принципово нових концепцій побудови обчислювальних систем.

SIMD (Single Instruction Stream/Multiple Data Stream) – одиничний потік команд і множинний потік даних. Ця архітектура дозволяє виконати одну арифметичну операцію відразу над багатьма даними – елементами вектору. Представниками цього класу є системи з матрицею процесорів, де один управляючий пристрій контролює множину процесорних елементів. Усі процесорні елементи отримують від пристрою управління однакову команду і виконують її над власними локальними даними. В цей клас можуть бути включеними і векторно-конвеєрні ОС, якщо кожний елемент вектора розглядати як окремий елемент даних.

Рисунок 42.1 –  Архітектура комп'ютерних систем за Флінном:   а - SISD;  б - MISD;  в - SIMD;  г - MIMD

MIMD (Multiple Instruction Stream/Multiple Data Stream) – множинний потік команд і множинний потік даних. До цього класу відносяться системи з множиною пристроїв обробки команд, які об'єднані в єдиний комплекс і кожний працює з власним потоком команд. Цей клас надзвичайно широкий, бо включає в себе різного роду мультипроцесорні системи.

Класифікація Флінна надто загальна, вона має деякі недоліки, наприклад відносить усі паралельні комп'ютери, крім мультипроцесорних, до одного класу і не вказує ніякої відмінності між конвеєрними комп'ютерами і матрицею МП.

Використовуються й інші класифікації архітектур, зокрема систематика  Д. Шора, структурна систематика Р. Хокні та К. Джессхоупа.

42.2.2 Структурна систематика Р. Хокні та К. Джессхоупа

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

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

Прикладом однієї з перших неконвеєрних обчислювальних машин з паралелізмом є комп'ютер CDC – 6600, побудований на основі декількох скалярних процесорів.

Конвеєрні ЕОМ поділяються на такі, що виконують тільки скалярні команди, наприклад комп'ютери CDC – 7800, FPC AP-120B, і такі, що вико-нують векторні команди. Комп'ютери, що використовують векторні команди, поділяють, у свою чергу, на комп'ютери із спеціалізованим конвеєром, наприклад CRAY-1, та з універсальним конвеєром – комп'ютер CYBER 205.

Комп'ютери з класу машин з матрицею процесорів поділяють за зв'язаністю процесорів у матриці, розрядністю тощо. Першими машинами такого типу були ILLIAC-IV, BSP, STA-RAN, ICL DAP, OMEN та ін.

42.2.3 Класифікація Шора

На початку 70-х років Д. Шором була запропонована одна з перших класифікацій паралельних комп’ютерних систем. В своїй класифікації Д. Шор запропонував спосіб компонування комп’ю¬терних систем на основі фіксованого числа базових блоків: при-строю керування, арифметико — логічного пристрою, пам’яті ко¬манд і пам’яті даних. При цьому додатково була накладена умова, що вибірка із пам’яті команд і пам’яті даних може здійснюватися словами або горизонтально, або вертикально. Розглянемо дану класифікацію за допомогою базових блоків, запропонованих Шором.

Перша комп’ютерна система наведена на рис. 42.2, де ПК — пам’ять команд, КП – керуючий пристрій, АЛП – арифметико - логічний пристрій, ПД – пам’ять даних.

Рисунок 42.2 –  Перша комп’ютерна система 

Згідно рис. 42.2 – це структура комп’ютерної системи, яка містить керуючий пристрій, арифметико – логічний пристрій, пам’ять команд і пам’ять даних із послідовною вибіркою. Зчитування даних здійснюється вибіркою всіх розрядів деякого слова для їх паралельної обробки в арифметико-логічному пристрої. Склад АЛП може допускати наявність декількох функціональних пристроїв, в тому числі і конвеєрного типу. Із за подібних міркувань до даного класу потрапляють комп’ютерні системи (ІВМ 701, РDР - 11, VAX11/780), так і конвеєрні скалярні (СDС 7600) і векторно - конвеєрні (СRAY-1).

Якщо в першій комп’ютерній системі здійснити вибірку не по горизонталі, а по вертикалі, то отримаємо другу комп’ютерну систему, яка наведена на рис. 42.3.

Рисунок 42.3 –  Друга комп’ютерна система 

Слова в пам’яті даних, як і в попередній структурі розташовуються горизонтально, але доступ до них здійснюється вертикально. Тобто, якщо в першій комп’ютерній системі відбувається послідовна обробка слів при паралельній обробці розрядів, то в другій комп’ютерній системі – послідовна обробка розрядів з однієї і тієї ж позиції кожного слова.

Структура другої комп’ютерної системи лежить в основі асоціативних комп’ютерів, наприклад, при побудові центрального процесора системи STARAN, де множина опкраційних пристроїв в складі арифметико логічного пристрою виконує порозрядну обробку даних. Іншим прикладом є матрична система ІСІ DАР, яка може одночасно обробляти по одному розряду з 4096 слів.

Третя комп’ютерная система утворюється на основі об’єднання принципів побудови першої і другої комп’ютерних систем. Така система наведена на рис. 42.4.

Рисунок 42.4 –  Третя комп’ютерна система 

Ця система має два арифметико — логічних пристрої (горизонтальний і вертикальний), а також модифіковану пам’ять даних, яка забеєпечує доступ як до слів, так і до розрядів для їх обробки з однієї і тієї позиції кожного слова. Представниками комп’ютерних систем такого класу є системи сімейства ОМЕN - 60 фірми Sanders Associatts, побудовані в прямій відповідності до концепції ортогональної комп’ютерної системи.

Четверта комп’ютерна система утворюється із першої шляхом збільшення кількості пар процесорних елементів. Під процесорним елементом слід розуміти арифметико-логічний пристрій і пам’ять даних. Така система наведена на рис. 42.5.

Із рис. 42.5 слідує, що пристрій керування є єдиним для даної системи, який видає команди відразу всім процесорним елементам. Така структура робить її простою для нарощування процесорних елементів, але з іншого боку сильно обмежує застосовність даного класу комп’ютерних систем. Представником комп’ютерних систем такого класу є система РЕРЕ, яка об’єднує 288 процесорних елементів.

Рисунок 42.5 –  Четверта комп’ютерна система 

П’ята комп’ютерна система утворюється шляхом вводу лінійних звязків між сусідніми процесорними елементами четвертої комп’ютерної системи, рис. 42.6.

Рисунок 42.6 –  П’ята комп’ютерна система 

Будь-який процесорний елемент в п’ятій комп’ютерній системі тепер може звертатися до даних як у своїй пам’яті, так і в пам’яті безпосередніх сусідів. Подібна структура характерна для класичної матричної багатопроцесорної системи ІЬЕІАСІУ.

Із рис. 42.2, ..., рис. 42.6 слідує, що у всіх системах дотримана концепція розділення пам’яті даних і арифметико-логічних пристроїв, припускаючи наявність шини даних або якого-небудь комутуючого елементу між ними. 

Шоста комп’ютерна система має інший підхід і утворюється шляхом розподілу логіки процесора по всьому запам’ятовуючому пристрою, рис. 42.7.

Таку систему називають матрицею з функціональною пам’яттю. Прикладом такої системи є як прості асоціативні запам’ятовуючі пристрої, так і складні асоціативні процесори.

Рисунок 42.7 –  Шоста комп’ютерна система