Файл: Мультипроцессоры (Понятие мультипроцессоров).pdf

Введение

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

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

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

Цель данной курсовой работы провести исследования понятие и принципов функционирования мультипроцессоров и многопроцессорных вычислительных систем.

Объектом данной курсовой работы выступает мультипроцессоры.

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

Для выполнения поставленной цели необходимо выполнить такие задачи:

1. проанализировать понятие мультипроцессоров;
2. рассмотреть различные виды мультипроцессоров;
3. рассмотреть различные архитектуры многопроцессорных вычислительных систем;
4. привести классификацию вычислительных систем;
5. разработать имитационную модель мультипроцессорной вычислительной системы.

Теоретические вопросы данной курсовой работы хорошо рассмотрены как в отечественной, так и зарубежной литературе. В ходе выполнения работы были использованы труды таких авторов: Э. Таненбаум, Ф.Г. Энслоу, Бройдо В. Л, Корнеев В. В.

1 Понятие мультипроцессоров

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

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

1. синхронизация процессов;
2. управление ресурсами;
3. планирование.

Мультипроцессорное аппаратное обеспечение

У всех мультипроцессоров каждый CPU может адресоваться ко всей памяти. Однако по характеру доступа к памяти эти машины делятся на два класса:

1) Мультипроцессоры, у которых каждое слово данных может быть считано с одинаковой скоростью, называются UMA-мультипроцессорами (Uniform Memory Access — однородный доступ к памяти)^[2].

2) В противоположность им NUMA-мультипроцессоры (NonUniform Memory Access неоднородный доступ к памяти) этим свойством не обладают.

Почему существует такое различие, станет ясно позднее. Сначала будут описаны мультипроцессоры UMA, а затем — мультипроцессоры NUMA.^[3]

1.2 Архитектура симметричных мультипроцессоров UMA с общей шиной

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

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

Решение этой проблемы состоит в том, чтобы добавить каждому CPU кэш, как показано на рис. 1(б). Кэш может располагаться внутри микросхемы CPU или рядом с CPU, на процессорной плате. Поскольку большое количество обращений к памяти теперь может быть удовлетворено прямо из кэша, обращений к шине будет существенно меньше, и система сможет поддерживать большее число CPU. Как правило, кэширование выполняется не для отдельных слов, а для блоков по 32 или по 64 байта. При обращении к слову весь блок считывается в кэш CPU, обратившегося к слову.^[5]

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

Рисунок 1 - Три варианта архитектуры мультипроцессоров с общей шиной: без кэша (а); с кэшем (б); с кэшем и собственной памятью (в)

Если в остальных кэшах соответствующие блоки «чистые», то есть модифицированные точные копии блока, находящегося в памяти, тогда они могут просто отбросить свои копии и позволить пишущему CPU получить этот блок из памяти. Если же в каком-либо кэше содержится «грязная» (то есть модифицированная) копия, она должна быть либо записана в память, прежде чем операция записи может быть продолжена, либо передана напрямую пишущему CPU по шине. Существует много протоколов обмена данных между кэшами и памятью.^[7]

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

1.3 Мультипроцессоры UMA с координатными коммутаторами

Даже при оптимальном использовании кэша наличие всего одной общей шины ограничивает число UMA-мультипроцессоров тридцатью двумя или шестьюдесятью четырьмя. Чтобы преодолеть это ограничение, требуется другая схема соединительной сети.^[8] Довольно простая схема соединения n CPU и k модулей памяти представляет собой координатный коммутатор, рис. 2.

На каждом пересечении горизонтальной (входной) и вертикальной (выходной) линий располагается координатный переключатель. Он представляет собой небольшой переключатель, который может быть открыт или закрыт, в зависимости от того, должны быть соединены вертикальная и горизонтальная линии или нет. На рис. 2(а) изображены три одновременно замкнутых переключателя, что позволяет одновременно соединить пары (CPU, блок памяти) (010, 000), (101, 101) и (110, 010).

Рисунок 2 - Координатный коммутатор 8х8 (а); разомкнутый переключатель (б); замкнутый переключатель (е)

Одно из самых замечательных свойств координатного коммутатора заключается в том, что он представляет собой неблокирующую сеть: ни один CPU не получает отказа соединения по причине занятости какого-либо переключателя (при условии, что сам требующийся модуль памяти свободен). При такой схеме не требуется планирования доступа к памяти. Даже если семь любых соединений уже установлены, всегда можно соединить оставшийся CPU с оставшимся модулем памяти.^[9]

Основной недостаток координатного коммутатора состоит в том, что число переключателей растет пропорционально квадрату от числа CPU. При 1000 CPU и 1000 модулях памяти потребуется миллион переключателей. Такой огромный координатный коммутатор просто не реализуем. Тем не менее, для систем среднего размера архитектура координатного коммутатора является применимой.^[10]

1.4 Мультипроцессоры UMA c многоступенчатые коммутаторными сетями

Принципиально другая архитектура мультипроцессоров базируется на простых коммутаторах 2x2, рис. 3(а). У такого коммутатора два входа и два выхода. Сообщения, поступающие по любой из входных линий, могут переключаться на любую выходную линию. Сообщения в рассматриваемом нами мультипроцессоре будут состоять из четырех частей, рис. 3(б):

1. Поле Module (модуль) указывает модуль памяти.
2. Поле Address (адрес) указывает адрес внутри модуля.
3. Поле Opcode (код операции) указывает операцию, то есть READ (чтение) или WRITE (запись).
4. Необязательное поле Value (значение) может содержать операнд, например 32-разрядное слово, которое должно быть записано операцией WRITE.^[11]

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

Рисунок 3 - Коммутатор 2x2 (а); формат сообщения (б)

С помощью данного коммутатора 2x2 можно построить самые различные многоступенчатые коммутаторные сети. Один из вариантов таких сетей представляет собой сеть омега, показанная на рис. 4. Это сеть без излишеств, так сказать, экономический класс сетей.^[12] В данном примере она соединяет восемь CPU с восемью модулями памяти всего 12 коммутаторами. В более общем случае для n CPU и n модулей памяти потребуется log₂ n ступеней с n/2 коммутаторами в каждой ступени. Таким образом, в целом для сети омега потребуется «n/2 log₂ n» коммутаторов, что значительно меньше, чем n² коммутаторов, особенно для больших n .

Рисунок 4 - Коммутирующая сеть омега

Схему соединений в сети омега часто называют идеальным тасованием, поскольку на каждой ступени перемешивание сигналов напоминает тасование колоды карт. Чтобы понять принципы работы сети омега, предположим, что CPU 011 нужно прочитать слово из модуля памяти 110. CPU посылает коммутатору 1D сообщение READ|module=110. Старший (то есть самый левый) бит этого поля коммутатор использует для выбора маршрута, 0 означает выбор верхнего выхода, а 1 — нижнего. Поскольку бит равен 1, сообщение направляется по нижнему выходу коммутатору 2D.^[13]

Все коммутаторы второй ступени, включая коммутатор 2D, используют для маршрутизации второй бит. Он также равен 1, поэтому сообщение передается по нижнему выходу коммутатору 3D. Он проверяет младший бит, и поскольку бит равен 0, то сообщение передается по верхнему выходу и попадает, как и требовалось, к модулю памяти 110. Путь этого сообщения помечен символом a .

По мере продвижения по коммутирующей сети, левые биты номера модуля оказываются более не нужными. Они могут использоваться для запоминания входных линий, чтобы ответ мог найти обратный путь. Для пути a , входные линии имеют номера 0 (верхний вход ID), 1 (нижний вход 2D) и 1 (нижний вход 3D). Ответ направляется по адресу 011, обработка которого производится справа налево.

В то же самое время CPU 001 хочет записать слово в модуль памяти 001. Этот процесс происходит аналогично описанному выше. Сообщение направляется по верхнему, верхнему и нижнему выходу (путь отмечен символом b). Когда сообщение доходит до модуля памяти, поле Module=001, то есть путь, пройденный сообщением. Поскольку эти два запроса не используют общих коммутаторов, линий и модулей памяти, они могут выполняться параллельно.

Теперь посмотрим, что произойдет, если CPU 000 одновременно с этим захочет обратиться к модулю памяти 000. Его запрос войдет в конфликт с запросом CPU 001 на коммутаторе 3А. Одному из них придется подождать. В отличие от координатного коммутатора, сеть омега представляет собой блокирующую сеть - не все наборы запросов могут быть обработаны одновременно. Возникают конфликты из-за использования линии или коммутатора как между запросами к памяти, так и между ответами памяти на эти запросы.^[14]

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