May 27th, 2013

Waveform 8 delay 5

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





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

1. Введение

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

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

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

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

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


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

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

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

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

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

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

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

Collapse )

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

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

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




Collapse )

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

Collapse )

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

Collapse )

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



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

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

Collapse )

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

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

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

Collapse )

Этот дизайн можно гонять на довольно неплохой тактовой частоте - 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




Collapse )

У такого описания есть несколько проблем стиля, которые 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.

Collapse )

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

Collapse )

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

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

Collapse )

Collapse )

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

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

Collapse )

Collapse )

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

Collapse )

Collapse )

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%)