Рассмотрение различных приёмов программирования при фиксации ресурсов ПЛИСов на Colamo на примере решения задачи суммирования элементов массива

На примере программирования задачи суммирования элементов массива разберём некоторые приёмы программирования на языке Colamo.

Вводные замечания

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

Постановка задачи

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

Структура, получающаяся при использовании одной накапливающей переменной

Рассмотрим вычислительную структуру¹, в соответствии с которой реализовано последовательное суммирование, использующее одну накапливающую переменную, но задействующее весь выделенный ресурс - все восемь сумматоров:

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

Правильная структура организации суммирования

Рассмотрим более правильную (связную по потокам и не простаивающую) вычислительную структуру¹:

Данная структура во многом похожа на предыдущую. Здесь также используются 8 сумматоров, но последний сумматор имеет обратную связь, на которой стоит регистр для хранения промежуточных сумм. Этот сумматор выполняет подсуммирование результатов. Главное отличие данной структуры от предыдущей в том, что на эту структуру элементы массива могут подаваться по мере их поступления, и сумматоры работают все время, а не ждут когда придет результат по обратной связи. Результат задерживается только на одном, последнем сумматоре, где ему надо ждать вычисления предыдущей частной суммы, а суммирование на всех остальных сумматорах выполняется аналогично предыдущей структуре. Если бы задержка на сумматоре составляла 1 такт, то структура работала бы в потоке и давала бы возможность увеличить длину "конвейера" всех вычислений². В дальнейшем будут рассмотрены способы, которые позволят обеспечить плотный поток для таких структур. В отличие от предыдущей, данная структура работает в 8 раз³ быстрее и эффективнее, поскольку не простаивает.

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

¹Под структурой здесь везде понимается набор вычислительных ресурсов (в данном случае сумматоров) ПЛИС, со связями между ними. Она не имеет ничего общего со структурами данных в обычных языках (типа Си, Паскаля и т.п.)
² Вообще говоря, сумматоры в ПЛИСах сами по себе являются конвейерами. Например, количество ступеней в 32-битной реализации суммирования с плавающей запятой на ПЛИС типа Virtex4 равно 18.
³Эта оценка, как и утверждение "не простаивает", не учитывает использования конвейерности самих сумматоров (см. предыдущее примечание). Ясно, что при полной синхронизации потоков данных увеличение производительности может быть гораздо большим. (8*18=144). Однако для этого, даже если б была проведена виртуозная синхронизация потоков с работой сумматоров,  необходимо сведение разнесённых на 1 такт потоков результатов в одну сумму, что требует дополнительной вычислительной структуры, которой мы на рисунке не видим.

Последовательное суммирование всего массива

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

Program SimpleSumArray;

End_Program.

Здесь N и M - размерности массива, N1 и M1 - индексы для организации циклов. ResSum - мемориальная переменная для хранения результата суммирования. Sum - регистровая переменная для организации подсуммирования. Организованы два вложенных цикла: первый - по элементам потоков, второй - по элементам вектора. Структура вычислений в этом примере реализуется следующим образом: стоит один регистр, один сумматор, затем - мультиплексор, который выбирает нужные элементы массива, поступление которых на вход мультиплексора регулируется с помощью задержек. Подчеркнём, что это регулирование выполняется в кадре транслятором автоматически, с учётом типов размерности массива Arr. Само собой, что при такой простоте программы реализация самого медленного способа суммирования останется таковой и при реализации на ПЛИСах: параллельная (по векторной размерности массива) подача потоков не даст нам никакого выигрыша, они будут простаивать очень долго, пока не истекут необходимые времена задержек..

Пирамида сумматоров (сдваивание)

Теперь рассмотрим суммирование элементов массива с помощью пирамиды сумматоров.

EndSubCadr;

Результат суммирования out_com, получаемый после выполнения подкадра на каждой итерации цикла, подсуммируется со значением, которое содержится в регистровой переменной sum.

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

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

Последовательное суммирование элементов массива

Рассмотрим следующий пример программы, реализующей последовательное суммирование элементов массива.

В кадре Sum1 организуется цикл по элементам потока. В теле цикла вызывается структура A, которая задана с помощью конструкции Let. В качестве входных параметров структура¹ A принимает элементы входного массива x - вектор за вектором, а так же переменную cm1. В качестве результата структура A возвращает модифицированную переменную cm1, которая сохраняется в мемориальной переменной summa.

Рассмотрим структуру A. Сначала выполняется инициализация регистровой переменной rg, которая необходима для подсуммирования результатов. В нее записывается входной параметр s, который в начальный момент времени равен нулю. Далее организуется цикл по переменной j до переменной chan_p, которая определяет количество порций каналов по 8. В данном случае таких порций две: в одной восемь каналов, в другой - два. В данном цикле организован цикл по переменной i до переменной chan_m, которая задана константой и равна 8. Это количество каналов в j-й порции. Если номер канала меньше 10, поскольку это общее количество каналов, то выполняется подсуммирование с предыдущим результатом.

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

Использование пирамиды сумматоров

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

endlet;

В данной программе основной кадр Sum1 полностью аналогичен тому, который использовался в предыдущем примере, поэтому мы не будем его приводить. Рассмотрим структуру A, которая реализует суммирование с помощью пирамиды сумматоров. Структура A во многом аналогична соответствующей структуре предыдущего примера. В то же время, цикл по переменной i в данном случае выполняется до значения chan_m/2. В теле цикла используются два оператора if, которые выполняют суммирование элементов в зависимости от их номеров в массиве. Далее организуется пирамида сумматоров и выполняется подсуммирование результата, полученного с пирамиды сумматоров, с предыдущим результатом. Результат накапливается в регистровой переменной rg.

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

И снова - последовательное суммирование элементов массива

Рассмотрим пример программы, реализующей последовательное суммирование элементов массива.

program Test_5;//Сумма последовательно

end_program.

Для данного примера массив разделен на восемь. Сначала вычисляется результат для самого первого сумматора последовательности c[0], а дальше выполняется последовательное суммирование. Для накопления результата используется регистровая переменная sum. Стоит отметить, что в данной программе не используется оператор if. Программа компактная и легко читается, и полностью соответствует описанной выше структуре. Вместе с тем в ней остались проблемы, связанные с фиксированным заданием первой размерности суммируемого массива.

Возвращаемся к пирамиде сумматоров

Рассмотрим пример программы, реализующей суммирование элементов массива с использованием пирамиды сумматоров.

program Test_4;//Сумма пирамидой

end_program.

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

Комбинация пирамиды и последовательности

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

4 сумматора

Рассмотрим пример программы, реализующей последовательное или пирамидальное сложение с использованием 4-х сумматоров:

Здесь использован подкадр, в котором реализовано либо последовательное суммирование (закомментировано в программе), либо пирамида сумматоров. Оба варианта используют 3 сумматора. Однако возникает вопрос насчет естественного порядка при последовательном суммировании. Где гарантия, что будет соблюден естественный порядок? В данном случае лучше использовать скобки, которые жестко зададут естественный порядок суммирования элементов (Result := ((FirstEl+SecondEl)+ThirdEl)+FourthEl;).

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

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

а для других архитектур могли бы ещё наэкономить, разбив внешний цикл на основную часть (делящуюся на 4) и остаток, в котором и сосредоточились бы все проверки условий. Однако будет ли подобная оптимизация действительно экономной для ПЛИС?

Оказывается, нет.
В приведенном первым фрагменте написано более правильно. Это связано с особенностью структурной реализации условного оператора: при структурной реализации оператора условного выбора if - then - else структурно реализуются обе ветки условия (и для then, и для else), а на выход выдается результат с мультиплексора, объединяющего результат вычислений, на управляющий вход которого подаётся результат вычисления условия if (как и в примере из описания языка Коламо). Дополнительно к этому, все вычисления в теле кадра выполняются с максимально возможной степенью параллелизма, если между ними нет информационной зависимости. Поэтому для приведенного примера, где I - векторная компонента, а J - потоковая, произойдет распараллеливание внутреннего цикла, содержащего условие, по числу векторных компонент внешнего цикла (т.е. при N1 = 9 будет 3 внутренних цикла, каждый из которых содержит условие из 4 веток. Итого - циклов 3, условий 3, подкадр 1). В предлагаемом в качестве более экономной альтернативы втором варианте произойдет распараллеливание оператора условия, содержащего 4 цикла и вызовы структурной составляющей подкадра Sum4Vect, что приведет к существенному увеличению занимаемого аппаратного ресурса (при N1 = 9 будет 3 условия, каждое из которых содержит 4 цикла и 4 подкадра. Итого - циклов 12, условий 3, подкадров 12). Скорость выполнения обоих рассматриваемых вариантов одинакова, но второй вариант занимает вычислительный ресурс в 4 раза больше, чем первый и поэтому обладает меньшей эффективностью. При программировании на Colamo нельзя пользоваться общепринятыми для фон-неймановских архитектур критериями эффективности программы, поскольку в расчет кроме компактности записи и скорости реализации необходимо также принимать критерий используемого ресурса оборудования. Поэтому важно вовремя остановиться на скользком пути оптимизации в стиле последовательного программирования, когда имеешь дело с программированием для ПЛИСов.

8 сумматоров

Ниже приведен пример программы, реализующей последовательное и пирамидальное сложение с использованием 8-ми сумматоров:

Program SumArray_8Sum;

Как и в случае с пирамидой суммирования из 4 сумматоров, в данной программе на первый взгляд может показаться не вполне экономной организация заполнения данных для основного подкадра, использующего 7 сумматоров из 8, но, как и в пирамиде для 4 сумматоров, это только кажется привыкшим к традиционному стилю программирования. Вместе с тем отметим, что эта проблема не настолько важна, как проблема универсальной настраиваемой масштабируемости по ресурсам, которые у нас будут в распоряжении. В этом плане, конечно, данная программа выглядит не так коряво, как уже рассмотренная выше, но по сути в ней осталась заложена немасштабируемость ресурсов. Хотя главной задачей для нас здесь при рассмотрении примеров было понять, как вообще ограничиваются используемые в ПЛИС ресурсы при программировании, отметим, что проблема масштабируемости не так сложна, как кажется. Скажем, при программировании пирамиды на 16 сумматоров можно использовать приведённую ниже программу (причём мы видим, что в ней число 16 вовсе не существенно - вместо него может быть параметр, равный как 1024, так и 2²⁰ и даже более):

Как ограничиваются ресурсы при программировании на Colamo

Рассмотрим задачу суммирования элементов массива, для решения которой имеется 4 сумматора и множество каналов распределенной памяти, например, 24, и при этом нет потока.

DCL A [ 24 : vector ]

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

Add(R, R', a)
dcl R, R' : com;
dcl a : [4 : vector] com;
R':=R+a1+a2+a3+a4

Как нужно обратиться к подкадру Add, при условии, что входной параметр - вектор, а также чтобы не произошло размножение элементов add? Если написать фрагмент:

R[0]:=0
For i:=1 to 5 do
Add (R[i-1], R[i], a[i*4-3]) ,

то здесь R - информационно-независимые коммутационные переменные, A - вектор. При организации цикла элементы распараллелятся, в результате чего потребуется 24 сумматора. Это произойдет, если приведенный выше фрагмент кода будет находиться в теле кадра:

R[0]:=0
cadr
for i:=1 to 5 do
Add (R[i-1], R[i], a[i*4-3])
endcadr

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

R[0]:=0
for i:=1 to 5 do
begin
cadr
Add (R[i-1], R[i], a[i*4-3])
endcadr
end;

Поэтому введение в программу, реализующую последовательное и пирамидальное сложение с использованием 8-ми сумматоров, переменной Stream18VectorArr, которая предотвратит распараллеливание, абсолютно оправдано.

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

Большой половник дёгтя в бочку и так не высшего качества мёда

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

Заключение

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

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

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

• выполнения условных операторов,
• распределения ресурсов ПЛИСов,
• использования коммутационных переменных,
• организации задержек транслятором.

© Лаборатория Параллельных информационных технологий НИВЦ МГУ