Thinking Parallel

A Blog on Parallel Programming and Concurrency by Michael Suess

How to do it ONCE in OpenMP…

Time to write about some of the things I am doing at work again. As you may remember from my last article related to work, I am presently toying around with OpenMP and C++, trying to implement commonly used patterns there. What I want to write about today is not exactly a pattern, but rather a language feature OpenMP does not have – the ability to specify a function that is supposed to be carried out exactly once.

An important use case of this is e.g. initialization code. POSIX Threads has this feature (called pthread_once), as does e.g. Boost (call_once). OpenMP does have something similar, but not quite equivalent with the single-directive. This worksharing directive makes sure, that only one thread carries out the enclosed code. Why is this not the same? If the same single directive is encountered multiple times (e.g in a loop), the enclosed code will be carried out multiple times as well (which is not so good, when you want once-semantics). When nested parallelism comes into play, single does not preserve once-semantics as well. Of course, all of these cases can be worked around by the programmer, but the question I was asking myself is, can a library call provide an easy to use interface for once in OpenMP?

Not surprisingly, the answer is yes. Here is how it should work in principle:
Once
The caller and the callee are both written by the application programmer (that’s why they are in yellow), while the once-function is a library call that handles all the dirty details of making sure that the callee is actually called only once (in orange). The Once-Flag serves a double role: first of all, it is an implementation detail that cannot be managed by the library and is necessary to make sure everything works together. Secondly, it identifies which region to protect. If you happen to specify two different functions with the same OnceFlag, only one of the two will be called. Make sure it is static, at least when the caller itself may be called multiple times! Here is a short test-code that shows how it is used and that it actually works as intended:

< View plain text >
C++

  1. int g_i; /**< a global variable for testing */
  2.  
  3. /** a helper function - the callee in our example*/
  4. void OnceTester()
  5. {
  6.     #pragma omp atomic
  7.     ++g_i;
  8. }
  9.  
  10. /** Test for the once function.
  11.  * Makes sure, that the callee is called exactly once.
  12.  * This is what I have called the caller.
  13.  */
  14. void OnceTests::testOnceFP(void)
  15. {
  16.     static OnceFlag flag = OMPAT_ONCE_INIT;
  17.     g_i = 0;
  18.  
  19.     #pragma omp parallel num_threads (numthreads)
  20.     {
  21.         /* this function is called numthreads times by
  22.          * different threads here, still the callee should
  23.          * be called only once */
  24.         once(&OnceTester, flag);
  25.  
  26.         /* this barrier makes sure, that all threads see a
  27.          * current and defined value of g_i */
  28.         #pragma omp barrier
  29.         CPPUNIT_ASSERT_EQUAL(g_i, 1);
  30.  
  31.         /* call function once again, to make sure that the
  32.          * same thread does not call it twice (this
  33.          * is what single would do) */
  34.         once(&OnceTester, flag);
  35.         CPPUNIT_ASSERT_EQUAL(g_i, 1);
  36.     }
  37.     CPPUNIT_ASSERT_EQUAL(g_i, 1);
  38. }
  39. &#91;/cpp]
  40. Don't mind the CPP_ASSERTS, they are from the unit testing framework (<a href="http://sourceforge.net/projects/cppunit">CppUnit</a>) I use to test my code and can basically be read like simple assertions. And here is a short peak into the actual implementation of the once-function (beware that this does not run without some surrounding code!):
  41. [cpp]
  42. /** Makes sure a function is called only once.
  43. * More specific: the function is called exactly once
  44. * for each flag-variable that is supplied.
  45. * @param func a pointer to the function to be called
  46. * @param flag the flag that makes sure, the function is
  47. * called only once (do not change its value!)
  48. */
  49. void ompat::once (void (*func)(void), OnceFlag& flag)
  50. {  
  51.     /* #pragma omp flush(flag) would be sufficient here, but
  52.      * OpenMP does not allow to flush reference variables */
  53.     #pragma omp flush
  54.     if (flag == OMPAT_ONCE_INIT) {
  55.         #pragma omp critical (OMPAT_ONCE_FP)
  56.         {
  57.             /* the double check is necessary, because the
  58.              * value is not guaranteed to be even
  59.              * defined during the first check */
  60.             if (flag == OMPAT_ONCE_INIT) {
  61.                 flag = OMPAT_ONCE_CALLED;
  62.                 func ();
  63.             }
  64.         }
  65.     }
  66. }

This may not be so easy to understand, as you need some understanding about the OpenMP memory model (a topic which I have meant to blog about for a long time, but have not gotten around to – but I will get to it, I promise). But then again, it is not rocket science either :D.

This could basically close this article, were it not for a slight detail that bothered me: Do my initialization-functions (or any functions that I would want to call only once) never take any parameters?? I think they do. Still, with the solution presented above, it is not possible to pass a parameter to the specified function. Of course, there are several workarounds to this problem as well. One could just overload the once-function for each and every possible parameter type the called function might take. Not such a hot idea, when you want to use this often. Or you could use global variables for the parameters – what a horrible idea :-).

A saner (but still not really great) idea is to pass a void pointer to the function. Programmers can then create a structure with all the parameters as elements, fill it, and pass it as void pointer to the structure. The called function can then cast it back and unpack the parameters. If all we had was C, then this would be the way to go (pthread_create for example passes parameters to the function carried out by the newly created thread this way). I have implemented this as well, but I think I have showed you enough source code for one post already and will not bother you with it, but merely describe the ideas involved. Sooner or later I will release the code for anyone interested to play with anyways, but as long as its only a couple hundred documented lines of code, its not really worth the effort.

Where was I? Oh yes, parameters through void pointer. Besides being very C-ish, the solution has another problem: It is not type-safe. There is no way for the compiler to check in the callee, whether or not the passed structure is really of the specified type. Change the structure, change the caller and forget the callee and you will have a mistake that can be hard to spot and the compiler will not help you at all. This is error-prone and can be avoided in C++.

The solution (and the last version I want to bother you with 😉 ) employs function objects (short: functors). This is not a C++-Blog, therefore I will not explain what a functor is (check the Wikipedia for an explanation), but will instead show you really quick how the once-function can be called now:

< View plain text >
C++

  1. class OnceFunctor {
  2.   public:
  3.     int i;
  4.     void operator() () {
  5.         #pragma omp atomic
  6.         ++i;
  7.     }
  8. };
  9.  
  10. static OnceFlag flag = OMPAT_ONCE_INIT;
  11. OnceFunctor func;
  12.  
  13. func.i = 0;
  14. once(func, flag);

Any parameters the callee needs are now in the function object. The compiler can check at compile time, whether or not there are any type mismatches, even in the callee. So everyone is happy, as this is the perfect solution!

Or isn’t it? I believe it is as good as a library function can become presently (at least I think so, but maybe you have a bright idea?). But still, I have this thought in the back of my head, that it could also work like this:

< View plain text >
C++

  1. /* THIS IS NOT REAL OPENMP, BUT ONLY AN IDEA! */
  2. #pragma omp once (A_NAME)
  3. {
  4.     /* put whatever code you want carried out once here */
  5. }

No need to fiddle with static variables. No need to even put your code in a function, if you don’t want to. And should not be too difficult to implement in a compiler either. But will this be part of OpenMP sometime? I suspect not, because the need to call a function only once is not so great. And most of the time you can do it before your parallel region even starts and therefore make sure, the code in question is only carried out once. There are some edge-cases that would benefit from the functionality (if there weren’t, it would not be there in many threading systems). But it is not a really pressing need and therefore it will probably stay an academic exercise for now…

By: Michael Suess | 2006/09/20 | OpenMP - Parallel Programming | Trackback | Comments [RSS 2.0]

Comments are closed



My other projects: Michael Suess | Günstiges Webhosting in den USA
WP Theme "Fast Lane" originally designed by: beng hafner