NON-LINEAR PIPELINE PROCESSORS/DYNAMIC PIPELINE

A dynamic pipeline can be reconfigured to perform variable functions at different times. It allows feed-forward and feedback connections in addition to the streamline connection.

  Difference Between Linear and Non-Linear pipeline:

Linear Pipeline	Non-Linear Pipeline
Linear pipeline are static pipeline because they are used to perform fixed functions.	Non-Linear pipeline are dynamic pipeline because they can be reconfigured to perform variable functions at different times.
Linear pipeline allows only streamline connections.	Non-Linear pipeline allows feed-forward and feedback connections in addition to the streamline connection.
It is relatively easy to partition a given function into a sequence of linearly ordered sub functions.	Function partitioning is relatively difficult because the pipeline stages are interconnected with loops in addition to streamline connections.
The Output of the pipeline is produced from the last stage.	The Output of the pipeline is not necessarily produced from the last stage.
The reservation table is trivial in the sense that data flows in linear streamline.	The reservation table is non-trivial in the sense that there is no linear streamline for data flows.
Static pipelining is specified by single Reservation table.	Dynamic pipelining is specified by more than one Reservation table.
All initiations to a static pipeline use the same reservation table.	A dynamic pipeline may allow different initiations to follow a mix of reservation tables.

 

A Three stage Pipeline

  Reservation Table: Displays the time space flow of data through the pipeline for one function evaluation.

Time

                                                          1      2    3     4     5     6    7     8

X					X		X
	X		X
		X		X		X

S1

            Stage         S2

S3

Reservation function for a function x                                  

 Latency: The number of time units (clock cycles) between two initiations of a pipeline is the latency between them. Latency values must be non-negative integers.

  Collision: When two or more initiations are done at same pipeline stage at the same time will cause a collision. A collision implies resource conflicts between two initiations in the pipeline, so it should be avoided.

  Forbidden and Permissible Latency: Latencies that cause collisions are called forbidden latencies. (E.g. in above reservation table 2, 4, 5 and 7 are forbidden latencies).

Latencies that do not cause any collision are called permissible latencies. (E.g. in above reservation table 1, 3 and 6 are permissible latencies).

  Latency Sequence and Latency Cycle: A Latency Sequence is a sequence of permissible non-forbidden latencies between successive task initiations.

A Latency cycle is a latency sequence which repeats the same subsequence (cycle) indefinitely.

The Average Latency of a latency cycle is obtained by dividing the sum of all latencies by the number of latencies along the cycle.

The latency cycle (1, 8) has an average latency of (1+8)/2=4.5.

A Constant Cycle is a latency cycle which contains only one latency value. (E.g. Cycles (3) and (6) both are constant cycle).

  Collision Vector: The combined set of permissible and forbidden latencies can be easily displayed by a collision vector, which is an m-bit (m<=n-1 in a n column reservation table) binary vector C=(C_m­C_m-1….C₂C₁). The value of C_i=1 if latency I causes a collision and C_i=0 if latency i is permissible. (E.g. C_x= (1011010)).

  State Diagram: Specifies the permissible state transitions among successive initiations based on the collision vector.

 

The minimum latency edges in the state diagram are marked with asterisk.

 

 Simple Cycle, Greedy Cycle and MAL: A Simple Cycle is a latency cycle in which each state appears only once. In above state diagram only (3), (6), (8), (1, 8), (3, 8), and (6, 8) are simple cycles. The cycle(1, 8, 6, 8) is not simple as it travels twice through state (1011010).

A Greedy Cycle is a simple cycle whose edges are all made with minimum latencies from their respective starting states. The cycle (1, 8) and (3) are greedy cycles.

MAL (Minimum Average Latency) is the minimum average latency obtained from the greedy cycle. In greedy cycles (1, 8) and (3), the cycle (3) leads to MAL value 3.