205

Оглавление.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История развития вычислительных машин и систем берет начало от концепции вычислительной машины фон Неймана. В качестве основных устройств универсальных ЭВМ были выделены: арифметико-логическое устройство (АЛУ), память для данных и команд, устройство управления (УУ) и устройство ввода-вывода (УВВ) (рис. 1.1).

Рисунок 1.1.

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

Рисунок 1.2.

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

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

В целях согласования скоростей работы АЛУ и памяти были совмещены во времени обращения к памяти. ОП разделяется на секции с раздельным обращением к ним. Количество секций либо равно степени 2, либо каждая секция снабжается собственными адресным и числовым регистрами. Вводится чередование адресов. Если память разбита на n=2^m секций, то ячейки с адресами 0, 1, … , n-1 реализуются как первые ячейки в любой из n последовательно расположенных секций, ячейки с адресами n, n+1, … , 2n-1, как вторые ячейки в этих секциях и т.д. В адресном поле команды номер секции кодируется старшими разрядами, а номер внутри секции – младшими. При такой организации обращения к ячейкам памяти с последовательно увеличивающимися адресами (что типично на практике) осуществляется последовательно к каждой секции. В наиболее благоприятном случае цикл работы памяти сокращается в n раз по сравнению с циклом работы ее отдельной секции.

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

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

Системами с квантованным обслуживанием называются системы с разделением времени.

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

Используются несколько дисциплин обслуживания. Их можно разбить на две группы: одноочередные и многоочередные (многоуровневые).

В одноочередном имеется одна очередь. Вновь поступающие запросы ставятся в конец очереди. Запросам предоставляется квант времени ∆, недообслужанные запросы поступают в конец очереди.

В многоочередных приоритет очереди убывает с увеличение ее номера m. Вновь поступающий запрос ставится в конец очереди со старшим приоритетом (m=0).

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

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

– число байт в программе,

- число байт, которые могут быть переданы из ОП во внешнюю память или обратно за время ∆ (алгоритм Ф. Корбато)