DataFlow_Компилятор с ЯВУ в ориентированный ациклический граф2(пример)

Предварительные пояснения.
Если вычислительную часть программа рассматривать как логическую схему без элементов
памяти (в текстах «DataFlow_Компилятор с ЯВУ в ориентированный ациклический граф»
показана возможность такого преобразования). Доставкой данных (DatSet) занимается сеть
ССИ. Исходные и результирующие данные помещаются в фифо буфера ССИ коммутатора.
При этом любая команда выполняется (генерируют результат на выход) только если на ВСЕ
входы поданы (существуют) требуемые объекты. Если нет объекта с требуемым уникальным
идентификатором, то нет срабатывания и генерации результирующего объекта с уникальным
идентификатором. Различные команды могут генерировать объекты с одинаковым
идентификатором только при гарантии невозможности создать два объекта с одинаковым
идентификатором (примерно как оператор IF, где или в одну сторону или в другую и никогда
в обе стороны).
Для демонстрации мне был прислан текст на языке СИ
Исходная программа :
int strlen(const char* s)
{
int i = 0;
while (s[i]) i++;
return i;
}
По вопросу доступа к обрабатываемым данным.
Данные передаются по ССИ сети и уже находятся в отдельных FIFO (каждый символ текста в
своем буфере) и доступ ко всем данным возможен параллельно. В реальности невозможно
получить бесконечное число буферов, соответственно строка при передаче будет разбита
(автоматически при генерации ассемблера) на куски размером (N) равным числу буферов.
Соответственно следующим элементом для буфера с S[0] будет S[N] . Преобразованием из
последовательной формы (хранится в оперативной памяти) в двумерную (да и вообще в
любой Data Set ) занимаются механизмы сети ССИ. Число N можно считать числом
одновременно исполняемых команд (числом нитей). Для DataFlow число N может достигать
миллиона на один кристалл (для современных тех. процессов), что соответствует миллиону
команд за такт. Производительность в 10Е15 операций в секунду на кристалл очень даже
неплохо. Если учесть плотность упаковки до 10.000 процессоров в одном кубическом метре
(определяется возможностью отвода тепла), то и вообще до 10E19 операций в секунду на
стойку.
Коды исполняемых команд, это тоже данные передаваемые сетью ССИ и исполнение
какого либо объекта происходит методом передачи его данных из памяти в (через)
«процессор». Взаимодействие двух объектов выглядит как передача данных объектов в один
«процессор», где они «взаимодействуют» с генерацией новых объектов (если это
необходимо).
В процессоре происходит взаимодействие двух потоков, содержащих разные объекты. После
взаимодействия исчезают старые (исходные) объекты и появляются новые.
Нет даже теоретической возможности одному и тому же объекту взаимодействовать с
другими объектами одновременно, для этого нужно сначала создать копию (но это будет
самостоятельный объект).
Звучит все сложно, но в реальности достаточно просто (будет описываться в статьях
посвященных архитектуре DataFlow вычислителя)
Применение:
Меня такая машина интересует для моделирования биологической клетки как целого объекта
(виртуальная биологическая клетка). При размере клетки в 5мкм, примерно получается (для
вычислителя 10Е20) 10Е8 операций в секунду на каждый атом. Сколько операций требуется
для моделирования одного шага моделирования не знаю, потому не могу сказать отношение
модельного времени к реальному.
Попробовал описать все преобразования но получается не
наглядно и возможно содержит ошибки (примерно как в ручную
компилировать программу с ЯВУ в ассемблер).
После разворачивания цикла и приведения к однократным присваиваниям
переменных
{Инициализация цикла}
0.i.0=0, (команда присваивания)
{Проверка на конец строки}
BranchTrue.0=Boolean(s[0]==0), (превратится в команду для АЛУ)
BranchTrue.1=Boolean(s[1]==0), (превратится в команду для АЛУ)
BranchTrue.2=Boolean(s[2]==0), (превратится в команду для АЛУ)
{повторяем до бесконечности}
{Проверка на наличие символа}
BranchFalse.0=Boolean(s[0]!=0), (превратится в команду для АЛУ)
BranchFalse.1=Boolean(s[1]!=0), (превратится в команду для АЛУ)
BranchFalse.2=Boolean(s[2]!=0), (превратится в команду для АЛУ)
{повторяем до бесконечности}
{Если не конец строки то генерируем следующую итерацию цикла, но не генерируем
результат исполнения}
if (BranchFalse.0) 0.i.1=0.i.0, (команда условного присваивания)
if (BranchFalse.1) 1.i.1=1.i.0, (команда условного присваивания)
if (BranchFalse.2) 2.i.1=2.i.0, (команда условного присваивания)
1.i.0= 0.i.1+1, (превратится в команду для АЛУ)
2.i.0= 1.i.1+1, (превратится в команду для АЛУ)
3.i.0= 2.i.1+1, (превратится в команду для АЛУ)
{повторяем до бесконечности}
{Если конец строки то генерируем результат, но не генерируем новый цикл}
if (BranchTrue.0) 0.i.2=0.i.0,(команда условного присваивания)
if (BranchTrue.1) 0.i.2=1.i.0,(команда условного присваивания)
if (BranchTrue.2) 0.i.2=2.i.0, (команда условного присваивания)
{повторяем до бесконечности}
{Передача результата исполнения функции}
strlen=0.i.2, (команда присваивания)
Выполнение графа автоматически остановится или по концу строки (нет символа или символ
равен нулю) или по отсутствию следующей итерации.
Полученный текст практически без изменений (нужно избавиться от бесконечных
повторений) может быть преобразован в любой HDL язык и откомпилирован для получения
прошивки FPGA.
Описывать стадию ассемблера без описания архитектуры DataFlow смысла нет. Следующая
статья будет с описанием архитектуры и только потом ассемблер.
Граф для N=4 (упрощенный рисунок без оптимизации).
Примерно так будет выглядеть текст программы преобразованной в Verilog :
// -----------------------------------------------------------------------------------------------------------
// Attention:
// All ideas and algorithms are the result of my independent and completely independent intellectual
activity.
// As an author, I give permission to freely use, change, supplement all ideas and algorithms to any
person or
// organization in any type of project, with the obligatory indication of my authorship.
// Balyberdin Andrey Leonidovich (Rutel@Mail.ru)
//------------------------------------------------------------------------------------------------------------
`timescale 1 ns / 1 ns
//
module strlen
(
input clk,
input ReStart,
//
input [7:0] FifoInData0,
input FifoInEmpty0,
output FifoInRd0,
//
input [7:0] FifoInData1,
input FifoInEmpty1,
output FifoInRd1,
//
input [7:0] FifoInData2,
input FifoInEmpty2,
output FifoInRd2,
//
input [7:0] FifoInData3,
input FifoInEmpty3,
output FifoInRd3,
//
input [7:0] FifoInData4,
input FifoInEmpty4,
output FifoInRd4,
//
input [7:0] FifoInData5,
input FifoInEmpty5,
output FifoInRd5,
//
input [7:0] FifoInData6,
input FifoInEmpty6,
output FifoInRd6,
//
input [7:0] FifoInData7,
input FifoInEmpty7,
output FifoInRd7,
//strlen
output [31:0] FifoOutData,
input FifoOutFull,
output FifoOutWr
);
reg [31:0] StrLen;
reg Busy;
//
assign FifoOutWr=(Busy | ReStart) & !FifoOutFull & !FifoInEmpty0 & !FifoInEmpty1 & !
FifoInEmpty2 & !FifoInEmpty3 &
!
FifoInEmpty4 & !FifoInEmpty5 & !FifoInEmpty6 & !FifoInEmpty7 &
(FifoInData0[7:0]==8'h0 | FifoInData1[7:0]==8'h0 | FifoInData2[7:0]==8'h0 |
FifoInData3[7:0]==8'h0 | FifoInData4[7:0]==8'h0 | FifoInData5[7:0]==8'h0 |
FifoInData6[7:0]==8'h0 | FifoInData7[7:0]==8'h0);
//
assign FifoOutData[31:0]= (FifoInData0[7:0]==8'h0)?(ReStart?32'h0:(StrLen[31:0]+32'h0)):
((FifoInData1[7:0]==8'h0)?(ReStart?
32'h1:(StrLen[31:0]+32'h1)):
((FifoInData2[7:0]==8'h0)?(ReStart?
32'h2:(StrLen[31:0]+32'h2)):
((FifoInData3[7:0]==8'h0)?(ReStart?
32'h3:(StrLen[31:0]+32'h3)):
((FifoInData4[7:0]==8'h0)?(ReStart?
32'h4:(StrLen[31:0]+32'h4)):
((FifoInData5[7:0]==8'h0)?(ReStart?
32'h5:(StrLen[31:0]+32'h5)):
((FifoInData6[7:0]==8'h0)?(ReStart?
32'h6:(StrLen[31:0]+32'h6)):
((FifoInData7[7:0]==8'h0)?(ReStart?
32'h7:(StrLen[31:0]+32'h7)):32'h7fffffff)))))));
//
//
assign FifoInRd0=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd1=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd2=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd3=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd4=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd5=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd6=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
assign FifoInRd7=FifoInEmpty0 & FifoInEmpty1 & FifoInEmpty2 & FifoInEmpty3 &
FifoInEmpty4 & FifoInEmpty5 & FifoInEmpty6 & FifoInEmpty7;
//
always @(posedge clk)
begin
//
if(ReStart & !Busy)Busy<=1'b1;
if(ReStart | !Busy)StrLen[31:0]<=32'h0;
//
if(!ReStart & Busy & !FifoInEmpty0 & !FifoInEmpty1 & !FifoInEmpty2 & !FifoInEmpty3 & !
FifoInEmpty4 & !FifoInEmpty5 & !FifoInEmpty6 & !FifoInEmpty7)
StrLen[31:0]<=StrLen[31:0]+32'h8;
//
end
//
endmodule