HPC – NEO

A simple prototype

In the cluster, a Master – Slave structure set up. Master node responses to send the task to slave nodes and regularly check the status of all slave nodes(busy or idle). Salve nodes response to split task from master into sub tasks running with multi-threads.

Master node assigns tasks by iterating each row of the first column in the lattice. If all slave nodes are busy, master will waiting for feedback from slave nodes, otherwise master node will send the new task to the idle slave node.

Master node uses non-blocking method(Irecv) to get the feedback from slave node. So that master node is able to check status of all slave nodes as well as receive feedback.

Slave node splits task into subtask by iterating each row of the second column in the lattice, which is running in a dynamic schedule looping. So that each thread can keep busy all time.

Non-blocking MPI

pool[node] is used to record working slave nodes, wait[node] is used to record if MPI_Irecv is running for the working slave node. Then use MPI_Request_get_status to check the status of request.

//receive result from slave nodes for(int node=0; node < (num_nodes-1); node++){ if(pool[node]==1){ if(wait[node]==0){ MPI_Irecv(&node_solution[node], 1, MPI_INT, node+1, TAG, MPI_COMM_WORLD,&rq[node]); wait[node]=1; } MPI_Request_get_status(rq[node],&flag[node],NULL); if(flag[node]){ // printf("rec by node %d: %d - %d \n",row,node+1,node_solution[node]); total_solution += node_solution[node]; pool[node]=0; wait[node]=0; } } }

Defination of Mandelbort set

According to wiki, the Mandelbrot set is the set of complex numbers $c$ for which the function $f_{c}(z)=z^{2}+c$ does not diverge when iterated from $z=0$ .

What magic does it has

If we try to find the set of $c$ in a complex plane. Here is the magic:

where x axis is the real part of $c$ , y axis is the imaginary of $c$ . A point $c$ is colored black if it belongs to the set.

How to find set

here is the pseducode from wiki:

For each pixel (Px, Py) on the screen, do:
{
  x0 = scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))
  y0 = scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))
  x = 0.0
  y = 0.0
  iteration = 0
  max_iteration = 1000

  //when the sum of the squares of the real and imaginary parts exceed 4, the point has reached escape.
  while (x*x + y*y < 2*2  AND  iteration < max_iteration) {
    xtemp = x*x - y*y + x0
    y = 2*x*y + y0
    x = xtemp
    iteration = iteration + 1
  }
  color = palette[iteration]
  plot(Px, Py, color)
}

for complex numbers:

$z=x+iy$

$z^{2}=x^{2}+i2xy-y^{2}$

$c=x_{0}+iy_{0}$

Hence: x is sum of real parts in z and c, y is sum of imaginary parts of z and c. $x={Re}(z^{2}+c)=x^{2}-y^{2}+x_{0}$ and $y={Im}(z^{2}+c)=2xy+y_{0}$

How about 3D

I am going to try my 3D later, but please see the detail from skytopia firstly, I cited the formula directly.

3D formula is defined by:

$z -> z^n + c$ where z and c are defined by {x,y,z}


{x,y,z}^n = r^n { sin(theta*n) * cos(phi*n) , sin(theta*n) * sin(phi*n) , cos(theta*n) }

where
r = sqrt(x^2 + y^2 + z^2)
theta = atan2( sqrt(x^2+y^2), z )
phi = atan2(y,x)

// z^n + c is similar to standard complex addition

{x,y,z}+{a,b,c} = {x+a, y+b, z+c}

//The rest of the algorithm is similar to the 2D Mandelbrot!

//Here is some pseudo code of the above:

r = sqrt(x*x + y*y + z*z )
theta = atan2(sqrt(x*x + y*y) , z)
phi = atan2(y,x)

newx = r^n * sin(theta*n) * cos(phi*n)
newy = r^n * sin(theta*n) * sin(phi*n)
newz = r^n * cos(theta*n)

NEO_AKSA

Tag: HPC

MPI non-blocking receiving with OpenMP