Табло - это централизованный метод, впервые использованный в компьютере CDC 6600 , для динамического планирования инструкций, чтобы они могли выполняться не по порядку, когда нет конфликтов и доступно оборудование. [1]
На табло зависимости данных каждой инструкции регистрируются, отслеживаются и строго соблюдаются в любое время. Инструкции выдаются только тогда, когда табло определяет, что нет противоречий с ранее выданными («в полете») инструкциями. Если инструкция остановлена из-за того, что ее выпускать небезопасно (или недостаточно ресурсов), табло отслеживает поток выполнения инструкций до тех пор, пока не будут устранены все зависимости, прежде чем будет выпущена остановленная инструкция. По сути: чтение продолжается при отсутствии опасностей записи, а запись продолжается при отсутствии опасностей чтения.
Табло по сути является аппаратной реализацией того же базового алгоритма, который используется в языках потока данных , создающего направленный ациклический график , в котором та же логика применяется во время выполнения языка программирования .
Этапы
Инструкции декодируются по порядку и проходят следующие четыре этапа.
- Вопрос : Система проверяет , какие регистры будут считаны и записаны с помощью этой инструкции и где конфликты WAR и RAW и WAW обнаружены. Опасности RAW и WAR регистрируются с помощью матрицы зависимостей (построенной из защелок SR NOR в исходной конструкции 6600), поскольку это потребуется на следующих этапах. Одновременно запись записывается во вторую матрицу, которая записывает порядок инструкций как направленный ациклический граф . Чтобы избежать зависимостей вывода ( WAW - запись после записи), инструкция останавливается до тех пор, пока инструкции, намеревающиеся записать в тот же регистр, не будут завершены. Команда также приостанавливается, когда требуемые функциональные блоки в настоящее время заняты. * Никакая инструкция не выдается, если она не отслеживается на 100% от начала до конца *.
- Чтение операндов : после того, как инструкция была выдана и правильно назначена требуемому аппаратному модулю (названному вычислительным блоком в книге Торнтона), блок ожидает, пока все операнды не станут доступными. Только чтение продолжается, когда зависимости записи ( RAW - чтение после записи) были отброшены со всех других модулей. Чтобы избежать конфликта портов регистрового файла, средство выбора приоритета выбирает одну вычислительную единицу (в случае, когда несколько единиц не подвержены опасности).
- Выполнение : после получения всех операндов вычислительный блок начинает свое выполнение. После того, как результат готов, на табло выводится уведомление.
- Результат записи : на этом этапе результат готов, но еще не записан в регистр назначения. Запись не может продолжаться до тех пор, пока блок не будет очищен от всех опасностей ( WAR - запись после чтения). Единственные дополнительные задержки здесь основаны на доступности портов регистрового файла: в 6600 было использовано средство выбора приоритета для выбора одного результата на порт записи. После написания блок помечается как более не занятый, и все опасности и состояния отбрасываются. Обратите внимание, что только в расширенных (расширенных, точных) табло с функцией «Тень» фаза результата записи будет предотвращена (отложена). В оригинальном 6600 такой возможности не было.
Важно отметить , что выше Считывает только проследовать в отсутствии в записи опасности, и что запись производится в отсутствие по Читать опасности. Это логично, но противоречит ожиданиям. В частности, обратите внимание, что записи должны ждать записи после чтения, чтобы дать другим модулям возможность прочитать текущее значение в регистре, прежде чем перезаписывать его новым. Следовательно, при записи необходимо дождаться отсутствия опасностей WaR.
Структура данных
Для контроля выполнения инструкций на табло поддерживаются три таблицы состояния:
- Состояние инструкции : указывает для каждой выполняемой инструкции, на каком из четырех этапов она находится.
- Состояние функционального блока : указывает состояние каждого функционального блока. Каждый функциональный блок поддерживает 9 полей в таблице:
- Занят: указывает, используется ли устройство или нет.
- Операция: операция, выполняемая в отряде (например, MUL, DIV или MOD).
- F i : регистр назначения
- F j , F k : номера регистров источника
- Q j , Q k : Функциональные блоки, которые будут производить исходные регистры F j , F k.
- R j , R k : Флаги, указывающие, когда F j , F k готовы и еще не прочитаны.
- Состояние регистра : указывает для каждого регистра, какой функциональный блок будет записывать в него результаты.
Оригинальный алгоритм 6600
Подробный алгоритм управления табло, изложенный в исходном патенте, описан ниже:
проблема с функцией ( op , dst , src1 , src2 ) подождите, пока (! Занят [FU] И! Результат [ dst ]); // FU может быть любым функциональным блоком, который может выполнять операцию op Занят [FU] ← Да; Op [FU] ← op ; F i [FU] ← dst ; F j [FU] ← src1 ; F k [FU] ← src2 ; Q j [FU] ← Результат [ src1 ]; Q k [FU] ← Результат [ src2 ]; R j [FU] ← Q j [FU] == 0; R k [FU] ← Q k [FU] == 0; Результат [ dst ] ← FU;
функция read_operands ( FU ) подождите, пока (R j [ FU ] AND R k [ FU ]); R j [ FU ] ← Нет; R k [ FU ] ← Нет;
выполнение функции ( FU ) // Выполняем все, что должен делать FU
функция write_back ( FU ) подождите, пока (∀f {(F j [f] ≠ F i [ FU ] OR R j [f] = Нет) AND (F k [f] ≠ F i [ FU ] OR R k [f] = Нет)} ) foreach f делать если Q j [f] = FU, то R j [f] ← Да; если Q k [f] = FU, то R k [f] ← Да; Результат [F i [ FU ]] ← 0; // 0 означает, что никакой FU не генерирует результат регистра RegFile [F i [ FU ]] ← вычисленное значение ; Занято [ FU ] ← Нет;
Замечания
Книга Торнтона предшествует современной компьютерной терминологии.
- Функциональные единицы (конвейеры) назывались «вычислительными единицами».
- "Конфликт первого порядка" охватил оба киоска из-за занятости всех подразделений, а также конфликт WAW . [2]
- «Конфликт второго порядка» был термином, используемым для конфликта RAW [3]
- "Конфликт третьего порядка" касался ВОЕННОГО конфликта [4]
Зависание происходило только на этапе выдачи, когда были обнаружены конфликты «первого порядка». Некоторые другие методы, такие как алгоритм Томасуло, дополнительно разрешают зависимости WAW с переименованием регистров . В оригинальном CDC 6600, вероятно, не было отслеживания опасностей WAW просто потому, что его разработчики должны были доставить продукт, а затем перешли к 7600: вместо этого остановка была наиболее целесообразным вариантом. Нет никаких технических причин, по которым переименование реестра не следует добавлять в табло.
Люк Лейтон провел анализ обоих алгоритмов и описал процесс преобразования, который показывает эквивалентность алгоритма Томасуло и алгоритма 6600 Scoreboard. [5] Разрешение опасностей WAW действительно отсутствует в исходном алгоритме: 6600 остановится при первом возникновении опасности записи. [6]
- Торнтон, Джеймс (1970). Дизайн компьютера: данные управления 6600 (PDF) . ISBN 9780673059536.
Смотрите также
Рекомендации
- ^ Торнтон, Джеймс Э. (1965). «Параллельная работа в управляющих данных 6600». Труды осенней совместной компьютерной конференции 27–29 октября 1964 г., часть II: высокоскоростные компьютерные системы . AFIPS '64. Сан-Франциско, Калифорния: ACM. С. 33–40. DOI : 10.1145 / 1464039.1464045 .
- ↑ Торнтон (1970 , стр.125)
- ↑ Торнтон (1970 , стр. 126)
- Перейти ↑ Thornton 1970 , p. 127
- ^ Преобразование Томасуло в табло
- ^ Дизайн компьютера, Джеймс Торнтон ISBN 9780673059536
- Гленфорд Майерс , «Регистрация результатов на микропроцессорной микросхеме», Патент США 4891753
Внешние ссылки
- Динамическое планирование - Табло
- Компьютерная архитектура: количественный подход , Джон Л. Хеннесси и Дэвид А. Паттерсон
- EECS 252 Компьютерная архитектура для дипломированных специалистов Lec XX - ТЕМА , Электротехника и компьютерные науки, Беркли, Калифорнийский университет.
- Пример табло