Parallel Reduction and MapReduce

The following demonstrates using GPC API to parallelize the reduction algorithm by computing a sum in parallel (just for the illustration purpose). The image below depicts the computation flow with an assumption that the number of leaves is unknown in advance:

1. On the websqlgui.html page, click Services and then New File.
2. Enter the file name sum.js and click the OK button.
3. Add the following code to the file:

   (function() {
       var num = request.query("num");
       var mtx = mutex();
       var count = 0;
       while( count < num ) {
           // the map phase in parallel
           fork("/dosum.js", count, count, 1, mtx);
           count++;
       }
       if( count === 0 ){
           response.write("0");
           response.end();
           return;
       }
       var level = 0;
       while( count > 1 ) {
           level++;
           if( count & 1 ) {
               // every level of the reduction must have an even number of nodes
               fork("/dosum.js", 0, count, level, mtx);
               count++;
           }
           count /= 2;
       }
       // when the reduction is complete, respond with the result
       level++;
       join(mtx[level][0], function(state) {
           if( state.counter == 1 ) {
               // returning false means this callback function must be executed again after the next task on this mutex
               return false;
           }
           response.write(state.data);
           response.end();
       });
   }());
                   

4. Use Command+S (Mac) or Control+S (Win) to save the file on the server.
5. On the websqlgui.html page, click Services and then New File.
6. Enter the file name dosum.js and click the OK button.
7. Add the following code to the file:

   function dosum(state) {
       sum += state.data;
       if( state.counter == 2 ) {
           // after two nodes are merged, continue to the next level
           index = Math.floor(index / 2);
           join(mtx[++level][index], dosum);
       } else {
           state.data = sum;
       }
   }
   
   sum = $args[0];
   index = $args[1];
   level = $args[2];
   mtx = $args[3];
   index = Math.floor(index / 2);
   join(mtx[level][index], dosum);
                   

8. Use Command+S (Mac) or Control+S (Win) to save the file on the server.
9. In a browser, enter http://yourWebSqlServer/sum.jsx?num=4.
10. The browser will render "6".

See Also:

Concurrent, Parallel, Distributed