Аппаратная реализация динамического планирования инструкций: метод Scoreboarding.

Введение

Счетная таблица — это централизованный метод, впервые реализованный в компьютере CDC 6600, для динамического планирования инструкций, позволяющий им выполняться вне порядка, когда отсутствуют конфликты и аппаратное обеспечение доступно. В счетной таблице фиксируются, отслеживаются и строго соблюдаются зависимости данных каждой инструкции в любой момент времени. Инструкции выполняются только тогда, когда счетная таблица определяет отсутствие конфликтов с ранее выданными ("в процессе выполнения") инструкциями. Если выполнение инструкции приостановлено из-за небезопасности выдачи (или недостатка ресурсов), счетная таблица контролирует поток выполняющихся инструкций до тех пор, пока все зависимости не будут устранены, после чего приостановленная инструкция будет выполнена. По сути, операции чтения выполняются при отсутствии рисков записи, а операции записи — при отсутствии рисков чтения. Счетная таблица представляет собой аппаратную реализацию того же базового алгоритма, который используется в языках потоковой обработки данных, создавая ориентированный ациклический граф, где та же логика применяется в среде выполнения языка программирования.

Этапы

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

Instructions are decoded in order and go through the following four stages. Issue: The system checks which registers will be read and written by this instruction and where conflicts WAR and RAW and WAW are detected. RAW and WAR hazards are recorded using a Dependency Matrix (constructed from SR NOR latches in the original 6600 design) as it will be needed in the following stages. Simultaneously, an entry is recorded in a second Matrix, which records the instruction order as a Directed Acyclic Graph. In order to avoid output dependencies (WAW – Write after Write) the instruction is stalled until instructions intending to write to the same register are completed. The instruction is also stalled when required functional units are currently busy. No instruction is ever issued unless it is fully trackable from start to finish. Read operands: After an instruction has been issued and correctly allocated to the required hardware module (named a Computation Unit in Thornton's book), the Unit waits until all operands become available. The read only proceeds when write dependencies (RAW – Read after Write) have been dropped from all other Units. To avoid Register File Port contention, a Priority Picker selects one Computational Unit (in the case where several Units are clear of hazards). Execution: When all operands have been fetched, the Computation Unit starts its execution. After the result is ready, the scoreboard is notified. Write Result: In this stage the result is ready but has not yet been written to its destination register. The write may not proceed until the Unit is clear of all (WAR – Write after Read) hazards. The only additional delays here are based on availability of register file ports: in the 6600 a Priority Picker was used to select one result per write port. Once written the unit is marked as no longer busy, and all hazards and state is dropped. Note that only in advanced (augmented, precise) scoreboards with "Shadow" capability will the Write Result phase be prevented (delayed). The original 6600 did not have this capability. It is critical to note above that Reads only proceed in the absence of write hazards, and that writes proceed in the absence of Read hazards. This is logical but contraindicative to expectations. In particular, note that Writes must wait to write after read in order to give other units the opportunity to read the current value in a register, before overwriting it with the new one. Hence why writes must wait until the absence of WAR hazards.

Замечания

Книга Торнтона предшествует современной компьютерной терминологии. Функциональные блоки (конвейеры) назывались "вычислительными блоками". "Конфликт первого порядка" охватывал как задержки из-за занятости всех блоков, так и конфликт WAW. "Конфликт второго порядка" использовался для обозначения конфликта RAW. "Конфликт третьего порядка" охватывал конфликт WAR. Задержки возникали только на этапе выдачи, при обнаружении конфликтов "первого порядка". Некоторые другие методы, такие как алгоритм Томасуло, дополнительно разрешают зависимости WAW посредством переименования регистров. Оригинальный CDC 6600, вероятно, не имел отслеживания опасностей WAW просто потому, что его разработчикам нужно было выпустить продукт, а затем они перешли к 7600: остановка была наиболее быстрым решением. Нет технических причин, по которым переименование регистров нельзя добавить к системе Scoreboard. Люк Лейтон проанализировал оба алгоритма и описал процесс преобразования, демонстрирующий эквивалентность алгоритма Томасуло и алгоритма Scoreboard для CDC 6600. Разрешение опасностей WAW действительно отсутствует в оригинальном алгоритме: CDC 6600 останавливался при первом возникновении Write Hazard.