Краткая историческая справка

Оглавление.

Оглавление. 3

Глава 1. Введение. 4

§1.1. Краткая историческая справка. 4

§1.2. Режим реального времени. 8

Глава 2. Вычислительные системы.. 10

§2.1. Классификация ВС. 10

§2.2. Показатели качества ВС. 13

§2.3. Классификация ВС по организации структуры. 13

Глава 3. Распределение ресурсов процессора. 19

§3.1. Принципы упорядочивания ресурсов ВС методами теории расписаний. 19

§3.2. Общая постановка задачи упорядочивания. 28

§3.3. Задачи и критерии детерминированного распределения производительности вычислительных систем. 30

Глава 4. Распределение памяти в ВС. 31

§4.1. Оптимизация распределения памяти по иерархическим уровням. 31

§4.2. Управление замещением страниц в двухуровневой памяти. 37

§4.3. Класс многоуровневых алгоритмов замещения. 40

§4.4. Модели поведения программ и критерии качества. 44

Глава 5. Классические архитектуры многомашинных и многопроцессорных комплексов. 48

§5.1. Многомашинные комплексы. 48

§5.2. Многопроцессорные комплексы. 52

§5.3. Типы структур МПВК. 53

Глава 6. Примеры многомашинных и многопроцессорных систем. 55

§6.1. ВК на базе ЕС ЭВМ (IBM). 55

§6.2. ВК на базе СМ ЭВМ (DEC). 61

§6.3. Комплексы на основе микро-ЭВМ и микропроцессоров. 64

Глава 7. Особенности организации вычислительных процессов. 68

Глава 8. Системы параллельной обработки данных. 73

§8.1. Классификация систем параллельной обработки данных. 73

§9.6. Кластерная архитектура. 88

§9.7. Проблемы выполнения сети связи процессоров в кластерной системе. 91

Глава 10. Принципы построения коммуникационных сред. 95

§10.1. Коммутаторы для многопроцессорных вычислительных систем. 95

§10.2. Простые коммутаторы. 96

Простые коммутаторы с временным разделением. 96

Алгоритмы арбитража. 98

Особенности реализации шин. 99

Простые коммутаторы с пространственным разделением. 99

§10.3. Составные коммутаторы. 100

Коммутатор Клоза. 101

Баньян-сети. 102

Распределенные составные коммутаторы. 102

Глава 11. Примеры построения коммуникационных сред. 103

§11.1. Когерентный интерфейс SCI. 103

§11.2.Коммуникационная среда MYRINET. 105

Глава 12. Сосредоточенные вычислительные системы высокой производительности. 107

§12.1. Конвейерные системы. 107

§12.2. Иерархия памяти. 109

§12.3. Управление и организация конвейеров. 117

§12.4. Статические конвейеры. 124

§12.5. Диаграмма состояний. 125

§12.6. Генерирование таблиц занятости на основе циклов. 136

§12.7. Конвейеры с динамической конфигурацией. 149

§12.8. Функции управления в конвейерных системах. 158

§12.9. Архитектура конвейерных систем. 176

§12.10. Примеры конвейерных систем. 188

§12.11. Матричные вычислительные системы. 195

Список литературы. 204

Глава 1. Введение.

Краткая историческая справка.

Рисунок 1.1.   В таких ЭВМ, ввод-вывод информации осуществляется через АЛУ, поэтому во время ввода/вывода вычисления прекращались. В…

Режим реального времени

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

Глава 2. Вычислительные системы

Классификация ВС.

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

· наличие единой цели функции для всей системы;

· сложность реализуемой функции;

· большое количество взаимосвязанных элементов;

· возможность деления системы на подсистему;

· иерархия связей подсистем и иерархия критериев качества;

· наличие взаимодействия с внешней средой и функционирование в условиях воздействия случайных факторов;

· наличие управления в системе и высокая степень его автоматизации;

· устойчивость к внутренним и внешним возмущающим факторам;

· надежность системы.

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

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

1. Выбор оптимальной структуры ВС.

2. Оптимальное с точки зрения производительности распределение программ (частей) в системе.

3. Оптимальное распараллеливание алгоритмов.

4. Организация мультипрограммного режима работы.

5. Определение оптимального уровня централизации (при полной централизации недостаток – передача значительных массивов информации при обмене; при децентрализации недостаток – снижение качества управления за счет неполных сведений о состоянии элементов системы).

6. Оптимальное распределение и защита памяти.

Классификация ВС.

Существует множество классификаций вычислительных систем. Приведем некоторые из них.

По назначению ВС делятся на универсальные и специализированные.

По числу машин или процессоров принята классификация на одномашинные (однопроцессорные) и многомашинные (многопроцессорные).

По типу ЭВМ (процессоров) делятся на однородные и неоднородные.

По степени территориальной разобщенности принята классификация на ВС совмещенного и разобщенного типов. В разобщенной ВС информация по каналам к абонентам передается последующими кодами. Отсюда ясен недостаток.

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

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

По временному режиму существуют ВС, работающие в оперативном и неоперативном временных режимах. Оперативный режим соответствует работе в реальном масштабе времени.

Показатели качества ВС.

К показателям качества относятся:

1. Производительность системы, которая бывает номинальной и эффективной.

2. Номинальная производительность определяется суммой номинальных быстродействий машин ВС.

3. Эффективная производительность равна сумме эффективных быстродействий машин ВС.

4. Эффективное быстродействие определяется количеством операций в единицу времени с учетом потерь на ввод/вывод, устранение сбоев, контроль правильности вычислений и т.д.

5. Достоверность информации, равная вероятности того, что в выходной информации не содержатся ошибки.

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

7. Помехозащищенность.

8. Готовность системы, определяемая скоростью подготовки к работе.

9. Экономичность, то есть затраты на разработку, создания и эксплуатацию ВС.

Классификация ВС по организации структуры.

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

1. тип потока команд;

2. тип потока данных;

3. способ обработки данных в центральных устройствах обработки;

4. степень связанности компонент системы;

5. степень однородности ВС;

6. Тип внутренних связей ВС.

Эти шесть признаков определяют одну из схем классификации.

Специалистом в области ВС Флинном введена следующая классификация:

1. SISD (single instruction single data). Один поток команд управляет одним потоком данных (ОКОД). ЭВМ фон Неймана.

2. SIMD (single instruction multiply data). Один поток команд управляет многими потоками данных (ОКМД). Такая организация характерна для матричных систем.

3. MISD (single instruction multiply data). В таких системах много потоков команд управляют одним потоком данных (МКОД). Это характерно для магистральных структур.

4. MIMD (multiply instruction multiply data). В данном случае много потоков команд управляют многими потоками данных (МКМД), что характерно для многопроцессорных и многомашинных систем, сетей ЭВМ.

Такая классификация не позволяет различать многие архитектуры, и относит их к одному классу. Если использовать эту классификацию совместно с приведенными выше признаками, можно устранить этот недостаток. Такая классификация приведена на рисунке 2.1.

Рисунок 2.1.

На рисунке 2.1 приняты следующие условные обозначения:

а) С, Р – пословная и поразрядная обработка в центральных обрабатывающих устройствах;

б) Н_с, В_с – низкая и высокая степень связанности ВС;

в) О_p, Н_p – однородная и неоднородная ВС;

г) К_н, П_м, П_р – системы со связями канал-канал через общую внешнюю память между процессорами;

д)О_ш, М_ш, П_к – связи через общую шину, множество шин, перекрестные коммутаторы.

При слабой связи (Н_с) процессоры имеют индивидуальные блоки ОП и связаны с устройством управления, но не имеют непосредственных связей между собой (через адаптер канал-канал, через внешние ЗУ (диски), непосредственных связей процессор-процессор).

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

Множественность и число потоков определяется как максимально возможное число одновременных операций (команд) или операндов (данных), находящихся в одинаковой стадии обработки.

На рисунках 2.2, 2.3, 2.4, 2.5 приведены упрощенные структурные схемы ВС типов SISD, SIMD, MKOD и MKMD, соответственно.

Рис. 2.2.Структура систем типа ОКОД (SISD)

 

Рисунок 2.3. Структура систем типа ОКМД (SIMD) (матричные системы).

 

Рисунок 2.4. Структура систем типа МКОД (MISD).

Рисунок 2.5. Структура систем типа МКМД (MIМD).

В системах ОКМД одно УУ осуществляет управление работой множества процессоров так, что каждый из них выполняет последовательно заданные команды. Скорость обработки зависит от возможности загрузки процессоров (распараллеливание). В системах МКОД процесс обработки разбивается на несколько этапов, каждому из которых соответствует процессорный модуль. При частых прерываниях линейных участков командами ветвления скорость обработки снижается.

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

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

Системы ОКМД подразделяются на системы с пословной и поразрядной обработкой (ОКМДС и ОКМДР).

К ОКМДС относятся ансамбли процессоров с векторным потоком данных и матричные системы. Ансамбли процессоров связаны слабо, матричные системы характеризуются сильной связью.

К ОКМДР относятся ассоциативные системы, оперирующие разрядными срезами.

МКОДС это магистральные системы, МКОДР – магистраль одноразрядных процессоров.

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

 

Глава 3. Распределение ресурсов процессора.

Принципы упорядочивания ресурсов ВС методами теории расписаний.

В приоритетном алгоритме каждой программе присваивается приоритет выраженный целым числом k. Приоритет убывает с возрастанием k. Первой получает… Кроме того, приоритеты подразделяются на статические и динамические. Если… В бесприоритетных алгоритмах для каждой новой программы указывается правило постановки ее в очередь и задается…

Общая постановка задачи упорядочивания.

. Здесь =1, если i-ая заявка реализуется на к-ом месте и нулю в противном…

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

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

Глава 4. Распределение памяти в ВС.

Оптимизация распределения памяти по иерархическим уровням.

· Время обращения к ЗУ (длительность поиска + перепись данных). · Стоимость устройства, обеспечивающего хранение 1 единицы информации (1… · Объем информации, хранимой в ЗУ.

Управление замещением страниц в двухуровневой памяти.

Основной вопрос, возникающий при синтезе алгоритмов замещения, заключается в нахождении алгоритмов, которые дают приемлемую частоту обращений к ВП… 1. Случайное замещение (СЗ). В этом случае с заданной на множестве страниц ОП… 2. Раньше пришла – раньше ушла (РПРУ). При этом замещается страница, которая дольше всех находилась в ОП.

Класс многоуровневых алгоритмов замещения.

Экспериментальные исследования показывают, что у подавляющего большинства программ есть относительно небольшие множества страниц, после ввода которых в ОП частота страничных сбоев резко падает. Такое множество можно назвать рабочим телом программы. Рабочее тело программы может меняться в процессе ее выполнения. Поэтому желательно, чтобы алгоритм замещения обладал двумя отчасти противоречивыми свойствами: с одной стороны, алгоритм замещения должен сохранять в ОП страницы рабочего тела, а с другой – быстро обновлять содержимое ОП при смене рабочего тела.

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

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

Пусть упорядоченный список страниц, определяющий состояние ОП в момент t имеет вид , где m_t - объем ОП, отводимый программе в момент t. Для определения алгоритма замещения необходимо указать правила преобразования B_t в B_t+1. Многоуровневый алгоритм замещения из класса в общем случае определяет позицию страницы x_t+1 в списке B_t+1 с помощью h приоритетных подмножеств (списков) M₁,M₂,…,M_h, которые не пересекаются и .

Если страница x_t+1 отсутствует в ОП, то ей (при вводе в ОП) ставится в соответствие первая позиция в списке M_h, если же страница x_t+1 находилась в ОП и имела позицию в подмножестве , то этой странице ставится в соответствие первая позиция в списке более высокого приоритета M_i-1. Подмножества M₁,M₂,…,M_h задают в общем случае несколько уровней позиций страниц в списках B_t, определяющих состояние ОП. Отсюда и название алгоритмов – многоуровневые.

Для включения в класс алгоритмов замещения типа алгоритма РК вводятся параметры T_i, i=1,2,…,h, определяющие максимально допустимое время хранения (в пределах активности процесса) страницы в ОП без обращения к ней при условии, что ее позиция содержится в списке М_i , i=1,2,…,h, и параметры , определяющие максимальное число элементов в множествах M_i.

Пусть заданы правила образования подмножества и пусть B_t= (M₁,M₂,…,M_h) – состояние ОП в момент t. Если в момент t+1 произошло обращение к странице x_t+1, то новое состояние ОП при алгоритме определяется посредством следующих шагов:

Шаг 1. Из каждого множества удаляются те страницы, к которым не происходили обращения в течение времени большего T_r от момента обращения к x_t+1.

Шаг 2. Оставшиеся элементы M_r в множествах перенумеровываются таким образом, чтобы получившееся после первого шага 1 состояние ОП B_t^' имело вид:

B_t^'= (M₁^',M₂^',…,M_h^'),

где M_r^', r=1,2,…,h приведено к виду:

M_r^'= (i_r1,i_r2,…,i_rm),

причем некоторое множество M_r^' может быть пустым.

Шаг 3. Новое состояние ОП B^'_t+1 отличается от B^'_t :

· Только множеством M_h^', если (случай 1);

· Только множеством M_r^', если и , причем (случай 2);

· Только множествами M_r-1^' и M_r^', , если , (случай 3).

Обозначим через время, прошедшее с момента последнего обращения к странице ,и зададим h целых чисел l₁,l₂,…,l_h и h чисел , где , смысл которых разъясняется ниже. Тогда, если имеет место случай 1, то M_h^' преобразуется в:

Если имеет место случай 2, то M_r^' преобразуется в:

Если имеет место случай 3, то M_r-1^' преобразуется в

а M_r^' преобразуется в:

Класс χ содержит целый ряд алгоритмов замещения, представляющих теоретический и практический интерес. При h=1 и имеет место модифицированный алгоритм РК, который при превращается в алгоритм РК. Параметр позволяет ограничить объем ОП, отводимый программе. Чем меньше , тем меньше страниц ОП будет занимать программа в худшем случае, когда к каждой из своих страниц она обращается по 1 разу. Аналогично, в общем случае, выбирая параметр можно регулировать размеры списков M_i, не давая им чрезмерно увеличиться.

Полагая и получаем класс алгоритмов замещения , определяемых h+1 параметром: и , т.е. . При h=1 и l=m, где имеем алгоритм РПРУ, а при h=l=1 имеем алгоритм НДИ. Алгоритмы 1<l<m являются промежуточными между РПРУ и НДИ и отчасти похоже на известный алгоритм «раньше пришла, если не использовалась, то раньше ушла». Если позиции списка B_t пронумерованы как обычно, слева направо, то при алгоритме до тех пор, пока странице соответствует позиция списка ее изменение происходит так же, как при РПРУ, а при так же как при НДИ. Параметры входящие в определение алгоритмов интерпретируются аналогично внутри каждого из множеств , . Рассмотрим случай . Тогда параметр может принимать единственное значение . При алгоритме странице, только что введенной в ОП соответствуют позиция в списке B_t. Если до следующего страничного сбоя к этой странице не произойдет ни одного обращения, то она будет замещена. При обращении к странице, находящейся в ОП, ее позиция изменяется на , а страница будет поставлена на позицию . Перемещение с позиции на позицию 1можно уподобить подъему наверх по лестнице из ступеней. Отсюда название алгоритма – ЛЕСТН (лестничный). При позиции списка B_t разбиваются на h приоритет множеств (M₁,M₂,…,M_h). Странице, только что введенной в ОП, ставится в соответствие первая позиция в множестве младшего приоритета M_h. При каждом новом обращении к этой странице ее позиция будет последовательно перемещаться на 1-е место в множестве все более высокого приоритета.

Класс значительно χ значительно расширяет возможности управления замещением страниц по сравнению с классом , алгоритмы которого рассчитаны только на фиксированный объем ОП, отводимый программе и, кроме того, обладают тем недостатком, что излишне долго задерживают в ОП относительно редко используемые страницы, если к ним происходит несколько обращений подряд.

Модели поведения программ и критерии качества.

Простейшая стохастическая модель (независимая модель) описывает обращения x1,x2,… последовательностью независимых (одинаково распределенных)… Непосредственным обобщением такой независимой модели является марковская модель, которая описывает обращения x1,x2,……

Глава 5. Классические архитектуры многомашинных и многопроцессорных комплексов.

Многомашинные комплексы.

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

Многопроцессорные комплексы.

Следует оговорить, что любой процессор может иметь индивидуальные, доступные только ему ОЗУ и ПУ. Упрощенную схему МПВК из трех процессоров и двух модулей ОЗУ и одной…    

Типы структур МПВК.

В системах с общей шиной (рисунок 5.3) все устройства соединяются между собой с помощью шины, по которым передаются информация, адреса и сигналы…  

Глава 6. Примеры многомашинных и многопроцессорных систем.

ВК на базе ЕС ЭВМ (IBM).

различные многомашинные комплексы. Первым двухмашинным комплексом был ВК-1010, построенный на базе ЕС-1030. В… В ВК-1010 нет лишь связи между ЭВМ через общую ОП. Структурная схема ВК-1010 осталась практически без изменения и для…

ВК на базе СМ ЭВМ (DEC).

Как и в ЕС ЭВМ в СМ ЭВМ предусмотрен набор средств для создания комплексов: переключатель общей шины, адаптер межпроцессорной связи, устройство… Переключатель общей шины предназначен для построения многомашинных комплексов…  

Глава 7. Особенности организации вычислительных процессов.

Многомашинные ВК в наибольшей степени приспособлены для решения потока не связанных между собой слабосвязанных задач, т.е. задач, при решении которых объем взаимно передаваемой информации невелик. При этом, чем больше объем взаимно передаваемой информации, тем больше уменьшается производительность системы, т.к. часть времени используется на обмен. Анализ показывает, что решение одной задачи несколькими машинами в составе может быть оправданным только при наличии связи между ними через общее ОЗУ. Необходимо отметить, что в этом случае трудность решения определяется не столько потерями производительности из-за обмена информацией, сколько сложностью синхронизации этапов решения, а, следовательно, действия ЭВМ.

С учетом этого, можно дать оценку сложности ОС ЭВМ, входящих в МПВК.

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

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

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

Однако, использование всех возможностей МПВК является непростой задачей, так как операционные системы оказываются очень сложными.

Известны три типа организации вычислительного процесса в МПВК и соответствующие три типа функционирования ОС:

1. ведущий-ведомый;

2. раздельное выполнение заданий в любом процессоре;

3. симметричная или однородная обработка информации всеми процессорами.

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

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

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

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

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

Во-вторых, ОС МПВК должна осуществить автоматическое реконфигурирование комплекса (перераспределение ресурсов), что осложняет ОС.

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

Сравнение ММВК и МПВК.

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

По параметру надежности МПВК имеют явное преимущество: в ММВК резервирование осуществляется по машинам, а в МПВК- по устройствам. МПВК может обеспечить большую надежность при том же объеме оборудования.

Оценку производительности выполнить сложно. Рассмотрим два варианта нагрузки комплекса. В первом варианте в ВК поступает большой поток несвязанных задач с небольшим объемом вычислений. Во втором варианте комплекс нагружается крупноразмерными задачами, число которых может быть и невелико, но с большим объемом вычислительной работы.

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

В МПВК при этом варианте из-за общедоступности всех ресурсов возрастает число конфликтов, то есть число простоев и производительность растет нелинейно в зависимости от числа процессоров. Операционная система здесь гораздо сложнее, что тоже ведет к потерям. Экспериментальные оценки показывают, что при подключении второго процессора производительность повышается на 60-80%(а не вдвое), а третьего - дает прирост в 2,1 раза, а не втрое.

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

Для МПВК решение таких задач не приводит к дополнительным затратам. Конечно, решение сложных задач с параллельной обработкой требует сложной ОС. Таким образом, при решении больших задач производительность МПВК больше производительности ММВК при равном числе процессоров.

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

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

ОС МПВК гораздо сложнее ОС ММВК. В связи с тем, что стоимость аппаратуры снижается, стоимость программного обеспечения приобретает все больший вес в затратах на создание ВК.

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

Глава 8. Системы параллельной обработки данных.

Классификация систем параллельной обработки данных.

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

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

Параллельные ЭВМ часто подразделяются по классификации Флинна на машины типа SIMD (Single Instruction Multiple Data - с одним потоком команд при множественном потоке данных) и MIMD (Multiple Instruction Multiple Data - с множественным потоком команд при множественном потоке данных). Как и любая другая, эта классификация несовершенна: существуют машины в нее не попадающие, имеются также важные признаки, которые в этой классификации не учтены. В частности, к машинам типа SIMD часто относят векторные процессоры, хотя их высокая производительность зависит от другой формы параллелизма - конвейерной организации машины. Многопроцессорные векторные системы, типа Cray Y-MP, состоят из нескольких векторных процессоров и поэтому могут быть названы MSIMD (Multiple SIMD).

Классификация Флинна не делает различия по другим важным для вычислительных моделей характеристикам, например, по уровню "зернистости" параллельных вычислений и методам синхронизации.

Можно выделить четыре основных типа архитектуры систем параллельной обработки:

1) Конвейерная и векторная обработка.

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

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

2) Машины типа SIMD. Машины типа SIMD состоят из большого числа идентичных процессорных элементов, имеющих собственную память. Все процессорные элементы в такой машине выполняют одну и ту же программу. Очевидно, что такая машина, составленная из большого числа процессоров, может обеспечить очень высокую производительность только на тех задачах, при решении которых все процессоры могут делать одну и ту же работу. Модель вычислений для машины SIMD очень похожа на модель вычислений для векторного процессора: одиночная операция выполняется над большим блоком данных.

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

Модели вычислений на векторных и матричных ЭВМ настолько схожи, что эти ЭВМ часто рассматриваются как эквивалентные.

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

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

4) Многопроцессорные машины с SIMD-процессорами.

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

Языки программирования и соответствующие компиляторы для машин типа MSIMD обычно обеспечивают языковые конструкции, которые позволяют программисту описывать "крупнозернистый" параллелизм. В пределах каждой задачи компилятор автоматически векторизует подходящие циклы. Машины типа MSIMD дают возможность использовать лучший из этих двух принципов декомпозиции: векторные операции ("мелкозернистый" параллелизм) для тех частей программы, которые подходят для этого, и гибкие возможности MIMD-архитектуры для других частей программы.

Многопроцессорные системы за годы развития вычислительной техники претерпели ряд этапов своего развития. Исторически первой стала осваиваться технология SIMD. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факторами:

1. Архитектура MIMD дает большую гибкость: при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения MIMD может работать как однопользовательская система, обеспечивая высокопроизводительную обработку данных для одной прикладной задачи, как многопрограммная машина, выполняющая множество задач параллельно, и как некоторая комбинация этих возможностей.

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

Одной из отличительных особенностей многопроцессорной вычислительной системы является сеть обмена, с помощью которой процессоры соединяются друг с другом или с памятью. Модель обмена настолько важна для многопроцессорной системы, что многие характеристики производительности и другие оценки выражаются отношением времени обработки к времени обмена, соответствующим решаемым задачам. Существуют две основные модели межпроцессорного обмена: одна основана на передаче сообщений, другая - на использовании общей памяти. В многопроцессорной системе с общей памятью один процессор осуществляет запись в конкретную ячейку, а другой процессор производит считывание из этой ячейки памяти. Чтобы обеспечить согласованность данных и синхронизацию процессов, обмен часто реализуется по принципу взаимно исключающего доступа к общей памяти методом "почтового ящика".

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

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

В сетях с коммутацией каналов и в сетях с коммутацией пакетов по мере возрастания требований к обмену следует учитывать возможность перегрузки сети. Здесь межпроцессорный обмен связывает сетевые ресурсы: каналы, процессоры, буферы сообщений. Объем передаваемой информации может быть сокращен за счет тщательной функциональной декомпозиции задачи и тщательного диспетчирования выполняемых функций.

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

К первой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Структура подобной системы представлена на рис. 8.1.

Рисунок 8.1.Типовая архитектура мультипроцессорной системы с общей памятью.

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

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

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

Обычно устройства ввода/вывода, также как и память, распределяются по узлам и в действительности узлы могут состоять из небольшого числа (2-8) процессоров, соединенных между собой другим способом. Хотя такая кластеризация нескольких процессоров с памятью и сетевой интерфейс могут быть достаточно полезными с точки зрения эффективности в стоимостном выражении, это не очень существенно для понимания того, как такая машина работает, поэтому мы пока остановимся на системах с одним процессором на узел. Основная разница в архитектуре, которую следует выделить в машинах с распределенной памятью заключается в том, как осуществляется связь и какова логическая модель памяти.

Рисунок 8.2. Типовая архитектура машины с распределенной памятью.

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

Рисунок 8.3. Структура класса многопроцессорных вычислительных систем.

Для мультипроцессоров учитывается способ построения общей памяти. Возможный подход – использование единой централизованной общей памяти. Такой подход обеспечивает однородный доступ к памяти (uniform memory access or UMA) и служит основой для построения векторных суперкомпьютерных систем (parallel vector processor-PVP) и симметричных мультипроцессоров (symmetric multiprocessor or SMP).

Общий доступ к данным может быть обеспечен и при физически распределенной памяти. При этом время доступа уже не будет одинаковым для всех модулей памяти. Такой подход именуется как неоднородный доступ к памяти (non-uniform memory access or NUMA). Среди систем с таким типом выделяют:

• Системы, в которых для предоставления данных используется только локальная кэш память процессоров (cache-only memory architecture or COMA);

• Системы в которых обеспечивается однозначность (когерентность) локальных кэш памятей разных процессоров (cache-coherent NUMA or CC-NUMA);

• Системы в которых обеспечивается общий доступ к локальной памяти разных процессоров без поддержки на аппаратном уровне когерентности кэша (non-cache coherent NUMA or NCC-NUMA).

Мультикомпьютеры (системы с распределенной памятью) уже не обеспечивают общий доступ ко всей имеющейся в системах памяти (no-remote access or NORMA).

Такой подход используется при построении двух важных типов многопроцессорных систем – массивно-параллельных систем (massively parallel processor or MPP) и кластеров (clusters).

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

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

• предсказания погоды и глобальных изменений в атмосфере;

• полупроводниковая техника;

• сверхпроводимость;

• биология;

• генетика;

• квантовая физика;

• астрономия;

• транспортные задачи;

• гидро- и газодинамика;

• управляемый термоядерный синтез;

• геоинформационные системы;

• геология;

• наука о мировом океане;

• распознавание и синтез речи;

• распознавание изображений.

Наиболее распространенными типами многопроцессорных вычислительных систем являются:

• системы высокой надежности;

• системы для высокопроизводительных вычислений;

• многопоточные системы.

Следует отметить, что при проектировании большой системы общего назначения она, как правило, должна выполнять все перечисленные функции. МВС являются идеальной схемой для повышения надежности информационно-вычислительной системы. Отдельные неисправные узлы или компоненты МВС могут прозрачно для пользователя заменяться, обеспечивая непрерывность и безотказную работу. Главной характеристикой многопроцессорной вычислительной системы является ее производительность, т.е. количество операций, производимых системой за единицу времени. Используют два вида производительности: пиковую и реальную производительность. Под пиковой понимают величину, равную произведению пиковой производительности одного процессора на число таких процессоров в данной машине. При этом предполагается, что все устройства компьютера работают в максимально производительном режиме. Пиковая производительность компьютера является базовой, по которой производят сравнение высокопроизводительных вычислительных систем. Пиковая производительность - величина теоретическая и недостижимая при запуске конкретного приложения. Реальная производительность, достигаемая на данном приложении, зависит от взаимодействия программной модели с архитектурными особенностями системы. Существует два способа оценки пиковой производительности компьютера. Одним из них является число команд (инструкций), выполняемых компьютером за единицу времени. Единицей измерения является MIPS (Million Instructions Per Second). Производительность, выраженная в MIPS, говорит о скорости выполнения компьютером своих же инструкций. Но, во-первых, заранее не ясно, в какое количество инструкций отобразится конкретная программа, а во-вторых, каждая программа обладает своей спецификой, и число команд от программы к программе может меняться очень сильно. В связи с этим данная характеристика дает лишь самое общее представление о производительности компьютера. Другой способ измерения производительности заключается в определении числа вещественных операций, выполняемых компьютером за единицу времени. Единицей измерения является Flops (Floating point operations per second) – число операций с плавающей точкой, производимых компьютером за одну секунду. Такой способ является более приемлемым для пользователя, поскольку ему известна вычислительная сложность программы, и, пользуясь этой характеристикой, пользователь может получить нижнюю оценку времени ее выполнения. Однако пиковая производительность получается только в идеальных условиях, т.е. при отсутствии конфликтов при обращении к памяти при равномерной загрузке всех устройств. В реальных условиях на выполнение конкретной программы влияют такие аппаратно-программные особенности данного компьютера как: особенности структуры процессора, системы команд, состав функциональных устройств, реализация ввода/вывода, эффективность работы компиляторов.

Одним из определяющих факторов является время взаимодействия с памятью, которое определяется ее строением, объемом и архитектурой подсистем доступа в память. В большинстве современных компьютеров в качестве организации наиболее эффективного доступа к памяти используется так называемая многоуровневая иерархическая память. В качестве уровней используются регистры и регистровая память, основная оперативная память, кэш-память, виртуальные и жесткие диски, ленточные роботы. При этом выдерживается следующий принцип формирования иерархии: при повышении уровня памяти скорость обработки данных должна увеличиваться, а объем уровня памяти – уменьшаться. Эффективность использования такого рода иерархии достигается за счет хранения часто используемых данных в памяти верхнего уровня, время доступа к которой минимально. А поскольку такая память обходится достаточно дорого, ее объем не может быть большим. Иерархия памяти относится к тем особенностям архитектуры компьютеров, которые имеют огромное значение для повышения их производительности.

Для того чтобы оценить эффективность работы вычислительной системы на реальных задачах, был разработан фиксированный набор тестов. Наиболее известным из них является LINPACK – программа, предназначенная для решения системы линейных алгебраических уравнений с плотной матрицей с выбором главного элемента по строке. LINPACK используется для формирования списка Top500 – пятисот самых мощных компьютеров мира. Однако LINPACK имеет существенный недостаток: программа распараллеливается, поэтому невозможно оценить эффективность работы коммуникационного компонента суперкомпьютера. В настоящее время большое распространение получили тестовые программы, взятые из разных предметных областей и представляющие собой либо модельные, либо реальные промышленные приложения. Такие тесты позволяют оценить производительность компьютера действительно на реальных задачах и получить наиболее полное представление об эффективности работы компьютера с конкретным приложением. Наиболее распространенными тестами, построенными по этому принципу, являются: набор из 24 Ливерморских циклов (The Livermore Fortran Kernels, LFK) и пакет NAS Parallel Benchmarks (NPB), в состав которого входят две группы тестов, отражающих различные стороны реальных программ вычислительной гидродинамики. NAS тесты являются альтернативой LINPACK, поскольку они относительно просты и в то же время содержат значительно больше вычислений, чем, например, LINPACK или LFK. Однако при всем разнообразии тестовые программы не могут дать полного представления о работе компьютера в различных режимах.

 

 

Рисунок 8.4. CRAY SV-2.

2. NEC SX-6, NUMA-архитектура. Пиковая производительность системы может достигать 8 Тфлопс, производительность одного процессора составляет 9,6 Гфлопс. Система масштабируется с единым образом операционной системы до 512 процессоров.

3. Fujitsu-VPP5000 (vector parallel processing), MPP-архитектура (рисунок 9.5). Производительность одного процессора составляет 9.6 Гфлопс, пиковая производительность системы может достигать 1249 Гфлопс, максимальная емкость памяти – 8 Тбайт. Система масштабируется до 512.

Рисунок 8.5. Fujitsu-VPP5000

Парадигма программирования на PVP-системах предусматривает векторизацию циклов (для достижения разумной производительности одного процессора) и их распараллеливание (для одновременной загрузки нескольких процессоров одним приложением).

На практике рекомендуется выполнять следующие процедуры:

· производить векторизацию вручную, чтобы перевести задачу в матричную форму. При этом, в соответствии с длиной вектора, размеры матрицы должны быть кратны 128 или 256;

· работать с векторами в виртуальном пространстве, разлагая искомую функцию в ряд и оставляя число членов ряда, кратное 128 или 256.

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

 

Глава 9. Кластерные системы.

Кластерная архитектура.

Кластеризация может осуществляться на разных уровнях компьютерной системы, включая аппаратное обеспечение, операционные системы, программы-утилиты,… Кластеры можно условно разделить на классы: · Класс I. Класс машин строится целиком из стандартных деталей, которые продают многие поставщики компьютерных…

Проблемы выполнения сети связи процессоров в кластерной системе.

В качестве примера рассмотрим задачу построения симметричной 16-процессорной системы, в которой все процессоры были бы равноправны. Наиболее… Рисунок 9.6. Схема соединения процессоров в виде плоской решетки.

Глава 10. Принципы построения коммуникационных сред.

Коммутаторы для многопроцессорных вычислительных систем.

При этом возможны различные конфигурации получающихся систем связи. Так, в компьютерах семейства Cray T3D/T3E все процессоры были объединены… Гораздо более простым и дешевым оказалось использование связей на базе сетей… Коммуникационные среды вычислительных систем (ВС) состоят из адаптеров вычислительных модулей (ВМ) и коммутаторов,…

Простые коммутаторы.

· с временным разделением; · с пространственным разделением. Достоинства: простота управления и высокое быстродействие.

Составные коммутаторы.

Составные коммутаторы имеют задержку, пропорциональную количеству простых коммутаторов, через которые проходит сигнал от входа до выхода, т.е. числу… Чаще всего составные коммутаторы строятся из прямоугольных коммутаторов 2 х 2…  

Глава 11. Примеры построения коммуникационных сред.

Когерентный интерфейс SCI.

Еще одно преимущество SCI – использование простых протоколов типа RISC, которые обеспечивают большую пропускную способность. Узлы с адаптерами SCI… Рисунок 11.1. Матрица узлов кластера на основе сети SCI.

Коммуникационная среда MYRINET.

Технология Myrinet основана на использовании многопортовых коммутаторов при ограниченных несколькими метрами длинах связей узлов с портами… Как коммутируемая сеть, аналогичная по структуре сегментам Ethernet,… На физическом уровне линки Myrinet состоят из 9 проводников: 8 битов предназначены для передачи информации,…

Конвейерные системы.

Основой конвейерных систем является конвейер (магистраль) обработки. Такая магистраль представляет собой набор функциональных блоков обработки с…   Рисунок 12.1.

Управление и организация конвейеров.

Имеются подклассы конвейеров, для которых существуют оптимальные или хотя бы эвристически хорошие алгоритмы диспетчеризации. Наиболее важные из этих… 1. время использования для любых ступеней является кратным некоторому периоду… 2. если вычисления начато в конвейере, то его временная схема использования ступеней фиксирована.

Статические конвейеры.

Последовательность латентностей представляет собой перечень латентностей между последовательностями инициациями и записывается как серия… Если последовательность латентностей состоит из некоторой периодически… Период цикла – сумма входящих в него латентностей. Средняя латентность цикла – это период делений на число латентности…

Диаграмма состояний.

В любом состояний закодированная информация называется вектором столкновений. Такой вектор является d – разрядно двоичной последовательностью, где d… Вектор столкновений для начального состояния называется начальным вектором… Альтернативный подход состоит в построении множества запрещенных латентностей. Число i является членом этого множества…

Генерирование таблиц занятости на основе циклов.

Определим множество Gс интервалов инициации данного цикла С как множество всех целых чисел i, таких, что интервал между некоторой парой инициаций… Здесь T(j)- начальный момент j-й инициации равен сумме латентностей предыдущих… T(j)=

Конвейеры с динамической конфигурацией.

Модифицированные диаграммы состояний. Диаграмма состояний для статического случая обобщается на динамический… Для каждого такта матрица столкновений указывает множество возможных инициаций. Матрица столкновений С- это двоичная…

Функции управления в конвейерных системах.

Основная функция управления состоит в определении момента, когда может быть сделана новая инициация. Этот момент зависит как от свойств…      

Примеры конвейерных систем.

Система STAR-100

Магистральная ВС STAR-100 (рисунок 12.37) разработана фирмой CDC в 1970 г., поставлена в 1973 г.

Рисунок 12.37.

Быстродействие – 10⁸ оп./сек, стоимость 15 млн. долларов, вес 75т. Система STAR-100 состоит из двух подсистем. Первая подсистема осуществляет переработку данных, вторая обеспечивает функциональные операции системы. Ядром первой подсистемы является процессор, образуемый из нескольких магистралей. В реализованном варианте STAR-100 процессор состоит из трех магистралей М1, М2, М3. Магистрали частично специализированы: две из них (М1,М2) служат для выполнения групповых операций, а третья (М3) предназначена для выполнения негрупповых операций над операндами. Иными словами, М1 и М2 – магистрали, каждая из которых служит для выполнения операций (с плавающей запятой) над парами векторов данных, М3 – магистраль для обработки обычных операндов не организованных в векторы. М1 и М2 выполняют основной объем вычислений.

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

В магистралях М1 и М2 путем введения служебного булевского вектора обеспечена избирательная обработка элементов векторов. Единица в i-м разряде булевского вектора означает, что операция над i-ми координатами соответствующей пары рабочих векторов производиться не будет. Память может включать в себя до 32 модулей и относиться к классу памятей с перемежающимися адресами. Модули допускают одновременное обращение.

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

Использование буферной памяти вызвано тем, что быстродействие памяти существенно ниже быстродействия процессора.

Назначение канала прямого доступа в память (КПДП) и мультиплексного канала следует из структуры связей между устройствами STAR-100.

Был реализован модифицированный вариант- система SUPERSTAR, в 2-3 раза производительней и более компактной.

Использовалась в системе противовоздушной обороны США.

Система CRAY 1-3.

Первый экземпляр системы CRAY-1поставлен в Лос-Аламос в 1976 г. Её особенностью является малые размеры. Машина состоит из цилиндрической стойки диаметром 1,76 м, высотой 1,98 м и диаметром в основании на уровне поля ≈2,74 м. Центральная стойка делится на три 90⁰ сегмента, в каждый из которых входят четыре клинообразные стойки, содержащие схемные модули. Каждый модуль содержит пару печатных плат, смонтированных на противоположных сторонах медной теплопроводящей пластины. Пластины вставляются в вертикальные литые алюминиевые штанги охлаждения. Охлаждение фреоновое (на уровне 25ºС на пластине и 48º-54º С в модуле). Максимальная скорость вычисления равна 160 мфлоп/сек (≈16∙10⁸ оп/сек).

Машина является глубоко конвейеризированной, имеющей все элементы показанной на типовой схеме конвейерной векторной ЭВМ. Набор команд – комбинация векторных и скалярных команд. Элементы векторов могут размещаться в памяти регулярно, причем имеются некоторые средства, основанные на двоичных векторах, для селективного запоминания и проверки векторов. Локальная память доступна программисту. Архитектура CRAY-1 показана на рисунке 12.38.

 

 

 

 

Рис

Рисунок 12.38.

Процессор обработки команд содержит все скалярные регистры и осуществляет декодирование команд и управление системой. Функцию локальной памяти выполняют восемь векторных регистров. Каждый векторный регистр может содержать до 64 слов (элементов вектора). Имеется 12 функциональных устройств (все конвейеризованы), производящих любые вычислительные действия, необходимые для использования команд. Шесть из этих устройств используются только процессором обработки команд для адресных вычислений, сложения целочисленных адресов, логические операции и операции сдвига, а также для сканирования двоичных векторов. Это последнее устройство – устройство подсчета нулей в старших разрядах 64 двоичного вектора, либо общее число нулей и единиц в двоичном векторе.

Из остальных шести функциональных устройств три используются только для векторных операций над целочисленными и логическими данными, а три других выполняют все операции с плавающей запятой, как для векторных, так и для скалярных команд. Все они являются линейными конвейерами с числом ступеней от 2 до 14. Большинство векторных команд имеет тот же формат, что и их скалярные эквиваленты – 16 разрядная команда, которая содержит 7 разрядный код операции и задает три векторных регистра. В число возможных операций входят: сложение, вычитание, умножение, вычисление обратной величины и сдвиги. Все они выполняются поэтапно. Например, если выбраны векторные регистры v_i, v_j и v_k, то m-е элементы регистров v_j и v_k прогоняются через соответствующие устройства, а результат заносится в m-й элемент v_i. Регистр длины вектора в процессоре обработки команд, содержит максимальное значение m, которое не может быть больше 64. Векторные регистры могут использоваться повторно, так что векторная программа может целиком исполняться, оперируя данными, находящимися в этих регистрах, без обращения к основной памяти. Всего команд 120. Все команды, кроме 18 имеют 16 разрядов, а те – 32 разряда. Команды обращения к адресам памяти (24 разряда) являются 32- разрядными.

Регистр векторной маски содержит 64 разрядный вектор для использования в операции, подобной селективному запоминанию и называемой слиянием. Содержимое m-го разряда регистра векторной маски определяет, какой из двух векторных регистров будет использован для выдачи m-го элемента в регистр результата (слияние двух векторов). К числу других применений этого регистра относится хранение результата векторной команды проверки. Каждый элемент выбранного векторного регистра проверяется на выполнение некоторого условия, и если он удовлетворяет этому условию, то в соответствующий разряд регистра маски заносится 1. Результат может затем использоваться последующей командой слияния или же скалярными командами, которые имеют возможность получать доступ к выбранным элементам векторного регистра. Имеются отдельные команды для передачи данных между векторным регистром и основной памятью. Эти команды задают начальный адрес памяти, промежуток между элементами и векторный регистр. Передача происходит по одному элементу за период синхронизации. Одной командой может быть передано не более 64 слов. Векторные операции над векторами, длиной более 64, должны программироваться явно, а векторы разбиваются на части, длиной меньше 64. Система CRAY-1 имеет некоторые уникальные свойства. Первое состоит в том, что векторные команды, которые не используют ни одного общего векторного регистра, могут использоваться почти одновременно (используя разные функциональные устройства). Другое свойство называется зацеплением, когда регистр результата одной векторной команды совпадает с одним из входных регистров следующей команды. Если эти команды используют различные функциональные устройства, то это эквивалентно построению нового конвейера. Система команд позволяет организовать зацепление более чем двух команд. При этом в цепочке могут быть не только арифметические операции, но и векторные: обмен между памятью и векторными регистрами. Память системы представляет собой 16-кратную расслоенную структуру.

 

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

Матричный процессор представляет собой «матрицу», связанных элементарных идентичных процессоров, управляемых одним потоком команд (рисунок 12.39). … Рисунок 12.39.

Резюме.

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

Матричные ВС – вариант реализации модели коллективных вычислений. В таких системах воплощены следующие принципы построения:

1. Параллельность выполнения операций и одновременной работы различных подсистем.

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

3. Конструктивная однородность.

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

Список литературы.

1. Бройдо В.А. Вычислительные системы, сети и телекоммуникации: Учебное пособие для вузов. – СПб.:Питер, 2006. – 704 с.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.:БХВ – Петербург, 2004. – 608.:с.

3. Каган Б.М. Электронные вычислительные машины и системы. М.: Энергоиздат, 1991. – 592 с.

4. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. – 600 с.

5. Коуги П. Архитектура конвейерных ЭВМ. М.: Радио и связь, 1985. -360с.

6. Ларионов А.М., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. М.: Энергоиздат, 1987.-287 с.

7. Пятибратов А.П. Вычислительные системы, сети и телекоммуникации. Учебник для вузов. М.: Финансы и статистика, 2004. – 512 с.

8. СуперЭВМ: Аппаратная и программная реализация. Под ред. С. Фернбаха. М.: Радио и связь, 1991. – 320 с.

9. Хокни Р., Джессхоун К. Параллельные ЭВМ: Архитектура, программирование и алгоритмы. М.: Радио и связь, 1986. – 392 с.

10. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем: Учебник для вузов.. – СПБ.: Питер, 2007. – 668 с.

11. http://parallel.ru/computers

12. http://informika.ru/text/teach/topolog

13. http://parallel.ru/krukov