coments from Tim

I liked the problem statement and the overall approach used in the solution section. The related patterns section near the end was Excellent!

The context section needs some work. Remember, the goal is to layout the problem and guide the reader to the solution. You open nicelly with this approach, but then leap to discussing how this pattern relatest to the other patterns. I'd leave that content for your later related patterns section.

I thoght the forces section was confustion. As i see it, you have one universal force (recurrsive splitting vs geometric decomposition) and three implementation forces (load balancing, granularity, and managing data dependencies. I'd make this more clear in the text of the forces. The implementation force you lable as number 3 seems to be a restatement of the first two implmentation forces. Am I missing something here?

In your examples section, I like the fact you are showing real code. But the code for the unsorted array problem is broken. I'll create working code for you and send you code to replace the code you are using. For the task parallel code, you defined your own code, but why not use tasking from OpenMP? Then people don't have to learn a made up syntax … they can use an established syntax?

Your known uses section needs some attention. I like a sentence or two for each item stating how it relates to this pattern. This is particularly important for Cilk since that's a programming language and not a application that uses this pattern.

Here is the program I suggest you for the example. It is correct OpenMP code for both versions of the problem

#include <stdio.h> #include <omp.h> #define N 131072

long search_geom(long Nlen, long *a, long key) {

  long count = 0;

  #pragma omp parallel reduction(+:count)
  {
     int num_threads = omp_get_num_threads();
     int ID          = omp_get_thread_num();
     int i;
     int istart = ID * N/num_threads;
     int iend   = (ID+1)*N/num_threads;

     if(ID == (num_threads-1)) iend = N;

     for (i=istart; i<iend; i++)
        if(a[i]==key) count++;
     
  }
  return count;

}

long search_recur(long Nlen, long *a, long key) {

  long count = 0;

  #pragma omp parallel reduction(+:count)
  {
     #pragma omp single 
         count = search(Nlen, a, key);
  }
  return count;

}

long search(long Nlen, long *a, long key) {

   long count1=0, count2=0, Nl2;

   if (Nlen == 2){
      if (*(a)   == key) count1=1;
      if (*(a+1) == key) count2=1;
      return count1+count2;
   }
   else {

      Nl2 = Nlen/2;
      
      #pragma omp task shared(count1)
          count1 = search(Nl2, a, key);
 
      #pragma omp task shared(count2)
          count2 = search(Nl2, a+Nl2, key);

      #pragma omp taskwait

       return count1+count2;
     }

}

static unsigned long long MULTIPLIER = 764261123; static unsigned long long PMOD = 2147483647; unsigned long long random_last = 42;

long random() {

  unsigned long long random_next;
  random_next = (unsigned long long)(( MULTIPLIER  * random_last)% PMOD);
  random_last = random_next;
  return (long) random_next;

} int main() {

 long a[N];
 int  i;
 double checksum, timepoint, time_geom, time_recur;
 long key = 42, nkey=0;

 for (i=0;i<N;i++) a[i] = random()%N;

   a[N%43] = key;      a[N%73] = key;    a[N%3] = key; 
 
 for (i=0, checksum=0.0;i<N;i++) checksum += (double) a[i];

 printf(" checksum = %f\n",checksum);

 timepoint = omp_get_wtime();

 nkey = search_geom(N, a, key);

 time_geom = omp_get_wtime() - timepoint;
 printf(" Found %d values in %f seconds\n",nkey, time_geom);
 for (i=0, checksum=0.0;i<N;i++) checksum += (double) a[i];
 printf(" checksum = %f\n",checksum);

 timepoint = omp_get_wtime();

 nkey = search_recur(N, a, key);

 time_recur = omp_get_wtime() - timepoint;
 printf(" Found %d values in %f seconds\n",nkey, time_recur);

}