No time improvement with multiple threads

[jdodle]

I am working on a program that uses 1 or more threads to process a NxN matrix. when I run the program for a 50x50 matrix with 1 thread I get an execution time of about 13000ms. When I process the same matrix with 2 threads I am getting an execution time of about 20000ms.

Obviously there is something wrong because with 2 thread it should take about half the time, i.e. 6500ms.

I was able to narrow it down to the loop that iterate through each element of the array:

for (uint32_t i = args->low; i < args->high+1; i++) {
    for (uint32_t j = 1; j < args->size+1; j++) {
        args->write[i][j] = (args->read[i-1][j]+args->read[i+1][j]+args->read[i][j-1]+args->read[i][j+1])*.25;
        dif = fabs(args->write[i][j]-args->read[i][j]);
        if (dif > max_dif) max_dif = dif;
    }
}

The way the threads work is that each thread gets assigned a set of rows to work on each thread passes over its section of the array several hundred times. For example, with two threads on a 50x50 matrix, thread 1 would get rows 0-25 and thread 2 would get 26-50. I have confirmed that each thread is being assigned the correct values for args->low and args->high so they are not doing duplicate work. So it makes sense that the program should execute in half the time... but it doesn't.

Looking at some debug output I was able to see that with two threads each iteration of the loop above was taking 30-70ms. After one thread completes each iteration for the remaining thread drops to about 30ms. And with 1 thread each iteration takes 40-80ms.

Does anyone know what is happening to cause this?

The processor on my system is an Intel i5 and the machine is almost completely idle without running my program. So there should be no hardware constraints on getting the expected improvement with 2 threads.

[algorism]

How large are the elements of the matrix?

How many cores does your processor have (I assume 4, but just to be sure)?
Do you know it's cache sizes? (or it's model number)

What are the timings with a 10x10 matrix?

[jdodle]

These are float matrices, so 32 bits per index.

I think it is 4 cores but not completely sure. It is an iMac, i don't know the year though. I am logged in remotely so Im not exactly sure how to get that information.


The timings with a 10x10 matrix are:
per iteration: 12-14ms with 1 thread and 40-70ms with 2 threads.
total execution time: 500ms with 1 thread and 1000ms with 2 threads

Though with a 10x10 matrix I would expect more threads to increase execution time. So maybe you meant a 100x100 matrix in which case here are the times.
per iteration: 239-242ms with 1 thread and 600-800ms with 2 threads
total execution time 80000 ms with 1 thread and 180000 with 2 threads

[jdodle]

After doing some research I was able to get the hardware stats with sysctl:

hw.cachelinesize = 64
hw.l1icachesize = 32768
hw.l1dcachesize = 32768
hw.l2settings = 1
hw.l2cachesize = 262144
hw.l3settings = 1
hw.l3cachesize = 6291456
hw.ncpu = 4

[algorism]

Can you post a link to a zip of the source?

[jdodle]

I don't want to make the source publicly available (academic integrity), however I can send you the source directly if you would like?

[algorism]

You could put it up on tinyupload (no need to sign up) and pm me the download link
and then, say 20 minutes later, use the delete link (make sure you save it).

[Codeplug]

The study of speed-up with multiple threads/processes can be a bit tricky. For example, in published papers, the overhead of thread startup time is typically omitted. "How" you perform you're timing is very important. So how?

13 to 20 seconds is fairly low. Eg. for what 1 thread requires 2 minutes, 2 threads may only need 1.8 minutes. "Perfect speedup" is very rarely achieved - ie. 1 thread taking 2 minutes, and 2 threads taking 1 minute.

gg

[jdodle]

I am fine with that, I am new to this forum, how do pm you?

[algorism]

I am fine with that, I am new to this forum, how do pm you?

You can click "Settings" at the top right, then "Send new message" over on the left somewhere. Send it to my username.

[jdodle]

There is no "send new message" option for me. I was able to find "PM user" at "quick links" -> "open contacts popup" but it gives me a permission denied error.

[jdodle]

I am starting the timer just before starting the last thread (just before the last call to pthread_create) and stops just after the last thread ends (just after the last pthread_join). For timing each iteration of the loop I posted I start the timer just before the loop starts and stop it just after the loop ends.

I am aware that I can not always expect "Perfect speedup" however each thread is given as equal amount of work as possible and each thread can run completely independent of each other thread for each iteration. My code does align the threads after each iteration using semaphores. However this just mean that the total execution time will be a sum of each iterations longest runtime. So as long as each thread is given equal work (or at least very close to equal) then you should see almost "Perfect speedup" when the thread count is small.

[rcgldr]

Add code to time the main loop in each thread, saving the results to be displayed after all threads have completed. Usually when multiple threads are slower, it is due to cache / memory conflicts, but a 10x10 matrix seems too small for this to be an issue.

[jdodle]

Add code to time the main loop in each thread, saving the results to be displayed after all threads have completed. Usually when multiple threads are slower, it is due to cache / memory conflicts, but a 10x10 matrix seems too small for this to be an issue.

I do have code for this, however I split it up into two sections. One timer is for how long each thread waits to start its next iteration and the second timer times the for loops I posted. the remaining parts of the loop are insignificant in comparison so they are not timed. As I posted in my original question, the timer for the for loops is showing that with 2 threads those loops take just as much time as with 1 thread. with two thread the outer loop loops half as many times thus it is taking twice as long to do the work.

[Codeplug]

>> My code does align the threads after each iteration using semaphores.
Using a barrier to ensure all threads start "at the same time" is good.

>> One timer is for how long each thread waits to start its next iteration
After the start barrier, there shouldn't be any other synchronization if the threads really are completely independent of each other.

The timer should start when the barrier releases the threads - and stop when all work has been completed. You should also set thread affinity to ensure that they are never scheduled on the same core. You can also make a "yield" call after the barrier (before the timer) to ensure that the thread/timer starts at the beginning of a new quantum.

gg