CPU of my dream (ru)

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

Начну пожалуй со сбора требований и пожеланий.

Регистры, регистры, регистры, регистры!

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

Рассмотрим регистры общего назначения.
Если их много, человеку, компилятору и планировщику есть где разгуляться:

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

Словом, много регистров - это хорошо.

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

Многопоточное окружение - тоже не любит большие регистровые файлы. Переключение потоков требует сохранения прикладного состояния процессора. А регистры - большая часть этого состояния.

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

Регистровые окна

Вот как эту проблему решили авторы SPARC (справедливости ради стоит сказать, что это решение они позаимствовали у исследовательского процессора Berkley RISC I).
Регистровый файл из 32 регистров был поделен на 4 банка по 8 регистров в каждом. Банки назывались %o, %l, %i, %g.
При входе в процедуру выполнялась специальная инструкция SAVE, которая сбрасывала в стек восемь регистров %i0..%i8 и восемь регистров %l0..%18, затем копировала регистры %o в %i.
Перед выходом из процедуры по команде RESTORE происходило обратное преобразование: регистры %i копировались в %o, и регистры %l и %i восстанавливались из стека (обе операции не затрагивают %g-регистры, которые предназначены для хранения tls-переменных).

Что это нам дает?
Типичная процерура  использует:

• %i-регистры для хранения своих параметров
• %l-регистры для временных переменных, которые должны сохраняться при вызове других процедур,
• %o-регистры для временных переменных, которые не сохраняют свои значения при вызовах процедур, в те же o-регистры она помещает параметры для вызовов и в них же принимает результаты.

Все сохранение кадров стека берет на себя аппаратура.

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

На самом деле регистров в SPARC гораздо больше. В процессоре есть специальный индексный регистр, который указывает, какой регистр в данный момент считается регистром %o0. Команда SAVE сдвигает этот индексный регистр на 16, превращая %o-регистры в %i-регистры и убирая %l- и %i-регистры в невидимую для программы зону регистрового файла. RESTORE выполняет обратное преобразование. Типичный SPARC-процессор имеет достаточно регистров для восми уровней вложенности процедур.

Если очередная инструкция SAVE использовала все невидимые регистры, процессор генерирует cпециальный TRAP, и его обрабочик в опрационной системе должен провернуть регистровый файл и сохранить в стек самые нижние 16 регистров. Аналогично, если RESTORE не может восстановить очередной кадр стека из невидимых регистров, происходит TRAP и регистры восстанавливаются из стека операционной системой.

Решение, примененное в процессоре SPARC имеет два достоинства и массу недостатков.

Достоинства:

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

Недостатки:

• Оверхед по памяти. Даже процедура без локальных переменных и с одним параметром истратит 16 регистров в регистровом файле (и должна будет зарезервировать столько же в стеке).
• Ничего не сделано для сохранения регистров FPU.
• Многопоточность - это катастрофа. Теперь для сохранения состояния при переключении потоков приходится сохранять и восстанавливать сотни теневых регистров.

Регистровый файл переменного размера

В середине 90-х AMD производила очень интересный процессор AMD 29000. В котором было 64 глобальных регистра (которые нам не интересны) и 128 регистров для локальных данных, объединенных в кольцо. Три специальных регистра контролировали работу кольца.

• RSP - хранит номер регистра, который будет считаться lr0 (при обращении к локальному регистру процессор прибавляет по модулю 128 к его номеру  содержимое RSP).
• RFB - адрес  в памяти оследнего регистра, который был сброшен в стек. В отличие от RSP этот регистр не используется аппаратурой процессора каким-то особым образом. Это обычный глобальный регистр, для которого в конвенции вызовов предусмотрена особая роль.
• RAB - адрес в стеке, куда сбрасывался бы регистр gr0.

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

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

Подробнее про этот весьма интересный процессор можно прочитать тут: AMD29000 Family.pdf

Подход, примененный в AMD 29000 позволяет решить важную проблему SPARC-процессоров - фиксированный размер стекового кадра. В 29000 память используется экономно, обмен с ней так же минимизирован.

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

Переименование регистров

Многие современные процессоры (особенно x86) вынуждены сохранять обратную совместимость с CISC архитектурой, имеющей небольшое количество регистров и тяжелые инструкции, исполняющиеся десятки тактов. Тяжелые инструкции транслируются во внутренние простые RISC-микроинструкции, которые работают над большим регистровым файлом. При этом планировщик отслеживает время жизни значений в исходном регистре и маппит каждое его значение на отдельный внутренний регистр.
Искусственный пример:

    mov eax, x
    shl eax, 4
    mov x, eax
    mov eax, y
    and eax, 0ffh
    mov y, eax

может быть преобразовано в микроинструкции

    ld x, %0
    ld y, %1
    shl %0, 4, %0
    and %1, 0ffh, %1
    st %0, x
    st %1, y

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

Но это очень дорогой метод:

• Требуется сложный декодинг инструкций.
• Регистровый файл становится ассоциативным, с теговой адресацией.
• Планировщик должен отслеживать зависимости по данным между соседними инструкциями, фактически, по внутренней сложности он приближается к RISC-процессору.
• Работа аллокатора регистров основывается на наборе эвристик, и время исполнения инструкций становится непредсказуемым.
• Фактически процессор исполняет приложение в системе команд другого процессора в режиме эмуляции.
• В несколько раз увеличивается длина конвейера.
• Части оттранслированного кода сохраняются во внутренних кешах процессора. Что создает проблемы не только при переключении потоков, но и при обработке асинхронных прерываний.
• Все эти механизмы (транскодер инструкций, аллокатор регистров, планировщик, кеш микроинструкций, сериализатор результатов) занимают площадь кристалла и потребляют лишние ватты. Их можно было потратить на что-то полезное.

Резюме

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

• существенно меньше по объему (средняя процедура использует около 2-6 параметров, 2-8 локалов и 1-6 временных значений, поэтому 32 регистров будет достаточно.
• сброс и восстановление регистов должен выполняться аппаратными инструкциями без trap-ов.
• для FPU и SIMD - инструкций должны использоваться те же регистры общего назначения (мы их расширим, когда добавим SIMD).

Продолжение