Вычисляем наибольший делитель

[vak]

До сих пор мои рассуждения про асинхронную логику носили несколько теоретический характер, но наконец я дозрел до реального примера. Попробуем соорудить схему для вычисления наибольшего общего делителя двух целых чисел. Ограничимся размером в 8 бит, до есть диапазон от 0 до 255. Исходный текст на воображаемом асинхронном диалекте языка Verilog мог бы выглядеть так:

module gcd (
    sync   slave        activate,              
    input  master [7:0] a,
    input  master [7:0] b,
    output master [7:0] c                      
);
    logic [7:0] x, y;

    while (activate) begin
        fork
            x <= a;
            y <= b;
        join

        while select
        x > y:
            x -= y;
        y > x:
            y -= x;
        endselect

        c <= x;
    end
endmodule

Исходный текст преобразуется компилятором в схему, составленную из элементарных асинхронных примитивов:



Результат компиляции на языке SystemVerilog получается следующий:

module gcd (
      sync.slave         activate,
    dlogic.master_input  a,
    dlogic.master_input  b,
    dlogic.master_output c
);
    //
    // Sequencers.
    //
    sync loop_out();
    Loop loop1 (activate, loop_out.master);

    sync s1(), s2();
    Sequence seq1 (loop_out.slave, s1.master, s2.master);

    sync s3(), s4();
    Sequence seq2 (s2.slave, s3.master, s4.master);

    //
    // Inputs.
    //
    sync par_xout(), par_yout();
    Concur par (s1.slave, par_xout.master, par_yout.master);

    dlogic#(8) a_fetch(), b_fetch();
    Fetch fp1 (par_xout.slave, a, a_fetch.master_output);
    Fetch fp2 (par_yout.slave, b, b_fetch.master_output);

    //
    // Do-while loop.
    //
    dlogic do_guard();
    sync do_activate();
    While wh1 (s3.slave, do_guard.master_input, do_activate.master);

    sync bar_xact(), bar_yact();
    dlogic xcompare_out(), ycompare_out();
    Bar b1 (do_guard.slave_output, do_activate.slave,
        xcompare_out.master_input, bar_xact.master,
        ycompare_out.master_input, bar_yact.master);

    //
    // Variable X subtract and compare.
    //
    dlogic#(8) xmix_in(), xmix_out();
    CallMux#(8) cmx (a_fetch.slave_input, xmix_in.slave_input, xmix_out.master_output);

    dlogic#(8) xsub_out();
    Fetch fx (bar_xact.slave, xsub_out.master_input, xmix_in.master_output);

    dlogic#(8) x1(), x2(), x3(), x4(), x5();
    dlogic#(8) y1(), y2(), y3(), y4();
    BinaryFunc_Sub#(8) subx (xsub_out.slave_output,
        x5.master_input, y2.master_input);

    BinaryFunc_GT#(8) gtx (xcompare_out.slave_output,
        x2.master_input, y3.master_input);

    Variable5#(8) x (xmix_out.slave_input, x1.slave_output,
        x2.slave_output, x3.slave_output, x4.slave_output, x5.slave_output);

    //
    // Variable Y subtract and compare.
    //
    dlogic#(8) ymix_in(), ymix_out();
    CallMux#(8) cmy (b_fetch.slave_input, ymix_in.slave_input, ymix_out.master_output);

    dlogic#(8) ysub_out();
    Fetch fy (bar_yact.slave, ysub_out.master_input, ymix_in.master_output);

    BinaryFunc_Sub#(8) suby (ysub_out.slave_output,
        y1.master_input, x4.master_input);

    BinaryFunc_GT#(8) gty (ycompare_out.slave_output,
        y4.master_input, x3.master_input);

    Variable4#(8) y (ymix_out.slave_input, y1.slave_output,
        y2.slave_output, y3.slave_output, y4.slave_output);

    //
    // Result output.
    //
    Fetch fc (s4.slave, x1.master_input, c);
endmodule

Временные диаграммы работы этой схемы можно видеть ниже. Кликайте чтобы увеличить. Здесь производятся вычисления для пяти тестовых случаев:
28 и 21 -> 7
52 и 39 -> 13
70 и 56 -> 14
112 и 80 -> 16
203 и 116 -> 29

Comments

[ygam]

На меня когда-то давно произвел впечатление язык SISAL: фукнциональный язык программирования с нормальным синтаксисом, а не со скобочками. Этот Verilog мне его напоминает.

[vak]

Некоторое отдалённое сходство есть. Verilog унаследовал синтаксис от языка HiLo, разработанного в Британии в конце 70-х. Видно, тогда такая мода была.