?

Log in

No account? Create an account
Почему микроэлектроника не сводится к гонке за нанометрами - Юрий Панчул [entries|archive|friends|userinfo]
Money can buy bandwidth. Latency requires bribing God.

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Почему микроэлектроника не сводится к гонке за нанометрами [May. 27th, 2013|10:04 pm]
Yuri Panchul
[Tags|]





Почему микроэлектроника не сводится к гонке за нанометрами
Юрий Панчул, Саннивейл, Калифорния, апрель-май 2013

1. Введение

Господа! В нескольких ветках предыдущего поста возникла дискуссия, сводится ли микроэлектроника к гонке за нанометрами.

Ответ на этот вопрос не менее архиважен для будущего России, чем судьба Пусси Райотс.

Ведь если микроэлектроника сводится к гонке за нанометрами, то российским микроэлетронщикам нечего ловить. Все, что им остается в жизни - это слушать оппозиционные рок-песни, наблюдая за клином протестантских журавлей в небе. Ибо Интел "держит самый маленький нанометр за яйца", а коварный Госдеп следит чтобы россияне всегда отставали от передового нанометра минимум на два поколения. (Иными словами, правительство США ограничивает technology transfer за рубеж для самых новых технологий, в исследованиях и разработке которых использовались какие-либо гранты от американского правительства).

К счастью, микроэлектроника НЕ сводится к гонке за нанометром, и российским разработчиками микросхем ЕСТЬ что ловить. В частности, они могут создавать прибавочную стоимость за счет выдумывания более хитрой микроархитектуры специализированных IP-блоков и лицензирования оных международным компаниям.

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


2. Отступление. Архитектура и микроархитектура - два большие разницы.

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

1. У Юлии Латыниной, also known as "стрелка осциллографа".
2. У чистых программистов, которые рассматривают процессор как черный ящик.
3. У чистых физиков, которые видят на уровне транзистора.

Чистым програмистам при слове "микроархитектура" мерещится либо архитектура, либо многоядерность, либо выплывшее из какой-то старой книжки смутное слово "микрокод". А чисто физическое видение мира иногда передается даже некоторым программистам, которые специализируются на EDA-тулах физического уровня (EDA = Electronic Design Automation).

Поэтому введем понятия архитектуры и микроархитектуры.

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

Микроархитектура процессора - это то, как процессор выглядит для разработчика логики (но не физики) процессора. В нее входит организация конвейера, алгоритм предсказателя перехода, такие трюки как forwarding, register renaming и т.д.


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

Аналогия: Архитектура - техника вождения автомобиля (что происходит при нажатии на газ, тормоз, повороте руля), микроархитектура - как устроен автомобиль (двигатель, трансмиссия, соединения и т.д.).

С этим все. Теперь:


3. Разъяснение на пальцах концепций комбинационной (combinational), секвенциальной (sequential) и конвейерной (pipelined) организации вычислений

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

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





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

Это пример секвенциальной (sequential) организации вычислений. Частным случаем такой организации вычислений является популярный в 1970-х годах микрокод - трюк, который я не буду рассматривать в данном посте.



Наконец, если у вас есть много комнат, то можно организовать конвейер (pipeline), который будет обеспечивать наибольшую пропускную способность, в идеальном случае определяемую только одним (самым медленным) специалистом. В неидеальном случае допризывник может начать скандалить и затормозит процесс для всех (stall) или для всех. кто стоит за ним (slip). Против этого существуют всякие out-of-order методы, которые я не буду рассматривать в этом посте - наш "военкомат" (конвейер для квадратного корня) будет работать идеально.





4. Проиллюстрируем наши рассуждения кодом и мигающими лампочками

Для иллюстрации я не буду использовать конвейерный процессор, а возьму нечто гораздо более базовое, а именно покажу свою реализацию несколькими способами хардвера для вычисления целочисленного квадратного корня. Я выложил весь код на https://code.google.com/p/fpga-examples/source/browse/trunk/showroom/isqrt/

Если вы никогда не слышали слова "верилог", "синтез", "симуляция", то я рекомендую вам для начала прочитать мой пост в ru_programming

http://ru-programming.livejournal.com/1271886.html
Введение в дизайн харвера микросхем для тех программистов, которые этим никогда не занимались

Хотя существует куча книжек про хардверную имплементацию компьютерной арифметики для хардверных дизайнеров, я взял исходный алгоритм квадратного корня из софтверной книжки, которая называется "Восторг хакера", а потом его переделал его под хардвер. Почему "Восторг хакера"? Частично чтобы показать, как переделывать софтверные алгоритмы в хардвер, а частично потому, что первое издание этой книги просто валялось у меня под рукой. Вот второе издание:

Hacker's Delight (2nd Edition) by Henry S. Warren

http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685


Софтверный код из книжки Генри Воррена "Восторг хакера" выглядит вот так, я скопировал его с косметическими изменениями как отправную точку для последующих преобразований:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/001_software_implementation/isqrt.c

unsigned isqrt (unsigned x)
{
    unsigned m, y, b;

    m = 0x40000000;
    y = 0;

    while (m != 0)  // Do 16 times
    {
        b = y |  m;
        y >>= 1;
            
        if (x >= b)
        {
            x -= b;
            y |= m;
        }
            
        m >>= 2;
    }

    return y;
}


Вот мой тестик для данной функции, чтобы вы не сомневались, что она работает: http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/001_software_implementation/test.c


5. Комбинационная имплементация


Из кода книжки Воррена легко сварганить "наивную" имплементацию на Верилоге, которая будет работать (симулироваться, синтезироваться), но при виде которой хардверные инженеры будут от вас шарахаться. Дело в том, что "repeat" - это не так сказать компактный цикл в софтверной парадигме, а фактически "препроцессорная" директива скопировать код внутри него 16 раз:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/002_combinational_unstructured/isqrt.v

// combinational unstructured

module isqrt
(
    input      [31:0] x,
    output reg [15:0] y
);

    reg [31:0] m, tx, ty, b;

    always @*
    begin
        m  = 31'h4000_0000;
        tx = x;
        ty = 0;
    
        repeat (16)
        begin
            b  = ty |  m;
            ty = ty >> 1;
            
            if (tx >= b)
            begin
                tx = tx - b;
                ty = ty | m;
            end
            
            m = m >> 2;
        end

        y = ty [15:0];
    end

endmodule



Эта комбинационная (combinational) имплементация. Протокол общения с ней очень прост - нужно положить число на вход x, и через довольно длинное по хардверным меркам время (типа 100 наносекунд на Altera Cyclone II FPGA) на выходе появится правильное значение. Все эти томительные 100 наносекунд комбинаторная логика внутри дизайна будет чавкать и булькать вдоль довольно длинного combinational path, пока не прийдет в стабильное состояние. Вот фрагмент этого пути:



6. Секвенциальная имплементация

Количество логики можно сильно уменьшить, если имплементировать только одну итерацию цикла, с одним сумматором и компаратором, но прогнать через него временные значения x и y шестнадцать раз. Для того, чтобы железо (косная материя) поняла недвусмысленно, что бы хотите делать чего-нибудь итеративно, вам прийдется ввести концепцию тактового сигнала (clock) и импементировать фактически небольшой конечный автомат.


Иными словами построить секвенциальную (sequential) имплементацию:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/003_sequential/isqrt.v

// sequential

module isqrt
(
    input             clock,
    input             reset_n,
    input             run,
    input      [31:0] x,
    output reg        ready,
    output reg [15:0] y
);

    reg [31:0] m,  r_m;
    reg [31:0] tx, r_tx;
    reg [31:0] ty, r_ty;
    reg [31:0] b,  r_b;

    reg new_ready;

    always @*
    begin
        if (run)
        begin
            m  = 31'h4000_0000;
            tx = x;
            ty = 0;
        end
        else
        begin
            m  = r_m;
            tx = r_tx;
            ty = r_ty;
        end
    
        b  = ty |  m;
        ty = ty >> 1;
            
        if (tx >= b)
        begin
            tx = tx - b;
            ty = ty | m;
        end

        new_ready = m [0];
            
        m = m >> 2;
    end

    always @(posedge clock or negedge reset_n)
    begin
        if (! reset_n)
        begin
            ready <= 0;
            y     <= 0;
        end
        else if (new_ready)
        begin
            ready <= 1;
            y     <= ty [15:0];
        end
        else
        begin
            ready <= 0;

            r_m   <= m;
            r_tx  <= tx;
            r_ty  <= ty;
            r_b   <= b;

        end
    end

endmodule



7. Вопросы стиля при секвенциальной имплементации

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

1. А зачем делать два always-блока (combinational и clocked)? Почему бы не поместить все в один clocked always block? Ведь синтезатору все равно?
2. Почему все присваивания в combinational always block являются blocking, а все присваивания в clocked always block являются non-blocking?


Дело в том, что следование такому стилю позволяет решить две проблемы - неумышленные регистры (flip-flops) и race conditions.

Допустим человек хотел сделать временную переменную t, значение которой он не собирается сохранять между пульсами clock-а и собирался написать:

always @(posedge clock)
begin
    t = a;

    if (b)
        t = b;

    c <= t;
end


Теперь допустим, что человек забыл написать первое присваивание:

always @(posedge clock)
begin
    if (b)
        t = b;

    c <= t;
end


Синтезатор может просто тихо сгенерировать флип-флоп, а человек заметит ошибку только когда дизайн уже будет выпекаться на фабрике на Тайване, после чего его работодателю прийдется потратить пару миллионов долларов на ликвидацию последствий (и слава Аллаху, если дизайн не пойдет в чип на АЭС!).

Вот такой стиль позволяет заметить ошибку рано, ибо синтезатор начнет ругаться про level-sensitive latch, и дизайнер будет всегда уверен, какие переменные в его дизайне являются настоящими регистрами, а какие - эфемерной фикцией:

always @*
begin
    t = a;

    if (b)
        t = b;
end

always @(posedge clock)
    c <= t;


Для сходных целей я отделяю реальные регистры префиксом r_ от временных переменных (tx и r_tx).

А почему все присваивания в clocked always block являются non-blocking? Чтобы избежать race conditions.

Пример race condition:
always @(posedge clock)
    a = f (t);

always @(posedge clock)
    t = b;

Понятно, что значение a будет зависеть от прихоти симулятора - будет ли сначала обработан первый always-блок или второй.

А вот если сделать все присваивания в clocked always block - non-blocking, то эта проблема исчезает - a будет вычислено строго на основе значения t до фронта тактового сигнала.
always @(posedge clock)
    a <= f (t);

always @(posedge clock)
    t <= b;


А почему все присваивания в combinational always block являются blocking? Для однородности, скорости симуляции (меньше дельта-циклов) и чтобы делать как выше (присваивать значение по умолчанию и потом его менять).


Этот дизайн можно гонять на довольно неплохой тактовой частоте - 123 MHz на Altera Cyclone II FPGA, т.е. каждый цикл будет занимать всего восемь с небольшим наносекунд. К сожалению, это не впечатляет, так как на вычисление каждого квадратного корня будет тратиться 16 циклов или в сумме более 130 наносекунд, что хуже, чем комбинационный квадратный корень.

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

Пропускную способность дизайна можно существенно повысить тремя способами:

1. Введением нескольких вычислителей квадратного корня, работающих параллельно (в рамках военкоматной аналогии - введение нескольких комиссий на военкомат)
2. Организацией конвейера
3. Введением передового нанометра (этот способ из-за происков Госдепа против россиян мы не рассматриваем)


8. Постепенно введем конвейерную имплементацию

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

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

Пропускная способность может увеличиться не в 16 раз (так как во многих дизайнах стадии разные) но в несколько раз, за вычетом неравномерности скорости в разных стадиях и издержек (setup и hold time) на вход и выход из каждой комнаты.

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

Для начала сделаем подмодуль, который имплементирует комбинационную логику для одной итерации:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/004_combinational_structured_no_generate/isqrt_slice.v

module isqrt_slice
(
    input  [31:0] ix,
    input  [31:0] iy,
    output [31:0] ox,
    output [31:0] oy
);

    parameter [31:0] m = 32'h4000_0000;

    wire [31:0] b      = iy | m;
    wire        x_ge_b = ix >= b;

    assign ox = x_ge_b ? ix - b : ix;
    assign oy = (iy >> 1) | (x_ge_b ? m : 0);

endmodule





Теперь разобьем большой комбинационный модуль на такие подмодули:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/004_combinational_structured_no_generate/isqrt.v

// combinational structured no generate

module isqrt
(
    input  [31:0] x,
    output [15:0] y
);

    localparam [31:0] m = 32'h4000_0000;

    wire [31:0] wx [0:16], wy [0:16];

    assign wx [0] = x;
    assign wy [0] = 0;

    isqrt_slice #(m >>  0 * 2) i00 (wx [ 0], wy [ 0], wx [ 1], wy [ 1]);
    isqrt_slice #(m >>  1 * 2) i01 (wx [ 1], wy [ 1], wx [ 2], wy [ 2]);
    isqrt_slice #(m >>  2 * 2) i02 (wx [ 2], wy [ 2], wx [ 3], wy [ 3]);
    isqrt_slice #(m >>  3 * 2) i03 (wx [ 3], wy [ 3], wx [ 4], wy [ 4]);
    isqrt_slice #(m >>  4 * 2) i04 (wx [ 4], wy [ 4], wx [ 5], wy [ 5]);
    isqrt_slice #(m >>  5 * 2) i05 (wx [ 5], wy [ 5], wx [ 6], wy [ 6]);
    isqrt_slice #(m >>  6 * 2) i06 (wx [ 6], wy [ 6], wx [ 7], wy [ 7]);
    isqrt_slice #(m >>  7 * 2) i07 (wx [ 7], wy [ 7], wx [ 8], wy [ 8]);
    isqrt_slice #(m >>  8 * 2) i08 (wx [ 8], wy [ 8], wx [ 9], wy [ 9]);
    isqrt_slice #(m >>  9 * 2) i09 (wx [ 9], wy [ 9], wx [10], wy [10]);
    isqrt_slice #(m >> 10 * 2) i10 (wx [10], wy [10], wx [11], wy [11]);
    isqrt_slice #(m >> 11 * 2) i11 (wx [11], wy [11], wx [12], wy [12]);
    isqrt_slice #(m >> 12 * 2) i12 (wx [12], wy [12], wx [13], wy [13]);
    isqrt_slice #(m >> 13 * 2) i13 (wx [13], wy [13], wx [14], wy [14]);
    isqrt_slice #(m >> 14 * 2) i14 (wx [14], wy [14], wx [15], wy [15]);
    isqrt_slice #(m >> 15 * 2) i15 (wx [15], wy [15], wx [16], wy [16]);

    assign y = wy [16];

endmodule







У такого описания есть несколько проблем стиля, которые OK для небольших дизайнов, но которые могут превратиться в большие проблемы, когда количество cтрочек кода меряется в сотни тысяч.

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

И особенно не рекомендуется подсоединение к портам по позиции, а не по имени. То же относится к параметрам модулей. Даже для небольших модулей лучше методически подсоединять по имени, т.е. писать не "f #(a) i (b, c)", а "f #(.a (a)) i (.b (b), .c (c))". Потому что потом кто-нибудь введет в модуль f дополнительный параметр или порт, а кто-нибудь другой перепутает порядок или не обратит внимание на warning с подсоединением по умолчанию.

В SystemVerilog введена конструкция для специального подсоединения по имени по умолчанию (".*"), но она может не поддерживаться бесплатными тулами от Xilinx и Altera, которые я рекомендую для читателей, не имеющих доступа к Synopsys, Cadence и полной версии Mentor.


Итого, более дисциплинированная все еще комбинационная версия:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/005_combinational_structured_rigid_no_generate/isqrt.v

// combinational structured rigid no generate

module isqrt
(
    input  [31:0] x,
    output [15:0] y
);

    localparam [31:0] m = 32'h4000_0000;

    wire [31:0] ix [0:15], iy [0:15];
    wire [31:0] ox [0:15], oy [0:15];

    isqrt_slice #(.m (m >>  0 * 2)) i00 (.ix (ix [ 0]), .iy (iy [ 0]), .ox (ox [ 0]), .oy (oy [ 0]));
    isqrt_slice #(.m (m >>  1 * 2)) i01 (.ix (ix [ 1]), .iy (iy [ 1]), .ox (ox [ 1]), .oy (oy [ 1]));
    isqrt_slice #(.m (m >>  2 * 2)) i02 (.ix (ix [ 2]), .iy (iy [ 2]), .ox (ox [ 2]), .oy (oy [ 2]));
    isqrt_slice #(.m (m >>  3 * 2)) i03 (.ix (ix [ 3]), .iy (iy [ 3]), .ox (ox [ 3]), .oy (oy [ 3]));
    isqrt_slice #(.m (m >>  4 * 2)) i04 (.ix (ix [ 4]), .iy (iy [ 4]), .ox (ox [ 4]), .oy (oy [ 4]));
    isqrt_slice #(.m (m >>  5 * 2)) i05 (.ix (ix [ 5]), .iy (iy [ 5]), .ox (ox [ 5]), .oy (oy [ 5]));
    isqrt_slice #(.m (m >>  6 * 2)) i06 (.ix (ix [ 6]), .iy (iy [ 6]), .ox (ox [ 6]), .oy (oy [ 6]));
    isqrt_slice #(.m (m >>  7 * 2)) i07 (.ix (ix [ 7]), .iy (iy [ 7]), .ox (ox [ 7]), .oy (oy [ 7]));
    isqrt_slice #(.m (m >>  8 * 2)) i08 (.ix (ix [ 8]), .iy (iy [ 8]), .ox (ox [ 8]), .oy (oy [ 8]));
    isqrt_slice #(.m (m >>  9 * 2)) i09 (.ix (ix [ 9]), .iy (iy [ 9]), .ox (ox [ 9]), .oy (oy [ 9]));
    isqrt_slice #(.m (m >> 10 * 2)) i10 (.ix (ix [10]), .iy (iy [10]), .ox (ox [10]), .oy (oy [10]));
    isqrt_slice #(.m (m >> 11 * 2)) i11 (.ix (ix [11]), .iy (iy [11]), .ox (ox [11]), .oy (oy [11]));
    isqrt_slice #(.m (m >> 12 * 2)) i12 (.ix (ix [12]), .iy (iy [12]), .ox (ox [12]), .oy (oy [12]));
    isqrt_slice #(.m (m >> 13 * 2)) i13 (.ix (ix [13]), .iy (iy [13]), .ox (ox [13]), .oy (oy [13]));
    isqrt_slice #(.m (m >> 14 * 2)) i14 (.ix (ix [14]), .iy (iy [14]), .ox (ox [14]), .oy (oy [14]));
    isqrt_slice #(.m (m >> 15 * 2)) i15 (.ix (ix [15]), .iy (iy [15]), .ox (ox [15]), .oy (oy [15]));

    assign ix [ 0] = x;
    assign ix [ 1] = ox [ 0];
    assign ix [ 2] = ox [ 1];
    assign ix [ 3] = ox [ 2];
    assign ix [ 4] = ox [ 3];
    assign ix [ 5] = ox [ 4];
    assign ix [ 6] = ox [ 5];
    assign ix [ 7] = ox [ 6];
    assign ix [ 8] = ox [ 7];
    assign ix [ 9] = ox [ 8];
    assign ix [10] = ox [ 9];
    assign ix [11] = ox [10];
    assign ix [12] = ox [11];
    assign ix [13] = ox [12];
    assign ix [14] = ox [13];
    assign ix [15] = ox [14];

    assign iy [ 0] = 0;
    assign iy [ 1] = oy [ 0];
    assign iy [ 2] = oy [ 1];
    assign iy [ 3] = oy [ 2];
    assign iy [ 4] = oy [ 3];
    assign iy [ 5] = oy [ 4];
    assign iy [ 6] = oy [ 5];
    assign iy [ 7] = oy [ 6];
    assign iy [ 8] = oy [ 7];
    assign iy [ 9] = oy [ 8];
    assign iy [10] = oy [ 9];
    assign iy [11] = oy [10];
    assign iy [12] = oy [11];
    assign iy [13] = oy [12];
    assign iy [14] = oy [13];
    assign iy [15] = oy [14];

    assign y       = oy [15];

endmodule



Правда как вы понимаете, у этой версии есть очень противная черта - многословие. К счастью, в районе 2000-го года в новый стандарт верилога (Verilog 2000 который из-за опоздания стал Verilog 2001) спионерили полезную конструкцию из VHDL под названием generic и с ее помощью адское многословие Verilog-95 удалось обуздать. До появления generate в верилоге наиболее хитрозадые пользователи использовали Perl-генерируемый код, при виде которого возникало желание никогда не связываться с этой профессией, а стать феминистическим журналистом, как Наталья Радулова.


Все еще комбинационная версия, использует generate и genvar:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/006_combinational/isqrt.v

// combinational structured

module isqrt
(
    input  [31:0] x,
    output [15:0] y
);

    localparam [31:0] m = 32'h4000_0000;

    wire [31:0] ix [0:15], iy [0:15];
    wire [31:0] ox [0:15], oy [0:15];

    generate
        genvar i;

        for (i = 0; i < 16; i = i + 1)
        begin : u
            isqrt_slice #(.m (m >> i * 2)) inst
            (
                .ix (ix [i]),
                .iy (iy [i]),
                .ox (ox [i]),
                .oy (oy [i])
            );
        end

        for (i = 1; i < 16; i = i + 1)
        begin : v
            assign ix [i] = ox [i - 1];
            assign iy [i] = oy [i - 1];
        end

    endgenerate


    assign ix [0] = x;
    assign iy [0] = 0;

    assign y = oy [15];

endmodule



Почти готово.

9. Конвейерная имплементация с 16 стадиями конвейера


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

Переименовываем комбинационный модуль isqrt_slice, чтобы не перепутать:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/007_pipelined_16_stages/isqrt_slice_comb.v

И вот версия с регистрами

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/007_pipelined_16_stages/isqrt_slice_reg.v

module isqrt_slice_reg
(
    input             clock,
    input             reset_n,
    input      [31:0] ix,
    input      [31:0] iy,
    output reg [31:0] ox,
    output reg [31:0] oy
);

    parameter [31:0] m = 32'h4000_0000;

    wire [31:0] cox, coy;

    isqrt_slice_comb #(.m (m)) i
    (
        .ix ( ix  ),
        .iy ( iy  ),
        .ox ( cox ),
        .oy ( coy )
    );

    always @(posedge clock or negedge reset_n)
    begin
        if (! reset_n)
        begin
            ox <= 0;
            oy <= 0;
        end
        else
        begin
            ox <= cox;
            oy <= coy;
        end
    end

endmodule






Конвейерная версия хардверной имплементации квадратного корня с 16-ю стадиями конвейера:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/007_pipelined_16_stages/isqrt.v

// pipelined - 16 stages

module isqrt
(
    input         clock,
    input         reset_n,
    input  [31:0] x,
    output [15:0] y
);

    localparam [31:0] m = 32'h4000_0000;

    wire [31:0] ix [0:15], iy [0:15];
    wire [31:0] ox [0:15], oy [0:15];

    generate
        genvar i;

        for (i = 0; i < 16; i = i + 1)
        begin : u
            isqrt_slice_reg #(.m (m >> i * 2)) inst
            (
                .clock   ( clock   ),
                .reset_n ( reset_n ),
                .ix      ( ix [i]  ),
                .iy      ( iy [i]  ),
                .ox      ( ox [i]  ),
                .oy      ( oy [i]  )
            );
        end

        for (i = 1; i < 16; i = i + 1)
        begin : v
            assign ix [i] = ox [i - 1];
            assign iy [i] = oy [i - 1];
        end

    endgenerate


    assign ix [0] = x;
    assign iy [0] = 0;

    assign y = oy [15];

endmodule





Пропускная способность (количество вычислений квадратного корня в секунду) у данного устройства будет 175 миллионов вычислений при имплементации на Altera Cyclone II. Хотя каждый отдельный корень будет проходить через устройство за 16 циклов или (1000 / 175) * 16 = примерно 90 наносекунд, одновременно в устройстве будут находится 16 корней на разных стадиях обработки, т.е. обрабатываться будет корень в цикл.

Также стоит учесть, что данный модуль займет менее одного процента ресурсов FPGA, т.е. мы можем насовать в один FPGA кучу таких модулей и вычислять миллиарды квадратных корней в секунду:


Timing report:





Fitter report:




Для иллюстрации поведения дизайнов во времени по циклам тактового сигнала привожу три теста и три waveform diagrams, сделанные в бесплатной версии ModelSim-а. Правда имейте в виду, что я не ставил реальный timescale, т.е. все числа пикосекунд нужно игнорировать и ориентироваться только по тактовому сигналу. Комбинационный же дизайн симулируется как работающий мгновенно (т.е. все действия внутри вычислительного модуля происходят за время 0:


Тесты для комбинационной, секвенциальной и конвейерной имплементаций:

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/006_combinational/testbench.v

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/003_sequential/testbench.v

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/008_pipelined/testbench.v



Waveform diagrams для комбинационной, секвенциальной и конвейерной имплементаций:








10. Конвейерная имплементация с параметризуемым количеством стадий конвейера - 1, 2, 4, 8 или 16 стадий

И наконец, с небольшим творческим усилием можно сделать модуль параметризуемым - с возможностью задания ему количества стадий конвейера - 1, 2, 4, 8 или 16 стадий.

http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/008_pipelined/isqrt.v

// pipelined with configurable number of stages

module isqrt
(
    input         clock,
    input         reset_n,
    input  [31:0] x,
    output [15:0] y
);

    parameter n_pipe_stages = 16;

    localparam n_slices           = 16;
    localparam n_slices_per_stage = n_slices / n_pipe_stages;

    localparam [31:0] m = 32'h4000_0000;

    wire [31:0] ix [0:15], iy [0:15];
    wire [31:0] ox [0:15], oy [0:15];

    generate
        genvar i;

        for (i = 0; i < 16; i = i + 1)
        begin : u
            if (i % n_slices_per_stage != n_slices_per_stage - 1)
            begin
                isqrt_slice_comb #(.m (m >> i * 2)) inst
                (
                    .ix      ( ix [i]  ),
                    .iy      ( iy [i]  ),
                    .ox      ( ox [i]  ),
                    .oy      ( oy [i]  )
                );
            end
            else
            begin
                isqrt_slice_reg #(.m (m >> i * 2)) inst
                (
                    .clock   ( clock   ),
                    .reset_n ( reset_n ),
                    .ix      ( ix [i]  ),
                    .iy      ( iy [i]  ),
                    .ox      ( ox [i]  ),
                    .oy      ( oy [i]  )
                );
            end
        end

        for (i = 1; i < 16; i = i + 1)
        begin : v
            assign ix [i] = ox [i - 1];
            assign iy [i] = oy [i - 1];
        end

    endgenerate


    assign ix [0] = x;
    assign iy [0] = 0;

    assign y = oy [15];

endmodule


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

Версия с 4 стадиями конвейера (фрагмент):



Версия с 8 стадиями конвейера (фрагмент):



Соответственно будет изменяться количество логических функций, количество регистров и максимальная тактовая частота.

Я сделал табличку для синтеза на Altera Cyclone II, на нем все довольно нелинейно, но вы можете увидеть так сказать тренд в тактовой частоте:

# стадий конвейера # комбинаторных функций # регистров частота, MHz
1 82 5 n/a
2 82 15 79.38
4 142 38 74.31
8 102 48 127.18
16 94 111 175.53


А вот пепелац, на котором я прогнал все тесты вживую с миганиями лампочек - студенческая плата Altera / Terasic DE1:




Poll #1915941 Почему микроэлектроника не сводится к гонке за нанометрами

Вам понравился мой образовательный пост? Хотите еще?

Это был образовательный пост?
16(19.3%)
Мои родители не одобряют, что я читаю ваш ЖЖ
3(3.6%)
Очень понравился, вот такое раз в месяц - и мы сможем возродить СССР!
48(57.8%)
Я почувствовала в посте сексизм и контрреволюционность, но не могу указать, в какой строчке
10(12.0%)
Из-за бугра плюете?
6(7.2%)

Что вам больше всего понравилось в моем посте?

Вступление про клин протестантских журавлей и Пусси Райотс
7(8.9%)
Дискуссия про архитектуру и микроархитектуру
10(12.7%)
Аналогия про комбинационный, секвенциальный и конвейерный военкомат
12(15.2%)
Путь от "наивной" комбинационной имплементации к структурированной с generate
10(12.7%)
Секвенциальная имплементация и вопросы стиля хорошо верифицируемого HDL
8(10.1%)
Конвейерная версия, ее параметризованная форма, анализ тайминга и пропускной способности
10(12.7%)
Пепелац с кнопочками и мигающими лампочками
22(27.8%)

Какая девушка, образ которой приведен в посте, имеет самое одухотворенное выражение лица?

Надя Толокно
32(41.0%)
Юлия Латынина
7(9.0%)
Наталья Радулова
13(16.7%)
Я готова выставить свои фотографии ню для следущего поста Панчула с кодом на верилоге или ассеблере
9(11.5%)
Из-за бугра плюете?
17(21.8%)
LinkReply

Comments:
Page 1 of 4
<<[1] [2] [3] [4] >>
[User Picture]From: latexzapal
2013-05-28 05:10 am (UTC)
ПЕПЕЛАЦ!
(Reply) (Thread)
(Deleted comment)
[User Picture]From: ammosov
2013-05-28 05:18 am (UTC)
под кат!
(Reply) (Thread)
[User Picture]From: panchul
2013-05-28 05:22 am (UTC)
Юра, ну неужели трудно пролистать? По моей самооценке это один из лучших пост, который я когда-либо написал в ЖЖ (разве что после "Радулова встречает тракториста").
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: freedom_of_sea
2013-05-28 05:25 am (UTC)

почему русские инженеры не могут сделать нанометр

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

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

Софтвер (включая верилог) это по сути внутренняя эммиграция инженеров от вороватого гнета чиновников.
(Reply) (Thread)
[User Picture]From: zevaka_derevnia
2013-05-28 05:30 am (UTC)

Re: почему русские инженеры не могут сделать нанометр

;-)))))
(Reply) (Parent) (Thread)
[User Picture]From: dom3d
2013-05-28 05:25 am (UTC)
Юра, я только про Радулову Наталью Викторовну radulova понял.
(Reply) (Thread)
[User Picture]From: panchul
2013-05-28 05:41 am (UTC)
Радулова хорошая женщина. Когда-нибудь я ее встречу, схожу с нею на экскурсию в Кремль и в Мавзолей (если Ленина к тому времени не похоронят). А также в кафе Прага (мой любимый общепит в 1990 году), в ее редакцию (контакты в Коммерсанте мне пригодятся) и на поезде "Сапсан" - в Санкт Петербург, чтобы взявшись с нею за руки гулять во время белых ночей.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: zevaka_derevnia
2013-05-28 05:31 am (UTC)
Правда - очень хороший пост, спасибо! Верилог не знаю (поздновато, думаю), а остальное понятно.
(Reply) (Thread)
[User Picture]From: zevaka_derevnia
2013-05-28 05:49 am (UTC)
P.S. Хреновина классная!
(Reply) (Parent) (Thread)
[User Picture]From: livejournal
2013-05-28 05:32 am (UTC)

Почему микроэлектроника не сводится к гонке за наноме

User search_facility referenced to your post from Почему микроэлектроника не сводится к гонке за нанометрами saying: [...] познавательно Originally posted by at Почему микроэлектроника не сводится к гонке за нанометрами [...]
(Reply) (Thread)
From: realurix
2013-05-28 05:54 am (UTC)
> Какая девушка, образ которой приведен в посте, имеет самое одухотворенное выражение лица?
ALTERA - тоже как бы на женское имя смахивает. Жаль, что её нет в списке...
(Reply) (Thread)
[User Picture]From: roland
2013-06-02 08:58 am (UTC)
Скажите пожалуйста, можно ли на базе похожих студенческих плат собрать FPGA майнер для Bitcoin, насколько это сложно и сколько будет стоить в расчете на 1 GH/sec? Ну и про Litecoin тот же вопрос, с учетом того, что алгоритм там другой, и говорят что под него майнер собрать невозможно.
Спасибо.
(Reply) (Parent) (Thread)
[User Picture]From: lider
2013-05-28 05:58 am (UTC)
"Иными словами построить секвенциальную (sequential) имплементацию"
Вайфочко, позачиняй віндови, щоб чілдренятка не простудилися.
(Reply) (Thread)
[User Picture]From: spamsink
2013-05-28 06:07 am (UTC)
Кроме лингвистических погрешностей, там еще есть и технические опущения. ФПГА ФПГой, но большие дяди в данном случае просто нашли бы минимальную форму для этих шестнадцати несчастных булевских функций от 32 аргументов; скажем, что для старшего бита эта функция будет просто сравнением с константой, а для следующего за ним - сравнением на принадлежность к паре диапазонов, очевидно невооруженным глазом.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: bronfenb
2013-05-28 06:38 am (UTC)
У российских граждан на столько плотно засело в головах советское "сделай сам", что они не признают никаких российских технологических успехов, если технология с начала и до конца не реализована в России. Учитывая, что таких технологий в современной глобальной экономике физически не существует и существовать не может, возникает замкнутый круг: успехов нет потому, что они невозможны в такой изоляционистской интерпретации.
(Reply) (Thread)
[User Picture]From: panchul
2013-05-28 06:46 am (UTC)
Вот-вот. А так как Госдеп действительно слегка мешает экспорт-контролем и ограничением трансфера технологий, сделанных с использованием грантов правительства - то всегда есть на кого свалить.

А самим усестся за ЖЖ какого-нибудь Дмитрия Ольшанского и спорить о словах на основе художественной литературы. И ждать, чтобы президентом России назначили бы Пусси Райот, а она бы привезла Стива Джобса, который бы научил.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: sdiki
2013-05-28 06:42 am (UTC)
Если перевести все это на английский и опубликовать, то интересно было бы сопоставить соотношение вопросов "по существу" и вопросов к иллюстрациям. Подозреваю, что вопросов по поводу Латыниной или Радуловой "кто это" оказалось бы на порядок больше.
(Reply) (Thread)
[User Picture]From: panchul
2013-05-28 06:54 am (UTC)
Дык на английском текстов на данную тематику завались. Я как-раз пинаю разных корпоративных орлов, чтобы те сфинансировали перевод и издание кое-чего на русский.

Проблема с русскими текстами на данную тему - есть куча текстов типа физтеховской методички А.Л.Ларин "Основы цифровой Электроники", но они излагают материал без использования HDL (Verilog или VHDL). Потом есть книги на русском по Verilog и VHDL, но они не содержат концепций структуризации дизайна и (особенно!) стиля а-ля японская книжка за 42 тысячи йен STARC HDL Design Guide. Или книжка по Computer Architecture, но без привязки к logic design.

Все это нужно объединить в одно целое, а то получается. что машину можно купить либо без двигателя, либо без колес, либо без корпуса.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: kirill_lunjov
2013-05-28 07:15 am (UTC)
В принципе все понятно.
И что делать вполне есть.
Вопрос в другом - сегодня вопросы финансирования работ со стороны государства решают те, кто путает чипы и чипсы - писал как-то отдельно (путал эти понятия один из трех членов комиссии областного правительства по распределению грантов по новым технологиям).
Что же касается частного бизнеса, то в России сегодня - из-за налогообложения предприятий (не путать с "самым низким" подоходным налогом в мире!) почти любое производство не выгодно.
Скажем, из Калининградской области экспортируют зерно, при этом почти 90% муки импортируют сегодня из той же Польши и Литвы.

Что же касается самой темы поста, то могу сказать, что последний НИР (1990), что не дали закончить, называлась "Процессор логического моделирования" и суть его состояла в том, чтобы разбить процесс работы БИС на кирпичики - сделать для них процессорную реализацию и по принципу того самого конвейера проводить моделирование.
Цель - сократить мощности, задействованные для аналогичной задачи на той же супер-ЭВМ.

Но самое интересное из канувшего в лету подхода, который мог бы (на мой взгляд) интересен и сегодня, это процесс "Кронос".
При мне сравнивали эффективность одних и тех задач "Кронос" (процессор 5 мГц) и "Электроника 79" (аналог DEC PDP 11/70) и "Кронос" показал эффективность, как на драйверах, так и собственно на вычислениях эффективность в 2-3 раза выше.

А что тот или иной подход - собственно на основе математике может много решить, так припоминаю простой пример.
в 80-ые в СССР не могли приобретать спецпроцессоры, скажем, для измерения кварцевым толщиномером (там нелинейная зависимость и 6-этажная формула с тангенсами и арктангесами от некоего параметра C, который определялся для каждого материала таблично, изначально определяемой, - представляете затраты на прямую апроксимацию вычислений?).
Какой нашел выход?
В СССР выпускался прибор промежуточной апроксимации...
Мне показалось, что разница между двумя функциями напоминает квадратичную (именно разница).
Затем я попросил знакомого математика подобрать тот или иной квадратичный полином для апроксимации этой РАЗНИЦЫ. Лучше всего подошли полиномы Лагранжа.

В итоге, если сам сигнал (частота) - х, то конечная формула стала Ax*x + x + C, где, А и С были константами с таблицой соответствия всего диапазона параметра "с" по американскому источнику.
Тот процессор, что реализовывал формулу точного вычисления стоил (в силу малой серии) на тот момент около 600-700 долларов, и мог работать с скоростью вычисления не быстрее, чем раз за 0,5 сек.

Это определяло ошибку (физические аспекты опускаю) измерения в районе 0,5-1% от конечного значения.
Очевидно, что предложенная нами формула реализовывалась на простейшей схеме задания двух параметров + схему умножения и сумматора)))

Да, схема позволяла проводить измерение каждые 0,1 сек с погрешностью - относительно изначальной формулы - не более 0,1%, но при этом ошибка измерения по изначальной схеме с американским процессором сокращалась минимум в 5 раз (за счет меньшего времени вычисления и более высокой частоты измерения значения).
то есть, как ни странно, но совокупная ошибка - после применения новой схемы была даже меньше пионерской схемы со спецпроцессором, за счет увеличения скорости))) - где-то 0,2% от всей величины.
То, что схема, реализующая формулу даже на "рассыпухе" стоила минимум в 10 раз дешевле того же процессора - очевидно.

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

Хотя справедливости ради надо сказать, что нанометры важны - ведь и новую архитектуру можно реализовать при помощи тех самых нанометров)))

(Reply) (Thread)
[User Picture]From: gineer
2013-05-28 02:10 pm (UTC)
\\Хотя с другой стороны особо доказывать, что математический, комбинаторный (архитектурный) подход может дать выигрыш там, где якобы все решают нанометры, понятно любому, к то решал практические задачи.

Например, плотность и соответственно емкость чипов памяти,
зависит исключительно от "нанометров",
и никаким "математический, комбинаторный (архитектурный) подход" выигрыша там не получиш.

А то что объем оперативной памяти доступной процессору -- это весьма важная характеристика...
"понятно любому, к то решал практические задачи."
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: to_r
2013-05-28 07:58 am (UTC)
лайкъ!
(Reply) (Thread)
[User Picture]From: Andrey Rogovsky
2013-06-02 03:48 am (UTC)
Дизлайк ибо это чепуха
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: vigna
2013-05-28 08:18 am (UTC)
Мне не нравится, что без ката!
(Reply) (Thread)
[User Picture]From: panchul
2013-05-28 10:37 pm (UTC)
Я понимаю, но сегодня я ничего не могу поделать со своим эгоизмом! Я прошу тебя раз в год смириться и пролистать!
(Reply) (Parent) (Thread)
[User Picture]From: Ivan Sopov
2013-05-28 08:28 am (UTC)
Сложно разобраться, но в абзаце:

>Переименовываем комбинационный модуль isqrt_slice, чтобы не перепутать:
>http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/007_pipelined_16_stages/isqrt_slice_reg.v
>И вот версия с регистрами
>http://fpga-examples.googlecode.com/svn/trunk/showroom/isqrt/007_pipelined_16_stages/isqrt_slice_reg.v

Точно одна и та же ссылка должны быть два раза вставлена?
(Reply) (Thread)
[User Picture]From: panchul
2013-05-28 03:53 pm (UTC)
Ой, описался, спасибо, что заметили. В первом нужно ..._comb.v
(Reply) (Parent) (Thread)
[User Picture]From: sir66
2013-05-28 10:04 am (UTC)
Неправильный пост. Кому нужны эти корни им цена копейка, ты бы обьяснил народу как биткойны майнить на конвейере. У самого небось в подвале давно уже биткойн фабрика.
(Reply) (Thread)
[User Picture]From: 1i7
2013-05-30 02:02 pm (UTC)
(Reply) (Parent) (Thread) (Expand)
Page 1 of 4
<<[1] [2] [3] [4] >>