Intel® Software Network

The judges were a bit disappointed in the number of entries. There were only six applications entered, 2 on Linux and 4 on Windows. We thought that this would be a pretty straightforward problem to solve with many chances for parallelism. Perhaps it is the time of year?

Six different graph data files were used to compute the execution score for this problem. The smallest file had 12 nodes and 60 edges; the largest file had 36 nodes with 161 edges. The table describes features of the data sets (Degree is the range of the number of edges per node):

File                | Nodes | Edges | Degree | Colors
------------------------------------------------------
paley17.txt     |    17   |    67   |      8    |   5
------------------------------------------------------
K6.txt            |    36   |   111   |   2-10  |   6 (run with max=5)
------------------------------------------------------
K6a60.txt       |    36   |   129   |   2-14  |   5
------------------------------------------------------
q6-6-3-4.txt   |    36   |   161   |   4-15  |   5
------------------------------------------------------
zz328-1-2.txt |    33   |   133   |   3-12  |   5
------------------------------------------------------
CP12.txt        |    12   |     60   |     10   |   6

To get bigger test cases that were still computable with the time limit, the judges started with a "small" test case and examined the coloring results. One of the colors was chosen and edges were added between pairs of nodes that had been assigned the chosen color. Three rounds of adding edges in this way typically boosted the execution time from less than 1 second to around 5 minutes. At first, the judges found it odd that adding edges, which would restrict the problem further, would increase the computation time when the number of nodes remained the same. It was soon realized that the added restrictions limited the number of solutions and having more solutions possible (fewer edges) led to finding one of those solutions much quicker.

A maximum of 10 minutes (600 seconds) was allowed for each data file. If an application exceeded this limit or terminated with some form of runtime error, a time of 600 seconds was recorded for the time on that data file. If the application delivered the wrong number of minimum colors it was considered incorrect and a time of 600 seconds was recorded. The total execution time of all six files was summed and a fraction of 100 points was awarded based on where the total fell within the range of the minimum and 3600 seconds. A 5 point penalty accessed to entries that printed colors starting with "0".

One entry was threaded with Cilk++, one was in Java, one used C#, and the rest were written in C/C++.

Point spread:

100
99
82
33 33
0

The write-up portion of each entry was read and scored by two judges. Each judge used the 10-30-10 breakdown of points for serial algorithm description, parallel algorithm description, and performance, respectively. One important component to the judging was to determine how close the submission was for publication on ISN. The assigned score was the average of the two judges scores.

Point spread:

45 42
36
10
0 0 0

Bonus points were given for contestant’s forum posts made before the problem entries were closed. Five points per post (maximum 25 points possible) were awarded.

The overall winner was akki (we tripled checked this time :-), who had the fastest code execution and highest scoring write-up. As an extra (unrecorded) test, larger data files were run. The entry submitted by mdm100 was able to handle the largest file used (76 nodes, 1367 edges, 12 colors) in less than the time limit.