Intel® Software Network

I have some philosophical question about the first problem of the Contest to ask the judges:

1) Why to start a threading challenge contest with a problem that is "is inappropriate for parallel computation" (Donald E. Knuth, The art of computing programming: Sorting and searching, pg 114, subsection "Quicksort"): it is like to make a running contest starting  with a cycling  race.

2) The input file added to the .zip file only contains a few numbers. Following the tutorial of Intel TBB it is not a good idea to multithread a so small problem. We need much more points otherwise does not make sense to multithread such a problem.

3) Following step 2 we also need to know how many points we are going to deal to decide how to thread the program: it could be a good idea to give an algorithm to generate a certain number of integer and then test the algorithm to order them.

4) As other collegue of the contest have already point out, the number of point is also important to know if they fit in the cache or not, or if half of them fit the cache etc.

To conclude: the problem as given now is not well posed. You have to give more information:
   a) number of points on which to optimize the algorithm (dependent on the amount and type of free cache on the testing system)
   b) give a number of points that allow an improvement when the program is threaded
   c) choose an algorithm suitable for threading (but it is probably late)

Respectfully

Gaetano

Let me see if I can address your questions and concerns:

1) Actually, Quicksort seems like an excellent problem for parallelism.  After partitioning the data around the pivot, each "half" of the data is independently sortable.  The more the data is split, the more independent pieces there are for parallel execution.  I agree that the traditional recursive version is harder to thread than many other algorithms.  However, we feel that the iterative version is much more amenable to parallelism.  (Besides, if we made the first problem really easy, it wouldn't be much of a Challenge, would it? :-)

2) The included input file is there only for an example of the format.  It will  not be used in the final judging since, as you state, it is much too small.  Rest assured that the data used for judging will contain many more items to be sorted.  We suggest that you create your won large test files for your own testing.

3) Unfortunately, as in real life, we don't know how many items will be included in the data files for judging.  In fact, I would expect that there may be several files with differing numbers of items in each.  Thus, rather than tune for a specific number of data points, you should tune the algorithm to scale to many different numbers of items to be sorted.  To generate a data file, we would suggest a simple loop that use a random number generator to create an input file.

4) How many data items will fit into cache?  1 million?  10 million?  100 million?  Different processors have different architectural characteristics.  Tuning for one specific architecture or cache size will not make the application portable.  You are free to add logic to your code that determines the size of the current cache and optimizes for that size.

I hope this addresses the issues you've raised and answers some of your questions.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K