Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

Stress makes me twistedly happy

Sign in to follow this  


This semester is insanely busy, but yet somehow the fact that I'm managing to juggle about 5000 tasks (and none of that day planner shit either) is strangely satisfying.

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.
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!