Самодельный процессор nedoRISC-1

[Shaos]

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

r0 - всегда 0
r1 - глобальный регистр (никогда не сдвигается)
r2 - глобальный регистр (никогда не сдвигается)
r3 - глобальный регистр (никогда не сдвигается)
r4 - глобальный регистр (никогда не сдвигается)
r5 - исчезнет после ret или превратится в r10 после call
r6 - исчезнет после ret или превратится в r11 после call
r7 - исчезнет после ret или превратится в r12 после call
r8 - исчезнет после ret или превратится в r13 после call
r9 - исчезнет после ret как и после call (вызов подпрограммы не должен разрушать флаги)
r10 - превратится в r5 после ret или сохранится после call
r11 - превратится в r6 после ret или сохранится после call
r12 - превратится в r7 после ret или сохранится после call
r13 - превратится в r8 после ret или сохранится после call
r14 - превратится в r9 после ret или сохранится после call (флаги)
r15 - содержит младшие 16 битов текущего PC (старшие 4 скрыты)

При вызове подпрограммы регистры r5-r8 встают на место r10-r13 (при этом старые r10-r14 сохраняются вместе с адресом возврата), а на место r5-r9 встаёт следующее окно. При очередном вызове подпрограммы всё также сдвинется вниз, а при возврате - вверх. Как видно вызывающая программа может проверить флаги подпрограммы в регистре r9, в то же время получив свои сохранённые флаги в r14.

Я тут с коллегой по работе (тоже программист) недавно обсуждал (ну как недавно - пару лет назад ;~) его гипотетический 64-битный процессор и он предложил одну интересную штуку - сдвигать окно регистров не на заранее определённое кол-во регистров, а на столько, сколько нужно вызванной подпрограмме (возвращая окно назад по ret) - при этом получаем экономию регистров и если физические регистры закончились, то всегда можно вызвать софтовый трап, который будет обрабатывать эту исключительную ситуацию, к примеру сбрасывая старые регистры во внешнюю память...

P.S. Как оказалось это похоже на Amd 29000:

The AMD 29000 improved the design by allowing the windows to be of variable size, which helps utilization in the common case where fewer than eight registers are needed for a call. It also separated the registers into a global set of 64, and an additional 128 for the windows.

https://web.archive.org/web/20070927060927/http://www.amd.com/epd/29k/29kprog/29kprog.pdf

P.P.S. Правда у AMD 29000 процесс вызова подпрограммы и возврата из неё выглядит несколько тяжеловато:
http://people.cs.clemson.edu/~mark/subroutines/amd29k.html
Коллега же в своём 64-битном проце просто при входе в подпрограмму предполагал вызывать спецоперацию, которая сдвигает окно на N, а при возврате из подпрограммы возвращает обратно (причём не обязательно на то же самое количество регистров)...

P.P.P.S. Itanium аналогичное регистровое окно переменного размера имеет
http://people.cs.clemson.edu/~mark/subroutines/itanium.html

[Shaos]

Процесс вызова подпрограммы может выглядеть примерно так:
r15 - младшие 16 битов PC (старшие 4 бита скрыты)
alloc 3 (похоже что надо уже перед вызовом подпрограммы сказать системе на сколько двигать окно)
call ADDR (адрес 20-битный)
(далее регистровое окно двигается вниз уводя за кадр r15 с PC, r14 с флагами и старшими битами PC, плюс ещё один регистр r13)
(r12 встаёт на место r15 и содержит новый адрес PC)
(r11 стирается и встаёт на место r14 копируя содержимое старого r14, чтобы флаги сохранились)
(r10 и выше могут быть использованы как регистры аргументов - в новой нумерации это будет r13 и выше)
(подпрограмма что-то делает с аргументами и пишет ответ назад - в теже r13 и выше)
ret (тут надо как-то помнить на сколько мы двигали окно, чтобы вернуть его назад - возможно в том же регистре флагов r14)
(после возврата результат работы функции будет в регистре r10)

P.S. Предположим, что младший байт регистра r14 будет иметь в себе два 3-битных поля, которые задают количество используемых текущей подпрограммой (младшие 3 бита) и вызвавшей подпрограммой (следующие 3 бита) регистров - причём при вызове подпрограммы и копировании регистра r14 в новый регистр эти биты будут сдвигаться влево и далее с помощью спецоперации (которую ещё надо завести) младшие три бита будут устанавливаться в соответствующее значение (для имитации команды alloc).

P.P.S. Если значение этих 3 битов 000, то это будет означать, что подпрограмма не использует локальные переменные и при вызове подпрограммы будут сдвинуты только регистры r14 и r15, а 111 будет означать использование 7 локальных переменных, т.е. при вызове подпрограммы окно будет сдвинуто на 7+2=9 регистров (при этом регистр r6 получит новый PC и превратится в r15, а r5 станет новым регистром флагов r14). Если при CALL окажется, что окно сдвинуть нельзя по причине закончившегося файла регистров, то будет вызван трап SPILL, который сольёт лишнее во внешнюю память, а при RET вызовется трап FILL, который вернёт слитое обратно (флаг переполнения стека, который будет сигнализировать о необходимости этого, есть в r14).

[Shaos]

Итак, регистр флагов r14 (carry и borrow пришлось объединить):

bit 15: S - sign (результат оказался отрицательным);
bit 14: Z - zero (результат оказался нулевым);
bit 13: V - overflow (было переполнение при сложении или вычитании чисел со знаком);
bit 12: C - carry/borrow (был перенос при сложении или заимствование при вычитании);
bit 11: H - half carry (был перенос между байтами при сложении или сдвиге);
bit 10: O - stack overflow (было переполнение стека регистров);
bit 9-6: PCH - higher nibble of PC (старшие 4 бита полного адреса);
bit 5-3: PAR - parent registers (количество используемых родителем регистров, которые были сохранены);
bit 2-0: CUR - current registers (количество используемых подпрограммой регистров, требующих сохранения).

При вызове подпрограммы старый r14 копируется в новый r14 за исключением того, что новый PAR становится равным старому CUR, а новый CUR становится равным нулю, ну и в новый PCH записываются старшие 4 бита вызванного адреса...

P.S. Наверное при уходе старого r14 в тень (в момент вызова CALL) всё-таки надо обновлять его PCH, чтобы можно было вернуть управление по полному адресу...

P.P.S. Изменение PCH программно ничего не меняет, пока не будет программно изменён r15 - в этом случае произойдёт передача управления по новому адресу (кроме того PCH может использоваться для адресации памяти данных при SAVE и LOAD).

[Shaos]

Копирования с перестановками должны как минимум разрешать менять местами байты любого регистра - пока предполагаю что за кодом операции 0111 будет идти 4 бита кода регистра куда надо записать результат, потом два раза по 4 - регистры аргументы, а потом у нас остаётся ещё 8 бит в которые и надо затолкать код пермутации (либо это будет два 4-битных кода для старшего байта и для младшего байта - точно также как и для арифметических и логических операций).

Видимо иначе надо это дело реализовать:
- код операции 0111
- код целевого регистра RRRR
- количество подменяемых битов NNNN
- смещение OOOO (может использоваться как дополнительне 4 бита числа для вставки)
- восьмибитное число для вставки (младшая часть числа для вставки если N>=8)

В этом случае команда "alloc 3" (использование трёх регистров текущей подпрограммой) будет выглядеть так:

0111 1110 0011 0000 0000 0011

Что значит скопировать число 3 в три бита регистра r14 со смещением 0, оставив остальное нетронутым...

[Shaos]

Гарвардская архитектура в нашем случае может быть "модифицированной" Гарвардской, т.е. память данных и кода может быть раздельной только на уровне кешей проца, а внешняя память очень даже может быть общей (и даже с побайтовой адресацией), общение с которой (с вычислением нужных адресов), может осуществляться программно при вызове трапа по пролетанию кеша (обработчики трапов могут сидеть внутри проца). Размер кешей для начала можно установить скажем в 1К (2048 байт для данных и 3072 байта для кода) плюс 1К несбрасываемого кода обработчика трапов - супервизора (тоже 3072 байта)...

P.S. И кстати внешняя память для начала даже может быть медленной памятью с последовательным доступом (SPI)

[Shaos]

Возможный список трапов на уровне супервизора:

0x00000: START - сюда передаётся управление после ребута;
0x00001: UNKNO - трап неизвестного кода операции (1111);
0x00002: CMISS - трап пролетания кода мимо кеша;
0x00003: DMISS - трап пролетания данных мимо кеша;
0x00004: SPILL - трап переполнения файла регистров;
0x00005: FILL - трап обратного заполнения файла регистров;
0x00006: INTR - трап прерывания таймера;
0x00007: DEBUG - трап отладки.

[Shaos]

Итак, регистр флагов r14 (carry и borrow пришлось объединить):

bit 15: S - sign (результат оказался отрицательным);
bit 14: Z - zero (результат оказался нулевым);
bit 13: V - overflow (было переполнение при сложении или вычитании чисел со знаком);
bit 12: C - carry/borrow (был перенос при сложении или заимствование при вычитании);
bit 11: H - half carry (был перенос между байтами при сложении или сдвиге);
bit 10: O - stack overflow (было переполнение стека регистров);
bit 9-6: PCH - higher nibble of PC (старшие 4 бита полного адреса);
bit 5-3: PAR - parent registers (количество используемых родителем регистров, которые были сохранены);
bit 2-0: CUR - current registers (количество используемых подпрограммой регистров, требующих сохранения).

При вызове подпрограммы старый r14 копируется в новый r14 за исключением того, что новый PAR становится равным старому CUR, а новый CUR становится равным нулю, ну и в новый PCH записываются старшие 4 бита вызванного адреса...

P.S. Наверное при уходе старого r14 в тень (в момент вызова CALL) всё-таки надо обновлять его PCH, чтобы можно было вернуть управление по полному адресу...

P.P.S. Изменение PCH программно ничего не меняет, пока не будет программно изменён r15 - в этом случае произойдёт передача управления по новому адресу (кроме того PCH может использоваться для адресации памяти данных при SAVE и LOAD).

А теперь про режим супервизора - любой переход или вызов подпрограммы в области младших 1K адресов переведёт процессор в режим супервизора (как и трап) в котором будут свои собственные r1-r4 никак не пересекающиеся с юзерскими r1-r4, свой 10-битный PC (который НЕ отображается на r15) и свой регистр флагов r14, в котором вместо битов PAR будут биты доступа в спецобласти:

Code: Select all

000 - access to data cache (default)
001 - access to full register file
010 - access to higher word of code cache
011 - access to lower word of code cache
100 - access to special registers (?)
101 - access to external I/O (???)
110 - access to external 8-bit memory (?)
111 - access to external 16-bit memory (?)

Это для того, чтобы супервизор сам программно заполнял кэши

Кэши будут по 2К-слов (16-битных) для данных и 2К-слов (24-битных) для кода - первые 1K предназначены для супервизора (никогда не сбрасываются), а вторые 1К могут быть побиты на блоки:

Code: Select all

0: 1 chunk 1024 words (AAAAAAAAAAXXXXXXXXXX) - 10 bits to check
1: 2 chunks 512 words (AAAAAAAAAAAXXXXXXXXX) - 11 bits to check
2: 4 chunks 256 words (AAAAAAAAAAAAXXXXXXXX) - 12 bits to check
3: 8 chunks 128 words (AAAAAAAAAAAAAXXXXXXX) - 13 bits to check
4: 16 chunks 64 words (AAAAAAAAAAAAAAXXXXXX) - 14 bits to check

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

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

[Shaos]

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

И больше одной коры тоже можно заставить работать с одной и той же внешней памятью

[Shaos]

Первую версию можно сделать 1-core sequential (no pipeline) и даже вообще с 8-битным ALU - т.е. операции 0000 (OP) будут делаться последовательно с половинками 16-битного слова - сначала с младшим байтом потом со старшим, однако при копировании вправо сначала должен обработаться старший байт, а только потом - младший (плюс ещё переставил немного AND и OR, чтобы буква A стала AND-ом):

Code: Select all

0000 (0) - MOV1 (low byte then high byte of 1st arg);
0001 (1) - MOV2 (low byte then high byte of 2nd arg);
0010 (2) - INV1 (low byte then high byte of 1st arg);
0011 (3) - INV2 (low byte then high byte of 2nd arg);
0100 (4) - RRC1 (C -> high byte -> H -> low byte -> C of 1st arg);
0101 (5) - RRC2 (C -> high byte -> H -> low byte -> C of 2nd arg);
0110 (6) - RLC1 (H <- low byte <- C then C <- high byte <- H of 1st arg);
0111 (7) - RLC2 (H <- low byte <- C then C <- high byte <- H of 2nd arg);
1000 (8) - NAND (low byte then high byte);
1001 (9) - XOR (low byte then high byte);
1010 (A) - AND (low byte then high byte);
1011 (B) - OR (low byte then high byte);
1100 (C) - ADI (H <- low byte then C <- high byte <- H);
1101 (D) - SBI (H <- low byte then C <- high byte <- H);
1110 (E) - ADC (H <- low byte <- C then C <- high byte <- H);
1111 (F) - SBC (H <- low byte <- C then C <- high byte <- H).

но если сдвиг вправо будет совмещён с другой операцией, то можно вернуть нормальный порядок - например:
- RRC1 для старшего и RLC1 для младшего сделают сначала H <- low byte <- C и потом C -> hight byte -> H (т.е. флаг H перепишется 2 раза);
- ADI для старшего и RRC2 для младшего сделают сначала H -> low byte -> C и потом C <- high byte <- H (т.е. флаг C перепишется 2 раза).
Причём во втором случае к старшему байту будет прибавляться только полуперенос H, т.к. 4-битное число должно было прибавиться только к младшему...

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

P.P.S. Pipelined версия с 16-битным ALU может иметь быстродействие до 1 операции с 16-битными данными на такт и до 2 операций с 8-битными данными на такт...

[Shaos]

Стал заполнять вики на тему недориска:

http://www.nedopc.org/nedopc/1

[Shaos]

Кэши будут по 2К-слов (16-битных) для данных и 2К-слов (24-битных) для кода - первые 1K предназначены для супервизора (никогда не сбрасываются), а вторые 1К могут быть побиты на блоки:

Code: Select all

0: 1 chunk 1024 words (AAAAAAAAAAXXXXXXXXXX) - 10 bits to check
1: 2 chunks 512 words (AAAAAAAAAAAXXXXXXXXX) - 11 bits to check
2: 4 chunks 256 words (AAAAAAAAAAAAXXXXXXXX) - 12 bits to check
3: 8 chunks 128 words (AAAAAAAAAAAAAXXXXXXX) - 13 bits to check
4: 16 chunks 64 words (AAAAAAAAAAAAAAXXXXXX) - 14 bits to check

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

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

А теперь о том, как собственно работать, если имеем более одного проца и у каждого есть свой кеш - тут встаёт в полный рост проблема когерентности кешей, когда процы полезут в одну и туже память (скопировав её в свои кеши) и один перезапишет свой кеш, а второй об этом не узнает. Можно конечно полную когерентность сделать как у больших дядей - это когда кеши знают что у остальных закешировано и если произошла запись в такую расшаренную память, то надо сбрасывать всех остальных. А можно сделать контролируемой только скажем одну строку кеша в 64 байта (а то может и вообще только 16 байт, причём только в памяти супервизора) - все же остальные доступы в общую память будут программно контролироваться через глобальные семафоры, хранимые в этой строке кеша - вобщем как-то так...

P.S. Либо по аналогии с nedoPC-580 сделать доступ в эту область глобальных семафоров (хоть на запись, хоть на чтение) лишь для одного проца - например путём запроса доступа через какой-то сигнал (таким сигналом может стать к примеру флаг O из r14, который в режиме супервизора можно расшифровать как Obey), при этом все остальные процы аппаратно встают, пока первый проц не сделает всё что ему надо (включая запись во все остальные супервизорские кеши) и не отпустит этот сигнал...

P.P.S. Короче если супервизор пишет 1 во флаг O, то все остальные процы встают и запись в первые 1K памяти производится в кеши ВСЕХ процов (а вот чтение только из своего) - тем самым мы можем реализовать сколь угодно сложные механизмы синхронизации - далее при записи 0 во флаг O система возвращается в нормальное состояние (если два или более проца одновременно запросят Obey, то доступ получит к примеру проц с меньшим порядковым номером либо случайно выбранный проц из просящих).

[Shaos]

Либо вместо реюзанья флага O надо задействовать те супервизорские 3 бита режима доступа к данным:

Code: Select all

000 - access to data cache (default)
001 - access to full register file
010 - access to higher word of code cache
011 - access to lower word of code cache
100 - access to ALL data caches (stop other cores)
101 - access to special registers and external I/O (stop cores that go to 1xx mode)
110 - access to external static 8-bit memory (stop cores that go to 1xx mode)
111 - access to external dynamic 16-bit memory (stop cores that go to 1xx mode)

Как видим если старший бит равен 1, то все остальные процы останавливаются аппаратно и ждут пока режим не переключится в первые 4 локальные опции (старший бит равен 0)...

P.S. На самом деле останавливать другие процы где бы они не находились надо только в режиме 100, а вот для режимов 101-111 надо останавливать только те процы, которые лезут в режимы с 1 в старшем бите...

[Shaos]

Плюс к этому надо завести функцию сброса кеша по диапазону адресов типа http://stackoverflow.com/questions/22701352/flush-cpu-cache-for-a-region-of-address-space чтобы проц после того как поработал с общей памятью сбросил бы свой кеш в общую память, чтобы другие процы апдейтнули свои версии...

[Shaos]

Первую версию можно сделать 1-core sequential (no pipeline) и даже вообще с 8-битным ALU - т.е. операции 0000 (OP) будут делаться последовательно с половинками 16-битного слова - сначала с младшим байтом потом со старшим, однако при копировании вправо сначала должен обработаться старший байт, а только потом - младший (плюс ещё переставил немного AND и OR, чтобы буква A стала AND-ом):

Code: Select all

0000 (0) - MOV1 (low byte then high byte of 1st arg);
0001 (1) - MOV2 (low byte then high byte of 2nd arg);
0010 (2) - INV1 (low byte then high byte of 1st arg);
0011 (3) - INV2 (low byte then high byte of 2nd arg);
0100 (4) - RRC1 (C -> high byte -> H -> low byte -> C of 1st arg);
0101 (5) - RRC2 (C -> high byte -> H -> low byte -> C of 2nd arg);
0110 (6) - RLC1 (H <- low byte <- C then C <- high byte <- H of 1st arg);
0111 (7) - RLC2 (H <- low byte <- C then C <- high byte <- H of 2nd arg);
1000 (8) - NAND (low byte then high byte);
1001 (9) - XOR (low byte then high byte);
1010 (A) - AND (low byte then high byte);
1011 (B) - OR (low byte then high byte);
1100 (C) - ADI (H <- low byte then C <- high byte <- H);
1101 (D) - SBI (H <- low byte then C <- high byte <- H);
1110 (E) - ADC (H <- low byte <- C then C <- high byte <- H);
1111 (F) - SBC (H <- low byte <- C then C <- high byte <- H).

но если сдвиг вправо будет совмещён с другой операцией, то можно вернуть нормальный порядок - например:
- RRC1 для старшего и RLC1 для младшего сделают сначала H <- low byte <- C и потом C -> hight byte -> H (т.е. флаг H перепишется 2 раза);
- ADI для старшего и RRC2 для младшего сделают сначала H -> low byte -> C и потом C <- high byte <- H (т.е. флаг C перепишется 2 раза).
Причём во втором случае к старшему байту будет прибавляться только полуперенос H, т.к. 4-битное число должно было прибавиться только к младшему...

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

P.P.S. Pipelined версия с 16-битным ALU может иметь быстродействие до 1 операции с 16-битными данными на такт и до 2 операций с 8-битными данными на такт...

Думаю таки надо сразу городить пипелайную архитектуру - иначе засмеют

Причём делать можно с 8-битным АЛУ, точнее с двумя (эдакий недопентиум), чтобы они в разных стадиях пипелайна работали - один с младшей половинкой, второй со старшей половинкой (или наоборот) - единственная проблема в данном решении это то, что соседние команды не смогут при этом использовать одни и теже регистры т.к. когда следующая команада использует значения каких-то регистров, предыдущая их могла ещё не поменять - либо ставить генератор "пузырей", которые будут заталкивать в пипелайн пустышку вместо очередного шага для того чтобы запись в регистр таки удалась и следующая команада заюзала уже изменённое значение....

P.S. Ориентировочно можно обойтись 4 стадиями конвеера:

Code: Select all

1) fetch instruction from instruction cache and decode;
2) execute instruction (with or without ALU1);
3) data cache access or use ALU2;
4) write back result to destination register and flags.

где третья стадия будет либо обращением к данным, либо работой со вторым АЛУ (т.к. у нас нету ни одной инструкции, где бы работа со вторым АЛУ совмещалась с обращением к памяти данных - а вот первый АЛУ для ISAVE/ILOAD очень даже пригодится, правда смещение на константу при этом будет только в пределах 256-словной страницы с перехлёстом в начало, если зашкалило).

P.P.S. Как видим мы уже получили 1 инструкцию на такт (и даже 2 в случае OP, считающего разные вещи на половинках слова)...

[Shaos]

После JUMP, CALL, RET и OP MOV R15 (?) надо запретить исполнение инструкций, которые успели залезть в конвейер - при этом штраф за переход будет составлять 3 такта - хотя в конце первой стадии пипелайна мы уже можем знать, что у нас на исполнение идёт JUMP/CALL/RET и как минимум после декода JUMP мы даже уже знаем адрес - соответственно уже можно начать засасывать следующую инструкцию с нового адреса не нарушая конвейер! А вот CALL/RET надо доделать до конца - соответственно в конвейер после них залезут 3 пустышки. Запись в R15 (который напомню является младшим словом PC) тоже легко детектируема на этапе декода и её также надо доделать до конца, однако тут можно схитрить и не генерить пустышек - пусть 2 (или 3?) следующие за OP MOV R15 инструкции исполнятся как ни в чём не бывало!!!

P.S. А ведь ещё есть LOAD R15, ILOAD R15, COPY R15, INIT R15, CLR R15 и SET R15 - видимо надо считать инструкции где меняется R15 имеющими побочные эфеекты как-то передачу управления только через 3 инструкции после...