Симулятор RTL - это очень просто

[vak]

Традиционно считается, что моделирование цифровой аппаратуры это технически очень сложная задача. Программы-симуляторы для Verilog и VHDL стоят жутких денег. SystemC хоть и бесплатный, но сущий ад для разработчиков. Хуже того: уровень абстракции имеет тенденцию повышаться, и сейчас мало кто вообще понимает, что происходит в симуляторе на самом нижнем уровне. Все нужные алгоритмы были описаны в научных статьях в начале 90-х и похоронены в библиотеках под толстым слоем пыли. В современных книжках в лучшем случае рассказывается про очередь событий и упоминаются дельта-циклы. Живем как питекантропы, поддерживая огонь в костре и не умея его зажечь.

Изначально я задумал это как задачку для продвинутых студентов: сваять в качестве курсовой работы простейший RTL-симулятор для цифровых схем. Но когда стал придумывать 'правильный ответ', оказалось все не так просто. Копать пришлось несколько глубже, чем может осилить студент. Поэтому пришлось превратить это просто в красивую иллюстрацию технологии симуляции. Исходники можно взять здесь: https://github.com/sergev/vak-opensource/tree/master/hardware/rtlsim

Основные установки:
1) Язык Си. Максимальная простота и ясность.
2) Простые структуры данных. Никаких объектов или шаблонов.
3) Событийно-управляемое моделирование: максимальная эффективность.
4) Динамическая память не используется.
5) Сопроцессы реализованы посредством стандартных POSIX-функций семейства getcontext(), входящих в библиотеку glibc.

Вся реализация уложилась примерно в 200 строчек Си-шного кода. Это, наверное, самая красивая программа, которую мне доводилось делать.

Пример симуляции есть в предыдущем посте: https://vak.dreamwidth.org/213855.html
Можно сравнить с тем же примером на Верилоге: https://vak.dreamwidth.org/213634.html

Значения

    typedef unsigned long long value_t;

Тип value_t -- 64-битное беззнаковое целое, используется для счетчика времени и для значений сигналов. Для увеличения эффективности, его можно переопределить в unsigned long, если не нужны сигналы шириной больше 32-х бит.

Время

    value_t time_ticks;

Внешняя переменная time_ticks отслеживает виртуальное модельное время.

Сигналы
Тип signal_t -- это структура данных, реализующая логический сигнал или шину, с шириной от 1 до 64 бит. Примерный эквивалент верилоговского типа reg. Определяется как:

    typedef struct {
        ...
        const char *name;
        value_t     value;
        ...
    } signal_t;

Программа пользователя может читать значения полей name и value, но не должна их изменять.

Сигналы объявляются в программе как статические переменные, используя макрос signal_init(). В качестве параметров задаются имя и начальное значение сигнала, например:

    signal_t clock = signal_init ("clock",  0);

Изменить значение сигнала можно вызовом функции signal_set(). Это соответствует неблокирующему присваиванию в Верилоге:

    signal_set (&clock, 1);

Процессы
Тип process_t -- структура данных, реализующая сопроцесс (lightweight thread), который моделирует поведение некоторого аппаратного блока. Для переключения сопроцессов используются стандартные POSIX-совместимые функции семейства swapcontext(), присутствующие в библиотеке glibc. Каждый процесс соответствует одному блоку 'always' в Верилоге. Определяется как:

    typedef struct {
        ...
        const char *name;
        ...
    } process_t;

Программа пользователя может читать значения поля name, но не должна его изменять.

Каждый процесс имеет собственный стек, выделяемый из стека родительского процесса. Обычно процессы создаются функцией main() при старте, так что расходуется основной стек программы. При создании процесса задается имя, главная процедура процесса и размер стека. Например:

    process_init ("counter", do_counter, 4096);

Здесь do_counter() - это процедура процесса. Для простых процессов обычно хватает стека в 4 килобайта. Главная процедура процесса работает по типовому алгоритму: устанавливает 'список чувствительности' и входит в бесконечный цикл, ожидая события и затем вычисляя новые значения для выходных сигналов. Например:

    void do_counter()
    {
        process_sensitive (&clock, POSEDGE);
        for (;;) {
            process_wait();
            ...
            signal_set (&count, count.value + 1);
            ...
        }
    }

Функция process_sensitive(signal, edge) добавляет сигнал и полярность фронта к 'списку чувствительности' текущего процесса. Она выделяет небольшую область памяти из стека (посредством alloca). Список чувствительности может быть произвольного размера. Полярность фронта задается флагом OSEDGE, NEGEDGE или 0 (оба фронта).

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

Функция process_wait(ticks) приостанавливает текущий процесс на указанный интервал модельного времени.

Глобальная переменная:

    process_t *process_current;

указывает на текущий процесс. Поле process_current->name можно использовать для выдачи сообщений трассировки.

Comments

[spamsink.livejournal.com]

Попробуй написать в своей системе

initial begin a = 0; b = 0; end
initial repeat (10) #10 begin a <= a + 2; b <= b + 3; end

assign abuf = a;
always @* begin sum = abuf + b; $display(sum); end

Я пишу

void do_buf () {
    process_sensitive (&a, 0);
    for (;;) {
        process_wait();
        signal_set (&abuf, a.value);
    }
}

void do_sum () {
    process_sensitive (&abuf, 0);
    process_sensitive (&b, 0);

    for (;;) {
        process_wait();

        printf ("%lld\n", abuf.value + b.value);
        signal_set(&sum, abuf.value + b.value);
    }
}

int main (int argc, char **argv)
{
    int i;
    process_init ("buf", do_buf, 4096);
    process_init ("sum", do_sum, 4096);

    for (i = 0; i < 10; ++i) {
    process_delay (10);

    signal_set(&a, a.value + 2);
    signal_set(&b, b.value + 3);
    }
    process_delay(100000);
    return 0;
}

Что я делаю не так? :)

[spamsink.livejournal.com]

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

[vak]

Да, переменную в макросе я исправлю, спасибо. У меня получается:

(10) sum = 3
(20) sum = 8
(30) sum = 13
(40) sum = 18
(50) sum = 23
(60) sum = 28
(70) sum = 33
(80) sum = 38
(90) sum = 43
(100) sum = 48

[spamsink.livejournal.com]

Ну да, но это же очевидным образом неправильно: значения, кратные 5, обязаны присутствовать.

[vak]

Доделал твой генератор случайных нетлистов и померял скорость. Моя реализация в 16 раз быстрее чем Icarus Verilog.

[spamsink.livejournal.com]

Надо понять, сколько и каких углов ты срезаешь. Реализация 4-уровневой логики (а для скаляров - еще и strength) тебя на сколько-то замедлит, но, надеюсь, не в 16 раз.

[vak]

4-state logic не особо сказывается: вычисления простые, и основное время тратится на переключение сопроцессов. Я прогнал этот же тест на Synopsys VCS - он в два раза быстрее. И понятно почему: swapcontext делает слишком много лишних действий. Если избавиться от вызова sigprocmask() и восстановления регистров FPU, мой симулятор будет быстрее чем Synopsys. Даже с 64-битной арифметикой. То есть имеет смысл переписать на longjmp() вместо swapcontext().

Вот мой вариант:

0000040000010002 b76ea027fb17fa95 554ac26b1fb14e61

real	0m0.990s
user	0m0.500s
sys	0m0.484s

Вот Synopsys:

Chronologic VCS simulator copyright 1991-2012
Contains Synopsys proprietary information.
Compiler version G-2012.09; Runtime version G-2012.09;  Feb 27 11:25 2013
0000040000010002 b76ea027fb17fa95 554ac26b1fb14e61
$finish called from file "random.v", line 2545.
$finish at simulation time               160800
           V C S   S i m u l a t i o n   R e p o r t 
Time: 160800
CPU Time:      0.530 seconds;       Data structure size:   0.0Mb
Wed Feb 27 11:25:51 2013

Тексты здесь, можешь попробовать на своих верилогах:
https://vak-opensource.googlecode.com/svn/trunk/hardware/rtlsim/random.v
https://vak-opensource.googlecode.com/svn/trunk/hardware/rtlsim/random.c

[spamsink.livejournal.com]

У нас VCS точно такой же. Но как ты собираешься пользоваться longjmp, если он на сопроцессы не рассчитан?
Кстати, как в твоей модели написать

always begin
    $display("waiting for var1");
    forever begin
        @(var1) $display("var1 changed, now waiting for var2");
        @(var2) $display("var2 changed, now waiting for var1");
    end
end

[vak]

Longjmp сам по себе и есть способ переключения сопроцессов: http://fanf.livejournal.com/105413.html

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

hook_t hook;
for (;;) {
    process_hook (&hook, &var1, 0);
    process_wait();
    process_unhook (&hook);
    printf ("var1 changed, now waiting for var2\n");

    process_hook (&hook, &var2, 0);
    process_wait();
    process_unhook (&hook);
    printf ("var2 changed, now waiting for var1\n");
}

[spamsink.livejournal.com]

Приведенный по ссылке хак со стеком мне кажется грязноватым. longjmp не предназначен для прыжков вниз по стеку вызовов.

[vak]

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

[spamsink.livejournal.com]

Т.е. можно, однажды сделав makecontext с отдельным стеком, потом прыгать с помощью longjmp? Думаешь, будет существенно быстрее, раз без системных вызовов?

[vak]

Надо подумать. Я когда-то уже делал реализацию сопроцессов через longjmp, но исходники не сохранились.

[vak]

Добавил макросы для ожидания типа "@(posedge var)":
process_wait1 (&var, POSEDGE);

А также для двух и трех переменных:
process_wait2 (&var1, POSEDGE, &var2, NEGEDGE);
process_wait3 (&var1, 0, &var2, 0, &var3, 0);

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

[spamsink.livejournal.com]

Бэсмовский АУ надо так смоделировать.

[panchul.livejournal.com]

Никакие контексты и лонгджампы не нужны, если вместо

void одна_функция_для_процесса () {
process_sensitive (&a, 0);
process_sensitive (&b, 0);
for (;;) {
process_wait();
signal_set (&с, f (a, b));
}
}

сделать

void функция_инициализации_для_процесса () {
process_sensitive (&a, функция_эвалюации_для_процесса);
process_sensitive (&b, функция_эвалюации_для_процесса);
}

void функция_эвалюации_для_процесса () {
signal_set (&c, f (a, b));
}

Вообще переключение контекстов - это ртосная ментальная модель.

[spamsink.livejournal.com]

Так будет неудобно implicit state machines писать.

[panchul.livejournal.com]

А почему ты с Вакуленко считаете, что генератор случайных netlist-ов вообще является репрезентативным примером RTL кода? Кроме этого:

1. В VCS (насколько я помню по работе в VCS team в 2002 году) есть куча оптимизаций для уплощения и удаления лишних ивентов. Например

assign a = b + c;
assign d = e + f;
assign g = a + d;

при отсутствии других ссылок на a и d уплощается в одно выражение которое не требует ивентов.

2. В VCS все данные для многобитных сигналов хранятся в упакованном виде - например 32 битный вектор типа bit хранится просто как сишный, а 32-битный вектор типа reg - как два числа.

3. VCS оптимизирован для больших дизайнов и имеет большой стартап. Benchmark длительностью полсекунды является бессмысленной.


Вообще в VCS насколько я смутно помню никаких longjump-ов и swapcontext-ов не было, а сгенерированный код разбивался на простые функции, представляющие из себя линейные участки кода.

[spamsink.livejournal.com]

Мы так не считаем, мы просто сравниваем яблоки с яблоками.

1. Поэтому и написано не assign, а always @* c неблокирующим присваиванием, чтобы приходилось очереди событий строить.

2. В смысле, что будь это однобитные переменные, VCS был бы еще быстрее? Пожалуй.

3. Да, конечно. Будь бенчмарк подлиннее, VCS был бы еще быстрее.

Соревноваться с VCS в производительности с надеждой выиграть смысла нет. Есть смысл получить очень короткий код, позволяющий писать на Си как на верилоге с производительностью того же порядка.

[panchul.livejournal.com]

*** Есть смысл получить очень короткий код, позволяющий писать на Си как на верилоге с производительностью того же порядка. ***

Мне нужно показать тебе последнюю инкарнацию CycleC в 2001 году. Ты бы заценил. Как нибудь устроим поход в лес и ты увидишь.

[vak]

Ты закопал инкарнацию в лесу? Обалдеть. :)

[spamsink.livejournal.com]

Ты ramlamyammambam-у ее покажи.

[vak]

Переписал на longjmp. Теперь сишный вариант почти в два раза быстрее синопсиса: 4.34 сек супротив 7.18 сек. Вместо swapcontext() используется такая конструкция:

    if (! _setjmp (old_context))
        longjmp(new_context, 1);

Пришлось задействовать свою упрощенную реализацию setjmp/longjmp и добавить флаг -U_FORTIFY_SOURCE, чтобы избавиться от всяких внутренних проверок стека в libc.

[spamsink.livejournal.com]

Красиво, но с отдельным стеком в 4 кб для каждого несчастного always блока кроме как для игрушечных дизайнов это неприменимо, потому что в реальных дизайнах этих always блоков миллионы, и это не преувеличение.

[vak]

Это понятно. Что ж, у каждого метода свои ограничения. Я пытаюсь прикинуть механической системы с цифровым управлением, и верилог тут не смотрится никак. СистемСи штука исключительно тяжеловесная и муторная, как трактором орехи колоть.

[vak]

Вместо setjmp/longjmp сделал ассемблерную вставку. Теперь летает ровно в два раза быстрее синопсиса. Но выглядит ужасно:

    asm (
        "mov %%esp, 0(%1) \n"       /* Save ESP to context[0] */
        "call 1f \n"
     "1: pop %%ebx \n"              /* Compute address of label 1 */
        "lea 2f-1b(%%ebx), %%ebx \n"
        "mov %%ebx, 4(%1) \n"       /* Save address of label 2 to context[1] */
        "mov 0(%0), %%esp \n"       /* Restore ESP from context[0] */
        "mov 4(%0), %%ecx \n"       /* Get address from context[1] */
        "jmp *%%ecx \n "            /* Jump to address */
     "2: "
        : : "r" (process_current->context), "r" (old->context)
        : "bx", "si", "di", "bp");

[spamsink.livejournal.com]

А на PDP-11 это делалось одной командой JSR PC, @(SP)+

[vak]

На самом деле, не так. Должно быть что-то вроде:

        mov     r5,(%0)+
        mov     sp,(%0)+
        mov     $1f,(%0) 
        mov     (%1)+,r5
        mov     (%1)+,sp
        jmp     (%1)
1:

[spamsink.livejournal.com]

А если сделать omit-frame-pointer?