retagged by
14,707 views

1 Answer

Best answer
13 votes
13 votes

[ need @arjun Sir to verify this contents   ]

Collision Vector   CV = $C_{m}C_{m-1} \cdots C_{3}C_{2}C_{1}$ Where
if $C_{i} = 0 \Rightarrow$ Permissible Latency
if $C_{i} = 1 \Rightarrow$ Forbidden Latency

Given CV : 1011010

Permissible Latency = 1,3,6
Forbidden Latency = 2,4,5,7

Step 1 : Constructing State Diagram

How to draw the state diagram ?

Initial State : 1011010

Step 1.a :   Right Shift Inital State with 'p' - permissible latency times

For p=1

Right Shift '1' time intical CV : 1011010 $\Rightarrow$ 0101101 .

Step 1.b  : Perform OR operation with Initial CV with Right Shifted Value

Initial CV $\Rightarrow$ 1011010   OR
'1' R-shift$\Rightarrow$ 0101101
______________________________________
Next State$\Rightarrow$  1111111

Step 1.c : Perform step 1.a and  step 1.b As many times untill same state repeats

New CV : 1111111
 
Step 1.a
   Right Shift '1' Time :  0111111
Step1.b   
   1111111 OR 0111111 $\Rightarrow$ 1111111
FOR p=3

Initial State : 1011010 OR '3' R-shift  0001011 $\Rightarrow$ 1011011 ( next state)
Initial State : 1011011 OR '3' R-shift 0001011 $\Rightarrow$101011 ( state Repeating )
For p=6
Initial State : 1011010 OR '6' R-shift  0000001 $\Rightarrow$ 1011011 ( next state)
Initial State : 1011011 OR '6' R-shift 0000001 $\Rightarrow$101011 ( state Repeating )

This proceure can be simplified in the following diagram . 



When Number of Shifts is 'm+1' or grater all transitions are returned back to inital state we denote this as (m+1)+ Here m=7 , Therfore 8+

Step 2 :  Determining MAL

Step 2.a : Find the number Of Simple Cycle

Formally 
" Simple Cycle are those latency cycles in which each state appears only once per each iteration of the cycle "
Informally
There should be a cycle and each state should be visited exactly once 

Here 3,6,8, (1,8) , (3,8) , (6,8)  are simple cycles

Step 2.b : Find the Greedy Cycles

Formally
A single cycle is a greedy cycle if each latency contained in the cycle is the minimal latency (outgoing arc) from a state in the cycle.
Procedure to determine the greedy cycles
1. From each of the state diagram, one chooses the arc with the smallest latency label unit; a closed simple cycle can formed.
2. The average latency of any greedy cycle is no greater than the number of latencies in the forbidden set, which equals the number of 1’s in the initial collision vector.
3. The average latency of any greedy cycle is always lower-bounded by the MAL in the collision vector
Informally

 $\triangleright$ Edges are made with min Latency 
$\triangleright$ Average Latency is lower than other simple cycles

Here , Among all the Simple cycles Avg latency is  minimum for
cycle 3, (1,8) 
$\frac{1+8}{2} = 4.5$

Step 2.c : Determining MAL

MAL is the minimum of the avegrage latency cycles ,
Here it is 3

MAL is 3

MAL edges are marked with *




Source : Advanced Computer Architecture , KAI HWANG
Good Read : GATE 2015 SET 3 Question on MAL

edited by

Related questions

0 votes
0 votes
1 answer
4
shima abdullah asked Jun 27, 2022
811 views
if an unpipelined processor with a cycle time of 25 ns is evenly divided into 5 pipeline stages using pipeline latches with 1-ns latency,what is the total latency of the ...