Исследование и анализ архитектуры компьютеров параллельного действия

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

ЮЖНО-КАЗАХСТАНСКИЙ ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ

Специальность: 3703 «Вычислительные машины, комплексы, системы и сети»

Дипломный проект

ТЕМА: Исследование и анализ архитектуры компьютеров параллельного действия.

Дипломник _____________ Иванов И.И _________

(Подпись) (Ф.И.О.)

Руководитель ___________ Элиадзе Ю.А ______

(Подпись) (Ф.И.О.)

Допустить к защите _______________________________________

Шымкент 2011г.

ОТЗЫВ

на дипломный проект

Дипломника: Иванова И, учащегося гр.472

Специальности: 3703 «Вычислительные машины, комплексы, системы и сети».

На тему: Исследование и анализ архитектуры компьютеров параллельного действия.

Выполнение согласно заданию:

А) описательной части:

Введение

1. Вопросы разработки компьютеров параллельного действия

2. Информационные модели

3. Производительность компьютеров параллельного действия.

4. Метрика аппаратного обеспечения

5. Метрика программного обеспечения

6. Методы достижения высокой производительности

7. Программное обеспечение

Б) Технической части:

8. Классификация компьютеров параллельного действия

9. Компьютеры SIMD

10. Мультикомпьютеры с передачей сообщений

11. МРР -- процессоры с массовым параллелизмом

12. Связное программное обеспечение для мультикомпьютеров

В) в специальной части:

13. Буферирование сигналов магистрали УС с ISA.

Д) охрана труда и техника безопасности:

Инструкция по охране труда для операторов ЭВМ.

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

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

Дипломный проект Киргизбаева Бахадыра заслуживает

оценки: 4 (четыре)

Руководитель дипломного проекта : Элиадзе Ю.А.

___________________Подпись

«Утверждаю»

Заместитель директора

по учебной работе

________________

18 декабря 2010г.

ЗАДАНИЕ

на дипломный проект

Дипломника: Иванова И уч-ся гр.472

Специальности: 3703 «Вычислительные машины, комплексы,

системы и сети»

Тема проекта: Исследование и анализ архитектуры компьютеров параллельного действия.

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

Содержание расчетно-пояснительной записки

А) описательной части:

Введение

1. Вопросы разработки компьютеров параллельного действия

2. Информационные модели

3. Производительность компьютеров параллельного действия.

4. Метрика аппаратного обеспечения

5. Метрика программного обеспечения

6. Методы достижения высокой производительности

7. Программное обеспечение

Б) Технической части:

8. Классификация компьютеров параллельного действия

9. Компьютеры SIMD

10. Мультикомпьютеры с передачей сообщений

11. МРР -- процессоры с массовым параллелизмом

В) в специальной части:

12. Связное программное обеспечение для мультикомпьютеров

Г) в экономической части: ____________________________________

Д) охрана труда и техника безопасности:

Инструкция по охране труда для операторов ЭВМ.

Содержание и объем графической части

Графическая часть дипломного проекта выполняется на листах формата А4 и дублируется файлом электронной презентации графической части, выполненной в PowerPoint, или листами прозрачной пленки. При выполнении графических работ может использоваться черная тушь или фломастер. Допускается использование лазерного принтера или ксерокса. При выполнении графических работ необходимо строго руководствоваться нормативными документами и ГОСТ. Количество рисунков и схем, поясняющих содержание дипломной работы - не менее 5 листов.

Руководитель проекта ____________/Элиадзе Ю.А./

Дата выдачи задания «20»декабря 2010г.

Дата окончания проекта «20» февраля 2011г.

Зав кафедрой____________/Элиадзе Ю.А./

Расчетно-пояснительная записка

Дипломник: Киргизбаев Б.

Руководитель дипломного проектирования:

Консультанты: ___________________

По технологической части: ___________________

По экономической части: ___________________

______________________ ___________________

______________________ ___________________

______________________ ___________________

Приложение:

Графическая часть на ______________________ листах

СОДЕРЖАНИЕ

компьютер параллельный коммутация маршрут

Введение

1. Вопросы разработки компьютеров параллельного действия

2. Информационные модели

2.1. Мультипроцессоры

2.2. Мультикомпьютеры

2.3. Сети межсоединений

2.3.1.Топология

2.4. Коммутация

2.5. Алгоритмы выбора маршрута

3. Производительность компьютеров параллельного действия.

4. Метрика аппаратного обеспечения

5. Метрика программного обеспечения

6. Методы достижения высокой производительности

7. Программное обеспечение

8. Классификация компьютеров параллельного действия

9. Компьютеры SIMD

9.1. Массивно-параллельные процессоры

9.2. Мультипроцессоры с памятью совместного использования

9.3. Мультипроцессор Stanford DASH

9.4. Мультипроцессор Sequent NUMA-Q

10. Мультикомпьютеры с передачей сообщений

11. МРР -- процессоры с массовым параллелизмом

11.1. МРР (Massively Parallel Processors -- процессоры с массовым

параллелизмом)

11.2. Cray T3E

11.3. Intel/Sandia Option Red

11.4. COW -- Clusters of Workstations (кластеры рабочих станций)

11.4.1. Планирование

11.4.2. Коммерческие сети межсоединений

12. Связное программное обеспечение для мультикомпью-

теров

12.1.РVM -- виртуальная машина параллельного действия)

12.1.1. РVM (Parallel Virtual Machine -- виртуальная машина параллельного действия

12.1.2. MPI -- интерфейс с передачей сообщений

13. Спец часть. Буферирование сигналов магистрали УС с ISA.

14. Охрана труда и техника безопасности. Инструкция по охране труда

для операторов.

14.1. Oбщие требования по безопасности.

14.2. Требования безопасности перед началом работы

14.3. Требования безопасности во время работы

14.4. Требования безопасности в аварийных ситуациях

14.5. Требования безопасности по окончанию работы

14.6. Ответственность

15. Экономическая часть.

Заключение.

Литература.

Приложение.

Введение

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

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

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

Параллелизм можно вводить на разных уровнях. На уровне команд, например, можно использовать конвейеры и суперскалярную архитектуру, что позволяет увеличивать производительность примерно в 10 раз. Чтобы увеличить производительность в 100,1000 или 1 000 000 раз, нужно продублировать процессор или, по крайней мере, какие-либо его части и заставить все эти процессоры работать вместе.

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

1. Вопросы разработки компьютеров параллельного действия

Когда мы сталкиваемся с новой компьютерной системой параллельного действия, возникает три вопроса:

1. Каков тип, размер и количество процессорных элементов?

2. Каков тип, размер и количество модулей памяти?

3. Как взаимодействуют элементы памяти и процессорные элементы?

Рассмотрим каждый из этих пунктов. Процессорные элементы могут быть самых различных типов -- от минимальных АЛУ до полных центральных процессоров, а по размеру один элемент может быть от небольшой части микросхемы до кубического метра электроники. Очевидно, что если процессорный элемент представляет собой часть микросхемы, то можно поместить в компьютер огромное число таких элементов (например, миллион). Если процессорный элемент представляет собой целый компьютер со своей памятью и устройствами ввода-вывода, цифры будут меньше, хотя были сконструированы такие системы даже с 10 000 процессорами. Сейчас компьютеры параллельного действия конструируются из серийно выпускаемых частей. Разработка компьютеров параллельного действия часто зависит от того, какие функции выполняют эти части и каковы ограничения.

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

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

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

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

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

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

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

2. Информационные модели

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

2.1 Мультипроцессоры

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

Мультипроцессорная модель распространяется на программное обеспечение. Все процессы, работающие вместе на мультипроцессоре, могут разделять одно виртуальное адресное пространство, отображенное в общую память. Любой процесс может считывать слово из памяти или записывать слово в память с помощью команд LOAD и STORE. Больше ничего не требуется. Два процесса могут обмениваться информацией, если один из них будет просто записывать данные в память, а другой "будет считывать эти данные.

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

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

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

В качестве примеров мультипроцессоров можно назвать Sun Enterprise 10000, Sequent NUMA-Q, SGI Origin 2000 и HP/Convex Exemplar.

2.2 Мультикомпьютеры

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

Поскольку процессоры в мультикомпьютере не могут взаимодействовать друг с другом просто путем чтения из общей памяти и записи в общую память, здесь необходим другой механизм взаимодействия. Они посылают друг другу сообщения, используя сеть межсоединений. В качестве примеров мультикомпьютеров можно назвать IBM SP/2, Intel/Sandia Option Red и Wisconsin COW.

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

При отсутствии памяти совместного использования в аппаратном обеспечении предполагается определенная структура программного обеспечения. В мультикомпьютере невозможно иметь одно виртуальное адресное пространство, из которого все процессы могут считывать информацию и в которое все процессы могут записывать информацию просто путем выполнения команд LOAD и STORE. Например, если процессор 0 (в верхнем левом углу) на рис. 1, б обнаруживает, что часть его объекта попадает в другую секцию, относящуюся к процессору 1, он может продолжать считывать информацию из памяти, чтобы получить хвост самолета. Однако если процессор 0 на рис.2, б обнаруживает это, он не может просто считать информацию из памяти процессора 1. Для получения необходимых данных ему нужно сделать что-то другое.

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

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

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

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

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

Второй подход -- использовать аппаратное обеспечение мультикомпьютера и операционную систему, которая моделирует разделенную память, обеспечивая единое виртуальное адресное пространство, разбитое на страницы. При таком подходе, который называется DSM (Distributed Shared Memory.-- распределенная совместно используемая память), каждая страница расположена в одном из блоков памяти (см. рис.2, а). Каждая машина содержит свою собственную виртуальную память и собственные таблицы страниц. Если процессор совершает команду LOAD или STORE над страницей, которой у него нет, происходит прерывание операционной системы. Затем операционная система находит нужную страницу и требует, чтобы процессор, который обладает нужной страницей, преобразовал ее в исходную форму и послал по сети межсоединений. Когда страница достигает пункта назначения, она отображается в память, и выполнение прерванной команды возобновляется. По существу, операционная система просто вызывает недостающие страницы не с диска, а из памяти. Третий подход -- реализовать общую разделенную память на уровне программного обеспечения. При таком подходе абстракцию разделенной памяти создает язык программирования, и эта абстракция реализуется компилятором. Например, модель Linda основана на абстракции разделенного пространства кортежей (записей данных, содержащих наборы полей). Процессы любой машины могут взять кортеж из общего пространства или отправить его в общее пространство. Поскольку доступ к этому пространству полностью контролируется программным обеспечением (системой Linda), никакого специального аппаратного обеспечения или специальной операционной системы не требуется.

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

Рис. 3. Уровни, на которых можно реализовать память совместного использования: аппаратное обеспечение (а); операционная система (б); программное обеспечение (в)

2.3 Сети межсоединений

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

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

Сети межсоединений могут состоять максимум из пяти компонентов:

1. Центральные процессоры.

2. Модули памяти.

3. Интерфейсы.

4. Каналы связи.

5. Коммутаторы.

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

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

Коммутаторы -- это устройства с несколькими входными и несколькими выходными портами. Когда на входной порт приходит пакет, некоторые биты в этом пакете используются для выбора выходного порта, в который посылается пакет. Размер пакета может составлять 2 или 4 байта, но может быть и значительно больше (например, 8 Кбайт). Сети межсоединений можно сравнить с улицами города. Улицы похожи на каналы связи. Каждая улица может быть с односторонним и двусторонним движением, она характеризуется определенной «скоростью передачи данных» (имеется в виду ограничение скорости движения) и имеет определенную ширину (число рядов). Перекрестки похожи на коммутаторы. На каждом перекрестке прибывающий пакет (пешеход или машина) выбирает, в какой выходной порт (улицу) поступить дальше в зависимости от того, каков конечный пункт назначения.

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

2.3.1.Топология

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

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

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

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

Рис. 4. Различные топологии. Жирные точки соответствуют коммутаторам. Процессоры и модули памяти не показаны: звезда (а); полное межсоединение (full interconnect) (б); дерево (в); кольцо (г); решетка (д); двойной тор (е); куб (ж); гиперкуб (з)

Если есть две оси и пакет может направиться направо или налево либо вверх или вниз, то такая сеть двумерна и т. д.

На рис. 4 показано несколько топологий. Здесь изображены только каналы связи (это линии) и коммутаторы (это точки). Модули памяти и процессоры (они на рисунке не показаны) подсоединяются к коммутаторам через интерфейсы. На рис.4, а изображена нульмерная конфигурация звезда, где процессоры и модули памяти прикрепляются к внешним узлам, а переключение совершает центральный узел. Такая схема очень проста, но в большой системе центральный коммутатор будет главным критическим параметром, который ограничивает производительность системы. И с точки зрения отказоустойчивости это очень неудачная разработка, поскольку одна ошибка в центральном коммутаторе может разрушить всю систему.

На рис.4, б изображена другая нульмерная топология -- полное межсоединение (full interconnect). Здесь каждый узел непосредственно связан с каждым имеющимся узлом. В такой разработке пропускная способность между двумя секциями максимальна, диаметр минимален, а отказоустойчивость очень высока (даже при утрате шести каналов связи система все равно будет полностью взаимосвязана). Однако для к узлов требуется к(к-1)/2 каналов, а это совершенно неприемлемо для больших значений к.

На рис.4, в изображена третья нульмерная топология -- дерево. Здесь основная проблема состоит в том, что пропускная способность между секциями равна пропускной способности каналов. Обычно у верхушки дерева наблюдается очень большой поток обмена информации, поэтому верхние узлы становятся препятствием для повышения производительности. Можно разрешить эту проблему, увеличив пропускную способность верхних каналов. Например, самые нижние каналы будут иметь пропускную способность Ь, следующий уровень -- пропускную способность 2Ь, а каждый канал верхнего уровня -- пропускную способность 4Ь. Такая схема называется толстым деревом (fat tree). Она применялась в коммерческих мультикомпьютерах Thinking Machines' CM-5.

Кольцо (рис.4, г) -- это одномерная топология, поскольку каждый отправленный пакет может пойти направо или налево.

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

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

Куб (рис.4, ж) -- это правильная трехмерная топология. На рисунке изображен куб 2x2x2, но в общем случае он может быть kxkxk. На рис.4, з показан четырехмерный куб, полученный из двух трехмерных кубов, которые связаны между собой. Можно сделать пятимерный куб, соединив вместе 4 четырехмерных куба. Чтобы получить 6 измерений, нужно продублировать блок из 4 кубов и соединить соответствующие узлы и т. д.; n-мерный куб называется гиперкубом. Эта топология используется во многих компьютерах параллельного действия, поскольку ее диаметр находится в линейной зависимости от размерности. Другими словами, диаметр -- это логарифм по основанию 2 от числа узлов, поэтому 10-мерный гиперкуб имеет 1024 узла, но диаметр равен всего 10, что дает очень незначительные задержки при передаче данных. Отметим, что решетка 32x32, которая также содержит 1024 узла, имеет диаметр 62, что более чем в шесть раз превышает диаметр гиперкуба. Однако чем меньше диаметр гиперкуба, тем больше разветвление и число каналов (и следовательно, тем выше стоимость). Тем не менее в системах с высокой производительностью чаще всего используется именно гиперкуб.

2.4 Коммутация

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

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

Рис. 5. Сеть межсоединений в форме квадратной решетки с четырьмя коммутаторами. Здесь показаны только два процессора



Рис. 6. Коммутация с промежуточным хранением

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

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

Вторая стратегия -- коммутация с промежуточным хранением. Здесь не требуется предварительного резервирования. Из исходного пункта посылается целый пакет к первому коммутатору, где он хранится целиком. На рис. 6, а исходным пунктом является процессор 1, а весь пакет, который направляется в процессор 2, сначала сохраняется внутри коммутатора А. Затем этот пакет перемещается в коммутатор С, как показано на рис. 6, б. Затем весь пакет целиком перемещается в коммутатор D (рис. 6, в). Наконец, пакет доходит до пункта назначения -- до процессора 2. Отметим, что никакого предварительного резервирования ресурсов не требуется.

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

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

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

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

Хотя метод коммутации с промежуточным хранением гибок и эффективен, здесь возникает проблема возрастающей задержки при передаче данных по сети межсоединений. Предположим, что время, необходимое для перемещения пакета по одному транзитному участку на рис. 6, занимает Т не. Чтобы переместить пакет из процессора 1 в процессор 2, нужно скопировать его 4 раза (в А, в С, в D и в процессор 2), и следующее копирование не может начаться, пока не закончится предыдущее, поэтому задержка по сети составляет 4Т. Чтобы выйти из этой ситуации, нужно разработать гибридную сеть межсоединений, объединяющую в себе коммутацию каналов и коммутацию пакетов. Например, каждый пакет можно разделить на части. Как только первая часть поступила в коммутатор, ее можно сразу направить в следующий коммутатор, даже если оставшиеся части пакета еще не прибыли в этот коммутатор.

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

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

2.5 Алгоритмы выбора маршрута

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

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

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

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

Рис. 7. Тупиковая ситуация в сети с коммутацией каналов

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

Популярным алгоритмом маршрутизации, который применяется для прямоугольных решеток с любым числом измерений и в котором никогда не возникает тупиковых ситуаций, является пространственная маршрутизация. В соответствии с этим алгоритмом пакет сначала перемещается вдоль оси х до нужной координаты, а затем вдоль оси у до нужной координаты и т. д. (в зависимости от количества измерений). Например, чтобы перейти из (3, 7, 5) в (6, 9,8), пакет сначала должен переместиться из точки х=3 в точку х=6 через (4, 7, 5), (5, 7, 5) и (6, 7, 5). Затем он должен переместиться по оси у через (6, 8, 5) и (6, 9, 5). Наконец, он должен переместиться по оси z в (6, 9, 6), (6, 9, 7) и (6, 9, 8). Такой алгоритм предотвращает тупиковые ситуации.

3. Производительность компьютеров параллельного действия

Цель создания компьютера параллельного действия -- сделать так, чтобы он работал быстрее, чем однопроцессорная машина. Если эта цель не достигнута, то никакого смысла в построении компьютера параллельного действия нет. Более того, эта цель должна быть достигнута при наименьших затратах. Машина, которая работает в два раза быстрее, чем однопроцессорная, но стоит в 50 раз дороже последней, не будет пользоваться особым спросом. В этом разделе мы рассмотрим некоторые вопросы производительности, связанные с созданием архитектур параллельных компьютеров.

4. Метрика аппаратного обеспечения

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

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