sample_qsort.cilk program hanging.

sample_qsort.cilk program hanging.

Iam worrking with the sample-qsort.cpp program on page 12, 13, and 14 of Intel Cilk++ SDK Programmer's Guide doc. no. 322581-001US.

I built the the serial program and it worked.I added include and and converted main to cilk_main and it still worked.

in each case it sorted 10 million integers with no problem and at all.

Now when I parallize it as explained on page 14 of the document and shownin the latter case it was a cilk program with no paralleleism, yet; but it worked.

Now going further, I added cilk_spawn sample_qsort(begin, end) and cilk_sync above and below the line sample_qsort(++middle, ++end0;Exclude pivot

Now when I run the program it only prints out

Sorting 10000000 integers

and nothing more. I am not sure if it hanging or simply operatng slowly. I am using a loaner laptop and am not sure of the core count in the processor but I know that it has at least one core. I am not sure why it is hanging or running slow. What is going on?/

Newport_j

my code is shown as follows:

#include

#include

#include

#include

#include

// Sort the range between begin and end.

// "end" is one past the the final element in the range.

// This is pure C++ code before Cilk++ conversion.

void sample_qsort(int * begin, int * end)

{

if (begin !=end) {

--end; // Exclude last element (pivot)

int * middle = std::partition(begin, end,

std::bind2nd(std::less(), *end));

std::swap(*end, *middle); //pivot to middle

cilk_spawn sample_qsort(begin, middle);

sample_qsort(begin, middle);

sample_qsort(++middle, ++end); //Exclude pivot

cilk_sync;

}

}

// A simple test harness

int qmain(int n)

{

int *a = new int[n];

for (int i = 0; i < n; i++)

a[i] = i;

std::random_shuffle(a, a + n);

std::cout << "Sorting " << n << " integers"

<< std::endl;

sample_qsort(a, a + n);

// Confirm that a is sorted and that each element contains the index

for (int i = 0; i < n-1; ++i) {

if (a[i] >= a[i+1] || a[i] != i) {

std::cout << "Sort failed at location i="

<< i << " a[i] ="

<< a[i] << " a[i+1] = " << a[i+1]

<< std::endl;

delete[] a;

return 1;

}

}

std::cout << "Sort succeeded." << std::endl;

delete[] a;

return 0;

}

int cilk_main(int argc, char* argv[])

{

int n = 10*1000*1000;

if (argc > 1)

n = std::atoi(argv[1]);

return qmain(n);

}

There is only one area to be concerned with and that is void_sample_qsort(int * begin, int * end) Since that is the function that when modified, the program hangs.

Any help appreciated.

2 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

void sample_qsort(int * begin, int * end) {
if (begin !=end) {
--end; // Exclude last element (pivot)
int * middle = std::partition(begin, end, std::bind2nd(std::less(), *end));
std::swap(*end, *middle); //pivot to middle
cilk_spawn sample_qsort(begin, middle);
sample_qsort(begin, middle);
sample_qsort(++middle, ++end); //Exclude pivot
cilk_sync;
}
}

The first thing is that you do not need to spawn sample_qsort(begin, middle) and then call sample_qsort(begin, middle), again. One of the nice things about Cilk is that you can visualize the semantics of the program by ignoring the Cilk keywords. Doing that, the program is calling sample_qsort() on the first portion of the space, twice. That might cause a program to take significantly longer to run.

Secondly, when parallelism is taken into account, the serial call to sample_qsort(begin, middle) will race with the parallel one. The two partition() calls will interact strangely, and I wouldn't be surprised if they caused an infinite loop.

Basically, remove the serial call to sample_qsort(begin, middle) and see if that works.

You can check how many cores your computer has by checking /proc/cpuinfo in Linux or by opening the Task Manager and clicking on the Performance tab in Windows.

Leave a Comment

Please sign in to add a comment. Not a member? Join today