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

Так как этапы 0 являются для обеих машин одинаковым, мы имеем

для всех внутренних сигналов Sэтапа 0 и, следовательно, требование 1. В частности, в обеих машинах IM(0) синхронизируется с регистром команд в конце цикла T= T ' = 0. Следовательно, требование 2 следует из

Таблица 4.12 Иллюстрация функции планирования I_πдля этапов k — 1 и k.

В шаге индукции мы заключаем от Т — 1 до T. Таким образом, мы должны показать требование 1 для сигналов S в цикле Tи мы требование 2 для регистров Rв цикле T + 1. Согласно рисунку 4.14, который иллюстрирует поток данных между этапами конструкции DLX_σ , есть следующие четыре случая:

1. k = 2 (выполнение) или k = 4 (обратная запись).Это простейший случай. На рисунках 4.3 и 4.14 все ребра в этап kисходят из выходных регистров

R € out(k-1)

этапа k — 1. Из функции планирования можно заключить, что

I_π(k-1,T-1)  = I_π(k,T) = I_σ(k,T ') = i.

Это показано в таблице 4.12. Пусть R - входной регистр этапа k, который является видимым или который был обновлен в конце цикла T — 1. Используя лемму 4.3 с t = 1 мы заключаем

r^t_п    =   R_iпо индукционной гипотезе  

=   R^{T '}_aпо лемме 4.3.

Следовательно, за исключением невидимых входных регистров R, которые не обновлялись после цикла T — 1, этап kмашины DLX_πимеем в цикле Tте же самые входы, что и этап kмашины DLX_a в цикле T'. Этап kодинаков в обеих машинах (это основа конструкции подготовленной машины !). По лемме 4.4 набор выходных регистров R' этапа k, которые обновляются после такта Tили T' соответственно, одинаков для обеих машин, и входные сигналы Sэтих регистров имеют одинаковые значения:

Из этого следует, что в конце этих циклов Tи T ' в R' синхронизируются одинаковые значения:

=   r'_iпо лемме 4.3.

Рисунок 4.14 Поток данных между конвейерными этапами конструкции DLX_σ

2. k = 3 (память). Входы этого этапа включают регистры из out(2) и память DM, которая принадлежит out(3). Для входных регистров R€ out (2) заключение такое же, что и выше

R^T_π = R_i = R^{T '}.

Для i > 0 заключаем из функции управления (таблица 4.12)

I_π(3, T-1) = i-1.

Мы имеем Mout(3), т.е., каждая ячейка памяти является выходным регистром этапа 3. Используя лемму 4.3 при t= k= 3 и индукционную гипотезу, мы можем заключить

Для i = 0, функция планирования подразумевает

I_π(3,T) = i  <->  T = 3.

Таблица 4.13 Иллюстрация функции планирования I_πдля этапов 0 и 1.

Согласно таблице 4.11, ячейки памяти Mне обновляются в течении циклов t€ {1,2}, потому что full[3]^t_π = 0. Так как конструкция DLX_πстартует с содержимым M¹_π = M_-1, из этого следует

В конструкции DLX_σ обновление памяти данных DM разрешается флагом full[3]. Таким образом, DM могла бы быть обновлена в течении сброса, но тогда обновление является отключенным пока I₀ не достиг этапа 3, при с full[3]^t_σ = 0 для t€ {0,1,2}. Поэтому

Теперь аргумент полностью как в первом случае.

3. k= 0 (выборка). Здесь мы должны доказать, что задержанный PC может быть отвергнут. В конвейерной конструкции PC' является входным регистром только этапа IF, тогда как в последовательной конструкции входным регистром является DPC. Оба регистра – выходные этапа s = 1.

Для i > 2 заключаем из функции управления (таблица 4.13)

I_π(1, T- l) = I_π(0,T-1) - 1 = i - 2. Индукционная гипотеза подразумевает (для T > 1)

PC_π' ^T = PC'_i-2 .

Для i= 1 (и T = 1) мы имеем конструкцию

PC'_-1 = 4 = PC' _π¹.

Используя лемму 4.3 при t = 1, мы заключаем для T > 1

PC'_П^T = PC'_i-2    =   DPC_i-1по конструкции

=   DPC^T_a'         по лемме 4.3.

Теперь аргумент полностью как в первом случае.