Тема 11 — Паралелни компютри с потоково управление

1. Въведение

Класическите компютри на фон Нойман изпълняват командите строго последователно, управлявани от брояч на командите. Паралелните компютри с потоково управление следват коренно различен принцип: всяка команда е готова за изпълнение в момента, когато всичките й операнди са налични — независимо от позицията й в програмата. По такъв начин максималният паралелизъм, заложен в програмата, се открива и използва автоматично.

Разграничават се два основни класа потокови компютри:

Управление по данни (dataflow) — всяка команда пасивно чака своите операнди. Изпълнението й се “задейства” при постъпването на всички входни данни. Програмата се представя като граф, чиито върхове са командите, а дъгите — потоците данни между тях (маркери).
Управление по заявки (demand-driven / reduction) — команда се активира само когато е необходим резултатът й. При липса на операнд тя изпраща заявка към командата, произвеждаща го. Изпълнението е серия от замествания на подизрази с техните стойности — т.нар. редукция на изрази. Програмата е структура от вложени математически изрази.

1.1. Пример за потокова организация

Нека изчислим y1 = x2(x1 + x2) и y2 = x1(x1 + x2) при x1 = 3, x2 = 2. Програмата се описва чрез три команди:

Pa: V3 = x1 + x2
Pb: y2 = x2 * V3
Pc: y1 = x1 * V3

При класическата организация командите се изпълняват последователно: Pa, после Pb, после Pc.

При потоковата организация Pa се изпълнява веднага щом x1 и x2 са налични. Резултатът V3 се изпраща едновременно до Pb и Pc — те получават всичките си операнди едновременно и се изпълняват паралелно.

Потоковата организация предоставя качествено нови свойства на изчислителната система:

Паралелизъм — автоматично се открива и използва максималният паралелизъм в задачата.
Модулно нарастване — при N разрешени команди те могат да се изпълняват от 1 до N процесорни елементи, без промяна на програмата. Броят на обработващите елементи може да се изменя динамично.
Асинхронни изчисления — разрешените команди се изпълняват независимо и асинхронно, без странични ефекти.
Самоидентификация на информацията — всеки обект носи идентификатор за вида, свойствата и състоянието си; дешифрирането се извършва апаратно.
Разпределена обработка — множеството операционни елементи работят паралелно и асинхронно.

2. Особености на компютрите с потоково управление

2.1. Управление и спускови функции

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

По начина на реализация потоковите компютри се делят на:

С централизирано управление — едно управляващо устройство проверява готовността на командите, избира разрешените и ги предава за обработка.
С разпределено управление — всяка команда “самостоятелно” установява готовността си; проверката се извършва в множество независими устройства.

По нивото на реализация на спусковите функции:

Микрониво — отделна спускова функция за всяка команда; реализира паралелизъм на ниво команди.
Макрониво — спускова функция за части от програмата (процедури, подпрограми); реализира паралелизъм на ниво програмни единици.

2.2. Статичен и динамичен модел

Статичен модел — работи само с едно копие на всяка команда; повторно изпълнение не е възможно, докато предходното не е завършило. Паралелизмът е ограничен до зададения в машинната програма.

Динамичен модел — допуска едновременно повече от едно изпълнение на дадена команда чрез създаване на нейни копия (тагове/маркери). Паралелизмът се открива динамично в хода на изчисленията, без предварително записване в програмата — постига се по-висока паралелност.

2.3. Формат на командите

Командната клетка в потоковия компютър съдържа не само код на операцията и адреси, но и самите стойности на данните:

Поле	Значение
OP	Код на операцията
SA	Адрес на резултата (кой обработващ елемент го получава)
D1, D2	Стойности на двата операнда
DV1, DV2	Флагове за наличност на операндите

Командата е готова за изпълнение, когато и двата флага DV1 и DV2 са в състояние “готовност”. Резултатът от операцията OP(D1, D2) се изпраща в командната клетка, посочена в SA.

2.4. Запомнящата среда

Освен стандартните функции по съхранение, запомнящата среда при потоковите компютри изпълнява и активна роля:

Участва в реализацията на спусковите функции (проверка за наличност на операнди чрез флагове).
Подготвя изпълнението на командите (комплектоване на OP, операнди и SA).

Изискванията за памет са по-значителни отколкото при класическите компютри: необходими са място за идентификатори, копия на командите (при динамичен модел), копия на входните данни и буфери за междинни резултати.

2.5. Комуникация и езици за програмиране

Асинхронното действие на обработващите елементи изисква развити комуникационни ресурси. Два метода:

Предаване на съобщения — блокове с различна дължина, носещи адреса на приемника.
Предаване на пакети — съобщения с фиксирана дължина. Типовете пакети са: командни (ОП + операнди), операндни (стойности), резултатни (изход от команда) и служебни (маркери).

Потоковите езици имат стойностен характер — данните се поглъщат и изработват еднократно. Прилагат правилото за “еднократно присвояване”, което елиминира страничните ефекти. Примери: LAU (Тулуза, Франция), VAL (MIT, за статичен тип), Id (Университета в Ървин, за динамичен тип).

3. Структура на потоковия компютър

Три подхода за организация на структурата:

Пряко взаимно свързване на обработващите елементи — програмата се задава чрез физическата комутация между обработващите елементи (аналог на аналоговите машини). Максимална скорост, но липса на гъвкавост.
Матричен превключвател — конфигурацията на връзките се управлява от програма. Универсален, но при нарастване на броя операции сложността на връзките бързо расте.
Комуникационна мрежа (логически пат) — единственият практически приложим подход за мащабируеми системи.

Без входно-изходните устройства, основните структури са четири: с обща шина, разпределена, кръгова и йерархична.

Кръговата структура работи като цикличен конвейер от изчислителни, комуникационни и запомнящи устройства, свързани с множество паралелни еднопосочни канали. Изчислителните устройства се изграждат от независими обработващи елементи, работещи паралелно; запомнящите са специализирани (за команди, за операнди) или с паралелен достъп.

4. Проблеми на компютрите с потоково управление

4.1. Обръщения към паметта

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

4.2. Обработка на регулярни структури

При обработката на масиви потоковият компютър разглежда масива като набор от независими елементи. Обръщенията към паметта добиват рандомизиран характер и техниката на разслояване (вижте тема 13) не може да се използва. Освен това обработката на индекси генерира допълнителни непродуктивни разходи. Препоръчително е включването на функционален блок от по-високо ниво, ориентиран специфично към регулярни структури.

4.3. Система от прекъсвания

Класическият апарат за прекъсвания отсъства в потоковите компютри. Изключителните ситуации се обработват чрез специални стойности-грешки в наборите данни. При препълване вместо числов резултат се генерира “стойност-грешка-препълване”, която се предава по потока до следващия оператор — той инициира подходяща реакция.

Резюме

Потоковите компютри изпълняват команди по готовност на операндите (dataflow) или по заявка (demand-driven), а не по ред на следване — реализира се максималният заложен в програмата паралелизъм.
Статичният модел ограничава до едно изпълнение на команда; динамичният модел позволява множество едновременни копия, постигайки по-висок паралелизъм.
Командният формат съдържа самите стойности на данните и флагове за наличност — команда се изпълнява, когато и двата флага са “готовност”.
Запомнящата среда изпълнява активна роля: участва в спусковите функции и комплектоването на командите.
Проблемите включват висока нужда от пропускателна способност на паметта, неефективна работа с регулярни масиви и липса на класически апарат за прекъсвания.
Практически единствената мащабируема структура е чрез комуникационна мрежа, реализираща логически пътища между обработващите елементи.