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

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

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

1. Алгоритм решения задачи, описанный на третьем этапе, представляется графом вычислительного процесса без переиспользования цепей графа для различных данных (Рис.4.).

Рис.4 Граф вычислительного процесса.

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

2. Обработка данных в соответствии с последовательностью, определяемой графом, ведется по мере готовности операторов к выполнению соответствующей обработки данных, т.е. наличия необходимых данных на входе оператора. Считаем, что количество исполнительных устройств не ограничено, а время передачи данных между операторами t << t_oп, где t_oп - минимальное время обработки данных оператором.

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

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

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

1. 
   Требуется значительная избыточность объема памяти за счет хранения возможных ветвей графа, вычислительный процесс по которым не пройдет при реализуемых величинах данных.
   
2. 
   Ввиду того, что имена операторов не повторяются, каждому данному и оператору должен быть придан уникальный номер (адрес). В этом случае поле адреса в команде может превысить поле данных, что по меньшей мере удвоит необходимый объем оперативной памяти.
   
3. 
   Необходимое количество итераций вычислительного процесса заранее, как правило, не известно и определяется в процессе счета по данным. Поэтому граф необходимо "разворачивать" на максимум итераций, который неизвестен.
   
4. 
   Оперативная память для решения поставленных задач должна иметь время доступа менее 1 нс и период темпа приема и выдачи информации менее 10 пс, обладая объемом, намного большим чем 10¹⁵ слов.
   
5. 
   Слишком малый коэффициент использования оборудования. Так, для максимального распараллеливания умножения трехмерных матриц размерностью 100x100x100 требуется 10⁶ умножающих устройств, из которых в среднем будет загружено 100. Еще меньшим коэффициентом загрузки будет обладать оперативная память при большом числе вариантов прохождения программы и неопределенности числа итераций по подпрограммам.
   
6. 
   Чрезвычайно неудобно работать в этой структуре с многократным использованием данного (типа константы).
   
7. 
   Принципиально неразрешимым кажется вопрос работы со структурами данных при одновременном обращении к ним из разных мест графа.
   
8. 
   Чрезвычайно не эффективна, по сравнению с традиционными машинами, работа на участках программ с сильно связанными данными.
   

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

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

50

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

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

В рамках работ по "Оптической сверхвысокопроизводительной вычислительной машине" ОСВМ [5], проводившихся ВЦКП РАН (ныне ИВВС РАН) совместно с ведущими физическими институтами РАН, создана новая нетрадиционная высокопараллельная архитектура вычислительных средств супер-ЭВМ на базе сетевой системы с потоковым принципом обработки данных для решения сложных задач вычислительного класса.

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

Рис.5 Манчестерская машина

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

3. Принципиальные особенности реализации машины потока данных в проекте ОСВМ

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

Особенности реализации обусловлены следующей целью проекта:

51

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

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

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

3.1. Память совпадения на аппаратной основе

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

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

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

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

Векторную память разместить в специальном векторном исполнительном устройстве и выполнить ее с дискретом в 100 слов с прямым доступом по адресам. Векторная память в скалярной машине потока данных представляется памятью массивов (размером не более 10000 слов каждый), имеющих свое виртуальное имя. Каждый такой массив в скалярной машине имеет статус операнда, из которого стандартным способом формируется токен. По готовности таких токенов формируется пакет и запускается операция векторного испытательного устройства (Рис.6).

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

52

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

Коммутатор K₁ производит распределение готовых пакетов токенов по свободным исполнительным устройствам, включая векторные. Готовые пакеты, не находящие свободных исполнительных устройств, сбрасываются в буферную память (БП). Таким образом, в структуру машины введена специальная буферная память прямого доступа достаточно больших размеров, которая хранит избыточную, готовую к выполнению информацию (пакеты токенов) в том случае, когда возникают так называемые информационные "взрывы". Несколько слов о происхождении "взрывов". Из графа видно, что есть операции, которые из двух операндов формируют один операнд, но есть и такие, которые из одного операнда формируют два. Если бы существовали только операции первого вида, то граф свернулся бы к одному узлу. Существование операций только второго вида существенно расширило бы количество параллельно выполняемых операций в принципе до бесконечности.

Рис.6 Блок-схема машины.

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

53

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

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

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

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

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

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

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

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

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

54

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

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

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

4. Особенности программирования и оценка производительности

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

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

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

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

N < n,

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

В этом случае неравенство примет следующий вид:

N х С < n.

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

если NC < n, то полная загрузка;

если NC > n, то загрузка будет пропорциональна соотношению n / NC.

55

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

Необходимо уточнить, что такое NC, например, для структуры, показанной на Рис.6.

NC = (N_прС_пр + N_к1C_кl+ N_k2C_k2+ N_AПC_AП)N_K,

где N_ПР, N_aп, N_k1, N_k2 - количество параллельно работающих устройств процессоров, модулей памяти и коммутаторов в одном канале; Спр, Сдп, С_к1,С_к2 - соответствующие величины глубины их конвейеризации.

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

Из этих соотношений видно, что чем меньше величина NC, тем более эффективно будет работать комплекс при малом параллелизме задачи.

Сравнивая эффективность загрузки традиционных машин с разрабатываемой, можно отметить два положительных фактора: какой бы большой ни была величина параллелизма n и какова бы ни была величина параллельно работающих каналов Nк, автоматически осуществляется предельно возможная загрузка системы. В традиционных системах с увеличением величин n и N возможности человека резко падают, начиная с N = 3-4. Этим можно объяснить то, что пользователи Connection Machine и nCUBE говорят лишь о 10% их средней загрузки на ориентированных на эти машины задачах.

Вторым преимуществом разрабатываемой системы является то обстоятельство, что в традиционных машинах параллелизм выявляется человеком или процессором на небольшом участке программы, не превосходящем, в лучшем случае, десятка команд. Поэтому средний параллелизм во времени исполнения для скалярных операций для таких машин как МВК "Эльбрус-2" не превосходит 2-3, а для векторных конвейерных машин типа Cray не превышает 10 [1,2]. Параллелизм в разрабатываемой машине автоматически определяется на данных всей задачи, находящейся в АП, в векторном ОЗУ и буфере, поэтому, чем больше память машины, тем большая задача может решаться на ней и тем большей будет величина параллелизма во времени, а, следовательно, и вероятность полной загрузки исполнительных устройств, и процент загрузки на участках задачи с малым параллелизмом. Немаловажным является и то обстоятельство, что в принятой нами концепции организации векторных вычислений параллелизм самих векторных вычислений на уровне операций над векторами определяется на скалярном процессоре по всей задаче, а параллелизм самой векторной операции над элементами вектора равен количеству элементов в векторе, длина которого может быть до 10 тысяч.

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

56

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

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

Рис.6а. Многопроцессорный комплекс на базе суперпроцессоров.

Используя тот же принцип организации вычислительного процесса и рассматривая описанную выше систему потока данных, как один суперпроцессор, можно создать своеобразный многопроцессорный комплекс (Рис.6а). В этом случае определенные разряды адресации данных (I,П,T,NK) необходимо использовать для распределения токенов по суперпроцессорам. Очевидно, что такая многоступенчатая структура распределения токенов сначала между суперпроцессорами, а затем по модулям памяти внутри него, существенно замедлит вычислительный процесс только в том случае, если будут необходимы частые передачи данных, в особенности векторных, между суперпроцессорами. Если распределение задач между машинами возложить на человека, то можно ожидать, что в основном работа по распределению токенов между модулями памяти будет идти внутри машины. Безусловно, как и в традиционных комплексах, человеку справиться с этой задачей при числе суперпроцессоров более 10-ти будет достаточно сложно, несмотря на то, что ему придется распределять между ними достаточно локализованные крупные куски задачи. Подобные