Mumbai University > Computer Engineering > Sem 8 > parallel and distributed systems

Marks: 5M

Basic task of Scheduler: Is Controlling the sequence of tasks presented to a pipeline for execution is extremely important for maximizing its utilization.

The scheduler also maintains the reservation table, forbidden list for scheduling the instruction in pipeline.

Definition

Latency:

a) The delay, or number of time units separating two initiations, is called latency.

b) A collision will occur if two pieces of input data are initiated with a latency equal to the distance between two X's in a reservation table. For example, the table in Figure below has two X's with a distance of 1 in the second row. Therefore, if a second piece of data is passed to the pipeline one time unit after first, a collision will occur in stage 2.

Initiation Rate:

This concept is used for software pipe-lining where it is defined as to overlap the execution of instructions from multiple iterations of a loop to keep the pipeline busy without stall

The objective is to sustain a high initiation rate- Initiation of a subsequent iteration may start even before the previous iteration is complete

Stage Utilization:

It is defined as that Real machines sometimes have function units with structural hazards, that is function units which reuse one or more stages of their pipelines during execution of an instruction.

But stage utilization leads to create a structural hazard problem in pipelining where one or more instruction demanding for the same resources.

Forbidden latency:

It is defined as the forbidden list F is simply a list of integers corresponding to these prohibited latencies.

Every reservation table with two or more X's in any given row has one or more forbidden latencies, which, if not prohibited, would allow two data to collide or arrive at the same stage of the pipeline at the same time.