Информатика и выч. техника \ Архитектура вычислительных систем

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

4.5.2    Функция планирования

С механизмом пересылки и аппаратной взаимной блокировкой возможно доказать аналог теоремы 4.7 вообще без гипотезы о последовательности команд.

Перед определением теоремы мы формализуем новую функцию планирования Iπ(k, T). Циклы Т при рассмотрении будут циклами CE2. Интуитивно определение говорит, что новая команда в каждом цикле CE1 вставляется в канал, и что впоследствии она просачивается по каналу вниз вместе со своими сигналами full.k. Предположим, что цикл 0 является последним циклом, в котором активен сигнал сброса.

Любые команды продвигаются самое большее на один этап за цикл, т.е., если Iπ(k,T) = i, тогда

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

CE2   =   1

ue.0   =   CE1

ue.1    =    ue.2 = ие.3 = ue.4 = 0.

Самое большее после одного цикла флаги заполненности инициализируются в

full.1 = 1,        full.2 = full.3 = full.4 = 0,

доступы по чтению к памяти данных запрещены (DMr’ = 0), и таким образом, busy = dhaz= 0.

Выполнение все еще начинается в цикле 0 при Iπ(0,0) = 0. Команды всегда выбираются в программном порядке, т.е.,

Когда завершены первые обращения к IM, регистр команд содержит

IR = IM[0].

Лемма 4.10

PROOF

Это ситуация в цикле Т = 0. Начиная со следующего цикла сигнал сброса выключен, и в тогда каждом цикле CE1 новая команда подается на этап 0. Кроме того, мы имеем

ue.0T = ue.1T = CE1Tдля всех    Т >= 1

т.е., после цикла Т = 0 этапы 0 и 1 всегда синхронизируются одновременно, а именно в каждом цикле CE1. Простая индукция по Т дает для любого i>= 1

Iπ(0, T) = i     ->     Iπ(1, T) = i-l                                                  (4.5)

ue.kT = 1     ->     ue.(k+\)T+1 = 1.

Так только команда синхронизируется на этапе 2 она проходит один этап за каждый цикл синхронизации CE2. Таким образом, команда не может быть остановлена после того, как была синхронизирована на этапе 2, т.е., это значит для k € {2,3}

Механизм останова гарантирует следующие две особенности:                                                                                         

1.Команда Ii никогда не может настигнуть предыдущую команду Ii-1 .

2. Для любого этапа k >= 1 и любого цикла Т >= 1, значение Iπ(k,T) функции планирования определено только тогда, когда флаг full.k активен в течении цикла T, full.kT = 1.

1)  Так как команды всегда выбираются по порядку (уравнение 4.3), команда Ii входит на этап 0 после команды Ii-1 . Из-за жесткой конфигурации поведения на первых двух этапах (уравнение 4.5), существует цикл Т с

Iπ(0, T) = i /\ Iπ(l, T) = i - l.

Пусть T’ >= Т – следующий цикл с активным синхроимпульсом CE1. Этапы 0 и 1 синхронизируются в конце цикла T'; по уравнению 4.4 из этого следует, что обе команды передвигаются на следующий этап:

Iπ(1,T ' + 1) = i  /\  Iπ(2, T ' + 1) = i-1.

Iπ(k, T) = i     ->     Iπ(k+ 1,Т + 1) = i.                (4.6)

Это означает, что команды перемещаются в жесткой конфигурации через этапы 0 и 1. Для T>= 1 и 1 <= k <= 3 это означает, что

Команда Ii-1 теперь выполняется на полной скорости (уравнение 4.6), т.е., это значит, что для a€ {1,2}

Iπ(2 + a,T ' + 1+ a) = i - 1.

Команда Ii может проходить самое большее один этап за цикл (уравнение 4.4), и до цикла Т + 1 + aона, следовательно, не перемещается за этапом 1 + a. Таким образом, Ii не может достигнуть Ii-1 . Это доказывает первое выражение.

Скачать файл