Конвейер инструкций в RISC-процессорах

Введение

Трубопровод инструкций

В истории компьютерного оборудования некоторые ранние центральные процессоры с уменьшенным набором инструкций (RISC-ЦПУ) использовали очень похожее архитектурное решение, которое сейчас называется классическим RISC-трубопроводом. К этим процессорам относятся: MIPS, SPARC, Motorola 88000, а позже – процессор DLX, разработанный для учебных целей. Каждый из этих классических скалярных RISC-дизайнов извлекает и пытается выполнить одну инструкцию за такт. Основной общей концепцией каждой конструкции является пятиступенчатый конвейер инструкций. В процессе работы каждый этап конвейера обрабатывает одну инструкцию за раз. Каждый из этих этапов состоит из набора триггеров для хранения состояния и комбинационной логики, которая обрабатывает выходные сигналы этих триггеров.

Привлечь инструкцию

Инструкции хранятся в памяти, чтение из которой занимает один цикл. Эта память может быть реализована на SRAM или в кэше инструкций. Термин "латентность" часто используется в информатике и означает время от начала выполнения операции до её завершения. Таким образом, выборка инструкции имеет латентность в один тактовый цикл (при использовании SRAM с доступом за один цикл или если инструкция находится в кэше). Следовательно, на этапе выборки инструкции из памяти инструкций извлекается 32-битная инструкция. Программный счетчик, или PC, – это регистр, содержащий адрес, который подается на вход памяти инструкций. Адрес подается в память инструкций в начале цикла. Затем, в течение этого цикла, инструкция считывается из памяти инструкций, и одновременно выполняется вычисление следующего значения PC. Следующее значение PC вычисляется путем приращения текущего PC на 4 и выбора между этим значением и результатом вычисления ветвления или перехода в качестве следующего PC. Важно отметить, что в классической RISC-архитектуре все инструкции имеют одинаковую длину. (Это одно из ключевых отличий RISC от CISC). В оригинальных RISC-проектах размер инструкции составляет 4 байта, поэтому к адресу инструкции всегда добавляется 4, но не следует использовать PC + 4 в случае выполненного ветвления, перехода или исключения (см. раздел о ветвлениях с задержкой ниже). (Следует отметить, что некоторые современные системы используют более сложные алгоритмы (предсказание переходов и предсказание цели перехода) для определения следующего адреса инструкции.)

Код инструкции

Еще одно отличие первых RISC-машин от более ранних CISC-машин заключается в отсутствии микрокода в RISC. В случае микрокодированных инструкций CISC, после извлечения из кэша инструкций, биты инструкции перемещаются по конвейеру, где простая комбинационная логика на каждом этапе конвейера генерирует управляющие сигналы для шины данных непосредственно из битов инструкции. В этих CISC-конструкциях декодирование на стадии, традиционно называемой стадией декодирования, выполняется в минимальном объеме. Следствием такого недостатка декодирования является необходимость использования большего количества битов инструкции для указания выполняемой операции. Это оставляет меньше битов для таких элементов, как индексы регистров. Все инструкции MIPS, SPARC и DLX имеют не более двух регистровых операндов. Во время декодирования индексы этих двух регистров идентифицируются в инструкции и передаются в память регистров в качестве адреса. Таким образом, два указанных регистра считываются из файла регистров. В конструкции MIPS файл регистров содержит 32 записи. Одновременно с чтением файла регистров, логика выдачи инструкций на этом этапе определяет, готов ли конвейер к выполнению инструкции. Если нет, логика выдачи вызывает остановку как стадии выборки инструкции, так и стадии декодирования. В цикле остановки входные триггеры не принимают новые биты, поэтому в течение этого цикла новые вычисления не производятся. Если декодируемая инструкция является инструкцией ветвления или перехода, целевой адрес ветвления или перехода вычисляется параллельно с чтением файла регистров. Условие ветвления вычисляется на следующем цикле (после чтения файла регистров), и если ветвление выполняется или инструкция является переходом, регистр PC на первом этапе присваивается целевому адресу ветвления, а не инкрементированному PC, который был вычислен. Некоторые архитектуры использовали арифметико-логическое устройство (АЛУ) на этапе выполнения, что приводило к незначительному снижению пропускной способности инструкций. Стадия декодирования оказалась оснащена значительным количеством аппаратного обеспечения: MIPS имеет возможность ветвления, если два регистра равны, поэтому 32-битное AND-дерево работает последовательно после чтения файла регистров, создавая очень длинный критический путь через этот этап (что означает меньшее количество циклов в секунду). Кроме того, вычисление целевого адреса ветвления обычно требовало 16-битного сложения и 14-битного инкрементатора. Разрешение ветвления на этапе декодирования позволило ограничиться штрафом за неправильное предсказание ветвления в один цикл. Поскольку ветвления часто выполнялись (и, следовательно, неправильно предсказывались), было очень важно поддерживать этот штраф на низком уровне.

Another thing that separates the first RISC machines from earlier CISC machines, is that RISC has no microcode. In the case of CISC micro coded instructions, once fetched from the instruction cache, the instruction bits are shifted down the pipeline, where simple combinational logic in each pipeline stage produces control signals for the datapath directly from the instruction bits. In those CISC designs, very little decoding is done in the stage traditionally called the decode stage. A consequence of this lack of decoding is that more instruction bits have to be used to specifying what the instruction does. That leaves fewer bits for things like register indices. All MIPS, SPARC, and DLX instructions have at most two register inputs. During the decode stage, the indexes of these two registers are identified within the instruction, and the indexes are presented to the register memory, as the address. Thus the two registers named are read from the register file. In the MIPS design, the register file had 32 entries. At the same time the register file is read, instruction issue logic in this stage determines if the pipeline is ready to execute the instruction in this stage. If not, the issue logic causes both the Instruction Fetch stage and the Decode stage to stall. On a stall cycle, the input flip flops do not accept new bits, thus no new calculations take place during that cycle. If the instruction decoded is a branch or jump, the target address of the branch or jump is computed in parallel with reading the register file. The branch condition is computed in the following cycle (after the register file is read), and if the branch is taken or if the instruction is a jump, the PC in the first stage is assigned the branch target, rather than the incremented PC that has been computed. Some architectures made use of the Arithmetic logic unit (ALU) in the Execute stage, at the cost of slightly decreased instruction throughput. The decode stage ended up with quite a lot of hardware: MIPS has the possibility of branching if two registers are equal, so a 32 bit wide AND tree runs in series after the register file read, making a very long critical path through this stage (which means fewer cycles per second). Also, the branch target computation generally required a 16 bit add and a 14 bit incrementer. Resolving the branch in the decode stage made it possible to have just a single cycle branch mis predict penalty. Since branches were very often taken (and thus mis predicted), it was very important to keep this penalty low.

Доступ к памяти

Если требуется доступ к памяти данных, он осуществляется на этом этапе. В течение этого этапа инструкции с задержкой в один цикл просто передают свои результаты на следующий этап. Такая пересылка гарантирует, что инструкции, выполняющиеся за один и два цикла, всегда записывают свои результаты на одной и той же стадии конвейера, что позволяет использовать только один порт записи в регистровую память, и он всегда доступен. Для кэша данных с прямым отображением и виртуальными тегами – самой простой из множества возможных организаций кэша данных – используются две SRAM: одна для хранения данных, а другая – для хранения тегов.

Отписать

На этом этапе инструкции как с одним, так и с двумя тактами записи записывают свои результаты в регистровый файл. Важно отметить, что две разные стадии одновременно обращаются к регистровому файлу: стадия декодирования читает два исходных регистра, в то время как стадия записи возврата записывает регистр назначения предыдущей инструкции. На реальном кремнии это может привести к конфликту (подробнее о конфликтах – ниже). Это происходит потому, что один из исходных регистров, считываемых на стадии декодирования, может совпадать с регистром назначения, записываемым на стадии записи возврата. В этом случае одни и те же ячейки памяти в регистровом файле одновременно читаются и записываются. На кремнии многие реализации ячеек памяти не будут функционировать корректно при одновременном чтении и записи.

Опасности

Хеннесси и Паттерсон ввели термин "угроза" для обозначения ситуаций, когда инструкции в конвейере приводят к неверным результатам.

Структурные опасности

Структурные конфликты возникают, когда две инструкции могут попытаться использовать одни и те же ресурсы одновременно. Классические RISC-конвейеры избегали этих конфликтов, дублируя аппаратное обеспечение. В частности, инструкции перехода могли использовать АЛУ для вычисления адреса перехода. Если бы АЛУ использовался на этапе декодирования для этой цели, то инструкция АЛУ, следующая за инструкцией перехода, привела бы к попытке одновременного использования АЛУ обеими инструкциями. Этот конфликт можно легко разрешить, добавив специализированный сумматор адреса перехода на этап декодирования.

Исключения

Предположим, 32-битный RISC-процессор выполняет инструкцию ADD, складывающую два больших числа, и результат не помещается в 32 бита. Самым простым решением, предоставляемым большинством архитектур, является перенос (wrapping) в арифметике. Числа, превышающие максимальное возможное кодируемое значение, усекаются, отбрасывая старшие биты, пока не поместятся. В обычной целочисленной системе 3000000000 + 3000000000 = 6000000000. При использовании 32-битной переноса для беззнаковых чисел, 3000000000 + 3000000000 = 1705032704 (6000000000 mod 2^32). Это может показаться не очень полезным. Главное преимущество переноса в арифметике заключается в том, что каждая операция имеет чётко определённый результат. Однако программист, особенно если он работает на языке, поддерживающем большие целые числа (например, Lisp или Scheme), может не желать использования переноса. Некоторые архитектуры (например, MIPS) определяют специальные операции сложения, которые при переполнении переходят к специальным местам, вместо того чтобы выполнять перенос результата. Программное обеспечение по целевому адресу отвечает за исправление проблемы. Этот специальный переход называется исключением. Исключения отличаются от обычных переходов тем, что адрес назначения не указан в самой инструкции, а решение о переходе зависит от результата выполнения инструкции. Наиболее распространённым типом исключения, видимого для программного обеспечения на одной из классических RISC-машин, является промах TLB. Исключения отличаются от переходов и прыжков тем, что эти другие изменения потока управления разрешаются на стадии декодирования. Исключения разрешаются на стадии записи результата. Когда обнаруживается исключение, последующие инструкции (находящиеся на более ранних стадиях конвейера) помечаются как недействительные, и их результаты отбрасываются по мере продвижения к концу конвейера. Счетчик команд устанавливается на адрес специального обработчика исключений, а специальные регистры записываются с указанием местоположения и причины исключения. Чтобы упростить (и ускорить) исправление проблемы и перезапуск программы, процессор должен генерировать точное исключение. Точное исключение означает, что все инструкции до вызвавшей исключение инструкции были выполнены, а вызвавшая исключение инструкция и все последующие не были выполнены. Для генерации точных исключений процессор должен фиксировать изменения в видимом для программного обеспечения состоянии в порядке программы. Это последовательное фиксирование происходит естественным образом в классическом RISC-конвейере. Большинство инструкций записывают свои результаты в регистровый файл на стадии записи, поэтому эти записи автоматически происходят в порядке программы. Однако инструкции сохранения записывают свои результаты в очередь данных сохранения на стадии доступа. Если инструкция сохранения вызывает исключение, запись в очереди данных сохранения становится недействительной, чтобы она не была записана в SRAM кэша данных позднее.

Suppose a 32 bit RISC processes an ADD instruction that adds two large numbers, and the result does not fit in 32 bits. The simplest solution, provided by most architectures, is wrapping arithmetic. Numbers greater than the maximum possible encoded value have their most significant bits chopped off until they fit. In the usual integer number system, 3000000000+3000000000=6000000000. With unsigned 32 bit wrapping arithmetic, 3000000000+3000000000=1705032704 (6000000000 mod 2^32). This may not seem terribly useful. The largest benefit of wrapping arithmetic is that every operation has a well defined result. But the programmer, especially if programming in a language supporting large integers (e. g. Lisp or Scheme), may not want wrapping arithmetic. Some architectures (e. g. MIPS), define special addition operations that branch to special locations on overflow, rather than wrapping the result. Software at the target location is responsible for fixing the problem. This special branch is called an exception. Exceptions differ from regular branches in that the target address is not specified by the instruction itself, and the branch decision is dependent on the outcome of the instruction. The most common kind of software visible exception on one of the classic RISC machines is a TLB miss. Exceptions are different from branches and jumps, because those other control flow changes are resolved in the decode stage. Exceptions are resolved in the writeback stage. When an exception is detected, the following instructions (earlier in the pipeline) are marked as invalid, and as they flow to the end of the pipe their results are discarded. The program counter is set to the address of a special exception handler, and special registers are written with the exception location and cause. To make it easy (and fast) for the software to fix the problem and restart the program, the CPU must take a precise exception. A precise exception means that all instructions up to the excepting instruction have been executed, and the excepting instruction and everything afterwards have not been executed. To take precise exceptions, the CPU must commit changes to the software visible state in the program order. This in order commit happens very naturally in the classic RISC pipeline. Most instructions write their results to the register file in the writeback stage, and so those writes automatically happen in program order. Store instructions, however, write their results to the Store Data Queue in the access stage. If the store instruction takes an exception, the Store Data Queue entry is invalidated so that it is not written to the cache data SRAM later.

Устранение ошибок с кэшем

Иногда кэш данных или кэш инструкций не содержит требуемых данных или инструкцию. В этих случаях процессор должен приостановить работу до тех пор, пока кэш не будет заполнен необходимыми данными, а затем возобновить выполнение. Проблема заполнения кэша необходимыми данными (и, возможно, записи вытесненной линии кэша в память) не является специфичной для организации конвейера и здесь не рассматривается. Существует два подхода к решению проблемы приостановки/возобновления. Первый – использование глобального сигнала остановки. Этот сигнал, при активации, предотвращает продвижение инструкций по конвейеру, как правило, блокируя тактовую частоту на триггерах в начале каждого этапа. Недостатком этого подхода является большое количество триггеров, из-за чего распространение сигнала остановки занимает много времени. Поскольку машина обычно должна остановиться в том же цикле, в котором обнаруживается условие, требующее остановки, сигнал остановки становится критическим путем, ограничивающим скорость работы. Другой подход к обработке приостановки/возобновления – повторное использование логики обработки исключений. Машина генерирует исключение для проблемной инструкции, и все последующие инструкции становятся недействительными. Когда кэш заполнен необходимыми данными, инструкция, вызвавшая промах кэша, перезапускается. Для ускорения обработки промахов кэша данных инструкцию можно перезапустить так, чтобы ее цикл доступа начался через один цикл после заполнения кэша данных.