|
Unit 3 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Linear
Pipeline Processor [RGPV
DEC 12(10)] Pipeline is similar to
the assembly line in industrial plant. To achieve pipelining one must divide
the input process into a sequence of sub tasks and each of which can be
executed concurrently with other stages. Pipelining is a technique of that
decompose any sequential process into small sub processes, which are
independent of each other so that each sub process can be executed in a
special dedicated segment and all these segments operates concurrently. Thus
whole task is partitioned to independent tasks and these subtask are executed
by a segment. The result obtained as an output of a segment (after performing
all computation in it) is transferred to next segment in pipeline and the
final result is obtained after the data have been through all segments. Thus
it could understand if take each segment consists of an input register
followed by a combinational circuit. This combinational circuit performs the
required sub operation and register holds the intermediate result. The output
of one combinational circuit is given as input to the next segment. Pipelining can be
effectively implemented for systems having following characteristics: • A system is
repeatedly executes a basic function. • A basic function must
be divisible into independent stages such that each stage have minimal
overlap. •
The complexity of the stages should be roughly similar Basic Structure and
Control of a Linear Pipeline Processor
(L=latch, C=clock, Si=the ith stage.) Speedup
ratio : The
speed up ratio is ratio between maximum time taken by non pipeline process
over process using pipelining Let
tp be the one clock cycle time. The
time taken for n processes having k segments in pipeline configuration will
be =
k*tp + (n-1)*tp= (k+n-1)*tp Speedup Sk
=T/TK=n.k/k+ (n-1) Max
speed up k when n tends to infinity Efficiency
:
The efficiency of linear pipeline is measured by the percentage of time when
processor are busy over total time taken i.e., sum of busy time plus idle
time. Thus if n is number of task , k is stage of pipeline and t is clock
period then efficiency is given by η
= n/ [k + n -1] Thus
larger number of task in pipeline more will be pipeline busy hence better
will be efficiency. It can be easily seen from expression as n
→∞, η →1. η
= Sk/k Throughput: The number of task
completed by a pipeline per unit time is called throughput, this represents
computing power of pipeline. We define throughput as W=
n/[k*t + (n-1) *t] = η/t In
ideal case as η -> 1 the throughout is equal to 1/t that is equal to
frequency. Thus maximum throughput is obtained is there is one output per
clock pulse. Eg: A non-pipeline
system takes 60 ns to process a task. The same task can be processed in six
segment pipeline with a clock cycle of 10 ns. Determine the speedup ratio of
the pipeline for 100 tasks. What is the maximum speed up that can be
achieved? Soln.
Total time taken by for non pipeline to complete 100 task is = 100 * 60 =
6000 ns Total
time taken by pipeline configuration to complete 100 task is =
(100 + 6 –1) *10 = 1050 ns Thus
speed up ratio will be = 6000 / 1050 = 4.76 The
maximum speedup that can be achieved for this process is = 60 / 10 = 6 Thus,
if total speed of non pipeline process is same as that of total time taken to
complete a process with pipeline than maximum speed up ratio is equal to
number of segments
Nonlinear Pipeline [RGPV DEC
12(10)JUN 13,JUN14 DEC14,JUN 15(7)] A dynamic
pipeline can be reconfigured to perform variable function at different times.
The traditional linear pipelines are static pipeline because they used to
perform fixed function. A dynamic pipeline allows feed
forward and feedback connections in addition to streamline connection. A
dynamic pipelining may initiate tasks from different reservation tables
simultaneously to allow multiple numbers of initiations of different
functions in the same pipeline. Reservation Tables and latency analysis Reservation tables are used how
successive pipeline stages are utilized for a specific evaluation function.
These reservation tables show the sequence in which each function utilizes
each stage. The rows correspond to pipeline stages and the columns to clock
time units. The total number of clock units in the table is called the
evaluation time. A reservation table represents the flow of data through the
pipeline for one complete evaluation of a given function. (For example, think
of X as being a floating square root, and Y as being a floating cosine. A
simple floating multiply might occupy just S1 and S2 in sequence.) We could
also denote multiple stages being used in parallel, or a stage being drawn
out for more than one cycle with these diagrams. Job Sequencing and Collision Prevention Initiation
the start a single function evaluation collision may occur as two or
more initiations attempt to use the
same stage at the same time. Thus it is required to properly schedule queued
tasks awaiting initiation in order to avoid collisions and to achieve high
throughput. We can define collision as: 1.
A collision occurs when two tasks are
initiated with latency (initiation interval) equal to the column distance
between two “X” on some row of the reservation table 2.
The set of column distances F ={l1,l2,…,lr} between all possible
pairs of “X” on each row of the reservation table is called
the forbidden set of latencies. 3.
The collision vector is a binary vector C = (Cn…C2 C1), Where
Ci=1 if i belongs to F (set of
forbidden latencies) and Ci=0 otherwise. Some fundamental concepts used in it are: Latency - number of time units between two initiations (any positive
integer 1, 2,…) Latency sequence – sequence of latencies between
successive initiations Latency cycle – a latency sequence that
repeats itself Control strategy – the procedure to choose a
latency sequence Greedy strategy – a control strategy that always
minimizes the latency between the current initiation and the very last
initiation. State
Diagrams ·
State diagrams can be constructed to specify the permissible
transitions among successive initiations. ·
The collision vector, corresponding to the initial state of
pipeline at time 1, is called the initial collision vector. ·
The next state of the pipeline at time t+p can be obtained by
using a bit-right shift register ·
Initial CV is loaded into the register. ·
The register is then shifted to the right. When a 0 emerges from
the right end after p shifts, p is a permissible latency .When a 1 emerges,
the corresponding latency should be forbidden. Logical 0 enters from the left
end of the shift register. ·
The next state after p shifts is obtained by bitwise-ORing the
initial CV with the shifted register contents. ·
This bitwise-ORing of the shifted contents is meant to prevent
collisions from the future initiations starting at time t+1 and onward. Latency
Cycles ·
Simple Cycles: Latency cycle in which each state appears only
once. ·
Greedy Cycles: whose edges are all made with minimum
latencies from their respective starting states. ·
MAL : minimum average latency ·
At least one of the greedy cycles will lead to MAL
[RGPV JUN 12(10)] Instruction to execute in
computer undergo following steps: • Fetch the instruction
from the memory. • Decode the instruction. • Calculate the effective
address. • Fetch the operands from
the memory. • Execute the instruction
(EX). • Store the result back
into memory (WB). For sake of simplicity we
take calculation of the effective address and fetch operand from memory as
single segment as operand fetch unit. Thus below figure shows how the
instruction cycle in CPU can be processed with five segment instruction
pipeline. Principles of designing pipeline processor Buffers are used to speed
close up the speed gap between memory access for either instructions or
operands. Buffering can avoid unnecessary idling of the processing stages
caused by memory access conflicts or by unexpected branching or interrupts.
The concepts of busing eliminates the time delay to store and to retrieve
intermediate results or to from the registers. The computer performance
can be greatly enhanced if one can eliminate unnecessary memory accesses and
combine transitive or multiple fetch-store operations with faster register
operations. This is carried by register tagging and forwarding. Another method to smooth
the traffic flow in a pipeline is to use buffers to close up the speed gap
between the memory accesses for either instructions or operands and
arithmetic and logic executions in the functional pipes. The instruction or
operand buffers provide a continuous supply of instructions or operands to
the appropriate pipeline units. Buffering can avoid unnecessary idling of the
processing stages caused by memory access conflicts or by
unexpected branching or interrupts. Sometimes the entire loop instructions
can be stored in the buffer to avoid repeated fetch of the same instructions
loop, if the buffer size is sufficiently large. It is very large in the usage
of pipeline computers. Three buffer types are
used in various instructions and data types. Instructions are fetched to the
instruction fetch buffer before sending them to the instruction unit. After
decoding, fixed point and floating point instructions and data are sent to
their dedicated buffers. The store address and data buffers are used for
continuously storing results back to memory. The storage conflict buffer is
used only used when memory Busing Buffers The sub function being
executed by one stage should be independent of the other sub functions being
executed by the remaining stages; otherwise some process in the pipeline must
be halted until the dependency is removed. When one instruction waiting to be
executed is first to be modified by a future instruction, the execution of
this instruction must be suspended until the dependency is released. Another example is the
conflicting use of some registers or memory locations by different segments
of a pipeline. These problems cause additional time delays. An efficient
internal busing structure is desired to route the resulting stations with
minimum time delays. In the AP 120B or FPS 164
attached processor the busing structure are even more sophisticated. Seven
data buses provide multiple data paths. The output of the floating point
adder in the AP 120B can be directly routed back to the input of the floating
point adder, to the input of the floating point multiplier, to the data pad,
or to the data memory. Similar busing is provided for the output of the
floating point multiplier. This eliminates the time delay to store and to
retrieve intermediate results or to from the registers. Internal Forwarding and Register Tagging To enhance the performance
of computers with multiple execution pipelines 1. Internal Forwarding refers
to a short circuit technique for replacing unnecessary memory accesses by
register -to-register transfers in a sequence of fetch-arithmetic-store
operations 2. Register Tagging refers
to the use of tagged registers, buffers and reservations stations for
exploiting concurrent activities among multiple arithmetic units. The computer performance
can be greatly enhanced if one can eliminate unnecessary memory accesses and
combine transitive or multiple fetch-store operations with faster register
operations. This concept of internal data forwarding can be explored in three
directions. The symbols Mi and Rj to represent the ith word in the memory and
jth fetch, store and register-to register transfer. The contents of Mi and Rj
are represented by (Mi) and Rj Store-Fetch Forwarding The store the n fetch can
be replaced by 2 parallel operations, one store and one register transfer. 2 memory accesses Mi -> (R1) (store) R2 -> (Mi) (Fetch) Is being replaced by Only one memory access Mi -> (R1) (store) R2 -> (R1) (register
Transfer) Fetch-Fetch Forwarding The following fetch
operations can be replaced by one fetch and one register transfer. One memory
access has been eliminated. 2 memory accesses R1 -> (Mi) (fetch) R2 -> (Mi) (Fetch) Is being replaced by Only one memory access R1 -> (Mi) (Fetch) R2 -> (R1) (register
Transfer) Store-Store Overwriting The following two memory
updates of the same word can be combined into one; since the second store
overwrites the first. 2 memory accesses Mi -> (R1) (store) Mi -> (R2) (store) Is being replaced by Only one memory access Mi -> (R2) (store) The above steps shows how
to apply internal forwarding to simplify a sequence of arithmetic and memory
access operations
Pipeline Hazards
RGPV JUN 14(7)
Hazards are
problems with the instruction pipeline in central processing unit (CPU) micro architectures that potentially result in incorrect
computation. There are typically three types of hazards: § data hazards § structural hazards § control hazards (branching hazards) There are several methods used to deal with
hazards, including pipeline stalls, pipeline
bubbling, register forwarding, and in
the case of out-of-order execution, the scoreboarding method
and the Tomasulo algorithm. Instructions in a pipelined processor are performed in
several stages, so that at any given time several instructions are being
processed in the various stages of the pipeline, such as fetch and execute.
There are many different instruction pipeline micro
architectures, and instructions may be executed out-of-order. A hazard occurs when two or more of these
simultaneous (possibly out of order) instructions conflict. Types:
Data
hazards
Data
hazards occur when instructions that exhibit data
dependence modify data
in different stages of a pipeline. Ignoring potential data hazards can result
in race
conditions (sometimes
known as race hazards). There are three situations in which a data hazard can
occur: 1.
read after write (RAW), a true dependency 2.
write after read (WAR), an anti-dependency 3.
write after write (WAW), an output dependency Consider
two instructions i1 and i2,
with i1 occurring
before i2 in
program order. Read After
Write (RAW)
(i2 tries to read a source before i1 writes to it) A read after write (RAW) data
hazard refers to a situation where an instruction refers to a result that has
not yet been calculated or retrieved. This can occur because even though an
instruction is executed after a previous instruction, the previous
instruction has not been completely processed through the pipeline. For example i1.R2< R1 + R3 i2.R4< R2 + R3 The first instruction is calculating a value to be saved in
register R2, and the second is going to use this value to compute a
result for register R4. However, in a pipeline, when we fetch the
operands for the 2nd operation, the results from the first will not yet have
been saved, and hence we have a data dependency. We say that there is a data dependency with
instruction i2, as it is dependent on the completion of
instruction i1. Write After Read (WAR) i2 tries to write a destination before it is read
by i1) A write after read (WAR) data hazard represents a problem with
concurrent execution. For example: i1. R4 <- R1 + R3 If we are in a situation that there is a chance
that i2 may be completed before i1 (i.e. with concurrent
execution) we must ensure that we do not store the result of
register R3 before i1 has had a chance to fetch the
operands. Write After Write (WAW) (i2 tries to write an operand before it is written
by i1) A write after write (WAW) data hazard may occur in
a concurrent execution environment For example: i1. R2 <- R4 + R7 We must delay the WB (Write Back) of i2 until the
execution of i1. Structural hazards A structural hazard occurs when a part of the processor's
hardware is needed by two or more instructions at the same time. A canonical
example is a single memory unit that is accessed both in the fetch stage
where an instruction is retrieved from memory, and the memory stage where
data is written and/or read from memory. They can often be resolved by
separating the component into orthogonal units (such as separate caches)
or bubbling the pipeline. Control hazards (branch hazards) Branching hazards (also known as control hazards)
occur with branches. On many instruction pipeline microarchitectures,
the processor will not know the outcome of the
branch when it needs to insert a new instruction into the pipeline (normally
the fetch stage).
Pipeline bubbling
RGPV JUN14(7),JUN15(7) Bubbling the pipeline, also known as a pipeline break or a pipeline stall, is a method for preventing data, structural,
and branch hazards from occurring. As instructions are fetched, control logic
determines whether a hazard could/will occur. If this is true, then the
control logic inserts NOPs into the pipeline. Thus, before the next
instruction (which would cause the hazard) is executed, the previous one will
have had sufficient time to complete and prevent the hazard. If the number of
NOPs is equal to the number of stages in the pipeline, the processor has been
cleared of all instructions and can proceed free from hazards. This is
called flushing the pipeline.
All forms of stalling introduce a delay before the processor can resume
execution. Data hazards There are several main solutions and algorithms used to resolve data
hazards:
In the case of out-of-order execution, the algorithm used can be:
We can delegate the task of removing data dependencies to the
compiler, which can fill in an appropriate number
of NOP instructions between dependent instructions to ensure
correct operation, or re-order instructions where possible. Register forwarding Forwarding involves feeding output data into a previous stage of the
pipeline. Forwarding is implemented by feeding back the output of an
instruction into the previous stage(s) of the pipeline as soon as the output
of that instruction is available. Example NOTE: In the following
examples, computed values are in bold, while Register numbers are
not. For instance let's say we want to write the value 3 to register 1,
(which already contains a 6), and then add 7 to register 1 and store the
result in register 2, i.e.: Instruction 0: Register 1 = 6 Instruction 1: Register 1 = 3 Instruction 2: Register 2 = Register 1
+ 7 = 10 Following execution, register 2 should contain the value 10.
However, if Instruction 1 (write 3 to register 1) does not
completely exit the pipeline before Instruction 2 starts execution, it means
that Register 1 does not contain the value 3 when
Instruction 2 performs its addition. In such an event, Instruction 2
adds 7 to the old value of register 1 (6), and so
register 2 would contain 13 instead ie Instruction 0: Register 1 = 6 Instruction 2: Register 2 = Register 1 + 7 = 13 Instruction 1: Register 1 = 3 This error
occurs because Instruction 2 reads Register 1 before Instruction 1 has committed/stored
the result of its write operation to Register 1. So when Instruction 2 is
reading the contents of Register 1, register 1 still contains 6, not 3. Forwarding
(described below) helps correct such errors by depending on the fact that the
output of Instruction 1 (which is 3)
can be used by subsequent instructions before the value 3 is committed to/stored in Register
1. Forwarding
applied to our example means that we do not wait to commit/store the output
of Instruction 1 in Register 1 (in this example, the output is 3) before making that output
available to the subsequent instruction (in this case, Instruction 2). The effect is that Instruction 2
uses the correct (the more recent) value of Register 1: the commit/store was
made immediately and not pipelined. With
forwarding enabled, the ID/EX or Instruction Decode/Execution stage of the
pipeline now has two inputs: the value read from the register specified (in
this example, the value 6 from Register 1), and the new value
of Register 1 (in this example, this value is 3) which is sent from the
next stage (EX/MEM) or Instruction Execute/Memory Access. Additional control
logic is used to determine which input to use. Control
hazards (branch hazards)
To avoid
control hazards micro architectures can: ·
insert a pipeline bubble (discussed above), guaranteed to
increase latency, or ·
use branch
prediction and
essentially guesstimate which instructions to insert, in which case a pipeline bubble will
only be needed in the case of an incorrect prediction In the event that a branch causes a pipeline bubble after incorrect
instructions have entered the pipeline, care must be taken to prevent any of
the wrongly-loaded instructions from having any effect on the processor state
excluding energy wasted processing them before they were discovered to be
loaded incorrectly.
[ RGPV JUN15(7)DEC 14 (7)JUN 14(7)] Dynamic
scheduling,
where the hardware rearranges the instruction execution to reduce the stalls.
Dynamic scheduling offers several advantages:
A major limitation of the pipelining
techniques is that they use in-order instruction issue: if an
instruction is stalled in the pipeline, no later instructions can
proceed. Thus, if there is a dependency between two closely spaced
instructions in the pipeline, it will stall. For example:
SUBD instruction cannot execute because the
dependency of ADDD on DIVD causes the pipeline to stall; yet SUBD is not data
dependent on anything in the pipeline. This is a performance limitation that
can be eliminated by not requiring instructions to execute in order. To allow SUBD to begin executing, we must
separate the instruction issue process into two parts: checking the
structural hazards and waiting for the absence of a data hazard. We can still
check for structural hazards when we issue the instruction; thus, we still
use in order instruction issue. However, we want the instructions to begin
execution as soon as their data operands are available. Thus, the pipeline
will do out-of-order
execution, which implies out-of-order completion In introducing
out-of-order execution, we have essentially split the ID pipe stage into two
stages Issue : ·
Decode
Instructions check structural hazards ·
Read operands - Wait until
no data hazards, then read operands Scoreboarding is a technique
for allowing instructions to execute out of order when there are sufficient
resources and no data dependencies; it is named after the CDC 6600
scoreboard, which developed this capability. The goal of a
scoreboard is to maintain an execution rate of one instruction per clock
cycle (when there are no structural hazards) by executing an instruction as
early as possible. Thus, when the next instruction to execute is stalled,
other instructions can be issued and executed if they do not depend on any
active or stalled instruction. The scoreboard takes full responsibility for
instruction issue and execution, including all hazard detection. Every instruction
goes through the scoreboard, where a record of the data dependencies is
constructed; this step corresponds to instruction issue and replaces part of
the ID step in the DLX pipeline. The scoreboard then determines when the
instruction can read its operands and begin execution. 2. Tomasulo
Approach is another scheme to allow execution to proceed in
the presence of hazards developed by the IBM 360/91 floating-point unit. This
scheme combines key elements of the score boarding scheme with the
introduction of register renaming. In the loop
unrolling section we showed how a compiler could rename registers to
avoid WAW and WAR hazards. In Tomasulo's scheme this functionality is
provided by the reservation stations, which buffer the operands of
instructions waiting to issue, and by issue logic.s The basic idea is
that a reservation station fetches
and buffers an operand as soon as it is available, eliminating the need to
get the operand from a register. In addition, pending instructions designate
the reservation station that will provide their input. Finally, when
successive writes to a register appear, only the last one is actually used to
update the register. As instructions are
issued, the register specifies for pending operands are renamed to the names
of the reservation station in a process called register renaming. This
combination of issue logic and reservation stations provides renaming
and eliminates WAW and WAR hazards. This additional
capability is the major conceptual difference between score boarding and
Tomasulo's algorithm. Since there can be more reservation stations than real
registers, the technique can eliminate hazards that could not be eliminated
by a compiler
Arthmatic pipeline
The principles used
in instruction pipelining can be used in order to improve the performance of
computers in performing arithmetic operations such as add, subtract, and
multiply. In this case, these principles will be used to realize the
arithmetic circuits inside the ALU, we can elaborate on the use of arithmetic
pipe-line as a means to speed up arithmetic operations. The pipeline
structures used for instruction pipelining may be applied in some cases to
other processing tasks. If pipelining is to be useful, however, we must be
faced with the need to perform a long sequence of essentially similar tasks.
Large numerical applications often make use of repeated arithmetic operations
for processing the elements of vectors and arrays. Architectures specialized
for applications if this type often provide pipelines to speed processing of
floating-point arithmetic sequences. This type of pipelining is called arithmetic
pipelining. Arithmetic pipelines
differ from instruction pipelines in some important ways. They are generally synchronous.
This means that each stage executes in a fixed number of clock cycles. In a
synchronous pipeline, moreover, no buffering between stages is provided. Each
stage must be ready to accept the data passed from a previous stage when that
data is produced. Another important
difference is that an arithmetic pipeline may be nonlinear. The
"stages" in this type of pipeline are associated with key
processing components such as adders, shifters, etc. Instead of a steady
progression through a fixed sequence of stages, a task in a nonlinear
pipeline may use more than one stage at a time, or may return to the same
stage at several points in processing. As an example of a
pipelined arithmetic unit we consider a floating point adder. This pipeline
accepts as input two normalized floating point numbers of the form: A = a x 2p B = b x 2q Here a
and b are 2's complement fractions in the range 0.5<f<1.0. p
and q are corresponding base 2 exponents. The normalized sum is to be
computed. Four stages can be identified for this pipeline:
static pipelining -
it is composition of stages one after another means that the output of one
stage is become input to the next stage we also called it linear pipelining.
it is further divided in two types synchronous and asynchronous.
RGPV JUN 13(7) A pipeline unit with
a fixed and dedicated function, such as the floating-point adder, is called
unifuctional . A multifunctional pipe may perform different functions, either
at different subsets of stages in the pipeline. A dynamic pipeline processor
permits several functional configurations to exist simultaneously. In this
sense, a dynamic pipeline must be multifunctional Texas Instruments’
Advanced Scientific Computer (TI-ASC) was the first vector processor that was
installed with multifunction pipelines in its arithmetic processors. The ASC
arithmetic pipeline consists of eight stages, as illustrated in figure. All
the interconnection routes among the eight stages are shown. This pipeline
can perform either fixed-point or floating-point arithmetic functions
and many logical-shifting operations over scaler and vector operands of
length 16, 32, or 64 bits. Different
arithmetic-logic instructions are allowed to use different connecting paths
through the pipeline. Figure shows four interconnection patterns of the ASC
pipeline for the evaluation of the functions: fixed-point add, fixed-point
multiply, and floating-point add, floating-point multiply. It’s not difficult
to see that the receiver and output stages are used by all instructions. The
multiply stage performs multiplication. The multiply stage produces two results,
called pseudo sum and pseudo carry, which are sent to
the accumulator stage or the add stage to produce the desired product.The
exponent subtract stage determines the exponent difference and sends this shift count to
the align stage to align fractions for floating-point add or subtract
instructions. All right shift operations are also implemented in this align
stage. The normalize stage does the floating-point normalization, all
leftshift operations, and conversions between fixed-point and floating-point
operands. Array pipelines are
two-dimensional pipelines with multiple data-flow streams for high-level
arithmetic computations, such as matrix multiplication, inversion, and L-U
decomposition. The pipeline is usually constructed with a cellular array of
arithmetic units. The cellular array is usually regularly structured and
suitable for microprocessor implementation.
Superscalar processing has its origins in the Cray-designed CDC
supercomputers, in which multiple functional units are kept busy by multiple
instructions. The CDC machines could pack as many as 4 instructions in a word
at once, and these were fetched together and dispatched via a pipeline. Given
the technology of the time, this configuration was fast enough to keep the
functional units busy without outpacing the instruction memory. Current technology has enabled, and at the same time created the need
to issue instructions in parallel. As execution pipelines have approached the
limits of speed, parallel execution has been required to improve performance.
As this requires greater fetch rates from memory, which hasn't accelerated
comparably, it has become necessary to fetch instructions in parallel --
fetching serially and pipelining their dispatch can no longer keep multiple
functional units busy. At the same time, the movement of the L1 instruction
cache onto the chip has permitted designers to fetch a cache line in parallel
with little cost. In some cases superscalar machines still employ a single
fetch-decode-dispatch pipe that drives all of the units. For example, the
UltraSPARC splits execution after the third stage of a unified pipeline.
However, it is becoming more common to have multiple fetch-decode-dispatch
pipes feeding the functional units. The choice of approach depends on tradeoffs of the average execute
time vs. the speed with which instructions can be issued. For example, if
execution averages several cycles, and the number of functional units is
small, then a single pipe may be able to keep the units utilized. When the
number of functional units grows large and/or their execution time approaches
the issue time, then multiple issue pipes may be necessary. Having multiple issue pipes requires being able to fetch instructions for that many pipes at once • inter-pipeline interlocking • reordering of instructions for multiple interlocked pipelines • multiple write-back stages • multiport D-cache and/or register file, and/or functionally split
register file Reordering may be either static (compiler) or dynamic (using hardware
lookahead). It can be difficult to combine the two approaches because the
compiler may not be able to predict the actions of the hardware reordering
mechanism. Superscalar operation is limited by the number of independent
operations that can be extracted from an instruction stream. It has been
shown in early studies on simpler processor models, that this is limited,
mostly by branches, to a small number (<10, typically about 4). More
recent work has shown that, with speculative execution and aggressive branch
prediction, higher levels may be achievable. On certain highly regular codes,
the level of parallelism may be quite high (around 50). Of course, such
highly regular codes are just as amenable to other forms of parallel
processing that can be employed more directly, and are also the exception
rather than the rule. Current thinking is that about 6-way instruction level
parallelism for a typical program mix may be the natural limit, with 4-way
being likely for integer codes. Potential ILP may be three times this, but it
will be very difficult to exploit even a majority of this parallelism.
Nonetheless, obtaining a factor of 4 to 6 boost in performance is quite
significant, especially as processor speeds approach their limits. Going beyond a single instruction stream and allowing multiple tasks
(or threads) to operate at the same time can enable greater system
throughput. Because these are naturally independent at the fine-grained
level, we can select instructions from different streams to fill pipeline
slots that would otherwise go vacant in the case of issuing from a single
thread. In turn, this makes it useful to add more functional units.
Superpipelining
improves the performance by decomposing the long latency stages
(such as memory access stages) of a pipeline into several shorter stages, thereby
possibly increasing the number of instructions running in parallel at each cycle.
superpipelining improves the
performance by dividing the long latency stages (such as the memory access stages)
of a pipeline into several shorter stages, thereby reducing the clock rate of
the pipeline. Superpipelining
simply allows a processor to improve its performance by running the
pipeline at a higher clock rate. The higher clock rate is achieved by
identifying the
pipeline stages that determine the clock cycle (in other words, the most time consuming
stages) and decomposing them into smaller stages. Superpipelining
is the simplest technique of the three. It does not require additional
hardware (such as functional units and fetch units) that a superscalar architecture
does. It also does not require the complex controls (no multiple issue control
or need to keep track of the instructions issued). Finally, it should be noted that
superpipelining does not need the advanced compiler technologies required by the
VLIW model. Super pipelining Super Pipelining execution Superpipelining
also brings a number of major side effects. As the number of stages
is increased, so is the number of forwarding paths (stages) and the delay
(stall cycles)
caused by branches and loads. The combination of the above two factors has strong
adverse a®ects on the performance of the processor since it increases the CPI (therefore,
techniques to improve CPI,
such as hardware-based pipeline schedul- ing,
branch prediction, multiple issue, and compiler-assisted parallelism
exploiting techniques
have been developed). These topics will be discussed in the context of superscalar
and VLIW. However, it should be noted that when the above techniques are
considered, superpipelining can improve CPI as well.) Three
processor architectures can show possible implementations of superpipelining. In
those examples, we focus on how superpipelining has helped improve the perfor mance
of each architecture and show the design techniques to exploit the benefits of
using superpipelining. MIPS R4000 (Register File write) stages. The eight
stages of R4000 are listed below:
The ARM11 Processor Fe1
- Instruction Fetch, First Half, Branch Prediction Fe2
- Instruction Fetch, Second Half, Branch Prediction De
- Instruction Decode Iss
- Register read and instruction issue Sh
- Shifter stage ALU - Main integer operation calculation Sat
- Pipeline stage to enable saturation of integer results Reference
{Advance computer architecture ,KAI HWANG} |