Skip to content
November 25, 2010 / Rohit

Parallel Programming Heuristics

Wherein I describe heuristics to achieve success* in parallel programming:

  1. Incorrect Output: Say you re-wrote your program to run in parallel, but now all the results are incorrect. Chances are that there are some critical sections which are causing problems. Solution: guess where the critical section might be and acquire as many locks as possible in that region. Lock all of the variables if you feel like it! Keep locking till your program starts running correctly. If locks aren’t your favorite drug, use whatever synchronization primitive you find attractive.
  2. Program Hangs: One implication of applying heuristic 1, is that your program might just hang (but at least it doesn’t produce incorrect output). This might be due to deadlocks! To solve this, you might have to release some locks. Pick your least favorite variable and stop locking it. Re-run the program and see if it works. If it doesn’t, pick another variable and repeat.
  3. Parallel Version Performs Poorly: Say after diligent application of heuristics 1 and 2, finally your program works as expected. But, to your embarrassment,  it performs poorly as compared to the serial version of the program. Don’t worry, this happens all the time. And I have a solution for it: one way to make your parallel version work better is to make your serial version suck. In addition to its original task, make the serial version do something compute intensive — like try to factor large primes, I don’t know, be creative. 

*Not really.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: