Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/omarflor/public_html/lib/plugins/importoldchangelog/action.php on line 8

Strict Standards: Declaration of action_plugin_importoldindex::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/omarflor/public_html/lib/plugins/importoldindex/action.php on line 57

Strict Standards: Declaration of action_plugin_tag::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/omarflor/public_html/lib/plugins/tag/action.php on line 117

Warning: Cannot modify header information - headers already sent by (output started at /home/omarflor/public_html/lib/plugins/importoldchangelog/action.php:8) in /home/omarflor/public_html/inc/auth.php on line 313

Strict Standards: Only variables should be passed by reference in /home/omarflor/public_html/index.php on line 77

Warning: Cannot modify header information - headers already sent by (output started at /home/omarflor/public_html/lib/plugins/importoldchangelog/action.php:8) in /home/omarflor/public_html/inc/actions.php on line 163
parallel-mandelbrot-set [Omar U. Florez]

Mandelbrot Set

Displaying the Mandelbrot set is an example of how parallel algorithms can be applied to process SPMD (single-program, multiple-instruction) algorithms. SPMD problems consist on intended –or disconnected– computational processes that solve a general case.

In the case of the Mandelbrot set, each pixel is computed without information of neighboring pixels. Hence, distributed memory multiprocessors (multicomputers with message passing protocols) are appropriate.

We will first show a sequential program that creates a 512×512-pixel Mandelbrot image in PPM format and run it on one of the nodes in a multiprocessor server. Then, we will extend this program to evaluate the same image in a parallel fashion. We will see here some of the issues associated to parallel programs such as synchronization, load balance, and efficiency.

Sequential Mandelbrot Set

Experiments

time_responses

|# iterations | time response
|

64 0.170000
128 0.220000
256 0.280000
1024 0.750000
5000 3.120000
50000 29.920000

Effect of the number of iterations

When increasing the number of iterations per each pixel, we finally obtain an image with higher resolution. Although a visual inspection of these two images may help, we quantize the difference by substracting two images of and computing the norm of the resulting vector. Next figure shows these values by considering Maldelbrot images of 64, 128, 256, 1024, 5000, and 50000.

Code

C Code

g++ test_sequential_mandelbrot.cpp
./a.out > test_mandelbrot.PPM

Parallel Mandelbrot Set

Since each pixel in the Mandelbrot set is independently evaluated, a parallel algorithm can be used to reduce the linear trend we saw in the sequential version of the algorithm. Intuitively, we can assign rectangular regions of the matrix that that contains the Mandelbrot set to specific processors. Then, each slave processor solves one part of the general problem, return its result to the master processor, and finally the master collect the data and display the figure. However, since some areas of the Mandelbrot set are easier to evaluate, some processors will finish earlier than others. Nevertheless, we would like all processors finish together to achieve a 100 percent efficiency. In other words, we would like to optimize the balance of load assigned to each processor over time. In seek of that goal, we use a dynamic task assignment approach known as Work pool/Processor farms. Each processor computes the pixels values of one row of the containing matrix and once it finishes evaluating its row, it sends the result to the master, and receives a new row available. Then, the master processor dynamically assigns tasks to a set of idle slave processors.

void master()
{
	int number_processors;
	int count = X_RES; //the number of rows in the image
	int row = 0;
	MPI_Status status;
	MPI_Comm_size(MPI_COMM_WORLD, &number_processors);
	int canvas[X_RES][Y_RES];
	int color[Y_RES]; 	
	
	//sending tasks to all the processors
	for(int i=1; i<number_processors; i++)
	{
		//send row and slave_id
		MPI_Send(&row, 1, MPI_INT, i, DATA_TAG, MPI_COMM_WORLD);			
		count--;
		row++;
		printf("%d\n", count);
	}
	
	
	printf("%d\n", count);
	//when slaves are idle, then keep sending		
	do
	{
		//color contains the values for the row colors
		MPI_Recv(color, Y_RES, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
		//row is row id in the canvas
		MPI_Recv(&row, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);			
		//slave_id is the proccesor that is idle now			
		//count++;
		
		printf("We received\n");
		if(row<X_RES)
		{
			for(int i=0; i<Y_RES; i++)
			{
				canvas[row][i] = color[i];
			}
			MPI_Send(&row, 1, MPI_INT, status.MPI_SOURCE, DATA_TAG, MPI_COMM_WORLD);
			count--; //minus one row processed			
			row++;
			printf("%d\n", count);
		}
		else
		{
			for(int i=0; i<number_processors; i++)
			{
				MPI_Send(0, 0, MPI_INT, i, TERMINATE_TAG, MPI_COMM_WORLD);
				
			}
		}
	}while(count>0);
	
	print_canvas(canvas);
}
void slave()
{
	float real_min=-2, imag_min = -2;
	float real_max=2, imag_max = 2;
	float scale_real = (real_max - real_min)/X_RES;
	float scale_imag = (imag_max - imag_min)/Y_RES;		  
	
	int canvas [X_RES][Y_RES];
	int color[Y_RES]; 	//it will be iteratively updated by a slave processor
				//Y_RES: number of columns in tha array
	int row;
	MPI_Status status;

	//color contains the values for the row colors
	MPI_Recv(&row, X_RES, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
			
	while(status.MPI_TAG==DATA_TAG)
	{
		//let's compute a row of the canvas
		int i = row;
		//c.real = j;
	        //c.imag = i;	         
	        //Y_RES lies on the x-axis!!       
		printf("++ We start the row\n");
		for(int j=0; j<Y_RES; i++)
	        {	                
			complex c;	                	
			c.real = real_min + ((float) j*scale_real);	
			c.imag = imag_min + ((float) i*scale_imag);
	            	color[j] = cal_pixel(c);    
		}	
		printf("++ We finish the row\n");
		MPI_Send(color, Y_RES, MPI_INT, 0, RESULT_TAG, MPI_COMM_WORLD);
		MPI_Send(&row, 1, MPI_INT, 0, RESULT_TAG, MPI_COMM_WORLD);
		MPI_Recv(&row, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
		printf("row: %d\n", row);
	}	
	
	if(status.MPI_TAG==TERMINATE_TAG)		
	{
		return;
	}

}
int main( int argc, char *argv[] )
{
	int rank;	
	//////////////////////////////////////////////////////
	
	MPI_Init(&argc, &argv );
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	
	if(rank==0) //MASTER
	{	
		master();
	}
	else //SLAVE
	{
		slave();
	}

	MPI_Finalize();
	return 0;
}
Experiments

time_responses (number of processors: 6)

|# iterations | time response
|

64 0.110000
128 0.180000
256 0.270000
1024 0.620000
5000 2.620000
50000 16.420000

Code

C Code with Message Passing Interface (MPI) library

lamboot /etc/lamhosts
mpiCC parallel_mandelbrot.cpp 
mpirun -v C ./a.out > test_mandelbrlt.PPM
lamhalt

More visualizations

Omar U. Florez 2009/03/06 14:40

 
parallel-mandelbrot-set.txt · Last modified: 2009/03/06 21:11 by omarflorez     Back to top
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki Design by Chirripó

Strict Standards: Only variables should be passed by reference in /home/omarflor/public_html/index.php on line 85