ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6691
Скачиваний: 8
6 2 8 Глава 8. Архитектуры компьютеров параллельного действия
Рассмотрим самую простую модель планирования. Должно быть известно,
сколько процессоров нужно для каждой работы (задачи). Тогда задачи выстра-
иваются в порядке FIFO («первым вошел — первым вышел») (рис. 8.31,
а).
Когда
первая задача начала выполняться, происходит проверка, есть ли достаточное ко-
личество процессоров для выполнения задачи, следующей по очереди. Если да, то
она тоже начинает выполняться и т. д. Если нет, то система ждет, пока не появится
достаточное количество процессоров. В нашем примере система COW содержит
8 процессоров, но она вполне могла бы содержать 128 процессоров, расположен-
ных в блоках по 16 процессоров (получилось бы 8 групп процессоров) или в какой-
нибудь другой комбинации.
Группа процессоров
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
-
-
Врем
я
I I I
\
-
Ipy
0 | 1
ina
2
1
процесс
3 | 4 | 5
эро
6
в
7
2
:
4
I
7
5
5
8
9
-
-
-
-
1
1
1 1 1
1
4
3
5
2
6
8
Г
-
-
-
-
I
I I
I
I I I
I
0
руппа
1 I 2
1
проце
3 | 4
ссс
5
4
3
6
8
9
>ров
6 | 7
7
5
2
Рис. 8 . 3 1
. Планирование работы в системе COW: FIFO («первым вошел — первым вышел») (а);
без блокировки начала очереди (б); заполнение прямоугольника «процессоры-время» (в).
Серым цветом показаны свободные процессоры
В глубже разработанном алгоритме задачи, которые не соответствуют количе-
ству имеющихся в наличии процессоров, пропускаются и берется первая задача,
для которой процессоров достаточно. Всякий раз, когда завершается выполнение
задачи, очередь из оставшихся задач проверяется в порядке «первым вошел — пер-
вым вышел». Результат применения этого алгоритма изображен на рис. 8.31,
б.
Еще более сложный алгоритм требует, чтобы было известно, сколько процессо-
ров нужно для каждой задачи и сколько минут займет ее выполнение. Располагая
такой информацией, планировщик заданий может попытаться заполнить прямо-
угольник «процессоры—время». Это особенно эффективно, когда задачи представ-
лены на рассмотрение днем, а выполняться будут ночью. В этом случае планиров-
щик заданий получает всю информацию о задачах заранее и может выполнять их
в оптимальном порядке, как показано на рис. 8.31,
в.
Коммерческие сети межсоединений
В этом разделе мы рассмотрим некоторые технологии связи. Наш первый пример —
система Ethernet. Существует три версии этой системы: classic Ethernet, fast
Мультикомпьютеры с передачей сообщений
629
Ethernet и gigabit Ethernet.
Они
работают со скоростью 10,100 и 1000 Мбит/с (1,25,
12,5 и 125 Мбайт/с)
1
соответственно. Все они совместимы относительно среды,
формата пакетов и протоколов
2
. Отличие только в производительности.
Каждый компьютер в сети Ethernet содержит микросхему Ethernet, обычно на
съемной плате. Изначально провод из платы вводился в середину толстого медно-
го кабеля, это называлось
«зуб вампира».
Позднее появились более тонкие кабели
и Т-образные коннекторы. В любом случае платы Ethernet на всех машинах соеди-
нены электрически, как будто они соединены пайкой. Схема подсоединения трех
машин к сети Ethernet изображена на рис. 8.32,
а.
\
Процессор Процессор Процессор
Пакет, Пакет,
движущийся движущийся
направо налево
1
-|
J
1
1 1
Плата
backplane
1 1
1
-С
i:
i
Канальная
карта Ethernet
Коммутатор
Рис. 8.32. Три компьютера в сети Ethernet (а); коммутатор Ethernet (б)
В соответствии с протоколом Ethernet, если машине нужно послать пакет, сна-
чала она должна проверить, не совершает ли передачу в данный момент какая-
либо другая машина. Если кабель свободен, то машина просто посылает пакет. Если
кабель занят, то машина ждет окончания передачи и только после этого посылает
пакет. Если две машины начинают передачу пакета одновременно, происходит
конфликтная ситуация. Обе машины определяют, что произошла конфликтная
ситуация, останавливают передачу, затем останавливаются на произвольный пе-
риод времени и пробуют снова. Если конфликтная ситуация случается во второй
раз, они снова останавливаются и снова начинают передачу пакетов, удваивая сред-
нее время ожидания с каждой последующей конфликтной ситуацией.
Дело в том, что «зубы вампира» легко ломаются, а определить неполадку в ка-
беле очень трудно. По этой причине появилась новая разработка, в которой кабель
из каждой машины подсоединяется к
сетевому концентратору (хабу).
По суще-
1
Соотнесение автором скоростных показателей упоминаемых технологий, выраженных отношением
скорости передачи бит/с, с отношениями Мбайт/с неправомочно. Ни одна их этих технологий не по-
зволяет передать по сети соответствующее количество байтов за секунду. Даже теоретически возмож-
ная скорость для стандарта Ethernet лежит в интервале 800-850 Кбайт/с. Дело в том, что для переда-
чи информации необходимо использовать служебные коды, к тому же передача осуществляется
кадрами (фреймами) относительно небольшой длины (1500 байтов), после чего сетевой адаптер обя-
зательно должен освободить среду передачи на фиксированный промежуток времени (с тем, чтобы
другие сетевые адаптеры тоже могли воспользоваться средой передачи). —
Примеч. научи, ред.
2
Это высказывание является чересчур смелым. В действительности совместимость имеет очень много
ограничений, и общим у них следует считать метод доступа к среде передачи. —
Примеч. научн. ред.
6 3 0 Глава 8. Архитектуры компьютеров параллельного действия
ству, это то же самое, что и в первой разработке, но производить ремонт здесь про-
ще, поскольку кабели можно отсоединять от сетевого концентратора по очереди,
пока поврежденный кабель не будет изолирован.
Третья разработка —
Ethernet с использованием коммутаторов
— показана на
рис. 8.32,
б.
Здесь сетевой концентратор заменен устройством, содержащим высо-
коскоростную плату backplane, к которой можно подсоединять
канальные карты.
Каждая канальная карта принимает одну или несколько сетей Ethernet, и разные
карты могут воспринимать разные скорости, поэтому classic, fast и gigabit Ethernet
могут быть связаны вместе.
Когда пакет поступает в канальную карту, он временно сохраняется там в буфе-
ре, пока канальная карта не отправит запрос и не получит доступ к плате backplane,
которая функционирует почти как шина. Если пакет был перемещен в канальную
карту, к которой подсоединена целевая машина, он может направляться к этой
машине. Если каждая канальная карта содержит только один Ethernet и этот
Ethernet имеет только одну машину, конфликтных ситуаций больше не возник-
нет, хотя пакет может быть потерян из-за переполнения буфера в канальной карте.
Gigabit Ethernet с использованием коммутаторов с одной машиной на Ethernet и
высокоскоростной платой backplane имеет потенциальную производительность (по
крайней мере, это касается пропускной способности) в 4 раза меньше, чем каналы
связи в машине ТЗЕ, но стоит значительно дешевле.
Но при большом количестве канальных карт обычная плата backplane не смо-
жет справляться с такой нагрузкой, поэтому необходимо подсоединить несколько
машин к каждой сети Ethernet, вследствие чего опять возникнут конфликтные
ситуации. Однако с точки зрения соотношения цены и производительности сеть
на основе gigabit Ethernet с использованием коммутаторов — серьезный конку-
рент на компьютерном рынке.
Следующая технология связи, которую мы рассмотрим, — это
ATM (Asynch-
ronous Transfer Mode — асинхронный режим передачи).
Технология ATM была
разработана международным консорциумом телефонных компаний в качестве за-
мены существующей телефонной системы на новую, полностью цифровую. Ос-
новная идея проекта состояла в том, чтобы каждый телефон и каждый компьютер
в мире связать с помощью безошибочного цифрового битового канала со скорос-
тью передачи данных 155 Мбит/с (позднее 622 Мбит/с). Но осуществить это на
практике оказалось не так просто. Тем не менее многие компании сейчас выпуска-
ют съемные платы для персональных компьютеров со скоростью передачи данных
155 Мбит/с или 622 Мбит/с. Вторая скорость,
ОС-12,
хорошо подходит для муль-
тикомпьютеров.
Провод или стекловолокно, отходящее от платы ATM, переходит в переключа-
тель ATM — устройство, похожее на коммутатор Ethernet. В него тоже поступают
пакеты и сохраняются в буфере в канальных картах, а затем поступают в исходя-
щую канальную карту для передачи в пункт назначения. Однако у Ethernet и ATM
есть существенные различия.
Во-первых, поскольку ATM была разработана для замещения телефонной сис-
темы, она представляет собой сеть с маршрутизацией информации. Перед отправ-
кой пакета в пункт назначения исходная машина должна установить виртуальную
цепь от исходного пункта через один или несколько коммутаторов ATM в конеч-
Мультикомпьютеры с передачей сообщений
631
ный пункт. На рис. 8.33. показаны две виртуальные цепи. В сети Ethernet, напротив,
нет никаких виртуальных цепей. Поскольку установка виртуальной цепи занимает
некоторое количество времени, каждая машина в мультикомпьютере должна уста-
навливать виртуальную цепь со всеми другими машинами при запуске и использо-
вать их при работе. Пакеты, отправленные по виртуальной цепи, всегда будут дос-
тавлены в правильном порядке, но буферы канальных карт могут переполняться,
как и в сети Ethernet с коммутаторами, поэтому доставка не гарантируется.
Процессор
Ячейка
5
6
1 2
I | | |
I 1 I 1
/
Порт
Пакет
Виртуальная цепь
_9^
10
атоpAT
L
h
г
M
i
—i
13
I
I —
14
J
С
L
]
г
3
4
1
--.
Г
1 гг
1 1 1 11
цепь •-{
L
]
Г
_ J Lj.
!
|l
--, i
^ r
1
-
15 1f
i M
| L
"Л
7
Q
1 1 1
4J
i
i
j L
5
11
12
Рис. 8.33. 16 процессоров, связанных четырьмя переключателями ATM.
Пунктиром показаны две виртуальные цепи (канала)
Во-вторых, Ethernet может передавать целые пакеты (до 1500 байтов данных)
одним блоком. В ATM все пакеты разбиваются на ячейки по 53 байта. Пять из
этих байтов — это поля заголовка, которые сообщают, какой виртуальной цепи
принадлежит ячейка, что это за ячейка, каков ее приоритет, а также некоторые
другие сведения. Полезная нагрузка составляет 48 байтов. Разбиение пакетов на
ячейки и их компоновку в конце пути совершает аппаратное обеспечение.
Наш третий пример — сеть Myrinet — съемная плата, которая производится
одной калифорнийской компанией и пользуется популярностью у разработчиков
систем COW [18]. Здесь используется та же модель, что и в Ethernet и ATM, где
каждая съемная плата подсоединяется к коммутатору, а коммутаторы могут со-
единяться в любой топологии. Каналы связи сети Myrinet дуплексные, они пере-
дают информацию со скоростью 1,28 Гбит/с в обоих направлениях. Размер паке-
тов неограничен, а каждый коммутатор представляет собой полное пересечение,
что дает малое время ожидания и высокую пропускную способность.
Myrinet пользуется популярностью у разработчиков систем COW, поскольку
платы в этой сети содержат программируемый процессор и большое ОЗУ. Хотя
6 3 2 Глава 8. Архитектуры компьютеров параллельного действия
Myrinet появилась со своей стандартной операционной системой, многие иссле-
довательские группы уже разработали свои собственные операционные систе-
мы. У них появились дополнительные функции и повысилась производительность
(см., например, [17,107,155]). Из типичных особенностей можно назвать защиту,
управление потоком, надежное широковещание и мультивещание, а также возмож-
ность запускать часть кода прикладной программы на плате.
Связное программное обеспечение для
мультикомпьютеров
Для программирования мультикомпьютера требуется специальное программное
обеспечение (обычно это библиотеки), чтобы обеспечить связь между процессами
и синхронизацию. В этом разделе мы расскажем о таком программном обеспече-
нии. Отметим, что большинство этих программных пакетов работают в системах
МРР и COW.
В системах с передачей сообщений два и более процессов работают независимо
друг от друга. Например, один из процессов может производить какие-либо дан-
ные, а другой или несколько других процессов могут потреблять их. Если у отпра-
вителя есть еще данные, нет никакой гарантии, что получатель (получатели) готов
принять эти данные, поскольку каждый процесс запускает свою программу.
В большинстве систем с передачей сообщений имеется два примитива send и
recei ve, но возможны и другие типы семантики. Ниже даны три основных варианта:
1. Синхронная передача сообщений.
2. Буферная передача сообщений.
3. Неблокируемая передача сообщений.
Синхронная передача сообщений.
Если отправитель выполняет операцию send,
а получатель еще не выполнил операцию recei ve, то отправитель блокируется до
тех пор, пока получатель не выполнит операцию receive, а в это время сообщение
копируется. Когда к отправителю возвращается управление, он уже знает, что со-
общение было отправлено и получено. Этот метод имеет простую семантику и не
требует буферизации. Но у него есть большой недостаток: отправитель блокиру-
ется до тех пор, пока получатель не примет и не подтвердит прием сообщения.
Буферная передача сообщений.
Если сообщение отправляется до того, как
получатель готов его принять, это сообщение временно сохраняется где-либо, на-
пример в почтовом ящике, и хранится там, пока получатель не возьмет его оттуда.
При таком подходе отправитель может продолжать работу после операции send,
даже если получатель в этот момент занят. Поскольку сообщение уже отправлено,
отправитель может снова использовать буфер сообщений сразу же. Такая схема
сокращает время ожидания. Вообще говоря, как только система отправила сооб-
щение, отправитель может продолжать работу. Однако нет никаких гарантий, что
сообщение было получено. Даже при надежной системе коммуникаций получа-
тель мог сломаться еще до получения сообщения.
Неблокируемая передача сообщений.
Отправитель может продолжать рабо-
ту сразу после вызова. Библиотека только сообщает операционной системе, что