Right now I'm trying to read through some papers and come up with a good idea for my honors project, which this semester happens to be for my Computer Architecture II class.
A portion of the class deals with parallel computing, so the basic premise of the project is supposed to be taking some useful (but cpu intensive) task and parallelizing it.
My idea at the moment is to implement a parallel implementation of a graph coloring algorithm. This might at first seem a little arbitrary, but theres actually a nice application of graph coloring that relates to the class. The problem is this: when you write a program in a high-level language you can use arbitrary numbers of variables. Underneath the hood however, the processor has a fixed number of registers where these values can be held. The problem is to figure out firstly, can we efficiently use registers in such away to avoid spilling extra data onto the stack? And if not, which registers should we spill?
Graph coloring comes into play for the first portion of the problem. The basic idea is this:
1. Draw a control flow graph of your code. Every statement is a vertex and edges exist between two vertices U and V if you can go directly from statement U to statement V.
2. Establish which variables are "live" on every edge. A variable is live on an edge if it's value needs to be saved when moving between the two statements (vertices).
3. Draw another graph, the interference graph. Every variable is a vertex, and an edge exists between two vertices U and V if the variable U and the variable V are live together at some time.
4. Suppose you have K registers, if the interference graph is K-colorable, then you can accomodate all the variables without spilling. (k-colorable means that you can use k different colors to color in the vertices without 2 adjacent vertices having the same color).
Right, anyway I went off on a tangent.
In other news, I have an interview next week with Amazon and Microsoft. I'm not exactly sure why I have an interview with MS after making myself look not-so-smart at the career fair, but there are no complaints here.
Regardless, Amazon is the more promising interview - I have two 45-minute interviews back-to-back, after which they should know if they are hiring me or not. The MS one is only 30 minutes (and there are a lot more people), so I suspect it's just a weed-out round.