Intel® Software Network

One test case of 25 variables that described a satisfiable expression was used to ensure that the entries could correctly find and print such a case. Execution time for finding the answer to a satisfiable expression could vary widely depending on the order of the clauses or the variables and how the application attempted to solve the expression. Thus, only one satisfiable test case was used and the solution time was ignored. Applications that generated a correct assignment to variables were awarded 25 points. The true chance for use of parallelism and optimizations within an application would be in dealing with unsatisfiable expressions.

There was a wide variety of solutions and execution times. The judges spent a week trying to find a set of unsatisfiable test cases that would be executable by all running applications within a reasonable amount of time, but still give the chance to differentiate between entries. Eventually it was decided to create a set of increasingly larger data files and record the largest data set (based on number of variables) 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).

A maximum of five minutes was used for each input data file. The number of variables started with 6 in the smallest data file and increased by 3 variables (6, 9, 12, ...) up to 48 variables. The remaining files used 50, 60, 75 and 100 variable expressions. If multiple entries reached the same maximum file size within the given time limit, the intent was to rank those entries by shortest execution time. Oddly enough, only 3 entries, that were able to execute and correctly identify the unsatisfiable expression, peaked with the same file size. These were three entries that could handle the expression with 100 variables. The fastest of these was submitted by jne100. The remainder of the 75 points available were assigned by hand, based on the largest data file that could be solved in five minutes or less.

There were 22 submissions of code solutions, 6 on Linux and 16 on Windows. There was one entry written in Java, three in C#, and the rest in C/C++. Twelve entries had run-time issues or generated incorrect answers. One working entry was not threaded and received a 50 point penalty.  (Files used in judging will be attached in a separate post in this thread.)

Point spread:

100
99
89
79
69 65
55 50
47 42
25
0(12)

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 ready (complete) the submission was for publication on ISN. The assigned score was the average of the two judge's scores.

Point spread (out of a possible 50 points):

40
39 30
27 20
19 18 15 13 13 11
6 6 5 2 1
0(7)

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 haojn, who also had the highest scoring write-up submission. The fastest code execution on the biggest problem size tested was submitted by jne100. One notable code submission was from denghui0815, who implemented two different methods of solution (with both a serial and parallel execution) that can be chosen at the command line.

--clay