khor32

5.2. Вычислительная система ILLIAC IV

B качестве примера рассмотрим умножение матриц A и X большого размера. Элементы гтк, 4 k =1, п, матрицы Z = A • X определяются выра-

жением

	п
	rIk = ^ ауxjk,
	j=1
где ау , xjk	элементы строки i матрицы А и столбца k матрицы X соответ-

ственно. Ясно, что это требует вычисления функций

п

fk(y, х) = yjxjk, k = 1,п,

j=1

в которых аргумент (у1, У2 ..., уп) последовательно заменяется на

(а11 , а2, ..., а' ) при i = 1, 2, ..., п.

Практически установлено, что ILLIAC IV была эффективна при решении широкого спектра сложных задач. Назовем классы задач, которые

допускают построение параллельных алгоритмов c высокой степенью использования ЭП: матричная арифметика, системы линейных алгебраиче-

ских уравнении, линейное программирование, исчисление конечных раз-

.,

ностеи в одномерных, двyмерных и трехмерных случаях, квадратуры (включая быстрое преобразование Фурье), обработка сигналов. Отметим классы задач, обеспечивающих неполное использование ЭП: движение частиц (метод Монте-Карло и т. д.), несимметричные задачи на собственные значения, нелинейные уравнения, отыскание корней полиномов (в не-

которых случаях эти задачи попадают в первую группу). Эффективность

системы ILLIAC IV, например, характеризует время решения типичной

задачи линейного программирования, имеющей 4000 ограничений и 10 000 переменных . Это время для ILLIAC IV составляло менее 2 мин, a для большой ЭВМ третьего поколения б.. .8 ч. Названные задачи говорят o большой сфере применения матричных ВС (наука, экономика, проектирование, атомная энергетика, предсказание погоды, радиолокация, оборона, космические исследования и т. д.).

Технические и программные средства ILLIAC IV многократно подвергaлись модификациям, что улучшало технико-экономические показ атели, увеличивало вычислительную мощность системы, расширяло сферу применения системы ILLIAC IV.

203

5. Матричные вычислительны системы

5.3. Вычислительная система DAP

Разработку матричной ВС DAP (Distribut ед Аггау Processor распре-

деленный матричный процессор) осуществл: ела английская фирма ICL

(International Computers Ltd.). Работы были начаты в 1972 г., опытные образ-

цы системы DAP (на дискретных элементах) i iз 1024 и 4096 элементарных

процессоров были построены в 1976 г. и 1977 г. Планировалось к 1980 г. организовать серийное производство ВС DAP н^L основе больших интегральных схем, однако из-за финансовых тpудностей работы были прекращены.

Система DAP по своей архитектуре относилась к SIMD-типу, это была

ВС c массовым параллелизмом. Планировалось, что ВС будет состоять из 50 000 параллельно работающих ЭП, управляемых одним потоком команд.

Каждый ЭП будет представлять собой монолит 7ную большую интегральную схему, подсистема ввода-вывода информации будет выполнена также на

БИС. Предполагалось аппаратно реализовать многие функции программного обеспечения.

Функциональная структура ВС DAP [13] это композиция ведущей

ВС и собственно DAP (рис. 5.4). Ведущая ВС Host Computer) предназнача-

лась для реализации функций операционной с истемы (включая подготовку

данных и команд для DAP, распределение дам оных по ЭП). B опытных образцах ВС DAP в качестве ведущей была использована серийная ВС Control

Ведущая ВС

E

Устpойство

управления

От памяти данного ЭП От соседнего ЭП сверху От соседнего ЭП снизу От соседнего ЭП слева От соседнего ЭП справа

Мультиrv гексор

^	AnyТ	ЭП

Чг

г

Мультип iексор

т ^

Матрица ЭП

Система DAP

^

K соседнему ЭП справа

Ксоседнему ЭП слева

Ксоседнему ЭП снизу

Ксоседнему ЭП сверху

Кпамяти данного ЭП

Рис. 5.4. Функциональная структура ВС DAP:

ЭП — элементарный процессор; АЛУ — арифмeтико-лог ическое устройство

204

5.3. Вычислительная система DAP

Data Corporation: конвейерная система CDC 7600 (восемь конвейеров, дли-

тельность такта 27,5 нс, быстродействие 10...15 млн опер./c). Собствен-

но матричная система DAP применялась для массовых параллельных вы-

числении.

Устройство управления формировало поток команд на матpицy ЭП, в

частности оно направляло команды, адреса и другую информацию, необходимую элементарным процессорам для выполнения «матpичных» операции.

Архитектуры систем ILLIAC IV и DAP на макроуровне близки, однако DAP имела свои особенности. Каждый элементарный процессор DAP

представлял собой одноразрядный микропроцессор, связанный c локальной памятью емкостью в 4096 бит. Матрица ЭП и их память для удобства представлялись в виде «прямоугольного вычислительного параллелепипеда» из 4097 горизонтальных слоев. Верхний слой параллелепипеда это матрица ЭП, в которой строка имела длину Ld элементов (д длина слова ведущей ВС, L число слов ведущей ВС в строке), a столбец состоял из 2" элементов (т некоторое выбранное целое положительное число). Таким обра-

зом, матрица ЭП имела размеры Ld • 2 т , следовательно, она была способна

параллельно обрабатывать L • 2т d-рaзрядных слов. Под каждым ЭП в параллелепипеде располагалась его локальная память вертикальная колонка из 4096 разрядов. Локальная память всех ЭП составляла распределенную память системы DAP в целом. Каждый слой разрядов этой распределенной

памяти был пронумерован от 0 до 4095 и был рассчитан на L • 2 т д-раз- рядных слов. Функции по распределению информации из ведущей ВС (по

вложению слов ведущей ВС в 4096-разрядную память ЭП и наоборот) вы-

полнялись устройством управления DAP.

Между ЭП существовала сеть связей. Она обеспечивала через мультиплексоры связь каждого ЭП c регистрами АЛУ четырех ближайших соседей, расположенных сверху, снизу, слева и справа от него. Следовательно,

сеть связей обеспечивала архитектypнyю гибкость ВС DAP. Она, в частно-

сти, превращала распределенную память в общедоступную для каждого ЭП, позволяла работать c произвольными L-элeмeнтными векторами и матрица-

ми размером L • 2m элементов, допускала варьирование разрядности d элементов.

Каждый ЭП имел в своем составе предельно простое одноразрядное АЛУ, которое обеспечивало последовательную поразрядную обработку информации (элементов векторов и матриц). Предусматривалась реализация арифметических и логических операций, при этом результат операции мог быть отослан из соответствующего регистра АЛУ в память данного ЭП или

B регистр одного ИЗ четырех соседних ЭП (через «нижний» мyльтиплексор,

см. рис 5.4).

205

5. Матричные вычислительные системы

B каждом ЭП был заложен механизм, позволявший программировать состояние процессора. Этот механизм был предельно прост и представлял собой одноразрядный регистр активности, одно из состояний которого (пассивное состояние) запрещало ЭП выполнять поступавшую команду. Следовательно, регистры активности использовались для маскиf ^ования частей матриц ЭП или отдельны ЭП в зависимости от условий выполнния вычислений.

Команды для матрицы ЭП DAP поступа. iи из устройства управления.

Они содержали всю информацию, которая требовалась для выполнения операции (адреса для операндов и результата и др.).

Найдем «оценку сверху» быстродействи я ВС DAP. При выполнении арифметических операций разряды операндов должны были обрабатываться отдельно. Поэтому, например, для выполнения сложения d-рaзрядных чисел c фиксированной запятой требовалось d раз пс вторить цикл из трех команд

DAP. Время цикла работы DAP составляло 200 нс. Следовательно, на вы-

полнение указанной операции на одном ЭП з.^трачивается 3d • 200 ис; при d = 20 эта величина равна 12 мкс. Ясно, что матрица из N ЭП была способна выполнить в 1 c до N / 3d • 200 таких операций сложения над d-разрядны- ми операндами; при d = 20 максимальное быстродействие матрицы из 4096 ЭП составляло около 340 млн опер./c.

Следует подчеркнуть, что в ВС DAP (в отличие от ILLIAC IV) в каж-

дом ЭП использовалось не параллельное, a очень простое и дешевое одноразрядное АЛц. Следовательно, любые опер ации над многоразрядными операндами должны были выполняться в ЭП при помощи программ. (Это

имело место и при организации DAP в виде r прямоугольного вычислитель-

ного параллелепипеда, который был описан вьЕше.) Последовательные ЭП в отдельности имели низкое быстpодействие, однако матрица из большого числа параллельно работавших ЭП c программно управляемыми связями между ними обеспечивала высокую производя тельность. Такой подход был очень гибким и c точки зрения вычислительных технологий, в частности, он позволял пользователю выбирать точность вычислений. При этом подход

обеспечил: во-первых, экономное расходовани памяти (операнды занимали только столько разрядов, сколько их требовал ось для достижения заданной

точности представления чисел); во-вторых, м: 4нимум времени выполнения любой арифметической операции (так как соответствующая ей последовательность команд выполнялась только над таким количеством разрядов операндов, которое соответствовало требуемой точности).

Архитектурной особенностью ВС DAP . являлось и то, что ее распре-

деленная память могла быть использована вед. щей ВС CDC 7600 как обычнaя память.

B 1976 г. создан опытный образец DAP, который имел матрицу из 32 x 32 ЭП, каждый из которых был оснащен локальной памятью 1 K бит.

206

5.4. Семейство вычислительных систем Connection Machine

Позднее эта конфигурация была расширена до 64 x 64 ЭП c емкостью ло-

кальной памяти каждого в размере 4 K бит. Последняя конфигурация ВС DAP превосходила по производительности в 5-10 раз старшие модели ЭВМ третьего поколения (ЭВМ 1ВМ 360/195 обладала быстpодействием

(7...10) • 106 опер./c и емкостью оперативной памяти 1024.. .4096 K байт).

Интегральные (на основе БИС) реализации ВС DAP не были созданы из-за

финансовых трудностей.

Вычислительная система DAP была ориентирована на решение задач,

связанных c предсказанием погоды. Планировалось установить системы в

двух организациях: Еигореап Centre for Medium Term Weather Forecasting; Meteorological Office in Bracknell. Очевидно, что данная ВС могла найти ряд

других областей применения.

5.4. Семейство вычислительных систем Connection Machine

Эволюция архитектуры матричных ВС и достижения в технологии БИС привели к созданию ВС c массовым параллелизмом, архитектура которых не может быть вписана в какой-либо один из канонов. Архитектура данных систем в зависимости от «глубины» просмотра может быть отнесена к классам MIMD и SIMD одновременно. Например, система в целом может

иметь архитектуру MIMD, a ее основные пpоцессорные компоненты

SIMD; сети связей между элементами обработки информации на различных иерархических уровнях могут быть также различными. К таким ВС относят-

ся модели семейства Connection Machine: СМ-1, СМ-2 и СМ-5 .

замысел создания ВС Connection Machine * возник еще в конце 1970-x го-

дов в Лаборатории искусственного интеллекта Массачусетсского техноло

гического института США (Massachusetts Institute of Technology's Artificial Intelligence Laboratory, MIT А' Laboratory) и принадлежит Y.Д. Хиллису (W.D. Hillis). B начале 1980-x годов были разработаны архитектура и схемы

для создания прототипа этой системы.

Актуальность построения системы привела к основанию в 1983 г.

Thinking Machines Corp. (США). Эта корпорация выполнила разработку всех моделей семейства Connection Machine: СМ-1 (1986), СМ-2 (1987), СМ-5

(1991).

Отметим архитектурные особенности систем семейства СМ:

• превалирующий класс архитектуры SIMD (MIMD, любой из моде-

лей в целом);

*Hillis W.D. The connection machine 1/ Scient. American, 1987. V. 156. N 6. P. 108-115.

207

5.Матричные вычислительные системы

•массовый параллелизм (МРР Massively Parallel Processing);

•максимальное число ЭП —65536 (или 2 1 '');

•быстродействие до 1 TFLOPS;

•однородность и программируемость структуры сети межпроцессор-

ных связен;

• масштабируемость ВС (возможность соз дания конфигураций в СМ-1

из 16 K, 32 K, 48 K и 64 K элементарных процессоров, в СМ-2 из 32, 64,

128, ..., 32 K, б4 K процессоров, a в СМ-5	из произвольного числа ЭП, не
превышающего 16 K).

Thinking Machines Corp. была одной из лидирующих компаний ХХ в.

по разработке МРР-суперкомпьютеров. Начиная c 1996 г. она сконцентрировaла свои усилия только на разработке ПО ,ля ВС c массовым параллелизмом (конструируемых другими компаниями). Выпуск моделей семейства

Connection Machine прекращен. Однако архит ^ктурные решения, заложен-

ные в это семейство, представляют и сейчас б эльшой интерес для создателе? высокопроизводительных средств ВТ. Эти решения могут составить основу при конструировании СБИС, содержащих коллективы связных элементарных процессоров.

5.4.1. Вычислительная система СМ-1

Вычислительная система СМ-1

перв^ ?я модель семейства Connec-

tion Machine была спроектирована в Thinki ng Machines Corp. в течение

1983 г. и первой половины 1984 г. Прототип м юдели СМ-1 из 16 K процессоров был построен к концу 1984 г. при финансовой поддержке Агентства по перспективному планированию исследований в области обороны США

(Defense Advanced Research Projects Agency). Демонстрация возможностей

прототипа СМ-1 была осуществлена в мае 198`? г. Полная 65 536-процессор-

ная конфигурация СМ-1 была собрана и успешно продемонстрирована в ноябре 1985 г.

Максимальная конфигурация модели СМ- l (из 64 K процессоров) имела

быстродействие 2000 MIPS (2 109 опер./c над 32-разрядными целыми чис-

лами) и обладала распределенной оперативной памятью емкостью 32 Мбайт. Эти данные говорят o простоте проекти^ ования и изготовления высо-

копроизводительных МРР-систем.

Функциональная структура системы (;М-1. Модель СМ-1 семейст-

ва Connection Machine имеет достаточно развi:тую функциональную струк-

туру, характеризуется иерархией средств управления процессами обработки

информации (рис. 5.5). B состав ВС СМ-1 входят: параллельное процессор-

ное устройство (Parallel Processor Unit); че гыре сервисных процессора (СПо–СПЗ, Front-ends) c интерфейсом шин (ИцI); коммутатор (Nexus).

208

5.4. Семейство вычислительных систем Connection Machine

Коммутатор	спо
o 0 0 0
	--♦

			urn
	Параллельное
	процессорное		СП 1
	устройство
				--.
	Подсистема	Подсистема	urn
	СМо	СМЗ
			СП2
			urn
		2	СП З
	Подсистема	Подсистема		г.
	СМ 1	СМ2	urn

Сеть

Рис. 5.5. Функциональная структура ВС СМ - 1:

СП — сервисный процессор; ИШ — интерфейс шин; УУ — устройство управления

Основу любой конфигурации СМ-1 в целом составляет параллельное

процессорное устройство c архитектурой MIMD, которое может иметь в

своем составе от одной до четырех подсистем: СМo- СМЗ . Архитектура подсистем СМo-СМЗ относится к классу SIMD. Следовательно, в пределах каждои из подсистем данные распределяются по процессорам и одна и та же программа управляет работой множества процессоров (но каждого над своим подмножеством данных). Любая из подсистем СМo-СМЗ является композицией из устройства управления (УУ) и 16 384 ЭП. Таким образом, мак-

симальная конфигурация модели СМ-1 имеет 65 536 ЭП.

Устройство управления (Sequencer) ВС СМ-1 специально спроекти-

рованньпй микрокомпьютер для реализац ш функций виртуальной маца i (ар-

хитектура которой существенно удобнее для пользоватeля, чем y реальной фи-

зической ВС). Это устройство содержит память нанокоманд емкостью 16 K

96-paзpядны слов. На входы четырех устройств управления поступает поток

информации «высокого уровня», a именно операций виртуальной машины и

аргументов. Этот поток поступает из коммутатора по синхронному параллель- ному (32-разрядному) каналу данных. На выходе УУ имеет место поток нанокоманд, которые и управляют работой элементарных процессоров и памяти.

209

5. Матричные вычислительны системы

Все элементарные процессоры ВС СМ сгруппированы в вычислительные узлы (или вершины) по 16 ЭП. Каждый узел конструктивно оформлен как объединение процессорного кристалла и кристалла памяти. Такой узел в целом называют просто процессорным кристаллом. В каждой из подсистем СМо—СМЗ имеется 1024 узла: Взаимодействие между узлами осуществляется через сеть связей, структура которой предст авляет собой 10-мерный гиперкуб.

Сервисные процессоры (Front-ends), по сyти, составляют аппаратурно-

программную среду для разработки системногэ ПО. Они выполняют также

функции ведущих (Host) процессоров и обеспс чивают взаимодействие c се-

тью ЭВМ (Network). В качестве такого процессора могут быть использованы

серийно производимые средства (например, система DEC VAX). Интррфейс шин (Bus Interfase) поддерживает 32-разрядный параллельный асинхронный

канал между сервисными процессорами и комN утатором.

Коммутатор (Nexus) предназначается для организации взаимодействии между сервисными процессорами и устрой гствами управления, он имеет

размер 4 х 4 (4 х 4 Cross-point Switch). Ком]иiутатор реализует механизм

разделения, который позволяет в пределах ВС СМ-1 конфигурировать до четырех подсистем, работающих под управлением своего сервисного процессора. Это дает возможность применять различные подсистемы для решения задач разных пользователей или, например, выделять одну из них для диагностирования и восстановления работоспособности, a остальные использовать для решения задач. В случае, если к одному сервисному процессору подсоединяется более одного устройства управления, осуществляется их синхронизация (при помощи генератора синхроимпульсов коммутатора).

Элементарные процессоры и вычислительные узлы ВС СМ-1. Элементарный процессор основной функциональный элемент системы СМ-1 (см. рис. 5.5). Он имеет архитектуру SISD и является однорaзрядным последовательным средством обработки инфо )нации. В состав каждого ЭП (рис. 5.6) входят:

•одноразрядное АЛУ;

•битно-адресуемая локальная память (ЛП) емкостью 4 K бит;

•восемь одноразрядных регистров признаков (РП) или флагов;

•интерфейс маршрутизатора (ИМ);

•двумерный интерфейс сети межпроцесссрных связей (ИСМС).

Элементарный процессор ВС СМ-1 не является конструктивно

оформленным элементом. В качестве конструктивной (да и функциональ-

ной) единицы выступает вершина или вычислительный узел (см. рис. 5.6). При реализации узла используются два типа кристаллов. Первый это

210

5.4: Семейство вычислительных систем Connection Machine

б

Рис. 5.б. Функциональные структуры ЭП и узла ВС СМ-1:

a — ВУ; б — ЭП; ИСМС — интерфейс сети межпроцессорньпс связей; ЛП — локальная память; АЛУ — арифмeтико-логическое устройство; РП — регистр признаков; ИМ — интерфейс маршрутизатора; ЭП — элементарный процессор

оригинальный, специально спроектированный (заказной) кристалл (Ргоргге- tary Custom Chip). Этот кристалл называют процессорным, он содержит

АЛУ, регистры признаков и коммуникационный интерфейс для 16 ЭП (маршрутизатор и средства межпроцессорной сети связей). Второй кристалл коммерческая статическая память c произвольным доступом и c защитой по четности. Таким образом, в полной конфигурации ВС СМ-1 (из 64 К ЭП) содержится 4096 процессорных кристаллов (узлов) и имеется память c произвольной выборкой емкостью 65 536 v бит (v емкость локальной памяти одного ЭП).

Арифметико-логическое устройство ЭП имеет три входа и два выхода и включает в себя логические элементы, однорaзрядные регистры-защелки

(Latches) и интерфейс памяти (см. рис. 5.6). Опишем цикл функционирования

АЛУ. Вначале осуществляется чтение двух одноразрядньх операндов из памяти и одного бита данных из регистра признака. Затем логические элементы выполняют операцию над этими тремя входными битами и выдают два одно-

разрядных результата. Наконец, один из двух результатов запоминается в па-

мяти, a другой в регистре признака. Логические элементы АЛУ способны

211

5. Матричные вычислительныЕ системы

вычислять значения любых булевых функций о г трех переменных. Арифме-

тические операции выполняются последователь о, побитно.

Элементарный процессор системы СМ-1 относится к классу RISC

(RISC Reduced Instruction Set Computer компьютер c упрощенным набо-

ром команд). Длительность цикла ЭП (АЛУ) с зставляет 0,75 мкс. Цикл ЭП подразделяется на подциклы. В каждом подцпкле ЭП выполняет команду

низкого уровня, называемую нанокомандой (Nanoinstruction). Нанокоманды

поступают в ЭП из устройства управления. Одг^овременно c реализацией нанокоманды в памяти ЭП может выполняться одна из операций: чтение или запись. Выполнение целочисленной операции с пожения двух операндов тре-

бует трех подциклов, соответствующих следуюiцим нанокомандам: LoadA чтение из памяти операнда A, LoadB чтение и' z памяти операнда В и Store

выполнение операции и запоминание результат а. Ясно, что время сложения

L-paзpядныx операндов в ЭП потребует 3Li еиниц времени (i длитель-

ность подцикла, i = 0,375 мкс). Тогда быстродсйствие ВС СМ-1 из б4 K ЭП составит 65 536/ 3Li целочисленных операций Р единицу времени. Например, при сложении 32-разрядных чисел быстродейс гвие СМ-1 оценивается величиной 1,82 109 опер./c.

Имеются также нанокоманды управлен: ля маршрутизатором и меж-

процессорной сетью связей (NEWS Grid), a также нанокоманды, реализую-

щие функции диагностики (в модели СМ-1 г [спользуется двумерная сеть,

это и предопределило аббревиатуру NEWS: North East West South).

Каждый ЭП может находиться либо в аь тивном состоянии (и воспринимать нанокоманды), либо быть замаскироваг:ным.

Гиперкубическая межузловая сеть СЛ7 -1. В составе любой из подсистем СМо —СМЗ содержится 16 K ЭП, сгруппированных в 1024 ВУ. Взаимодействие между ВУ осуществляется через с еть связей, которая представ-

ляется в виде гиперкуба (Hypercube Data Network). Что собой представляет

такой куб?

Понятие o гиперкубе дано в разд. 3.1.2 , a на рис. 3.2 представлены гиперкубы размерностей 1, 2, 3, 4. Стандартное представление гиперкуба размерности 4, или 4D-куба это конструкция «куб в кубе», в которой каждая вершина одного куба соединена ребром c симметричной вершиной другого куба (см. рис. 3.2). Очевидно, ч'го такую конструкцию четырехмерного гиперкуба легко трансформировать к видам, представленным на рис. 5.7.

В представлении 4D-куба в виде одномерного куба (см. рис. 5.7) считает-

ся, что вершины трехмерные кубы, a гиперре бро совокупность из восьми ребер, каждое из которых соединяет соответствующие вершины 3D-кyбoв.

212