11,684 views
Collition Vector : 1011010

MAL for the above Collition Vector is _____
Please also tell me how to calculate efficiency and throughtput

[ 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

by

Thanks ! I got my mistake . my ordering of the collision vector was wrong.

but suppose we have 8 bit collision vector in which we have 2,3,4,6 as the forbidden latencies and 1,5,7,8 as the permissible latencies then the collision vector will be 00101110 . in this case Cm(the first bit is not 1).

@Pranavpurkar It will be 101110. Remember we write upto the last Forbidden Latency. Because rest are not required.

Thanks brother!