Algorithms


                Yes.. It has happened again. Whoever said it happens only once in a lifetime was definitely lying. For a reader who has never been in the hearing distance of a Spanish speaker the title translates to “My Second love”. It is my feeble attempt to keep in touch with whatever little Spanish I have learnt so far.

So after heaps I wasn’t completely closed to the possibility that I will come along some idea that would leave me enamoured. Something so fundamentally beautiful that would raise the bar of what I consider an ingenious thought. And so the day came when in my Computer Architecture class at University of Michigan I was taught –

    “Register Renaming”

Lets dive a little into what is this idea all about.  Modern day processors are out of order and pipelined. The first adjective essentially means that a processor, irrespective of what order the instructions are fed to it, will execute them in the order it likes to gain maximum performance and the programmer shall still see the results that he/she expects. The second adjective  simply means that the logic for each instruction is broken down into smaller pieces which can be termed as different stages in the execution.This allows us to start an  instruction before the preceding one completes as multiple instructions can be in different stages at the same time.  If the longest stage of our execution pipeline took x time units then the best possible throughput we could get is at least one instruction every x time units.

But there are reasons why we don’t quiet get this performance. One of these is data hazards.

Consider this code snippet :

        Instruction 1    : MULT R0,R0,R1        –> R1    = R0 * R0
        Instruction 2    : ADD R1,R2,R3        –> R3    = R1 + R2
        Instruction 3    : MULT R5,R6,R3        –> R3    = R5 * R6
        Instruction 4    : ADD R7,R8,R6        –> R6    = R7 + R8

Now instruction 2 cannot begin execution till instruction 1 completes because it needs the value of register R1 which instruction 1 will compute. This is RAW (Read after Write) dependency. Also, instruction 2 and 3 write to the same register R3 and even though the processor could merrily execute them out of order given they don’t effect each other we need to make sure that it is instruction 3 that writes last to register R3. This is WAW dependency (Write after Write). Finally we need to  make sure that instruction 3 reads the value of R6 before we let instruction 4 write to it. This is WAR(Write after Read) dependency. Given all this complications, our dear processor might as well execute them in order!!

But this is not what happens in real processors because of the amazing idea of register renaming! If we really think about it, the only true dependency is RAW.  By true what I mean is for the program to be correct, it is essential that the value computed by instruction 1 is what should actually be used by instruction 2. But  the other dependencies are just name dependencies.

Consider our processor had infinite registers to play around with. But to the programmers we expose only a certain set of registers. These two groups are  called : physical registers and architectural registers respectively. It is clear that ,
physical registers >= architectural registers

What register renaming does is :
–Every time we encounter an instruction we give it a new physical register to write to. Essentially rename an architectural location to new physical register.
–We maintain and update the mapping of architecture register -> physical register accordingly.

Now lets assume we have 14 physical registers(P0 to P13) and 10 architectural registers (R0 to R9). Consider that the intial mapping is
R0 – P0, R1 – P1 and so on.
In this sunlight of register renaming (sunlight: a phenomenon which was omnipresent in my life which is now kindof extinct) our code snippet will now be:

        Instruction 1    : MULT P0,P0,P10    –> mapping R1 -> P1 changes to R1 -> P10    
        Instruction 2    : ADD P10,P2,P11    –> mapping R3 -> P3 changes to R3 -> P11, notice that P10 is referred here instead of P1 for R1    
        Instruction 3    : MULT P5,P6,P12    –> mapping R3 -> P11 changes to R3 -> P12
        Instruction 4    : ADD P7,P8,P13        –> mapping R6 -> P6 changes to R6 -> P13

So what we achieved by this is, our processor can now execute instruction 2, 3 and 4 in any order as :
– WAW hazard is removed as both instruction 1 and instruction 2 have different destination registers.
– WAR hazard is removed as instruction 3 will read the right value whether instruction 4 executes before it or not.

      That is the amazing concept of register renaming!! If you want to dig deeper here’s a well written paper : Register Renaming Paper

Advertisements

In our final year of engineering we are given the liberty to choose from a set of subjects as to be our “elective”. Now elective is a choice… It’s a choice you make based on what your interests are and you are “expected” to be interested in something which the college offers you. It is an altogether different issue that college always offers something boring and students are always never sure of what they are interested in and hence usually prefer to take a course wherein teachers don’t turn up.

Entering into my final semester of engineering I was sure of what my interests are but I was also sure college authorities wouldn’t have anything to offer that would interest me. But scrolling through the list put up at department notice board, I found a new offering. “Computational Biology”. The syllabus seemed interesting (it had algorithms). Most importantly it was going to be taught by people from the industry. I really appreciate people from industry who volunteer for teaching assignments. Taking time out of their busy schedule to interact with students is indeed commendable. Besides I have always being in favor of continuous interaction between academia and industry. Producers and consumers should always be in sync with each other. So I signed in for the course.

And so in my final semester of engineering I was admitted to a school.I experienced things which I last saw/felt in high school.

  • All the course instructors always come on time

  • Basically they never miss any of their allotted slots i.e. lectures take place as per schedule.

  • They are so enthusiastic about giving assignments and making us scratch our brains.

  • They actually read our answer sheets (they did. Believe me)

Of the many algorithms that we studied the ones which I found really interesting were pair-wise sequence alignment algorithms. One of the basic units in biology is DNA which is a sequence of 4 letters A, C, T, G. DNA defines us. It contains the code which makes us what we are. Now comparing DNA sequences from two different organisms is really helpful in deciding the relationship between organisms. It helps biologists conclude about any common ancestry amongst them to name just one.

Pair-wise sequence alignment can basically be of two types. The ones aiming at global alignment and ones aiming at local alignment. Calculating a global alignment is a form of global optimization that forces the alignment to span the entire length of all query sequences. An example of this is Needleman–Wunsch algorithm. By contrast to global alignments, local alignments identify regions of similarity within long sequences that are often widely divergent overall. Let’s consider Smith- Waterman algorithm which aims to align two sequences with emphasis on local alignment. Here are the basic steps in the algorithm along with an example.

Consider two DNA sequences: 1: ACTGAAGG

2: AATGGACTT

1) Decide upon match, mismatch scores (similarity measure, s (a, b)) and gap penalty.

Let us assume the match score to be 1. What we mean by this is,

s (A, A) = s (C, C) = s (G, G) = s (T, T) = 1, where s is similarity measure.

Let mismatch score to be – (1/3). What we mean by this is s (A, C) = – (1/3).

And gap penalty = 1 + k/3, where k = extent of gap. So for gap length =1, penalty = 1.3, for gap length = 2, penalty = 1.7 and so on.

Here I have decided these scores randomly. But these scores are usually decided keeping biological aspects into consideration. What we are technically doing by deciding these scores is deciding what our distance matrix is. In this example my distance matrix is:

A

T

C

G

A

1

-0.3

-0.3

-0.3

T

-0.3

1

-0.3

-0.3

C

-0.3

-0.3

1

-0.3

G

-0.3

-0.3

-0.3

1

2) Construct matrix.

Now in sequence alignment algorithms we create a matrix using the distance matrix. We write one sequence along one axes and other sequence along other axes. The rule in SW algorithm to fill up the matrix is as follows:

Set Hi, 0 = H0, j = 0 for 1 ≤ i n and 1 ≤ j m, where n and m are lengths of the two sequences under consideration. Then,

Hi, j = max { { Hi-1, j-1 + s( ai , bj )} , max1 ≤ k ≤ i {Hi-k, j – Wk}, max1 ≤ k ≤ j {Hi, j-k – Wk}, 0}. Here W is the gap penalty and the k is the extent of gap. Initially the matrix looks like (i.e. putting 0 in row 0 and column 0):

A

C

T

G

A

A

G

G

0

0

0

0

0

0

0

0

0

A

0

?

A

0

T

0

G

0

G

0

A

0

C

0

T

0

T

0

Now let’s fill up the matrix one element at the time from top left hand corner to bottom right hand corner (always moving from left to right) using the equation given above. Consider the cell containing ‘?’. The corresponding letter from sequence 1 is ‘A’ and that from sequence 2 is ‘A’. Hence substituting values in our equation we have,

H = max {{0 + s (A, A)}, {0-1.3}, {0-1.3}, 0} = max {1, -1.3, -1.3, 0} = 1.

Similarly we can fill up other positions in matrix. Here’s one more example: Consider row 4 and column 6. The letter in sequence1 is ‘A’ and that in sequence2 is ‘G’. So we have,

H4, 6 = max { {H3, 5 + s(A, G)}, max { (H4, 5 – 1.3) , (H4,4 – 1.7), (H4,3 ­ – 2)}, max {(H3, 6 – 1.3), (H2,6 – 1.7), (H1,6) – 2}, 0 }

= max {-0.3, max {0.1, 1,-1.6}, max {-0.6, 0.3, -1}, 0} = max {-0.3, 1, 0.3} = 1

Thus our final matrix is:

A

C

T

G

A

A

G

G

0

0

0

0

0

0

0

0

0

A

0

1

0

0

0

1

1

0

0

A

0

1

0.7

0

0

1

2

0.7

0.3

T

0

0

0.7

1.7

0.4

0

0.7

1.7

0.4

G

0

0

0

0.4

2.7

1.4

1

1.7

2.7

G

0

0

0

0

1.4

2.4

1.1

2

2.7

A

0

1

0

0

1

2.4

3.4

2.1

1.7

C

0

0

2

0.7

0.3

1.1

2.1

3.1

1.8

T

0

0

0.7

3

1.7

0.4

1.7

1.8

2.8

T

0

0

0.3

1.7

2.7

1.4

0.4

1.4

1.5

3) Trace- back

The next step is to trace a path in this matrix which will give us the optimal local alignment. The steps here are:

a) Locate the maximum element and start the trace from that cell.

b) Now check the diagonal (i-1, j-1), immediate left (i , j-1) and immediate top(i-1, j). Move to the maximum of these 3 and choose diagonal element in case of a tie.

c) Stop the trace when you reach a stage where a diagonal element is 0.

The trace path in the matrix is shown with bold numbers.

A

C

T

G

A

A

G

G

0

0

0

0

0

0

0

0

0

A

0

1

0

0

0

1

1

0

0

A

0

1

0.7

0

0

1

2

0.7

0.3

T

0

0

0.7

1.7

0.4

0

0.7

1.7

0.4

G

0

0

0

0.4

2.7

1.4

1

1.7

2.7

G

0

0

0

0

1.4

2.4

1.1

2

2.7

A

0

1

0

0

1

2.4

3.4

2.1

1.7

C

0

0

2

0.7

0.3

1.1

2.1

3.1

1.8

T

0

0

0.7

3

1.7

0.4

1.7

1.8

2.8

T

0

0

0.3

1.7

2.7

1.4

0.4

1.4

1.5

4) Alignment

This is the last step. Using the trace- back we have our maximum similar segment as:

–ACTGAA–

–AATGGA–

Our alignment has 4 matches, 2 mismatches and no gaps.

So this was about Smith – Waterman Algorithm. Thanks to my faculty and Swati (we usually end up fighting trying to figure out how things work before happily coming to a consensus) I hope I have got things right. Also here’s the link to the original paper by Smith which is very well written (and I don’t say that about every paper I go through) : http://www-hto.usc.edu/papers/msw_papers/msw-040.pdf.

I referred this paper and it has NW algorithm explained as well.


The time I saw him I was bound to fall in love. Such an amazing behavior!! Such a consistent performance!! Unbeatable, I told Swati. She was still scrutinizing him (No, he is not an athlete).This post is about my very first love.

I am a computer science engineer (There you raise your eyebrows.) I mean I am positive I will be one in about 7 months. I don’t believe in fuzzy logic (as of now.. Life has taught me ‘never say never!’). I don’t think I can have a crush. Either I am in love, or I am not. And yes. This was for sure love.

He is a Heap. Oh you never heard of him? Or if you did you think he is not friendly? Oh no. He is the most friendly data structure around. Arrays, link-list no one comes even close to performance that Heap offers. So wanna know more about him? Read on.

Heap data structure is an array object that can be viewed as a nearly complete binary tree. (The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point) If heap is an array object then what makes it different?? There is an interesting property that differentiates a heap from an array and that it is: key stored in parent node should be less than the key stored in any of its children. This is an example of a min-heap. Heaps are two kinds, min-heaps and max-heap. Max-heap being one in which the parent has key value greater than the any of its children. Here’s an example:

Max-Heap

a)Max heap viewed as a binary tree b) Max heap in its array representation

(Each node with two children)

Any data structure is judged by the asymptotic complexity involved in various operations that we perform on it, which includes create, search, insert, delete. Let’s analyze each of these in turn.

Create:

Consider that we are building a max-heap (binary). Our input is an array with arbitrary elements and we ought to make sure that the ‘heap property’ is valid i.e. each parent node holds a key greater than any of its children (in this case 2 children). Now if we observe in the diagram above parent nodes / internal nodes begin from position 5. Given n nodes/elements, internal nodes begin at array position n/2. (Assuming array indexes start from 1. If we take this to be 0, this will change to (n/2-1)).

Now to create heap all we got to do is start scanning the array from the last internal node (index =n/2) to index 1 and check if ‘heap property is satisfied or not. Anytime we find that the heap property is violated we ought to swap the nodes. Here’s a pictorial representation of this procedure:

Creation of max-heap

A: initial array a) 16 compared with 7, no swap. b) 2 compared with 14 and 8, the larger node 14 is swapped with 2. This ensures heap property is not violated as 14 >8. c) 3 and 10 are swapped. d) 1 and 16 swapped e) 4 and 16 swapped f) the final max-heap.

The asymptotic complexity of building heap is O (n).

Insert:

To insert an element into the heap just place it in the next empty array location and let it bubble up the tree till heap property is not satisfied. Since height of heap (in binary tree representation) is O (log n), complexity of insert is O (log n).

Delete:

Deleting a leaf from heap is straightforward. When it comes to deleting an internal node, replace it with the larger of its two children and continue this down the tree. Again since height of heap (represented as binary tree) is O (log n), complexity of delete is O(log n).

Search:

Searching the heap is O (n) i.e. you can search a heap in linear time as you do in arrays or link-list.

Heaps have huge applications in numerous algorithms cause of their property to give the minimum /maximum of a set of elements in constant amount of time (O(1)).If you have observed carefully in a max-heap we always get the largest element of the array in array index 1. So we can use this property to sort numbers as follows:

1)Form heap from n input elements: O(n)

2)Delete the element at array index 1 (this is the largest element) : O(1)

3)Adjust the heap with n-1 elements. O (log n). (As we saw above deleting an element and readjusting heap is O(log n))

4)Repeat from step 2 till 1 element is left in heap.

This is my favorite sorting algorithm. It is called the Heapsort and it is an optimal sorting algorithm. The overall complexity of this algorithm is O (n log n) cause we adjust the heap n times (after deleting element at array index 1 to get the largest in present set).

So this was all about Heap. Trust me once you know him well you really can’t stop falling in love with him!