Changes between Version 28 and Version 29 of Next-GenOpenMPTransformation

Timestamp:

06/25/19 16:50:06 (7 years ago)

Author:

siegel

Comment:

--

Next-GenOpenMPTransformation

@@ -353 +353 @@
 * `void $omp_flush_all($omp_team)`
  * performs an OpenMP flush operation on all shared objects.  This is the default in OpenMP if no argument is specified for a flush construct.
+
+=== Worksharing and barriers ===
+
+* `void $omp_barrier($omp_team team)`
+ * performs a barrier only.  Note however that usually (always?) a barrier is accompanied by a flush-all, so `$omp_barrier_and_flush` should be used instead.
+
+* `void $omp_barrier_and_flush($omp_team team)`
+ * combines a barrier and a flush on all shared objects owned by the team.  Implicit in many OpenMP worksharing constructs.
+
+* `$domain $omp_arrive_loop($omp_team team, int location, $domain loop_dom,  $DecompositionStrategy strategy)`
+ * called by a thread when it reaches an omp for loop, this function returns the subset of the loop domain specifying the iterations that this thread will execute.  The dimension of the domain returned equals the dimension of the given domain `loop_dom`.
+
+* `$domain(1) $omp_arrive_sections($omp_team team, int location, int numSections)`
+ * called by a thread when it reaches an omp sections construct, this function returns the subset of the integers 0..numSections-1 specifying the indexes of the sections that this thread will execute.  The sections are numbered from 0 in increasing order.
+
+* `int $omp_arrive_single($omp_team team, int location)`
+ * called by a thread when it reaches on omp single construct, returns the thread ID of the thread that will execute the single construct.
+
+
+== Worksharing model ==
+
+This section describes how the system functions dealing with worksharing are implemented.
+
+The global data structure `$omp_gteam` contains a FIFO queue for each thread.   The queue contains work-sharing records, one record for each work-sharing or barrier construct encountered.    The record contains the basic information about the construct as provided by the arguments to the arrival function, as well as the distribution chosen for that thread. 
+
+The constructs are a lot like MPI collective operations, and are modeled similarly.
+
+When a thread arrives at one of these constructs, it invokes the relevant arrival function.  At this point you can determine whether this thread is the first to arrive at that construct.  If its queue is empty, it is the first, otherwise it is not first, and the oldest entry in its queue will be the entry corresponding to this construct.
+
+When a thread is the first thread to arrive at a construct, a distribution is chosen for every thread and a record is created and enqueued in each thread queue (including the caller).   The distributions can be chosen nondeterministically, possibly with some restrictions to achieve some tractability/soundness compromise.  The record for this thread is then dequeued and the iterator returned.
+
+If a thread is not the first to arrive, its record is dequeued and compared with the arguments given in the function call.  They should match, and if they don't, an error is reported.  This indicates that either threads encountered constructs in different orders or the loop parameters changed.
+
+
+== Translations of specific directives ==
+
+=== Translating `parallel` ===
+
+`parallel`: this spawns some nondeterministic number of threads.  We will assume there is a constant `THREAD_MAX` defined somewhere.  The number of threads created will be between 1 and `THREAD_MAX` (inclusive).  Each thread is assigned an ID.  The original ("master") thread has ID 0.  All threads execute the parallel region.
+
+{{{
+  float x; // shared
+  int y; // private
+  #pragma omp parallel shared(x) private(y)
+  {
+    ...
+    x=5.2;
+    y=3;
+   ...
+  }
+}}}
+
+=>
+
+{{{
+  float x;
+  int y;
+  { // begin parallel construct
+    int _nthreads = 1+$choose_int(THREAD_MAX);
+    $omp_gteam gteam = $omp_gteam_create($here, nthreads);
+    $omp_gshared x_gshared = $omp_gshared_create(gteam, &x);
+
+    $parfor (int _tid : {0..nthreads-1}) {
+      $omp_team team = $omp_team_create($here, gteam, _tid);
+      $omp_shared x_shared = $omp_shared_create(team, x_gshared);
+      int _y; // private variable
+
+      ...
+      { // "x=5.2":
+        float tmp = 5.2;
+  
+        $omp_write(x_shared, x_shared->local, &tmp);
+      }
+      _y = 3;
+      ...
+     $omp_barrier_and_flush(team); // implicit at end of parallel region
+     $omp_shared_destroy(x_shared);
+     $omp_team_destroy(team);
+    } // end $parfor
+    $omp_gshared_destroy(x_gshared);
+    $omp_gteam_destroy(gteam);
+  } // end parallel construct
+}}}
+
+All variables that occur in the parallel construct, i.e., the lexical extent of the parallel construct, must be determined to be either private or shared.   This is determined by the clauses and the default rules as specified in the OpenMP Standard.  Obviously any variable declared within the construct itself must be private.
+
+For all private variables `y` not declared within the parallel construct, create a new variable of the same type, `_y`.    The new variable is declared within the thread scope.  If `y` is also firstprivate,  then `_y` is initialized with the value of `y`, e.g. `int _y=y;`.  Otherwise, `_y` is uninitialized, so has an undefined value.
+
+=== Translating `for` ===
+
+Try to determine whether the loop iterations are independent.  In that case, they can all be executed by one thread.
+Otherwise:
+
+{{{
+#pragma omp for
+for (i=0; i<n; i++)  
+  S
+}}}
+
+=>
+
+{{{
+{
+  $domain loop_domain = {0..n-1};
+  $domain(1) my_iters = ($domain(1))$omp_arrive_loop(team, FOR_LOC++, loop_domain, STRATEGY);
+
+  $for (int i : my_iters) {
+    translate(S);
+  }
+  $barrier_and_flush(team);
+}
+}}}
+
+We can vary the way the sub-domains are chosen to explore different tradeoffs and strategies.  On one extreme, every kind of partition can be explored; on the other, some fixed strategy like round-robin with chunksize 1 can be used.  This only changes the definition of `$omp_arrive_loop`, not the translation above.
+
+{{{
+#pragma omp parallel for collapse(3)
+for (i=0; i<n; i++)
+  for (j=0; j<m; j++)
+    for (k=0; k<l; k++) {
+      S
+    }
+}}}
+
+=>
+
+{{{
+{
+  $domain loop_domain = {0..n-1, 0..m-1, 0..l-1};
+  $domain(3) my_iters = ($domain(3))$omp_arrive_loop(team, FOR_LOC++, loop_domain, STRATEGY);
+
+  $for (int i, j, k : my_iters) {
+    translate(S);
+  }
+  $omp_barrier_and_flush(team);
+}
+}}}
+
+=== Translating `reduction` clause ===
+
+{{{
+#pragma omp for reduction(+:x,y)
+for (i=a; i<b; i++) {
+  S
+}
+}}}
+
+=>
+
+The following translation assumes that $omp_shared has already been created somewhere.
+
+{{{
+{
+  $domain loop_domain = {a..b-1};
+  $domain(1) my_iters = ($domain(1))$omp_arrive_loop(team, FOR_LOC++, loop_domain, STRATEGY);
+  double _x=0.0, _y=0.0; // not the local view of the shared variable x/y
+
+  $for (int i : my_iters) {
+    translate(S) but replace x with _x and y with _y;
+  }
+  $omp_apply_assoc(x_shared, CIVL_SUM, &_x);
+  $omp_apply_assoc(y_shared, CIVL_SUM, &_y);
+  $omp_barrier_and_flush(team);
+}
+}}}
+
+
+
+=== Translating `sections` ===
+
+Say there are `numSections` sections.  This number is known statically.
+
+{{{
+#pragma omp sections
+#pragma omp section
+  S0
+#pragma omp section
+  S1
+...
+}}}
+
+=>
+
+{{{
+{
+  $domain(1) my_secs = $omp_arrive_sections(team, SEC_LOC++, numSections);
+
+  $for (int i : my_secs) {
+    switch (i) {
+    case 0: {
+      translate(S0);
+      break;
+    }
+    case 1: {
+      translate(S1);
+      break;
+    }
+    ...
+    } /* end of switch */
+  } /* end of $for loop */
+  $omp_barrier_and_flush();
+}
+}}}
+
+
+=== Translating `single` ===
+
+{{{
+#pragma omp single
+S
+}}}
+
+=>
+
+{{{
+int owner = $omp_arrive_single(team, SINGLE_LOC++);
+
+if (owner == _tid) {
+  translate(S);
+}
+$omp_barrier_and_flush(team);
+}}}
+
+
+=== Translating `barrier` ===
+
+{{{
+#pragma omp barrier
+}}}
+
+=>
+
+{{{
+$omp_barrier_and_flush(team);
+}}}
+
+=== Translating `critical` ===
+
+Basically, use a lock for each critical name, plus one for the "no name".  All threads must obtain lock to enter the critical section, then release it.
+I.e., if there are critical sections name a, b, and c, there should be global root-scope variables of boolean type named `_critical_noname`, `_critical_a`, etc.
+
+{{{
+#pragma omp critical(a)
+S
+}}}
+
+=>
+
+{{{
+...
+_Bool _critical_a = $false;
+.
+.
+.
+$when (!_critical_a) _critical_a=$true;
+translate(S);
+_critical_a=$false;
+}}}
+
+=== Translating `atomic` ===
+
+In general, reads and writes to shared variables will be processed using the protocols described above.  However if the operation occurs within an omp atomic construct, it is translated differently.
+
+TODO: need to look up the rules on the different flavors of atomics.
+
+If sequentially consistent atomic...
+
+If non-sequentially consistent atomic...
+
+
+===  Translating`ordered` ===
+
+This can only be used inside and OMP `for` loop in which the pragma used the `ordered` clause.  (Check that.)  It indicates that the specified region must be executed in iteration order. 
+
+In this case the system function must return an int iterator in which the ints occur in loop order.
+
+{{{
+#pragma omp for ordered
+for (i=a; i<b; i++) {
+  ...
+  #pragma omp ordered
+  S1
+  ...
+  #pragma omp ordered
+  S2
+  ...
+}
+}}}
+
+=>
+
+{{{
+{
+  $domain loop_domain = {a..b};
+  $domain(1) my_iters = ($domain(1))$omp_arrive_loop(team, FOR_LOC++, loop_domain, STRATEGY);
+  int order1=a, order2=a;
+
+  $for (int i : my_iters) {
+     ...
+    $when (order1==i) {
+      translate(S1);
+      order1++;
+    }
+      ...
+    $when (order2==i) {
+      translate(S2);
+      order2++;
+    }
+      ...
+  }
+}
+}}}
+
+=== Translating `master` ===
+
+{{{
+#pragma omp master
+S
+}}}
+
+=>
+
+{{{
+if (_tid == 0) {
+  translate(S);
+}
+}}}
+
+=== Translating `nowait` ===
+
+Just leave out the `$omp_barrier_and_flush` at the end of the translated construct.
+