ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2021
Просмотров: 357
Скачиваний: 1
Тема 7. Понятие о многомашинных и многопроцессорных вычислительных системах (ВС)
Лекция 15. Организация многомашинных и многопроцессорных ВС
1. Классификация параллельных ВС
2. Вычислительные системы с систолической структурой.
3. Симметричные мультипроцессорные структуры.
4. Кластерные ВС.
1. Классификация параллельных ВС
Среди всех рассматриваемых систем классификации ВС наибольшее признание получила классификация, предложенная в 1966 году М. Флинном. В ее основу положено понятие потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. В зависимости от количества потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, SIMD, MIMD.
SISD (Single Instruction Stream/Single Data Stream) – одиночный поток команд и одиночный поток данных (рис. 1).
Рис. 1. SISD-архитектура
Представителями этого класса являются, прежде всего, классические фон-неймановские ВМ, где имеется только один поток команд, команды обрабатываются последовательно и каждая команда инициирует одну операцию с одним потоком данных. То, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка, не имеет значения, поэтому в класс SISD одновременно попадают как ВМ со скалярными функциональными устройствами, так и с конвейерными.
MISD (Multiple Instruction Stream/Single Data Stream) – множественный поток команд и одиночный поток данных (рис. 2).
Из определения следует, что в архитектуре ВС присутствует множество процессоров, обрабатывающих один и тот же поток данных. Примером могла бы служить ВС, на процессоры которой подается искаженный сигнал, а каждый из процессоров обрабатывает этот сигнал с помощью своего алгоритма фильтрации.
Рис. 2. MISD-архитепктура
Тем не менее ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не сумели представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят к данному классу конвейерные системы, однако это не нашло окончательного признания. Отсюда принято считать, что пока данный класс пуст.
SIMD (Single Instruction Stream/Multiple Data Stream) — одиночный поток команд и множественный поток данных (рис. 3).
Рис. 3. SIMD-архитектура
ВМ данной архитектуры позволяют выполнять одну арифметическую операцию сразу над многими данными – элементами вектора. Бесспорными представителями класса SIMD считаются матрицы процессоров, где единое управляющее устройство контролирует множество процессорных элементов. Все процессорные элементы получают от устройства управления одинаковую команду и выполняют ее над своими локальными данными. В принципе в этот класс можно включить и векторно-конвейерные ВС, если каждый элемент вектора рассматривать как отдельный элемент потока данных.
MIMD (Multiple Instruction Stream/Multiple Data Stream) – множественный поток команд и множественный поток данных (рис. 4).
Класс предполагает наличие в вычислительной системе множества устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Класс MIMD чрезвычайно широк, поскольку включает в себя всевозможные мультипроцессорные системы. Кроме того, приобщение к классу MIMD зависит от трактовки. Так, ранее упоминавшиеся векторно-конвейерные ВС можно вполне отнести и к классу MIMD, если конвейерную обработку рассматривать как выполнение множества команд (операций ступеней конвейера) над множественным скалярным потоком.
Рис. 4 MIMD-архитектура
Схема классификации Флинна вплоть до настоящего времени является наиболее распространенной при первоначальной оценке той или иной ВС, поскольку позволяет сразу оценить базовый принцип работы системы, чего часто бывает достаточно. Однако у классификации Флинна имеются и очевидные недостатки, например неспособность однозначно отнести некоторые архитектуры к тому или иному классу. Другая слабость – это чрезмерная насыщенность класса MIMD. Все это породило множественные попытки либо модифицировать классификацию Флинна, либо предложить иную систему классификации.
2. Вычислительные системы с систолической структурой
В фон-неймановских машинах данные, считанные из памяти, однократно обрабатываются в процессорном элементе, после чего снова возвращаются в память (рис. 5, а). Авторы идеи систолической матрицы Кунг и Лейзерсон предложили организовать вычисления так, чтобы данные на своем пути от считывания из памяти до возвращения обратно пропускались через как можно большее число ПЭ (рис. 5, б).
Рис. 5 Организация фон-неймановской ВМ и ЭВМ
с систолической структурой
Систолические структуры эффективны при выполнении матричных вычислений, обработке сигналов, сортировке данных и т. д. В качестве примера авторами идеи был предложен линейным массив для алгоритма матричного умножения, показанный на рис. 6.
Рис 6. Процесс векторного умножения матриц (n=4)
В основе схемы лежит ритмическое прохождение двух потоков данных Х и У, навстречу друг другу. Последовательные элементы каждого потока разделены одним тактовым периодом, чтобы любой из них мог встретиться с любым элементом встречного потока. Если бы они следовали в каждом периоде, то элемент Хi никогда бы не встретился с элементами Уi+1,Уi+3, … Вычисления выполняются параллельно в процессорных элементах, каждый из которых реализует один шаг в операции вычисления скалярного произведения (IPS, Inner Product Step) и носит название IPS-элемента (рис. 7).
Рис. 7. Функциональная схема IPS-элемента
Значение Увх, поступающее на вход ПЭ, суммируется с произведением входных значений Хвх и авх. Результат выходит из ПЭ как Увых. Значение Хвх, кроме того, для возможного последующего использования остальной частью массива транслируется через ПЭ без изменений и покидает его в виде Хвых.
Таким образом, систолическая структура – это однородная вычислительная среда из процессорных элементов, совмещающая в себе свойства конвейерной и матричной обработки и обладающая следующими особенностями:
вычислительный процесс в систолических структурах представляет собой непрерывную и регулярную передачу данных от одного ПЭ к другому без запоминания промежуточных результатов вычисления;
каждый элемент входных данных выбирается из памяти однократно и используется столько раз, сколько необходимо по алгоритму, ввод данных осуществляется в крайние ПЭ матрицы;
образующие систолическую структуру ПЭ однотипны и каждый из них может быть менее универсальным, чем процессоры обычных многопроцессорных систем;
потоки данных и управляющих сигналов обладают регулярностью, что позволяет объединять ПЭ локальными связями минимальной длины;
алгоритмы функционирования позволяют совместить параллелизм с конвейерной обработкой данных;
производительность матрицы можно улучшить за счет добавления в нее определенное число ПЭ, причем коэффициент повышения производительности при этом линеен.
В настоящее время достигнута производительность систолических процессоров порядка 1000 млрд операций/с.
Классификация систолических структур
Анализ различных типов систолических структур и тенденций их развития позволяет классифицировать эти структуры по нескольким признакам.
По степени гибкости систолические структуры могут быть сгруппированы на:
специализированные (ориентированы на выполнение определенного алгоритма). Эта ориентация отражается не только в конкретной геометрии систолической структуры, статичности связей между ПЭ и числе ПЭ, но и в выборе типа операции, выполняемой всеми ПЭ;
алгоритмически ориентированные (обладают возможностью программирования либо конфигурации связей в систолической матрице, либо самих ПЭ). Возможность программирования позволяет выполнять на таких структурах некоторое множество алгоритмов, сводимых к однотипным операциям над векторами, матрицами и другими числовыми множествами;
программируемые (имеется возможность программирования как самих ПЭ, так и конфигурации связей между ними). При этом ПЭ могут обладать локальной памятью программ, и хотя все они имеют одну и ту же организацию, в один и тот же момент времени допускается выполнение различных операций из некоторого набора. Команды или управляющие слова, хранящиеся в памяти программ таких ПЭ, могут изменять и направление передачи операндов.
В одноразрядных матрицах ПЭ в каждый момент времени выполняет операцию над одним двоичным разрядом; а в многоразрядных – над словами фиксированной длины.
По характеру локально-пространственных связей систолические структуры бывают:
одномерные;
двухмерные;
трехмерные.
Выбор структуры зависит от вида обрабатываемой информации. Одномерные схемы применяются при обработке векторов, двухмерные – матриц, трехмерные – множеств иного типа.
Топология систолических структур
В настоящее время разработаны систолические матрицы с различной геометрией связей: линейные, квадратные, гексагональные, трехмерные и др. Перечисленные конфигурации систолических матриц приведены на рис. 8.
Рис. 8. Конфигурация систолических матриц
Каждая конфигурация матрицы наиболее приспособлена для выполнения определенных функций, например линейная матрица оптимальна для реализации фильтров в реальном масштабе времени; гексагональная – для выполнения операций обращения матриц, а также действий над матрицами специального вида; трехмерная – для нахождения значений нелинейных дифференциальных уравнений в частных производных или для обработки сигналов антенной решетки.
Матрицы ПЭ обычно реализуются на основе сверхбольших (СБИС) интегральных схем, возникающие при этом ограничения привели к тому, что наиболее распространены матрицы с одним, двумя и тремя трактами данных и одинаковым либо противоположным направлением передачи, обозначаемые как ULA, BLA и TLA соответственно.
ULA (Unidirectional Linear Array) – это однонаправленный линейный процессорный массив, где потоки данных перемещаются в одном направлении. ПЭ в массиве могут быть связаны одним, двумя или тремя трактами (рис. 9).
Рис. 9. Поток данных при векторном умножении матриц в ULA (n=4)
При реализации алгоритма векторного произведения матриц один из потоков данных перемещается вправо, в то время как второй резидентно расположен в массиве. Используемый ПЭ представляет собой модифицированный IPS элемент, поскольку имеется только один тракт данных, а элементы второго потока хранятся в ПЭ массива.
BLA (Bidirectional Linear Array) – это двунаправленный линейный процессорный массив, в котором два потока данных движутся навстречу друг другу (рис. 10).
Рис. 10. Поток данных при векторном умножении матриц в BLA (n=4)
BLA, где один из потоков является выходным, называется регулярным.
На рисунке показана реализация рассмотренной ранее операции с применением BLA. В версии ULA процессоры используются более эффективно, поскольку в них элементы потока следуют в каждом такте, а не через такт, как в BLA.
TLA (Three-path communication Linear Array) – линейный процессорный массив с тремя коммуникационными трактами, в котором по разным направлениям перемещаются три потока данных (рис. 11).
TLA часто называют сдвоенным конвейером, поскольку он может быть разделен на два линейных конвейера типа BLA. Соответственно, TLA можно получить объединением двух BLA с одним общим потоком данных.
Рис. 11. Поток данных в TLA
Структура процессорных элементов
Тип ПЭ выбирается в соответствии с назначением систолической матрицы и структурой пространственных связей. Наиболее распространены процессорные элементы, ориентированные на умножение с накоплением.
На рис. 12 показаны ПЭ для двух типов матриц: прямоугольной и гексагональной.
Рис. 12. Структура процессорного элемента
В обоих случаях на вход ПЭ подаются два операнда Авх, Ввх, а выходят операнды Авых, Ввых и частичная сумма Свых. На n-м шаге работы систолической системы ПЭ выполняет операцию
на основе операндов, полученных на (n - 1)-м шаге, при этом операнды на входе и выходе ПЭ одинаковы:
Частичная сумма поступает на вход ПЭ либо с данного процессорного элемента (штриховая линия), либо с соседнего ПЭ матрицы.
3. Симметричные мультипроцессорные структуры
Симметричные мультипроцессорные системы
До сравнительно недавнего времени практически все однопользовательские персональные ВМ и рабочие станции содержали по одному микропроцессору общего назначения. По мере возрастания требований к производительности и снижения стоимости микропроцессоров поставщики вычислительных средств как альтернативу однопроцессорным ВМ стали предлагать симметричные мультипроцессорные вычислительные системы, так называемые SMP-системы (SMP, Symmetric Multiprocessor). Это понятие относится как к архитектуре ВС, так и к поведению операционной системы, отражающему данную архитектурную организацию. SMP можно определить как вычислительную систему, обладающую следующими характеристиками:
имеются два или более процессоров сопоставимой производительности;
процессоры совместно используют основную память и работают в едином виртуальном и физическом адресном пространстве;
все процессоры связаны между собой посредством шины или по иной схеме, так что время доступа к памяти любого из них одинаково;
все процессоры разделяют доступ к устройствам ввода/вывода либо через одни и те же каналы, либо через разные каналы, обеспечивающие доступ к одному и тому же внешнему устройству;
все процессоры способны выполнять одинаковые функции (этим объясняется термин «симметричные»);
любой из процессоров может обслуживать внешние прерывания;
вычислительная система управляется интегрированной операционной системой, которая организует и координирует взаимодействие между процессором и программами на уровне заданий, задач, файлов и элементов данных.
Хотя технически SMP-системы симметричны, в их работе присутствует небольшой фактор перекоса, который вносит программное обеспечение. На время загрузки системы один из процессоров получает статус ведущего (master). Это не означает, что позже, во время работы какие-то процессоры будут ведомыми – все они в SMP-системе равноправны. Термин «ведущий» вводится только затем, чтобы указать, какой из процессоров по умолчанию будет руководить первоначальной загрузкой ВС.
Операционная система планирует процессы сразу по всем процессорам, скрывая при этом от пользователя многопроцессорный характер SMP-архитектуры.