Print indd

3
The GNU OpenMP Synchronization Barrier
Mechanism
OpenMP is a library designed to help users to develop parallel software by adding
an abstraction layer over the classic parallel services (threads management, syn-
chronization mechanisms, ...). In this section, we present the key principles of
this library.
3.1
Code Parallelization and Synchronization
The Listing
1.1
exposes an example of a simple “high abstraction level” code.
Listing 1.1. Original high level C code with openMP directives
1
#i n c l u d e <omp . h>
2
#d e f i n e TAB SIZE 10 00
3
i n t
main (
v o i d
)
{
4
u n s i g n e d
i n t
n =0;
5
u n s i g n e d
i n t
s i n T a b l e [ TAB SIZE ] ;
6
o m p s e t n u m t h r e a d s ( 1 6 ) ;
7
#pragma omp p a r a l l e l
f o r
s h a r e d
( s i n T a b l e )
8
f o r
( n =0; n<TAB SIZE ; n++)
9
s i n T a b l e [ n ] = n
∗ 2 ;
10
p r i n t t a b l e ( s i n T a b l e ) ;
11
r e t u r n
1 ;
}

---

60
M. France-Pillois et al.
The aim of this program is to compute the elements of an array (line 9) then to
display them (line 10). The array computation is parallelized into sixteen threads
thanks to the OpenMP directives lines 6 and 7. During the compilation phase
OpenMP directives are interpreted by the compiler, and the code is expanded with
threads creation and management services. In our example, the
for loop will be
replaced by the creation of sixteen threads. Each thread processing one sixteenth
of the array. The OpenMP library inserts also a synchronization barrier after the
parallel loop (between lines 9 and 10) in order to wait for the completion of all
thread computations before going forward to the display of the array (line 10).
The display of the array is processed by only one thread (the main thread) since
the parallel section ends with the end of the for loop.
At first sight, in this example, we note the heavy impact of synchronization
mechanisms on parallelized code since the OpenMP library inserts a synchro-
nization barrier at the end of each parallel section.
Delays introduced by synchronization mechanisms are of two kinds. (1) Appli-
cation dependent delays which are most of the time due to bad load balancing.
In our barrier example, all the tasks have to wait for the slowest to complete its
computation, which can lead to inefficient use of computing power and reduced
application performance. (2) Synchronization mechanisms intrinsic delays: delays
resulting from the establishment of the synchronization itself.
When we speak about synchronization optimization, we aim to reduce the
second type of delays since the first one, which is more a global application
optimization issue, is out of our scope of action.