Описание языка программирования COLAMO

Содержание

• Вводная часть
• Вычислительные структуры
  • Кадр
  • Операторы присваивания
  • Операторы безусловного перехода
  • Параллелизм в кадрах
    
  • Переменные языка
  • Массивы
  • Оператор цикла
  • Выборки массивов
  • Буферизация потоков
  • Условный оператор
  • Подкадры
  • Подструктуры
  • Подпрограммы
  • Массивы кадров
    
  • Подключения
    
• Заключение
• Приложения
  • Проблемы условных операций и принципа однократного присваивания в языке COLAMO
  • Проблемы, связанные с рекурсивными алгоритмами при их записи на языке COLAMO
  • Рассмотрение различных приёмов программирования при фиксации ресурсов ПЛИСов на COLAMO на примере решения задачи суммирования элементов массива
  • Примеры
    • Быстрое преобразование Фурье на языке COLAMO

Вводная часть

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

• Язык должен эффективно реализовываться на различных МВС;
• Иметь средства для записи алгоритмов без изменения их начальной параллельной структуры;
• Язык должен позволять программисту максимально просто описывать различные виды параллелизма, реализованные в МВС, в достаточно сжатом виде;
• Cодержать мощные конструкции, как в традиционных ЯПВУ типа Фортрана, Си и т.п.

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

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

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

Операторы языка программирования делятся на три группы:

• операторы описания вычислительных структур;
• операторы управления вычислительным процессом;
• операторы описания данных и программно-аппаратных ресурсов.

Вычислительные структуры

Кадр

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

В общем случае кадр задается следующим образом:

CADR name;
P
ENDCADR;

где СADR, ENDCADR - ключевые слова языка;
name - имя кадра;
P - список операторов (тело) кадра.

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

Операторы присваивания

Операторы присваивания имеют вид:

Name:=f;

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

Операторы безусловного перехода

Операторы безусловного перехода имеют вид

goto lab;

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

Параллелизм в кадрах

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

Переменные языка

В рассматриваемом языке переменные языка Colamo разделяются по "способу хранения" на мемориальные (MEMory), внутренней памяти (InterMem), коммутационные (COMmutation) и регистровые (REGister). Вне кадра для программиста доступны только значения мемориальных переменных.

Такое разделение типизации переменных по способу их хранения связано с тем, каким образом после трансляции они будут связывать между собой операции программы. Внутри вычислительных структур передача данных обычно не требует хранения, поэтому такие переменные (коммутационнные) являются только символами, с помощью которых мы, программируя, соединяем каналами связи выходы одних схемотехнических устройств (или их групп) с входами других. Однако бывает, что такая непосредственная передача данных между устройствами невозможна, поскольку устройство-"потребитель" данных ещё не готово к приёму, и нужно реализовать задержки. Для таких целей служат регистровые переменные.  Не следует по этому названию думать, что им соответствует какой-то быстрый тип памяти (такой, как регистры в обычных ассемблерах или Си) - как и коммутационные, регистровые переменные тоже только дают связь между устройствами, их отличие в том, что на этих линиях связи расположены дополнительные устройства задержки. Вне микросхем ПЛИСов располагается память, управляемая КРП. Для того, чтобы брать оттуда данные для вычислений, а также для того, чтобы сохранять туда результаты, введены мемориальные переменные.
Когда разрабатывался язык Colamo, на чипах ПЛИСов ещё не было собственной (внутренней) памяти, поэтому сначала  не был введён тип переменной, соответствующий хранению данных в ней. Разработчиками языка, однако, уже в 2008 г. было заявлено намерение о включении в язык нового типа. В июне 2009г. в язык был включён новый "способ хранения" - InterMem.

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

Переменная внутреннего хранения (на настоящий момент эти переменные ещё не поддерживаются транслятором языка) - величина, хранящаяся в ячейке внутренней памяти чипа ПЛИС, и также сохраняющая свое значение до очередного переприсваивания. Введение этого типа связано с появлением внутренней памяти чипов ПЛИС.

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

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

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

A=B_*C+D-K/L+S;
B2=B_*C+D-K/L-S;

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

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

Как видно из рассмотренного примера, введение дополнительной промежуточной переменной позволит значительно уменьшить объем оборудования (количество ЭП), необходимого для построения вычислительной структуры. Значения коммутационной переменной недоступны пользователю, данное имя "сцепляется" с вершиной графа, соответствующей элементарному процессору по аналогии с "сцеплением" (hoked), реализованному в языке Пролог. Возможно аналогичным образом получить программу и без использования коммутационной переменной, но с использованием промежуточной мемориальной переменной (рис.1б). В этом случае граф эквивалентен предыдущему, но используется дополнительная ячейка памяти для хранения промежуточных вычислений Z, и время решения задачи увеличится для третьего варианта по сравнению с предыдущими, т.к. необходимо осуществить запись с транзитов в ячейку Z.

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

Z=B*C+D-K/L;

А=Z+S;

выполнится первой.

Следовательно, неизвестно, корректной ли будет организация вычислений в кадре, представленном на рис.1в, или ошибочной. Величина А может быть получена как из старого значения Z до выполнения оператора Z=B*C+D-K/L, так и после него.

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

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

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

В самом деле, запись

X[i]=f(X[j])

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

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

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

CADR S1;
Z=B*C+D-K/L;
ENDCadr;

CADR S2;
A=Z+S;
B2=Z-S;
ENDCadr;

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

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

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

Var p₁, p₂,..., p_n: a_n;

где p_i - список переменных i-й группы, для которых установлены соответствующим списком характеристики a_n, Var - ключевое слово языка.

Элементы списка переменных разделяются запятыми. Элементы списка характеристик переменных разделяются пробелами. К характеристикам переменных относятся: способ "хранения в памяти" (Mem - мемориальная, InterMem - на внутренней памяти, Reg - регистровая, Com - коммутационная, по умолчанию - мемориальная), а также тип переменной (REAL - вещественная, COMPL - комплексная, CHAR - символьная, ADDR - адресная, LOGIC - логическая, CONTR - управляющая, INTEGER - целая, NUMBER - целая для параметров циклов, BIT - битовая, по умолчанию - REAL).

Для битовых переменных в Colamo, кроме логических операций (And, Or, Xor) введены такие битовые операции, как ShL, ShR, ShLC, ShRC.

Массивы

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

Описание массивов в общем случае имеет синтаксис

Var p₁, p₂,..., p_n: Array TypeVariable [a₁,a₂, ... , a_n] Access;

где p_i – переменная из списка объявляемых переменных, a_i - характеристики i-й размерности массива, TypeVariable - тип переменной массива, Access – "способ хранения" переменной.

В COLAMO массивы различаются по способу обработки на векторы (Vector) и потоки (Stream); аналогичные предложения были реализованы в языке программирования IVTRAN. По умолчанию массивы считаются векторами. Потоками являются массивы переменных, элементы которых могут быть обработаны только последовательно. Векторами являются массивы переменных, элементы которых могут быть обработаны параллельно.

На рис.2 и рис.3 представлены программы, являющиеся граничными примерами извлечения параллелизма, и графы ВС, в которые они будут оттранслированы.

На рис.2 приведена программа, реализующая суммирование двух векторов полностью параллельно, на рис.3 - полностью последовательно.

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

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

Кадр s эквивалентен следующему:

CADR summa;
FOR i=1 TO 10 DO
C[i]=A[i]+B[i];
ENDCadr;

где FOR - оператор цикла.

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

Оператор цикла

Оператор цикла COLAMO в общем случае имеет следующий вид:

FOR [j=i1] [TO i2] [STEP i3] [WHILE i4] BEGIN p END;

где FOR, TO, STEP, WHILE - ключевые слова языка;
j - имя переменной цикла;
i1 - список начальных значений переменной цикла;
i2 - выражение, определяющее предел приращений переменной j;
i3 - приращение переменной цикла;
i4 - логическое выражение, при невыполнению которого производится выход из цикла;
BEGIN и END - синтаксические скобки, ограничивающие тело цикла;
р - список операторов цикла.

Любые конструкции данной записи, ограниченные квадратными скобками, могут отсутствовать. Если в теле цикла находится один оператор, то могут отсутствовать и синтаксические скобки группового оператора BEGIN и END.

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

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

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

Таким образом, внешний оператор цикла эквивалентен оператору цикла стандартных языков программирования.

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

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

Var A,B,C: Array [2: Vector, 5: Stream];
CADR summa3;
C=A+B;
ENDCadr;

В этом случае массивы А, В, С будут располагаться в двух каналах распределенной памяти, и в каждом канале будет расположено по пять элементов. Для случая, изображенного на рис.3, массивы А, В, С располагаются в 10 каналах памяти, в каждом из которых расположено по одному элементу массива. Для случая, представленного на рис.2, все десять элементов массива располагаются в одном канале распределенной памяти. Запись, приведённая выше,предпочтительна для реализации. Здесь, как и в программе, приведенной на рис.4, будут работать только два ЭП, но в обработке вычислений не будет разрывов, которые требуются для перенастройки кадра summa. Кроме того, коммутация во время выполнения программы остается неизменной. Коммутация в вычислительных структурах, соответствующих программе на рис.4, будет изменяться с каждой перенастройкой кадра summa (необходимо обеспечить доступ между элементарными процессорами и новой парой каналов, в которых хранятся следующие элементы векторов А, В, С).

Только что приведённую программу можно записать в развернутом виде:

Var A,B,C: Array [2: Vector, 5: Stream
CADR summa4;
FOR i=1 TO 5 BEGIN
  FOR j=1 TO 2 BEGIN
    C[i, j]=A[i, j]+B[i, j];
  END;
END;
ENDCadr;

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

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

Var A,B: Array [4, 4: Stream, 4, 4: Vector];
CADR tran;
FOR I=1 TO 4
  FOR J=1 TO 4
    FOR K=1 TO 4
      FOR L=1 TO 4
        B[I,J,K,L]=A[J,I,L,K];
ENDCadr;

Из четырех циклов в теле кадра в структурный компонент (в данном случае в каналы обмена между модулями распределенной памяти исходной матрицы А и результирующей матрицы В) будут преобразованы циклы по переменным K и L, которые осуществляют транспонирование элементов клетки матрицы, причем все перестановки производятся одновременно по 16 информационным каналам.

Циклы по переменным I, J отображаются в процедурный компонент и соответствуют транспонированию матриц на уровне клеток 4 на 4, причем в каждый момент времени происходит только одна пересылка.

Выборки массивов

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

A[b:k:s]

где А - имя массива;
b - значение индекса, определяющее начало выборки;
k - значение индекса, определяющее конец выборки;
s - значение шага индекса в выборке.

Все параметры являются позиционными. При пропуске любого параметра, кроме последнего, необходимо ставить определенное количество двоеточий. По умолчанию начальный индекс выборки равен начальному значению в описании массива, k - конечному значению в описании массива. Например, запись A[i, 4:8] означает, что производится выборка по второй координате массива, начиная с 4-го по 8-й с шагом 1.

Запись A[-2:3,15:100:21]; определяет выборку на пересечении следующих индексов: первого - от -2 до 3 с шагом 1, второго - от 15 до 100 с шагом 21. В общем случае массив описывается следующим образом:

Var A: Array S [p1, p2, ... , pn] M

где А - имя массива;
pi - характеристики i-й размерности массива;
S - тип переменной массива;
M - "способ хранения" массива.

Характеристика размерности имеет вид: a:d t, где а - начальное значение индекса; b - конечное значение индекса; t - способ обработки размерности. По умолчанию а считается равным единице.

Шаг выборки может быть отрицательным, если b<k. Выборка всего массива определяется по его имени без скобок. Выборка по одной координате определяется символом _* (A[B,_*], A[::2,_*]), в этом случае выборка будет называться срезом. Cтруктурное отображение выборки определяется типом обработки компонента массива, по которому производится выборка (срез). Для векторной составляющей массива выборка соответствует определенным номерам каналов распределенной памяти, которые одновременно выставляют (считывают) данные на вычислительную структуру. Для среза потоковой составляющей данные считываются (записываются) во все каналы распределенной памяти, которые соответствуют массивам. Для потоковой составляющей выборка определяет цикл обращения к ячейкам памяти в каналах распределенной памяти, в случае среза - последовательное обращение ко всем элементам распределенной памяти.

Массивы переменных могут быть как мемориальные, внутренней памяти, коммутационные, так и регистровые. Коммутационные векторы представляют собой группу информационных каналов, которым присвоено одно имя. Коммутационный поток позволяет организовать запаздывание операндов. На рис.5 приведены программы на языке программирования высокого уровня и графы вычислительных структур, в которые они будут оттранслированы. Жёлтыми квадратиками обозначены задержки.

Буферизация потоков

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

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

Следует отметить, что если в программе встречается, например, следующая ситуация:

Var X: Array [100: Stream];
CADR ST;
FOR i=1 TO 50
C=X[i]+X[j];
ENDCadr;

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

В противном случае невозможно осуществить неявную буферизацию.

Пусть требуется вычислить A_i=(B_i+B_i-1)_*C. Программа, реализующая данные вычисления, может выглядеть следующим образом при использовании неявной буферизации:

Var A,B,C: Array [4: Stream];
CADR A;
FOR i=2 TO 4
A[i]=(B[i]+B[i-1])*C[i];
ENDCadr;

Ниже приведена программа, реализующая тот же пример, но уже с явно заданной буферизацией:

Var A,B,C: Array [4: Stream;
Var R REG;
CADR BO;
R=C[1];
ENDCadr;

CADR B;
FOR i=2 TO 4 BEGIN
A[i]=(B[i]+R)*C[i];
R=B[i];
END;
ENDCadr;

На первый взгляд мы имеем дело с нарушением корректности данных: чтение и запись одной переменной происходят в теле кадра, однако, идентификатор R описывает регистровую переменную, которая используется специально для организации запаздываний. Регистровая переменная выставит свое значение тогда и только тогда, когда в нее происходит запись (при этом читается старое значение регистровой переменной), или в момент запуска кадра (в этом случае читаются начальные значения регистровой переменной).

Таким образом, в фрагменте этой программы оператор присваивания R=B[i] выполняется одновременно с оператором присваивания A=(B[i]+R)*C[i], при этом переменной R соответствуют значения B[i-1].

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

Var A: Array [10: Stream];
Var R1, R2 REG;
CADR I;
R1=A[1];
R2=A[2];
ENDCadr;

CADR C;
FOR i=3 TO 10 Begin
C=A[i]+R1+R2;
R1=A[i];
R2=R1;
END;
ENDCadr;

Поскольку регистровой переменной соответствует задержка потока на один отсчет, R1 соответствует A[i-1], а R2 есть задержка отсчета R1 и соответствует A[i-2].

Данный пример демонстрирует частный случай использования регистровых переменных.

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

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

Семантически она эквивалентна бесконечному коммутационному потоку, i - е значение которого можно использовать только при (i+1)-м обращении к нему. На рис.6 приведены примеры решения задачи суммирования элементов массива.

На рис.6а представлены программа и эквивалентный ей граф вычислительной структуры, реализующей сложение элементов массива последовательно на одном ЭП с помощью двух кадров.

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

В данном случае регистровая переменная А сама инициализирует себя.

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

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

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

Var A: REG;
Var B: Array [4: Vector, 25: Stream];
Var C, I;
Var R[5: Vector] COM;
CADR b;
FOR I=1 TO 25 BEGIN
FOR J=1 TO 4
R[J+1]=R[J]+B[J,I];
A=A+R[5];
END;
C=A;
ENDCadr;

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

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

Например, следующая запись:

Var A,B: MEM;
CADR a;
A=B; B=A;
ENDCadr;

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

Запись вида

Var A,B: REG;
CADR a;
A=B; B=A;
ENDCadr;

семантически правильная. По завершении данной программы переменные А и В поменяют свои значения. Непривычность подобного действия объясняется тем, что все операторы в теле кадра выполняются параллельно.

Рассмотрим еще один пример использования регистровых переменных. Необходимо осуществить произведение матриц размером 16х16.

На рис.7 приведена программа и эквивалентный ей граф вычислительной структуры, реализующей поставленную задачу на 8 ЭП.

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

Условный оператор

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

IF q THEN a [ELSE b];

где IF, THEN, ELSE - ключевые слова языка;
q - логическое выражение;
a, b - списки операторов, ограниченные синтаксическими скобками BEGIN, END, выполняемые при истинности или ложности q соответственно.

Если списки а или b состоят из одного оператора, синтаксические скобки BEGIN, END могут отсутствовать. Допускаются вложенные конструкции условных операторов:

IF q1 THEN IF q2 THEN IF q3 .... ELSE d;

Выражение ELSE может отсутствовать.

Семантика внешнего условного оператора совпадает с семантикой условных операторов процедурных ЯПВУ.

Внутренний условный оператор выполняется следующим образом: группа операторов а и b, представляющих подграфы графа кадра, выполняяется параллельно; результаты вычислений обеих групп поступают на переключатель, работа которого определяется логическим выражением q. Другими словами, внутренний условный оператор реализует структурный аналог условного перехода. На рис.8 приведен пример использования внутреннего условного оператора.

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

Var A,B: Array [100: Stream];
FOR I=1 TO 100 DO;
IF A[I]>0 THEN CADR b1; B[I] = sin(A[I]); ENDCadr;
ELSE CADR b2; B[I] = exp(A[I]**2); ENDCadr;
END

Здесь условный оператор расположен вне кадра, задача реализуется на двух ВС, причем в процессе выполнения программы производится инициализация одной из них в зависимости от значения логического выражения A[I]>0. Данная реализация вычисления проигрывает предыдущей по скорости, но позволяет решить задачу с использованием меньшего количества элементарных процессоров.

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

Т_внутр = t_нас + t_{зад.ком} + n*t_{зад.мах} + 100*t_выч

где t_зад.max - задержка критического пути графа;
t_выч - время вычисления операторов присваивания в теле цикла;
t_{зад.ком} - задержка на вычислении условия и переключатель;
t_нас - время на насыщение конвейера.

Время вычисления программы с использованием внешнего оператора условного перехода определяется по формуле

Т_внеш = 100*(t_нас + К + t_выч),

где К - вычислительный параметр, меньший 1.
Параметр К вычисляется по формуле:

К = t_зад.mах * S_max + t_зад.min*S_min,

где t_зад.min - задержка альтернативного пути графа;
S_max - частота прохода по критическому пути графа;
S_min - частота прохода по альтернативной ветви графа.

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

Cоставной внутренний оператор условного перехода имеет следующий вид:

IF q THEN BEGIN a₁=t₁; a₂=t₂;...; a_n=t_n; END;
ELSE BEGIN a₁=f₁; a₂=f₂;...;a_n=f_n; END;

где q - логическое выражение; a_i - имя переменной, которой присваивается арифметико-логическое выражение t_i при истинности арифметико-логических выражений или f_i при ложности q.

Для реализации переключателя потребуется Зn элементарных процессоров (по три ЭП на вычисление каждой переменной составного условного оператора: два ЭП на конъюнкции, вычисляющей b_i = t_i & q; c_i = f_i&q, и один ЭП для дизъюнкции, вычисляющей a_i = b_i V c_i.

Можно утверждать, что cоставной внутренний оператор условного перехода эквивалентен следующей записи:

lb = q;
IF lb THEN a₁ = t₁ ELSE a₁ = f₁;
IF lb THEN a₂ = t₂ ELSE a₂ = f₂;
...
IF lb THEN a_n = t_n ELSE a_n = f_n;

где lb - имя переменной (коммутационной), значение которой определяется выражением q.

Запись в теле кадра типа

a=d;
IF q THEN a=b ELSE a=c;

являются синтаксической ошибкой, здесь нарушено правило единственной подстановки.

Оператор IF b THEN a=t ELSE a = f можно записать в более компактном виде: a = IF b THEN t ELSE f, что эквивалентно записи:

a = b & t V ¬b & f

Вышеприведенные рассуждения касались только тех случаев, когда во внутреннем условном операторе есть обе альтернативные ветви THEN и ELSE. Если во внутреннем операторе IF есть только конструкция THEN, то трансляция будет происходить иначе.

Оператор IF q THEN а=b будет оттранслирован в различные варианты вычислительных структур в зависимости от типа переменной а по способу хранения. Подразумевается, что если q - ложно, то переменная а сохраняет свое значение, что эквивалентно записи:

a=q & b V ¬q & a.

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

Внутренний оператор, у которого отсутствует конструкция ELSE, является неявной рекурсивной записью.

Подкадры

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

Subcadr Name ( F ) <СписокОператоров> Endsubcadr;

где Subcadr, Endsubcadr - ключевые слова языка;
Name - имя подкадра;
F - список формальных параметров, ограниченных круглыми скобками.

Обращение к подкадру производится по имени, после которого следует список фактических параметров, ограниченных круглыми скобками. Если подкадр является функцией (имя подкадра имеет свое значение), то необходимо в операторе описания данных Var указать имя подкадра и тип переменной; в теле подкадра должен включаться оператор присваивания Name=a, где а - арифметико-логическое выражение. Подкадр является независимой локальной ВС, все переменные подкадра, кроме помеченных в операторе Var EXTERN, являются внутренними и не связаны с именами переменных в кадре, вызывающем данный подкадр. В подкадрах не разрешена рекурсия, в том числе и скрытая, т.е. из подкадра не разрешается вызывать как собственный подкадр, так и последовательность подкадров, которая завершается вызовом текущего подкадра. Чтобы избежать побочных эффектов подкадров, целесообразно использовать в теле подкадра только коммутационные переменные. При вызове подкадра происходит сцепление (hocked) информационных каналов обмена, соответствующих фактическим параметрам, с формальными параметрами подкадра. В целом подкадры оформляются аналогично кадрам. В них запрещено использование операторов передачи управления, операторов описания вычислительных структур.

Рассмотрим примеры использования подкадров. На рис.9 приведены программа использования подкадров и графы вычислительных структур, в которые данная программа будет оттранслирована.

В данном случае продемонстрированы две особенности использования подкадров, на которых следует подробнее остановиться: динамическая организация массива и подстановка параллельного параметра. Под динамической организацией массива переменных понимается тот факт, что размерность массива в подкадре pirsum задана как переменная A [N], где N - параметр, задаваемый пользователем. Очевидно, что возможно использование как векторного, так и потокового массивов переменных. Подстановка потокового массива производится аналогично передаче в качестве параметров подпрограммы имени массива переменных в традиционных языках. Передается начальный адрес массива, с которым начинает работать подкадр и число членов массива, заданного пользователем. Кроме этого, необходимо передать адрес канала распределенной памяти, откуда извлекается данный массив. Таким образом, при вызове подкадра в качестве фактических параметров передается адрес потока в виде упорядоченной пары <Ak, Ag>, где Ak - адрес канала распределенной памяти, Ag - адрес начала данных. При работе с потоком Ak фиксирован, Ag изменяется при обращении к тому или иному элементу массива.

При обращении к подкадру с фактическим параметром векторного потока фиксируется Ag, а Ak изменяется. Адрес канала распределенной памяти является двойным. Во-первых, это адрес канала распределенной памяти, во-вторых, это совокупность адресов для многокаскадного коммутатора, обеспечивающего доступ с требуемого канала распределенной памяти на решающее поле элементарных процессоров вычислительной структуры. Таким образом, Ak=<Akв, Akk>, где Аkв - адрес канала распределенной памяти, Аkk - список адресов для многокаскадного коммутатора, обеспечивающего доступ к требуемому каналу распределенной памяти.

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

Var A,B,C,D,E,F,G : Real Mem;
Var K: Integer Com;
Subcadr BETA (In: A1,B1; Out: C1,D1);
Var A1,B1,C1,D1: Integer Com;
C:= A1+B1/2; D1:=A1-B1*2;
Endsubcadr;
Subcadr ALFA (In: A2,B2,C2);
Var A2,B2,C2: Integer Com;
C2=A2*3.14+B2*B2;
Endsubcadr;
Cadr A1;
Beta (A*2,4-B,D,C);
Alfa(D*C,E*E,F);
Endcadr;
Cadr A2;
Beta (F,F,G,K);
Alfa (K,E,A);
Endcadr;

Подструктуры

В процессе развития языка COLAMO понадобилось ввести ещё одну конструкцию - Let (подструктуру). Как и подкадр, подструктура используется там, где функционально законченные подграфы кадров изоморфны и потому при смене кадров эту подструктуру можно не перезагружать. Оператор объявления подструктуры выглядит следующим образом:

LET <Имя> ( <СписокПараметров> ) <СписокОператоров> ENDLET;

где LET, ENDLET - ключевые слова языка.

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

Все переменные конструкции LET, кроме помеченных в операторе VAR EXTERN, являются внутренними и не связаны с именами переменных в кадре. В конструкции LET не разрешена рекурсия, в том числе и скрытая, то есть из конструкции LETне разрешается вызывать как собственную конструкцию LET, так и последовательность подкадров, кадров или подпрограмм. В теле конструкции рекомендуется использовать коммутационные переменные. В данной конструкции запрещено использование операторов передачи управления, операторов описания вычислительных структур. В процессе выполнения программы возможно отключение конструкции LET при помощи оператора STOPLET. Оператор отключения конструкции LET в РБНФ выглядит следующим образом:

STOPLET <Имя конструкции LET>;

Для конструкций типа LET действуют следующие ограничения:
1. Конструкция LET может быть использована в теле кадров только одна;
2. Ограничено количество подставляемых переменных, принадлежащих различным контроллерам распределенной памяти во входные и выходные параметры конструкции LET.

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

Const N = 100;
Var A, B, C, D : Array Integer [N : Stream] Mem;
Var I : Number;
Let Argument (in : In1, In2; Out : Out1);
Var In1, In2, Out1 : Integer Com;
       Out1 := In1 + In2;
EndLet;

Cadr One;
    For I := 0 to N - 1 Do
        Argument(A[I], B[I], C[I]);
EndCadr;

Cadr Two;
    For I := 0 to N - 1 Do
        Argument(C[I], B[I], A[I]);
EndCadr;

Cadr Three;
    For I := 0 to N - 1 Do
        Argument(D[I], B[I], A[I]);
EndCadr;

Представим, что программист использует только кадры One и Two. В таком случае входной параметр In1 конструкции Argument обрабатывает два контроллера распределенной памяти, которым принадлежат переменные A и C. Такая ситуация оценивается транслятором как корректная в результате чего транслятор объединяет два контроллера распределенной памяти переменных A и C в один объект, называемый сдвоенным контроллером распределенной памяти, который представляет собой библиотечный элемент, разработанный в САПР Xilinx ISE. 
В случае если программист добавляет в рассмотрение кадр Three, возникает синтаксическая ошибка, связанная с тем, что входной параметр In1 конструкции Argument должен обрабатывать уже три контроллера распределенной памяти, обработка которых является невозможной в силу отсутствия соответствующего элемента в библиотеке.
Таким образом, количество подставляемых переменных, принадлежащих различным контроллерам распределенной памяти во входные и выходные параметры конструкции LET, должно быть не более двух.

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

Подпрограммы

Кроме подкадров, и подструктур в языке существуют традиционные подпрограммы. В общем случае подпрограмма имеет вид:

SUBROUTINE Name (f) P Endsubroutine;

где SUBROUTINE, Endsubroutine - ключевые слова языка;
f - список формальных параметров подпрограммы;
Р - список операторов подпрограммы.

В тело подпрограммы могут входить несколько кадров, операторы управления. Подпрограмма вызывается по имени, после которого следует список фактических параметров. Если в качестве параметров используются имена функций, процедур, подкадров, то они должны быть описаны с помощью конструкций Var Name CONTR; где Name - имя процедуры. Переменные, объявленные в подпрограмме, независимы от переменных основной программы, кроме тех переменных, которые в теле SUBROUTINE отмечены конструкциями Var n EXTERN. Здесь n - список имен внешних переменных.

Массивы кадров

Для эффективного управления работой кадров в языке COLAMO предусмотрена (но пока не поддерживается текущей версией транслятора) конструкция MCADR. Конструкция позволяет описать все объявленные кадры в виде одного массива, доступ к элементам которого осуществляется через индекс массива. Конструкция MCADR в РБНФ выглядит следующим образом:

MCADR: <Имя> [ <СписокКадров> ];

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

Cadr Cadr1
............
Endcadr;
Cadr Cadr2
............
Endcadr;
............
Cadr CadrN
............
Endcadr;

Mcadr: MasCadr [Cadr1, Cadr2,....., CadrN];
// Последовательная обработка вызываемых кадров
For I := 0 To 5 Step 2 Do
MasCadr[I];

// Параллельная обработка вызываемых кадров
Cadr Cadr0
For J := 0 To 5 Step 1 Do
MasCadr[J];
Endcadr;

Подключения

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

include MyLibNewElement;

где include - ключевое слово языка, а MyLibNewElement - имя используемой стандартной библиотеки (оно может меняться, в зависимости от того, для какой конкретной МВС приготовлена библиотека; например, для Virtex 5 она называется MyLibNewElement_V5). Эта конструкция необходима практически в любой прикладной программе, иначе программисту пришлось бы расписывать "подкадры" сумматор, умножитель и т.п.

Заключение

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

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

Приложения

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

Примеры

Быстрое преобразование Фурье на языке COLAMO.