Всеволод Сергеевич Бурцев Параллелизм вычислительных процессов и развитие архитектуры суперэвм м, 1997

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

Ввиду того, что динамические массивы могут возникать и уничтожаться в процессе решения задачи, работа с ними требует постраничной разбивки задачи. Это диктуется тем, что принятый нами максимальный массив в 10 тыс. слов без разбиения на страницы даст существенные потери в плотности его упаковки в оперативной памяти (потери на дискретность). Предположим, что динамические массивы разбиты на блоки по 100 слов в каждом. Рассмотрим случай, когда размер массива не превосходит одного блока. Работа с массивами в этом случае практически ничем не отличается от работы со сложными операторами с многими входами и выходами. Блок памяти инициализирует команды НСО в одном из процессоров, после чего формируется токен запроса и посылается в АП. Ключ входного операнда НСО без поля индекса является фактически динамическим именем этого массива. В поле данных операнда НСО может стоять величина, определяющая число обращений к этому массиву. Подпрограмма сложного оператора выполняет все необходимые действия по мере прихода параметров, которыми в этом случае являются либо значения элементов массива, либо запросы по считыванию этих элементов, т.е. выдачи результатов. Эта же программа может вести общий счет обращений к элементам массива и при необходимости осуществляет его стирание. Так, запись элемента массива ничем не отличается от записи параметра сложного оператора. Однако, в этом случае (в поле данных ВП) программным путем осуществляется выдача всех отложенных запросов этого элемента, если они были. При поступлении ключа выдачи результата выполняется считывание элемента массива. В этом случае при помощи подпрограммы осуществляется считывание элемента, если он имеется в памяти и выдача его по указанному адресу. Если элемента нет, то запрос запоминается в отдельном блоке памяти и выдается после прихода значения элемента.

Обращения к элементам массива по их записи или считыванию происходит так же, как и при работе со многими входами и выходами через команды ПИ, ПСО, ИЗ и ИС. В случае записи элемента используется команда ИЗ, в случае считывания команда ИС. В том случае, если обращение к элементу массива происходит из контекста, в котором он был инициализирован (контекст массива), используются одновходовые команды ПИ. Если происходит обращение к элементу массива из внешнего контекста, используется двухвходовая команда ИП. Работа команд ИП, ПСО, ИЗ и ИС ничем не отличается от их работы со сложным оператором. Элементы массива являются параметрами в подпрограмме сложного оператора работы с динамическими массивами (Рис.7).

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

135

B.C. Бурцев, Л.Г.Тарасенко. Использование микропроцессоров традиционной архитектуры в

системе потока данных

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

Рис.7. Работа с динамическими массивами

Работа со статическими массивами значительно упрощается за счет того, что имя массива и его структура известны при программировании и трансляции. По этому имени-адресу константы, хранящейся в ПК, из любого микропроцессора можно определить его физический адрес. Поэтому нет необходимости в Команде НСО, а следовательно и в команде ПИ. Обращение к элементам массива может осуществляться через команду индексации с записью элемента в статический массив ИЗст и команду индексации со считыванием элемента из статического массива ИСст (Рис.8).

Эти команды, так же как и команды ИЗ и ИС, производят индексацию физического адреса элемента величиной И=Nэл, указывающей на номер элемента в блоке. Отличие этих команд от команд ИЗ и ИС состоит в том, что они являются одновходовыми, т.к. физический адрес блока элемента они считывают из ПК по второму адресу назначения этой команды К₂. Первый адрес назначения указывает на вход в подпрограмму. Таким образом, имя подпрограммы

одназначно определяется адресом команды ИЗст и ИСст. Ввиду того, что эти команды одновходовые, их можно использовать из любого контекста программы. Таким образом, для обращения к элементу массива необходимо сформировать токен, в поле "цвета" которого определяется контекст, поле И определяет индекс элемента, а в поле данных стоит ВЭ в случае записи элемента и Кл в случае считывания элемента. Проиндексированный физический адрес элемента вместе с K₁ и ВЭ или Кл через коммутатор К₂' передаются на тот процессор, в котором хранится этот элемент массива. Дальнейшая работа определяется подпрограммой сложного оператора работы с массивами.

Рис.8. Работа со статическими массивами

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

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

2. Описанная система массового параллелизма концептуально является однопроцессорной системой. Используя те же принципы потока данных, мы можем объединить эти процессоры в своеобразную многопроцессорную структуру (8-16 процессорную). Как и в традиционной многопроцессорной системе с целью достижения большей эффективности прохождения вычислительного процесса не будет желательно вмешательство человека для распределения процессоров и их АП по вычислительным процессам задачи.

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

3. Предлагаемая система обладает целым рядом преимуществ конструкторско-технологического характера: она может быть построена на серийно выпускаемых микропроцессорах или микропроцессорных наборах, серийно выпускаемых высокоинтегрированных схемах ассоциативной памяти, интегральных схемах коммутаторов и оперативной памяти. Пропускная способность исполнительных устройств, коммутаторов и АП с целью достижения временного баланса этих устройств может регулироваться количеством микропроцессоров в каждом исполнительном устройстве, количеством параллельно работающих интегральных схем в модуле АП и количеством параллельно работающих коммутаторов К₁, K₁' и К₂.

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

4. Безусловно, разработка специальных исполнительных устройств для скалярных и векторных вычислений и использование оптических принципов широкополосной коммутации на порядок поднимет производительность однопроцессорного комплекса и позволит подойти к пределу производительности в 10¹²-10¹³ оп/с, а на 8-16 процессорном комплексе достичь 10¹⁴ оп/с.

Авторы приносят благодарность профессору Д.Б. Подшивалову, сделавшему целый ряд принципиальных замечаний по публикуемой статье, многие из которых авторы учли в предлагаемой работе. Мы благодарны также И.К. Хайлову, Э.В. Сызько, Л.А. Козлову и М.Ю. Никитину, внесшим творческий вклад в эту работу.

Работа выполнена при поддержке Российского фонда Фундаментальных исследований.

138

B.C. Бурцев, Л.Г.Тарасенко. Использование микропроцессоров традиционной архитектуры в

системе потока данных



Литература

1. B.C. Бурцев. Выбор новой системы организации выполнения высокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ (в данной книге).

2. 
   Л.А. Богачева, Д.Б. Подшивалов. Проблемы построения системы команд для машин, основанных на принципе потока данных. В сб. "Вычислительные машины с нетрадиционной архитектурой. Супер ВМ." Вып.2, 1994, с.38-77.
   
3. 
   Л.Г. Тарасенко. Реализация языков программирования на ЭВМ архитектуры потока данных. В сб. "Вычислительные машины с нетрадиционной архитектурой. Супер ВМ". Вып.2, 1994, с.108-125.
   
4. 
   B.C. Бурцев. Тенденции развития высокопроизводительных систем и много-процессорные вычислительные комплексы. Препринт ИТМиВТ, 1977, с.27.
   
5. 
   V.S. Burtsev, V.B. Fyodorov. Associative memory of new generation supercomputers based on optical information processing principles. Holography and Optical Information Processing, 1991, v.1731, p.201-216.
   

В.С.Бурцев

Введение векторного ИУ в состав новой структуры суперЭВМ обусловлено, в первую очередь, требованием уменьшения объема ассоциативной памяти (АП) скалярного процессора. Хранение векторных операторов требует большого объема памяти, в то время как необходимости в ассоциативной памяти для хранения этих данных нет. В ассоциативной памяти скалярного процессора достаточно хранить описание вектора (его дескриптор), имея в виду, что действия над всеми его элементами идентичны. В этом случае в поле данных токена скалярного процессора располагается дескриптор вектора. Объединенные в АП пары токенов дескрипторов посылаются в векторное устройство, где и происходит выполнение оператора над векторами, результат которого посылается в оперативную память векторного устройства. В качестве результата в скалярный процессор возвращается токен, у которого в поле данных устанавливается дескриптор вектора-результата. В этом случае полностью реализуется принцип управления потоком данных на векторных задачах. Некоторое отступление от этого принципа при работе с векторными операндами состоит

в том, что размножение вектора, которое требует пересылки всех его элементов, целесообразно заменить размножением его дескриптора. Это приводит к тому, что на один вектор "смотрит" несколько дескрипторов. Стирание в памяти элементов вектора после обращения к ним, как того требует принцип управления потоком данных, может вызвать искажение вычислительного процесса. Это обстоятельство вынуждает следить за количеством обращений к вектору в процессе работы, и только после того, как все "смотрящие" на него дескприпторы использованы, производить освобождение памяти. Соблюдая эти особенности обращения к векторам, с дескрипторами векторов можно работать как с данными [1]. Таким образом, роль скалярного процессора сводится к определению векторных операций, готовых к выполнению. Если средняя длина вектора равна 1000, то можно в тысячу раз уменьшить объем АП, работая с векторными операциями по такому принципу. Наряду с экономией дорогой, в аппаратном отношении, ассоциативной памяти мы получаем увеличение ее быстродействия, так как с увеличением объема производительность АП падает [2].

Предлагаемая новая архитектура суперЭВМ без векторного исполнительного устройства на скалярном процессоре реализует максимальный параллелизм вычислений при поэлементном выполнении векторных операций, так как в этом случае операторы программы работают по мере готовности каждого элемента вектора, что в векторном исполнительном устройстве практически исключено. Ограничением такого подхода реализации векторных операций являются аппаратные средства, которыми мы сегодня реально располагаем. В первую очередь это возможность реализации коммутирующих устройств и многопортовой ассоциативной памяти. Наиболее вероятными для реализации этих устройств являются оптоэлектронная и оптическая элементные базы. В настоящее время построены рабочие макеты коммутаторов на оптоэлектронной базе, превосходящие по параметрам полупроводниковые, и показаны возможности создания многовходовой ассоциативной памяти [3]. Возможно, что с внедрением этих устройств на оптических и оптоэлектронных принципах необходимость в векторных исполнительных устройствах отпадет.

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

141

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

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

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

Исходя из этих соотношений, можно предположить, что объем векторной памяти в зависимости от задач должен быть в 10 - 100 раз больше скалярной.

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

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

2. Особенности структурной схемы векторного ИУ

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

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

Эффективность работы комплекса на векторах, меньших размера страниц, может быть обеспечена путем выполнения последних на скалярной части комплекса. Средняя величина вектора, безусловно, изменяется от задачи к задаче. Как показывает опыт, эта величина близка к 1000 элементам. В этом случае легко оценить потери ОЗУ на дискретность при различных длинах страниц. При размере страницы в 100 слов средняя величина потерь не превысит 5%, для 200 слов - 10%, для 400 слов - 20%. С учетом того, что операции над векторами размером меньше страницы будут выполняться на скалярной части комплекса, можно считать достаточной производительность векторной части в 10 раз больше скалярной. При этом темп работы векторной памяти должен быть в три раза больше темпа работы АП, так как каждая векторная операция требует двух считываний и одной записи. За счет увеличения формата векторной памяти до 400 слов, что потребует 400 модулей, мы получим увеличение производительности только в 4 раза. Увеличение производительности векторной части может идти и в направлении увеличения числа процессоров, работающих с каждым модулем памяти, с соответствующим увеличением числа блоков памяти в каждом модуле. Наиболее естественным представляется использование конвейерных процессоров с увеличением их количества до уровня конвейеризации в каждом процессоре и разбиением модуля памяти на блоки таким образом, чтобы элементы одного вектора располагались в разных блоках памяти.

Так, если число модулей N=400, то при 10 блоках памяти (М=10) можно для многих векторов получить увеличение производительности памяти, ее темпа работы в 40 раз по сравнению с темпом работы АП скалярного процессора, содержащего сто модулей. В этом случае коммутатор на выходе и входе модулей памяти и процессоров практически не требуется - он вырождается в сборку, а коммутация реализуется по временному принципу. Это наиболее реальный путь построения векторного ИУ, так как при одной и той же элементной базе темп работы скалярной части всегда будет соизмерим с векторной (Рис.1). Традиционный путь снижения числа обращений к ОЗУ за счет сверхоперативной памяти в данном случае малоэффективен ввиду того, что мы не имеем информации, даже вероятностной, на основании которой можно было бы принять решение о сохранении результатов в сверхоперативной памяти для дальнейшей работы: векторные команды, как было сказано ранее, выдаваемые скалярным процессором векторному для исполнения, никак алгоритмически не связаны между собой, так как их появление во времени непредсказуемо.

Таким образом, в векторном процессоре с каждым модулем памяти связан один или несколько векторных микропроцессоров. Число таких модулей равно формату ОЗУ и составляет 200-400 единиц. Управление процессорами происходит

143

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

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

Рис.1. Базовая схема векторного процессора

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

Выполняя операцию обмена векторами между векторным ИУ и скалярным процессором, управляющий процессор считывает или записывает вектор в ОЗУ и через буфер векторов осуществляет обмен векторами между векторной и скалярной частями суперЭВМ. Управляющий процессор осуществляет контроль за количеством обращений к вектору и, если необходимо, удаляет его. Фактически управляющий процессор выполняет также функции операционной системы по распределению памяти (Рис.1).

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