Тема 9 — Систолични процесори

1. Въведение

VLSI технологията позволява интеграция на стотици хиляди компоненти върху единична силициева подложка. Именно тя открива пътя към масивни паралелни изчисления при компактни, енергоефективни архитектури. Систоличната обработка произлиза от работата на Кунг и Лейсерсон от Carnegie Mellon University, описана за пръв път в края на 70-те години.

По същество систоличната обработка е конвейерна обработка в мрежа от елементи. Нейните принципи са изначално съвместими с VLSI технологията, което я прави привлекателен избор за хардуерна реализация.

Дефиниция. Систолична матрица е мрежовидна структура от елементи (клетки), обработващи данни чрез n-мерен конвейер. За разлика от обикновения конвейер, при систоличната матрица входните и междинните данни се движат физически из матрицата от клетки — те могат да се движат с различна скорост и в различни посоки. Само граничните клетки взаимодействат с паметта; останалите обменят данни единствено помежду си.

Пример за систолична матрица с Output Stationary конфигурация. Данните “протичат” през масив от прости изчислителни клетки, всяка от които натрупва частичен резултат.

Процесорните елементи са прости клетки, обикновено съдържащи един-два регистъра, суматор и/или умножител. Моделът на свързване трябва да бъде прост, регулярен и само с локални връзки — дългите пътища за данни увеличават закъснението и изразходват повече площ и енергия, което е особено критично при висока тактова честота.

Характерните свойства на VLSI-съвместими систолични структури са: висока степен на модулност, липса на дълги пътища за данни, локалност на връзките, ограничени но достатъчни изчислителни възможности на клетките, липса на централно управление и прости механизми за синхронизация.

Систоличните матрици са подходящи само за алгоритми с повтарящи се изчисления — обработка на сигнали, линейна алгебра и алгоритми с вложени цикли. Извличането на данни от паметта трябва да бъде последвано от максимален брой операции върху тях, преди да се запишат обратно, тъй като I/O каналът е вероятното тясно място.

2. Видове систолични матрици

Систоличните матрици се различават по три характеристики:

Топология — начинът на свързване между клетките определя ефективността за различни класове алгоритми.

Функционални възможности на клетките:

• Прости аритметично-логически устройства (само елементарни операции)
• Аритметично-логическо устройство с няколко регистъра
• Прост процесор с локална програма
• Процесорен модул (процесор + памет + допълнителна логика)

Реконфигурируемост — FPGA (Field Programmable Gate Arrays) предлагат възможност за препрограмиране, което прави малките систолични матрици достъпни за широк кръг приложения.

Клас	Тип	Организация	Топология
Специализирани	Хардуерни	FVIMD	Фиксирана
Универсални	Програмируеми	SIMD/MIMD	Статична/Динамична
Универсални	Реконфигурируеми	FVIMD	Реконфигурируема
Универсални	Хибридни	Хибридна	n-размерна

Съкращения: FVIMD — Very Few Instructions Multiple Data; SIMD — Single Instruction Multiple Data; MIMD — Multiple Instruction Multiple Data.

3. Специализирани систолични матрици

При специализираните систолични матрици архитектурата се проектира конкретно за всяко приложение. Функциите са хардуерно имплементирани, а топологията — фиксирана. Областта с най-естествено приложение са матричните операции.

3.1. Скаларно произведение на вектори

Базовата систолична клетка изчислява скаларното произведение:

$s = \sum_{i=1}^{n} a_i \cdot b_i$

След инициализация елементите на векторите a и b синхронно преминават през клетката — всяка двойка a[i], b[i] се умножава и произведението се натрупва в акумулатора. Резултатът s се извежда след завършване на обработката.

3.2. Матрично умножение

На базата на клетката за скаларно произведение се изгражда систолична матрица за матрично умножение. За матрици 3×3 е необходима матрица от 9 клетки (c[i][j]). Разликата спрямо единичната клетка е закъснение от един цикъл за всеки допълнителен ред и стълб — елементите на матриците постъпват с отместване, за да пристигнат синхронно в съответните клетки.

Ключово предимство: след като даден елемент a[1][1] се извлече от паметта, той се използва не само от клетка c[1][1], но и от c[1][2] и c[1][3] — намален достъп до паметта в сравнение с последователен алгоритъм.

3.3. Ограничения на специализираните матрици

Обработката на матрици с по-голяма размерност от систоличната матрица изисква разделянето им на по-малки части и поетапна обработка, което намалява ефективността поради паралелно-последователния характер на изчисленията.

По-съществен е проблемът с цената на приложение — чистото хардуерно изпълнение гарантира висока производителност, но функционалността е тясно специализирана. Решението се търси в разработването на архитектури с универсално приложение.

4. Универсални систолични матрици

Универсалните систолични матрици са три вида: програмируеми, реконфигурируеми и хибридни. Размерността им е обикновено едно- или двумерна — при по-голяма размерност I/O ограниченията стават prohibitive.

4.1. Warp и iWarp

Проектите Warp и iWarp — разработени съвместно от Carnegie Mellon University и Intel Corporation — демонстрират осъществимостта на систоличната обработка за универсални цели. Проектантите на Warp избират малък брой (10) структурно сложни клетки вместо голям брой прости, за да постигнат гъвкавост и широк обхват от приложения.

Всяка Warp клетка включва:

• RAM памет за данни (32K думи)
• Два регистрови файла по 32 регистъра
• Три опашки по 512 думи
• 6 входно-изходни канала

Warp — 10 клетки в едномерна матрица.

iWarp — 32×32 клетки в двумерна матрица, обща пикова производителност 20 GFLOPS.

Резюме

• Систоличната обработка е конвейерна обработка в мрежа от прости, плътно свързани клетки; данните се движат физически из матрицата, а само граничните клетки взаимодействат с паметта.
• Архитектурата е съвместима с VLSI благодарение на локалните връзки, модулността и опростените механизми за синхронизация.
• Подходяща е само за алгоритми с повтарящи се изчисления (матрични операции, цифрова обработка на сигнали), при които едно извличане от паметта поражда много операции.
• Специализираните матрици постигат максимална производителност за конкретна задача, но са неизползваеми за други.
• Универсалните матрици (Warp, iWarp) балансират между производителност и гъвкавост чрез по-сложни програмируеми клетки.
• FPGA технологията позволява реализация на малки реконфигурируеми систолични матрици с разумна цена.