4

I understand that threading is needed to get the maximum performance out of today's multicore processors but starting a thread is rather costly so you can't put every single calculation that can be done in parallel in an own thread. For example

answer = new thread(plus(1,2)) + new thread(plus(3,4))

will run much slower than the simple single-threaded

answer = 1+2+3+4

but if plus was some really complicated calculation the threaded variant might be faster.

Now to the questions

  • Are there any convention or standards about what the minimum length of code, operations or execution time that are defendable to put in its own thread?
  • Do I even have to worry about this or are the compiler/processor so smart that they do all the work for me?

The reason I ask this question is that I saw an implementation of quicksort that started a new thread for every recursive call ending up with (n²) threads and there many of this threads just returned some value.

2
  • 5
    Introducing concurrency in arbitary code is highly nontrivial, don't expect any compiler to do it.
    – user7043
    Apr 23, 2012 at 18:51
  • 1
    Have a thread pool...
    – user1249
    Apr 23, 2012 at 19:17

5 Answers 5

4

when parallelizing there are 3 different timings to take into consideration

  1. the serial time: this is the time spent doing stuff that cannot be parallelized and where you cannot get below (getting the input, writing the output)

  2. the parallel time: this is the part where you can parallelize, this you can get down to 0 by throwing more processors at it

  3. overhead: the time spent communicating between processes/threads, this is very dependent on the algorithm used and the distribution of the work

basically you can add threads until the overhead becomes too big compared to actual gain from parallelization there are formulas for that

but really this is a job for profiling as every algorithm is different

2
  1. There are no conventions, every program is a different story, there is no quick and dirty rule that will let you skip the "careful planning" part.

  2. Unfortunately no. To take advantage of threads you have to use them manually. However, there are languages or libraries that facilitate this e.g. a construct that runs a loop in parallel (but you still have to make sure that it makes sense).

1

If you're only creating a couple of threads, the overhead is negligible. So in your example, answer = new thread(plus(1,2)) + new thread(plus(3,4)) is roughly equivalent to answer = 1+2+3+4 (as long as you're not running this multiple times). This operation runs in a constant number of instructions so there is really no need to thread.

Threading is more appropriate when you are performing calculations on large (variable) sets of data where the running time for the algorithm is not constant. For any such calculation, your aim should be to have all cores at 100% over the duration of the calculation, so that there is no need to create 8000 threads to sort a list. Create one thread per processor and divide the work evenly.

2
  • 3
    If I have a data set with 10 million entries and I want to map some embarrassingly parallel O(1) operation (e.g. saturating each pixel of an raster image individually) over those values, the running time is O(1) -- after all, 10 million is just another constant -- but halving the runtime by using two threads for 5 million operations each, I'd say that makes a pretty significant difference.
    – user7043
    Apr 23, 2012 at 19:24
  • 10 million hard-coded constants is an extremely unlikely use case and would constitute as an exception. However if it is a "data set" that you are mining somehow, I'd consider that "variable" for the purpose of my answer. If you wish you can edit my answer to change the wording, but I think I was clear enough.
    – JSideris
    Apr 23, 2012 at 19:31
0

Multithreading is not only about performance. It's also about user-experience. One of the main reasons to use multithreading is for applications to remain responsive. You wouldn't want your browser to become totally unresponsive until your next webpage has loaded.

So those situations need their own metric.

0

While a lot dependson your actual tools, the following guideline from Intel's TBB documentation may givea useful ballpark figure:

A rule of thumb is that grainsize iterations of operator() should take at least 10,000-100,000 instructions to execute.

TBB is not exactly heavyweight.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.