Switch lang: Русский \ English

Hardware multicore optimizer


Коротко , что это такое ?

Вы про FPGA что-нибудь слышали ? И знаете что такое Software CPU Core ?

Тогда поздравляю детали следующих разделов Вам будут понятны :)

HMO - это задел для аппаратной реализации CPVM.

Мы сделали компактный модульный SoftwareCoreCPU для FPGA, который понимает байт код динамического языка высокого уровня Lua

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

Уже можно смало использовать в проектах робототехники. Даже ребенок сможет писать на Lua.

(мы же планируем генерировать код Lua фрагментов кода из PTS)

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

Задача ставилась так: сделать software «ядро процессора» (интерпретатор) для прошивки в FPGA . Язык Lua.

Допускается:

  • использовать препроцессор «байткода» для его изменения, в связи с нуждами задачи, с целью загрузки в память «интерпретатора»
  • в препроцессоре или конфиге трансляции или иначе накладывать ограничения на
    • размер стека функции
    • длину функции
    • размер/длинну строк
    • число регистров процессора
    • общее число инструкций итд.
    • Ограничение на конструкции языка, например goto или способ работы с таблицами (составные структуры данных)
    • не значительное изменение семантики языка (должна быть возможность запускать код написанный для ядра на обычном lua5.1 — а в нем можно запускать за счёт добавления и переопределений родных функций очень многие варианты семантики)

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

Ядро должно иметь возможность работы с внешними структурами через последовательные и параллельные порты, обработку событий.

Можно

  • отобразить IO порты на глобальные переменные
  • и туда же отобразить потоки последовательного ввода вывода

Требования к реализации

Для реализации потратить минимально возможное число вентилей.

Допустимо,если их потребуется от 500 до 5000.

Планируется прошивать в малые БМК хотя бы одно ядро с внешней по отношению к микросхеме памятью, а лучше 2-3 в большие ПЛИС зашивать систему из 20-30 ядер соединённых сетью так, чтобы ядра могли однообразно взаимодействовать между собой в кристалле и между несколькими кристаллами, образуя вычислительный кластер

Требовния к реализации Lua

Для Lua существует 2 известных варианта OPCODE множеств : 5.1 и Jit_2.0

5.1 — классический более короткий набор операций.

jit_2.0 - число операций больше, более мудрёные, больше информации о типах

считаю, что 5.1 для нас более предпочтителен. Jit2.0 не сильно упрощает интерпретацию для fpga, а при этом, работы больше

требования к lua 5.1

Lua 5.1 instruction pdf

opcodes

Cписок "команд" байт-кода минимален среди других языков.

typedef enum {
/*----------------------------------------------------------------------
name            args    description
------------------------------------------------------------------------*/
OP_MOVE,/*      A B     R(A) := R(B)                                    */
OP_LOADK,/*     A Bx    R(A) := Kst(Bx)                                 */
OP_LOADBOOL,/*  A B C   R(A) := (Bool)B; if (C) pc++                    */
OP_LOADNIL,/*   A B     R(A) := ... := R(B) := nil                      */
OP_GETUPVAL,/*  A B     R(A) := UpValue[B]                              */

OP_GETGLOBAL,/* A Bx    R(A) := Gbl[Kst(Bx)]                            */
OP_GETTABLE,/*  A B C   R(A) := R(B)[RK(C)]                             */

OP_SETGLOBAL,/* A Bx    Gbl[Kst(Bx)] := R(A)                            */
OP_SETUPVAL,/*  A B     UpValue[B] := R(A)                              */
OP_SETTABLE,/*  A B C   R(A)[RK(B)] := RK(C)                            */

OP_NEWTABLE,/*  A B C   R(A) := {} (size = B,C)                         */

OP_SELF,/*      A B C   R(A+1) := R(B); R(A) := R(B)[RK(C)]             */

OP_ADD,/*       A B C   R(A) := RK(B) + RK(C)                           */
OP_SUB,/*       A B C   R(A) := RK(B) - RK(C)                           */
OP_MUL,/*       A B C   R(A) := RK(B) * RK(C)                           */
OP_DIV,/*       A B C   R(A) := RK(B) / RK(C)                           */
OP_MOD,/*       A B C   R(A) := RK(B) % RK(C)                           */
OP_POW,/*       A B C   R(A) := RK(B) ^ RK(C)                           */
OP_UNM,/*       A B     R(A) := -R(B)                                   */
OP_NOT,/*       A B     R(A) := not R(B)                                */
OP_LEN,/*       A B     R(A) := length of R(B)                          */

OP_CONCAT,/*    A B C   R(A) := R(B).. ... ..R(C)                       */

OP_JMP,/*       sBx     pc+=sBx                                 */

OP_EQ,/*        A B C   if ((RK(B) == RK(C)) ~= A) then pc++            */
OP_LT,/*        A B C   if ((RK(B) <  RK(C)) ~= A) then pc++            */
OP_LE,/*        A B C   if ((RK(B) <= RK(C)) ~= A) then pc++            */

OP_TEST,/*      A C     if not (R(A) <=> C) then pc++                   */ 
OP_TESTSET,/*   A B C   if (R(B) <=> C) then R(A) := R(B) else pc++     */ 

OP_CALL,/*      A B C   R(A), ... ,R(A+C-2) := R(A)(R(A+1), ... ,R(A+B-1)) */
OP_TAILCALL,/*  A B C   return R(A)(R(A+1), ... ,R(A+B-1))              */
OP_RETURN,/*    A B     return R(A), ... ,R(A+B-2)      (see note)      */

OP_FORLOOP,/*   A sBx   R(A)+=R(A+2);
                        if R(A) <?= R(A+1) then { pc+=sBx; R(A+3)=R(A) }*/
OP_FORPREP,/*   A sBx   R(A)-=R(A+2); pc+=sBx                           */

OP_TFORLOOP,/*  A C     R(A+3), ... ,R(A+2+C) := R(A)(R(A+1), R(A+2)); 
                        if R(A+3) ~= nil then R(A+2)=R(A+3) else pc++   */ 
OP_SETLIST,/*   A B C   R(A)[(C-1)*FPF+i] := R(A+i), 1 <= i <= B        */

OP_CLOSE,/*     A       close all variables in the stack up to (>=) R(A)*/
OP_CLOSURE,/*   A Bx    R(A) := closure(KPROTO[Bx], R(A), ... ,R(A+n))  */

OP_VARARG/*     A B     R(A), R(A+1), ..., R(A+B-1) = vararg            */
} OpCode;


#define NUM_OPCODES     (cast(int, OP_VARARG) + 1)



/*===========================================================================
  Notes:
  (*) In OP_CALL, if (B == 0) then B = top. C is the number of returns - 1,
      and can be 0: OP_CALL then sets `top' to last_result+1, so
      next open instruction (OP_CALL, OP_RETURN, OP_SETLIST) may use `top'.

  (*) In OP_VARARG, if (B == 0) then use actual number of varargs and
      set top (like in OP_CALL with C == 0).

  (*) In OP_RETURN, if (B == 0) then return up to `top'

  (*) In OP_SETLIST, if (B == 0) then B = `top';
      if (C == 0) then next `instruction' is real C

  (*) For comparisons, A specifies what condition the test should accept
      (true or false).

  (*) All `skips' (pc++) assume that next instruction is a jump
===========================================================================*/

Как пользоваться

  1. программист пишет в рамках acapella прямолинейную программу на lua (acapella pts умеет пока только lua)
  2. система acapella , в процессе тестирования алгоритма:
    1. разбивает программу на фрагменты разумного размера
    2. находит зависимости между ними и полный dataflow + controlflow
    3. человек (разработчик) утверждает найденные зависимости как постоянные
    4. делается кодо-генерация сотней фрагментов для «fpga lua ядер» и прошивается в память программ ядер в FPGA
  3. fpga asic кластер на высокой скорости решает задачу, используя супер-мелкозернистую параллельность
    1. ядро внутри себя работает последовательно. Но в нем затраты на динамическую природу скомпенсированы за счёт fpga природы
    2. ALU эффективно как любое другое
    3. память тратится слегка с избытком, но на регистры должно хватать памяти в самом кристалле — она очень быстрая, быстрее чем внешняя шина памяти + там "много мини-шин"
    4. сами ядра lua и внутри кристалла и при взаимодействии между кристаллами работают распределено, параллельно, раскрывая потенциал параллельности заложенного алгоритма (в стиле erlang, CSP). Разница в том, что там их много и работают они одновременно.

что готово ? результаты.

пример сборки

luac -o 1.luac 1.lua
lua lua-chunk-spy\x32\ChunkSpy.lua -o 1.txt 1.luac
lua_pmem_gen\Release\lua_pmem_gen 1.luac 1.bin
bin2hex\Release\bin2hex 1.bin 1.hex 4 1
copy 1.hex ..\pmem_data.hex

здесь по строкам смысл такой:

  1. получаем байт код типовым компилятором.
  2. делаем декомпозицию байт кода
  3. генерируем бинарный файл для прошиивки
  4. генерим hex файл для памяти fpga
  5. кидаем файл в проект fpga

подсистемы ядра

  • регистры
  • менеджер регистров
  • память комманд
  • память регистров
  • память данных
  • динамическое управление памятью , выделение памяти, мультиплексор памяти, Reg_AddRef и Reg_Release, Reg_AddRef и Reg_Release, удаление памяти (Mem_Release, Mem_InnerRelease, Mem_Free)
  • создание и работа с таблицами Lua , быстрый расчёт хеша
  • память стека
  • регистры внутреннего стека и алгоритмы для него
  • операции
    • LOADBOOL
    • LOADNIL
    • OP_MOVE
    • MOVE
    • LOADK
    • GetTable SetTable
    • GetGlobal SetGlobal
    • OP_TEST
    • OP_TESTSET
    • ADD, SUB, MUL, DIV, MOD, UNM
    • OP_EQ
    • команды арифметического модуля
    • OP_LE, OP_LT
    • OP_FORLOOP и OP_FORPREP
    • микропрограммы встроенных функций
    • OP_NOT
    • OP_CLOSURE
    • операция OP_CALL для обычных функций
    • OP_GETUPVAL
    • OP_SETUPVAL
    • OP_RETURN
    • OP_SELF
  • ввод-вывод в тестовом режиме
  • константы типа Nil, счётчик ссылок для контстант

тестовая программа которая работает в ядре FPGA сейчас

--write = print

local all_pass = true

local function assert(c)
    all_pass = all_pass and c
    if c then write(0, 1) else write(0, 0) end
end

-- loadk, move, loadnil, loadbool

local a, b, c, d, e, f, g
a = true
b = false
c = 123
d = 0.5
e = "foobar"
f = "abc"
assert(a == true)
assert(b == false)
assert(c == 123)
assert(d == 0.5)
assert(e == "foobar")
assert(f == "abc")

a = b
b = c
c = d
d = e
assert(a == false)
assert(b == 123)
assert(c == 0.5)
assert(d == "foobar")

e = nil
f = nil
assert(e == nil)
assert(f == nil)

-- add, sub, mul, div, mod, unm

a = 95415
b = 625
c = a + b
assert(c == 95415 + 625)
c = a - b
assert(c == 95415 - 625)
c = a * b
assert(c == 95415 * 625)
c = a / b
assert(c == 95415 / 625)
c = a % b
assert(c == 95415 % 625)
c = -a
assert(c == -95415)

-- not

a = true
b = false
c = 1
d = "123"
e = ""
f = {}
g = function () end
assert(not a == false)
assert(not b == true)
assert(not c == false)
assert(not d == false)
assert(not e == false)
assert(not f == false)
assert(not g == false)

-- call, return

g = function (a, b, c, d) return b, c end
a = 1
b = "2"
c = 3
d = "4"
a, b = g(a, b, c, d)
assert(a == "2" and b == 3)
a = 1
b = "2"
c = 3
d = "4"
a, b, c, d = g(a, b, c, d)
assert(a == "2" and b == 3 and c == nil and d == nil)
a = 1
b = "2"
c = 3
d = "4"
a, b, c, d = g(a, b)
assert(a == "2" and b == nil and c == nil and d == nil)
a = 1
b = "2"
c = 3
d = "4"
b, a, d, c = g(a, b, c, d)
assert(b == "2" and a == 3 and d == nil and c == nil)
a = 1
b = "2"
c = 3
d = "4"
g()
assert(a == 1 and b == "2" and c == 3 and d == "4")
a = 1
b = "2"
c = 3
d = "4"
g(a, b, c, d)
assert(a == 1 and b == "2" and c == 3 and d == "4")

-- getupval, setupval, closure

a = 10
b = 20

g = function () return a + b end
assert(g() == a + b)

g = function () 
    local tmp = a
    a = b
    b = tmp
end
g()
assert(a == 20 and b == 10)

g = function() 
    local tbl = {}
    return function ()
        return tbl
    end
end
a = g()
b = g()
assert(a ~= b)
assert(a() ~= b())

f = {}
g = function() 
    return function ()
        return f
    end
end
a = g()
b = g()
assert(a ~= b)
assert(a() == b())

-- getglobal, setglobal, newtable

a = {}
GBL_1 = 10
GBL_2 = "20"
GBL_3 = a

assert(GBL_1 == 10)
assert(GBL_2 == "20")
assert(GBL_3 == a)

GBL_3.abc = 5234

assert(abc == nil)
assert(GBL_3.abc == 5234)

-- gettable, settable, newtable

a = {}
a.foo = "123"
a.bar = "baz"
a[1] = 10
a[100] = 20
a[5000] = {}
a[5000].a = 1
a[5000].b = 2
a[5000].c = 3
a[true] = 1
a[false] = 0

assert(a.foo == "123")
assert(a.bar == "baz")
assert(a[1] == 10)
assert(a[100] == 20)
assert(a[5000].a == 1)
assert(a[5000].b == 2)
assert(a[5000].c == 3)
assert(a[true] == 1)
assert(a[false] == 0)

-- jmp, while loops

a = 0
b = 10
c = 0
while a < b do 
    c = c + a
    a = a + 1
end
assert(a == 10)
assert(c == 45)

a = 1
b = 10
c = 0
while a <= b do
    c = c + a
    a = a + 1
end
assert(a == 11)
assert(c == 55)

a = 20
b = 10
c = 0
while not (a <= b) do
    c = c + a
    a = a - 1   
end
assert(a == 10)
assert(c == 155)

-- self

local function counter()    
    return {
        count = 0,  
        inc = function (this)
            this.count = this.count + 1
        end,
        dec = function (this)
            this.count = this.count - 1
        end
    }
end

local a = counter()
local b = counter()
assert(a ~= b)

a:inc()
a:inc()
assert(a.count == 2)
assert(b.count == 0)

b:inc()
a:inc()
b:inc()
b:inc()
assert(a.count == 3)
assert(b.count == 3)

a:dec()
a:dec()
b:dec()
assert(a.count == 1)
assert(b.count == 2)

-- forloop, forprep

a = 0
for b = 1, 10 do
    a = a + b
end
assert(a == 55)

a = 0
for b = 1, 2, 0.25 do
    a = a + 1
end
assert(a == 5)

-- test

a = true
b = false
c = 10
d = nil
e = "ff"

if a     then assert(true)  else assert(false) end
if not b then assert(true)  else assert(false) end
if not c then assert(false) else assert(true)  end
if d     then assert(false) else assert(true)  end
if e     then assert(true)  else assert(false) end

-- testset

a = true
b = false
c = 10
d = nil
e = "ff"

assert((b or a)  == true)
assert((a or b)  == true)
assert((a and b) == false)
assert((a or c)  == true)
assert((c or a)  == 10)
assert((d or c)  == 10)
assert((c and e) == "ff")

assert((d or "ff") == "ff")
assert(("ff" and d) == nil)

-- lt, le

--[[a = 10
b = 20
c = "aaa"
d = "aab"
e = "aa"

assert(a < b)
assert(a <= b)
assert(not (a > b))
assert(not (a >= b))
assert(c < d)
assert(c <= d)
assert(not (c > d))
assert(not (c >= d))
assert(d > c)
assert(d >= c)
assert(c > e)
assert(d > e)
assert(e >= e)
assert(e <= e)]]



if all_pass then write(1, 1) else write(1, 0) end

while true do end

Итоговые диаграммы сигналов для этой программы

Начало диаграммы:

Конец диаграммы:

Как вам ?

Comments

Comments powered by Disqus
Skip to main content