Детальный проект конвейерного RISC процессора (Глава 4 "Основы конвейеризации"), страница 10

Новое вычисляемое заранее управление генерирует те же управляющие сигналы, что и FSD, но машина теперь имеет очень регулярную структуру: управляющие сигналы поступающие из регистра R.k€ out (k - 1) управляют этапом kпутей данных для всех k > 1. Действительно, если мы определим R.0 и R.1 как фиктивные регистры длиной 0, то же самое потребуется для всех k. Структура путей данных и вычисляемого заранее управления машины DLXσ иллюстрируются рисунком 4.10.

Аппаратная часть, генерирующая входы регистра R.2 является автоматом Мура с 10 состояниями EX, вычисляемыми заранее управляющими сигналы и параметрами exиз таблицы 4.10. Состояние noEXслужит начальным состоянием автомата. Следующее состояние зависит только от входа IRно не от текущего состояния. Включая регистры R.3 и R.4, управляющие сигналы этапов EX - WB могут быть вычислены заранее со следующей стоимостью и временем цикла:

C_CON(moore)    =   С_pMoore(ех) + (3 + 2) * C_ff T_CON(moore)    =    T_pMoore(ex).

Сигналы Mealy, которые управляют этапом ID, генерируются автоматом Mealy с одним состоянием и параметрами idиз таблицы 4.10. Все его входы обеспечиваются регистром IR с нулевой задержкой. Согласно разделу 2.6, стоимость этого автомата и задержка сигналов Mealy может быть представлена как

C_CON (mealy)   =   C_Mealy(id) + (3 + 2) * C_ff

A_CON (mealy)    =   A_o(id).

Мы не будем утруждать себя анализом стоимости и временем цикла механизма останова.

4.2.4    Основное наблюдение

Позже мы установим правильность конвейерной машины показав, что она моделирует машину DLX_σ . Это требует индуктивного доказательства на основе такт за тактом. Мы всегда будем говорить о фиксированной но произвольной последовательности

I = I₀, I₁, ...

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

Если в течении такта сигнал busyактивен, тогда состояние машины не изменяется до конца этого цикла. Следовательно, мы перечислим только циклы в течении которых сигнал busy неактивен

T = 0,1,...

Для таких циклов Т и сигналов Rмы обозначим через R^Tзначение Rв течении цикла T; Rтакже может быть выходом регистра. Мы вводим сокращение

означающее, что команда I_i находится на этапе kмашины DLX_σв течении  цикла T. Формально это может быть определено как

•  выполнение начинается в цикле T = 0, т.е., I_σ(0,0) = 0,

•  если I_σ(k,T) = iи k < 4, тогда I_σ(k + 1, T + 1) = i,

•  если I_σ(4,T) = i, тогда I_σ(0, T + 1) = i + 1.

Для любых других комбинаций Tи kфункция планирования I_σ(k,T) не определена. Следовательно,

I_σ(k,T) = i    <->     T = 5*i + k    <->     i=[T/5]  и k = T mod 5;

и для любого цикла Т >= 0, этап kполон (full^T[k] = 1) тогда и только тогда, когда I_σ(k, T) определено. Повторимся, что мы обозначаем через R_i значение Rпосле выполнения команды I_i. Через R_-1мы обозначаем начальное значение R, т.е., значение Rпосле сброса. Основное наблюдение о работе такт за тактом машины DLXσ формулируется в следующей лемме.

Dateline Лемма. Пусть I(k, T ' ) = i ипусть R € out(t), тогда

Это проиллюстрировано на рисунке 4.11. В течении цикла T', регистры выше этапа kуже имеют новое значение R_i, тогда как регистры ниже этапа kвсе еще имеют старое значение R_i-1. Другими словами, на нисходящих стрелках рисунка 4.3 машины DLXσ, читаются значения R_i  из текущей команды, тогда как на восходящих стрелках машиной читаются значение R_i-1  из предыдущей команды.

Очень интуитивная формулировка леммы – причина, по которой на рисунке 4.3 мы перенесли файл регистров общего назначения в самый низ конвейера а не – как обычно – в середину этапа ID. Формальное доказательство использует тот факт, что

R_i-1 =R⁵ⁱ

и выполняется для T = 5i + kиндукцией по k. Мы оставляем простые подробности на упражнение 4.2.

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