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

 

В мультикомпьютере для взаимодействия между процессорами часто используются примитивы 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.4 Коммутация

 

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

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

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

 

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

 

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

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

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

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

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

 

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

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