Конвейер (процессоры)/Перевод

Пожалуйста, не удаляйте эту статью! В данный момент в ней идет работа по переводу основной английской версии для замены кошмарной русской. После завершения работы я объединю получившуюся статью с имеющейся русской версией.

Простой пятиуровневый конвейер в IF (англ. Instruction Fetch) — получение инструкции, ID (англ. Instruction Decode) — раскодирование инструкции, EX (англ. Execute) — выполнение, MEM (англ. Memory access) — доступ к памяти, WB (англ. Register write back) — запись в регистр. Вертикальная ось — это последовательные независимые инструкции, горизонтальная — время. Соответственно, в зеленой колонке, которая описывает состояние процессора в один момент времени, самая ранняя, верхняя инструкция уже находится в состоянии записи в регистр, а самая последняя, нижняя инструкция только в процессе чтения.

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

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

Сам термин «конвейер» пришел из промышленности, где используется аналогичный принцип работы — материал автоматически подтягивается по ленте конвейера к рабочему, который осуществляет с ним необходимые действия, следующий за ним рабочий выполняет свои функции над получившейся заготовкой, следующий делает еще что-то, таким образом, к концу конвейера цепочка рабочих полностью выполняет все поставленные задачи, не срывая, однако, темпов производства.

Считается, что впервые конвейерные вычисления были использованы либо в проекте ILLIAC II (англ. en:ILLIAC II), либо в проекте IBM Stretch (англ. en:IBM Stretch). Проект IBM Stretch предложил термины «получение» (англ. «Fetch»), «расшифровка» (англ. «Decode») и «выполнение» (англ. «Execute»), которые затем стали общеупотребляемыми.

Многие современные процессоры управляются таймером. Процессор внутри состоит из логики и памяти (триггеров). Когда приходит сигнал от таймера, триггеры приобретают своё новое значение и логике требуется отрезок времени для декодирования новых значений. Затем приходит следующий сигнал от таймера, триггеры снова принимают новые значения, и так далее. Разбивая логику на более мелкие части и вставляя триггеры между частями логики, время, необходимое логике для правильного вывода, уменьшается. В этом случае, интервал сработки таймера процессора может быть соответственно уменьшен. Например, конвейер

1. получение инструкции (англ. Instruction Fetch);
2. раскодирование инструкции (англ. Instruction Decode) и чтение регистров (англ. Register fetch);
3. выполнение(англ. Execute);
4. доступ к памяти (англ. Memory access);
5. запись в регистр (англ. Register write back);

Когда программист (либо компилятор) пишут ассемблерный код, они делают предположение, что каждая инструкция заканчивает выполняться до того, как начнет выполняться следующая за ней. Использование конвейера делает это предположение неверным. Ситуация, когда использование конвейера заставляет программу работать некорректно, известна как «конфликт конвейера» (англ. en:Hazard (computer architecture)). Существуют различные техники устранения конфликтов, например, форвардинг (англ. «Forwarding») или пробуксовка (англ. «Stalling»).

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

Процессоры с конвейером внутри устроены так, что они разделены на «этапы», которые могут полу-независимо работать над разными задачами. Каждый этап связан в «цепочку» с другими таким образом, что результаты работы каждого из этапов «скармливаются» следующему этапу в цепочке до тех пор, пока работа не будет выполнена. Подобная организация процессора позволяет значительно уменьшить время работы.

К сожалению, не все инструкции являются независимыми. В простом конвейере обработка инструкции может потребовать 5-ти этапов обработки. Для работы в полную мощность, этот конвейер должен выполнять 4 последовательные независимые инструкции, пока заканчивается обработка первой. Если же 4-х инструкций, которые не зависят от результата выполнения первой инструкции, нет, управляющая логика должна вставлять в конвейер ничего не делающую заглушку (англ. stall) до тех пор, пока зависимость не будет разрешена. К счастью, такие техники, как форвардинг, значительно уменьшают количество случаев, где всё же необходимо вставлять заглушки (т.е. заставлять процессор пробуксовывать). Хотя конвейеры в теории позволяют увеличить производительность по сравнению с бесконвейерным процессором в количество раз, равное количеству этапов (подразумевая, что частота таймера также масштабируется с количеством этапов), в реальности, большинство кода не позволяет идеального выполнения.

Advantages and Disadvantages

Pipelining does not help in all cases. There are several possible disadvantages. An instruction pipeline is said to be fully pipelined if it can accept a new instruction every clock cycle. A pipeline that is not fully pipelined has wait cycles that delay the progress of the pipeline.

Advantages of Pipelining:

1. The cycle time of the processor is reduced, thus increasing instruction issue-rate in most cases.
2. Some combinatorial circuits such as adders or multipliers can be made faster by adding more circuitry. If pipelining is used instead, it can save circuitry vs. a more complex combinatorial circuit.

Disadvantages of Pipelining:

1. A non-pipelined processor executes only a single instruction at a time. This prevents branch delays (in effect, every branch is delayed) and problems with serial instructions being executed concurrently. Consequently the design is simpler and cheaper to manufacture.
2. The instruction latency in a non-pipelined processor is slightly lower than in a pipelined equivalent. This is due to the fact that extra flip flops must be added to the data path of a pipelined processor.
3. A non-pipelined processor will have a stable instruction bandwidth. The performance of a pipelined processor is much harder to predict and may vary more widely between different programs.

Examples

Generic pipeline

Generic 4-stage pipeline; the colored boxes represent instructions independent of each other

To the right is a generic pipeline with four stages:

1. Fetch
2. Decode
3. Execute
4. Write-back

The top gray box is the list of instructions waiting to be executed; the bottom gray box is the list of instructions that have been completed; and the middle white box is the pipeline.

Execution is as follows:

Time	Execution
0	Four instructions are awaiting to be executed
1	the green instruction is fetched from memory
2	the green instruction is decoded the purple instruction is fetched from memory
3	the green instruction is executed (actual operation is performed) the purple instruction is decoded the blue instruction is fetched
4	the green instruction's results are written back to the register file or memory the purple instruction is executed the blue instruction is decoded the red instruction is fetched
5	the green instruction is completed the purple instruction is written back the blue instruction is executed the red instruction is decoded
6	The purple instruction is completed the blue instruction is written back the red instruction is executed
7	the blue instruction is completed the red instruction is written back
8	the red instruction is completed
9	All instructions are executed

Bubble

A bubble in cycle 3 delays execution

Основная статья: Bubble (computing)

When a "hiccup" in execution occurs, a "bubble" is created in the pipeline in which nothing useful happens. In cycle 2, the fetching of the purple instruction is delayed and the decoding stage in cycle 3 now contains a bubble. Everything "behind" the purple instruction is delayed as well but everything "ahead" of the purple instruction continues with execution.

Clearly, when compared to the execution above, the bubble yields a total execution time of 8 clock ticks instead of 7.

Bubbles are like stalls, in which nothing useful will happen for the fetch, decode, execute and writeback. It can be completed with a nop code.

Example 1

A typical instruction to add two numbers might be ADD A, B, C, which adds the values found in memory locations A and B, and then puts the result in memory location C. In a pipelined processor the pipeline controller would break this into a series of tasks similar to:

LOAD A, R1
LOAD B, R2
ADD R1, R2, R3
STORE R3, C
LOAD next instruction

The locations 'R1' and 'R2' are registers in the CPU. The values stored in memory locations labeled 'A' and 'B' are loaded (copied) into these registers, then added, and the result is stored in a memory location labeled 'C'.

In this example the pipeline is three stages long- load, execute, and store. Each of the steps are called pipeline stages.

On a non-pipelined processor, only one stage can be working at a time so the entire instruction has to complete before the next instruction can begin. On a pipelined processor, all of the stages can be working at once on different instructions. So when this instruction is at the execute stage, a second instruction will be at the decode stage and a 3rd instruction will be at the fetch stage.

Pipelining doesn't reduce the time it takes to complete an instruction rather it increases the number of instructions that can be processed at once and it reduces the delay between completed instructions- called 'throughput'. The more pipeline stages a processor has, the more instructions it can be working on at once and the less of a delay there is between completed instructions. Every microprocessor manufactured today uses at least 2 stages of pipeline. (The Atmel AVR and the PIC microcontroller each have a 2 stage pipeline). Intel Pentium 4 processors have 20 stage pipelines.

Example 2

To better visualize the concept, we can look at a theoretical 3-stage pipeline:

Stage	Description
Load	Read instruction from memory
Execute	Execute instruction
Store	Store result in memory and/or registers

and a pseudo-code assembly listing to be executed:

LOAD  #40, A      ; load 40 in A
MOVE  A, B        ; copy A in B
ADD   #20, B      ; add 20 to B
STORE B, 0x300    ; store B into memory cell 0x300

This is how it would be executed:

Clock 1

Load	Execute	Store
LOAD

The LOAD instruction is fetched from memory.

Clock 2

Load	Execute	Store
MOVE	LOAD

The LOAD instruction is executed, while the MOVE instruction is fetched from memory.

Clock 3

Load	Execute	Store
ADD	MOVE	LOAD

The LOAD instruction is in the Store stage, where its result (the number 40) will be stored in the register A. In the meantime, the MOVE instruction is being executed. Since it must move the contents of A into B, it must wait for the ending of the LOAD instruction.

Clock 4

Load	Execute	Store
STORE	ADD	MOVE

The STORE instruction is loaded, while the MOVE instruction is finishing off and the ADD is calculating.

And so on. Note that, sometimes, an instruction will depend on the result of another one (like our MOVE example). When more than one instruction references a particular location for an operand, either reading it (as an input) or writing it (as an output), executing those instructions in an order different from the original program order can lead to hazards (mentioned above). There are several established techniques for either preventing hazards from occurring, or working around them if they do.

Complications

Many designs include pipelines as long as 7, 10 and even 20 stages (like in the Pentium 4) The later "Prescott" and "Cedar Mill" Pentium 4 cores (and their Pentium D derivatives) had a 31-stage pipeline, the longest in mainstream consumer computing. The Xelerator X10q has a pipeline more than a thousand stages long^[1] . The downside of a long pipeline is when a program branches, the entire pipeline must be flushed, a problem that branch prediction helps to alleviate. Branch prediction itself can end up exacerbating the problem if branches are predicted poorly. In certain applications, such as supercomputing, programs are specially written to branch rarely and so very long pipelines are ideal to speed up the computations, as long pipelines are designed to reduce clocks per instruction (CPI). If branching happens constantly, re-ordering branches such that the more likely to be needed instructions are placed into the pipeline can significantly reduce the speed losses associated with having to flush failed branches. Programs such as gcov can be used to examine how often particular branches are actually executed using a technique known as coverage analysis, however such analysis is often a last resort for optimization.

The higher throughput of pipelines falls short when the executed code contains many branches: the processor cannot know where to read the next instruction, and must wait for the branch instruction to finish, leaving the pipeline behind it empty. After the branch is resolved, the next instruction has to travel all the way through the pipeline before its result becomes available and the processor appears to "work" again. In the extreme case, the performance of a pipelined processor could theoretically approach that of an un-pipelined processor, or even slightly worse if all but one pipeline stages are idle and a small overhead is present between stages.

Because of the instruction pipeline, code that the processor loads will not immediately execute. Due to this, updates in the code very near the current location of execution may not take effect because they are already loaded into the Prefetch Input Queue. Instruction caches make this phenomenon even worse. This is only relevant to self-modifying programs.

See also

• Wait state
• Classic RISC pipeline
• Pipeline (computing)
• Parallel computing
• Dual pipelining

Примечания

1. ↑ http://www.mdronline.com/watch/watch_Issue.asp?Volname=Issue+%23171&on=1#item13

Ссылки

• Branch Prediction in the Pentium Family
• ArsTechnica article on pipelining
• Counterflow Pipeline Processor Architecture