Difference between revisions of "Prefix sums"

From Mesham
Jump to navigationJump to search
m (8 revisions imported)
 
(5 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
== Source Code ==
 
== Source Code ==
  
  function void main[var arga,var argb]
+
#include <maths>
{
+
#include <io>
  var m:=10;
+
#include <string>
  var a:Int :: allocated[multiple[]];
+
  var p;
+
var processes:=10;
  par p from 0 to m - 1
+
  {
+
  function void main(var argc:Int,var argv:array[String]) {
    var mine:Int;
+
    var a:Int :: allocated[multiple[]];
    mine:= randomnumber[0,toInt[argb#1]];
+
    var p;
    var i;
+
    par p from 0 to processes - 1 {
    for i from 0 to m - 1
+
      var mine:Int; // Force to be an integer as randomnumber function defaults to double
    {
+
      mine:= randomnumber(0,toint(argv[1]));
      var myvalue:=mine;
+
      var i;
      if (i < p) myvalue:=0;
+
      for i from 0 to processes - 1 {
      (a :: reduce[i, "sum"]):=myvalue;
+
          var myvalue:=mine;
 +
          if (i < p) myvalue:=0;
 +
          (a :: reduce[i, "sum"]):=myvalue;
 +
      };
 +
      print(itostring(p)+" "+itostring(mine)+" = "+itostring(a)+"\n");
 
     };
 
     };
    print[p," = ",a,"\n"];
 
  };
 
 
  };
 
  };
 +
 +
''This code requires at least Mesham version 1.0''
  
 
== Notes ==
 
== Notes ==
  
The function main has been included here so that the user can provide, via command line options, the range of the random number to find. The complexity of the prefix sums is taken away by using the reduce primitive communication type.  
+
The user can provide, via command line options, the range of the random number to find. The (relative) complexity of the prefix sums is taken away by using the reduce primitive communication type.
  
 
== Download ==
 
== Download ==
  
Download the entire prefix sums source code [http://www.mesham.com/downloads/prefix.mesh here]
+
Download the entire prefix sums source code [http://www.mesham.com/downloads/prefix.mesh here] you can also download a legacy version for Mesham 0.5 [http://www.mesham.com/downloads/prefix-0.5.mesh here]
 +
 
 +
[[Category:Example Codes]]

Latest revision as of 15:44, 15 April 2019

Overview

Prefix sums is a very simple, basic parallel algorithm commonly used as the building block of many applications. Also known as a scan, each process will sumate their value with every preceding processes' value. For instance, p=0 returns its value, p=1 returns p=1 + p=0 values, p=2 returns p=2 + p=1 + p=0 values. The MPI reduce command often implements the communication via the logarithmic structure shown below.

Source Code

#include <maths>
#include <io>
#include <string>

var processes:=10;

function void main(var argc:Int,var argv:array[String]) {
   var a:Int :: allocated[multiple[]];
   var p;
   par p from 0 to processes - 1 {
      var mine:Int;	// Force to be an integer as randomnumber function defaults to double
      mine:= randomnumber(0,toint(argv[1]));
      var i;
      for i from 0 to processes - 1 {
         var myvalue:=mine;
         if (i < p) myvalue:=0;
         (a :: reduce[i, "sum"]):=myvalue;
      };		
      print(itostring(p)+" "+itostring(mine)+" = "+itostring(a)+"\n");
   };
};

This code requires at least Mesham version 1.0

Notes

The user can provide, via command line options, the range of the random number to find. The (relative) complexity of the prefix sums is taken away by using the reduce primitive communication type.

Download

Download the entire prefix sums source code here you can also download a legacy version for Mesham 0.5 here