CSC/ECE 506 Spring 2010/ch 2 maf - Revision history

Cslingaf at 20:31, 31 January 2011

2011-01-31T20:31:40Z

← Older revision		Revision as of 20:31, 31 January 2011
Line 53:		Line 53:
	Print sum;		Print sum;

			== Example of Data Parallel Programing Model ==


			This section shows a simple example adapted from Solihin textbook (pp. 24 - 27) that illustrates the data-parallel programming model. Each of the codes below are written in pseudo-code style.


			Suppose we want to perform the following task on an array <code>a</code>: updating each element of <code>a</code> by the product of itself and its index, and adding together the elements of <code>a</code> into the variable <code>sum</code>. The corresponding code is shown below.


			// simple sequential task
			sum = 0;
			'''for''' (i = 0; i < a.length; i++)
			{
			a[i] = a[i] * i;
			sum = sum + a[i];
			}


			When we orchestrate the task using the data-parallel programming model, the program can be divided into two parts. The first part performs the same operations on separate elements of the array for each processing element (sometimes referred to as PE or pe), and the second part reorganizes data among all processing elements (In our example data reorganization is summing up values across different processing elements). Since data-parallel programming model only defines the overall effects of parallel steps, the second part can be accomplished either through shared memory or message passing. The three code fragments below are examples for the first part of the program, shared-memory version of the second part, and message passing for the second part, respectively.


			// data parallel programming: let each PE perform the same task on different pieces of distributed data
			pe_id = getid();
			my_sum = 0;
			'''for''' (i = pe_id; i < a.length; i += number_of_pe) //separate elements of the array are assigned to each PE
			{
			a[i] = a[i] * i;
			my_sum = my_sum + a[i]; //all PEs accumulate elements assigned to them into local variable my_sum
			}


			In the above code, data parallelism is achieved by letting each processing element perform actions on array's separate elements, which are identified using the PE's id. For instance, if three processing elements are used then one processing element would start at i = 0, one would start at i = 1, and the last would start at i = 2. Since there are three processing elements then the index of the array for each will increase by three on each iteration until the task is complete (note that in our example elements assigned to each PE are interleaved instead of continuous). If the length of the array is a multiple of three then each processing element takes the same amount of time to execute its portion of the task.


			The picture below illustrates how elements of the array are assigned among different PEs for the specific case: length of the array is 7 and there are 3 PEs available. Elements in the array are marked by their indexes (0 to 6). As shown in the picture, PE0 will work on elements with index 0, 3, 6; PE1 is in charge of elements with index 1, 4; and elements with index 2, 5 are assigned to PE2. In this way, these 3 PEs work collectively on the array, while each PE works on different elements. Thus, data parallelism is achieved.

			[[Image:506wiki1.png\|frame\|center\|150px\|Illustration of data parallel programming(adapted from [http://computing.llnl.gov/tutorials/parallel_comp/#ModelsData Introduction to Parallel Computing])]]

			==Example of Task Parallel Programming Model==
	The logical opposite of data parallel is [[#Definitions \| ''task parallel,'']] in which a number of distinct tasks operate on common data. An example of a task parallel code which is functionally equivalent to the sequential and data parallel codes given above follows below.		The logical opposite of data parallel is [[#Definitions \| ''task parallel,'']] in which a number of distinct tasks operate on common data. An example of a task parallel code which is functionally equivalent to the sequential and data parallel codes given above follows below.

Mpsenn: Changing formatting to put headers at the top level

2011-01-24T16:36:12Z

Changing formatting to put headers at the top level

← Older revision		Revision as of 16:36, 24 January 2011
Line 3:		Line 3:
	Chapter 2 of [[#References \| Solihin (2008)]] covers the shared memory and message passing parallel programming models. However, it does not address the [[#Definitions \| ''data parallel'']] model, another commonly recognized parallel programming model covered in other treatments like [[#References \| Foster (1995)]] and [[#References \| Culler (1999)]]. Whereas the shared memory and message passing models are often present as competing models, the data parallel model addresses fundamentally different programming concerns and can therefore be used in conjunction with either. The goal of this supplement is to provide a treatment of the data parallel model which complements Chapter 2 of [[#References \| Solihin (2008)]]. The [[#Definitions \| ''task parallel'']] model will also be introduced briefly as a point of contrast.		Chapter 2 of [[#References \| Solihin (2008)]] covers the shared memory and message passing parallel programming models. However, it does not address the [[#Definitions \| ''data parallel'']] model, another commonly recognized parallel programming model covered in other treatments like [[#References \| Foster (1995)]] and [[#References \| Culler (1999)]]. Whereas the shared memory and message passing models are often present as competing models, the data parallel model addresses fundamentally different programming concerns and can therefore be used in conjunction with either. The goal of this supplement is to provide a treatment of the data parallel model which complements Chapter 2 of [[#References \| Solihin (2008)]]. The [[#Definitions \| ''task parallel'']] model will also be introduced briefly as a point of contrast.

	==Overview==		=Overview=

	Whereas the shared memory and message passing models focus on how parallel tasks access common data, the [[#Definitions \| ''data parallel'']] model focuses on how to divide up work into parallel tasks. Data parallel algorithms exploit parallelism by dividing a problem into a number of identical tasks which execute on different subsets of common data. An example of a data parallel code can be seen in Code 2.5 from [[#References \| Solihin (2008)]] which is reproduced below. It has been annotated with comments identifying the region of the code which is data parallel.		Whereas the shared memory and message passing models focus on how parallel tasks access common data, the [[#Definitions \| ''data parallel'']] model focuses on how to divide up work into parallel tasks. Data parallel algorithms exploit parallelism by dividing a problem into a number of identical tasks which execute on different subsets of common data. An example of a data parallel code can be seen in Code 2.5 from [[#References \| Solihin (2008)]] which is reproduced below. It has been annotated with comments identifying the region of the code which is data parallel.
Line 111:		Line 111:
	\|}		\|}

	==History of Parallel Programming Models==		=History of Parallel Programming Models=

	===Vector Machines===		==Vector Machines==

	First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.		First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.
Line 121:		Line 121:
	An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.		An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.

	===References for this section===		==References for this section==
	*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552		*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552
	*Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730		*Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		=Comparing the Data Parallel Model with the Shared Memory and Message Passing Models=

	Although the shared memory and message passing models may be combined into hybrid approaches, the two models are fundamentally different ways of addressing the same problem (of access control to common data). In contrast, the data parallel model is concerned with a fundamentally different problem (how to divide work into parallel tasks). As such, the data parallel model may be used in conjunction with either the shared memory or the message passing model without conflict. In fact, [[#References \| Klaiber (1994)]] compares the performance of a number of data parallel programs implemented with both shared memory and message passing models.		Although the shared memory and message passing models may be combined into hybrid approaches, the two models are fundamentally different ways of addressing the same problem (of access control to common data). In contrast, the data parallel model is concerned with a fundamentally different problem (how to divide work into parallel tasks). As such, the data parallel model may be used in conjunction with either the shared memory or the message passing model without conflict. In fact, [[#References \| Klaiber (1994)]] compares the performance of a number of data parallel programs implemented with both shared memory and message passing models.
Line 137:		Line 137:
	Once written, data parallel programs can scale easily to large numbers of processors. The data parallel model implicitly encourages data locality by having each thread work on a chunk of data. The regular data chunks also make it easier to reason about where to locate data and how to organize it.		Once written, data parallel programs can scale easily to large numbers of processors. The data parallel model implicitly encourages data locality by having each thread work on a chunk of data. The regular data chunks also make it easier to reason about where to locate data and how to organize it.

	==Definitions==		=Definitions=

	* ''Data parallel.'' A data parallel algorithm is composed of a set of identical tasks which operate on different subsets of common data.		* ''Data parallel.'' A data parallel algorithm is composed of a set of identical tasks which operate on different subsets of common data.
Line 143:		Line 143:
	* ''SIMD (single-instruction-multiple-data).'' A processor which executes a single instruction simultaneously on multiple data locations.		* ''SIMD (single-instruction-multiple-data).'' A processor which executes a single instruction simultaneously on multiple data locations.

	==References==		=References=

	* David E. Culler, Jaswinder Pal Singh, and Anoop Gupta, [http://portal.acm.org/citation.cfm?id=550071 ''Parallel Computer Architecture: A Hardware/Software Approach,''] Morgan-Kauffman, 1999.		* David E. Culler, Jaswinder Pal Singh, and Anoop Gupta, [http://portal.acm.org/citation.cfm?id=550071 ''Parallel Computer Architecture: A Hardware/Software Approach,''] Morgan-Kauffman, 1999.
Line 183:		Line 183:
	}		}
	-->		-->
	==Appendix: C for CUDA Example Code==		=Appendix: C for CUDA Example Code=

	The following code is a data parallel implementation of the sequential Code 2.3 from [[#References \| Solihin (2008)]] using [http://www.nvidia.com/object/cuda_learn.html C for CUDA]. It is presented to give an impression of programming for a SIMD architecture, but a detailed discussion is beyond the scope of this supplement. Ignoring memory allocation issues, the code is very similar to the data parallel example, Code 2.5 from [[#References \| Solihin (2008)]], discussed earlier. The main difference is the presence of a control thread that sends the parallel tasks to the CUDA device.		The following code is a data parallel implementation of the sequential Code 2.3 from [[#References \| Solihin (2008)]] using [http://www.nvidia.com/object/cuda_learn.html C for CUDA]. It is presented to give an impression of programming for a SIMD architecture, but a detailed discussion is beyond the scope of this supplement. Ignoring memory allocation issues, the code is very similar to the data parallel example, Code 2.5 from [[#References \| Solihin (2008)]], discussed earlier. The main difference is the presence of a control thread that sends the parallel tasks to the CUDA device.

Mpsenn: /* References */ deleting

2011-01-24T16:32:48Z

References: deleting

← Older revision		Revision as of 16:32, 24 January 2011
Line 240:		Line 240:
	cudaFree(d_sum);		cudaFree(d_sum);
	}		}

	~~=References=~~

	~~{{reflist}}~~

Mpsenn: /* Vector Machines */

2011-01-24T16:29:06Z

Vector Machines

← Older revision		Revision as of 16:29, 24 January 2011
Line 121:		Line 121:
	An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.		An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.

	References for this section		===References for this section===
	*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552		*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552
	*Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730		*Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730
	*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==

Mpsenn: /* History of Parallel Programming Models */ Moving references to bottom of section

2011-01-24T16:28:27Z

History of Parallel Programming Models: Moving references to bottom of section

← Older revision		Revision as of 16:28, 24 January 2011
Line 117:		Line 117:
	First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.		First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.

	The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.~~<ref>Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552</ref>~~		The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.

	An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points~~<ref>~~Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730~~</ref>, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.<ref>~~Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552~~</ref>~~		An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.

			References for this section
			*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552
			*Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730
			*Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==

Mpsenn: Adding reflist to bottom

2011-01-24T16:22:08Z

Adding reflist to bottom

← Older revision		Revision as of 16:22, 24 January 2011
Line 236:		Line 236:
	cudaFree(d_sum);		cudaFree(d_sum);
	}		}

			=References=

			{{reflist}}

Mpsenn: /* Vector Machines */ Adding references

2011-01-24T16:21:29Z

Vector Machines: Adding references

← Older revision		Revision as of 16:21, 24 January 2011
Line 117:		Line 117:
	First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.		First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.

	The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.		The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.<ref>Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552</ref>

	An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.		An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points<ref>Wikipedia, Cray-1 http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730</ref>, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.<ref>Wikipedia, Vector processor http://en.wikipedia.org/w/index.php?title=Vector_processor&oldid=405209552</ref>

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==

Mpsenn: /* Vector Machines */ Adding MFLOPs data

2011-01-24T16:14:53Z

Vector Machines: Adding MFLOPs data

← Older revision		Revision as of 16:14, 24 January 2011
Line 117:		Line 117:
	First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.		First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.

	The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems.		The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.

	An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased.		An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased. The Cray-1 could perform at 240 MFLOPS.

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==

Mpsenn: /* Vector Machines */

2011-01-24T16:12:37Z

Vector Machines

← Older revision		Revision as of 16:12, 24 January 2011
Line 118:		Line 118:

	The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems.		The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems.

			An innovation came with the Cray-1 supercomputer in 1976. It was realized that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased.

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==

Mpsenn: /* Vector Machines */

2011-01-24T16:04:30Z

Vector Machines

← Older revision		Revision as of 16:04, 24 January 2011
Line 114:		Line 114:

	===Vector Machines===		===Vector Machines===

			First appearing in the 1970s, vector machines were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.

			The Solomon project at Westinghouse was one of the first machines to use vector operations. It's CPU had a large number of ALUs that would each be fed different data each cycle. Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems.

	==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==		==Comparing the Data Parallel Model with the Shared Memory and Message Passing Models==