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

Beburrou: /* Shared Memory */

2011-02-28T05:09:44Z

Shared Memory

← Older revision		Revision as of 05:09, 28 February 2011
Line 212:		Line 212:
	<br>		<br>

	As is readily seen, this code is short and simple, so we will analyze it line by line. To summarize the method, each row is solved serially, with the columns each being normalized and subtracted the remaining rows in parallel.		As is readily seen, this code is short and simple, so we will analyze it line by line. To summarize the method, each row is solved serially, with the columns each being normalized and subtracted from the remaining rows in parallel.

	The pivot column is the column currently being reduced (and subsequently, also the row).		The pivot column is the column currently being reduced (and subsequently, also the row).
Line 229:		Line 229:
	Now, we loop through all other rows and update them with the just normalized column. This involves subtracting it the needed number of times.		Now, we loop through all other rows and update them with the just normalized column. This involves subtracting it the needed number of times.
	8: b(i) = b(i) - (xmult * b(pivot))		8: b(i) = b(i) - (xmult * b(pivot))
	We also update the solution column, which is ~~here~~ <code>b</code>		We also update the solution column, which is in the <code>b</code> array.
	9: end do		9: end do
	10: 1: !$omp end parallel do		10: 1: !$omp end parallel do
	11: end do		11: end do
	Back substitution is done next, but is not shown.		Back substitution would be done next, but is not shown.

	== Message Passing ==		== Message Passing ==

Beburrou: /* Data Parallel */

2011-02-28T05:08:02Z

Data Parallel

← Older revision		Revision as of 05:08, 28 February 2011
Line 182:		Line 182:
	This data parallel code works by performing operations on entire rows of the equation matrix. In the first loop, the forward reduction is performed. The variable <code>i</code> is an index which keeps track of the column (and thus row) that is currently being reduced.		This data parallel code works by performing operations on entire rows of the equation matrix. In the first loop, the forward reduction is performed. The variable <code>i</code> is an index which keeps track of the column (and thus row) that is currently being reduced.

	Instead of reducing the rows starting with row 1, we will ~~swap row 1~~ with the row that has the largest element in column 1. We will ~~do this~~ at the beginning of each iteration. (lines 12-14)		Instead of reducing the rows starting with row 1, we will instead work with the row that has the largest element in the pivot column that hasn't already been used. We will find the row with which to work at the beginning of each iteration. (lines 12-14)

	Next, we divide every element in the current row by the value in the column we are reducing. (~~line~~ 15-16)		Next, we divide every element in the current row by the value in the column we are reducing. (lines 15-16)

	To finish the forward reduction, we subtract the current row from all remaining rows the needed number of times (so that the current column becomes 0). This part of the algorithm is extremely parallelizable. (lines 18-20)		To finish the forward reduction, we subtract the current row from all remaining rows the needed number of times (so that the current column becomes 0). This part of the algorithm is extremely parallelizable. The <code>FORALL</code> statement tells the compiler that this statement is parallelizable, and this statement implies data parallelism. (lines 18-20)

			Lines 22-24 exchange rows to put the matrix in row-echelon form, and the <code>FORALL</code> statement again shows that this operation is highly parallelizable.

	The last loop does the back substitution. The loop starts on the end and works its way to the first row.		The last loop does the back substitution. The loop starts on the end and works its way to the first row.

	First, the ~~current~~ row is solved. (line 26)		First, the last row is solved. (line 26)
	Then, the just found solution is immediately substituted into all remaining rows and added to the right side of the matrix (the n+1 column). (line 27)		Then, the just found solution is immediately substituted into all remaining rows and added to the right side of the matrix (the n+1 column). (line 27)

Beburrou: /* Gaussian Elimination */

2011-02-28T04:47:34Z

Gaussian Elimination

← Older revision		Revision as of 04:47, 28 February 2011
Line 3:		Line 3:

	= Gaussian Elimination =		= Gaussian Elimination =
	Gaussian Elimination is common method used to solve a system of linear equations. The method was popularized by Issac Newton and is today taught in most elementary linear algebra textbooks.<sup><span id="5body">[[#5foot\|[5]]]</span></sup> The method consists of two steps: forward reduction and back substitution. The method is not strictly matrix based, but since any system of equations can be represented in matrix form, we will only work with the matrix forms for convenience.		Gaussian Elimination is a common method used to solve a system of linear equations. The method was popularized by Issac Newton and is today taught in most elementary linear algebra textbooks.<sup><span id="5body">[[#5foot\|[5]]]</span></sup> The method consists of two steps: forward reduction and back substitution. The method is not strictly matrix based, but since any system of equations can be represented in matrix form, we will only work with the matrix forms for convenience.

	'''Forward Reduction'''		'''Forward Reduction'''

	The first step is to reduce the equation matrix to [http://en.wikipedia.org/wiki/Echelon_form row echelon form]. In this form, each row has at least one more zero in a column on the left than the previous row, and the first non-zero element is 1. A couple of ~~example are best~~ to illustrate:		The first step is to reduce the equation matrix to [http://en.wikipedia.org/wiki/Echelon_form row-echelon form]. In this form, each row has at least one more zero in a column on the left than the previous row, and the first non-zero element is 1. A couple of examples will help to illustrate row-echelon form:

	<blockquote>		<blockquote>

Mnmiskie: /* Gaussian Elimination */

2011-02-28T04:33:32Z

Gaussian Elimination

← Older revision		Revision as of 04:33, 28 February 2011
Line 3:		Line 3:

	= Gaussian Elimination =		= Gaussian Elimination =
	Gaussian Elimination is common method used to solve a system of linear equations. The method was popularized by Issac Newton and is today taught in most elementary linear algebra textbooks<sup><span id="5body">[[#5foot\|[5]]]</span></sup>. The method consists of two steps: forward reduction and back substitution. The method is not strictly matrix based, but since any system of equations can be represented in matrix form, we will only work with the matrix forms for convenience.		Gaussian Elimination is common method used to solve a system of linear equations. The method was popularized by Issac Newton and is today taught in most elementary linear algebra textbooks.<sup><span id="5body">[[#5foot\|[5]]]</span></sup> The method consists of two steps: forward reduction and back substitution. The method is not strictly matrix based, but since any system of equations can be represented in matrix form, we will only work with the matrix forms for convenience.

	'''Forward Reduction'''		'''Forward Reduction'''

Mnmiskie: /* Gaussian Elimination */

2011-02-28T04:33:15Z

Gaussian Elimination

← Older revision		Revision as of 04:33, 28 February 2011
Line 3:		Line 3:

	= Gaussian Elimination =		= Gaussian Elimination =
	~~Guassian~~ Elimination is common method used to solve a system of linear equations. The method was popularized by Issac Newton and is today taught in most elementary linear algebra textbooks<sup><span id="5body">[[#5foot\|[5]]]</span></sup>. The method consists of two steps: forward reduction and back substitution. The method is not strictly matrix based, but since any system of equations can be represented in matrix form, we will only work with the matrix forms for convenience.		Gaussian Elimination is common method used to solve a system of linear equations. The method was popularized by Issac Newton and is today taught in most elementary linear algebra textbooks<sup><span id="5body">[[#5foot\|[5]]]</span></sup>. The method consists of two steps: forward reduction and back substitution. The method is not strictly matrix based, but since any system of equations can be represented in matrix form, we will only work with the matrix forms for convenience.

	'''Forward Reduction'''		'''Forward Reduction'''

Mnmiskie: /* Shared Memory */

2011-02-28T04:30:28Z

Shared Memory

← Older revision		Revision as of 04:30, 28 February 2011
Line 195:		Line 195:
	== Shared Memory ==		== Shared Memory ==

	The following section of code implements Gaussian Elimination with a shared memory scheme, using HPF. It ~~is found in~~ the ~~book ''Designing and Building Parallel Programs (Online)'' by Ian Foster~~.<sup><span id="~~2body~~">[[#~~2foot~~\|[2]]]</span></sup> <br>		The following section of code implements Gaussian Elimination with a shared memory scheme, using HPF. It was taken from a paper by S.F.McGinn and R.E.Shaw from the University of New Brunswick, New Brunswick, Canada.<sup><span id="1body">[[#1foot\|[1]]]</span></sup> <br>

	1: do pivot = 1, (n-1)		1: do pivot = 1, (n-1)
Line 210:		Line 210:
	<br>		<br>

	~~This data parallel~~ code ~~works~~ by ~~performing operations on entire rows of the equation matrix~~. In the ~~first loop~~, ~~the forward reduction~~ is ~~performed. The variable <code>i</code> is an index which keeps track of~~ the ~~column (~~and ~~thus row) that is currently being reduced~~.		As is readily seen, this code is short and simple, so we will analyze it line by line. To summarize the method, each row is solved serially, with the columns each being normalized and subtracted the remaining rows in parallel.

	~~Instead of reducing~~ the ~~rows starting with row 1~~, ~~we will swap row 1 with~~ the row ~~that has the largest element in column 1. We will do this at the beginning of each iteration~~. ~~(lines 12-14)~~		The pivot column is the column currently being reduced (and subsequently, also the row).

	~~Next~~, ~~we divide every element in the current~~ row ~~by the value in the column we are reducing~~. (~~line 15-16~~)		1: do pivot = 1, (n-1)
			Loop through each row for forward reduction.
	~~To finish the forward reduction~~, ~~we subtract~~ the current row from ~~all remaining rows~~ the ~~needed number of times~~ (~~so that~~ the ~~current~~ column ~~becomes 0)~~. This ~~part of~~ the ~~algorithm is extremely parallelizable~~. (~~lines 18~~-20)		2: !$omp parallel do private(xmult) schedule(runtime)
			Spawn parallel threads here, making <code>xmult</code> private.
	~~The last~~ loop ~~does~~ the ~~back substitution~~. ~~The loop starts on~~ the ~~end and works its way to the first row~~.		3: do i = (pivot+1), n
			Loop through all columns in the current row starting from the pivot.
	~~First, the current row is solved.~~ (~~line 26~~)		4: xmult = a(i,pivot) / a(pivot,pivot)
	~~Then,~~ the ~~just found~~ solution is ~~immediately substituted into all remaining rows and added to the right side of the matrix (the n+~~1 ~~column)~~. ~~(line 27)~~		Divide the i'th column by the pivot column. This is the normalization step.
			5: do j = (pivot+1), n
			6: a(i,j) = a(i,j) - (xmult * a(pivot,j))
			7: end do
			Now, we loop through all other rows and update them with the just normalized column. This involves subtracting it the needed number of times.
			8: b(i) = b(i) - (xmult * b(pivot))
			We also update the solution column, which is here <code>b</code>
			9: end do
			10: 1: !$omp end parallel do
			11: end do
			Back substitution is done next, but is not shown.

	== Message Passing ==		== Message Passing ==

Mnmiskie: /* Shared Memory */

2011-02-28T04:14:04Z

Shared Memory

← Older revision		Revision as of 04:14, 28 February 2011
Line 194:		Line 194:

	== Shared Memory ==		== Shared Memory ==

			The following section of code implements Gaussian Elimination with a shared memory scheme, using HPF. It is found in the book ''Designing and Building Parallel Programs (Online)'' by Ian Foster.<sup><span id="2body">[[#2foot\|[2]]]</span></sup> <br>

			1: do pivot = 1, (n-1)
			2: !$omp parallel do private(xmult) schedule(runtime)
			3: do i = (pivot+1), n
			4: xmult = a(i,pivot) / a(pivot,pivot)
			5: do j = (pivot+1), n
			6: a(i,j) = a(i,j) - (xmult * a(pivot,j))
			7: end do
			8: b(i) = b(i) - (xmult * b(pivot))
			9: end do
			10: 1: !$omp end parallel do
			11: end do
			<br>

			This data parallel code works by performing operations on entire rows of the equation matrix. In the first loop, the forward reduction is performed. The variable <code>i</code> is an index which keeps track of the column (and thus row) that is currently being reduced.

			Instead of reducing the rows starting with row 1, we will swap row 1 with the row that has the largest element in column 1. We will do this at the beginning of each iteration. (lines 12-14)

			Next, we divide every element in the current row by the value in the column we are reducing. (line 15-16)

			To finish the forward reduction, we subtract the current row from all remaining rows the needed number of times (so that the current column becomes 0). This part of the algorithm is extremely parallelizable. (lines 18-20)

			The last loop does the back substitution. The loop starts on the end and works its way to the first row.

			First, the current row is solved. (line 26)
			Then, the just found solution is immediately substituted into all remaining rows and added to the right side of the matrix (the n+1 column). (line 27)

	== Message Passing ==		== Message Passing ==

Mnmiskie: /* Data Parallel */

2011-02-28T04:10:26Z

Data Parallel

← Older revision		Revision as of 04:10, 28 February 2011
Line 147:		Line 147:
	== Data Parallel ==		== Data Parallel ==

	The following section of code implements Gaussian Elimination via ~~message passing, using MPI~~. It ~~was taken from a paper~~ by ~~S.F.McGinn and R.E.Shaw from the University of New Brunswick, New Brunswick, Canada~~.<sup><span id="~~1body~~">[[#~~1foot~~\|[1]]]</span></sup> <br>		The following section of code implements Gaussian Elimination via data parallel with HPF. It is found in the book ''Designing and Building Parallel Programs (Online)'' by Ian Foster.<sup><span id="2body">[[#2foot\|[2]]]</span></sup> <br>

	1: subroutine gauss(n, A, X)		1: subroutine gauss(n, A, X)
Line 179:		Line 179:

	<br>		<br>
	This code lacks some of the declarations for the variables, but most of the variables are self-explanatory. The code also attempts to do some load balancing via the <code>chunk</code> variable. <code>chunk</code> is also used to determine how much data to send, as the amount of data needed in each step gets progressively smaller. Making <code>chunk</code> smaller will therefor decrease the amount of time spent in communication, thus yielding better runtimes. The other variable of note is <code>root</code>, which refers to the root processor, the processor that controls the rest of the processors.

	~~The code effectively begins its~~ parallel section at line 4. Lines 5-41 have the root processor setting the chunk size and setting up the data to be passed to the other processors. In lines 43-68, the root processor sends the necessary data to the other processors. The functions <code~~>MPI_BCAST</code>, <code>MPI_SCATTER</code>, and <code>MPI_SCATTERV</code> serve as either a "send" or a "receive", depending on which processor is executing them;~~ on the ~~root, they act as a send, while on all other processors, they act as a receive<sup><span id="3body">[[#3foot\|[3]]]</span></sup>~~. In ~~lines 70-78~~, ~~each processor is performing~~ the forward ~~elimination on its chunk of data~~. ~~Finally, the data from each processor is sent back to the root processor using the~~ <code>~~MPI_GATHERV~~</code> ~~function,~~ which ~~also functions as either a "send" or a receive", only the root processor is now~~ the ~~receiver~~ and ~~the other processors are the senders. All of this code is executed for each pivot point in the matrix. Backwards substitution~~ is ~~then done sequentially on the root processor~~.		This data parallel code works by performing operations on entire rows of the equation matrix. In the first loop, the forward reduction is performed. The variable <code>i</code> is an index which keeps track of the column (and thus row) that is currently being reduced.

	~~The key elements~~ of ~~Message Passing~~ in this ~~code example~~ are the ~~communication via~~ the ~~<code>MPI_</code> functions and~~ the ~~root processor performing some set~~-~~up of data to be passed~~ on its ~~own~~. ~~This code~~ is ~~using~~ the ~~MPI library~~ to ~~support parallelization~~.		Instead of reducing the rows starting with row 1, we will swap row 1 with the row that has the largest element in column 1. We will do this at the beginning of each iteration. (lines 12-14)

			Next, we divide every element in the current row by the value in the column we are reducing. (line 15-16)

			To finish the forward reduction, we subtract the current row from all remaining rows the needed number of times (so that the current column becomes 0). This part of the algorithm is extremely parallelizable. (lines 18-20)

			The last loop does the back substitution. The loop starts on the end and works its way to the first row.

			First, the current row is solved. (line 26)
			Then, the just found solution is immediately substituted into all remaining rows and added to the right side of the matrix (the n+1 column). (line 27)

	== Shared Memory ==		== Shared Memory ==

Mnmiskie: /* Data Parallel */

2011-02-28T02:47:22Z

Data Parallel

Show changes

Mnmiskie: /* Data Parallel */

2011-02-28T02:45:52Z

Data Parallel

← Older revision		Revision as of 02:45, 28 February 2011
Line 149:		Line 149:
	The following section of code implements Gaussian Elimination via message passing, using MPI. It was taken from a paper by S.F.McGinn and R.E.Shaw from the University of New Brunswick, New Brunswick, Canada.<sup><span id="1body">[[#1foot\|[1]]]</span></sup> <br>		The following section of code implements Gaussian Elimination via message passing, using MPI. It was taken from a paper by S.F.McGinn and R.E.Shaw from the University of New Brunswick, New Brunswick, Canada.<sup><span id="1body">[[#1foot\|[1]]]</span></sup> <br>

	subroutine gauss(n, A, X)		1: subroutine gauss(n, A, X)
	integer n		integer n
	real A(n, n+1)		real A(n, n+1)