CSC/ECE 506 Spring 2010/ch 2 aj/Data Parallel Programming - Revision history

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

2010-05-04T03:43:24Z

Example of Data Parallel Programing Model

← Older revision		Revision as of 03:43, 4 May 2010
Line 39:		Line 39:


	When we ~~implement~~ 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.		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.


Line 55:		Line 55:


	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.		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])]]		[[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])]]

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

2010-02-23T20:54:26Z

Example of Data Parallel Programing Model

← Older revision		Revision as of 20:54, 23 February 2010
Line 24:		Line 24:


	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.		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.

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

2010-02-23T20:54:13Z

Example of Data Parallel Programing Model

← Older revision		Revision as of 20:54, 23 February 2010
Line 24:		Line 24:


	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.		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.

Zzhang14: /* Data parallelism vs Task parallelism */

2010-02-06T04:20:41Z

Data parallelism vs Task parallelism

← Older revision		Revision as of 04:20, 6 February 2010
Line 12:		Line 12:

	= Data parallelism vs Task parallelism =		= Data parallelism vs Task parallelism =
	One important feature of data-parallel programming model or data parallelism (SIMD) is the single control flow: there is only one control processor that directs the activities of all the processing elements. In stark contrast to this is task parallelism (MIMD: Multiple Instruction, Multiple Data): characterized by its multiple control flows, it allows the concurrent execution of multiple instruction streams, each manipulates its own data and services separate functions. Below ~~are contrasts of~~ the data parallelism and task parallelism models from wikipedia: [http://en.wikipedia.org/wiki/SIMD SIMD] and [http://en.wikipedia.org/wiki/MIMD MIMD]. In the following subsections we continue to compare and contrast different features of data-parallel model and task-parallel model to help reader understand the unique characteristics of data-parallel programming model.		One important feature of data-parallel programming model or data parallelism (SIMD) is the single control flow: there is only one control processor that directs the activities of all the processing elements. In stark contrast to this is task parallelism (MIMD: Multiple Instruction, Multiple Data): characterized by its multiple control flows, it allows the concurrent execution of multiple instruction streams, each manipulates its own data and services separate functions. Below is a contrast between the data parallelism and task parallelism models from wikipedia: [http://en.wikipedia.org/wiki/SIMD SIMD] and [http://en.wikipedia.org/wiki/MIMD MIMD]. In the following subsections we continue to compare and contrast different features of data-parallel model and task-parallel model to help reader understand the unique characteristics of data-parallel programming model.
	[[Image:Smid.png\|frame\|center\|425px]]		[[Image:Smid.png\|frame\|center\|425px\|contrast between data parallelism and task parallelism]]

	== Synchronous vs Asynchronous ==		== Synchronous vs Asynchronous ==

Zzhang14: /* References */

2010-02-06T04:15:58Z

References

← Older revision		Revision as of 04:15, 6 February 2010
Line 131:		Line 131:

	8) ''MIMD'', Wikipedia, the free encyclopedia, [http://en.wikipedia.org/wiki/MIMD http://en.wikipedia.org/wiki/MIMD].		8) ''MIMD'', Wikipedia, the free encyclopedia, [http://en.wikipedia.org/wiki/MIMD http://en.wikipedia.org/wiki/MIMD].

			9) ''Lockstep'', Wikipedia, the free encyclopedia, [http://en.wikipedia.org/wiki/Lockstep_(computing) http://en.wikipedia.org/wiki/Lockstep_(computing)].

			10) ''SPMD'', Wikipedia, the free encyclopedia, [http://en.wikipedia.org/wiki/SPMD http://en.wikipedia.org/wiki/SPMD].

Zzhang14: /* Data parallelism vs Task parallelism */

2010-02-06T04:13:10Z

Data parallelism vs Task parallelism

← Older revision		Revision as of 04:13, 6 February 2010
Line 12:		Line 12:

	= Data parallelism vs Task parallelism =		= Data parallelism vs Task parallelism =
	One important feature of data parallel programming model or data parallelism (SIMD) is the single control flow: there is only one control processor that directs the activities of all the processing elements. In stark contrast to this is task parallelism (MIMD: Multiple Instruction, Multiple Data): characterized by its multiple control flows, it allows the concurrent execution of multiple instruction streams, each manipulates its own data and services separate functions. Below are contrasts of the data parallelism and task parallelism models from wikipedia: [http://en.wikipedia.org/wiki/SIMD SIMD] and [http://en.wikipedia.org/wiki/MIMD MIMD].		One important feature of data-parallel programming model or data parallelism (SIMD) is the single control flow: there is only one control processor that directs the activities of all the processing elements. In stark contrast to this is task parallelism (MIMD: Multiple Instruction, Multiple Data): characterized by its multiple control flows, it allows the concurrent execution of multiple instruction streams, each manipulates its own data and services separate functions. Below are contrasts of the data parallelism and task parallelism models from wikipedia: [http://en.wikipedia.org/wiki/SIMD SIMD] and [http://en.wikipedia.org/wiki/MIMD MIMD]. In the following subsections we continue to compare and contrast different features of data-parallel model and task-parallel model to help reader understand the unique characteristics of data-parallel programming model.
	[[Image:Smid.png\|frame\|center\|425px]]		[[Image:Smid.png\|frame\|center\|425px]]

Zzhang14: /* Synchronous vs Asynchronous */

2010-02-06T04:08:41Z

Synchronous vs Asynchronous

← Older revision		Revision as of 04:08, 6 February 2010
Line 16:		Line 16:

	== 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 the execution~~ of a task parallel program, communication and synchronization primitives are needed to allow different instruction streams to coordinate their efforts, and that is where variable-sharing and message-passing ~~comes~~ 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 ==

Zzhang14: /* Synchronous vs Asynchronous */

2010-02-06T04:06:59Z

Synchronous vs Asynchronous

← Older revision		Revision as of 04:06, 6 February 2010
Line 16:		Line 16:

	== Synchronous vs Asynchronous ==		== Synchronous vs Asynchronous ==
	While data parallelism~~'s single control flow over~~ all ~~processing elements~~ 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 the execution of a task parallel program, communication and synchronization primitives are needed to allow different instruction streams to coordinate their efforts, and that is where variable-sharing and message-passing comes 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 the execution of a task parallel program, communication and synchronization primitives are needed to allow different instruction streams to coordinate their efforts, and that is where variable-sharing and message-passing comes into play.

	== Determinism vs. Non-Determinism ==		== Determinism vs. Non-Determinism ==

Zzhang14: /* Comparison in different aspects */

2010-02-06T03:18:36Z

Comparison in different aspects

← Older revision		Revision as of 03:18, 6 February 2010
Line 90:		Line 90:
	}		}

	== Comparison in ~~different aspects~~ ==		== Comparison in Different Aspects ==
	The table below is extended from Table 2.1 on page 22 of the Solihin text. A column has been added for the data-parallel model. The table compares some key characteristics of each programming model. As you can see, the complexity of the data-parallel model comes mainly in the form of dividing up the work among PEs. Most of this work is done by the programmer and does not necessarily require special hardware, although, specific types of hardware can optimize the benefits of the model. For instance, SIMD and SPMD hardware are examples that have efficiently utilized the data-parallel model.		The table below is extended from Table 2.1 on page 22 of the Solihin text. A column has been added for the data-parallel model. The table compares some key characteristics of each programming model. As you can see, the complexity of the data-parallel model comes mainly in the form of dividing up the work among PEs. Most of this work is done by the programmer and does not necessarily require special hardware, although, specific types of hardware can optimize the benefits of the model. For instance, SIMD and SPMD hardware are examples that have efficiently utilized the data-parallel model.

Line 113:		Line 113:
	\| high \|\| high \|\| low		\| high \|\| high \|\| low
	\|}		\|}




	= References =		= References =

Zzhang14: /* Example continued */

2010-02-06T03:18:18Z

Example continued

← Older revision		Revision as of 03:18, 6 February 2010
Line 60:		Line 60:

	= Other Parallel Programming Models =		= Other Parallel Programming Models =
	== Example ~~continued~~ ==		== Example Continued ==
	As previously mentioned, the shared memory and message passing parallel programming models are commonly used. The following descriptions and code snippets are intended to develop a contrast between the data-parallel programming model and the other two models.		As previously mentioned, the shared memory and message passing parallel programming models are commonly used. The following descriptions and code snippets are intended to develop a contrast between the data-parallel programming model and the other two models.