Файл: Мультипроцессоры (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МУЛЬТИ ПРОФЕССОРОВ И ИХ ИСПОЛЬЗОВАНИЯ).pdf

Таблица 1 – Свод данных

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

Рис. 11 График роста коэффициента ускорения для 16-точечного БПФ

Модель может быть аппроксимирована на любую размерность алгоритма БПФ. Общая формула для подсчёта времени выполнения алгоритма приводится ниже.

Первое слагаемое - это соотношение для времени выполнения вычислений, которое учитывает время счёта базовой операции и число базовых операций в алгоритме равное .

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

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

В качестве демонстрационного примера мы выбираем Результаты вычислений коэффициента ускорения для алгоритма БПФ на 1024 отсчёта. Граф алгоритма при данной размерности состоит из 10 слоёв по 512 бабочек в каждом слое, всего в графе содержится 5120 базовых процедур. Максимальный потенциал распараллеливания данного алгоритма составляет 512 последовательных линий из 10 базовых процедур каждая. Результаты вычислений для = 1024 при = 1 и = 5 приведены в Таблице 2

Таблица 2 – Сводная таблица

График роста коэффициента ускорения приводится на рис. 12

Рис. 12 График роста коэффициента ускорения для БПФ на 1024 точки

Данная модель позволяет исследовать поведение всех обозначенных компонентов, формирующих баланс временных затрат и их зависимость от числа процессоров. На рис.13 приводится динамика времени выполнения алгоритма по всем слагаемым: времени счёта, времени пересылки данных и времени протоколов доступа к обменной среде.

Рис. 13 Динамика времени выполнения алгоритма по основным слагаемым

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

Рис. 14 Начальный фрагмент динамики времени выполнения алгоритма по основным составляющим

Подведём итог - алгоритм имеет потенциал параллелизма, позволяющий распределить на 512 процессорах 512 последовательных линий, каждая из которых представляет собой последовательность из 10 базовых процедур. Следовательно, в идеальном случае можно получить коэффициент ускорения близкий к значению 512. Полученное на модели значение ускорения 6,81 , заметно отличается от ожидаемых 512. Модель позволяет обнаружить в явном виде причины такого расхождения. Время счёта устойчиво падает с ростом числа процессоров , но его вклад в рост ускорения подавляется двумя слагаемыми, которые растут с ростом . Это временные затраты на обмен данными и на выполнение протокольных событий. Обе растущие компоненты порождаются работой обменной среды и событиями, обслуживающими параллелизм.

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

Далее мы рассмотрим улучшенный вариант применения общей шины. Допустим, что многоядерная структура формируется путём наращивания кластеров, состоящих из 16 процессоров, объединённых общей шиной. Это позволяет распараллелить обменные операции, локализованные в пределах кластера. При этом обмены между кластерами осуществляются по общей шине верхнего уровня, которая объединяет кластеры. Для модельных подсчётов сохраним ранее принятые параметры. Рассматривается граф алгоритма БПФ, = 1024 при параметрах шины = 1 и = 5, что означает передачу одного машинного слова за один такт и осуществление протокола доступа к шине за 5 тактов. Обмены между процессорами внутри кластера осуществляются одним проходом по шине кластера. Доступ процессора к обмену между кластерами требуют двух проходов по шинам. Сначала проход по кластерной шине для выхода на межкластерную шину и далее проход по этой шине в смежный кластер.

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

Таблица 3

На рис. 15 изображены кривые роста ускорения. Красным цветом отмечено ускорение в структуре с одной шиной, синим в системе с множеством шин.

Рис. 15 Кривые роста ускорения. Красная линия для одной шины, синяя для множества шин

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

Рис. 16 Динамика роста временных затрат по основным компонентам процесса

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

Данные модельного эксперимента показывают, что структура с множеством шин может дать определённое улучшение на относительно небольших значениях параллелизма, в пределах нескольких десятков. Далее по мере роста числа процессоров в область сотен экземпляров результаты многошинной структуры сравниваются с результатами одной шины. Таким образом, мы можем объяснить заметное улучшение результатов, полученных в [19] . В последнем эксперименте вычисления проводились на более совершенной установке IBM SP2 с более скоростной многошинной обменной средой.

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

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

ГЛАВА 2 ПРАКТИЧЕСКИЕ АСПЕКТЫ ПРИМЕНЕНИЯ МУЛЬТИПРОЦЕССОРОВ

2.1 Обзор работ по коммутационным средам

На текущий момент среди обменных сред (сетей интерконнекта) выделяются 4 основных класса, основанных, преимущественно, на топологии сети: сеть с коллективно используемой средой, сеть с прямым доступом, сеть с косвенным доступом и гибридная сеть. В сетях с коллективно используемой средой обменная среда делится между всеми коммутирующими устройствами. В таких сетях одновременно только одно ядро может использовать сеть. Сеть обычно является пассивной, поскольку она не генерирует сообщения. По причине ограниченной пропускной способности такие сети не могут быть использованы в суперкомпьютерах. Ярким представителем такой сети является сеть с топологией толстое дерево (Fat Tree).

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

Важным параметром применимости сетей для суперкомпьютеров является их масштабируемость. Каждое ядро представляет собой программируемый компьютер с собственным процессором, локальной памятью и прочими поддерживающими устройствами. Такие ядра могут иметь различные функциональные возможности. Например, подмножество ядер может содержать векторные процессоры, графические процессоры и процессоры ввода/вывода. Общим компонентом ядер является роутер, который поддерживает передачу сообщения от ядра к ядру. По этой причине сети с прямым доступом так же можно назвать сетями, основанными на роутерах. Каждый роутер имеет непосредственное соединение с соседними роутерами. Обычно, роутеры соединены парой ненаправленных каналов в разных направлениях. Хотя, функции роутера могут быть представлены локальным процессором, выделенные роутеры используются в мультикомпьютерах с высокой производительностью, позволяя перекрывать вычисления и коммуникацию каждого ядра. С увеличением числа ядер в системе так же растет общая ширина коммуникации, пропускная способность памяти и возможности обработки системы. Таким образом, сети с прямым доступом являются популярной архитектурой межсоединений для создания крупномасштабных параллельных компьютеров. [21]