CSC/ECE 506 Spring 2011/ch2 cl - Revision history

Admin: /* Vector Machines */

2011-03-21T02:21:06Z

Vector Machines

← Older revision		Revision as of 02:21, 21 March 2011
Line 235:		Line 235:
	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. Its 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. 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.
Line 242:		Line 242:
	*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=

Admin: /* Example of Data Parallel Programing Model */

2011-03-21T02:12:06Z

Example of Data Parallel Programing Model

← Older revision		Revision as of 02:12, 21 March 2011
Line 31:		Line 31:
	pe_id = getid();		pe_id = getid();
	my_sum = 0;		my_sum = 0;
	'''~~for~~''' (i = pe_id; i < a.length; i += number_of_pe) //separate elements of the array are assigned to each PE		'''for_all''' (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;		a[i] = a[i] * i;

Cslingaf at 20:46, 7 February 2011

2011-02-07T20:46:24Z

← Older revision		Revision as of 20:46, 7 February 2011
Line 126:		Line 126:
	===1950's===		===1950's===
	*1955		*1955
	**IBM introduces the 704. Principal architect is Gene Amdahl; it is the first commercial machine with floating-point hardware, and is capable of approximately 5 ~~kFLOPS~~.		**IBM introduces the 704. Principal architect is Gene Amdahl; it is the first commercial machine with floating-point hardware, and is capable of approximately 5 k[http://en.wikipedia.org/wiki/FLOPS FLOPS].

	*1956		*1956

Cslingaf at 20:34, 7 February 2011

2011-02-07T20:34:17Z

← Older revision		Revision as of 20:34, 7 February 2011
Line 191:		Line 191:
	**J. R. Allen's Ph.D. thesis at Rice University introduces the concepts of loop-carried and loop-independent dependencies, and formalizes the process of vectorization.		**J. R. Allen's Ph.D. thesis at Rice University introduces the concepts of loop-carried and loop-independent dependencies, and formalizes the process of vectorization.
	**Scientific Computer Systems founded to design and market Cray-compatible minisupercomputers.		**Scientific Computer Systems founded to design and market Cray-compatible minisupercomputers.
	**CRAY-1 with 1 processor achieves 12.5 MFLOPS on the 100x100 LINPACK benchmark.		**CRAY-1 with 1 processor achieves 12.5 MFLOPS on the 100x100 [http://searchdatacenter.techtarget.com/definition/Linpack-benchmark LINPACK benchmark].

	*1984		*1984

Cslingaf: /* Definitions */

2011-02-07T20:30:36Z

Definitions

← Older revision		Revision as of 20:30, 7 February 2011
Line 266:		Line 266:
	* ''PE'' A Processing Element		* ''PE'' A Processing Element
	* ''PU'' A Processing Unit (synonymous with PE)		* ''PU'' A Processing Unit (synonymous with PE)
			* ''FLOPS'' FLoating point Operations Per Second (a 'benchmark' allowing comparisons between different parallel system architectures)

	=References=		=References=

Cslingaf: corrected graphic subtitle

2011-02-07T20:27:09Z

corrected graphic subtitle

← Older revision		Revision as of 20:27, 7 February 2011
Line 120:		Line 120:
	===Comparison Diagram===		===Comparison Diagram===
	The following diagram may be of use conceptually distinguishing between data parallelism (SIMD: Single Instruction, Multiple Data) and task parallelism (MIMD: Multiple Instruction, Multiple Data). In the SIMD, it is observed that a single instruction runs to multiple processors which then access multiple connections to the data. In contrast, the MIMD has multiple instruction streams (evidenced by two groups of processors) which interact, again, with multiple connections to the data		The following diagram may be of use conceptually distinguishing between data parallelism (SIMD: Single Instruction, Multiple Data) and task parallelism (MIMD: Multiple Instruction, Multiple Data). In the SIMD, it is observed that a single instruction runs to multiple processors which then access multiple connections to the data. In contrast, the MIMD has multiple instruction streams (evidenced by two groups of processors) which interact, again, with multiple connections to the data
	[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism]]		[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism (PU (Processing Unit) and PE (processing Element) are synonymous]]

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

Cslingaf: Added PE/PU definitions

2011-02-07T20:23:31Z

Added PE/PU definitions

← Older revision		Revision as of 20:23, 7 February 2011
Line 264:		Line 264:
	* ''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.
	* ''MIMD (multiple instruction, multiple data).'' A processor which executes multiple instructions simultaneously on multiple data locations		* ''MIMD (multiple instruction, multiple data).'' A processor which executes multiple instructions simultaneously on multiple data locations
			* ''PE'' A Processing Element
			* ''PU'' A Processing Unit (synonymous with PE)

	=References=		=References=

Cslingaf: moved comparison diagram to correct section

2011-02-07T20:19:35Z

moved comparison diagram to correct section

← Older revision		Revision as of 20:19, 7 February 2011
Line 79:		Line 79:
	Since each parallel task is unique, a major limitation of task parallel algorithms is that the maximum degree of parallelism attainable is limited to the number of tasks that have been formulated. This is in contrast to data parallel algorithms, which can be scaled easily to take advantage of an arbitrary number of processing elements. In addition, unique tasks are likely to have significantly different run times, making it more challenging to balance load across processors. [[#References \| Haveraaen (2000)]] also notes that task parallel algorithms are inherently more complex, requiring a greater degree of communication and synchronization. In the task parallel code above, after thread 0 computes an element of ''a'' it must send it to thread 1. To support this, sends and receives occur every iteration of the two loops, resulting in a total of 8 messages being sent between the threads. In contrast, the data parallel code sends only 2 messages, one at the beginning and one at the end.		Since each parallel task is unique, a major limitation of task parallel algorithms is that the maximum degree of parallelism attainable is limited to the number of tasks that have been formulated. This is in contrast to data parallel algorithms, which can be scaled easily to take advantage of an arbitrary number of processing elements. In addition, unique tasks are likely to have significantly different run times, making it more challenging to balance load across processors. [[#References \| Haveraaen (2000)]] also notes that task parallel algorithms are inherently more complex, requiring a greater degree of communication and synchronization. In the task parallel code above, after thread 0 computes an element of ''a'' it must send it to thread 1. To support this, sends and receives occur every iteration of the two loops, resulting in a total of 8 messages being sent between the threads. In contrast, the data parallel code sends only 2 messages, one at the beginning and one at the end.

	The following diagram may be of use conceptually distinguishing between data parallelism (SIMD: Single Instruction, Multiple Data) and task parallelism (MIMD: Multiple Instruction, Multiple Data). In the SIMD, it is observed that a single instruction runs to multiple processors which then access multiple connections to the data. In contrast, the MIMD has multiple instruction streams (evidenced by two groups of processors) which interact, again, with multiple connections to the data
	~~[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism]]~~

	==Comparison between Data and Task Parallel Programming Models==		==Comparison between Data and Task Parallel Programming Models==
Line 119:		Line 118:
	Data parallelism's synchronous nature and task parallelism's asynchronism give rise to another pair of features that add to the difference between these two models: determinism versus non-determinism. Data parallelism is deterministic, i.e. computing with the same input will always yield the same result, since its synchronism ensures that issues like relative timing between PEs will not arise. In contrast, task parallelism's asynchronous updates of common data can give rise to non-determinism, i.e, the same input won't always yield the same computation result (the result of a computation will depend also on factors outside the program control, such as scheduling and timing of other PEs). Obviously, non-determinism makes it harder to write and maintain correct programs. This partially explains the advantage of data parallel programming model over data parallelism in terms of development effort (also discussed in section 4.2).		Data parallelism's synchronous nature and task parallelism's asynchronism give rise to another pair of features that add to the difference between these two models: determinism versus non-determinism. Data parallelism is deterministic, i.e. computing with the same input will always yield the same result, since its synchronism ensures that issues like relative timing between PEs will not arise. In contrast, task parallelism's asynchronous updates of common data can give rise to non-determinism, i.e, the same input won't always yield the same computation result (the result of a computation will depend also on factors outside the program control, such as scheduling and timing of other PEs). Obviously, non-determinism makes it harder to write and maintain correct programs. This partially explains the advantage of data parallel programming model over data parallelism in terms of development effort (also discussed in section 4.2).

			===Comparison Diagram===
			The following diagram may be of use conceptually distinguishing between data parallelism (SIMD: Single Instruction, Multiple Data) and task parallelism (MIMD: Multiple Instruction, Multiple Data). In the SIMD, it is observed that a single instruction runs to multiple processors which then access multiple connections to the data. In contrast, the MIMD has multiple instruction streams (evidenced by two groups of processors) which interact, again, with multiple connections to the data
			[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism]]

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

Cslingaf: /* Definitions */

2011-01-31T22:14:13Z

Definitions

← Older revision		Revision as of 22:14, 31 January 2011
Line 260:		Line 260:
	* ''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.
	* ''Task parallel.'' A task parallel algorithm is composed of a set of differing tasks which operate on common data.		* ''Task parallel.'' A task parallel algorithm is composed of a set of differing tasks which operate on common data.
	* ''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.
			* ''MIMD (multiple instruction, multiple data).'' A processor which executes multiple instructions simultaneously on multiple data locations

	=References=		=References=

Cslingaf at 22:11, 31 January 2011

2011-01-31T22:11:24Z

← Older revision		Revision as of 22:11, 31 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 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 as a point of contrast.

	=~~Data Parallel~~ 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.		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.
Line 82:		Line 82:
	[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism]]		[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism]]

			==Comparison between Data and Task Parallel Programming Models==

	~~The table below summarizes the key differences between data parallel and task parallel programming models.~~

	{\| class="wikitable" border="1" align="center"		{\| class="wikitable" border="1" align="center"
Line 113:		Line 113:
	\|}		\|}

	==Synchronous vs Asynchronous==		===Synchronous vs Asynchronous===
	While the [http://en.wikipedia.org/wiki/Lockstep_(computing) lockstep] imposed by data parallelism on all data streams ensures synchronous computation (all PEs perform their tasks at the exact same pace), every processor in task parallelism performs its task at their own pace, which we call asynchronous computation. Thus, at a certain point of a task parallel program's execution, communication and synchronization primitives are needed to allow different instruction streams to coordinate their efforts, and that is where variable-sharing and message-passing come into play.		While the [http://en.wikipedia.org/wiki/Lockstep_(computing) lockstep] imposed by data parallelism on all data streams ensures synchronous computation (all PEs perform their tasks at the exact same pace), every processor in task parallelism performs its task at their own pace, which we call asynchronous computation. Thus, at a certain point of a task parallel program's execution, communication and synchronization primitives are needed to allow different instruction streams to coordinate their efforts, and that is where variable-sharing and message-passing come into play.

	== Determinism vs. Non-Determinism ==		===Determinism vs. Non-Determinism===
	Data parallelism's synchronous nature and task parallelism's asynchronism give rise to another pair of features that add to the difference between these two models: determinism versus non-determinism. Data parallelism is deterministic, i.e. computing with the same input will always yield the same result, since its synchronism ensures that issues like relative timing between PEs will not arise. In contrast, task parallelism's asynchronous updates of common data can give rise to non-determinism, i.e, the same input won't always yield the same computation result (the result of a computation will depend also on factors outside the program control, such as scheduling and timing of other PEs). Obviously, non-determinism makes it harder to write and maintain correct programs. This partially explains the advantage of data parallel programming model over data parallelism in terms of development effort (also discussed in section 4.2).		Data parallelism's synchronous nature and task parallelism's asynchronism give rise to another pair of features that add to the difference between these two models: determinism versus non-determinism. Data parallelism is deterministic, i.e. computing with the same input will always yield the same result, since its synchronism ensures that issues like relative timing between PEs will not arise. In contrast, task parallelism's asynchronous updates of common data can give rise to non-determinism, i.e, the same input won't always yield the same computation result (the result of a computation will depend also on factors outside the program control, such as scheduling and timing of other PEs). Obviously, non-determinism makes it harder to write and maintain correct programs. This partially explains the advantage of data parallel programming model over data parallelism in terms of development effort (also discussed in section 4.2).