ИТМиВТ - Институт точной механики и вычислительной техники С. А. Лебедева РАН
Институт точной механики и вычислительной техники им. С. А. Лебедева РАН - научно-исследовательский институт в области информационных технологий, вычислительной техники и микроэлектроники
English
Главная страница Контактная информация Карта сайта и поиск
Об институте Решения Проекты Образование

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

А.В. Климов, А.С. Окунев, А.М. Степанов

Модель вычислений dataflow имеет огромные преимущества перед фон-неймановской моделью в теоретическом плане. Об этом много написано, и это всем известно [2,3]. Однако эффективной конкурентоспособной реализации такой модели вычислений нет до сих пор. Существуют исследователи, которые проанализировали причины неконкурентоспособности dataflow систем и определили два фундаментальных недостатка, которыми страдают все dataflow системы:
  • отсутствие иерархии памяти;
  • наивный подход к планированию (основной действующий принцип: если данные для вычисления готовы, — выполняй его).

В ИТМиВТ им. С.А.Лебедева продолжаются работы, связанные с поиском подхода к решению именно этих двух проблем. Предложена модель вычислений, которая является обобщением dataflow и сохраняет все положительные теоретические свойства этой модели. Но, кроме того, эта новая модель имеет потенциальные архитектурные преимущества перед dataflow, которые дают надежду решить эти две практические проблемы и вывести это направление из тупика.

Базовая модель вычислений была реализована в проекте ИПИ РАН коллективом под руководством академика Бурцева В. С.[1]. Были созданы система команд, язык ассемблера и собственно ассемблер, язык повышенного уровня (язык модели) DFL и соответствующий компилятор, программная модель системы и макет на ПЛИС.

Основным принципом реализации модели являлось использование ассоциативной памяти, прежде всего для сопоставления токенов, с целью обнаружения полных наборов (пар) входных токенов вычислительных элементов, а также для временного хранения тех токенов, которые еще не «встретились» со своими партнерами. Для реализации параллелизма, присущего модели вычислений, в системе предусматривалось наличие многих исполнительных устройств (ИУ). В свою очередь, ассоциативная память (АП) была реализована как множество модулей (модули ассоциативной памяти — МАП). Множество ИУ и МАП были соединены при помощи коммутационной среды.

При посылке любого токена работает аппаратно реализованная хеш-функция, которая по адресу вычислительного элемента, содержащемуся в токене, вычисляет номер того МАП, в который данный токен следует послать. Хеш-функция обеспечивает случайно-равномерное распределение токенов по модулям, а также гарантирует, что токены, направленные в один и тот же вычислительный элемент, всегда окажутся в одном и том же модуле, а, следовательно, смогут «встретиться». Предполагалось также, что готовые пары могут выполняться независимо друг от друга, в любом порядке и на любых ИУ.

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

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

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

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

В качестве первого шага к решению проблемы аппаратной локальности предлагается следующая аппаратная структура системы:

  • ИУ и МАП объединяются в одну аппаратную единицу — модуль;
  • через коммутационную среду передаются только токены. Пары, формируемые в локальной ассоциативной памяти модуля, передаются на исполнение только в «свое» ИУ; 
  • предполагается, что все связи внутри модуля относительно короткие, связи между модулями — более длинные;
  • структура коммутационной среды может быть неоднородной (то есть связи внутри некоторых групп модулей могут быть короче, чем между модулями из разных групп).

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

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

Программист сам указывает те функции распределения, которые будут использоваться в его программе. При этом ему предоставляются удобные средства задания этих функций. Основная идея — отделить собственно параллельный алгоритм, изложенный на DFL, от распределения выполняемых в соответствии с этим алгоритмом вычислений по модулям системы. Программа состоит из двух относительно независимых частей: описания алгоритма, не учитывающего распределения вычислительных элементов по модулям и дополнительных указаний (в форме прагма-предложений), задающих распределение вычислительных элементов по физическим модулям.

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

  • для решения вышеописанных проблем реализуется новая структура системы (с объединением ИУ и МАП в модуль и исключением коммутации пар);
  • разработаны подходы к приспосабливаемости программ к неоднородной иерархической коммутационной среде;
  • отказ от хеш-функции и переход к управляемой программистом функции распределения вычислений по модулям.

Литература

  1. Бурцев В.С. Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи // Cб. Вычислительные машины с нетрадиционной архитектурой. СуперЭВМ. — Вып. 2. — М.: ВЦКП РАН, 1994. — С.3—37.
  2. Бурцев В.С. О необходимости создания суперЭВМ в России//Cб. статей «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ», М., 1997
  3. Dennis J., Data Flow Supercomputers // Computer. — Vol.13. — No.11. Nov, 1980. — P.48—56

 

УДК 004.272.44
Информационные технологии в науке, образовании, телекоммуникации и бизнесе
(IT + S&E’07)

Секция «Высокопроизводительные вычислительные системы: архитектура и методы организации вычислений»
© 1948—2016 «ИТМиВТ»
Версия для печати Контактная информация