Тема 8 — Матрични процесори (SIMD процесори)

1. Въведение

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

Матричният процесор е синхронен паралелен компютър, съставен от множество процесори, управлявани от едно единствено управляващо устройство. Управляващото устройство извлича и декодира командите, след което размножава управляващите сигнали към всички процесори в матрицата — всички те изпълняват едновременно една и съща операция, но върху различни данни. По класификацията на Флин (вижте тема 3) този клас спада към SIMD (Single Instruction stream, Multiple Data streams).

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

Матричните процесори могат да се разглеждат като фон Ноймановски по отношение на управляващото устройство: то управлява процесорната матрица по същия начин, по който управлява единичен процесор. Именно това опростява програмирането в сравнение с другите многопроцесорни конфигурации.

2. Структура на SIMD компютрите

2.1. Двата модела на миграция от последователен към паралелен процесор

Два основни начина на свързване на процесорните елементи определят и двете организации на матричните процесори.

Модел с N:N комутатор. Обменът на данни между процесорите се реализира на ниво процесори и по битове чрез комутатор от тип N:N. Пример: Connection Machine с хиперкубична топология на връзките (вижте тема 12) и MPP.

Модел с 1:N комутатор. Данните се прехвърлят между процесорите или между процесорите и паметта на блокове, чрез комутатор от тип 1:N. Примери: STARAN, ASPRO.

2.2. SIMD компютър с локална памет

Всеки процесорен елемент PE[i] разполага с собствена памет M[i]. Управляващото устройство извлича командите от собствената си памет (CU Memory) и ги изпраща до всички PE. При векторни операции управляващото устройство предава адресите, a всеки PE извлича данните от локалната си памет. Чрез индексен регистър адресирането може да стане по-гъвкаво.

Комуникацията между процесорите се реализира чрез комуникационна мрежа (Interconnection Network). Типичен представител е ILLIAC IV на Илинойски университет — четири квадранта по 64 процесора (8×8), свързани по специфична ILLIAC IV схема. Друг представител е Connection Machine (CM) — 65 536 еднобитови процесора, групирани по 16 в 4 096 възела, свързани в хиперкуб.

2.3. SIMD компютър с разделяема памет

Паметите са отделени от процесорните елементи чрез мрежа за подравняване (Alignment Network). Всеки PE може да осъществява достъп до всяка памет, а мрежата позволява паралелен достъп. Предимство: по-лесна настройка на вече познати алгоритми. Недостатък: по-голям обем на превключваните данни увеличава времето за достъп.

И в двата модела е налице последователна (host) машина, изпълняваща компилацията, зареждането на програмата, входно-изходните операции и функциите на операционната система.

3. Особености на SIMD компютрите

3.1. Набор команди и механизъм на маска

Командите на матричния процесор се разделят на три подмножества:

Скаларно подмножество — обикновени последователни команди, изпълнявани от управляващото устройство.
Паралелно подмножество — команди без преходи, изпраща се до всички PE и се изпълнява паралелно.
Управляващо подмножество — команди за обмен на данни между скаларната и паралелната части.

За ситуациите, при които не всички PE трябва да изпълняват дадена команда (напр. клауза if a[i] > 0 then ...), е въведен механизмът на маска. В най-проста форма той се реализира чрез контекстен регистър: стойност 1 разрешава изпълнението, стойност 0 — блокира го. В развития си вариант е специализиран процесор, извършващ булеви операции и подаващ резултата на входовете за блокиране/деблокиране на PE. Механизмът е въведен за пръв път в ILLIAC-IV.

3.2. Синхронни операции и масов паралелизъм

Единственото управляващо устройство определя синхронния режим на работа. Двете исторически причини за развитието на SIMD компютрите са:

По-ниска цена: N процесора + 1 управляващо устройство срещу N процесора + N управляващи устройства.
Пълно използване на лентата на пропускане на комуникационната мрежа при синхронни операции.

Под масов паралелизъм се разбира броят на едновременно работещите процесори. В началото на 70-те години максимумът е 512–1024 процесора; 25 години по-късно той достига 256K.

Много SIMD компютри (DAP на ICL, серията Connection Machine) използват еднобитови процесори, тъй като:

Позволяват разполагане на значително повече PE в един чип с по-проста структура.
При определено съотношение между скоростта на аритметиката и времето за достъп до паметта (τ_A ≈ τ_M, характерно за съвременните технологии), разряднo-секционната обработка постига до ~9× по-висока производителност при b=32-битови думи.

3.3. Ъглово завъртане (Corner Turning)

Стандартните компютри организират данните като последователни по думи, паралелни по разряди, докато еднобитовите PE изискват формат последователен по разряди, паралелен по думи. Преобразуването между двата формата се нарича ъглово завъртане и се реализира от специално устройство между паметта и процесорната матрица. В компютрите Staran и Aspro то се извършва ефективно от самата комуникационна мрежа при обикновено обръщение към паметта, без допълнително закъснение.

3.4. Пример: пирамидална архитектура за обработка на изображения

Концепцията за пирамидална архитектура е предложена от L. Uhr. На най-ниско ниво компютърът представлява двумерна матрица от PE за груба обработка на пикселите. По-горните нива обработват все по-абстрактни представяния, а колкото по-високо — толкова по-малко синхронизирани са операциите. Проектът IUA (Image Understanding Array) на MIT включва:

Ниво 1: CAAPP — матрица 512×512 еднобитови процесора (обработка на ниво пиксели).
Ниво 2: ICAP — матрица 64×64, 16-битови процесора, MIMD управление.
Ниво 3: SPA — 64 по 32-битови процесора, LISP машина.

Резюме

SIMD компютърът управлява множество процесори с единствено устройство за управление, осигурявайки синхронно изпълнение на еднакви операции върху различни данни.
Двете основни организации са с локална памет (всеки PE има собствена памет) и с разделяема памет (PE достъпват обща памет чрез мрежа за подравняване).
Механизмът на маска осигурява условно изпълнение на команди от избрани PE чрез контекстен регистър или булев процесор.
Еднобитовите процесори позволяват масов паралелизъм с прости структури; разряднo-секционната организация постига до 9× ускорение при съвременни технологии (τ_A ≈ τ_M).
Ъгловото завъртане е задължително преобразуване на формата на данните при работа с еднобитови PE.
Пирамидалните архитектури съчетават SIMD на ниски нива с MIMD на по-горните, за задачи като разпознаване на изображения.