3 ms·
Good introduction to using OpenMP for scientists, but I was confused by his terminology. He kept referring to his Python code also as the "pthreads" version, pr
by scott_s 15y ago
Good introduction to using OpenMP for scientists, but I was confused by his terminology. He kept referring to his Python code also as the "pthreads" version, presumably because Python was using Pthreads for the parallelism. That confused me, since I had assumed he meant that his "pthreads version" was C code only, that directly used the Pthreads API. It's worth nothing that gcc's OpenMP implementation is also using Pthreads.
edit: I think he's missing "count++" inside the inner if-statement in the "Amdahl" and "Using many..." sections.
edit the second: I also think he has an unnecessary critical section in the "Amdahl" section. Assuming the correction above, this should work:
#pragma omp parallel for private(count, target_index)
for (query_index=0; query_index<N; query_index++) {
count = 0;
for (target_index=query_index+1; target_index<N; target_index++) {
if (tanimoto(fingerprint[query_index], fingerprint[target_index]) >= threshold) {
count++;
#pragma omp critical (add_count)
counts[target_index]++;
}
}
counts[query_index] += count;
}
Because query_index is the induction variable for the outer-most loop, we know that only one thread will ever see any given value for it. In other words, the iteration space of query_index is completely partitioned among the threads. Hence, accessing an array using query_index still gives use independent iterations of the outer-most loop, and we don't need to wrap the array access using it in a critical section. The above is a more involved case of the canonical example:
#pragma omp parallel for
for (i = 0; i < N; ++i)
sum[i] = a[i] + b[i];
The iteration space for target_index is not completely partitioned, so the critical section is still needed.
- deleted 15y ago[deleted]
- dalke 15y agoHi scott_s. Taking your points in order; by "pthreads" I mean "built on top of the the POSIX thread library API, and available from any language which supports the API calls." While gcc may use POSIX threads for its implementation, they are not necessarily inter-compatible. For example, I found on my Mac that OpenMP dies with a segfault when used from a pthread. OpenMP also works with Microsoft's C++ compiler, while the available pthreads support for that OS is built on the actual native methods. I lack a better way to distinguish these two types of threading libraries, hence the confusion. Thanks for the corrections! I am indeed missing the count++, now fixed. My actual code, which I used to generate the numbers, was a bit more complicated and using it would obfuscate the points of the essay. You are absolutely right about how the second critical section is not needed! That could should only be executed 110,000 times, while in the worst case the other critical section is executed N*(N-1)/2 = 12 billion times, so I decided to not redo the timings. I've updated the document to point out that those were not needed, with a pointer to this thread.
- scott_s 15y agoAs a systems research guy - someone who implements the sorts of things you're using - I would recommend just calling it the "Python" version as the short name, and clarify that you are using Pthreads from within Python as needed. In that version, that you're using Python is the most interesting thing, since many languages have bindings for Pthreads.
- dalke 15y agoAs a Python guy, it's an API layer on top of POSIX threads organizing calls to a shared library extension written in C. Most of the time is spent in the C extension (max 10 seconds out of 130), so doesn't seem right to call it the "Python" version. In any case, the section is "using pthreads from Python" and the chart lists "Python/pthreads", so I think I labeled it well enough, and won't be making a change. (The point, after all, was to compare an OpenMP version to something which doesn't use OpenMP.)
- scott_s 15y agoPython is driving the program, and the threading library you're using provides its own abstractions on top of Pthreads itself. Pthreads has no concept of work pools - although many people end up implementing them when using Pthreads. Pthreads is a relatively low-level library that specifies how to create and join threads, and then provides mutexes and condition variables to synchronize across them. The threading library you're using hides all of that from you (which is a good thing!). Where the code spends most of its time isn't the important thing for classification. What's important is what decided the structure of your code? And that was the threading library as provided by Python, not Pthreads. In fact, the threading library you're using only incidentally uses Pthreads as their implementation mechanism, similar to how gcc's implementation of OpenMP only incidentally uses Pthreads.