наявність принципової можливості розпаралелити задачу; деякі алгоритми не піддаються ефективній паралелізації. Нехай в програмі доля операцій, які треба виконати послідовно, тобто розпаралелити їх не можливо = f; 0 f 1. Якщо f=0, то всі операції – не залежні, f=1, то залежні. Для оцінки прискорення продуктивності S на комп’ютері із P-процесорами при певному значенні f використовують закон Амдала:
.
Він дуже обмежує використання паралельних
комп’ютерів. Якщо в програмі лише 10%
послідовного колу, то за законом Амдала
не слід очікувати прискорення більш
ніж у 10 разів, яку б кількість Р –
процесорів не використовували.
Трудові витрати на розпаралелювання та використання програми
Самий простий спосіб пришвидшити наявну програму це використання вбудованих в компілятор засобів для векторизації програми. При цьому ніяких змін в програму вносити не треба. Проте існує дуже велика ймовірність, що компілятор не розпізнає паралельного фрагменту коду. Другий варіант роботи із програмою – це аналіз часу, що витрачаються різними частинами програм і визначення найбільш ресурсо споживчої. Далі слід оптимізувати якраз ці частини тіла. В програмі найбільш затратними є цикли, тому потрібно якомога більше розпаралелити циклічні операції.
Третій варіант – заміна алгоритму обчислень в найкритичніших частинах програми. Спосіб написання оптимальних програм істотно відрізняється в 2-х парадигмах програмування. Тому програма, яка оптимальна для скалярного процесору не може бути векторизована. В той же час паралельна програма на скалярних процесорах може виконуватись дуже повільно. Додаткові можливості дають спеціальні векторні та паралельні бібліотеки, що розроблені для конкретної ОЕМ. Але із використанням даних бібліотек можуть виникнути проблеми при переносі програм.
4-ий варіант – написання програм „з нуля” для кожної конкретної ЕОМ. Цей спосіб являється ідеальним для розробки ефективних високопродуктивних векторних паралельних програм. Проте даний підхід є дуже затратним з точки зору використаного часу.
Класи задач, які можна ефективно розпаралелювати
Ефективно розпаралелювати можна наступні види під задач:
одновимірні масиви:
задачі даного виду зустрічаються часто. Якщо значення елементів масиву визначаються доволі складним виразом, а обчислювати їх потрібно декілька раз, то розпаралелення циклу може виявитися досить ефективним. Недолік, немає змісту розпаралелювати дії над короткими масивами;
двовимірні масиви
при виконанні вкладених циклів зазвичай ефективно розпаралелюються самі зовнішні цикли. Практично всі дії з матрицями, а саме множення, додавання, множення на вектор ... можна виконати на пластері. Недолік, неефективно використовувати пластери для матриць малої розмірності. Наприклад, 33. при збільшення розмірів матриць збільшується ефективність використання пластера;
кліткові автомати
в багатьох областях науки зустрічаються задачі, які зводяться до обчислення еволюції об’єктів, які взаємодіють із своїми сусідами. Наприклад, гра „Life”. Всі задачі такого роду розпаралелюються.
системи диференційних рівнянь
рішення систем диференційних рівнянь зустрічаються в багатьох інженерних та наукових задачах. В більшості випадків, алгоритм рішення подібних задач можна ефективно розпаралелити. Однак, слід врахувати, що паралельність задачі визначається не стільки її фізичним змістом, скільки вибраним числовим алгоритмом. Наприклад, метод прогонки не паралелізується. З іншого боку метод Монте-Карло ідеально підходить для кластерного комп’ютера.
Бібліотека мрі
Для написання програм, що можуть використовуватись на кластерних комп’ютерах, потрібно розробити інтерфейс обміну повідомленнями між кластерами для синхронізації процесів. Можна розробити свій власний інтерфейс, проте існує набір декількох стандартів, які можна використати у власних програмах.
На даний час найрозповсюдженішим є стандарт МРІ (Message Passing Interface). МРІ – це стандарт на програмний набір інструментів для забезпечення зв’язку між окремими процесами паралельних задач. МРІ представляє програмісту єдиний механізм взаємодії процесів в середині задачі незалежно від використаної архітектури, ОС чи взаємного розміщення процесорів. Даний стандарт являє собою набір функцій, які забезпечують обмін повідомленнями та синхронізацією. Використовувати бібліотеку слід обережно так як сам стандарт до кінця ще не доведений. При використанні програми МРІ змінюється парадигма програмування. В МРІ використовується парадигма, яка називається SPMD. При запуску задачі створюється група з Р – процесів, кожен із яких від 0 до Р-1. кожен процес може знати свій ідентифікатор. Поведінка всіх процесів описується однією програмою. Між процесорні взаємодії програмуються із використанням функцій FPI. Всі Р – процесів асинхронно виконують одну і ту ж саму програму, але в кожного з них є свій власний ідентифікатор (myProc). Тому в програмі мають бути такі фрагменти:
If (myProc= = 0) { . . . }
Else if (myProc= = 1) { . . . }
Else if (myProc = = 2) { . . .}
. . . . . . . . . .
таким чином в одній програмі „під одним дахом” закодована поведінка всіх процесорів. В цьому заключається парадигма SPMD (Single Program Multiple Data). За звичай, поведінка процесорів однакова для всіх, крім одного, який виконує функції координатора. За звичай, в якості координатора виступає процесор з 0-вим ідентифікатором.
Компіляція і запуск мрі – програм
У стандартну бібліотеку МРІ входять бібліотеки для мов С++ і Fortran. Проте є розроблені бібліотеки для мов Free Pascal і легко переробляється для Object Pascal. Програму обов’язково писати з парадигмою SPMD. Після компіляції програми екземпляр напускного файлу повинен бути скопійований всіма вузлами кластера в одну й ту ж саму папку з однаковими адресами. В ОС Windows цього можна досягти скопіювавши екземпляр програми в папку, яка є відкритою для мереженого доступу і вказавши мережений шлях до нього. В Unix – подібних ОС з використанням NFS – файлової системи. Для запуску програми використовують команду mpirun, параметрами для якої є кількість процесів, відповідно повна адреса до програми, яка буде запускатися. Після цього буде запущена вказана кількість копій програми. Ця кількість копій буде оптимально розподілена між вузлами.
Метакомп’ютери
На початку розвитку масово паралельні комп’ютери були досить дорогими та рідкісними. В наш час завдяки розвитку мережених технологій кластер можна створювати в будь-яких умовах.
Програміст може розділяти задачу між декількома комп’ютерами в мережі і отримувати результати. В такому розумінні можна використовувати глобальну мережу Internet. Взагалі кажучи, Інтернет можна розглядати як надпотужний єдиний паралельний комп’ютер з найбільшою в світі піковою продуктивністю та іншими характеристиками.
Комп’ютер, що складається з великої кількості інших комп’ютерів, називається метакомп’ютером. Звідси і походить назва процесу вирішення задач на таких комп’ютерах. Не обов’язково в якості комунікаційного середовища обирати Інтернет. Це може бути довільна мережева технологія. Основне не спосіб передачі даних, а принцип створення системи. Конструктивні ідеї використання розподілених обчислень ресурсів з’явилися на початку 90-х років. Деякі системи були універсальними, а деякі створювалися для вирішення певної задачі. В деяких системах використовувалися високопродуктивні мережі та спеціальні протоколи, а деякі системи використовували звичайні канали зв’язку і звичайні протоколи. Наведемо декілька прикладів.
Розширення МРІ, що використовується для проведення обчислень РАСХ-МРІ. Підтримуються розподілені обчислення шляхом створення єдиного метакомп’ютера МРІ шляхом з’єднання декількох МРІ –систем. Передача даних відбувається по протоколу ТСР/ІР, що дозволяє використовувати Інтернет, як комунікаційне середовище. У 1998 році було продемонстровано роботу такого комп’ютера, що складався з двох 512-ти-процесорних комп’ютерів Cray T3E, перший з яких знаходився в Німеччині, а другий в США.
Розподіляє задачу в корпоративні мережі система Condor, тоді, коли комп’ютери простоюють. Програмне забезпечення системи Condor існує для всіх операційних систем і є безкоштовним.
Проект SETI@Home – це проект пошуку неземних цивілізацій шляхом проведення розподілених обчислень і обробці даних, що поступають з радіотелескопу. Будь-хто може завантажити програму розкодування сигналу для будь-якої операційної системи. З моменту старту у 2002 році даного проекту, участь у ньому прийняли понад 4 млн. бажаючих. Сумарна продуктивність роботи системи за цей час була вищою за будь-які комп’ютери зі списку ТОР500 (список найбільш продуктивних комп’ютерів).
Ще один проект – GIMPS – пошук простих чисел Мерцена. Просте число Мерцена – це 2р-1, де р – просте число. На даний час завдяки розподіленим обчисленням отримали число 213466917-1. мета цього проекту досить проста: організація EFF запропонувала 100 000$ тій людині, яка представить число Мерцена з 10 млн. цифр.
Прогрес в мережених технологіях останнім часом дуже великий. Гігабітні канали зв’язку є досить звичайним явищем у наш час.
Об’єднавши різні обчислювальні системи в рамках єдиної мережі можна сформувати спеціальну обчислювальну систему. Деякі комп’ютери будуть від’єднуватись, деякі приєднуватись, проте для зовнішнього користувача все це має бути прозорим. Користувач задає тільки задачу, а система сама визначає, які вузли підключати, як перетворювати дані тощо. Для користувача все одно, як працює всередині метакомп’ютер. Можна провести аналогію з електричною мережею. Коли користувач вмикає електричний пристрій, йому байдуже, яка електростанція виробляє енергію. По цій аналогії обчислювальні мережі називають в англомовній літературі Creed.
При взаємодії метакомп’ютера з користувачем виникають наступні особливості:
Метакомп’ютер володіє дуже великими ресурсами, які навіть не йдуть у порівняння із звичайними комп’ютерами. Це пікова продуктивність, об’єм пам’яті, число доступних процесорів.
Метакомп’ютер є розподіленим по своїй природі. Складові метакомп’ютера можуть бути віддалені один від одного на сотні кілометрів, що впливає на швидкість їх взаємодії.
Метакомп’ютер може міняти конфігурацію. Деякі вузли можуть від’єднуватись, деякі приєднуватись, проте на роботу метакомп’ютера це впливати не повинно.
Метакомп’ютер не є однорідним. Він може включати в себе сотні, тисячі вузлів різної конфігурації з різними операційними системами. Все це повинно враховуватись при створенні метакомп’ютера.
Метакомп’ютер об’єднує комп’ютери багатьох організацій, в кожній з яких є своя власна політика доступу до ресурсів, адміністрування політики захисту.
Метакомп’ютер не належить нікому і тому його адміністрування проводиться в загальних рисах.
Говорячи про метакомп’ютер, мається на увазі не реалізація його апаратної частини, а принцип взаємодії його компонентів між собою.
При роботі з метакомп’ютером необхідно враховувати такі питання як: моделі програмування, розподілення і керування задачами, технологія організації доступу, інтерфейс з користувачем, безпека, надійність тощо.
Не дивлячись на здавалось би велику складність створення метакомп’ютера, на проблематику його роботи, вони здобули широке застосування у наш час. Метакомп’ютер дозволяє вирішити такі задачі, вирішення яких колись було нереальне. Наприклад, для побудови однієї макромолекули одному комп’ютеру потрібно було би декілька днів. І кількість числових експериментів для даної молекули може перевищити сотні тисяч. Жоден традиційний комп’ютер не володіє потужністю для вирішення даної задачі, проте спільні ресурси метакомп’ютера можуть допомогти.
Також до особливостей метакомп’ютерів можна віднести задачу розподіленого зберігання даних. В багатьох задачах об’єми даних, з якими працює дана задача, можуть перевищувати 1015 байт. Немає традиційного комп’ютера, який міг би зберігати таку інформацію. В метакомп’ютері всі ці дані розподілені на географічно віддалених між собою вузлах. Характерною задачею даної області є задача створення інформаційної системи для підтримки експерименту в фізиці високих технологій.
В 2006-2007рр. планується ввести в дію великий едронний колайдер європейськими організаціями ядерних випробувань. Чотири фізичні установки даного типу на протязі 15-20 років будуть зберігати інформацію 1015 байт кожного року. Під час експериментів дані будуть поступати зі швидкістю 100 Мбіт/с або 1 Гбіт/с. оптимальна схема зберігання усіх цих даних – це їх розподілення між сотнями учасників експерименту в світі.
Комп’ютерні ресурси кожного такого цеху повинні бути адекватно поставлені задачі, а саме, об’єм фізичної пам’яті 2.5 Пбайт (Пбайт=1015 байт). Об’єм зберігання на магнітних плівках 10-15 Пбайт, причому кожного року об’єм бази даних на магнітних плівках повинен збільшуватися на цю ж величину.
Продуктивність паралельних комп’ютерів
Необхідність оцінювання продуктивності комп’ютерів виникла з початку їх виникнення. Основна задача оцінювання – знайти оптимальний критерій для визначення ефективності роботи, що буде універсальним для вибору комп’ютера.
Однією з одиниць оцінки продуктивності є пікова продуктивність, тобто кількість операцій, що виконує комп’ютер у найбільш сприятливих умовах (конвеєри заповнені, дані в регістрах, немає конфліктів з пам’яттю). Проте пікова продуктивність – це лише теоретичний показник. На одних задачах продуктивність може досягати до пікової продуктивності, а на інших задачах буде досягати лише 2% пікової продуктивності.
Користувача цікавить, наскільки продуктивно комп’ютер буде працювати на його програмах, тому показник пікової продуктивності не є універсальним при виборі комп’ютера.
Ще один спосіб оцінки продуктивності – це обрахунок кількості операцій за секунду. Вимірюється в МІРS-ах. Для визначення цього показника достатньо порахувати кількість операцій процесора за одиницю часу. Цей показник також не є універсальним, так як кожний процесор має свій власний набір інструкцій і програма користувача може на різних процесорах утворювати різну кількість операцій. Наприклад, операція а+b на процесорах Intel буде потребувати 3 мікрооперації, 2 з яких – зчитування значень з пам’яті, а третя – безпосередньо додавання. На інших процесорах ця операція може мати іншу кількість мікрооперацій.
Інший приклад – комп’ютер ILLIAC IV. Продуктивність комп’ютера – 10 мільярдів операцій/с. проте продуктивність досягалась тільки при роботі з даними розмірності «байт». На більших розмінностях продуктивність різко падала. Ще один недолік використання даного показника – це неможливість точного вимірювання продуктивності з використанням співпроцесора. Якщо співпроцесор існує, то всі операції з плаваючою комою покладаються на нього, тобто головний процесор виконує меншу кількість операцій. Якщо ж співпроцесора немає, то головний процесор регулює його роботу, тобто починає виконувати велику кількість операцій для виконання дій з плаваючою комою, тобто фактично кількість збільшується. Виникає протиріччя: з використанням співпроцесора кількість інструкцій зменшується, а отже, продуктивність зменшується, проте операції з плаваючою комою виконуються швидко; а коли співпроцесора немає, кількість інструкцій за секунду велика, а отже, продуктивність велика, проте реально операції над числами з плаваючою комою виконуються повільніше.
Отже, при оцінці продуктивності комп’ютерних систем не варто користуватися лише апаратними показниками, потрібно також враховувати програмно-апаратне середовище. На основі деяких критеріїв формуються еталонні тестові програми, які при запуску на кожній комп’ютерній системі показують продуктивність даної системи. Ці програми називають benchmark.
Однією з найпопулярніших тестових програм є тест LINPACK, який для тестового завдання розв’язує систему рівнянь із щільною матрицею. Спочатку в цьому тесті розв’язується система із ста рівнянь. Проте продуктивність сучасних систем є настільки великою, що дана система рівнянь вирішується надзвичайно швидко і оцінити продуктивність стає неможливо. Тому дана програма поставляється з відкритим кодом і кожен користувач може змінювати розмірність матриці.
Також існує ще ряд тестових програм, наприклад STREAM для тестування векторних операцій, LFK, PERFECT та багато інших. Проте жоден з цих тестів не покаже реальну продуктивність системи. Тому потрібно проводити комплексне тестування системи, також потрібно чітко розуміти призначення комп’ютерної системи та які задачі вона буде вирішувати.
Підходи до організації обчислювального процесу та потокові машини
На сучасному етапі можна виділити наступні три підходи до організації обчислювального процесу:
Процедурне програмування
Даний підхід реалізовується майже в усіх машинах Фон-Неймановського типу. Дані машини повинні містити пристрій управління в процесорі, що містить вказівник на поточну команду, яка виконується, щоб команди послідовно зчитувалися і виконувалися на операційному пристрої, а результат записувався в запам’ятовуючий пристрій. Особливості принципів роботи машини даного типу наступні:
Послідовне виконання команд
Обробка даних з перезаписом в пам’яті та регістрі
При послідовній обробці швидкість визначається швидкодією елементів, що обмежує продуктивність ЕОМ. Ці обмеження обумовлені елементною базою кожного компонента.
Функціональне програмування
Обчислювальна модель, в якій програма розглядається як множина визначених функцій, називається функціональною моделлю. Для опису функціональних моделей використовують два типи мов програмування:
Використання аплікативних мов
Використання мов з однократним присвоєнням
Відмінною рисою цих моделей є те, що в їх основу покладена чітка і зрозуміла математична модель λ-перетворень.
Потокове програмування
Основна ідея потокового програмування або моделі обчислювального процесу по потоку даних заснована на операції обробки даних, яка активується цими даними. В даній моделі кожна операція виконується лише тоді, коли дані цієї операції готові для використання.
Реальне виконання деякої операції можливе тільки тоді, коли дані для цієї операції будуть готові дані, що передаються від однієї операції до іншої активізуючи дану операцію. В цьому принцип керування потоком даних наступний: всі операції виконуються тільки при наявності всіх операндів для її виконання.
Програма для машин даного типу задається у вигляді графа в якому вершини – це суть операції, а дуги – це напрямок передачі даних між операціями. Наприклад, y = (a+b)*c-(d+f)
z = c*b+y
граф обчислювального процесу:
a b c d f c b
0
+ + +
1
*
2
+
3
+
4
З показаного графа дуже чітко видно залежність даних один від одного, операції, що розміщені на одному рівні виконуються одночасно.
Основні відмінності від машин Фон-Неймановського типу наступні:
Операції з готовими операндами можна виконувати одночасно
Обмін даними між операціями чітко визначений, тому відношення залежності між операціями легко виявити
Оскільки управління операціями виконується шляхом передачі даних між ними, то немає необхідності в управлінні ходом виконання операцій, а отже, немає необхідності в централізованому управлінні даних.
Реалізація такої ідеї приводить до появи поняття командної комірки, яка повинна зберігати код операції, безпосередньо операнди операції та їх біти готовності та адресні поля, в яких вказуються поля операндів других командних комірок, в які відправляються результати даних операцій.
Схематично командну комірку можна зобразити наступним чином (рис. 19):
Рис. 19. Схематична командна комірка
В загальному вигляді машина потоків даних повинна містити пам’ять командних комірок, де зберігаються всі комірки з готовностями, арбітражну мережу, яка вибирає на виконання готові операції. Готові операції передаються в пул процесорних елементів, що одночасно виконують деякі прості операції. Результат операцій – розділена мережа записує в відповідні командні комірки та виставляє відповідні біти готовності даних. Операція вважається готовою для використання, якщо біти готовності для ор1 та ор2 одночасно рівні 1 (рис. 20).
Рис. 20. Структура машини потоків даних
Переваги даної архітектури є значно більша продуктивність чим в машинах Фон – Неймоновського типу та значно менша вартість виготовлення. Але основний недолік – це абсолютна абсолютна непридатність класичних програм для роботи на даній архітектурі.
Нестандартні архітектури пам’яті. Пам’ять з чергуванням адрес
Аналіз звернень в пам’ять особливо при обробці масивів показує, що доля звернень з послідовним збільшенням адреси достатньо велика. Для узгодження з конвеєром необхідно, щоб відбувалося випереджаюче зчитування у швидку регістрову пам’ять для послідовних адрес.
Таке випереджаюче зчитування і реалізовано у архітектурі з чергуванням адрес. Основна ідея полягає в тому, що адресний простір розподілений між банками пам’яті, так щоб сусідні слова розміщувалися в різних банках. При зверненні по деякій адресі всі еквівалентно адресовані слова всіх банків зчитуються у спеціальну швидку пам’ять, що називається фіксатором. При зверненні до наступного слова зчитування відбувається з фіксатора, а не з ОЗП.
Розглянемо більш детально архітектуру даної пам’яті. Коли відбувається зчитування з комірки за адресою 1, її значення зчитується фіксатором, причому у фіксатори зчитуються відповідні адреси з банку 2, 3, 0, тобто у фіксатори заносяться наступні m комірок, де m – кількість банків.
Розподілення адрес між m банками називають m-кратним чергуванням, звичайно m використовують як 2m. Таким чином ефект пам’яті залежить від кількості банків.
Рис. 21. Структурна організація банків пам’яті
Наприклад, коли відбувається зчитування з комірки із адресою 1, значення комірки записується у фіксатор. Але при цьому записуються значення комірки 0,2,3. наступне зчитування відбувається з наступного фіксатора (рис. 21).
Асоціативна пам’ять (безадресна пам’ять)
Асоціативна пам’ять являє собою сховище даних, в якому звернення до даних проходить полю ключа, що зберігається разом з даними. Схема порівняння (компаратор) виконує побітове порівняння вхідного із значенням ключів в словах асоціативної пам’яті. В результаті вибраними з пам’яті будуть ті слова, які мають аналогічний ключ.
В асоціативній пам’яті не використовується адрес, а кожна комірка описується своїм ключем. При пошуку даних в асоціативній пам’яті спеціальна схема порівняння (компаратор) порівнює вхідне значення із значеннями ключів в асоціативній пам’яті. В результаті будуть вибрані лише ті дані, які мають вказаний ключ.
Схема асоціативної пам’яті:
Рис. 21. Асоціативна пам’ять
Для виконання операції пошуку вільних слів та пошуку по декількох бітах ключа персонального комп’ютера асоціативною пам’яттю вводиться регістр маски, біти якого вказують, які біти регістра ключа треба порівнювати.
Ключ являє собою просте число, яке зв’язує комірки даних. Перевагою даного виду пам’яті є те, що за одну операцію зчитування можна зчитати декілька комірок одночасно, значення ключів – аналогічне.
Також в асоціативній пам’яті присутня маска пошуку, яка визначає, які біти ключів порівнювати при пошуку, а які ні. Це також робить систему гнучкою.
Недолік даного виду пам’яті – це несумісність з існуючими програмами та підходами.
Трансп’ютери
Трансп’ютер являється елементом побудови багатопроцесорних систем, який виконується на одному кристалі великої інтегральної схеми. Він включає засоби для виконання обчислень, такі як центральний процесор, АЛП для операцій з комою і внутрішня пам’ять об’ємом від 4 Кбайт, а також 4-канали для зв’язку з іншими трансп’ютерами із зовнішніми пристроями. Вбудований інтерфейс дозволяє підключати зовнішню пам’ять до 4 Гбайт (рис. 22).
Рис. 22. Схема трансп’ютера
Для створення трансп’ютерних систем, трансп’ютери можуть під’єднуватись один до одного або безпосередньо через спеціальний комутатор. Варіанти з’єднання показані на рис. 23.
Рис. 23. З ’єданння трансп ’ютерних систем
Схема із комутаторами зображена на рис. 24.
Рис. 24. Схема трансп’ютера із комутаторами
Як комутатори використовуються координатні перемикачі, які можуть одночасно забезпечити 16 пар зв’язків. Перемикачі знаходяться у вузлах решітки.
Організація трансп’ютерів базується на основі мови Occam. Основою даної мови являються засоби опису паралелізму використовуваних процесів, засоби опису між процесорного обміну даними, засоби опису розміщення процесів та обладнання.
Організація трансп’ютерів
Кожен канал трансп’ютера складається із двох різнонаправлених одно розрядних каналів, які називаються linkin, link.out. всі канали працюють незалежно один від одного.
В ЦП використовується 6 регістрів 32-розрядних:
1. вказівник області для локальних змінних в програмі;
2. вказівник наступної команди;
3. регістр операндів, де формуються операнди та команди.
Регістри А, В, С формують обчислювальний стек. Вся система команд та АЛП трансп’ютера формується по стековому принципу LIFO (рис. 23).
Регістри Список планувань Команди
Рис. 23. Регістрова будова трансп’ютера
Наявність обчислювального стеку відкидає необхідність задання в командах явних операндів. Наприклад, команда ADD додає числа в регістрах A і B, результат записує в регістр A, а значення регістру С в B.
В трансп’ютері крім обчислювального стеку для цілочисельної арифметики присутній стек для роботи із числами з плаваючою комою в регістрах AF, BF, CF.
Список команд трансп’ютера включає 110 команд, вони діляться на три групи:
із прямою адресацією, 1 байт;
із непрямою адресацією, 2 і більше байт.
Трансп’ютер може одночасно обробляти будь-яку кількість паралельних процесів. Він має спеціальний розподілювач, що розділяє час між процесорами. В будь-який момент часу процеси діляться на 2 класи:
активні процеси, які виконуються або готові до виконання;
не активні процеси.
Активні процеси, що очікують виконання розміщуються в список планування, що є списком робочих областей цих активних процесів в пам’яті. Він задається значеннями двох регістрів: перший вказує на перший процес, а другий – на останній процес в списку. Стан процесу готового до виконання зберігається в його робочій області. Стан визначається двома словами: поточними значеннями вказівника інструкцій та вказівником на робочу область наступного процесу.
На рис. 23 P, Q, R, S – деякі процеси. Кожен із яких має вказівник на команду і наступну робочу область. Процес S – в даний момент виконується, а P,Q,R – очікують виконання.
Команда трансп’ютера start process створює новий активний процес додаючи його в кінець списку планувань. Дана команда дозволяє новому паралельному процесу виконуватись разом із іншими процесами, які трансп’ютер обробляє в даний момент часу.
Команда end process закінчує поточний процес та забирає його із списку планувань.
При обробці паралельних процесів насправді існує не один список планувань, а два: список із високим рівнем пріоритету і список із низьким рівнем пріоритету. Процеси із низьким рівнем пріоритету виконуються тільки тоді, коли список високо пріоритетних команд пустий. Процеси із високим пріоритетом вводяться для забезпечення системи в реальному часі.
Комутації між паралельними процесами реалізуються через канали при чому існують так звані внутрішні канали, для обміну даними між процесами в середині одного трансп’ютера та зовнішніми каналами для зв’язку іщ процесами на інших трансп’ютерах.
Не дивлячись на принципові відмінності в реалізації внутрішніх та зовнішніх каналів команди обміну однакові і різняться лише адресами. Це дозволяє реалізувати компіляцію програми незалежно від способу реалізації каналів, а отже і не залежно від конфігурації обчислювальної системи в цілому.
Розглянемо передачу даних по зовнішньому каналі. Команда передачі даних направляє автономному канальному інтерфейсу задачу на передачі даних і призупиняє виконання процесу. Після закінчення передачі даних канальний інтерфейс розміщує цей процес в список планування. Під час виконання передачі даних обидва процеси, що обмінюються даними стають не активними. Це дозволяє трансп’ютеру продовжити обробку інших процесів під час пересилки через більш повільні конали. Кожен канальний інтерфейс використовує три свої регістри в які він записує вказівник на робочу область процесу, адресу даних, що передаються і кількість байт, що будуть передаватися. Для передачі даних використовують простий протокол який не залежить від розрядності трансп’ютера. Це дозволяє об’єднувати трансп’ютери різних типів. Повідомлення передаються у вигляді окремих пакетів кожне із яких містить 1 байт даних. Після відправки пакету даних трансп’ютер очікує отримання пакета підтвердження від приймаючої сторони. Тільки після цього передається наступний байт.
Характеристики трансп’ютерів
Трансп’ютери виготовляються фірмою INMOS починаючи із 1985р. Всі моделі окрім моделі Т212 мають чотири канали зв’язку та 32 – розрядний арифметико – логічний пристрій. Модель Т212 має 16 – розрядний АЛП та містить два канали зв’язку.
Система команд трансп’ютерів відноситься до архітектури CISC. В сімействі трансп’ютерів ці моделі після моделі Т9000 є суперскалярним. Він має наступні особливості:
введений 5-ти стадійний конвеєр;
можливе одночасне виконання декількох команд не тільки за рахунок конвеєризації, а й за рахунок розпаралелювання операцій на окремих стадіях конвеєра;
внутрішня пам’ять має об’єм до 16 Кбайт і може використовуватись або як кеш пам’ять або як адресна пам’ять;
наявний пристрій групування команд який виявляє пари інструкцій, що можуть використовуватись одночасно.
В комплект Т9000 входить мікросхема комутатора IMS C104, яка має 32*32 не блокуючих однорозрядних ліній зв’язку. Даний комутатор створює зв’язок за 700нсек. За допомогою цього комутатора можна будувати багато транспортні системи практично необмеженого розміру.
Трансп’ютери використовуються як і для побудови багато транспортних систем так і для побудови акселераторів для ПК.
Функціонально розподілені системи
В ЕОМ перших трьох поколінь всі обчислювальні функції реалізовувались одним процесором і інтерпретувалися ним, як арифметичні та логічні операції. Висока продуктивність системи утворилась на основі багатопроцесорних комплексів.
Використання в таких комплексах однотипних процесорів є економічно невигідним, оскільки в кожному процесорі використовується лише та частина ресурсів, яка необхідна для виконання певної операції в певний момент часу. Найбільш економічний спосіб побудови багатопроцесорних систем – це використання спеціалізованих процесорів, орієнтованих на реалізацію певних функцій: обробка скалярних величин, текстів, матрична обробка, ввід-вивід даних.
Система складається із сукупності процесорів, що мають індивідуальну та основну пам’ять (рис. 24).
Рис. 24. Функціонально розподілена система
Система складається із сукупності процесорів, що мають індивідуальну та основну пам’ять – кожен процесор виконує певний вид операцій. Ядро системи забезпечує інформаційне спряження усіх пристроїв. Воно реалізоване у вигляді системної шини комунікаційного поля або комутатора основної пам’яті. Управляючий процесор виконує супер візарні функцій (керуючі функцій). Обробляючий процесор виконує обробку числових та символьних даних. Матричний – матричну обробку. Процесор баз даних забезпечує роботу із жорсткими дисками, а процесор вводу/виводу забезпечує контроль над вхідною або вихідною інформацією.
В залежності від конкретної задачі управляючий процесор розподіляє функції та завдання між спеціалізованими процесорами . Даний підхід до створення багатопроцесорних систем є більш економічно вигідним ніж утворення багатопроцесорних систем на однотипних процесорах.
Обчислювальні системи з структурою, що перебудовується
Обчислювальні системи з структурою, що перебудовується будуються на основі мікропроцесорних модулів. Модуль повинен реалізовувати наступні функції:
обробку даних, що зводиться до обробки числових та логічних значень та рядків;
управління обчислювальним процесом, що забезпечує взаємодію модуля із групою модулів та системою в цілому;
встановлення з’єднання із іншими модулями і передачу даних між ними для забезпечення обчислювального процесу.
З урахуванням усіх цих функцій модуль обчислювальної системи розглядається як сукупність трьох процесорів – обробляючого, управляючого та комунікаційного.
Комунікаційний пристрій забезпечує обслуговування кількох каналів передачі даних. Фізично модуль може реалізуватися на основі однієї мікро ЕОМ, яка виконує в мультипрограмному режимі функції обробки управління процесорами та передачі даних.
В системах, що перебудовуються модулі об’єднуються в найпростіші структури, які дозволяють достатньо легко визначити шляхи з’єднань між взаємодіючими модулями. Найбільш зручними структурами для побудови розглядуваних систем є матричні, пірамідальні та кубічні.
Організація обчислювальних процесів забезпечується наступними засобами: після вводу завдання в систему, модуль, що прийняв завдання, посилає через комунікаційне середовище запит на пошук вільного модуля. Коли він знайдений, йому посилається завдання, що визначає:
імена наборів даних, в яких розміщується програма
вихідні дані
дані, в яких будуть розміщені результати обчислень
Із завдання та програми модуль дізнається про необхідні ресурси, закріплює їх за собою і після цього ініціює виконання завдання. Після завершення роботи ресурси звільняються і відбувається очікування наступного завдання.
Паралельні програми будуються традиційним способом: виділення під задач та гілок програми, операції над векторами і матрицями та організація конвеєрної обробки даних.
В обчислювальній системі, що перебудовується повинно бути реалізовано децентралізоване управління ресурсами. Це означає, що в системі не повинно існувати окремого модуля, що відповідає за централізований розподіл ресурсів. Розподілене управління засноване на узгодженій роботі всіх модулів системи. Кожний з модулів реалізує однаковий набір правил управління, що забезпечує ефективне використання всіх ресурсів системи. Розподілене управління підвищує надійність системи, так як кожний модуль здатний реалізувати управління ресурсами. Як і в будь-якій багатопроцесорній системі, механізм управління повинен включати взаємне блокування процесів при запитах ресурсів. Для усунення блокування використовуються різні механізми управління ресурсами:
одночасне формування запитів на всі необхідні ресурси
розподіл ресурсів по типах
ієрархічний порядок виділення ресурсів
Матричні системи
Під матричними системами або матричними процесорами за звичай розуміють багатопроцесорну систему в якій процесори за допомогою певної мережі об’єднані в матрицю. Задача пристрою управління матричним процесором разом із операційною системою оптимально завантажити матриці процесорів та ефективно передавати дані між ними. Розпаралелюватись можуть етапи рішення задачі, машинні команди або навіть бітові операції.
Існує велика кількість методів реалізації матричних систем, а також реалізації зв’язків матричних систем. Розглянемо основні із них:
однорідні системи
В даній матричній системі елементами матриці являються процесори зі своєю власною оперативною пам’яттю. Вершини графа обчислювально процесу розподіляються між процесорами матриці, а вказані зв’язки на управління даними, що реалізуються за допомогою мережі, яка об’єднує ці процесори.
Ефективність функціонування даної системи вимагає однорідності під задач по часові виконання, а також однорідності по ресурсах тобто однорідність апаратної реалізації повинна відповідати однорідності задач, які будуть виконуватись на даній матричній системі. При умові, що на будь-якому процесорі однорідної матричної системи кожна під задача виконується за однаковий час. Паралельні вітки в графі обчислювального процесу будуть закінчуватися одночасно. Виконання такої умови забезпечує використання однорідної системи мінімізуючи тим самим час переходу на наступний етап.
Зрозуміло, що така ідеологія пов’язана із надлишковістю однорідності матриці. Так як мінімальна необхідна кількість процесорних елементів рівна максимальній кількості паралельних етапів в графі обчислювального процесу.
Відмітимо, що проблема розподілення задачі на однорідні етапи повинна вирішуватись програмістом. В зв’язку із тим, що різні задачі мають різні шрафи обчислювального процесу реально задіяна структура процесорних елементів та зв’язків суттєво міняється для різних задач. Тому такі системи отримали назву однорідні матричні системи, що перебудовуються.
Рис. 25. Однорідна процесорна матриця
Ідея однорідних систем була запропонована на початку 60-х років минулого століття у вигляді трьох принципів побудови системи:
паралельність під задач в алгоритмах;
змінність логічної структури;
однорідність елементів та зв’язків між ними.
матриці хвильового фронту даних;
Цей підхід до організації матричних систем заснований на принципі управління потоком даних. На відміну від машинних потоків даних де арбітражна мережа вибирає готові до використання команді комірки. У матричному процесорі кожен елемент матриці являє собою самостійний арифметико-логічний пристрій із призначеною командною коміркою.
Передаючи результат виконання команд процесори активують один-одного створюючи динамічну по часу активну процесорну структуру.
Рис. 26. Матриця хвильового фроту
Однак реалізація матриці хвильового фронту даних вимагає достатньо складного алгоритму управління так як керуючий процесор повинен відслідковувати динамічний стан матриці і при умові, що кількість АЛП в матриці менша кількості команд комірок розсилати нові командні комірки на заміну тим, що вже виконались.
класичні матричні системи;
Класичні матричні системи реалізують принцип „єдиний потік команд – множинний потік даних”.
Процесорна матриця складається із множини процесорних елементів та одного пристрою керування. Пристрій керування одночасно передає всім процесорним елементам одну і ту ж саму команду. Тому на всіх процесорних елементах одночасно виконується одна і та ж сама команда проте із різними даними. Схема матричної система зображена на рис. 27.
Рис. 27. Класична матрична система
Дана архітектура орієнтована на задачі обробки матриць та обробки зображень.