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

Иерархическая ассоциативная память в вычислительной системе массового параллелизма

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

Предложенная в работе [1] архитектура вычислительной системы массового параллелизма, поддерживает модель вычислений, основанную на управлении данными (data driven computation): вычисление операции (программы узла) активизируется появлением операндов на всех входах узла. Следствием этого принципа является необходимость использования глобальной ассоциативной памяти для сопоставления токенов-операндов, что порождает следующие проблемы:
  1. Во избежание блокировки системы, связанной с переполнением АП, требуется потенциально очень большой объем АП, хотя реально используется лишь небольшая ее часть.
  2. Ограниченная производительность в связи с необходимостью выполнять обработку запросов последовательно.
  3. Энергия, потребляемая АП в режиме поиска очень велика, поскольку необходимо выполнять сравнение со всеми хранимыми ключами, а не только с тем, который совпадет.

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

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

Однако ограничение объема осталось, и даже усугубилось, поскольку переполнение любого из модулей делает невозможным дальнейшее выполнение программы (несмотря на то, что другие МАП могут оставаться заполненными слабо).

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

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

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

Ячейки, содержащие ключ и дескриптор являются перемещаемыми: МАП может их по своему произволу переместить в другую свободную ячейку, освободив исходную. Но если дескриптор не записан, этого делать нельзя, поскольку еще может прийти команда на запись дескриптора в ячейку с заданным внутренним адресом. Соответственно, такие ячейки являются неперемещаемыми. Если при поиске найдена неперемещаемая ячейка, то возвращается не дескриптор, а ее внутренний адрес и признак, что это именно адрес. Перемещаемость служит для втягивания более «нужных» ключей из медленных уровней в более быстрые и наоборот.

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

Формат входной информации для поиска:

КОП Локатор (10р.) КЛЮЧ (64р.)

Иерархическая АП — это возможная реализация АП, которая обеспечивает ее более эффективную работу. Все ее ячейки разбиты на уровни, как показано на Рис.1. На каждом уровне ячейки могут объединяться в слоты. На уровне 0 имеется столько слотов, сколько адресов задает входной локатор. Для 10-разрядного локатора это 1024. В каждом слоте 0-го уровня по 1 ячейке, то есть по 1 ключу. Команда поиска выполняется последовательно по уровням. Сначала проходим уровень 0. Здесь выполняется чисто адресный доступ. Если в ячейке с соответствующим адресом лежит ключ, он сравнивается с входным ключом. При совпадении формируется отклик и процесс завершается. Если совпадения нет, то поиск может быть продолжен на уровне 1 в слоте, номер которого получается отрезанием младшего бита локатора. В этом слоте уже 4 ячейки, он «обслуживает переполнение» в одном из двух слотов 0-го уровня. Здесь выполнятся 4-х канальный ассоциативный поиск. Если и здесь искомого ключа нет, возможен поиск в соответствующем слоте из 16 ячеек на уровне 2 и т.д.

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

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

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

Общее число уровней равно числу разрядов локатора плюс 1. На последнем уровне размер слота равен квадрату числа различных локаторов. Общее число ячеек вдвое больше этого количества. Таким образом, при 10-разрядном локаторе будет 2 миллиона ячеек, для адресации которых потребуется 21-разрядный регистр.

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

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

Рис. 1. Структура 5-и уровневой АП. На уровне 0 находятся 16 слотов по 1 ячейке в каждом слоте. На уровне 1 — 8 слотов по 4 ячейки. На уровне 2 — 4 слота по 16 ячеек. На уровне 3 — 2 слота по 64 ячейки. На уровне 4 — 1 слот из 256 ячеек. Всего — 496 ячеек. Поиск для ключа с локатором 5 проходит по темным областям.

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

В работе [2] высказывались идеи, связанные с реализацией подобного вида памяти, состоящей всего из двух уровней (в нашей интерпретации — 0-го и последнего), здесь же предлагается вариант реализации иерархической АП с любым количеством уровней и с единой адресацией. То есть при реализации такой ИАП фактически представляется возможным создание полноценной виртуальной ассоциативной памяти для параллельной потоковой вычислительной системы, работа которой базируется на модели вычислений с управлением потоком данных.

Литература

  1. Бурцев В.С. Новые принципы организации вычислительных процессов высокого параллелизма // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы — 2003». Т.1. Таганрог: Изд-во ТРТУ, 2003.
  2. Хайлов И.К. Варианты использования оперативной прямоадресуемой памяти и кэш-памяти в потоковой ЭВМ // Вычислительные машины с нетрадиционной архитектурой.Супер ВМ. Сборник научных трудов ИВВС РАН, выпуск 7, Москва, 1998. С. 31—39.

 

© 1948—2016 «ИТМиВТ»
Версия для печати Контактная информация