[ 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