4,391 Posts served

10,712 Conversations started

White Rabbits - part 2

By jimdempseyatthecove (8 posts) on November 25, 2009 at 4:22 pm

This is a continuation of my White Rabbits blog. Let’s go looking for some White Rabbits.

The above represents a series of 10 test runs, with average, of a program running 5 different tests per run. Run on a quad core Intel Q6600.

Test 1 is single threaded

// t1 single thread for loops
__int64 t1 = __rdtsc();
for(int i=0; i<arraySize; ++i)
A[i] = ((double)i) / 1000.0;
for(int i=0; i<arraySize; ++i)
B[i] = sin(A[i]);
for(int i=0; i<arraySize; ++i)
C[i] = cos(A[i]);
t1 = __rdtsc() - t1;
std::cout << " " << t1;

Where arraySize is 1024*1024

Test 2 is multi-threaded (4 threads) using OpenMP

// t2 multi-threaded for loop
// using all threads
// without background thread
__int64 t2 = __rdtsc();
#pragma omp parallel for
for(int i=0; i<arraySize; ++i)
A[i] = ((double)i) / 1000.0;
#pragma omp parallel for
for(int i=0; i<arraySize; ++i)
B[i] = sin(A[i]);
#pragma omp parallel for
for(int i=0; i<arraySize; ++i)
C[i] = cos(A[i]);
t2 = __rdtsc() - t2;
std::cout << " " << t2;

Test 3 is multi-threaded (4 threads) using OpenMP with the OpenMP chunk size

// t3 loops with chunk size
// using all threads
// without background thread
__int64 t3 = __rdtsc();
#pragma omp parallel for schedule(dynamic, chunk)
for(int i=0; i<arraySize; ++i)
A[i] = ((double)i) / 1000.0;
#pragma omp parallel for schedule(dynamic, chunk)
for(int i=0; i<arraySize; ++i)
B[i] = sin(A[i]);
#pragma omp parallel for schedule(dynamic, chunk)
for(int i=0; i<arraySize; ++i)
C[i] = cos(A[i]);
t3 = __rdtsc() - t3;
std::cout << " " << t3;

Tests 2 and 3 are run with the system relatively unloaded. Some instances of other applications are loaded but not busy working.

Tests 4 and 5 are run with a load of one non-OpenMP thread within the application

// startup non-OpenMP thread
// simulate one compute thread
// running other program running
done = true;
HANDLE h = (HANDLE)_beginthread(&tieUpThread, 0, 0);

with

void tieUpThread(void* context)
{
done = false;
while(!done)
_mm_pause();
}

Test 4 is the same as test 2 but run with the additional load.
Test 5 is the same as test 3 but run with the additional load.

In observing the charted lines, the separations of the lines are the White Rabbits.

Test 2, in 4 of the 10 runs, showed scaling between 3.5 and 4x that of single threaded program. This is good scaling. However, test 2, in 5 of the 10 runs, showed scaling between 2 and 3x that of single threaded program. Not as good scaling. And in test 2, 1 of the 10 runs, showed about 1.5x that of the single threaded program. The average for test 2 being 2.87x that of the single threaded program. This is likely a benchmark that you will not find posted to promote someone’s threading prowess. I am posting it here, to illustrate White Rabbits.

Test 3, showed tighter grouping and at greater than 3x improvement over serial performance.

Test 4, has a precipitous drop when the additional thread load comes in to play and when you make no programming consideration for this possibility.

Test 5, mitigates some of the performance hit by using the OpenMP schedule(dynamic, chunk) where chunk is set to:

int chunk = arraySize / maxThreads / 4;

Test 3, (prior to additional thread load) also used schedule(dynamic, chunk) and the average time benefited over coding without chunk. Your experience may vary.

The above runs were of a synthetic program that generally will not be typical of your OpenMP programs. However, the test data does illustrate the White Rabbits in the program.

In a more complex OpenMP application you may use nested levels. The following is an expansion on the test program

Test 6 is the same as test 4, except run one Nest Level deeper (and with additional thread load).
Test 7 is the same as test 5 (with chunk), except run one Nest Level deeper (and with additional thread load).
Test 8 the same as test 6, except run with one less thread (with knowledge of busy thread).
Test 9 the same as test 7, except run with one less thread (with knowledge of busy thread).

As you can see from the chart, using OpenMP chunking can improve performance. And more significantly, knowledge of activities of other threads within your application can yield significant improvement in performance. You will have to construct a rule for determining how many threads to remove from your parallel for loops. Perhaps at least one per level. (More White Rabbit management.)

Let’s see what happens when we run the second test program, but configured to use a threading toolkit that provides enhanced programming capabilities. We will run the same functional test using QuickThread.

As you can see from the chart plots, even with QuickThread, the program still has White Rabbits. But you can also see, with appropriate programming for the run-time environment, you can corral the White Rabbits within a narrow band. Test 2 and 3 for lightly loaded system, and test 6 and 7 for moderately loaded system (one additional compute bound thread).

Let’s see what the QuickThread code looks like

Test 1 is the same serial code

Test 2

// t2 multi-threaded for loop
// using all threads
// without background thread
__int64 t2 = __rdtsc();
parallel_for(
0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
A[i] = ((double)i) / 1000.0;
});
parallel_for(
0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
B[i] = sin(A[i]);
});
parallel_for(
0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
C[i] = cos(A[i]);
});
t2 = __rdtsc() - t2;
std::cout << " " << t2;

With Intel C++, or any compiler with C++0x Lambda function capabilities, you can convert your OpenMP program relatively easy by using Lambda functions.

Test 3 (QuickThread equivalent to OpenMP chunking)

// t3 loops with chunk size
// using all threads
// without background thread
__int64 t3 = __rdtsc();
parallel_for(
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
A[i] = ((double)i) / 1000.0;
});
parallel_for(
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
B[i] = sin(A[i]);
});
parallel_for(
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
C[i] = cos(A[i]);
});
t3 = __rdtsc() - t3;
std::cout << " " << t3;

The QuickThread statement to launch compute bound thread within thread pool of application

// Create a QuickThread thread
// within this application
// to simulate other task running
// using our thread pool
parallel_task(tieUpThread, 0);

Test 8 (non-chunking but reduced thread count)

// t8 reduced thread count without chunking
__int64 t8 = __rdtsc();
parallel_for(
AllWaitingThreads$,
0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
A[i] = ((double)i) / 1000.0;
});
parallel_for(
AllWaitingThreads$,
0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
B[i] = sin(A[i]);
});
parallel_for(
AllWaitingThreads$,
0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
C[i] = cos(A[i]);
});
t8 = __rdtsc() - t8;
std::cout << " " << t8;

Special note about 8.

Note the use of AllWaitingThreads$ as a parameter to parallel_for. When you use this on the outer nest level, all threads are available, and the iteration space is divided up by the number of threads. When use of AllWaitingThreads$ as a parameter is nested, the parallel_for loop is partitioned by the number of waiting threads + current thread (assuming you do not request for the thread pool to be selected elsewhere (e.g. on/in different socket).

Test 9, reduced thread count with chunking

// t9 reduced thread count with chunking
__int64 t9 = __rdtsc();
parallel_for(
AllWaitingThreads$,
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
A[i] = ((double)i) / 1000.0;
});
parallel_for(
AllWaitingThreads$,
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
B[i] = sin(A[i]);
});
parallel_for(
AllWaitingThreads$,
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
C[i] = cos(A[i]);
});
t9 = __rdtsc() - t9;
std::cout << " " << t9;

Integrating QuickThread into this OpenMP program was relatively easy when used with Intel C++ Lambda function support.

Now consider what you could do with QuickThread to make the last two parallel_for loops run in parallel. For this we use parallel_invoke to fork and join the thread stream.

// t10 all of our pool threads, with chunking
// and with second two loops in parallel
__int64 t10 = __rdtsc();
parallel_for(
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
A[i] = ((double)i) / 1000.0;
});
// run two parallel for loops in parallel
parallel_invoke(
AllThreads$,
// Lambda task 1
[&]() {
parallel_for(
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
B[i] = sin(A[i]);
});
},
// Lambda task 2
[&]() {
parallel_for(
chunk, 0, arraySize,
[&](int iBegin, int iEnd)
{
for(int i=iBegin; i<iEnd; ++i)
C[i] = cos(A[i]);
});
}
);
t10 = __rdtsc() - t10;
std::cout << " " << t10;

And chart with data to add test 10

With the additional level of parallel programming control within QuickThread it is a relatively trivial programming job to corral the White Rabbits and to produce significantly faster code.

Visit me at The Parallel Void.

Jim Dempsey

Categories: Parallel Programming

For more complete information about compiler optimizations, see our Optimization Notice.

Comments (9)

Trackbacks (0)

Leave a comment  

Name (required)*

Email (required; will not be displayed on this page)*

Your URL (optional)


Comment*