Difference between pages "Template:ElementTypeCommunication" and "Prime factorization"

From Mesham
(Difference between pages)
Jump to navigationJump to search
 
(Download)
 
Line 1: Line 1:
When a variable is assigned to another, depending on where each variable is allocated to, there may be communication required to achieve this assignment. Table \ref{tab:eltypecomm} details the communication rules in the assignment \emph{assignmed variable := assigning variable}. If the communication is issued from MPMD programming style then this will be one sided. The default communication listed here is guaranteed to be safe, which may result in a small performance hit.
+
== Overview ==
  
 +
This example will perform prime factorization on a number parallely, to return the prime factors which make up that number. The example uses the primitive communication, all reduce. There are actually a number of ways such a result can be obtained - this example is a simple parallel algorithm for this job.
  
{| border="1" cellspacing="0" cellpadding="5" align="center"
+
== Source Code ==
! Assigned Variable
 
! Assigning Variable
 
! Semantics
 
|-
 
| multiple[]
 
| multiple[]
 
| local assignment
 
|-
 
| single[on[i]]
 
| multiple[]
 
| individual processes write values to process i
 
|-
 
| multiple[]
 
| single[on[i]]
 
| individual processes read values from process i
 
|-
 
| single[on[i]]
 
| single[on[i]]
 
| local assignment where i==i
 
|-
 
| single[on[i]]
 
| single[on[j]]
 
| communication from j to i where i!=j
 
|}
 
  
==== Communication Example ====
+
var n:=976; // this is the number to factorize
 
+
  var m:=12; // number of processes
  var a:Int;
+
  var s:Int :: allocated[multiple[]];
  var b:Int :: allocated[single[on[2]]];
 
 
  var p;
 
  var p;
  par p from 0 to 3 {
+
  par p from 0 to m - 1
    if (p==2) b:=p;
+
{
    a:=b;
+
  var k:=p;
    sync;
+
  var divisor;
 +
  var quotient:Int;
 +
  while (n > 1)
 +
  {
 +
      divisor:= getprime[k];
 +
      quotient:= n % divisor;
 +
      var remainder:= mod[n,divisor];
 +
      if (remainder == 0)
 +
      {
 +
        n:=quotient;
 +
      } else {
 +
        k:=k + m;
 +
      };
 +
      (s :: allreduce["min"]):=n;
 +
      if ((s==n) && (quotient==n))
 +
      {
 +
        print[divisor,","];
 +
      };
 +
      n:=s;
 +
  };
 
  };
 
  };
  
 +
== Notes ==
 +
 +
Note how we have typed the quotient to be an integer - this means that the division n % divisor will throw away the remainder. Also, for the assignment s:=n, we have typed s to be an allreduce communication primitive (resulting in the MPI all reduce command.) However, later on we use s as a normal variable in the assignment n:=s due to the typing for the previous assignment being temporary.
 +
 +
As an exercise, the example could be extended so that the user provides the number either by command line arguments or via program input.
 +
 +
== Download ==
  
This code will result in each process reading the value of ''b'' from process 2  and then writing this into ''a''. As already noted, in absence of allocation information the default of allocating to all processes is used. In this example the variable ''a'' can be assumed to additionally have the type ''allocated[multiple]''.
+
You can download the prime factorization source code [http://www.mesham.com/downloads/fact.mesh here]

Revision as of 17:26, 11 January 2010

Overview

This example will perform prime factorization on a number parallely, to return the prime factors which make up that number. The example uses the primitive communication, all reduce. There are actually a number of ways such a result can be obtained - this example is a simple parallel algorithm for this job.

Source Code

var n:=976; // this is the number to factorize
var m:=12; // number of processes
var s:Int :: allocated[multiple[]];
var p;
par p from 0 to m - 1
{
  var k:=p;
  var divisor;
  var quotient:Int;
  while (n > 1)
  {
     divisor:= getprime[k];
     quotient:= n % divisor;
     var remainder:= mod[n,divisor];
     if (remainder == 0)
     {
        n:=quotient;
     } else {
        k:=k + m;
     };
     (s :: allreduce["min"]):=n;
     if ((s==n) && (quotient==n))
     {
        print[divisor,","];
     };
     n:=s;
  };
};

Notes

Note how we have typed the quotient to be an integer - this means that the division n % divisor will throw away the remainder. Also, for the assignment s:=n, we have typed s to be an allreduce communication primitive (resulting in the MPI all reduce command.) However, later on we use s as a normal variable in the assignment n:=s due to the typing for the previous assignment being temporary.

As an exercise, the example could be extended so that the user provides the number either by command line arguments or via program input.

Download

You can download the prime factorization source code here