Simple Multithreading design

[Kaliemon]

I need help with a simple multithreaded design.

I have an app that loops through each pixel of an image and calculates the data at that point. Each pixel is completely independent of the others, so there shouldn't be any synchronization issues.

Mainly, I need to find out how to spawn about 5 threads that each handle a 32x32 square, and do this for the entire image. Or possibly 5 threads each doing a pixel in the 32x32 square, I don't know which is better.

I already have a subclass of a Qthread and a method that can handle the square, I just don't know how to create the next thread when one finishes. I thought about a loop, but it waits for all 5 threads to finish before creating the next set.

I hope this all makes sense.

Note: this is done in C++ on Linux

[Sander]

I'm not sure this is a Mac-specific question.

I wouldn't make the threads operate on square sub-images, but rather on "strips" of the image. This is better for cache coherancy. Also, it would not make much sense to spawn more threads than you have cores in your system.

[Menge]

If you want the benefits of multi-threading, then you don't create a thread when the last one finishes. You create all threads at the same time, assign them an area (re-recommending the same as Sander: a strip of pixels) and wait for all of them to finish. Multithreading doesn't go like this:
(1)--, (2)--, (3)--, *

it goes like this:
(1) -\,
(2) --,*
(3) -/,

[Kaliemon]

So if I have a 4 core system, and say a 500px high image, would I create 500 threads and let the OS handle the queueing?

I was thinking it would be best to have 4 threads processing, a 5th waiting to run and every time the 5th thread starts create another thread to be waiting to run. I am trying to break up the threads to process the smallest amount of data since 3 could finish instantly and I don't won't the last running thread to have to do a large amount of work when there are available threads.

Also with the square vs line choices, the data in our case is much more similar in a 32x32 patch vs across a line, so wouldn't it be better for cache?

[savar]

Originally Posted by Kaliemon

So if I have a 4 core system, and say a 500px high image, would I create 500 threads and let the OS handle the queueing?

Definitely DO NOT create 500 threads. That's too much for any current computer.

The Snow Leopard way to do this is to create 500 blocks, and let GCD decide how many threads to create and when to schedule them.

[Kaliemon]

Originally Posted by savar

The Snow Leopard way to do this is to create 500 blocks, and let GCD decide how many threads to create and when to schedule them.

That's how I am used to doing things, but since this has to run on linux I don't have GCD.

[Catfish_Man]

Threadsafe queue implementations shouldn't be *too* hard to find. Once you have one, you can simply spawn N threads where N is the number of cpus available, then have them sit in while (pixelstrip = workqueue.pop()) { process(pixelstrip); } loops. You may have to fiddle with the granularity of the pixel strips for optimum efficiency.