Современные информационные технологии/1. Компьютерная  инженерия

Д-р техн. наук, профессор И. И. Левин, канд. техн. наук Ю. И. Доронченко,

канд. техн. наук А. К. Мельников

Научно-исследовательский институт многопроцессорных вычислительных систем имени академика А. В. Каляева Южного федерального университета, Таганрог

Эффективная реализация алгоритмов с глубокими циклами на реконфигурируемых вычислительных системах*

Введение

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

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

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

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

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

Пусть задан конвейеризованный информационный граф задачи , состоящий из подграфов , , , …, , кортежной входной информационной вершины (здесь и далее в угловых скобках обозначаем кортежные вершины, за вертикальной чертой – число информационных вершин в кортеже) и кортежной выходной информационной вершины , причем между подграфами , , существует такая информационная зависимость, при которой между вершинами и существует дуга . Кроме того, существуют дуги, соединяющие каждую входную вершину со всеми подграфами , , , …, . На рис. 1 показан информационный граф задачи. Для простоты рассуждений будем полагать, что других информационных зависимостей не существует:

, , ,

Рис. 1. Информационный граф задачи

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

for a(n) = 0 to m.

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

Определим для простоты размер цикла обработки значений последовательности (количество элементов кортежа) как .

Рис. 2. Синхронизация данных в конвейере

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

,

где τ – время следования операнда;

– время настройки вычислительной структуры.

Аппаратные затраты (число одноразрядных элементов задержки на один временной отсчет) на построение линии задержки определяются по формуле

.

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

Исходная последовательность разбивается на две последовательности

.

Последовательность – постоянная часть последовательности , а последовательность разрядности – переменная часть последовательности . Задача решается в 2^n−v (если граф не распараллелен) кадров. Под кадром будем понимать выполнение задачи с текущей настройкой вычислительной структуры. В каждом кадре структура вычислительной системы настраивается на обработку в цикле значений переменной части при одной и той же постоянной части . Пример выполнения кадра задачи представлен на рис. 3. Такая обработка может быть представлена в виде вложенного цикла:

for ac(n − v) = 0 to 2^{n − v};

for a(v) = 0 to 2^v.

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

Рис. 3. Выполнение кадра задачи

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

;

.

Для минимизации аппаратных затрат целесообразно уменьшать разрядность переменной части , однако необходимо учитывать, что с ростом числа кадров задачи время на настройку структуры (накладные расходы) увеличивается. Следовательно, и время решения задачи увеличивается, причем если выбрана небольшая разрядность переменной части, то это увеличение весьма существенно:

.

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

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

Литература

1. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры / под общ. ред. И. А. Каляева. 2-е изд., перераб. и доп. Ростов-н/Дону : Изд-во ЮНЦ РАН, 2009. 344 с.

______________________________________

*Работа выполнена при финансовой поддержке Министерства образования и науки РФ по Соглашению о предоставлении субсидии №14.578.21.0006 от 05.06.2014, уникальный идентификатор RFMEFI57814X0006, гранту Южного федерального университета №213.01-2014/014 и НИР №2257 базовой части государственного задания №2014/174.