Систолічний масив

У паралельних комп'ютерних архітектурах, систолічний масив є однорідною мережею щільно з'єднаних блоків обробки даних, які називаються клітинами або вузлами. Систолічні масиви були винайдені Річардом Брентом і Кунгом, який розробив їх для обчислення найбільших спільних дільників цілих чисел і поліномів. Вони іноді класифікуються як декілька команд одноядерних даних (MISD) архітектури з систематики Флінна, але ця класифікація залишається під питанням, бо існує вагомий аргумент, щоб відрізнити систолічний масив від будь-якої з чотирьох категорій Флінна: SISD, SIMD, MISD, MIMD, який буде зазначено далі в цій статті.

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

Область застосування

Систолічні масиви часто використовують для конкретних операцій, таких, як «поширення і накопичення», щоб виконати в широкому масштабі паралельну інтеграцію, згортку, кореляцію, множення матриць або сортування даних завдань. Вони також використовуються для динамічного програмування алгоритмів, використовуваних в ДНК і аналізу послідовності білку.

Особливості

Таким чином, систолічна структура — це однорідне обчислювальне середовище з процесорних елементів, що поєднує в собі властивості конвеєрної і матричної обробки і володіє наступними особливостями:

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

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

В даний час досягнута продуктивність систолічних процесорів близько 1000 мільярдів операцій/с.

Архітектура

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

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

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

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

Цілі і переваги

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

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

Класифікаційна дискусія

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

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

Незважаючи на все вищесказане, систолічні масиви часто пропонуються як класичний приклад MISD архітектури як в підручниках по паралельних обчисленнях, так і в інженерному класі. Якщо масив розглядається з зовнішнього боку, як атомарна операція, то можливо його класифікувати як SFMuDMeR = Однофункціональні (Single Function), Багаторазові дані (Multiple Data), Об'єднані в результат (s) (Merged Result).

Детальний опис

Систолічний масив складається з матриць типу рядів блоків обробки даних, званих датчиками. Блоки обробки даних аналогічні центральним процесорам (CPU), (окрім для ситуації звичайної відсутності лічильника програми, коли операція транспортно-спрацьовує, тобто після прибуття об'єкта даних). Кожна клітинка ділиться інформацією зі своїми сусідами відразу після обробки. Систолічний масив часто прямокутної форми, де потік даних проходить через весь масив між сусідніми блоками обробки даних, часто з різним потоком даних в різних напрямках. Потоки даних, що надходять і виходять з портів масиву генеруються блоками пам'яті автоматичного секвенування, ASMs (auto-sequencing memory units). Кожен блок ASM включає в себе дані лічильника. У вбудованих системах потік даних може бути також введений і (або) виходити до зовнішнього джерела.

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

Систолічні масиви це масиви блоків обробки даних, які підключені до кількох найближчих сусідів блоку обробки даних в сітчастій топології. Блоки обробки даних виконують послідовність операцій над даними, що передаються між ними. Так як традиційні методи синтезу систолічного масиву практикувалися алгебраїчними алгоритмами, можуть бути отримані тільки уніфіковані масиви з тільки лінійними трубами, так що архітектура однакова у всіх блоках обробки даних. Наслідком цього є те, що тільки програми з регулярною залежністю даних можуть бути реалізовані на класичних систолічних масивах. Як SIMD машини, систолічні масиви з тактовою частотою замкнуто-пошагово обчислюються з кожним процесором беручи альтернативні обчислювання | зв'язок фаз. Але систолічні масиви з асинхронним зв'язком між блоками обробки даних називаються масивами хвильового фронту. Один добре відомий систолічний масив це iWarp процесор Університету Карнегі — Меллон, який був виготовлений виробником Intel. Система iWarp має лінійний матричний процесор, з'єднаний з шинами даних, що йдуть в обох напрямках.

Історія

Систолічні масиви (< процесорів хвильового фронту), були вперше описані Кунгом і Лейзерсоном, які опублікували перший документ, що описує систолічні масиви в 1978 р. Проте перша машина, яка використовувала подібну техніку була Колос Mark II в 1944 році.

Приклад застосування

Поліноміальна оцінка:

Схема Горнера для обчислення багаточлена:

$y=(...(((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+...+a_{1})\cdot x+a_{0}.$

Лінійний систолічний масив, в якому процесори розташовані попарно: один примножує його вхід на х і передає результат вправо, наступний додає $a_{j}$ і передає результат далі.

Переваги та недоліки

Плюси:

Швидкий;
Масштабний;

Мінуси:

Дорогий;
Не широко застосовується;
Обмежений базовий код програм і алгоритмів;
Вузькоспеціалізований, часто виготовлений на замовлення обладнання конкретного додатка.

Реалізації

Cisco PXF — мережевий процесор внутрішньо організований як систолічний масив.

Див. також

MISD — Multiple Instruction Single Data, Приклад: систолічний масив.

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

Цилькер Б. Я. Організація ЭОМ та систем: Підручник для вузів / Б. Я. Цилькер, С. А. Орлов. — 2-е вид. — СПб.: Питер, 2011. — 688 с. — ISBN 978-5-49807-862-5.
Н. Петков: Систолічна паралельна обробка; Північна Голландія,1992.