Speculative tomasulo, branch in the issue phase

I had confusions on SPeculative tomasulo; now, which I know the correct answer for.

1) If one branch is in issue phase in cycle (C) should we suspend other later instruction from issuing in the cycle cycle ?

Ans:Yes. So, if there is a branch instruction in a cycle (say 10) issue no other later instruction in the 10th cycle.

2) When a reservation station becomes  free?

Ans: It becomes free after writing the result to CDB. Not after issuing the instruction in the functional unit.

How Tomasulo (non Speculative) avoid WAW hazard

In non speculative Tomasulo, for each register, we designate how the corresponding register will get its value from.

i instruction : R1 = R3 + R4

i+1   instrction : R1  = R5 + R6

when i th instruction is in progress,  R1 will mark corresponding reservation station for this instruction who will provide value for R1.

Similarly, when (i+1)th instruction, is in progress, it will later update that value of R1 will come from the reservation station associated with (i+1) instruction.

Thus the value of (i+1) instruction will prevail avoiding WAW hazard.

How Speculative Tomasulo Prevent WAW,WAR,RAW,RAR hazards?

In speculative Tomasulo, the ReOrderBuffer (ROB), contains the instruction before the result of an instruction is updated in the register file. So, In oder to exist any hazard, the hazard should be in the ROB.

WAW Hazard:

Assume,

Instruction i : R1 = R1 + R2

Instruction i+1 : R1 = R3- R4.

Now, even though, if (i+1) instruction is finished earlier before ith instruction, they are kept in the ROB first before they are commited. Now, the commit becomes in order ( first ith instruction and then (i+1) th instruction ). So, it does not matter which instruction first updated the ROB entry. This is the way, WAW hazard is removed.

WAR:

Assume,

ith instruction: R1 = R2 + R3

(i+1)th instruction: R2 = R5 + R6

In order to avoid WAR hazard, R2 must be read first by Instruction i before (i+1) instruction overwrite it.

It happens in Tomasulo, because, instruction is issued in Order and when an instruction is issued, the reservation station tracks down how it can get its operand from. So, As i is issued first, R2 will always be read before i+1 overwrite it.

RAW: If there is a dependency on a register which is not yet completed, the reservation station keeps tract of which other Reservation station is going to produce it. So, it does not make RAW Hazard.

RAR: Not a hazard anyway in Speculative tomasulo.

Sort n elements, each of which is red, white, or blue on the color in the order Red, White, Blue.

Skiena : 4-18. Suppose an array A consists of n elements, each of which is red, white, or blue. We seek to sort the elements so that all the reds come before all the whites, which come before all the bluesThe only operation permitted on the keys are

1. Examine(A,i) — report the color of the ith element of A.
2. Swap(A,i,j) — swap the ith element of A with the jth element.

Find a correct and efficient algorithm for red-white-blue sorting. There is a linear-time solution. This is also known as the Dutch national flag problem. The simplest linear time solution performs two passes of the partition operation from Quicksort. The first pass treats the red and white elements as indistinguishable, and separates them from the blue. The second pass is just separates the elements within the red/white sub-array.

Solution:

i1 <—-Red —> i2      j1 <——–White ——-> j2     k1 <——-Blue ——-> k2          NEXT

In some already sorted list, i1 is the index of first red, i2 = last red index, j1 = first white index, j2 = last white index,  k1=first blue and k2 = last blue.

now, the algorithm would be

if ( NEXT == Blue)  {NEXT ++; k2++};

if (NEXT == White) { swap(Elements[k1],Elements[NEXT];j2++;k1++;k2++;}

if ( NEXT == Red) { swap(Elements[k1],Elements[NEXT]); swap(Elements[k1],Elements[j1]); i2++;j1++;j2++;k1++;k2++}

for initial value assume all values i1=i2=j1=j2=k1=k2 = 0;

Bingo, this is O(n) complexity algorithm.

[3] Give an efficient algorithm to rearrange an array of n keys so that all the negative keys precede all the nonnegative keys.

Give an efficient algorithm to rearrange an array of n keys so that all the
negative keys precede all the nonnegative keys.

 

Solution:

1. Scan through the list from left to right through i .

2. Point the first positive number in the list say it  j (initially -1).

3. When List[i] is a negative number and j >-1, swap list[i] & list [j] and increment j by 1

4. When List[i] is a negative number and j == -1, we haven’t get any positive number and go through scanning.

 

Complexity : O(n)

Determine whether there exists a path in graph G of length L.

Determine whether there exists a path in graph G of length L.

Solution:

If the graph has a cycle, then the graph has a path of any length L.

If the graph does not have a cycle , then we are finding a simple path of length L.

We will use DFS with some modification to find simple path of length L.

For this with every node n, we will maintain a value  named maxPath (other than start_time and end_time) which determines path of Maximum value.

We will initialize each nodes of G with maxPath = 0;

So, the steps to find simple path of Lengh L  is :

1. Run modified DFS-visit()

2. check each node for the maxPath value.

DFS-visit(u) {

time = time + 1

u.start = time;

for each v <em>belongs-to</em> adj[u]

if ( v.color = WHITE ) {

DFS-visit(v)

if (u.maxPath < v.maxPath + 1 )

u.maxPath = v.maxPath + 1;

}

u.endtime = time + 1;

u.color = BLACK

Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3

Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3.

Give o(v^3) algorithm for it.

Solution:

step 1: Run DFS on the given as  it is.

step 2: In the DFS-visit of vertice ( say u ) run a modified BFS ( say BFS2).

The algorithm for BFS2 is as following:

BFS2(u) {

foreach v1 belongs to adj[u]

foreach v2 belongs to [adj[v1] - u] { // because we know u must be adjacent of v1. that's why we will not let u create massacre here.

if ( v2 and u are adjacent to each other )

Report ( u,v1,v2) as a cycle or length 3 .

}

}

This problem appears in algorithm design manual by skiena as following

5-17. Consider the problem of determining whether a given undirected graph G = (V,E) contains a triangleor cycle of length 3.

1. Give an O( | V | ³) to find a triangle if one exists.

The complexity id v3 because for each vertices BFS2 will run for with v^2 complexity.

Find the node of a graph from which all nodes are reachable

If we have a graph G=(V,E) and all vertices are reachable from vertex s, then our problem is to find such a vertex s.

Solution: Solution to this problem is in DFS of the graph. Before going to the algorithm, we need to consider the following properties of DFS.

i) DFS tree produced by the DFS algorithm is always a tree ( it means that it must be acyclic, whatever the graph is)

Here is the algorithm that reports if a given graph has a vertex from which all other vertex are reachable.

DFS-Visit(u)

time = time + 1;

u.start_time = time;

child= 0;

Color = GRAY;

for each v belongs to adj[u] {

if ( v.color == WHITE ) {

DFS-visit(v);

child = (v.finish_time - v.start_time + 1 ) / 2;

}

}

u.finish_time = time + 1;

u.color = BLACK;

u.child = child + 1; // child include number of nodes this node visits including itself.

if ( u.child == |V| )

## Report u as source vertex ##

In fact, this is the solution for the following problem
5-26. A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices G can be reached by a directed path from v.

1. Give an O(n + m) algorithm to test whether a given vertex v is a mother of G, where n = | V | and m = | E | .
2. Give an O(n + m) algorithm to test whether graph G contains a mother vertex.

Sorting of Pairwise sum

In this problem, we have two list X & Y. we have to take any element x of X and y of Y to make a pair. The problem is to sort the sum of the pair in the ascending order.

if X = {100,110,130} Y = {50,75,125} the sorted pair sum would be

150, 160,175,180,185,205,225.

The code below does this :

class pairwisesum {
public static void main(String [] s) {

int [] X = {100,110,130};
int [] Y = {50,75,125};
int [] index = {0,0,0};
int sum ,next;
for ( int k=0; k<X.length*Y.length;  k++) {
sum = 99999;
next = 0;

for (int i=0; i<X.length; i++) {
//System.out.println(index[i]);
if ( X[i] + Y[index[i]] < sum ){
sum = X[i] + Y[index[i]];
next = i;
}

}
index[next] ++;
System.out.println( “” + sum + “::” + next );
}

}

}

 

ancestor reporting in a tree

S Dasgupta- 3.18 :You are given a binary tree T = (V;E) (in adjacency list format), along with a designated root  node r belongs to V . Recall that u is said to be an ancestor of v in the rooted tree, if the path from r to v in T passes through u. You wish to preprocess the tree so that queries of the form “is u an ancestor of v?” can be answered in constant time. The preprocessing itself should take linear time. How can this be done?

Solution:

Let Ancestor[n][n] be an two dimentional array. If there is a query “is u an ancestor of v” our program will answer “yes” if A[u][v] is true otherwise it will report “no”.

Algorithm:

DFS-visit ( u , list){

Process_ancestor();

time = time + 1

u.color = GRAY;

foreach v belongs to adj[u] {

append(list,v);

DFS-visit (v,list);

remove_last_element(); // which will remove v from the end of the list.

}

}

Process_parent ( list ) {

if ( list.size > 1 ) {

for ( i=1; i<=list.size; i++) {

for ( j=i+1; j<=list.size; j++)

ancestor[list[i]][list[j]] = true; // list[i] is a ancestor of list[j]

}

}

}

Process_query( u,v) {   // This will answer our question.

if ( ancestor[u][v] == true ) return yes;

return false;

}