Панков С.В. Лекции по системному анализу

Подождите немного. Документ загружается.

Регистр маски вектора: 128 разрядов.

Функциональные устройства

ФУ исполняют свой набор команд и могут работать одновременно друг с другом. Все ФУ

конвейерные и делятся на четыре группы: адресные, скалярные, векторные и для работы с

плавающей точкой.

Адресные ФУ (2): целочисленное сложение/вычитание, целочисленное умножение.

Скалярные ФУ (4): целочисленное сложение/вычитание, логические поразрядные

операции, сдвиг, число единиц/число нулей до первой единицы.

Векторные ФУ (5-7): целочисленное сложение/вычитание, сдвиг, логические поразрядные

операции (1-2), число единиц/число нулей до первой единицы (1-2), умножение битовых

матриц (0-1). Предназначены для выполнения только векторных команд.

ФУ с плавающей точкой (3): сложение/вычитание, умножение, нахождение обратной

величины. Предназначены для выполнения как векторных, так и скалярных команд.

Векторные ФУ и ФУ с плавающей точкой продублированы: векторные команды

разбивают 128 элементов векторных регистров на четные и нечетные, обрабатываемые

одновременно двумя конвейерами (pipe 0, pipe 1). Когда завершается выполнение

очередной пары операций результаты записываются на соответствующие четные и

нечетные позиции выходного регистра. В полностью скалярных операциях,

использующих ФУ с плавающей точкой, работает только один конвейер.

ФУ имеют различное число ступеней конвейера, но каждая ступень срабатывает за один

такт, поэтому при полной загрузке все ФУ могут выдавать результат каждый такт.

Секция управления процессора

Команды выбираются из ОП блоками и заносятся в буфера команд, откуда они затем

выбираются для исполнения. Если необходимой для исполнения команды нет в буферах

команд, то происходит выборка очередного блока.

Команды имеют различный формат и могут занимать 1 пакет (16 разрядов), 2 пакета или 3

пакета (в одном слове 64 разряда, следовательно, в слове содержится 4 пакета).

Максимальная длина программы на CRAY C90 равна 1 Гигаслову.

Параллельное выполнение программ

Конвейеризация выполнения команд

Все основные операции, выполняемые процессором: обращения в память, обработка

команд и выполнение инструкций являются конвейерными.

Независимость функциональных устройств

Большинство ФУ в CRAY C90 являются независимыми, поэтому несколько операций

могут выполняться одновременно. Для операции A=(B+C)*D*E порядок выполнения

может быть следующим (все аргументы загружены в S регистры). Генерируются три

инструкции: умножение D и E, сложение B и C и умножение результатов двух

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

Векторная обработка

Векторная обработка увеличивает скорость и эффективность обработки за счет того, что

обработка целого набора (вектора) данных выполняется одной командой. Скорость

выполнения операций в векторном режиме приблизительно в 10 раз выше скорости

скалярной обработки. Для фрагмента типа

Do i = 1, n

A(i) = B(i)+C(i)

End Do

в скалярном режиме потребуется сгенерировать целую последовательность команд:

прочитать элемент B(I), прочитать элемент C(I), выполнить сложение, записать результат

в A(I), увеличить параметр цикла, проверить условие цикла. В векторном режиме этот

фрагмент преобразуется в: загрузить порцию массива B, загрузить порцию массива C (эти

две операции будут выполняться со сдвигом в один такт, т.е. практически одновременно),

векторное сложение, запись порции массива в память, если размер массивов больше

длины векторных регистров, то повторить эту последовательность некоторое число раз.

Перед тем, как векторная операция начнет выдавать результаты, проходит некоторое

время (startup), связанное с заполнением конвейера и подкачкой аргументов. Чем больше

длина векторов, тем менее заметным оказывается влияние данного начального

промежутка времени на все время выполнения программы.

Векторные операции, использующие различные ФУ и регистры, могут выполняться

параллельно.

Зацепление функциональных устройств

Архитектура CRAY Y-MP C90 позволяет использовать регистр результатов векторной

операции в качестве входного регистра для последующей векторной операции, т.е. выход

сразу подается на вход. Это называется зацеплением векторных операций. Вообще говоря,

глубина зацепления может быть любой, например, чтение векторов, выполнение операции

сложения, выполнение операции умножения, запись векторов.

Многопроцессорная обработка: multiprogramming, multitasking

Multiprogramming - выполнение нескольких независимых программ на различных

процессорах.

Multitasking - выполнение одной программы на нескольких процессорах.

Пиковая производительность CRAY Y-MP C90

Пиковая производительность компьютера CRAY Y-MP C90 вычисляется так:

функциональные устройства выдают два результата каждый такт (сдвоенные конвейеры),

зацепление сложения и умножения дает четыре операции за такт, что составляет почти 1

Гфлопс (10

опер/с). Если работают все 16 процессоров, то 16 Гфлопс.

3.4 Архитектура вычислительной системы HP/Convex Exemplar SPP1600

Ниже приводится схема компьютера HP/Convex Exemplar SPP1600, на которой можно

найти те компоненты высокопроизводительных вычислительных систем, о которых шла

речь в данной главе.

Процессорными элементами являются RISC процессоры HP PA7200 с тактовой частотой

120 Мгц, кэш-памятью для данных объемом 1 Мб и кэш-памятью команд объемом тоже 1

Мб. Основным строительным элементом SPP является гиперузел, представляющий собой

симметричную мультипроцессорную систему из 8 процессоров и банков памяти, с

высокоскоростным перекрестным соединением 5x5. Топология соединения здесь - кольцо

(одномерный тор), который может соединять до 16 гиперузлов, то есть до 128

процессоров. Система обеспечивает кэш-когерентность. Процессоры SPP могут быть

организованы в независимые подсистемы с полной поддержкой многопользовательского

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

проявляться в разном времени доступа к виртуальной памяти различных классов, впрочем

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

3.5. Архитектура массивно-параллельных компьютеров (на примере CRAY T3D).

Особенности программирования

Общая структура компьютера CRAY T3D

Компьютер CRAY T3D - это массивно-параллельный компьютер с распределенной

памятью, объединяющий от 32 до 2048 процессоров. Распределенность памяти означает

то, что каждый процессор имеет непосредственный доступ только к своей локальной

памяти, а доступ к данным, расположенным в памяти других процессоров, выполняется

другими, более сложными способами.

CRAY T3D подключается к хост-компьютеру (главному или ведущему), роль которого,

в частности, может исполнять CRAY Y-MP C90. Вся предварительная обработка и

подготовка программ, выполняемых на CRAY T3D, проходит на хосте (например,

компиляция). Связь хост-машины и T3D идет через высокоскоростной канал передачи

данных с производительностью 200 Mбайт/с.

Массивно-параллельный компьютер CRAY T3D работает на тактовой частоте 150MHz

и имеет в своем составе три основные компоненты: сеть межпроцессорного

взаимодействия (или по-другому коммуникационную сеть), вычислительные узлы и

узлы ввода/вывода.

Вычислительные узлы и процессорные элементы

Вычислительный узел состоит из двух процессорных элементов (ПЭ), сетевого

интерфейса контроллера блочных передач. Оба процессорных элемента, входящие в

состав вычислительного узла, идентичны и могут работать независимо друг от друга.

Процессорный элемент. Каждый ПЭ содержит микропроцессор, локальную память и

некоторые вспомогательные схемы.

Микропроцессор - это 64-х разрядный RISC (Reduced Instruction Set Computer) процессор

ALPHA фирмы DEC, работающий на тактовой частоте 150 MHz. Микропроцессор имеет

внутреннюю кэш-память команд и кэш-память данных.

Объем локальной памяти ПЭ - 8 Mслов. Локальная память каждого процессорного

элемента является частью физически распределенной, но логически разделяемой (или

общей), памяти всего компьютера. В самом деле, память физически распределена, так как

каждый ПЭ содержит свою локальную память. В тоже время, память разделяется всеми

ПЭ, так как каждый ПЭ может обращаться к памяти любого другого ПЭ, не прерывая его

работы.

Обращение к памяти другого ПЭ лишь в 6 раз медленнее, чем обращение к своей

собственной локальной памяти.

Сетевой интерфейс формирует передачи перед посылкой через коммуникационную сеть

другим вычислительным узлам или узлам ввода/вывода, а также принимает приходящие

сообщения и распределяет их между двумя процессорными элементами узла.

Контроллер блочных передач - это контроллер асинхронного прямого доступа в память,

который помогает перераспределять данные, расположенные в локальной памяти разных

ПЭ компьютера CRAY T3D, без прерывания работы самих ПЭ.

Коммуникационная сеть

Коммуникационная сеть обеспечивает передачу информации между вычислительными

узлами и узлами ввода/вывода с максимальной скоростью в 140M байт/с. Сеть образует

трехмерную решетку, соединяя сетевые маршрутизаторы узлов в направлениях X, Y, Z.

Каждая элементарная связь между двумя узлами - это два однонаправленных канала

передачи данных, что допускает одновременный обмен данными в противоположных

направлениях.

Топология сети, чередование вычислительных узлов

Коммуникационная сеть компьютера CRAY T3D организована в виде двунаправленного

трехмерного тора, что имеет свои преимущества перед другими способами организации

связи:

 быстрая связь граничных узлов и небольшое среднее число перемещений по тору

при взаимодействии разных ПЭ: максимальное расстояние в сети для

конфигурации из 128 ПЭ равно 6, а для 2048 ПЭ равно 12;

 возможность выбора другого маршрута для обхода поврежденных связей.

Все узлы в коммуникационной сети в размерностях X и Z расположены с чередованием,

что позволяет минимизировать длину максимального физического соединения между ПЭ.

Маршрутизация в сети и сетевые маршрутизаторы.

При выборе маршрута для обмена данными между двумя узлами сетевые маршрутизаторы

всегда сначала выполняют смещение по размерности X, затем по Y, а в конце по Z. Так как

смещение может быть как положительным, так и отрицательным, то этот механизм

помогает минимизировать число перемещений по сети и обойти поврежденные связи.

Сетевые маршрутизаторы каждого вычислительного узла определяют путь перемещения

каждого пакета и могут осуществлять параллельный транзит данных по каждому из трех

измерений X, Y, Z.

Нумерация вычислительных узлов.

Каждому ПЭ в системе присвоен уникальный физический номер, определяющий его

физическое расположение, который и используется непосредственно аппаратурой.

Не обязательно все физические ПЭ принимают участие в формировании логической

конфигурации компьютера. Например, 512-процессорная конфигурация компьютера

CRAY T3D реально содержит 520 физических ПЭ, 8 из которых находятся в резерве.

Каждому физическому ПЭ присваиваится логический номер, определяющий его

расположение в логической конфигурации компьютера, которая уже и образует

трехмерный тор.

Каждой программе пользователя из трехмерной решетки вычислительных узлов

выделяется отдельный раздел, имеющий форму прямоугольного параллелепипеда, на

котором работает только данная программа (не считая компонент ОС). Для

последовательной нумерации ПЭ, выделенных пользователю, вводится виртуальная

нумерация.

3.6. Кластеры рабочих станций

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

компьютеров (но все-таки не суперкомпьютеров), соединенных в локальную сеть, обычно,

в масштабе отдела, факультета или института. Такой кластер можно рассматривать как

некую вычислительную систему с распределенной памятью, распределенным

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

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

характеристиками по быстродействию, сравнимыми с показателями специализированных

суперкомпьютеров, но стоимость такой системы относительно невелика, ведь рабочие

станции уже существуют! Они закуплены и установлены и не всегда загружены работой,

так почему бы не превратить их в виртуальный (временный) вычислительный комплекс?

Еще одним из преимуществ такой гетерогенной вычислительной системы может быть то,

что отдельные части программы могут выполняться на наиболее подходящих для этого

компьютерах.

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

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

фирмпроизводителей, имеющие разную архитектуру, работающие под управлением

разных операционных систем, имеющих разные файловые системы и т.д. То есть,

возникает проблема совместимости. Имеется и проблема доступа, так как для входа в

любой компьютер может потребоваться разрешение работать на нем. Может быть и так,

что время счета измеряется днями, а то и неделями, а некоторые из рабочих станций

кластера время от времени должны быть загружены своей собственной работой. То есть

особенно важным оказывается управление такой вычислительной системой, очень

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

административным образом, для решения других требуется специальное программное

обеспечение, реже специальная аппаратура, ведь оборудование уже есть, включая

процессоры и сети. В качестве примера приведем здесь систему управления

гетерогенными кластерами рабочих станций CONDOR. Эта система позволяет

пользователю сохранить за собой полный контроль за своей собственной рабочей

станцией и не требует от него наличия прав доступа к другим рабочим станциям. Она

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

гибкое управление процессом выполнения программ. Важно еще и то, что эта система

бесплатная. Другие примеры бесплатных систем такого рода DQS и PBS(разработка

НАСА). Коммерческие системы - CODINE, LoadLeveler (IBM) и некоторые другие.

4. Издержки и выигрыш при реализации параллельных и векторных вычислений

Если у Вас есть векторная ЭВМ с длиной векторного регистра 128 элементов или

параллельная ЭВМ с таким же числом процессоров, то теоретически Ваша программа

может быть выполнена в 128 раз быстрее, чем на аналогичной по быстродействию

однопроцессорной скалярной машине. Это предел, который обычно недоступен, но к

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

ЭВМ не только возможно, но и целесообразно. Выигрыш в быстродействии по

отношению к обычной ЭВМ может окупить финансовые затраты на аренду или покупку

суперЭВМ и трудовые затраты на написание и оптимизацию векторной или параллельной

версии программы.

В 3 главе речь пойдет о реально достижимом выигрыше в быстродействии программ и о

причинах, мешающих достичь наивысшей производительности.

4.1. Трудовые затраты на распараллеливание или векторизацию программы

4.1.1. Способы векторизации и распараллеливания программ

Целью программиста не должно быть получение правильного результата вычислений

любой ценой, но получение правильного результата наибыстрейшим, оптимальным

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

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

чтобы потратить минимум усилий на тестирование и отладку. Если программа

предназначена для частого использования или время ее работы будет гораздо больше

времени ее написания и отладки, то не следует жалеть труда на оптимизацию ее

быстродействия. Но в результате программа, оптимальная для одного типа ЭВМ, окажется

совсем не оптимальной для машин других типов.

Методы программирования для скалярных, векторных и параллельных ЭВМ коренным

образом отличаются друг от друга. Конечно, любая программа, написанная на языке

высокого уровня, может быть оттранслирована в коды любой ЭВМ и исполнена как на

скалярной, так и на векторной или параллельной машинах и результаты работы всех

программ скорее всего будут близкими. Эту оговорку надо принять во внимание. Дело в

том, что результат действий с вещественными числами может изменяться при изменении

последовательности операций, т.к. в компьютерной арифметике закон сочетаний не всегда

выполняется:

(A+B)+C не всегда равно A+(B+C).

Самый простой вариант попробовать ускорить имеющуюся программу - это

воспользоваться встроенными в транслятор (обычно с ФОРТРАНа или Си) средствами

векторизации или распараллеливания. При этом никаких изменений в программу вносить

не придется. Однако вероятность существенного ускорения (в разы или десятки раз)

невелика. Трансляторы с ФОРТРАНа и Си векторизуют и распараллеливают программы

очень аккуратно и при любых сомнениях в независимости обрабатываемых данных

оптимизация не проводится. Поэтому, кстати, и не приходится ожидать ошибок от

компиляторов, если программист явно не указывает компилятору выполнить векторную

или параллельную оптимизацию какой-либо части программы.

Второй этап работы с такой программой - анализ затрачиваемого времени разными

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

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

наиболее затратными являются циклы и усилия компилятора направлены прежде всего на

векторизацию и распараллеливание циклов. Диагностика компилятора поможет

установить причины, мешающие векторизовать и распараллелить циклы. Возможно, что

простыми действиями удастся устранить эти причины. Это может быть простое

исправление стиля программы, перестановка местами операторов (цикла и условных),

разделение одного цикла на несколько, удаление из критических частей программы

лишних операторов (типа операторов отладочной печати). Небольшие усилия могут дать

здесь весьма существенный выигрыш в быстродействии.

Третий этап - замена алгоритма вычислений в наиболее критичных частях программы.

Способы написания оптимальных (с точки зрения быстродействия) программ

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

параллельной (векторной). Поэтому программа, оптимальная для скалярного процессора,

с большой вероятностью не может быть векторизована или распараллелена. В то же время

специальным образом написанная программа для векторных или параллельных ЭВМ

будет исполняться на скалярных машинах довольно медленно. Замена алгоритма в

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

программы при относительно небольших потраченных усилиях. Дополнительные

возможности предоставляют специальные векторные и параллельные библиотеки

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

конкретной ЭВМ, можно упростить себе задачу по написанию и отладке программы.

Единственный недостаток данного подхода состоит в том, что программа может стать не

переносимой на другие машины (даже того же класса), если на них не окажется

аналогичной библиотеки.

Написание программы "с нуля" одинаково сложно (или одинаково просто) для машин

любых типов. Этот способ является идеальным для разработки эффективных,

высокопроизводительных векторных или параллельных программ. Начинать надо с

изучения специфики программирования для векторных и параллельных ЭВМ, изучения

алгоритмов, которые наиболее эффективно реализуются на ЭВМ данных типов. После

этого надо проанализировать поставленную задачу и определить возможность применения

векторизуемых и распараллеливаемых алгоритмов для решения конкретной задачи.

Возможно, что придется переформулировать какие-то части задачи, чтобы они решались с

применением векторных или параллельных алгоритмов. Программа, специально

написанная для векторных или параллельных ЭВМ, даст наибольшее ускорение при ее

векторизации и распараллеливании.

Программист должен быть готов к поддержанию одновременно нескольких (двух или

даже трех) версий программы, предназначенных для работы на ЭВМ разного типа. Это,

наверно, самая существенная из всех "издержек", связанная с одновременным

использованием скалярных, векторных и параллельных машин

4.1.2. Применение разных языков программирования

Перенос готовой программы и оптимизация ее для исполнения на машине другого типа

может потребовать весьма существенных усилий по исправлению стиля написаниния

программы. Опыт показывает, что проще всего адаптировать к исполнению на векторных

или параллельных машинах программы на ФОРТРАНе. Конструкции ФОРТРАНа для

организации циклов и для работы с массивами менее разнообразны, чем в Си, а именно

циклы по обработке массивов и являются главными объектами оптимизации при

векторизации или распараллеливанию программ. Более того, в ФОРТРАНе-90 встроенные

функции по работе с массивами и арифметические операции с массивами имеют довольно

эффективную реализацию в виде стандартных библиотечных векторных или

параллельных функций или даже в виде генерируемого компилятором объектного кода (in

line).

Больше всего трудностей появится при переносе программ на Си, оптимальным образом

написанных для скалярных процессоров. Следующие программы на Си показывают два

принципиально разных подхода к операциям с массивами. Традиционный Си'шный

подход к копированию массивов является недопустимым при написании векторных или

параллельных программ. Приведенный ниже цикл не может быть векторизован или

распараллелен из-за того, что значение ссылок на элементы массивов вычисляются

рекуррентно (зависят от значений на предыдущем шаге):

float x[100], a[100];

for( i=0; i<100; i++){ *xx++ = *aa++ };

В то время как другой цикл, написанный совсем не в традициях Си, может быть

распараллелен и векторизован:

float x[100], a[100];

for( i=0; i<100; i++){ x[i] = a[i]; }

Сравните: ФОРТРАН-77 позволяет единственным способом записать цикл и этот способ

совпадает со вторым, нетрадиционным способом в Си:

real x(100), a(100)

do i=1, 100

x(i) = a(i)

enddo

ФОРТРАН-90 разрешает применить векторную операцию присваивания, что упрощает

анализ программы транслятором:

real x(100), a(100)

x = a ! векторное присваивание

Приведенный пример показывает, что существенным фактором при адаптации готовых

программ к работе на параллельных и векторных ЭВМ является не только стиль

написания программы, но и сам использованный язык программирования

4.2. Различие и сходство между распараллеливанием и векторизацией программ

Сходство алгоритмов - параллелизм данных Из архитектуры векторных и параллельных

компьютеров следует самое важное свойство алгоритмов, которые могут быть эффективно

исполнены на таких ЭВМ: эти алгоритмы должны включать одинаковые действия над

некоторыми наборами данных (массивами), при этом результаты действий над любой

частью данных не должны зависеть от результатов действий над другой их частью. Иначе

говоря, последовательность вычисления величин не должна играть роль в данном

алгоритме. Это есть параллелизм данных. Простейшим примером такого алгоритма может

служть следующий фрагмент программы:

real x(100), a(100), b(100)

do i=1, 100

x(i) = real(i)**2 + 3.0

a(i) = b(i) + x(i)

enddo

или в другой интерпретации:

real x(100), a(100), b(100)

do i=100, 1, -1

x(i) = real(i)**2 + 3.0

a(i) = b(i) + x(i)

enddo

Предположим, что i=5, тогда тело цикла примет вид:

x(5) = 5.0**2 + 3.0

a(5) = b(5) + x(5)