|
Deadlock Free Execution (Выполнение, свободное от тупиков) Наконец, мы должны доказать, что механизм останова не может производить тупики. Пусть оба синхроимпульса активны в течении цикла Т — 1, т.е., CEIT-1 = CE2T-2 = 1, пусть команды I, I' и I'' находятся на этапах 1 - 3 в течении цикла T. I', I'', возможно являются фиктивными командами. Кроме того, пусть CE1T = 0. Таким образом, должен быть установлен флаг опасности (dhazT = 1) и одна из команд I' и I'' должна быть командой загрузки, которая обновляет исходный регистр команды I. 1. Предположим, что команда I' на этапе 2 является такой командой загрузки, тогда v.2T = v.3T+1 = 0 и v.4T+2 = l. Команда I' производит опасности данных в течении циклов Т и Т + 1. В течении этих циклов только фиктивные команды, которые не могут активировать сигнал dhazвходят на низшие этапы, и поэтому dhazT+2 = 0 и CE1T+2 = 1. 2. Предположим, что команда I’' на этапе 3 является последней командой загрузки, которая обновляет исходный регистр команды I, тогда v.2T = v.3T+1 = 1, v.3T = 0 и v.4T+1 = 1. Команда I'' производит опасности данных в течении цикла Tи фиктивная команда вводится на этапе 2 в конце цикла. В следующем цикле CE2 не существует опасностей данных и весь конвейер засинхронизирован: dhazT+1 = 0 и CE1T+l = 1. Таким образом, синхросигнал CE1 отключен (CE1 = 0) в течении самое большее двух последовательных циклов CE2, и поэтому все команды достигают всех этапов конвейера. Обратите внимание, что ни один из вышеупомянутых аргументов не зависит от того факта, что конвейерная машина моделирует подготовленную последовательную машину. |
|
QED |
2) Второе выражение может быть доказано простой индукцией по T; мы оставляем подробности на упражнение (смотри упражнение 4.5).
4.5.3 Теорема моделирования
Теперь мы можем показать теорему моделирования для произвольной последовательности команд:
|
Теорема 4.11 |
Для всех i, k, T, T ' таких, что Iπ(k,T) = Iσ(k,T ') = i и ue.kT = 1, выполняются следующие два требования:
1. для всех сигналов S на этапе k, которые являются входами регистра R€ out(k), обновление происходит в конце цикла Т:
|
|
2. для всех регистров и R€ out(k}, которые являются видимыми или обновленными в конце цикла T:
RπT+1 = Ri .
|
ДОКАЗАТЕЛЬСТВО |
Мы говорили выше о том, что IM[0] синхронизируется в регистр IRв конце CE2 цикла 0, и что PC проинициализирован верно. Таким образом, теорема верна для T = 0. Для шага индукции мы различаем четыре случая:
1. k = 0. Этап 0 получает входы только из этапов 0 и 1. Без сброса эти два этапа синхронизируются одновременно. Таким образом, входы этапа 0 изменяются только при активном синхроимпульсе CE1. Рассуждая о циклах CE1 вместо циклов CE2, можно повторить аргумент из теоремы 4.7.
2. k€ {2, 4}. В путях данных существуют только нисходящие грани в этап k, и команды проходят этапы со 2 по 4 на полной скорости. Поэтому рассуждения остаются неизменными.
3. k = 3. Из Iπ(3, T) = iбольше нельзя заключить, что Iπ(3, Т - 1) = i - 1. Вместо этого можно заключить
Iπ(3, t) = i -1
|
Mπt+1 = Mi-1по индукционной гипотезе = MTπ. |
для последних циклов t < Tтаких, что I(3,t) определен, т.е., таких, что не фиктивная команда была на этапе 3 в течении цикла t. Так как фиктивные команды не обновляют ячейки памяти данных M, из этого следует что
4. k = 1. Для I(1, T) = iи ue.1T = 1 мы обязательно имеем dhazT = 0. Если Ii не имеет регистра операнда GPR[r], тогда используются только нисходящие грани, и требование следует как и выше. Таким образом, пусть Ii читает регистр GPR[r] при r =/= 0. Чтение может быть для операнда Aили B. Мы рассматриваем только чтение операнда A; чтение В обрабатывается тем же самым путем с очевидными изменениями в записи.
Если команды I0 ,... Ii-1 не обновляют регистр GPR[r], из этого следует для любых k > 1, что
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
