WorkGraph execution policy

[hcedwar]

@ckrisgarrett : parallel pattern/policy useful for algorithms of type in https://github.com/lanl/tycho2

parallel_for( WorkGraph<Space> const &
            , KOKKOS_LAMBDA ( int i ) { ... } );

parallel_reduce( WorkGraph<Space> const &
               , KOKKOS_LAMBDA ( int i , double & update ) { ... }
               , result );

WorkGraph is a CRS graph that says the function can be called for row index i only after the
function has completed for the row's column indices. If multiple row indices can be called then
prioritize according to number of other rows waiting; e.g., if row 'i' has 4 waiting rows
and row 'j' has 2 waiting rows then choose row 'i' over row 'j'.
This prioritization attempts to clear dependences sooner and thus make more work available sooner.

Construct WorkGraph:

1. parallel_scan to determine the column lengths
2. parallel_for to populate column 'execute after' dependences

Primitive parallel pattern / policy for sweep algorithms.

Implementation:
Array of integers used for linked list queues of prioritized ready queues and waiting queues.
Atomically push and pop among queues as work items (indices) complete and pending work items are updated.

[hcedwar]

A potentially reusable implementation by the phalanx library is a work graph queue with lock free pop_ready and complete functions:

  while ( ! work.empty() ) {
    int n = work.pop_ready();
    // do work for 'n'
    work.complete( n );
  }

[hcedwar]

some thoughts on the queue

using p = pair<int32_t,int32_t> ;
int32_t pop()
{
  int volatile * const queue = ... ;
  p volatile * const range = ... ;
  p w(-1,-1);
  for ( int attempt = 1 ; attempt ; ) {
    const p w_new( w.first + 1 , w.second );
    w = CAS( range , w , w_new );
    if ( w.first < w.second ) { // range was viable
      // some work to pop, did I get it?
      attempt = ! ( w_new.first == w.first + 1 && w_new.second == w.second );
   }
   else { // currently nothing to pop, wait for some work
     attempt = w.first < total_work ;
   }
  }
  if ( w.first < total_work ) {
    int i = -1 ;
    while ( -1 == ( i = queue[ w.first ] ); // racing with push
    return i ;
  }
  else {
    return -1 ;
  }
}
void push( int32_t ready )
{
   p w(-1,-1);
   for ( int attempt = 1; attempt ; ) {
      const p w_new( w.first , w.second + 1 );
      w = CAS( range , w , w_new );
      attempt = ! ( w.first == w_new.first && w.second + 1 == w_new.second );
    }
    queue[ w.second ] = ready ;
    memory_fence();
}