Mandelbrot

Overview

The mandlebrot example will compute the Mandlebrot set over any number of processes. This is a set of points in the complex plane, the boundary of which forms a fractal. The mathematics, which are quite simple, behind the Mandlebrot computation really do not matter for our purposes. The important issue is that firstly the calculation is embrasingly parallel (i.e. simple and natural to parallelise) and secondly will produce an image which the user can identify with.

The algorithm itself is actually quite simple, with a relatively large proportion of it dealing with specific colourisation of the resulting fractal. The example on this page is purposly basic so that the potential programmer can understand it.

Performance

The Mandelbrot example was evaluated against one written in C-MPI on a super computing cluster. Below is the graph detailing the performance of such codes, due to the close performance of the codes when run on an initial number of processors was the same and as such not shown. Due to the embarrassingly parallel nature of this problem the advantages of using Mesham in terms of performance do not start to stand out until a large number of processors is reached.

Source Code

#include <io>
#include <string>

typevar pixel::=record["r",Int,"g",Int,"b",Int];

var pnum:=16; // number of processes to run this on
var hxres:=512;
var hyres:=512;
var magnify:=1;
var itermax:=1000;

function Int iteratePixel(var hy:Float, var hx:Float) {
   var cx:Double;
   cx:=((((hx / hxres) - 0.5) / magnify) * 3) - 0.7;
   var cy:Double;
   cy:=(((hy / hyres) - 0.5) / magnify) * 3;
   var x:Double;
   var y:Double;
   var iteration;
   for iteration from 1 to itermax {
      var xx:=((x * x) - (y * y)) + cx;
      y:= ((2 * x) * y) + cy;
      x:=xx;
      if (((x * x) + (y * y)) > 100) {
         return iteration;
      };
   };
   return -1;
};

function void main() {
   var mydata:array[pixel,hxres,hyres] :: allocated[single[on[0]]];
   var p;
   par p from 0 to pnum - 1 {
      var tempd:array[record["r",Int,"g",Int,"b",Int], hyres];
      var myStart:=p * (hyres / pnum);
      var hy:Float;
      for hy from myStart to (myStart +  (hyres / pnum)) - 1 {
         var hx;
         for hx from 0 to hxres - 1 {
            var iteration := iteratePixel(hy, hx);
            tempd[hx]:=determinePixelColour(iteration);
         };
         mydata[hy]:=tempd;
         sync mydata;
       };
   };
   proc 0 {
      createImageFile("picture.ppm", mydata);
   };
};

function pixel determinePixelColour(var iteration:Int) {
   var singlePixel:pixel;
   if (iteration > -1) {
      singlePixel.b:=(iteration * 10) + 100; 
      singlePixel.r:=(iteration * 3) + 50;
      singlePixel.g:=(iteration * 3)+ 50;
      if (iteration > 25) {
         singlePixel.b:=0;
         singlePixel.r:=(iteration * 10);
         singlePixel.g:=(iteration * 5);
       };
       if (singlePixel.b > 255) singlePixel.b:=255;
       if (singlePixel.r > 255) singlePixel.r:=255;
       if (singlePixel.g > 255) singlePixel.g:=255;
   } else {
      singlePixel.r:=0;
      singlePixel.g:=0;
      singlePixel.b:=0;
   };
   return singlePixel;
};

function void createImageFile(var name:String, var mydata:array[pixel,hxres,hyres]) {
   var file:=open(name,"w");
   writestring(file,"P6\n# CREATOR: LOGS Program\n");
   writestring(file,itostring(hyres));
   writestring(file," ");
   writestring(file,itostring(hxres));
   writestring(file,"\n255\n");
   // now write data into the file
   var j;
   for j from 0 to hyres - 1 {
      var i;
      for i from 0 to hxres - 1 {
         writebinary(file,mydata[j][i].r);
         writebinary(file,mydata[j][i].g);
         writebinary(file,mydata[j][i].b);
       };
   };
   close(file);
};

Notes

To change the number of processes, edit pnum. In order to change the size of the image edit hxres and hyres. The mandlebrot set will calculate up until itermax for each point, by increasing this value you will get a crisper image (but it will take much more time!) Lastly, the variable magnify will specify the magnification of the image - the value of 1 will generate the whole image and by increasing this image the computation is directed into working on a specific area in more detail.

Note: This example will produce an image in the Portable PixMap format (PPM), viewers of these on Unix based systems are easy to come by (i.e. eye of gnome) but on Windows are slightly more difficult. Windows users might want to rewrite some of the last bit on process 0 so that a BitMaP is created.

Download

You can download the Mandelbrot example here