Winners Announced for Master Problem 2, Tiling Rectangles, for Threading Challenge 2011

Winners Announced for Master Problem 2, Tiling Rectangles, for Threading Challenge 2011

Master Level Problem Set 1 (P1:M2) Tiling Rectangles

Key Scoring Principles

Basic scoring principles used for the contest entries judging are described at the official rules page. Here is a short summary: each contest entry was scored according to the following criteria: 1) up to 100 points for solutions performance (speed); 2) up to 50 points for the solutions write-up using the 10-30-10 breakdown of points for a serial algorithm description, parallel algorithm description and performance analysis respectively; 3) a maximum of 25 bonus points for a contestants activity in the forum, calculated as 5 bonus points for each valid forum post/reply.

Input Data Sets Used for Performance Scoring

Seven different input data sets were used to compute the execution score for this problem. These data sets contain multiple different rectangles with manifold tiling to reveal the potential of various parallel algorithms and methods. The simplest one is a 4x4 rectangle; the hardiest is a huge, complicated 40000x8000 one. Full archive of input data sets can be downloaded here.

Points in Performance Scoring

Each input data set was weighted equally and was judged individually based on a ranking scheme. The overall performance score was calculated as a sum of all seven input data sets individual points.

We allowed a total of 1000 seconds execution (~17 minutes) maximum for each input set; for those runs that took longer than 1000 seconds or had runtime errors during execution, zero performance points were awarded. Some entries that could not be built on the MTL or were not able to complete the task correctly got zero points as well.

Successful contest entries that solved input data sets in less than 1000 seconds were ranked based on their execution time and got performance points according to a reciprocal rank-weight scale. For example, the fastest solution[s] of a data set got ~14.3 points, next solution got ~7.1 points, then ~4.8 points and so on and so forth.

Execution Results and Point Spread

We received 15 contest entries in the Master Level Tiling Rectangles problem set.

Five entries successfully solved all seven input data sets. Nine entries solved at least one data set. Unfortunately, one entry was incomplete and therefore unable to solve any data set.

All the timings and performance points are available in the final scoring table.

Write-ups Scoring

The write-up portion of each entry was read and scored by several 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.

Forum Activity and Bonus Points

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

Entry points and penalties.

Each contest entry got 100 entry points.

The assigned points and final score are available in the final Tiling Rectangles scoring table.


The Tiling Rectangles winners based on highest point total are the following:

1. akki

2. denghui0815

3. protocolocon

These three contestants provided the solutions which correctly resolved all the input data sets and had the fastest overall code execution. They also supplied their entries with well-written, comprehensive write-ups.

8 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Congratulations akki!

Congratulations akki!Looks like Dmitry and I optmized for the wrong input :-)

Thanks, john_e_lilley.I tried to optimize for both cases. I guess my solution struggled a bit with the smaller problems. But I'm happy with the results for larger problems. My write-up is here if anyone's interested.

Here's my Source Code


I was very disappointed with the organization and judging of the competition. My program passes tests which are listed as failed the table.

Quoting oshapovalov
I was very disappointed with the organization and judging of the competition. My program passes tests which are listed as failed the table.

Well, could you please be a little bit more precise? What tests are we talking about?

We're tried hard to run all the entries. We tried different machines, compilers, DLLs, etc. In some cases we even looked inside the source code to understand possible dependencies and memory leaks.

Let's start with the simpliest case:setsinf.txt. Please let me know what should I do in order to pass this input data set in less than 1000 seconds?


--Dmitry O.


Only contains a set of data.
Since I am the particle size is each of the parallel data. So are single-threaded operation.
This is my misstep. : (

Leave a Comment

Please sign in to add a comment. Not a member? Join today