Mi Segundo Amor

                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

 

The Impossible Dream

          Reminiscing school days with a fellow Don Bosconian at work the other day, I couldn’t help but recollect this one particular song that had a deep impact on me.  We had performed this song as part of a skit on Don Bosco. On researching about it I found that it was composed by Mitch Leigh and was written for the 1965 musical “Man of La Mancha” inspired by Miguel de Cervantes’s seventeenth century masterpiece “El ingenioso hidalgo don Quijote de la Mancha” ; something which is on my reading wishlist (I wish after two levels of spanish, I can read this in spanish Que agradable pensamiento!! ).  Here are the lyrics of this beautiful song :

To dream the impossible dream
To fight the unbeatable foe
To bear with unbearable sorrow
To run where the brave dare not go

To right the unrightable wrong
To love pure and chaste from afar
To try when your arms are too weary
To reach the unreachable star

This is my quest to follow that star
No matter how hopeless, no matter how far
To fight for the right
Without question or pause
To be willing to march
Into hell for a heavenly cause

And I know if I’ll only be true
To this glorious quest
That my heart will lie peaceful and calm
When I’m laid to my rest

And the world will be better for this
That one man, scorned and covered with scars
Still strove with his last ounce of courage
To reach the unreachable star..
The fight the unbeatable foe..
To dream the impossible dream..

 

Veintidós años alrededor del Sol

Its been long that I have come here. I had somehow lost any appetite to blog.  But well here I am again . Needless to say much has changed in the interim. But this post is primarily about my recent trip with my friends.

Transition from college life to a work life had taken both me and my friends to different cities with technology as the only means to keep in touch. We always tried to plan a re-union but trust me getting 4 different outlook calendars to show ‘free’ in the same time slot is a herculean task and takes a lot of concerted effort  (add planning vacation with your boss to that and you know I am talking of exponential complexity here ). But finally, more than a year after graduating from college we all hatched a plan to get out of our rat races and headed to my hometown ; the beautiful and scenic Konkan region.

It was my birthday and our plan was to have a small celebration with my family and spend the weekend in Goa and Malvan. So after Day 1 of birthday celebrations and munching on my Mother’s delicacies we started pretty early for Goa the next day. Goa is about 90Km from my place and well connected by the NH17 national highway. Along the way we were mesmerized by  beautiful Moti Talav (Lake) in Sawantwadi and overlooking it was the famous Rajwada. We decided to visit the famous Calangute beach in Goa first. It was quiet crowded by the time we reached there and water sports were in full swing. Looking at the fun and frolic around we dropped our initial plan to indulge in water sports at the Dona Paula beach and grabbed the first water scooter in sight .

Boy.. I don’t remember the last time I must have been so thrilled!!! Being never fond of sports, I was a bit apprehensive initially but my friends were adamant that they were going to make me start a new year of my life with as much as craziness as possible; with the ‘scary’ Banana ride or ‘you are the king of world’ Para sailing ride or ‘get spanked’ Bumping ride !! After completely exhausting ourselves we headed to Panjim for lunch. Walking on the June 18 Road and interacting with a host of locals we were advised to go to the ‘Ritz Hotel’ for authentic Goan food. My fishetarian friend enjoyed the ‘fish plate’ there,  (5 delicious varieties of fish in one plate.. all she could say was ‘I am loving it’) while I was left mulling over the fact that my sweet lime juice cost as much as the some varieties of booze there!! We headed to Old Goa after that; for a trip to Goa is never complete for me till I visit the famous Basilica Of Bom Jesus. After spending a calm evening on the Miramar beach we headed for home to take some rest before another excited day began.

Day 3 of our trip was dedicated to exploring beaches in Malvan, again an hour’s ride from my place.  We reached there early in morning and after hiring a boat we headed to the ‘Dolphin point’  about 9 Km in the sea through the back waters.  It was there,  for the first time in our lives that we saw the amazing symmetry with which dolphins swim !! We were left spellbound by the beauty of their movement which was over-powering the vastness of the ocean. It was only when the cruel and unstoppable ‘Time’ shone on our heads in the form of Sun that we  headed back to the shore. After a short visit to the famous and serene Tarkarli beach we headed to the Malvan Jetty to do something we all were mightily excited about – Snorkeling!!  Snorkeling is a recently started activity near the Sindhudurg fort. Our guides were two patient individuals who calmly explained us how to use our gear. Well, after that it was but Discovery live for you!!! We saw different varieties of corals and many beautiful fishes.  We ended our Day-3 trip by a visit to the famous Sindhudurg fort.

All in all it was a near perfect start of a new year for me; all cause of my lovely and energetic buddies. Love you all big time girls

 

 

Moving on…

First of all many thanks to a friend who took the pains to mail me that she happened to read my blog and that I should keep writing. They say ‘a friend is someone who knows the song in your heart and can sing it back to you when you have forgotten the words’. Thanks to her that I finally felt like posting this one. So many things have happened in the past 2 months that I guess it took some time for me to come to terms with myself. Here’s a quick list:

1. I finished my engineering studies with static colors . So now I can claim that I am an Engineer. Shaizeen Aga, BTech IT (COEP) happens to be my new designation .
2. We, which means (Akki, Swati and me) won Imagine Cup Parallel Computing Award. I really want to thank some people without whom this achievement would not have been possible.-Niks: For suggesting to me that I participate ( I had better mention Shira’s name here for inviting us to her birthday party and coming late herself which gave Niks and me, the time to start chatting). He not only suggested that I participate but also wholeheartedly believed that I would win . Niks, do let me know how you developed this foresight:).

   -Sudhir: For answering all my silly doubts with his immense patience and helping out.

   -Jinson and Kumbhar Sir: For helping us arrange a quad core machine for getting our test results.

   -And last but not the least Swati, for having a dual core machine, almost killing it for getting the results we got and for converting herself into a anthropomorphic debugger for almost over a month to make our code run with atmost precision and Akki for being at a ‘missed call’ distance from me for last four years and  bearing up with PRETCT who almost used to throw up (or faint) when fed with our code and large datasets.

3. I had my first press conference for winning the Imagine Cup which was arranged by our college. Here’s a short list of various  newspapers covering this:
   Pune MirrorIndian Express

   Times of India

4. I moved out of Pune and I am back at home now. I definitely miss the city a lot… esp Smokin Joes, Corn Club, Horn Ok Please, Krishna Juice Center, ABC, J-Block and most of all C-O-E-P… The last four years have been some of the best years of my life and they wouldn’t have been so had it not been for all my beloved friends who made it so for me. I miss you all a lot…

Life at home is good.. Rain gods are pouring their hearts out and it rains cats and dogs out here… I have never been a devout  Sun Fan  nor a Rain Fan , but I surely am  missing  Sun a lot . If any you guys happen to see him please let him know I am heart-broken and that he should try striking some sort of pact with Rain and show up atleast for a few hours everyday. I am waiting for the hegemony of Rain god to end and for my mornings to be welcomed by the dulcet sounds of birds instead of the constant clamor of incessant rains.

 

Shaiz votes!!

Where have I been in the last one month? Yes. Same stuff, submission (just 1 this time though) and viva. But I think the buggy-ness quotient of this one submission was really high as compared to the other submissions that we have had. And yes of course my project report submission. Jeez… Documentation is a herculean task and by no means should be done at eleventh hour. But I never had documented any stuff and so creating the report really took the breath out of me. ‘Digging a well only when thirsty’ is definitely not a right way to quench your thirst.

As usual everything is done and I think was done well. But this week has been completely packed with some really important stuff for me. First on Tuesday we had Graduation day at the Akanksha center I volunteer for. This is a day when kids graduate from one level to next and demonstrate what they have learned in the present term. The kids were so enthusiastic about what they were presenting. It was fun attending it but at the same time it reminded me that I won’t be seeing them anymore as the center will be closed for summer holidays. I am sure gonna miss them .

Second (n really important) was today I cast my first vote. I am really so happy and proud about this . Thanks to my roomies (Trups, Shitu, Appulocks) for letting me know that we could register for voting in Pune even though we aren’t permanently residing here. Also special thanks to “Jaago Re! One Billion Votes”, the non-partisan national campaign launched by Janaagraha Centre for Citizenship and Democracy and Tata Tea for making it so simple to register for voting. So,

“Here we stand with a dot,

Proud that we added our tot ”

Us after voting

And finally now I think I will retire to studying something as the last important (??) thing this week is my end semester exam on Saturday. It’s high time and I should better start digging now

 

Shaiz Aligned!!

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 H_{i, 0} = H_{0, j} = 0 for 1 ≤ i ≤ n and 1 ≤ j ≤ m, where n and m are lengths of the two sequences under consideration. Then,

H_{i, j} = max { { H_{i-1, j-1} + s( a_i , b_j )} , max_{1 ≤ k ≤ i} {H_{i-k, j} - W_k}, max_{1 ≤ k ≤ j} {H_{i, j-k} – W_k}, 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,

H_{4, 6} = max { {H_{3, 5 +} s(A, G)}, max { (H_{4, 5} – 1.3) , (H_4,4 – 1.7), (H_{4,3 ­} – 2)}, max {(H_{3, 6} – 1.3), (H_2,6 – 1.7), (H_1,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.

 

Developers Conference @ COEP

Its being almost a month since I last blogged. This being my first one since the beginning of 2009. The one thing which I dont understand about education system is why do academic year and calendar year dont start and end at the same time. Its new year and I am still in BTECH IT at COEP as was I last year. So many things in your life just don’t seem to change though there are people out there celebrating an entire new year!! I spend my new year eve with Anju, my childhood friend and her family at her home. She is one of my best buddies and its always a treat to spend time with her.They have been a family to me ever since I moved to Pune and it is thanks to them that I never feel I am alone in this city.

My BE project cum internship at NVIDIA keeps me busy enough that many a times I end up being in office sometimes even at weekends inspite of spending my weekdays almost entirely there. I had vowed that I will never spent weekends in office. Trups (my roomie since the first day at hostel) who was the sole witness to my “resolution” has gone at length to suggest that I rent a room near office to avoid commuting. Not that she cares about me hitting someone while being “activated” (which I actually did a few days ago) but more that she likes to remind me that I am a workaholic in a very tactful way.  And trust me as far as  “hitting” (pun intended) goes, it can be mutual as is certainly always in my case .

But what better to start your new year than to be part of an amazing event which took place at my college auditorium.Each year we Microsoft Student Partners from Pune organise Developers Conference (DEVCON) , a day filled with technical sessions and fun for colleges in Pune. This year we had organised DEVCON on 18th Jan and the response was huge. More than 1000 students turned up from in and around the entire city. We organisers were indeed overwhelmed!!

The entire team had worked hard to make this event successful and we all were really happy with the turnout. Here are some pics:

Students lined up at COEP auditoriu

Packed Auditorium @ COEP

Quiz @ DEVCON

And yes finally here are we the MSP’s, the ultimate ROCKERS!!

Microsoft Student Partners, Pune

( left to right)  Prachi, Manish, Ravikant, Shristi,Anuja, Dev, Awadesh, Piyusha, Abin,Dhaval , Sonali , Me,

( right to left) Rashi, Pradyna, Nikhil, Mayur, Aniket,Anand, Rahul, Ritesh.