Бухтiяров Станiслав Олексiйович   

Факультет: Обчислювальної техніки та інформатики
Кафедра: Електронних обчислювальних машин
Спеціальність: Комп'ютерні системи та мережі
Група: КС-06м

Тема магістерської роботи:

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

Керівник: проф.  Баркалов О.О.

Автореферат

Тема:

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

Керівник:

проф. Баркалов О.О.

Консультатнт:

Особливості магістерської роботи

Ввідна частина:

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

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

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

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

Паралельні ЕОМ часто підрозділяються по класифікації Флінна на машини типа SIMD (Single Instruction Multiple Data - з одним потоком команд при множинному потоці даних) і MIMD (Multiple Instruction Multiple Data - з множинним потоком команд при множинному потоці даних). Як і будь-яка інша, приведена вище класифікація недосконала: існують машини прямо в неї не потрапляючі, є також важливі ознаки, які в цій класифікації не враховані. Зокрема, до машин типа SIMD часто відносять векторні процесори, хоча їх висока продуктивність залежить від іншої форми паралелізму - конвейєрної організації машини. Багатопроцесорні векторні системи, типа Cray Y-MP, складаються з декількох векторних процесорів і тому можуть бути названі MSIMD (Multiple SIMD).

Класифікація Флінна не робить відмінності по інших важливих для обчислювальних моделей характеристиках, наприклад, по рівню "зернистості" паралельних обчислень і методам синхронізації.

Основна частина:

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

Звичайно подібні високопродуктивні системи мають декілька іншу, ніж робочі станції або мейнфрейми, архітектуру. Потреба в обробці великих масивів багатовимірних даних, а також залежність розмірів алгоритмів обробки сигналів від ступеня паралелізму призводять до того, що для вирішення поставлених задач застосовуються пристрої із сполученими в мережу і даними по самих різних комунікаційних каналах, що обмінюються, процесорами. Найбільш відома архітектура типу гіперкуб, систоли і багатоканальні, з використанням DSP-процесорів. У цих DSP-процесорах елементарна обчислювальна потужність поєднується з високопродуктивними каналами введення/висновку. Наприклад, процесор SHARC компанії Analog Devices має шість зв'язних портів з пропускною спроможністю 40 Мбайт/с кожен.

Можна виділити чотири основні типи архітектури систем паралельної обробки:

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

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

2) Машини типа SIMD.

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

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

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

3) Машини типа MIMD

Термін "мультипроцесор" покриває більшість машин типа MIMD і (подібно тому, як термін "матричний процесор" застосовується до машин типа SIMD) часто використовується як синонім для машин типа MIMD. У мультипроцесорній системі кожен процесорний елемент (ПЕ) виконує свою програму достатньо незалежно від інших процесорних елементів. Процесорні елементи, звичайно, повинні якось зв'язуватися один з одним, що робить необхідним докладнішу класифікацію машин типа MIMD. У мультипроцесорах із загальною пам'яттю (сильносвязанних мультипроцесорах) є пам'ять даних і команд, доступна всім ПЕ. Із загальною пам'яттю ПЕ зв'язуються за допомогою загальної шини або мережі обміну. У протилежність цьому варіанту в слабосвязанних багатопроцесорних системах (машинах з локальною пам'яттю) вся пам'ять ділиться між процесорними елементами і кожен блок пам'яті доступний тільки пов'язаному з ним процесору. Мережа обміну зв'язує процесорні елементи один з одним.

Базовою моделлю обчислень на MIMD-мультипроцесорі є сукупність незалежних процесів, що епізодично звертаються до даних, що розділяються. Існує велика кількість варіантів цієї моделі. На одному кінці спектру - модель розподілених обчислень, в якій програма ділиться на досить велике число паралельних задач, що складаються з безлічі підпрограм. На іншому кінці спектру - модель потокових обчислень, в яких кожна операція в програмі може розглядатися як окремий процес. Така операція чекає своїх вхідних даних (операндів), які повинні бути передані їй іншими процесами. Після їх отримання операція виконується, і набуте значення передається тим процесам, які його потребують. У потокових моделях обчислень з великим і середнім рівнем гранулярності, процеси містять велике число операцій і виконуються в потоковій манері.

4) Багатопроцесорні машини з SIMD-процесорами.

Багато сучасних СУПЕРЕОМ є багатопроцесорними системами, в яких як процесори використовуються векторні процесори або процесори типа SIMD. Такі машини відносяться до машин класу MSIMD.

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

Багатопроцесорні системи за роки розвитку обчислювальної техніки зазнали ряд етапів свого розвитку. Історично першої стала освоюватися технологія SIMD. Проте в даний час намітився стійкий інтерес до архітектури MIMD. Цей інтерес головним чином визначається двома чинниками:

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

Архітектура MIMD може використовувати всі переваги сучасної мікропроцесорної технології на основі строгого обліку співвідношення вартість/продуктивність. Насправді практично всі сучасні багатопроцесорні системи будуються на тих же мікропроцесорах, які можна знайти в персональних комп'ютерах, робочих станціях і невеликих однопроцесорних серверах.

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

У архітектурі з локальною пам'яттю безпосереднє розділення пам'яті неможливе. Натомість процесори дістають доступ до спільно використовуваних даних за допомогою передачі повідомлень по мережі обміну. Ефективність схеми комунікацій залежить від протоколів обміну, основних мереж обміну і пропускної спроможності пам'яті і каналів обміну.

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

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

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

До першої групи відносяться машини із загальною (що розділяється) основною пам'яттю, об'єднуючі до декількох десятків (звично менше 32) процесорів. Порівняно невелика кількість процесорів в таких машинах дозволяє мати одну централізовану загальну пам'ять і об'єднати процесори і пам'ять за допомогою однієї шини. За наявності у процесорів кеш-пам'яті достатнього об'єму високопродуктивна шина і загальна пам'ять можуть задовольнити звернення до пам'яті, поступаючі від декількох процесорів. Оскільки є єдина пам'ять з одним і тим же часом доступу, ці машини іноді називаються UMA (Uniform Memory Access). Такий спосіб організації з порівняно невеликою пам'яттю, що розділяється, в даний час є найпопулярнішим.

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

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

Розподіл пам'яті між окремими вузлами системи має дві головні переваги. По-перше, це ефективний з погляду вартості спосіб збільшення смуги пропускання пам'яті, оскільки більшість обігу може виконуватися паралельно до локальної пам'яті в кожному вузлі. По-друге, це зменшує затримку звернення (час доступу) до локальної пам'яті. Ці дві переваги ще більше скорочують кількість процесорів, для яких архітектура з розподіленою пам'яттю має сенс. Звично пристрої введення/висновку, також як і пам'ять, розподіляються по вузлах і насправді вузли можуть складатися з невеликого числа (2-8) процесорів, сполучених між собою іншим способом. Хоча така кластеризація декількох процесорів з пам'яттю і мережевий інтерфейс можуть бути достатньо корисними з погляду ефективності у вартісному виразі, це не дуже істотно для розуміння того, як така машина працює, тому ми поки зупинимося на системах з одним процесором на вузол. Основна різниця в архітектурі, яку слід виділити в машинах з розподіленою пам'яттю полягає в тому, як здійснюється зв'язок і яка логічна модель пам'яті.

Завершальна частина:

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

- забезпечують таку продуктивність, яка близька до пікової продуктивності на будь-якому класі вирішуваних задач;

- дають можливість програмувати архітектуру, включаючи прямі канали комунікацій, набори макро операцій, внутрішню мову високого рівня і структуру розподіленої пам'яті;

- забезпечують практично лінійне зростання продуктивності пропорційно числу паралельно функціонуючих супер трансп'ютерів;

- забезпечують за рахунок оригінальних апаратно-програмних засобів і модульного принципу організації масштабованість системи.

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

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

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

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

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

Щоб відстежити, чи є блок тим, що розділяється, ми можемо ввести додатковий біт стану (shared), пов'язаний з кожним блоком, точно також як це робилося для бітів достовірності (valid) і модифікації (modified або dirty) блоку. Додавши біт стану, що визначає чи є блок тим, що розділяється, ми можемо вирішити питання про те, чи повинен запис генерувати операцію анулювання в протоколі з анулюванням, або операцію трансляції при використовуванні протоколу з оновленням. Якщо відбувається запис в блок, що знаходиться в змозі що "розділяється" при використовуванні протоколу запису з анулюванням, кеш формує на шині операцію анулювання і позначає блок як приватний (private). Ніяких подальших операцій анулювання цього блоку даний процесор посилати більше не буде. Процесор з винятковою (exclusive) копією блоку кеш-пам'яті звичайно називається "власником" (owner) блоку кеш-пам'яті.

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

Оскільки будь-яка транзакція на шині контролює адресні теги кеша, потенційно це може приводити до конфліктів із зверненнями до кеша з боку процесора. Число таких потенційних конфліктів можна понизити застосуванням одного з двох методів: дублюванням тегов, або використовуванням багаторівневих кешів з "обхватом" (inclusion), в яких рівні, що знаходяться ближче до процесора є піднабором рівнів, що знаходяться далі від нього. Якщо теги дублюються, то обіг процесора і спостереження за шиною можуть виконуватися паралельно. Звичайно, якщо при обігу процесора відбувається промах, він повинен буде виконувати арбітраж з механізмом спостереження для оновлення обох наборів тегов. Точно також, якщо механізм спостереження за шиною знаходить співпадаючий тег, йому буде потрібно проводити арбітраж і звертатися до обох наборів тегов кеша (для виконання анулювання або оновлення бита що "розділяється"), можливо також і до масиву даних в кеші, для знаходження копії блоку. Таким чином, при використовуванні схеми дублювання тегов процесор повинен припинитися тільки в тому випадку, якщо він виконує звернення до кеша в той же самий момент часу, коли механізм спостереження знайшов копію в кеші. Більш того, активність механізму спостереження затримується тільки коли кеш має справу з промахом.

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

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

СПИСОК ЛiТЕРАТУРИ:

1. Глушков В.М. Синтез цифровых автоматов. - М.: Физматгиз,1962. - 476 с. 2. Глушков В.М., Капитонова Ю.В., Мищенко А.Т. Логическое проектирование дискретных устройств. - Киев: Наук, думка, 1987. - 264 с.3. Варшавский В.И. Однородные структуры: Анализ. Синтез.Поведение.М.Энергия,1973.-152 с4. Евреинов Э.В. Однородные вычислительные системы,структуры и среды. М Радио и связь, 1981. - 208 с. 5. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраиваемой структурой (однородные среды). - М.: Энергия, 1974. - 240 с.