My colleague has organized Windows Supercomputing Contest 2006 at Kasetsart University. It is a kind of MPI programming contest but all codes must be compiled and ran on Windows Compute Cluster Server 2003. Anyway, this contest is just the first time so he made focus on students inside Kasetsart University including all bachelor degrees from 1st to 4th year. However, all competitors had to attend a short 2-day training course to learn basic of parallel programming and how to implement MPI application especially for Windows Cluster. The contest problem is to write a program to solve specified problem in 3 weeks at home.

My task was to find an appropriate problem. The problem must be solvable by 1st year student but not too easy at the same time. I don’t know many problems but it seems there are 2 classes of problem.

1. Matrix-based problem i.e. matrix multiplication, heat transfer, and turbulence flow
2. Graph-based problem i.e. travelling saleman and shortest path

The first class can be solved by data composition method. However, it would be very similar technique to compose 2d or 3d data. So I ended up to the second class, graph-based problem. To solve graph-based problem, search technique must be used such as depth first search, breadth first search, best first search, IDA*, genetic algorithm, simulated annealing and etc. The selected problem is one of classic NP-Complete problem namely Bandwidth Minimization Problem. Basically, the objective is to minimize total bandwidth of all nodes in linear form. In other words, the problem gives a set of vertices and edges formed into a graph. You have to order all vertices so that it gives minimum total length of edges. If vertex A and B are connected and A is placed next to B, its length is 1. If vertex C is placed between the A and the B, the length will be 2. That’s all. At the first glance, this problem is n! complexity. It is very interesting problem and not too hard to solve.

Nowadays, all codes had been submitted back to the committees. One team didn’t wrote parallel program instead they optimize sequential program using greedy technique. It turned out that their heuristic is extremely fast! For example, it takes only 7 ms for 8-node while other teams using MPI takes 34 ms. I am finding the weakness of this heuristic so that parallel program can beat it up. If I can’t, it seems parallel programming is useless.

Lastly, the team said that this problem is just n⁴ complexity and they reduced the complexity to n². Arg....

Technorati Tags: English, IT, Programming, Tips and Tricks, Parallel Programming, MPI, Windows, Cluster, Bandwidth,