CSC/ECE 506 Spring 2011/ch4a ob - Revision history

Admin: /* Pseudocode for Serial Simplex Method */

2011-04-12T17:07:39Z

Pseudocode for Serial Simplex Method

← Older revision		Revision as of 17:07, 12 April 2011
Line 52:		Line 52:
	Shown below is an example pseudo code for the Serial Nelder-Mead Algorithm.		Shown below is an example pseudo code for the Serial Nelder-Mead Algorithm.

	===~~Pseudo Code~~ for Serial Simplex Method===		===Pseudocode for Serial Simplex Method===
	<pre>		<pre>
	int N;		int N;

Oabapat: /* Message Passing Implementation */

2011-04-11T21:17:32Z

Message Passing Implementation

← Older revision		Revision as of 21:17, 11 April 2011
Line 406:		Line 406:
	}		}
	</pre>		</pre>

	~~Similar method can be used to parallelize all the other functions like sorting and new point calculation.~~

	=Conclusion=		=Conclusion=

Oabapat: /* Shared Memory Implementation */

2011-04-11T21:17:18Z

Shared Memory Implementation

← Older revision		Revision as of 21:17, 11 April 2011
Line 316:		Line 316:
	}		}
	</pre>		</pre>

	~~Similar method can be used to parallelize all the other functions like sorting and new point calculation.~~

	===Message Passing Implementation===		===Message Passing Implementation===

Oabapat: /* Single Step of the Nelder-Mead Algorithm */

2011-04-11T21:15:18Z

Single Step of the Nelder-Mead Algorithm

← Older revision		Revision as of 21:15, 11 April 2011
Line 21:		Line 21:
	After ordering, we calculate the centroid of all but the worst point <tt>Xn</tt> in the current simplex.		After ordering, we calculate the centroid of all but the worst point <tt>Xn</tt> in the current simplex.

	~~<math>~~Xcen = 1/N summation(Xi) ~~</math>~~ for i = 0,1 .... N-1		Xcen = 1/N summation(Xi) for i = 0,1 .... N-1

	*Reflection		*Reflection

Oabapat: /* Conclusion */

2011-04-11T18:15:13Z

Conclusion

← Older revision		Revision as of 18:15, 11 April 2011
Line 412:		Line 412:

	=Conclusion=		=Conclusion=
	We have seen here that a highly serial algorithm like Nelder Mead can be parallelized using various methods. The most efficient approach to this would be to parallelize it at algorithmic level first, which provides faster convergence. Once ~~this~~ is done, ~~the~~ individual tasks can be parallelized using any of the methods described above, depending on the underlying hardware available.		We have seen here that a highly serial algorithm like Nelder Mead can be parallelized using various methods. The most efficient approach to this would be to parallelize it at algorithmic level first, which provides faster convergence. For any program or application, choice of algorithm (efficiency, run time, memory usage) is most important to performance. A poor choice of algorithm will give sub standard performance compared to a good algorithm, assuming both of them are parallelized at task level.

			Once algorithm level parallelization is done, individual tasks can be parallelized using any of the methods described above, depending on the underlying hardware available. Data parallel implementation is suitable for vector processors or GPUs while the shared memory implementation can be used with any bus based or distributed shared memory system. The message passing model has lot of communication overhead but does not need a shared memory between processors.

	=References=		=References=

Oabapat: /* Introduction */

2011-04-11T18:07:46Z

Introduction

← Older revision		Revision as of 18:07, 11 April 2011
Line 2:		Line 2:
	The [http://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method Nelder-Mead Algorithm] is a [http://en.wikipedia.org/wiki/Simplex simplex] method for function minimization developed by J. A. Nelder and R. Mead in 1965<sup><span id="2body">[[#2foot\|[2]]]</span></sup>. The method is used for minimizing an <tt>N</tt> dimensional function, by comparing the function values at <tt>n+1</tt> vertices of a [http://en.wikipedia.org/wiki/Simplex simplex], followed by the replacement of the vertex with highest function value by another vertex having a lower function value. The algorithm, by itself is highly serial in nature.		The [http://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method Nelder-Mead Algorithm] is a [http://en.wikipedia.org/wiki/Simplex simplex] method for function minimization developed by J. A. Nelder and R. Mead in 1965<sup><span id="2body">[[#2foot\|[2]]]</span></sup>. The method is used for minimizing an <tt>N</tt> dimensional function, by comparing the function values at <tt>n+1</tt> vertices of a [http://en.wikipedia.org/wiki/Simplex simplex], followed by the replacement of the vertex with highest function value by another vertex having a lower function value. The algorithm, by itself is highly serial in nature.

	In this article, we will discuss the Serial Nelder-Mead Algorithm and its parallelization at Algorithmic level and Task Level. For the Algorithmic level parallelism, we will look at a method to replace more than one point from the simplex in a single iteration. For task level parallelism, we will pick individual tasks from the algorithm and try to parallelize them using methods like data parallel programming, shared memory programming and message passing.		In this article, we will discuss the Serial Nelder-Mead Algorithm and its parallelization at Algorithmic level and Task Level. For the Algorithmic level parallelism, we will look at a method to replace more than one point from the simplex in a single iteration. For task level parallelism, we will pick individual tasks from the algorithm and try to parallelize them using methods like data parallel programming, shared memory programming and message passing. The choice of methods for task level parallelism largely depends on the underlying hardware and the computation / communication overhead for each of the methods.

	The figure below demonstrates how Nelder-Mead minimizes a two dimensional [http://en.wikipedia.org/wiki/Rosenbrock_function banana function] using a 3 point simplex.		The figure below demonstrates how Nelder-Mead minimizes a two dimensional [http://en.wikipedia.org/wiki/Rosenbrock_function banana function] using a 3 point simplex.

Oabapat: /* Shared Memory Implementation */

2011-04-11T17:43:50Z

Shared Memory Implementation

← Older revision		Revision as of 17:43, 11 April 2011
Line 216:		Line 216:
	===Shared Memory Implementation===		===Shared Memory Implementation===
	In the [http://en.wikipedia.org/wiki/Shared_memory shared memory] implementation of the algorithm, we use lock () and unlock () commands to make sure that multiple threads do not write to the same memory location at a given time. Only one thread can be in the [http://en.wikipedia.org/wiki/Critical_section critical section] of the program at a given time.		In the [http://en.wikipedia.org/wiki/Shared_memory shared memory] implementation of the algorithm, we use lock () and unlock () commands to make sure that multiple threads do not write to the same memory location at a given time. Only one thread can be in the [http://en.wikipedia.org/wiki/Critical_section critical section] of the program at a given time.
	Let us ~~take an example of the function to calculate~~ the centroid and ~~parallelize it~~. As shown in the code below, ~~The centroid array needs~~ to be a shared ~~variable~~ since multiple threads will be updating it. We use a lock and unlock around it so that no more than one thread tries to modify it at the same time. After waiting for all the updates from different [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 threads] to be done, we proceed ahead.		Let us parallelize the sorting, centroid calculation and next point calculation functions. As shown in the code below, the arrays for all the variables need to be shared since multiple threads will be updating it. We use a lock and unlock around it so that no more than one thread tries to modify it at the same time. After waiting for all the updates from different [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 threads] to be done, we proceed ahead.

	<pre>		<pre>

Oabapat: /* Message Passing Implementation */

2011-04-11T17:42:07Z

Message Passing Implementation

← Older revision		Revision as of 17:42, 11 April 2011
Line 320:		Line 320:

	===Message Passing Implementation===		===Message Passing Implementation===
	In [http://en.wikipedia.org/wiki/Message_passing Message passing] , thread division would be similar to that of the shared memory model, except that each thread has its own private memory and data updates are made by messaging~~, Lets consider the centroid function once again~~. Here, ~~<tt>myXcen</tt> variable~~ for each thread will be updated by values received from other threads and each thread will send its own updated value to the others.		In [http://en.wikipedia.org/wiki/Message_passing Message passing] , thread division would be similar to that of the shared memory model, except that each thread has its own private memory and data updates are made by messaging. Here, private variables for each thread will be updated by values received from other threads and each thread will send its own updated value to the others.

	<pre>		<pre>

			// processes do not complete till all the receives are done. Sends are asynchronous.

	Sort_Simplex()		Sort_Simplex()
	{		{
	~~DECOMP X[i] (CYCLIC~~,*,Nprocs) // ~~decompose into tasks for~~ each ~~processor~~		// break sorting calculation to P threads,
	sort ~~X[i]~~ in ascending order of f(x) (function to be minimized)		// each thread sorts an array N+1 / P points
	~~MERGE sorted outputs of~~ all ~~processors~~ // using ~~any merge-~~sort ~~algorithm~~		for_each_thread
			sort myX in ascending order of f(x[i]) (function to be minimized)

			SEND(X, to all other procs) // update centroid using the value from each thread
			X = MERGE and sort { X, myX};
			RECEIVE(X, from all other procs);


	}		}

Line 335:		Line 343:
	Calculate_new_point()		Calculate_new_point()
	{		{
			// break all calculations to P threads,
			// each thread working on N+1 / P points
	// reflection		// reflection
	~~DECOMP Xr[i] (CYCLIC, Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N do
	~~for_all~~ i = 0 thru N do		myXr[i] = (1+alpha)Xcen[i] – alpha*X[N][i];
	Xr[i] = (1+alpha)Xcen[i] – alpha*X[N][i];

			SEND(Xr[i], to all other procs) // update centroid using the value from each thread
			myXr[i] += Xr[i];
			RECEIVE(Xr[i], from all other procs);

	// expansion		// expansion
	~~DECOMP Xe[i] (CYCLIC, Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N do
	~~for_all~~ i = 0 thru N do		myXe[i] = gamma*Xr[i] + (1- gamma)Xcen[i];
	Xe[i] = gamma*Xr[i] + (1- gamma)Xcen[i];
			SEND(Xe[i], to all other procs) // update centroid using the value from each thread
			myXe[i] += Xe[i];
			RECEIVE(Xe[i], from all other procs);

	//contraction		//contraction
	~~DECOMP Xc[i] (CYCLIC, Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N do
	~~for_all~~ i = 0 thru N do		myXc[i] = beta*X[N][i] + (1- beta)Xcen[i];
	Xc[i] = beta*X[N][i] + (1- beta)Xcen[i];

			SEND(Xc[i], to all other procs) // update centroid using the value from each thread
			myXc[i] += Xc[i];
			RECEIVE(Xc[i], from all other procs);


	// accept one of the points based on their function values		// accept one of the points based on their function values
Line 356:		Line 375:
	// If none of the values is better, shrink or reduce the simplex based on X0		// If none of the values is better, shrink or reduce the simplex based on X0

	~~DECOMP X[i][j](CYCLIC,*,Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N-1 do
	~~for_all~~ i = 0 thru N-1 do		for_each_thread j = 0 thru N do
	~~DECOMP X[i][j](*,CYCLIC, Nprocs) // decompose into tasks for each processor~~		myX[i][j] = X[0][j] + gamma(X[i][j] – X[i][0]);
	~~for_all~~ j = 0 thru N do		end_for
	X[i][j] = X[0][j] + gamma(X[i][j] – X[i][0]);		end_for
	~~end_for_all~~
	~~end_for_all~~		SEND(X[i][j], to all other procs) // update centroid using the value from each thread
			myX[i][j] += X[i][j];
			RECEIVE (X[i][j], from all other procs);

	}		}

Oabapat: /* Shared Memory Implementation */

2011-04-11T17:35:36Z

Shared Memory Implementation

← Older revision		Revision as of 17:35, 11 April 2011
Line 221:		Line 221:

	shared float Xcen[N];		shared float Xcen[N];
			shared float Xr[N];
			shared float Xe[N];
			shared float Xc[N];
			shared float X[N+1][N];

	Sort_Simplex()		Sort_Simplex()
	{		{
	~~DECOMP X[i] (CYCLIC~~,*,Nprocs) // ~~decompose into tasks for~~ each ~~processor~~		// break sorting calculation to P threads,
	sort ~~X[i]~~ in ascending order of f(x) (function to be minimized)		// each thread sorts an array N+1 / P points
	~~MERGE sorted outputs of all processors~~ // using ~~any merge~~-~~sort algorithm~~		for_each_thread
			sort myX in ascending order of f(x[i]) (function to be minimized)

			LOCK(X) // update centroid using the value from each thread
			X = MERGE and sort { X, myX};
			UNLOCK(X);

			WAIT_FOR_END(nprocs-1); // wait till entire array gets sorted

	}		}

Line 232:		Line 244:
	Calculate_new_point()		Calculate_new_point()
	{		{
			// break all calculations to P threads,
			// each thread working on N+1 / P points
	// reflection		// reflection
	~~DECOMP Xr[i] (CYCLIC, Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N do
	~~for_all~~ i = 0 thru N do		myXr[i] = (1+alpha)Xcen[i] – alpha*X[N][i];
	Xr[i] = (1+alpha)Xcen[i] – alpha*X[N][i];

			LOCK(Xr[i]) // update centroid using the value from each thread
			myXr[i] += myXr[i];
			UNLOCK(Xr[i]);

	// expansion		// expansion
	~~DECOMP Xe[i] (CYCLIC, Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N do
	~~for_all~~ i = 0 thru N do		myXe[i] = gamma*Xr[i] + (1- gamma)Xcen[i];
	Xe[i] = gamma*Xr[i] + (1- gamma)Xcen[i];
			LOCK(Xe[i]) // update centroid using the value from each thread
			myXe[i] += myXe[i];
			UNLOCK(Xe[i]);

	//contraction		//contraction
	~~DECOMP Xc[i] (CYCLIC, Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N do
	~~for_all~~ i = 0 thru N do		myXc[i] = beta*X[N][i] + (1- beta)Xcen[i];
	Xc[i] = beta*X[N][i] + (1- beta)Xcen[i];
			LOCK(Xc[i]) // update centroid using the value from each thread
			myXc[i] += myXc[i];
			UNLOCK(Xc[i]);


			WAIT_FOR_END(nprocs-1); // we wait for all threads to update all points

	// accept one of the points based on their function values		// accept one of the points based on their function values
Line 253:		Line 278:
	// If none of the values is better, shrink or reduce the simplex based on X0		// If none of the values is better, shrink or reduce the simplex based on X0

	~~DECOMP X[i][j](CYCLIC,*,Nprocs) // decompose into tasks for each processor~~		for_each_thread i = 0 thru N-1 do
	~~for_all~~ i = 0 thru N-1 do		for_each_thread j = 0 thru N do
	~~DECOMP X[i][j](*,CYCLIC, Nprocs) // decompose into tasks for each processor~~		myX[i][j] = X[0][j] + gamma(X[i][j] – X[i][0]);
	~~for_all~~ j = 0 thru N do		end_for
	X[i][j] = X[0][j] + gamma(X[i][j] – X[i][0]);		end_for
	~~end_for_all~~
	~~end_for_all~~		LOCK(X[i][j]) // update centroid using the value from each thread
			myX[i][j] += myX[i][j];
			UNLOCK(X[i][j]);

			WAIT_FOR_END(nprocs-1); // we wait for all threads to update entire simplex

	}		}

Line 272:		Line 302:

	//The J LOOP and centroid update be broken down into P threads		//The J LOOP and centroid update be broken down into P threads
	// with each thread ~~workingon~~ N+1/P points		// with each thread working on N+1/P points

	for_each_thread j = 0 thru N-1 do // Centroid of all but worst point		for_each_thread j = 0 thru N-1 do // Centroid of all but worst point
	myXcen[i] += X[i][j]; // private variable for each accumulate		myXcen[i] += X[i][j]; // private variable for each accumulate

Oabapat: /* Message Passing Implementation */

2011-04-11T17:23:42Z

Message Passing Implementation

@@ Line 293: / Line 293: @@
 <pre>
 Calculate_Centroid()
+{