Табло

Табло — это централизованный метод, впервые использованный в компьютере CDC 6600 для динамического планирования инструкций, чтобы они могли выполняться вне очереди, когда нет конфликтов и доступно оборудование. ^[1]

На табло зависимости данных каждой инструкции регистрируются, отслеживаются и постоянно строго соблюдаются. Инструкции выдаются только тогда, когда табло определяет отсутствие противоречий с ранее отданными («в полете») инструкциями. Если инструкция зависает из-за того, что ее выполнение небезопасно (или недостаточно ресурсов), табло контролирует поток выполнения инструкций до тех пор, пока все зависимости не будут разрешены, прежде чем будет выдана остановленная инструкция. По сути: чтение продолжается при отсутствии опасностей записи, а запись продолжается при отсутствии опасностей чтения.

Табло — это, по сути, аппаратная реализация того же базового алгоритма, который используется в языках потоков данных , создавая направленный ациклический график , где та же логика применяется во время выполнения языка программирования .

Этапы [ править ]

Инструкции декодируются по порядку и проходят следующие четыре этапа.

Проблема : Система проверяет, какие регистры будут считываться и записываться этой инструкцией и где конфликты WAR и RAW и WAW обнаруживаются . Опасности RAW и WAR записываются с использованием матрицы зависимостей (составленной из защелок SR NOR в исходной конструкции 6600), поскольку она понадобится на следующих этапах. Одновременно запись записывается во вторую матрицу, которая записывает порядок инструкций в виде направленного ациклического графа . Чтобы избежать зависимостей вывода ( WAW – запись после записи), инструкция приостанавливается до тех пор, пока не будут завершены инструкции, предназначенные для записи в один и тот же регистр. Инструкция также приостанавливается, когда необходимые функциональные блоки в данный момент заняты. Ни одна инструкция не выдается, если ее нельзя полностью отследить от начала до конца.
Чтение операндов : после того, как инструкция была выдана и правильно назначена требуемому аппаратному модулю (названному в книге Торнтона вычислительным модулем), модуль ждет, пока все операнды не станут доступны. Доступ только к чтению осуществляется, когда записи зависимости ( RAW – чтение после записи) удалены из всех остальных модулей. Чтобы избежать конфликта порта регистрации файла, средство выбора приоритета выбирает один вычислительный модуль (в случае, когда несколько модулей свободны от опасностей).
Выполнение : Когда все операнды выбраны, вычислительный блок начинает выполнение. После того, как результат будет готов, на табло будет отправлено уведомление.
Запись результата : на этом этапе результат готов, но еще не записан в регистр назначения. Запись не может продолжаться до тех пор, пока устройство не будет очищено от всех опасностей ( WAR – запись после чтения). Единственные дополнительные задержки здесь связаны с доступностью портов файлов регистров: в 6600 использовался инструмент выбора приоритета для выбора одного результата для каждого порта записи. После записи устройство помечается как незанятое, и все опасности и состояния удаляются. Обратите внимание, что только в расширенных (дополненных, точных) табло с возможностью «Тени» фаза записи результата будет предотвращена (отложена). Оригинальный 6600 не имел такой возможности.

Выше важно отметить, что чтение происходит только при отсутствии опасностей записи , а запись продолжается при отсутствии опасностей чтения . Это логично, но противоречит ожиданиям. В частности, обратите внимание, что операции записи должны ждать записи после чтения, чтобы дать другим устройствам возможность прочитать текущее значение в регистре, прежде чем перезаписать его новым. Следовательно, почему записи должны ждать до тех пор, пока не исчезнет опасность WAR.

Структура данных [ править ]

Для контроля выполнения инструкций на табло ведутся три таблицы состояний:

Статус инструкции : указывает для каждой выполняемой инструкции, на каком из четырех этапов она находится.
Статус функционального блока : указывает состояние каждого функционального блока. Каждый функциональный блок поддерживает 9 полей в таблице:
- Занято: указывает, используется устройство или нет.
- Op: Операция, выполняемая в устройстве (например, MUL, DIV или MOD).
- F _i : Регистр назначения
- F _j ,F _k : Номера регистров источника
- Q _j ,Q _k : Функциональные блоки, которые будут создавать исходные регистры F _j , F _k
- Rj _, ,Rk _: Флаги, указывающие, когда Fj _Fk готовы _к использованию и еще не считаны.
Статус регистра : указывает для каждого регистра, какой функциональный блок будет записывать в него результаты.

Оригинальный алгоритм 6600 [ править ]

Подробный алгоритм управления табло, изложенный в оригинальном патенте, описан ниже:

 function issue(op, dst, src1, src2)
    wait until (!Busy[FU] AND !Result[dst]); // FU can be any functional unit that can execute operation op
    Busy[FU] ← Yes;
    Op[FU] ← op;
    F_i[FU] ← dst;
    F_j[FU] ← src1;
    F_k[FU] ← src2;
    Q_j[FU] ← Result[src1];
    Q_k[FU] ← Result[src2];
    R_j[FU] ← Q_j[FU] == 0;
    R_k[FU] ← Q_k[FU] == 0;
    Result[dst] ← FU;

 function read_operands(FU)
    wait until (R_j[FU] AND R_k[FU]);
    R_j[FU] ← No;
    R_k[FU] ← No;

 function execute(FU)
    // Execute whatever FU must do

 function write_back(FU)
    wait until (∀f {(F_j[f]≠F_i[FU] OR R_j[f]=No) AND (F_k[f]≠F_i[FU] OR R_k[f]=No)})
    foreach f do
        if Q_j[f]=FU then R_j[f] ← Yes;
        if Q_k[f]=FU then R_k[f] ← Yes;
    Result[F_i[FU]] ← 0; // 0 means no FU generates the register's result
    RegFile[F_i[FU]] ← computed value;
    Busy[FU] ← No;

Замечания [ править ]

Книга Торнтона появилась раньше современной компьютерной терминологии.

Функциональные блоки (конвейеры) назывались «вычислительными блоками».
«Конфликт Первого Ордена» охватывал как стойло, поскольку все подразделения были заняты, так и конфликт WAW . ^[2]
«Конфликт второго порядка» — это термин, используемый для обозначения конфликта RAW . ^[3]
«Конфликт третьего порядка» охватывал военный конфликт . ^[4]

Застой произошел только на этапе выпуска, когда были обнаружены конфликты «Первого порядка». Некоторые другие методы, такие как алгоритм Томасуло, дополнительно разрешают зависимости WAW с помощью переименования регистров . Первоначальный CDC 6600, вероятно, не имел функции отслеживания опасностей WAW просто потому, что его разработчикам нужно было доставить продукт, а затем перешли к 7600: вместо этого остановка была наиболее целесообразным вариантом. Нет никаких технических причин, по которым переименование Регистров не должно быть добавлено в Табло.

Анализ обоих алгоритмов был проведен Люком Лейтоном и описан процесс преобразования, который показывает эквивалентность алгоритма Томасуло и алгоритма 6600 Scoreboard. ^[5] Разрешение опасностей WAW действительно отсутствует в исходном алгоритме: 6600 останавливался при первом возникновении опасности записи. ^[6]

См. также [ править ]

Ссылки [ править ]

^ Торнтон, Джеймс Э. (1965). «Параллельная работа в данных управления 6600». Материалы осенней совместной компьютерной конференции, состоявшейся 27–29 октября 1964 г., часть II: Очень быстродействующие компьютерные системы . АФИПС '64. Сан-Франциско, Калифорния: ACM. стр. 33–40. дои : 10.1145/1464039.1464045 .
^ Торнтон (1970 , стр. 125)
^ Торнтон (1970 , стр. 126)
^ Торнтон 1970 , с. 127
^ Преобразование Томасуло в табло
^ Торнтон, Джеймс (1970). Проектирование компьютера: Контрольные данные 6600 (PDF) . п. 126. ИСБН 9780673059536 .

Гленфорд Майерс , «Регистровое табло на микропроцессорном чипе», патент США 4891753.

Внешние ссылки [ править ]

Динамическое планирование — табло
Компьютерная архитектура: количественный подход , Джон Л. Хеннесси и Дэвид А. Паттерсон
EECS 252 Выпускник компьютерной архитектуры Лек XX — ТЕМА , Электротехника и компьютерные науки, Беркли, Калифорнийский университет.
Пример табло

[1] Торнтон, Джеймс Э. (1965). «Параллельная работа в данных управления 6600». Материалы осенней совместной компьютерной конференции, состоявшейся 27–29 октября 1964 г., часть II: Очень быстродействующие компьютерные системы . АФИПС '64. Сан-Франциско, Калифорния: ACM. стр. 33–40. дои : 10.1145/1464039.1464045 .

[2] Торнтон (1970 , стр. 125)

[3] Торнтон (1970 , стр. 126)

[4] Торнтон 1970 , с. 127

[5] Преобразование Томасуло в табло

[6] Торнтон, Джеймс (1970). Проектирование компьютера: Контрольные данные 6600 (PDF) . п. 126. ИСБН 9780673059536 .

[1]

[2]

[3]

[4]

[5]

[6]