Forums

Quoting - Clay Breshears (Intel)

It was decided to create two separate sets of increasingly larger data files and measure the largest data set (based on number of nodes) that could be handled in a fixed amount of time. This is a demonstration of using parallel execution to enhance throughput (doing more work in a set amount of time).

The first data set collection was graphs based on the N-queens attack patterns for each square on a board. That is, each square on an NxN chessboard was a node and an edge was created from a given square to any other square that could be attacked by a queen sitting on the initial square. Board sizes ranged from 3x3 to 26x26.

The second data set collection was constructed by using a fixed size binary number as a node and included an edge to another binary number if there was exactly one or two bit differences in the binary number. There were seven possible data files based on 3 to 9 bit node "labels".

A maximum of five minutes was set for each input data file tested. The largest queen graph file solved in that time limit was 22x22 (484 nodes, 16786 edges). For the binary graphs, the largest file solved correctly was 7 bits (128 nodes, 1792 edges).

Each data set was worth a maximum of 50 points. The points available were assigned by hand based on the largest data file that could be solved correctly in five minutes or less. If multiple entries reached the same maximum file size within the given time limit, these were ranked by shortest execution time. Entries that did not generate the correct answer on the smallest data set or had compile or runtime issues received zero points for that collection of test data. Several entries were not threaded and were penalized 50 points.

There were 15 submissions of code solutions, 7 on Linux and 8 on Windows. There was one entry written in Cilk++, two in C#, and the rest in C/C++.

Point spread:

94
83 82
73
63
39 31
21
8
0(6)

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:

48 46
39 35 30 30
15
9 9

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 BradleyKuszmaul. The two fastest code executions on the biggest problem sizes tested were submitted by avparate and Sean Lee, and the highest scoring write-up was submitted by Waiting4you.

--clay

Tools

Downloads

Intel Software Network Forums Statistics