Параллельные структуры вычислительных систем

Два уровня распараллеливания

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

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

Уже давно стало ясно, что только структурными методами можно уравнять возможности вычислительных средств и требуемые скорости решения на них задач. Под структурными понимают методы распараллеливания работ. К распараллеливанию прибегают при проектировании отдельных устройств ЭВМ — устройств управления, буферов команд, каналов обращения к памяти и модулей памяти, многофункциональных арифметическо-логических устройств (АЛУ), повсеместно применяемых конвейеров и т.д. Но к распараллеливанию же прибегают и в проектировании совместной работы многих процессоров при параллельной или распределенной обработке информации, вводя в обращение термин "вычислительная система (ВС)".

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

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

Важным революционизирующим моментом стал переход на микропроцессорную элементно-конструкторскую базу, обусловившую построение мультимикропроцессорных ВС.

Сложилось представление о двух основных уровнях, на которых в ВС применяются практические методы распараллеливания:

Эти уровни обусловили уровни структуризации ВС на пути превращения ее в супер-ЭВМ. Современным практическим воплощением первого уровня структуризации являются однородные многопроцессорные ВС на общей (разделяемой) оперативной памяти. Они получили название симметричных ВС за обеспечение "равноправия" составляющих модулей. Окончательное признание симметричных ВС положило конец поиску "экзотических" архитектур, эффективных лишь при решении определенных классов задач. Универсальность симметричных ВС, возможность реализации на них любых вычислительных процессов с высокой эффективностью оборудования иллюстрируются многими применениями и анализируются ниже.

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

Различают два способа реализации такой загрузки: динамический и статический.

Динамическая загрузка осуществляется аппаратурой в процессе выполнения программы. Она использует упрощенные алгоритмы распараллеливания.

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

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

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

Классификация параллельных ВС

Потоки команд и потоки данных. Общепринята удачная классификация ВС, которую предложил в 1966 г. М.Флинн (США). Основным определяющим архитектурным параметром он выбрал взаимодействие потока команд и потока данных (операндов и результатов).

В ЭВМ классической архитектуры ведется последовательная обработка команд и данных. Команды поступают одна за другой (за исключением точек ветвления программы), и для них из ОЗУ или регистров так же последовательно поступают операнды. Одной команде (операции) соответствует один необходимый ей набор операндов (как правило, два для бинарных операций). Этот тип архитектуры — " один поток команд — один поток данных", ОКОД (SISD - "Single Instruction, Single Data") условно изображен на рис. 1.1.

(рис 1.1) ВС типа ОКОД (SISD)

Тип ОКМД — "один поток команд — много потоков данных" (SIMD — "Single Instruction — Multiplе Data") охватывает ВС, в которых одной командой обрабатывается набор данных, множество данных, вектор, и вырабатывается множество результатов. Это векторные и матричные системы, в которых по одной команде выполняется одна и та же операция над всеми элементами массива — вектора или матрицы, распределенными между процессорными (обрабатывающими) элементами ПЭ или процессорами. Принцип обработки показан на рис. 1.2.

(рис 1.2) ВС типа ОКМД (SIMD)

Отечественные векторные ВС — ПС-2000, ПС-2100. Допускают организацию матричной обработки. Классический пример матричной архитектуры — ILLIAC-1V (США).

К типу МКОД — "много потоков команд — один поток данных" (MISD — "Multiple Instruction — Single Data") принято относить векторный конвейер (обычно в составе ВС, чтобы подчеркнуть основной используемый принцип вычислений), например, в составе ВС Crey -1, "Электроника ССБИС". На векторном конвейере производится последовательная обработка одного потока данных многими обрабатывающими устройствами (ступенями, станциями) конвейера.

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

Принцип обработки показан на рис. 1.3.

(рис 1.3) ВС типа МКОД (MISD)

Тип МКМД — "много потоков команд — много потоков данных" (MIMD — "Multiple Instruction — Multiple Data") cоответствует более полному и независимому распараллеливанию. К этому типу относятся, например, все многопроцессорные вычислительные комплексы (МВК) семейства "Эльбрус".

"Фон-Неймановские" и "не-Фон-Неймановские" архитектуры

Немного истории. Первую ЭВМ создал в 1939 г. в США профессор Джон Атанасов, болгарин, со своим аспирантом К.Берри. Две малые ЭВМ, созданные ими в период 1937 — 1942 гг., были прототипами большой ЭВМ АВС для решения систем линейных уравнений, которая в 1942 г. доводилась по устройствам ввода-вывода и должна была войти в строй в 1943 г., но призыв Атанасова в армию в 1942 г. воспрепятствовал этому. Проект электронной ЭВМ Эниак (Electronics Numerical Integrator and Computer) был сделан в 1942 г. Д.Моучли и Д.Эккертом и осуществлен в 1945 г. в Муровской электротехнической лаборатории Пенсильванского университета. В 1946 г. Эниак был публично продемонстрирован в работе. В нем впервые были применены триггеры. Рождение Эниак считают началом компьютерной эры, посвящая ему научные симпозиумы и другие торжественные мероприятия. (Международный симпозиум, посвященный 50-летию первой ЭВМ, был проведен и в Москве в июне 1996 г.)

Однако еще в начале 40-х годов XX века Атанасов поделился с Моучли информацией о принципах, заложенных в ЭВМ АВС. Хотя Моучли впоследствии утверждал, что он не воспользовался этой информацией в патенте на Эниак, суд не согласился с этим. Вернувшись из армии после войны, Атанасов узнал, что более мощная ЭВМ Эниак уже создана, и потерял интерес к этой теме, не поинтересовавшись, насколько Эниак похож на его ЭВМ АВС.

Известный английский математик Алан Тьюринг был не только теоретиком по информации и теории алгоритмов, автором теоретического автомата "машины Тьюринга", но и талантливым инженером, создавшим в начале 1940-х годов первую работающую специализированную ЭВМ. Эта ЭВМ под названием "Колосс" была сконструирована и сделана им совместно с Х.А.Ньюменом в Блетчи (Англия) и начала работать в 1943 г. Сообщения о ней своевременно не публиковались, т.к. она использовалась для расшифровки секретных германских кодов во время войны.

Основные архитектурно-функциональные принципы построения ЭВМ были разработаны и опубликованы в 1946 г. венгерским математиком и физиком Джоном фон Нейманом и его коллегами Г.Голдстайном и А.Берксом в ставшем классическим отчете "Предварительное обсуждение логического конструирования электронного вычислительного устройства". Основополагающими принципами ЭВМ на основании этого отчета являются: 1) принцип программного управления выполнением программы, и 2) принцип хранимой в памяти программы. Они легли в основу понятия фон-Неймановской архитектуры, широко использующей счетчик команд .

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

Альтернативной архитектурой является "не-фон-Неймановская" архитектура, допускающая одновременный анализ более одной команды. Поиски ее обусловлены необходимостью распараллеливания выполнения программы между несколькими исполнительными устройствами — процессорами. Счетчик команд при этом не нужен. Порядок выполнения команд определяется наличием исходной информации для выполнения каждой из них. Если несколько команд готовы к выполнению, то принципиально возможно их назначение для выполнения таким же количеством свободных процессоров. Говорят, что такие ВС управляются потоком данных (data flow).

Общая схема потоковых ВС представлена на рис. 1.4.

(рис 1.4) "Идеальная" потоковая ВС

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

{код операции, операнд 1, ..., операнд L,
адрес результата 1, ..., адрес результата M}

В командах проверки условия возможно альтернативное задание адреса результата (ИЛИ — ИЛИ). Адреса результатов являются адресами ПК, т.е. результаты выполнения одних команд в качестве операндов могут поступать в текст других команд. Команда не готова к выполнению, если в ее тексте отсутствует хотя бы один операнд. Ячейка, обладающая полным набором операндов, переходит в возбужденное состояние и передает в селекторную сеть информационный пакет (токен), содержащий код операции и необходимую числовую и связную информацию. Он поступает по сети на одно из исполнительных устройств. Там же операция выполняется, и в распределительную сеть выдается результирующий пакет, содержащий результат вычислений и адреса назначения в ПК (возможно, за счет выбора альтернативы, т.е. такой выбор — тоже результат). По этим адресам в ПК результат и поступает, создавая возможность активизации новых ячеек. После выдачи токена в селекторную сеть операнды в тексте команды уничтожаются, что обеспечивает повторное выполнение команды в цикле, если это необходимо.

Селекторная и распределительная сети образуют коммуникационную сеть ВС.

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

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

Системы с общей и распределенной памятью

Системы с общей (разделяемой) оперативной памятью образуют современный класс ВС — многопроцессорных супер-ЭВМ. Одинаковый доступ всех процессоров к программам и данным представляет широкие возможности организации параллельного вычислительного процесса (параллельных вычислений). Отсутствуют потери реальной производительности на межпроцессорный (между задачами, процессами и т.д.) обмен данными (рис. 1.5a).

(рис 1.5) ВС с общей (а) и распределённой (б) памятью

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

Другое, противоположное воплощение принципа МИМД — масспроцессорные или высокопараллельные архитектуры, объединяющие сотни — тысячи — десятки тысяч процессоров.

В современных супер-ЭВМ наметилась тенденция объединения двух принципов: общей (распределяемой) и распределенной (локальной) оперативной памяти (ЛОП). Такая структура используется в проекте МВК "Эльбрус-3" и "Эльбрус-3М" (рис. 1.6).

(рис 1.6) Схема ВС с модулями локальной памяти

Способы межмодульного соединения (комплексирования)

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

На рис. 1.7 представлена система с общей шиной. Шина состоит из линий, по которым передаются информационные и управляющие сигналы.

(рис 1.7) Схема ВС с общей шиной

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

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

Матричный коммутатор можно представить (прямоугольной) сеткой шин. К одному концу каждой подсоединен источник-потребитель информации (рис. 1.8). Точки пересечения — узлы этой сетки — представляют собой управляющие ключи, которые соединяют или разъединяют соответствующие шины, устанавливая или прекращая связь между модулями. Реализуется связь "каждый с каждым". Одновременно могут связываться многие (до n/2 ) пары модулей.

(рис 1.8) Матричные коммутаторы: а) — перекрёстная коммутация процессоров, б) — коммутация процессоров и модулей памяти

На рис. 1.8а — перекрестная связь между процессорами в ВС с распределенной памятью, на рис. 1.8б — между n процессорами и m модулями ОП.

"Исторические" модели

Векторная ВС ПС-2000

Разрабатывалась как проблемно-ориентированная ВС для задач обработки геофизической информации, информации со спутников в интересах геологии, картографии, обработки изображений, моделирования поведения среды и т.д. Является типичной иллюстрацией типа ОКМД.

Схема ВС приведена на рис. 1.9.

(рис 1.9) Схема ВС ПС-2000

Основу ПС-2000 составляет параллельный процессор с общим потоком команд ППС-2000, содержащий до 64 ПЭ.

Соседние ПЭ связаны регулярными каналами РК для оперативного обмена данными. В связи с проблемной ориентированностью ВС это обеспечивает быстрый обмен при обработке "соседними" ПЭ "соседних" же элементов поверхностей, конечно же, информационно взаимосвязанных. Связь с помощью РК — циклическая, в частности, ПЭ1 с помощью РК связан с ПЭ64. Т.е. при "прокатывании" 64 ПЭ по длинной последовательности обрабатываемых элементов поверхности ПЭ1 и ПЭ64 являются "соседними": после элемента поверхности, обрабатываемого ПЭ64, следует элемент поверхности, обрабатываемый ПЭ1. Затем пошли дальше, превратив векторную ППС-2000 в матричную ВС.

Ввели сегментирование множества процессоров (процессоров решающего поля ). 64 ПЭ разбиваются или на 8 сегментов по 8 ПЭ, или на 4 сегмента по 16 ПЭ, или на 2 сегмента по 32 ПЭ. Это осуществляется, прежде всего, за счет установления связи с помощью РК между первым и последним ПЭ каждого сегмента. Тогда при обработке поверхности ПЭ "прокатываются" циклически не только по "длинному" вектору, но и, при сегментировании, по матричным элементам поверхности, как будет показано далее.

Для общей связи всех элементов ППС-2000, включая УУ, используется магистральный канал — общая шина. По магистрали микрокоманд каждому ПЭ сообщаются команды, микропрограммы операций и микрокоманды из УУ.

ППС-2000 имеет распределенную память.

В ППС-2000 предусмотрена двухуровневая схема управления: на уровне микрокоманд и команд. Память для их хранения — в УУ. На микрокомандном уровне пишутся отдельные фрагменты задачи — подпрограммы процедур, на командном — последовательность обращения к этим подпрограммам.

Основным, задающим, является вычислительный процесс в мониторной подсистеме МПС. В ней в режиме разделения времени могут выполняться несколько задач. С ППС-2000 в данный момент может быть связана только одна задача. Т.е. ППС-2000 по отношению к малой машине (типа СМ-2), выполняющей функции МПС, является интеллектуальным терминалом с последовательным доступом.

В обычном режиме набор процедур, выполняемых в ППС-2000, по запросам со стороны МПС, определяется заранее. Микропрограммы, реализующие этот набор процедур, загружаются в память ППС-2000 заранее. Если в ходе вычислительного процесса в МПС возникает необходимость в какой-либо процедуре из этого набора, задача запускает соответствующую микропрограмму и передает ей необходимые данные.

Возможна и динамическая загрузка микропрограмм в память ППС-2000.

Матричные ВС

Матричная ВС также является типичным представителем ОКМД, расширением принципа векторных ВС.

Классическим примером, прототипом и эталоном стала ВС ILLIAC 1V, разработанная в 1971 г. в Иллинойском университете и в начале 1972 г. установленная в Эймском научно-исследовательском центре NASA (Калифорния).

Одна последовательность команд программы управляет работой множества 64 ПЭ, одновременно выполняющих одну и ту же операцию над данными, которые могут быть различными и хранятся в ОП каждого ПЭ. (Производительность — до 200 млн. оп./с)

В целом структура центральной части может быть представлена аналогичной векторной ВС (рис. 1.10).

(рис 1.10) Схема обмена в матричной ВС

УУ — фактически простая вычислительная машина небольшой производительности и может выполнять операции над скалярами одновременно с выполнением матрицей ПЭ операций над векторами или матрицами. Посылает команды в независимые ПЭ и передает адреса в их ОП.

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

Почему же ВС — матричная?

ПЭ образуют матрицу, в которой информация от одного ПЭ к другому может быть передана через сеть пересылок данных при помощи специальных команд обмена. Регистры пересылок (рис. 1.11) каждого i -го ПЭ связаны высокоскоростными линиями обмена с регистрами пересылок ближайшего левого ( i-1 -го) и ближайшего правого ( i+1 )-го ПЭ, а также с регистрами пересылок ПЭ, отстоящего влево на 8 позиций от данного ( i-8 )-й и отстоящего вправо на 8 позиций от данного ( i+8 )-й, при этом нумерация ПЭ рассматривается как циклическая с переходом от 63 к 0 (нумерация возрастает по mod 64 ) слева направо и от 0 к 63 справа налево.

(рис 1.11) Конфигурация "быстрых" связей в ВС ILLIAC-4

Расстояния между ПЭ в сети пересылок и соответствующие пути передачи информации задаются комбинациями из (-1, +1, -8, +8).

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

Доступ к ОП имеют АУ соответствующего ПЭ, УУ системы и подсистема ввода-вывода. Управление доступом и разрешение конфликтов при доступе к ОП осуществляет УУ системы.

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

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

(рис 1.12) Решение задачи методом "сеток"

Кратко рассмотрим план решения подобной задачи на матричной ВС.

Пусть необходимо решить уравнение с частных производных$$\frac{\partial^2 f}{\partial x^2}-\frac{\partial f}{\partial y}=0$$ на области B:$$\left\{ \begin{array}{l} {0\le x\le A} \\ {0\le y\le B} \end{array} \right }$$

Граничные условия:

f(0,y)= f1(y),

f(A,y)= f2(y),

f(x,0)= f3(x),

f(x,B)= f4(x).

Частные производные можно выразить через конечные разности несколькими способами, например:$$\begin{aligned} \left\frac{\partial f}{\partial x} \right|_{i,j} \cong \frac{f_{ij}-f_{i-1,j} }{h_{x} } \cong \frac{f_{i+1,j} -f_{ij} }{h_{x}};\\ \left. \frac{\partial ^{2} f}{\partial x^{2} } \right|_{i,j} \cong \frac{(f_{i+1,j} -f_{ij} )-(f_{ij} -f_{i-1,j} )}{h_{x}^{2} } =\frac{f_{i+1,j} -2f_{ij} +f_{i-1,j} }{h_{x}^{2}};\\ \left. \frac{\partial f}{\partial y} \right|_{i,j} \cong \frac{f_{i,j+1} -f_{i,j-1} }{2h_{y}}.\\ \end{aligned}$$

Подставив полученные выражения в уравнение, получим основное рекуррентное соотношение для нахождения значения функции через ее значения в соседних четырех узлах:

fi, j = 0,5 fi+1, j + 0,5 fi-1, j - 0,25 hx2/hy(fi, j+1 - fi, j-1).

Распараллеливание вычислений и "прокатывание" матрицей ПЭ области B — многократные, до получения необходимой точности — очевидны.

А именно: первоначально в одном цикле итерации 64 ПЭ по выведенной формуле рассчитывают 8 x 8 узловых значений функции близ вершины координат, "цепляя" при этом граничные значения. Затем производится смещение вправо на следующую группу узловых значений функции. По окончании обработки по горизонтали производится смещение по вертикали и т.д. При следующей итерации процесс повторяется. От итерации к итерации распространяется влияние граничных условий на рассчитываемые значения функции. Процесс сходится для определения значений функции-решения в узлах сетки с требуемой точностью.

В ILLIAC-1V такая регулярность сохранялась бы, если бы существовали быстрые связи между ПЭ7 и ПЭ0, ПЭ15 и ПЭ8 и т.д., то есть циклически по строкам матрицы.

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