khor32

3.1. Модель коллектива вычислителей

	Общая шина	Top
		т
	Вычислители
	a
г	1
	1
1	...
	^ ^

б в Рис. 3.1. Фрагменты простейших структур ВС: a — нульмерная; б — одномерная; в — д вумерная

структура практически реaлизуема при небольшом числе вычислителей. для достижения производительности ВС в диапазоне 1010 . .. 1015 опер./c при существyющих интегpaльных технологиях необходимо около 10-10 5 вычислителей. Следовательно, структуры таких систем не могут быть организова-

ны по типу полного графа хотя бы из-за ограничений на число выводов c

корпусов интегральных схем. Рассмотрим структуры сети связей между вы-

числителями, которые используются при формировании ВС.

Простейшие структуры ВС. Различают нульмерные, одномерные и двумерные простейшие структуры ВС (рис. 3.1). B первом случае структура

сети межвычислительньiх связен «вырождена», взаимодействие между вы-

числителями ВС осуществляется через общую шину (Common bus, Uni bus). В случае одномерньх структур (« инейки» Linear graph или «кольца»

Ring) обеспечивается связь каждого вычислителя c двумя другими (соседни-

ми) вычислителями (рис. 3.1, a, б). B нульмерньх структурах имеется общий ресурс шина, в одномерньх же структурах этот ресурс трансформируется в распределенный, т. e. в локальные связи между вычислителями. Следователь-

но, архитектурные возможности (в частности, надежность) последних структyp существенно выше, чем y нульмерньх.

Увеличение ра.змерности структуры повышает структурную надежность ВС. B самом деле, двумерные структуры предоставляют каждому вы-

числителю непосредственную связь c четырьмя соседними. В качестве примеров двумерных структур (рис. 3.1, в) может служить «решетка» (точнее,

2D-решетка

Two-dimensional griд) и тор (2D-тор

Two-dimensional

torus). Следовательно, в системах c двумерной структурой при отказах некоторых вычислителей и (или) связей между ними сохраняется возможность организации связных подмножеств исправных вычислителей.

113

З. Архитектура вычислительных систем

0 1

O—^

a

100 101

	001
	111
010	011
	в

г

Рис. 3.2. Гиперкубические структуры ВС :

a — 1 D-кyб (N = 2, п = 1); б — 2D-куб (N = 4, п = 2); в -- ЗD-кyб (N = 8, п = 3); г — 4D-куб

(N = 16, п = 4)

B n-мepныx структурах каждый вычисл итель связан c 2n соседними

вычислителями. Существуют технико-экономические и технологические ограничения в наращивании размерности структуры ВС.

Гиперкубические структуры ВС. Гиперкубы, или структуры в виде булевых n-мepныx кубов, нашли широкое применение при построении со-

временных высокопроизводительных ВС c массовым параллелизмом. Ги-

перкуб (Hypercube) по определению это од Кородный граф, для которого

справедливо

		п = log2 N,
где N	количество вершин; п	число ребер, выходящих из каждой вер-
шины; n	называют также размерностью гип еркуба. Каждый вычислитель

в гиперкубической ВС имеет связь ровно c n другими вычислителями. На рис. 3.2 представлены гиперкубические структуры ВС. Гиперкуб размер-

ности n называют также пД-кубом (D означает размерность (Dimension)).

Если вершины гиперкуба пронумеровать от О до (N —1) в двоичной

системе счисления так, что каждый разряд соответствует одному из n направлений, то получим булев n-мepный куб (ст. рис. 3.2).

114

3.1. Модель коллектива вычислителей

Вид структуры ВС c массовым параллелизмом существенно влияет на производительность системы в целом. B самом деле, даже при одном и том

же количестве вершин существует разнообразие структур. Для создателей ВС

интерес представляют структуры, обеспечивающие наименьшие временные

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

нужны структуры c минимальным диаметром. Под диаметром структуры

понимается максимальное расстояние (число ребер) между двумя верши-

нами, определяемое на множестве кратчайших путей. Возможности

распространенных структур ВС отражены в табл. 3.1.

							Таблица 3.1
	Характе-			тип cтpyктypы ВС
	ристика	ПО ш	,Лейка	Кот ьцо	2D-решетка	2Д-тор	Гиперкуб
		граф
	диаметр	1	N —1	[N/2] *	2(' —1)	2 JК / 2	1og 2 N
	Количе-	N(N — 1)/2	N — 1	N	2(N	2N	(N log2 N)/2
	ство

ребер

[N]целая часть числа N.

Из табл. 3.1 следует, что структуры c меньшим диаметром имеют

большее количество ребер; удвоение числа вершин в гиперкубе увеличивает его диаметр только на единицу.

Примечания: 1. Тор (от лат. Тогив выпуклость) геометрическое тело, обрaзуемое вращением круга вокруг непересекающеи его и лежащей в одной c н м плоскости прямой. Приблизительно форму тора имеет баранка и спасательный круг. 2. B теории структур ВС тор это решетка, в которой имеют место отождествления

граничных связей в каждой «строке» и в каждом «столбце» (см. рис. 3.1). Легко пред-

стaвить размещение такой структуры—графа на поверхности геометрического тора.

3. Гиперкуб ((N п=-44), представленный на рис. 3.2, г, является двумерньпи мором.

3.1.3. Алгоритм функционирования вычислительных систем

Алгоритм A работы коллектива S обеспечивает согласованную работу

всех вычислителей с1 Е C и сети связей между ними (структуры G) в про-

цессе решения общей задачи. Данный алгоритм может быть представлен в виде сyперпозиции

(33)

115

З. Архитектура вычислительньйх систем

где D исходный массив данных, подлежащих обработке в процессе решения задачи,

		N-1
	D =uD1,			(3.4)
		1=0
D1	индивидуальный массив данных для вьчислителя			с1 Е C, причем в
общем случае
	NП- 1	D1	^ е;	(3.5)
	i=0
P параллельная программа решения общей задачи,
	N-1		N-1
	P=UP,			(3.6)
	1=о		1=о
P	ветвь i программы P.

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

Ясно, что решение общей задачи осуществляется по некоторому па

рaллельному алгоритму, a именно он являетсА основой параллельной проаммы (3.6). Распределенные по вычислителям данные (3.4) и параллельнаягр программа инициирyют работу алгоритма A (3.3) и определяют функционирование конструкции H коллектива вычислителей до конца решения задачи.

Эквивалентным представлением алгоритма (3.3) работы коллектива вычислителей является композиция

(Ао *Ао )*...*(А1 *А1)*...*(ллг-1 * AN-1)•

Здесь (А * А) осуществляет функционированi:е вычислителя с1 среди других вычислителей множества C; А1 и А' соответственно алгоритм автономной работы с1 и алгоритм реализации взаи] {одействий (в частности, обменов данными) c вычислителями с C \ с1 . I [оследний алгоритм является суперпозициеи

где G описание структуры коллектива C вычислителей; P' программа

для установления связен и выполнения взаимодействии между вычислите-

116

3.1. Модель коллектива вычислителей

лем с и другими вычислителями подмножества C \ c . Программа P' явля ется, как правило, частью ветви Р параллельной программы (3.б).

Многообразие архитектурных реализаций модели коллектива вычислителей (многообразие типов ВС) является следствием разницы в способах

воплощения совокупности алгоритмов {А1'}, i = 0, N –1, задания {Р/} и

выбора структуры G, a также разнообразия в правилах композиции алго-

ритмов.

Аппаратypные средства, c помощью которых реализуется совокупность алгоритмов { А, Al, ..., А, ..., АN_1 и которые вместе c сетью связей

составляют среду для осуществления взаимодействии между вычислителями коллектива, называются коммутатором. От способа реализации коммутатора во многом зависит эффективность ВС параллельного действия. Коммyтатор настолько же необходим при создании ВС, насколько нyжны процессор и оперативная память для построения ЭВМ.

При полном воплощении принципа однородности имеют место отношения эквивалентности: А1 = А, А1 = А, , i ^ j, i; j = 0, N –1, которые, в

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

ленномy коммутатору, состоящему из N локальных идентичных коммутато-

ров (находящихся во взаимно однозначном соответствии c вычислителями), не вызывают никаких сложностей в формировании сети связей между вычислителями.

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

экономическую эффективность коллектива вычислителей как единого аппа-

ратурно-прогpаммного комплекса.

3.1.4. Модель вычислительной системы

Формулы (3.1)–(3.3) позволяют записать для модели коллектива вычислителей или модели BC

s = (c, G, A(P(D))>,

(3.7)

где C — множество вычиcлитeлeй; G — структура сети связей между вычислителями; A — алгоритм работы множества C как коллектива вычиcли

тeлeй (взаимосвязанных через сеть	G) при реализации параллельной пpo-
аммы P обработки данных D.	гр

Модель BC (3.7) является формализованным описанием коллектива вычиcлитeлeй, ориентированного («запрограммированного») на решение

117

3. Архитектура вычислительных систем

сложной задачи и реализующего процесс параллельных вычислений. Здесь уместно отметить опыт по организации параллельных вычислении, которые были осуществлены в 1950-x годах математиком[ A.A. Самарским (1919-2008; академик АН СССР c 1976 г.). Требовалось выполнить сложные расчеты, связанные c созданием ядерного оружия, a в расп ^ряжении были только арифмометpы. Для расчетов был привлечен больц: ой коллектив сотрудниц-вы- числителей, которым были распределены исходные данные. Каждая сотрудница реализовывала свою ветвь вычислений (рассчитывала свои узлы сетки). Обмен данными между сотрудницами (параллельными ветвями вычислений) осуществлялся путем передачи листов бумаги c полученными числами. Такой параллельный процесс вычислений позволил решить задачу в срок!

Модель коллектива вычислителей (3.7) допускает создание средств

обработки информации разнообразных конфигураций. Представление кол-

., лектива вычислителей в качестве макровычнслителя делает возможным

формирование сверхколлективов или систем коллективов, или макровы числительных систем. Модель коллектива вычислителей (3.7) применима и на микроуровне; c ее помощью можно строить вы числитель как коллектив, составленный из микровычислителеи.

Средства, основанные на модели коллектива вычислителей, называются вычислительными системами. Они заняли прочные позиции в совре-

менной индустрии обработки информации (точнее, в индустрии параллельных вычислений). Наиболее полно принципы модели коллектива вычисли-

телей воплощены в ВС c программируемой структурой (см. гл. 7 или [5, 6]). Концепция таких ВС была предложена в Сибирском отделении АН СССР.

Разработка теоретических основ и принципоi; технической реализации, a также создание первых ВС c программируемой структурой были осуществлены к началу 70-x годов ХХ в.

3.2. Техническая реализация модели коллектива вычислителей. Архитектypные свойства вычислительных систем

3.2.1. Принципы технической реализации модели коллектива вычиелителеи

Каноническое описание модели коллектива вычислителей (см. § 3.1), основополагающие принципы ее констpyкции , a также состояние микроэлектроники и уровень развития (параллельной) вычислительной математики определяют принципы технической реализации модели или принципы построения ВС. Выделим модульность и близкодействие как главные принципы технической реализации модели коллектива вычислителей.

118

3.2. Техническая реализация модели коллектива вы числителей

Модульность (Мodularity) принцип, предопределяющий формиро-

вание ВС из унифицированных элементов (называемых модулями), которые

ф ункционально и конструктивно закончены, имеют средства сопряжения c

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

Функциональные и конструктивные возможности модулей, разнообразие их

типов определяются исходя из требований, предъявляемыx к ВС, и, безусловно, из возможностей микpоэлектpонной базы.

Модyльность вычислительной системы обеспечивает:

1) возможность использования любого модуля заданного типа для выполнения любого соответствующего ему задания пользователя;

2) простоту замены одного модуля на другой однотипный;

з) масштабируемость, т. e. возможность увеличения или уменьшения модулей без коренной реконфигурации связей между остальны-

ми модулями; 4) открытость системы для модернизации, исключающую ее мораль-

ное старение.

Следует заметить, что принцип модyльности распространим и на средства программного обеспечения ВС.

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

с

мy для связи c другими модулями. На практике принято такой модульвычислитель называть либо элементарным процессором (ЭП), либо элементарной машиной (ЭМ). При этом считается, что ЭП это композиция из процессора и локального коммутатора. Разрядность таких ЭП в различных ВС колеблется от 1 до 64. Под элементарной машиной понимается архиtектурно более развитая композиция из ЭВМ и локального коммутатора.

Близкодействие (short-range interaction) принцип построения ВС,

обусловливающий такую организацию информационных взаимодействий между модyлями-вычислителями, при которой каждый из них может непо-

средственно (без «посредников») обмениваться информацией c весьма огра-

ниченной частью модyлей-вычислителей. Следовательно, структура ВС по-

зволяет осуществлять информационные взаимодействия между удаленными вершинами-вычислител ми лишь c помощью промежуточных вершин-

вычислителей, передающих информацию от точки к точке (point-to-point).

Удаленными считаются те вершины в структуре ВС, расстояние между которыми более 1 (число ребер между которыми более 1).

Принцип близкодействия допускает реализацию механизма управления ВС (организации функционирования коллектива вычислителей как еди-

119

3. Архитектура вычислительн 5тх систем

кого целого), не зависящий от количества составляющих ее вычислителей. Данный принцип, в частности, выражается в том, что поведение каждого вычислителя с1 Е C зависит от поведения толь ко ограниченного подмноже-

ства С* c C других вычислителей системы.

Во взаимосвязи c принципом близкодейс твия говорят также o локаль-

ности (locality) связей u взаимодействий между вычислителями. Последнее означает, что состояние Е1 (t + 1) вычислите пя с1 , i Е {0, 2, ... , N —1 }, на

очередном временном шаге (t + 1) зависит от юстояний (на предшествующем шаге t) непосредственно c ним связанныx вычислителей с С* т. e.

состояние является функцией

E; (t+1) = I(Eг(1 ), E' (1), Е'2 (t),..., Е' (1)),

где i1 , 1 =1, М номера вычислителей, составляющих С* , M < N. При этом вычислители подмножества

С* = {с1, , с12 , ... , c ' }

называются соседними по отношению к с1 Е С. Для достижения однородности структуры сети связей необходимо, чтобы каждый вычислитель был соединен c М другими вычислителями.

Вычислительные системы, основанные На принципах модульности и близкодействия, удовлетворяют также требов-:киям асинхронности, децентрализованности и распределенности.

Асинхронность функционирования (Asynchronous functioning) ВС обеспечивается, если порядок срабатывания ее модулей определяется не c помощью вырабатываемых тем или иным образе м отметок времени, a достижением заданных значений определенны (кап с правило, логических) функций. Использование асинхронных схем позволяет достичь в системе алгоритмически предельного быстpодействия: модули ВС срабатывают немедленно после выполнения соответствующего условия. Применение асинхронных схем обмена информацией между i;ычислителями позволяет не учитывать рaзброс в их тактовых частотах и колебания времени задержки сигналов в линиях связи.

Децентрализованность управления (Decentralized control) ВС достига-

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

120

3.2. Техническая реализация модели коллектива вычислителей

ванного решения об управлении системой, каждый модуль пользуется толь-

ко локальной информацией o системе.

Децентрализованное управление системой (в отличие от централизованного) позволяет:

1) достичь живучести ВС, т. e. ее способности продолжать работу при

отказах модулей (в том числе и тек, которые предназначены для принятия решений);

2) избежать очередей при обслуживании заявок на управление.

Распределенность ресурсов (State of distribution) ВС позволяет создавать такую систему, в которой нет единого ресурса, используемого другими в режиме разделения времени. Под ресурсами ВС понимаются все объекты, которые запрашиваются, используются и освобождаются в ходе выполнения вычислений. B качестве ресурсов ВС выступают процессоры или даже модули, входящие в их состав, модули оперативнойV памяти, внешние устройV- ства, линии межмодульных связей, шины, файлы данных, компоненты ПО. Вместе c этим каждый ресурс распределенной ВС рассматривается как об- щий, доступный любому потребителю.

3.2.2. Арxитектypные свойства ВС

Основополагающие принципы (параллелизма, программируемости,

однородности) и принципы модульности и близкодействия (см. разд. 3.1.1 и 3.2.1) позволяют достичь полноты архитектурных свойств в ВС. Oтмeтим

важнейшие свойства архитектуры ВС. При этом заметим, что не все свойст-

ва и не в полной мере могут проявляться в той или иной реализации ВС.

Масштабируемость (Scalability) ВС. Под масштабируемостью ВС

понимается их способность к наращиванию и сокращению ресурсов, воз-

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

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

Свойство наращиваемости производительности предоставляет потенциaльную возможность решать задачи любой априори заданной сложности. Однако для практической реализации этой возможности требуется, чтобы

алгоритм решения сложной задачи удовлетворял условию локальности, a

межмодyльные пересылки информации слабо влияли на время решения за-

121

3. Архитектура вычислительных систем

дачи. Это можно достичь за счет крупноблочного распараллеливания сложных задач (см. § 3.3) и (или) аппаратурных ср :дств, позволяющих совмес-

тить межмодульные обмены информацией c вычислениями.

Универсальность (Genericity, Generality, Versatility) ВС. Вычисли-

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

горитмическои универсальностью, следователi,но, и система универсальна (в общепринятом смысле).

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

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

Таким образом, ВС сочетают в себе дос гоинства цифровой техники, где процесс вычислений в основном задается а лгоритмически (точнее, про-

гpаммно), и аналоговой техники, где процесс вычислений предопределяется

структурными схемами.

Структурная универсальность позволяет говорить и o специализиро-

ванности ВС: для каждой задачи допустима автоматическая настройка такой конфигурации из ресурсов ВС, которая наиболее адекватна алгоритму решения задачи. Таким образом, ВС это средство, в котором диалектически сочетаются противоположные свойства ,'ниверсальности и специализированности.

Алгоритмическая и структурная универса. гiьность ВС проявляются также в возможности организации «виртуaльных» конфигураций c произвольной архитектурой (на уровне потоков команд и дан :ных) и реализации в ней известных режимов обработки информации.

Производительность (Performance, Throughput, Processing power) ВС.

B отличие от ЭВМ, построенных на основе модели вычислителя, ВС не имеют принципиальных ограничений в повышении производительности. Увеличение производительности в них достигается з а счет не только повышения физического быстродействия микроэлектроннык элементов, a главным образом увеличения числа вычислителей. Следует подчеркнуть, что благодаря

122