понедельник, 16 июля 2012 г.

Knowledge Brings Fear

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



Лисп немного осилил, учу в меру ленивости Verilog. Букварь о 800-страницах ещё и до середины не пролистан, но вчера, на ночь глядя, кривыми интернетными тропками вспомнил, что не знаю, как работает целочисленное умножение в процессоре. Решил просветиться.

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

  1. Дважды-два - четыре. Т.е. заучивается таблица умножения. Компьютер может позволить себе иметь таблицу для параметров не только одноразрядных, но и  чуток побольше. Сложность O(1).
  2. X*Y можно получить, если X в цикле сложить Y раз. Сложность O(N).
  3. Множитель можно разложить на двойки и единицы и использовать их для бинарного сдвига и сложения. Сложность не знаю какая.
Википедия говорит, что очень хорош собой алгоритм Карацубы, который обладает сложностью O(nlog23). Перескажу его кратко:

Нужно перемножить два двухзначных числа, допустим, 12 и 34. Для этого разбиваем числа по разрядам, получаем x1 = 1, x2 = 2, y1 = 3, y2 = 4. Находим:

    A = x1 * y1.
    B = x2 * y2.
    C = (x1 + x2) * (y1 + y2).
    K = C - A - B

Результат умножения получается так: 100 * A + 10 * K + B. Очень просто, в принципе.

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

multx.lisp
(defvar *table* (loop for x from 0 below 8
                      collect (loop for y from 0 below 8
                                    collect (* x y))))

(defun multiply (x y)
  (labels ((vectorize (x &optional (n 4))
             (reverse (loop for i = x then (ash i -4)
                            repeat n
                            collect (logand i #xf))))
           (table-lookup (x y)
             (nth x (nth y *table*)))
           (trivial-mult (sx sy)
             (let* ((x1 (ash sx -2))
                    (x2 (logand sx 3))
                    (y1 (ash sy -2))
                    (y2 (logand sy 3))
                    (a (table-lookup x1 y1))
                    (b (table-lookup x2 y2))
                    (c (table-lookup (+ x1 x2) (+ y1 y2)))
                    (k (- c a b)))
               (+ (ash a 4) (ash k 2) b)))
           (vector-multiply (x y)
             (loop for x1 in x
                   for i in '(12 8 4 0)
                   sum (ash (loop for y1 in y
                                  for i in '(12 8 4 0)
                                  sum (ash (trivial-mult x1 y1) i))
                            i))))
    (vector-multiply (vectorize x) (vectorize y))))

(multiply 12 34) => 408


Табличка умножения 8 на 8 нужна для выполнения внутренних умножений в самом алгоритме. На самом деле, таблица нужна 4 на 4, т.к. размер разряда я принял в 2 бита, но в ходе отладки обнаружилось, что при вычислении C происходит выход за пределы таблицы, поэтому я её малодушно сделал в два раза больше по обоим измерениям.

Следующим шагом было переписывание того же самого на Верилоге. В оном языке, как и в Лиспе, умножение присутствует из коробки, но ради обучения  сей факт проигнорировал, конечно. Значит, вот вымученный 8-битный умножитель (размер разряда у числа - 4 бита):

123
module Multiplier8x8 (x, y, q, clk);
   input          clk;
   input [7:0]    x, y;
   output [15:0]  q;

   reg [15:0]     q;
   reg [7:0]      a, b;
   reg [11:0]     c, k;
   wire [3:0]     x1, x2, y1, y2;
   wire [4:0]     cx, cy;
   
   reg [15:0]      tbl [0:1023];
   wire [4:0]      x1l, x2l, y1l, y2l;
     
   initial begin
      $readmemb("mult2.tbl", tbl);
   end

   assign {x1, x2} = x;
   assign {y1, y2} = y;
   assign cx = x1 + x2;
   assign cy = y1 + y2;
   assign x1l = x1;
   assign x2l = x2;
   assign y1l = y1;
   assign y2l = y2;

   always @ (posedge clk) begin
      a <= tbl[{x1l, y1l}];
      b <= tbl[{x2l, y2l}];
      c <= tbl[{cx, cy}];
      q <= (a << 8) + (k << 4) + b;
   end

   always @ (negedge clk) begin
      k <= c - a - b;
   end
endmodule

Для внутреннего умножения тоже используется таблица, но размером 32x32 (5 на 5 бит). Генерируется вот таким лиспокодом:

mult-gen.lisp
(with-open-file (f "~/src/verilog/mult2.tbl"
                   :direction :output
                   :if-exists :supersede
                   :element-type 'character)
  (dotimes (i 32)
    (dotimes (j 32)
      (format f "~16,'0b~%"  (* i j)))))

Сверхкраткий ракурс в Verilog.

Логика абстрагируется в модуле. У модуля есть входные и выходные параметры. У параметров есть разрядность в битах. Параметры могут быть проводами (wire) или регистрами (reg). Провода от регистров отличаются тем, что первые не хранят значение, а вторые - хранят. Соответственно, выход провода меняет значение одновременно с входом, а регистр выступает в роли защёлки-триггера (которому нужна опорная тактовая частота). Это если очень-очень просто.

assign соединяет провода. assign {x1, x2} = x; разбирает 8-битный x на 4-битные x1 и x2 (фигурные скобки - оператор конкатенации). assign cx = x1 + x2; складывает 4-битные x1 и x2, а 5-битный результат присваивает cx. assign x1l = x1; расширяет 4-битный x1 до 5-битного x1l с нулём в старшем бите.

always @ (posedge clk) срабатывает, когда сигнал опорной частоты clk изменяется с 0 на 1 (передний фронт). always @ (negedge clk) срабатывает, соответственно, наоборот: с 1 на 0 (задний фронт).

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

Значит, вычисление A, B и C прямолинейно и понятно. Единственное, что стоить отметить: т.к. аргументы у нас 4-битные, а таблица умножения построена для 5-битных множителей из-за переполнения при вычислении C, плюс она является одномерным массивом размерностью 2^(5 + 5), то x1, x2, y1 и y2 расширены до 5 бит. cx и cy (суммы x1 + x1 и y1 + y2) и так 5-битные.

Вкусность программирования под железо заключается в массивном параллелизме. Все операции в коде выполняются одновременно, кроме кода в разных блоках always. Внутри always код тоже полностью параллельный, но K не может быть вычислен одновременно с C, A и B. Поэтому K нужно вынести либо в другой такт, либо повесить его вычисление на спад clk. Таким образом, умножение двух восьмибитных чисел происходит за один такт.

На самом деле, при программировании под реальную железяку вылезет море проблем. Например, tbl смотрится одновременно с тремя наборами параметрами, и для такой возможности нужно иметь, как-минимум, 3-портовую память. Или использовать 3 одинаковые таблицы.

Тестбенч для умножителя:
123
module test;
   reg clk = 0;
   always #1 clk = ~clk;

   wire [15:0] q;
   reg [7:0]   x, y;

   initial begin
      $dumpfile("test.vcd");
      $dumpvars(0, test);

      x = 123;
      y = 255;

      # 4 $finish;
   end

   Multiplier8x8 m (x, y, q, clk);
endmodule
Ложим оба модуля в один файл, компилируем Икарусом, выполняем, прогоняем через gtkwave:

$ iverilog mult.v && ./a.out && gtkwave test.vcd



Теперь применим всю мощь массового параллелизма и сделаем на основе 8-битных умножителей один 16-битный. Для этого всего лишь нужно сделать матрицу 2 на 2:
123
module Multiplier16x16 (x, y, q, clk);
   input          clk;
   input [15:0]   x, y;
   output [31:0]  q;

   wire [31:0]     q;
   wire [15:0]     v11, v12, v21, v22;

   Multiplier8x8 m11 (x[7:0], y[7:0], v11, clk);
   Multiplier8x8 m12 (x[7:0], y[15:8], v12, clk);
   Multiplier8x8 m21 (x[15:8], y[7:0], v21, clk);
   Multiplier8x8 m22 (x[15:8], y[15:8], v22, clk);
 
   assign q = (((v22 << 8) + v21) << 8) + (v12 << 8) + v11;
endmodule

Матрица собирается тоже за один такт, если верить симуляции:
123
module test;
   reg clk = 0;
   always #1 clk = ~clk;

   wire [31:0] q;
   reg [15:0]  x, y;

   initial begin
      $dumpfile("test.vcd");
      $dumpvars(0, test);

      x = 12345;
      y = 43210;

      # 4 $finish;
   end

   Multiplier16x16 m (x, y, q, clk);
endmodule



И, чтобы совсем заставить рыдать публику, которой обсчёт матрицы 8 на 8 - это нифига не бесплатно, вот 32-битный умножитель на том же принципе, что и 16-битный:
123
module Multiplier32x32 (x, y, q, clk);
   input          clk;
   input [31:0]   x, y;
   output [63:0]  q;

   wire [63:0]     q;
   wire [31:0]     v11, v12, v21, v22;

   Multiplier16x16 m11 (x[15:0], y[15:0], v11, clk);
   Multiplier16x16 m12 (x[15:0], y[31:16], v12, clk);
   Multiplier16x16 m21 (x[31:16], y[15:0], v21, clk);
   Multiplier16x16 m22 (x[31:16], y[31:16], v22, clk);
 
   assign q = (((v12 << 16) + v11) << 0) + (((v22 << 16) + v21) << 16);
endmodule
В качестве множителей использованы микрософтовские константы BIG BOOBS и BOOBIES, которые вызвали такие волны околосексистких говен в этих ваших интернетах:
123
module test;
   reg clk = 0;
   always #1 clk = ~clk;

   wire [63:0] q;
   reg [31:0]  x, y;

   initial begin
      $dumpfile("test.vcd");
      $dumpvars(0, test);

      x = 32'hB16B00B5;
      y = 32'h0B00B1E5;
      # 4 $finish;
   end

   Multiplier32x32 m (x, y, q, clk);
endmodule


Проверяем результаты в Лиспе:
123
(format nil "~x" (* 123 255)) => "7A85"
(format nil "~x" (* 12345 43210)) => "1FCB74FA"
(format nil "~x" (* #xB16B00B5 #x0B00B1E5)) => "7A014517734C6E9"
Ура! :)

Распознание лица года три назад ещё на Лиспе написал, так что Терминатор, практически, готов! На следующих выходных поставлю на шасси от детской коляски старый вольвовский аккумулятор, стартер, вебкамеру, альтеровский девкит и палку.

6 комментариев:

  1. Анонимный16 июля 2012 г., 8:05

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

    ссылка на гитхаб будет прилагаться? ;)

    ОтветитьУдалить
    Ответы
    1. Хотите сделать свою боевую детскую коляску для противодействия моей? :) Боюсь, это всё закончится соревнованием, у чьей коляски длиннее палка...

      Удалить
  2. Во-первых, в VLSI сложность считается совсем не так. Здесь две сложности -- это количество условных транзисторов в реализацыи (реально один физический можэт идти за несколько) и propagation delay.
    Насколько я помню, никакого резона делать для умножэния какие-то таблицы (как в п.1) нет -- во всяком случае никто их не делал на моей памяти. При этом обычно делают аппаратный умножытель nxn (вот здесь например http://www.ece.ucdavis.edu/~vojin/CLASSES/EEC280/Lecture-Material/Arith-Chapter-v6.PDF описано как, в общем, делается именно побитовое умножэние в столбик, трюки на нашэм уровне несущественны, притом делается оно вполне в параллель, так что говорить об O(...) не приходится) -- а затем ужэ либо микрокодом расшыряют его до нужной величины, либо вообще софтом.

    ОтветитьУдалить
    Ответы
    1. Сложность алгоритма к параллельности отношения ведь не имеет? Понятно, что если алгоритм хорошо параллелится, то он будет выполняться быстрее в соответствующих условиях. Но количество элементарных действий всё равно тем же останется.

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

      Удалить
    2. Кстати, в этой pdf'ке рассматривается метод, разработанный в 64-м году, а Карацуба появился в 67-м, что ли. И такую большую табличку достаточно накладно хранить.

      Хотя, можно использовать этот Wallace/Dadda умножитель для внутреннего умножения в Карацубе :)

      Удалить