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

Zzhang15: /* References */

2011-04-01T05:28:55Z

References

← Older revision		Revision as of 05:28, 1 April 2011
Line 176:		Line 176:

	[13] Mills, P.H.; Nyland, L.S.; Prins, J.F.; Reif, J.H.; , [http://www.cs.duke.edu/~reif/paper/proteus/ipps92.pdf "Prototyping N-body simulation in Proteus,"] Parallel Processing Symposium, 1992. Proceedings., Sixth International , vol., no., pp.476-482, 23-26 Mar 1992		[13] Mills, P.H.; Nyland, L.S.; Prins, J.F.; Reif, J.H.; , [http://www.cs.duke.edu/~reif/paper/proteus/ipps92.pdf "Prototyping N-body simulation in Proteus,"] Parallel Processing Symposium, 1992. Proceedings., Sixth International , vol., no., pp.476-482, 23-26 Mar 1992

			[14] David E. Culler, Jaswinder Pal Singh and Anoop Gupta. [http://www2.lib.ncsu.edu/catalog/record/NCSU1020944 "Parallel computer architecture : a hardware/software approach"]Morgan Kaufmann Publishers, c1999.

	= Appendix: Comparison of Performance =		= Appendix: Comparison of Performance =

Zzhang15: /* Message-passing Implementation */

2011-04-01T05:20:08Z

Message-passing Implementation

← Older revision		Revision as of 05:20, 1 April 2011
Line 109:		Line 109:

	[[Image: Octtree.png\|frame\|right\|A quad-tree shown along with the binary key coordinates of the nodes. Figure from [[#References\|[9]]] ]]		[[Image: Octtree.png\|frame\|right\|A quad-tree shown along with the binary key coordinates of the nodes. Figure from [[#References\|[9]]] ]]

			Implementing the BH tree algorithm is more difficult in a distributed-memory system compared with the shared-memory implementation. Because we need assign the different bodies to different processor dynamically. When the location of bodies have been changed exceed a certain limit, the BH tree needs to be reconstruct. The good news is we don't need reconstruct the BH tree very frequently(compared with the simulation step size).

	In message-passing architectures, a processor’s local memory is often used as a software-controlled cache		In message-passing architectures, a processor’s local memory is often used as a software-controlled cache
	for communicated data, in addition to holding the processor’s own assigned data partition; that is, data are replicated in the memories of those processors that need to use them.		for communicated data, in addition to holding the processor’s own assigned data partition; that is, data are replicated in the memories of those processors that need to use them.

	Warren and Salmon introduced a parallel hashed Oct-tree N-body algorithm[[#References\|[9]]]. One of the advantages of using hash table is that the non-local data may be accessed by requesting a key, which is a uniform addressing scheme and easy to be implemented on a message passing architecture. The pseudocode of tree traversal are shown below:		Warren and Salmon introduced a parallel hashed Oct-tree N-body algorithm[[#References\|[9]]]. The hashed Oct-tree is the message-passing version of BH tree implementation. One of the advantages of using hash table is that the non-local data may be accessed by requesting a key, which is a uniform addressing scheme and easy to be implemented on a message passing architecture. The pseudocode of tree traversal are shown below:

	<pre>		<pre>
Line 133:		Line 136:

	There are two major challenges of using message-passing parallel to solve the N-body problem:		There are two major challenges of using message-passing parallel to solve the N-body problem:
	* The nonuniform and dynamic nature of the particle distribution, which implies that the partitions assigned to processors change with time to maintain load balancing and data locality;		# The nonuniform and dynamic nature of the particle distribution, which implies that the partitions assigned to processors change with time to maintain load balancing and data locality;
	* The need for long-range communication which is irregular as a result of the nonuniformity.		# The need for long-range communication which is irregular as a result of the nonuniformity.

	The typical message-passing strategy of allowing communicated data to accumulate in local memory and ﬂushing them out at		The typical message-passing strategy of allowing communicated data to accumulate in local memory and ﬂushing them out at

Zzhang15: /* References */

2011-04-01T05:08:27Z

References

← Older revision		Revision as of 05:08, 1 April 2011
Line 146:		Line 146:
	* Software (algorithm) side: On the other hand, the high-level architecture-independent algorithms also have been develop to simulate the N-body problem[[#References\|[13]]]. These algorithm allowed researchers test their prototype parallel program under different architecture without using the machine-specified languages.		* Software (algorithm) side: On the other hand, the high-level architecture-independent algorithms also have been develop to simulate the N-body problem[[#References\|[13]]]. These algorithm allowed researchers test their prototype parallel program under different architecture without using the machine-specified languages.

	==References==		=References=

	[1] [http://faculty.ifmo.ru/butikov/Projects/Collection1.html Collection of remarkable three-body motions]		[1] [http://faculty.ifmo.ru/butikov/Projects/Collection1.html Collection of remarkable three-body motions]

Zzhang15: /* Parallel N-body problem */

2011-04-01T05:07:57Z

Parallel N-body problem

← Older revision		Revision as of 05:07, 1 April 2011
Line 10:		Line 10:
	The simulation of N-body system can be used from simulation of celestial bodies ([http://www.mpa-garching.mpg.de/galform/virgo/millennium/index.shtml gravitational interaction])to interactions of a set of particles (electromagnetic interaction).		The simulation of N-body system can be used from simulation of celestial bodies ([http://www.mpa-garching.mpg.de/galform/virgo/millennium/index.shtml gravitational interaction])to interactions of a set of particles (electromagnetic interaction).

	== Parallel N-body problem ==		= Parallel N-body problem =

	As MIT professors Dimitri Bertsekas and John Tsitsiklis stated in their book [http://web.mit.edu/dimitrib/www/pdc.html "Parallel and Distributed Computation: Numerical Methods"], parallel computers have provided an excellent platform for numerical analysis. In the N-body problem, since each particle will interact with others by the force of gravity, the simulation of N-body system is computationally expensive for large numbers of N. There a ''O''(''N''<sup>2</sup>) interactions to compute for every iteration. Furthermore, in order to have a accurate result, the discrete time step must relatively small. Thus, there has been a huge interest in faster parallel algorithm for N-body problem.		As MIT professors Dimitri Bertsekas and John Tsitsiklis stated in their book [http://web.mit.edu/dimitrib/www/pdc.html "Parallel and Distributed Computation: Numerical Methods"], parallel computers have provided an excellent platform for numerical analysis. In the N-body problem, since each particle will interact with others by the force of gravity, the simulation of N-body system is computationally expensive for large numbers of N. There a ''O''(''N''<sup>2</sup>) interactions to compute for every iteration. Furthermore, in order to have a accurate result, the discrete time step must relatively small. Thus, there has been a huge interest in faster parallel algorithm for N-body problem.

			== Data-parallel Implementation ==

			=== Barnes-Hut Tree (BH tree) ===
	~~=== Data-parallel Implementation ===~~

	==== Barnes-Hut Tree (BH tree) ====
	In 1985, Appel took the first step of decomposes the problem by introducing a tree structure[[#References\|[4]]]. In the next year, Barnes and Hut extend the tree-based force calculation with logarithmic growth of force terms per particle[[#References\|[5]]]. That is, construct a tree hierarchy(BH tree) of bodies based on the partition of entire space. The partition is shown on the left. The empty block have been pruned, thus the traversal time have been reduced from''O''(''N''<sup>2</sup>) to ''O''(''N'' log''N'').		In 1985, Appel took the first step of decomposes the problem by introducing a tree structure[[#References\|[4]]]. In the next year, Barnes and Hut extend the tree-based force calculation with logarithmic growth of force terms per particle[[#References\|[5]]]. That is, construct a tree hierarchy(BH tree) of bodies based on the partition of entire space. The partition is shown on the left. The empty block have been pruned, thus the traversal time have been reduced from''O''(''N''<sup>2</sup>) to ''O''(''N'' log''N'').

Line 42:		Line 40:
	Even though the Barnes-Hut tree decomposition algorithm have these challenges, BH tree is still the one of most efficient methods for solving the n-body problem.		Even though the Barnes-Hut tree decomposition algorithm have these challenges, BH tree is still the one of most efficient methods for solving the n-body problem.

	==== Orthogonal Recursive Bisection (ORB) ====		=== Orthogonal Recursive Bisection (ORB) ===

	[[Image: orthogonal recursive bisection.gif\|right\|frame\|upright=0.5\| [http://en.wikipedia.org/wiki/CUDA Orthogonal Recursive Bisection] ]]		[[Image: orthogonal recursive bisection.gif\|right\|frame\|upright=0.5\| [http://en.wikipedia.org/wiki/CUDA Orthogonal Recursive Bisection] ]]
Line 48:		Line 46:
	Unlike BH tree divided the space into square cells, the Orthogonal Recursive Bisection (ORB) divided space into rectangular with same number of bodies in each of them. It is a recursive approach because all processors are associated with the entire space at the very beginning; then a orthogonal line has been drawn to separate the space into bisection; each of the subsection has associated with half of the processors. Until the number of partition is equal to the number of processors.		Unlike BH tree divided the space into square cells, the Orthogonal Recursive Bisection (ORB) divided space into rectangular with same number of bodies in each of them. It is a recursive approach because all processors are associated with the entire space at the very beginning; then a orthogonal line has been drawn to separate the space into bisection; each of the subsection has associated with half of the processors. Until the number of partition is equal to the number of processors.

	==== Other Data-parallel Implementation ====		=== Other Data-parallel Implementation ===

	When using data-parallel algorithm to solve the N-body problem, one obvious approach for the data-parallel implementation is to divide the interactions into different sets based on the distances from current particle to other "interacting" particles. Thus the force from 'far away' particles can be updated less frequently or even can be ignored.		When using data-parallel algorithm to solve the N-body problem, one obvious approach for the data-parallel implementation is to divide the interactions into different sets based on the distances from current particle to other "interacting" particles. Thus the force from 'far away' particles can be updated less frequently or even can be ignored.
Line 67:		Line 65:
	Another data-parallel implementation can be found in [[#References\|[8]]]. The drawback of this type of approach is obvious: the error may be increased significantly due to the clustering process.		Another data-parallel implementation can be found in [[#References\|[8]]]. The drawback of this type of approach is obvious: the error may be increased significantly due to the clustering process.

	=== Shared-memory Implementation ===		== Shared-memory Implementation ==

	==== Costzones ====		=== Costzones ===

	[[Image: Costzone.png\|center\|frame\| [http://www.eecs.berkeley.edu/~demmel/cs267/lecture27/lecture27.html The partitioning of Costzones] ]]		[[Image: Costzone.png\|center\|frame\| [http://www.eecs.berkeley.edu/~demmel/cs267/lecture27/lecture27.html The partitioning of Costzones] ]]
Line 77:		Line 75:
	The costzones method have a better performance in a shared-memory machine compared with the ORB method. The reason is mainly because the time spent in the space partition is shorter.		The costzones method have a better performance in a shared-memory machine compared with the ORB method. The reason is mainly because the time spent in the space partition is shorter.

	==== Other Shared-memory Implementation ====		=== Other Shared-memory Implementation ===

	Besides the Costzones method of implementing the N-body simulation on shard-memory machines, there is a tremendous interests of using [http://en.wikipedia.org/wiki/CUDA CUDA] to solve the N-body problem by modern GPUs [[#References\|[10]]][[#References\|[11]]].		Besides the Costzones method of implementing the N-body simulation on shard-memory machines, there is a tremendous interests of using [http://en.wikipedia.org/wiki/CUDA CUDA] to solve the N-body problem by modern GPUs [[#References\|[10]]][[#References\|[11]]].
Line 108:		Line 106:
	CUDA shows an impressive potential to execute extremely parallel applications such as N-body problem. Twenty years ago, the N-body simulation can only runs on super computers. Because of the development of CUDA makes the classical N-body problem become a term project for some graduate students (see [http://www.evl.uic.edu/sjames/cs525/project2.html 2008 Fall CS 525 Project2 n-body simulation in CUDA]).		CUDA shows an impressive potential to execute extremely parallel applications such as N-body problem. Twenty years ago, the N-body simulation can only runs on super computers. Because of the development of CUDA makes the classical N-body problem become a term project for some graduate students (see [http://www.evl.uic.edu/sjames/cs525/project2.html 2008 Fall CS 525 Project2 n-body simulation in CUDA]).

	=== Message-passing Implementation ===		== Message-passing Implementation ==

	[[Image: Octtree.png\|frame\|right\|A quad-tree shown along with the binary key coordinates of the nodes. Figure from [[#References\|[9]]] ]]		[[Image: Octtree.png\|frame\|right\|A quad-tree shown along with the binary key coordinates of the nodes. Figure from [[#References\|[9]]] ]]
Line 141:		Line 139:
	certain points in the program does not work well here like it does in regular predictable programs. Thus, the only convenient points at which to ﬂush communicated data in the application program are the boundaries between computational phases. Since the amount of nonlocal data read from the tree during the force computation phase can be quite large, the memory overhead due to data replication can be large when replacement is managed in this typical message-passing style.		certain points in the program does not work well here like it does in regular predictable programs. Thus, the only convenient points at which to ﬂush communicated data in the application program are the boundaries between computational phases. Since the amount of nonlocal data read from the tree during the force computation phase can be quite large, the memory overhead due to data replication can be large when replacement is managed in this typical message-passing style.

			== Other Parallel Approaches ==

	=== Other Parallel Approaches ===
	Other than the conventional approaches, there are also some new techniques have been developed to simulate the N-body problem:		Other than the conventional approaches, there are also some new techniques have been developed to simulate the N-body problem:

Line 149:		Line 145:

	* Software (algorithm) side: On the other hand, the high-level architecture-independent algorithms also have been develop to simulate the N-body problem[[#References\|[13]]]. These algorithm allowed researchers test their prototype parallel program under different architecture without using the machine-specified languages.		* Software (algorithm) side: On the other hand, the high-level architecture-independent algorithms also have been develop to simulate the N-body problem[[#References\|[13]]]. These algorithm allowed researchers test their prototype parallel program under different architecture without using the machine-specified languages.



	==References==		==References==

Zzhang15: /* Introduction */

2011-04-01T05:07:09Z

Introduction

← Older revision		Revision as of 05:07, 1 April 2011
Line 1:		Line 1:
	== Introduction ==		= Introduction =

	[[Image:Nasanbody.jpg\|thumb\|left\|N-body Problem. Picture source: NASA]]		[[Image:Nasanbody.jpg\|thumb\|left\|N-body Problem. Picture source: NASA]]

Zzhang15: /* Comparison of Performance */

2011-04-01T05:06:44Z

Comparison of Performance

← Older revision		Revision as of 05:06, 1 April 2011
Line 180:		Line 180:
	[13] Mills, P.H.; Nyland, L.S.; Prins, J.F.; Reif, J.H.; , [http://www.cs.duke.edu/~reif/paper/proteus/ipps92.pdf "Prototyping N-body simulation in Proteus,"] Parallel Processing Symposium, 1992. Proceedings., Sixth International , vol., no., pp.476-482, 23-26 Mar 1992		[13] Mills, P.H.; Nyland, L.S.; Prins, J.F.; Reif, J.H.; , [http://www.cs.duke.edu/~reif/paper/proteus/ipps92.pdf "Prototyping N-body simulation in Proteus,"] Parallel Processing Symposium, 1992. Proceedings., Sixth International , vol., no., pp.476-482, 23-26 Mar 1992

	== Comparison of Performance ==		= Appendix: Comparison of Performance =

	The following table is a summary of sequential and parallel implementations of N-body simulation from [[#References\|[7]]].		The following table is a summary of sequential and parallel implementations of N-body simulation from [[#References\|[7]]].

Zzhang15: /* Comparison of Performance */

2011-04-01T05:06:21Z

Comparison of Performance

← Older revision		Revision as of 05:06, 1 April 2011
Line 150:		Line 150:
	* Software (algorithm) side: On the other hand, the high-level architecture-independent algorithms also have been develop to simulate the N-body problem[[#References\|[13]]]. These algorithm allowed researchers test their prototype parallel program under different architecture without using the machine-specified languages.		* Software (algorithm) side: On the other hand, the high-level architecture-independent algorithms also have been develop to simulate the N-body problem[[#References\|[13]]]. These algorithm allowed researchers test their prototype parallel program under different architecture without using the machine-specified languages.

	~~== Comparison of Performance ==~~

	~~The following table is a summary of sequential and parallel implementations of N-body simulation from [[#References\|[7]]].~~
	~~<table border="1" bordercolor="#FFFFFF" style="background-color:#FFFFFF" width="800" cellpadding="3" cellspacing="3">~~
	~~<tr>~~
	~~<td>Author</td>~~
	~~<td>Method and Error</td>~~
	~~<td>Program Model</td>~~
	~~<td>N</td>~~
	~~<td>Times (s)</td>~~
	~~<td>P</td>~~
	~~<td>Efficiency</td>~~
	~~<td>Machine</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Salmon (1990)</td>~~
	~~<td>BH, quadrupole</td>~~
	~~<td>Message passing</td>~~
	~~<td>?</td>~~
	~~<td>?</td>~~
	~~<td>?</td>~~
	~~<td>?</td>~~
	~~<td>Ncude</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Warren_Salmon (1993)</td>~~
	~~<td>BH,ϵ = 10<sup>-3</sup></td>~~
	~~<td>Message passing</td>~~
	~~<td>8.78 M</td>~~
	~~<td>114</td>~~
	~~<td>512</td>~~
	~~<td>28%</td>~~
	~~<td>Intel Delta</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Warren_Salmon (1995)</td>~~
	~~<td>BH,ϵ = 10<sup>-2</sup></td>~~
	~~<td>Message passing</td>~~
	~~<td>2 M</td>~~
	~~<td>10.8</td>~~
	~~<td>256</td>~~
	~~<td>?</td>~~
	~~<td>CM-5E</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Liu-Bhatt (1994)</td>~~
	~~<td>BH, quadrupole</td>~~
	~~<td>Message passing</td>~~
	~~<td>10 M</td>~~
	~~<td>59</td>~~
	~~<td>256</td>~~
	~~<td>30%</td>~~
	~~<td>CM-5</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Leathrum-Board(1992)</td>~~
	~~<td>GR,p=8</td>~~
	~~<td>Shared memory</td>~~
	~~<td>1 M</td>~~
	~~<td>1520</td>~~
	~~<td>32</td>~~
	~~<td>20%</td>~~
	~~<td>KSR-1</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Elliott-Board(1994)</td>~~
	~~<td>GR,FFT,p=8</td>~~
	~~<td>Shared memory</td>~~
	~~<td>1 M</td>~~
	~~<td>1420</td>~~
	~~<td>32</td>~~
	~~<td>14%</td>~~
	~~<td>KSR-1</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Schmidt-Lee(1991)</td>~~
	~~<td>GR,p=8</td>~~
	~~<td>?</td>~~
	~~<td>40,000</td>~~
	~~<td>94</td>~~
	~~<td>1</td>~~
	~~<td>39%</td>~~
	~~<td>CRAY Y-MP 8/864</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Zhao-Johnsson(1991)</td>~~
	~~<td>Zhao, p=3</td>~~
	~~<td>Data parallel</td>~~
	~~<td>16,000</td>~~
	~~<td>5</td>~~
	~~<td>8 K</td>~~
	~~<td>12%</td>~~
	~~<td>CM-2</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Hu-Johnsson</td>~~
	~~<td>Anderson</td>~~
	~~<td>Data parallel</td>~~
	~~<td>100 M</td>~~
	~~<td>180</td>~~
	~~<td>256</td>~~
	~~<td>27%-35%</td>~~
	~~<td>CM-5E</td>~~
	~~</tr>~~
	~~<tr>~~
	~~<td>Singh et al.(1993)</td>~~
	~~<td>GR, 2-D, adaptive</td>~~
	~~<td>Shared memory</td>~~
	~~<td>?</td>~~
	~~<td>?</td>~~
	~~<td>?</td>~~
	~~<td>?</td>~~
	~~<td>DASH, KSR-1</td>~~
	~~</tr>~~

	~~</table>~~

	~~All performance numbers are for uniform particle distributions. Methods used are for 3-D, unless other wise stated. "?" imply unavailable data.~~

	==References==		==References==

Zzhang15: /* References */

2011-04-01T05:06:10Z

References

← Older revision		Revision as of 05:06, 1 April 2011
Line 296:		Line 296:

	[13] Mills, P.H.; Nyland, L.S.; Prins, J.F.; Reif, J.H.; , [http://www.cs.duke.edu/~reif/paper/proteus/ipps92.pdf "Prototyping N-body simulation in Proteus,"] Parallel Processing Symposium, 1992. Proceedings., Sixth International , vol., no., pp.476-482, 23-26 Mar 1992		[13] Mills, P.H.; Nyland, L.S.; Prins, J.F.; Reif, J.H.; , [http://www.cs.duke.edu/~reif/paper/proteus/ipps92.pdf "Prototyping N-body simulation in Proteus,"] Parallel Processing Symposium, 1992. Proceedings., Sixth International , vol., no., pp.476-482, 23-26 Mar 1992

			== Comparison of Performance ==

			The following table is a summary of sequential and parallel implementations of N-body simulation from [[#References\|[7]]].
			<table border="1" bordercolor="#FFFFFF" style="background-color:#FFFFFF" width="800" cellpadding="3" cellspacing="3">
			<tr>
			<td>Author</td>
			<td>Method and Error</td>
			<td>Program Model</td>
			<td>N</td>
			<td>Times (s)</td>
			<td>P</td>
			<td>Efficiency</td>
			<td>Machine</td>
			</tr>
			<tr>
			<td>Salmon (1990)</td>
			<td>BH, quadrupole</td>
			<td>Message passing</td>
			<td>?</td>
			<td>?</td>
			<td>?</td>
			<td>?</td>
			<td>Ncude</td>
			</tr>
			<tr>
			<td>Warren_Salmon (1993)</td>
			<td>BH,ϵ = 10<sup>-3</sup></td>
			<td>Message passing</td>
			<td>8.78 M</td>
			<td>114</td>
			<td>512</td>
			<td>28%</td>
			<td>Intel Delta</td>
			</tr>
			<tr>
			<td>Warren_Salmon (1995)</td>
			<td>BH,ϵ = 10<sup>-2</sup></td>
			<td>Message passing</td>
			<td>2 M</td>
			<td>10.8</td>
			<td>256</td>
			<td>?</td>
			<td>CM-5E</td>
			</tr>
			<tr>
			<td>Liu-Bhatt (1994)</td>
			<td>BH, quadrupole</td>
			<td>Message passing</td>
			<td>10 M</td>
			<td>59</td>
			<td>256</td>
			<td>30%</td>
			<td>CM-5</td>
			</tr>
			<tr>
			<td>Leathrum-Board(1992)</td>
			<td>GR,p=8</td>
			<td>Shared memory</td>
			<td>1 M</td>
			<td>1520</td>
			<td>32</td>
			<td>20%</td>
			<td>KSR-1</td>
			</tr>
			<tr>
			<td>Elliott-Board(1994)</td>
			<td>GR,FFT,p=8</td>
			<td>Shared memory</td>
			<td>1 M</td>
			<td>1420</td>
			<td>32</td>
			<td>14%</td>
			<td>KSR-1</td>
			</tr>
			<tr>
			<td>Schmidt-Lee(1991)</td>
			<td>GR,p=8</td>
			<td>?</td>
			<td>40,000</td>
			<td>94</td>
			<td>1</td>
			<td>39%</td>
			<td>CRAY Y-MP 8/864</td>
			</tr>
			<tr>
			<td>Zhao-Johnsson(1991)</td>
			<td>Zhao, p=3</td>
			<td>Data parallel</td>
			<td>16,000</td>
			<td>5</td>
			<td>8 K</td>
			<td>12%</td>
			<td>CM-2</td>
			</tr>
			<tr>
			<td>Hu-Johnsson</td>
			<td>Anderson</td>
			<td>Data parallel</td>
			<td>100 M</td>
			<td>180</td>
			<td>256</td>
			<td>27%-35%</td>
			<td>CM-5E</td>
			</tr>
			<tr>
			<td>Singh et al.(1993)</td>
			<td>GR, 2-D, adaptive</td>
			<td>Shared memory</td>
			<td>?</td>
			<td>?</td>
			<td>?</td>
			<td>?</td>
			<td>DASH, KSR-1</td>
			</tr>

			</table>

			All performance numbers are for uniform particle distributions. Methods used are for 3-D, unless other wise stated. "?" imply unavailable data.

Zzhang15: /* Other Approaches */

2011-04-01T05:04:11Z

Other Approaches

← Older revision		Revision as of 05:04, 1 April 2011
Line 143:		Line 143:


	=== Other Approaches ===		=== Other Parallel Approaches ===
	Other than the conventional approaches, there are also some new techniques have been developed to simulate the N-body problem:		Other than the conventional approaches, there are also some new techniques have been developed to simulate the N-body problem:

Zzhang15: /* Other Implementation */

2011-04-01T05:03:46Z

Other Implementation

← Older revision		Revision as of 05:03, 1 April 2011
Line 77:		Line 77:
	The costzones method have a better performance in a shared-memory machine compared with the ORB method. The reason is mainly because the time spent in the space partition is shorter.		The costzones method have a better performance in a shared-memory machine compared with the ORB method. The reason is mainly because the time spent in the space partition is shorter.

	==== Other Implementation ====		==== Other Shared-memory Implementation ====

	Besides the Costzones method of implementing the N-body simulation on shard-memory machines, there is a tremendous interests of using [http://en.wikipedia.org/wiki/CUDA CUDA] to solve the N-body problem by modern GPUs [[#References\|[10]]][[#References\|[11]]].		Besides the Costzones method of implementing the N-body simulation on shard-memory machines, there is a tremendous interests of using [http://en.wikipedia.org/wiki/CUDA CUDA] to solve the N-body problem by modern GPUs [[#References\|[10]]][[#References\|[11]]].