CSC/ECE 506 Spring 2012/3a df - Revision history

Ajdavis7: /* Complex Patterns */

2012-02-20T22:50:57Z

Complex Patterns

← Older revision		Revision as of 22:50, 20 February 2012
Line 131:		Line 131:
	Complex patterns involve the interplay between two or more parallel patterns, or are a single pattern that greatly deviates from a common implementation itself. Such algorithms require moderate to advanced programmer skill, and are almost always accompanied by a framework or involve a significant amount of custom "infrastructural" code to accomodate the needs of the architecture.		Complex patterns involve the interplay between two or more parallel patterns, or are a single pattern that greatly deviates from a common implementation itself. Such algorithms require moderate to advanced programmer skill, and are almost always accompanied by a framework or involve a significant amount of custom "infrastructural" code to accomodate the needs of the architecture.
	* '''Multi-grid'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/multigrid.pdf Multigrid Pattern] at UIUC Computer Science Department</ref> - Multiple geometric grids are employed with an iterative solver in order to determine efficient grid granularity		* '''Multi-grid'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/multigrid.pdf Multigrid Pattern] at UIUC Computer Science Department</ref> - Multiple geometric grids are employed with an iterative solver in order to determine efficient grid granularity
	* '''Multi-domain'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/multidomain.pdf Multi-domain Pattern] at UIUC Computer Science Department</ref> - Leverage different domains (spatial, frequency) to come to a solution more quickly		* '''Multi-domain'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/multidomain.pdf Multi-domain Pattern] at UIUC Computer Science Department</ref> - Leverage different mathematical domains (spatial, frequency; Fourier, Laplace) to come to a solution more quickly
	* '''Odd-Even Communication Group'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/oddeven.pdf Odd-Even Communication Group] at UIUC Computer Science Department</ref> - Recursive data structure that allows for more efficient operations on nodes		* '''Odd-Even Communication Group'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/oddeven.pdf Odd-Even Communication Group] at UIUC Computer Science Department</ref> - Recursive data structure that allows for more efficient operations on nodes
	* '''Loosely Synchronous'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/loosely_synchronous.doc Loosely Synchronous Model As Parallel Structure] at UIUC Computer Science Department</ref> - Use of phases to simplify the assumptions on parallel processes		* '''Loosely Synchronous'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/loosely_synchronous.doc Loosely Synchronous Model As Parallel Structure] at UIUC Computer Science Department</ref> - Use of phases to simplify the assumptions on parallel processes

Ajdavis7: /* Geometric */

2012-02-20T22:49:52Z

Geometric

← Older revision		Revision as of 22:49, 20 February 2012
Line 119:		Line 119:
	===Geometric===		===Geometric===
	[[Image:506-2012-Spring-3a-df-geometric.png\|right\|thumb\|200px\|Geometric pattern]]		[[Image:506-2012-Spring-3a-df-geometric.png\|right\|thumb\|200px\|Geometric pattern]]
	The Geometric pattern<ref name="kim_ppp_ppt"/> is a specialized implementation of the Divide & Conquer pattern. It differs in that there is sharing of data on boundaries of the problem, be that the first and last elements of different sets (1D), perimeters (2D), or faces (3D). The significant difference between the Geometric and Divide & Conquer patterns is that in the Geometric pattern, there is ideally no sub-problem step, as the inter-process communication that might occur is used in the current process’ calculation and does not have to subsequently be calculated. A great example of the Geometric pattern is a fluid simulation, where a matrix (or higher dimension) data set must be analyzed for changes in motion.		The Geometric pattern<ref name="kim_ppp_ppt"/> is a specialized implementation of the Divide & Conquer pattern. It differs in that there is sharing of data on boundaries of the problem, be that the first and last elements of different sets (1D), perimeters (2D), or faces (3D). The significant difference between the Geometric and Divide & Conquer patterns is that in the Geometric pattern, there is ideally no sub-problem step, as the inter-process communication that might occur is used in the current process’ calculation and does not have to subsequently be calculated. A great example of the Geometric pattern is a fluid simulation, where a matrix (or higher dimension such as cubic or quartic) data set must be analyzed for changes in motion.

	===Irregular Mesh===		===Irregular Mesh===

Ajdavis7: /* Recursive Data */

2012-02-20T22:49:13Z

Recursive Data

← Older revision		Revision as of 22:49, 20 February 2012
Line 115:		Line 115:
	===Recursive Data===		===Recursive Data===
	[[Image:506-2012-Spring-3a-df-recursive.png\|right\|thumb\|200px\|Recursive Data pattern]]		[[Image:506-2012-Spring-3a-df-recursive.png\|right\|thumb\|200px\|Recursive Data pattern]]
	The Recursive Data pattern<ref name="kim_ppp_ppt"/> presents an interesting problem for parallel algorithms; while the need is common, its solution can be very complex depending on the data structure. In general, when working with recursive data structures, it is desired for any and all commonalities and reductions to be established in order to minimize the operations required to traverse the structure. Once the structure is mapped (or its behavior analyzed), other parallel patterns can be employed. One possible example is that of an electric utility’s mesh network of smart meters. Hub (head-end) units where data is aggregated need to employ parallel processing in order to efficiently collect usage data. For smaller hubs, it might be beneficial to communicate directly with the meters, whereas for larger hubs it may be more prudent to communicate with smaller hubs. In such a case, Recursive Data can be paired with Divide & Conquer to come to a solution much faster than its serial or naively parallel alternatives.		The Recursive Data pattern<ref name="kim_ppp_ppt"/> presents an interesting problem for parallel algorithms; while the need is common, its solution can be very complex depending on the data structure. In general, when working with recursive data structures, it is desired for any and all commonalities and reductions to be established in order to minimize the operations required to traverse the structure. Once the structure is mapped (or its behavior analyzed), other parallel patterns can be employed. One possible example is that of an electric utility’s mesh network of [http://en.wikipedia.org/wiki/Smart_meter smart meters]. Hub (head-end) units where data is aggregated need to employ parallel processing in order to efficiently collect usage data. For smaller hubs, it might be beneficial to communicate directly with the meters, whereas for larger hubs it may be more prudent to communicate with smaller hubs. In such a case, Recursive Data can be paired with Divide & Conquer to come to a solution much faster than its serial or naively parallel alternatives.

	===Geometric===		===Geometric===

Ajdavis7: /* Pipeline */

2012-02-20T22:47:33Z

Pipeline

← Older revision		Revision as of 22:47, 20 February 2012
Line 109:		Line 109:
	===Pipeline===		===Pipeline===
	[[Image:506-2012-Spring-3a-df-pipeline.png\|right\|thumb\|200px\|Pipeline pattern]]		[[Image:506-2012-Spring-3a-df-pipeline.png\|right\|thumb\|200px\|Pipeline pattern]]
	The Pipeline pattern<ref name="kim_ppp_ppt"/> is a hybrid of the “Embarrassingly” Parallel pattern as well as the Replicable pattern. The best way to think of the Pipeline pattern is as an assembly line <ref name=”pipeline_wiki”>[http://en.wikipedia.org/wiki/Pipeline_(computing) Pipeline (computing)] on Wikipedia</ref>. Suppose there are three steps in assembling a computer: un-packaging the internals, installing the internals, and performing a first-boot diagnostic, all of which take 15 minutes each. In a serial pattern, the entire process takes 45 minutes for one assembled computer, and it takes 45 more minutes for another computer to be assembled. In a Pipeline pattern, however, that same process would still have the same [http://en.wikipedia.org/wiki/Latency_(engineering)#Computer_hardware_and_operating_system_latency latency] (since it takes 45 minutes for a particular computer to be built), but the overall throughput is increased because a computer in general is completed every 15 minutes after the first one.		The Pipeline pattern<ref name="kim_ppp_ppt"/> is a hybrid of the “Embarrassingly” Parallel pattern as well as the Replicable pattern. The best way to think of the Pipeline pattern is as an assembly line <ref name=”pipeline_wiki”>[http://en.wikipedia.org/wiki/Pipeline_(computing) Pipeline (computing)] on Wikipedia</ref>. Suppose there are three steps in assembling a computer: un-packaging the internals, installing the internals, and performing a first-boot diagnostic, all of which take 15 minutes each. In a serial pattern, the entire process takes 45 minutes for one assembled computer, and it takes 45 more minutes for another computer to be assembled. In a Pipeline pattern, however, that same process would still have the same [http://en.wikipedia.org/wiki/Latency_(engineering)#Computer_hardware_and_operating_system_latency latency] (since it takes 45 minutes for a particular computer to be built), but the overall [http://en.wikipedia.org/wiki/Throughput throughput] is increased because a computer in general is completed every 15 minutes after the first one.

	Pipelining differs from the Replicable pattern because in Pipeline only one copy of the resources is available. Referring back to the assembly line example, there is only one station for un-packaging, one station for installation, and one station for diagnostics. In a Replicable pattern, however, each work stream would have its own copy of the resources, so that the same steps could occur simultaneously. To be sure, this does nothing for latency, but has the capability to increase throughput dramatically.		Pipelining differs from the Replicable pattern because in Pipeline only one copy of the resources is available. Referring back to the assembly line example, there is only one station for un-packaging, one station for installation, and one station for diagnostics. In a Replicable pattern, however, each work stream would have its own copy of the resources, so that the same steps could occur simultaneously. To be sure, this does nothing for latency, but has the capability to increase throughput dramatically.

Ajdavis7: /* Pipeline */

2012-02-20T22:46:44Z

Pipeline

← Older revision		Revision as of 22:46, 20 February 2012
Line 109:		Line 109:
	===Pipeline===		===Pipeline===
	[[Image:506-2012-Spring-3a-df-pipeline.png\|right\|thumb\|200px\|Pipeline pattern]]		[[Image:506-2012-Spring-3a-df-pipeline.png\|right\|thumb\|200px\|Pipeline pattern]]
	The Pipeline pattern<ref name="kim_ppp_ppt"/> is a hybrid of the “Embarrassingly” Parallel pattern as well as the Replicable pattern. The best way to think of the Pipeline pattern is as an assembly line <ref name=”pipeline_wiki”>[http://en.wikipedia.org/wiki/Pipeline_(computing) Pipeline (computing)] on Wikipedia</ref>. Suppose there are three steps in assembling a computer: un-packaging the internals, installing the internals, and performing a first-boot diagnostic, all of which take 15 minutes each. In a serial pattern, the entire process takes 45 minutes for one assembled computer, and it takes 45 more minutes for another computer to be assembled. In a Pipeline pattern, however, that same process would still have the same latency (since it takes 45 minutes for a particular computer to be built), but the overall throughput is increased because a computer in general is completed every 15 minutes after the first one.		The Pipeline pattern<ref name="kim_ppp_ppt"/> is a hybrid of the “Embarrassingly” Parallel pattern as well as the Replicable pattern. The best way to think of the Pipeline pattern is as an assembly line <ref name=”pipeline_wiki”>[http://en.wikipedia.org/wiki/Pipeline_(computing) Pipeline (computing)] on Wikipedia</ref>. Suppose there are three steps in assembling a computer: un-packaging the internals, installing the internals, and performing a first-boot diagnostic, all of which take 15 minutes each. In a serial pattern, the entire process takes 45 minutes for one assembled computer, and it takes 45 more minutes for another computer to be assembled. In a Pipeline pattern, however, that same process would still have the same [http://en.wikipedia.org/wiki/Latency_(engineering)#Computer_hardware_and_operating_system_latency latency] (since it takes 45 minutes for a particular computer to be built), but the overall throughput is increased because a computer in general is completed every 15 minutes after the first one.

	Pipelining differs from the Replicable pattern because in Pipeline only one copy of the resources is available. Referring back to the assembly line example, there is only one station for un-packaging, one station for installation, and one station for diagnostics. In a Replicable pattern, however, each work stream would have its own copy of the resources, so that the same steps could occur simultaneously. To be sure, this does nothing for latency, but has the capability to increase throughput dramatically.		Pipelining differs from the Replicable pattern because in Pipeline only one copy of the resources is available. Referring back to the assembly line example, there is only one station for un-packaging, one station for installation, and one station for diagnostics. In a Replicable pattern, however, each work stream would have its own copy of the resources, so that the same steps could occur simultaneously. To be sure, this does nothing for latency, but has the capability to increase throughput dramatically.

Ajdavis7: /* "Embarrassingly" Parallel */

2012-02-20T22:35:01Z

"Embarrassingly" Parallel

← Older revision		Revision as of 22:35, 20 February 2012
Line 9:		Line 9:
	Intuitive patterns are termed as such because even those with basic knowledge of parallel processes could create their design. They are obvious, straight-forward applications of parallel computing tasks, and their implementation and use are easily implemented even without specialized software packages or advanced [http://en.wikipedia.org/wiki/Algorithm algorithm] development.		Intuitive patterns are termed as such because even those with basic knowledge of parallel processes could create their design. They are obvious, straight-forward applications of parallel computing tasks, and their implementation and use are easily implemented even without specialized software packages or advanced [http://en.wikipedia.org/wiki/Algorithm algorithm] development.
	==="Embarrassingly" Parallel===		==="Embarrassingly" Parallel===
	Embarrassingly parallel patterns<ref name="kim_ppp_ppt">[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt Parallel Programming Patterns] by Eun-Gyu Kim</ref> are those in which the tasks to be performed are completely disparate. Specifically, these operations occur when the datasets of concern are able to be abstracted to a point where the resources are not in contention. Examples abound of this behavior in productivity programs like Word or Outlook, when a spell-check or auto-archive operation is in progress.		Embarrassingly parallel patterns<ref name="kim_ppp_ppt">[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt Parallel Programming Patterns] by Eun-Gyu Kim</ref> are those in which the tasks to be performed are completely disparate. Specifically, these operations occur when the datasets of concern are able to be abstracted to a point where the resources are not in contention. Examples abound of this behavior in productivity programs like [http://en.wikipedia.org/wiki/Microsoft_Office Microsoft Word or Outlook], when a spell-check or auto-archive operation is in progress.

	===Replicable===		===Replicable===

Ajdavis7: /* Introduction */

2012-02-20T22:34:21Z

Introduction

← Older revision		Revision as of 22:34, 20 February 2012
Line 2:		Line 2:

	==Introduction==		==Introduction==
	Computer programming has gone through several paradigm shifts in regards to how software is design and constructed. In more recent years with the advent of object-oriented programming, an effort was made by the “[http://en.wikipedia.org/wiki/Design_Patterns Gang of Four]” to categorize different arrangements and relationships between programming objects in terms of commonly used [http://en.wikipedia.org/wiki/Design_patterns design patterns]. In a similar vein, with recent advances in parallel programming and availability of hardware, there are several common designs that can be drawn from the vast amount of literature available. Although there exists no canonical text for parallel programing as there exists for object oriented programming, there is substantial overlap, which is presented here.		Computer programming has gone through several paradigm shifts in regards to how software is design and constructed. In more recent years with the advent of object-oriented programming, an effort was made by the "[http://en.wikipedia.org/wiki/Design_Patterns Gang of Four]" to categorize different arrangements and relationships between programming objects in terms of commonly used [http://en.wikipedia.org/wiki/Design_patterns design patterns]. In a similar vein, with recent advances in parallel programming and availability of hardware, there are several common designs that can be drawn from the vast amount of literature available. Although there exists no canonical text for parallel programing as there exists for object oriented programming, there is substantial overlap, which is presented here.

	Overall, programming patterns can be split into three categories of similar abstraction: intuitive, common, and complex, with each having involvement with architecture, design, and idioms.<ref name="ortega">Ortega-Arjona, Jorge Luis. Patterns for Parallel Software Design. Hoboken, NJ: John Wiley, 2010</ref> An architectural pattern defines software organization, a design pattern is a refinement of an architectural pattern in regards to solving a particular pattern, and an idiom is a particular implementation of a design pattern in a programming language or framework. This chapter will focus on architectural and design patterns.		Overall, programming patterns can be split into three categories of similar [http://en.wikipedia.org/wiki/Abstraction_(computer_science) abstraction]: intuitive, common, and complex, with each having involvement with architecture, design, and idioms.<ref name="ortega">Ortega-Arjona, Jorge Luis. Patterns for Parallel Software Design. Hoboken, NJ: John Wiley, 2010</ref> An architectural pattern defines software organization, a design pattern is a refinement of an architectural pattern in regards to solving a particular pattern, and an idiom is a particular implementation of a design pattern in a programming language or framework. This chapter will focus on architectural and design patterns.

	==Intuitive Patterns==		==Intuitive Patterns==

Ajdavis7: /* Intuitive Patterns */

2012-02-20T22:33:34Z

Intuitive Patterns

← Older revision		Revision as of 22:33, 20 February 2012
Line 7:		Line 7:

	==Intuitive Patterns==		==Intuitive Patterns==
	Intuitive patterns are termed as such because even those with basic knowledge of parallel processes could create their design. They are obvious, straight-forward applications of parallel computing tasks, and their implementation and use are easily implemented even without specialized software packages or advanced algorithm development.		Intuitive patterns are termed as such because even those with basic knowledge of parallel processes could create their design. They are obvious, straight-forward applications of parallel computing tasks, and their implementation and use are easily implemented even without specialized software packages or advanced [http://en.wikipedia.org/wiki/Algorithm algorithm] development.
	==="Embarrassingly" Parallel===		==="Embarrassingly" Parallel===
	Embarrassingly parallel patterns<ref name="kim_ppp_ppt">[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt Parallel Programming Patterns] by Eun-Gyu Kim</ref> are those in which the tasks to be performed are completely disparate. Specifically, these operations occur when the datasets of concern are able to be abstracted to a point where the resources are not in contention. Examples abound of this behavior in productivity programs like Word or Outlook, when a spell-check or auto-archive operation is in progress.		Embarrassingly parallel patterns<ref name="kim_ppp_ppt">[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt Parallel Programming Patterns] by Eun-Gyu Kim</ref> are those in which the tasks to be performed are completely disparate. Specifically, these operations occur when the datasets of concern are able to be abstracted to a point where the resources are not in contention. Examples abound of this behavior in productivity programs like Word or Outlook, when a spell-check or auto-archive operation is in progress.

Ajdavis7: /* Example */

2012-02-20T22:32:43Z

Example

← Older revision		Revision as of 22:32, 20 February 2012
Line 16:		Line 16:
	[[Image:506-2012-Spring-3a-df-repl.png\|center\|thumb\|400px\|Replicable pattern, shown enlarged due to its centrality to other patterns]]		[[Image:506-2012-Spring-3a-df-repl.png\|center\|thumb\|400px\|Replicable pattern, shown enlarged due to its centrality to other patterns]]
	====Example====		====Example====
	Because the Replicable pattern is so important to subsequent patterns, a fully developed example using C and OpenMP (mentioned later in this chapter) is provided below.		Because the Replicable pattern is so important to subsequent patterns, a fully developed example using C and OpenMP (mentioned later in this chapter) is provided [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2012/3a_df#Frameworks below].
	=====Code Listing=====		=====Code Listing=====
	<pre>// This code example for the Replicable pattern spawns four threads which copy		<pre>// This code example for the Replicable pattern spawns four threads which copy

Ajdavis7: /* Replicable */

2012-02-20T22:29:36Z

Replicable

← Older revision		Revision as of 22:29, 20 February 2012
Line 12:		Line 12:

	===Replicable===		===Replicable===
			====Description====
	The Replicable pattern comes from the fact that data available to all processes needs to be duplicated for use in other processes<ref name="kim_ppp_ppt"/>. This necessitates a reduction step where the results from all of the tasks is analyzed for the total final result. An application of this pattern could be in certain kinds of encryption algorithms where a set of data can be broken into "chunks" of a particular size, decrypted seperately, and joined back together at the end.		The Replicable pattern comes from the fact that data available to all processes needs to be duplicated for use in other processes<ref name="kim_ppp_ppt"/>. This necessitates a reduction step where the results from all of the tasks is analyzed for the total final result. An application of this pattern could be in certain kinds of encryption algorithms where a set of data can be broken into "chunks" of a particular size, decrypted seperately, and joined back together at the end.
	[[Image:506-2012-Spring-3a-df-repl.png\|center\|thumb\|400px\|Replicable pattern, shown enlarged due to its centrality to other patterns]]		[[Image:506-2012-Spring-3a-df-repl.png\|center\|thumb\|400px\|Replicable pattern, shown enlarged due to its centrality to other patterns]]
			====Example====
	Because the Replicable pattern is so important to subsequent patterns, a fully developed example using C and OpenMP (mentioned later in this chapter) is provided below.		Because the Replicable pattern is so important to subsequent patterns, a fully developed example using C and OpenMP (mentioned later in this chapter) is provided below.
			=====Code Listing=====
	<pre>// This code example for the Replicable pattern spawns four threads which copy		<pre>// This code example for the Replicable pattern spawns four threads which copy
	// the data and proceed to reverse it and place it back into a global results		// the data and proceed to reverse it and place it back into a global results
Line 81:		Line 84:
	printf("\b ");		printf("\b ");
	}</pre>		}</pre>
			=====Results=====
	Execution of this compiled program in the Microsoft Windows 7 operating system yielded the following output. Notice how the threads actually executed out of order, and that the final output is still correct as the ordered list of numbers.		Execution of this compiled program in the Microsoft Windows 7 operating system yielded the following output. Notice how the threads actually executed out of order, and that the final output is still correct as the ordered list of numbers.