Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Spring 2012/12b ad

2012-04-25T04:30:41Z

Ajdavis7:

On-chip Interconnects

==Introduction==
As the number of processors in multiple-processor systems increases, increasing consideration needs to be given to how those processors communicate. With current technology, for a small number of processors [http://en.wikipedia.org/wiki/Shared_memory shared-memory] arrangements are quite effective. However, as the number of processors increases contention for available resources (memory, bus time, etc.) increases, negatively impacting performance of the system. However, keeping these processors all on the same physical piece of hardware is convenient and helps performance due to physical proximity. As such, it is desirable to design hardware where [http://en.wikipedia.org/wiki/Multiprocessing many cores] are part of the same die while allowing for the performance gains possible with [http://en.wikipedia.org/wiki/Computer_network interconnections]. Recently there has been more research into these [http://en.wikipedia.org/wiki/Network_On_Chip on-chip interconnects], and this article will explore the state of those efforts.

==Topologies==
The intricacies of semiconductor design and layout afford many different kinds of possible layouts when creating [http://en.wikipedia.org/wiki/Network_topology networking topologies] on [http://en.wikipedia.org/wiki/System-on-a-Chip SoCs]. Specifically, designs need to be amenable to creation on a two-dimension [http://en.wikipedia.org/wiki/Die_(integrated_circuit) substrate], and as such practically limits the use of some more advanced topologies like hypercubes<ref name="GrotKeckler">Grot and Keckler, [http://www.cs.utexas.edu/~bgrot/docs/CMP-MSI_08.pdf Scalable On-Chip Interconnect Topologies]</ref> (circularly-connected mesh).

===Rings===
[http://en.wikipedia.org/wiki/Ring_network Ring topologies] can be effective when the “number of cores is still relatively small but is larger than what can be supported using a bus” [Solihin 409]. Such cases are considered to use “medium-scale” interconnection networks.

===Meshes===
[http://en.wikipedia.org/wiki/Mesh_networking 2D mesh networks] are used when the scale of the network topology breaks into “larger-than-medium” scale. This is especially true when the dimensions are divisible by a factor two, as the benefit in the number of hops versus a traditional ring network can be tremendous.

For example, in a worst-case scenario a sixteen-core multiprocessor would require eight hops to get to the farthest node. In a 2D mesh, however, creating a 4x4 grid guarantees that the maximum number of hops is six. Assuming random data distributed evenly among the cores, the expectation value (1/16 chance for each node) of the number of hops in a ring would be 3.6 (1/16*[0+1+2+3+... hops]), whereas the expectation value for the 2D mesh in minimal path would be 2.8. This benefit, though, comes at the necessary cost of increased power for the extra processing required. A potential solution to this "[http://en.wikipedia.org/wiki/CPU_power_dissipation power problem]" is to group cores together in what is called a concentrated mesh, but even that requires increased [http://en.wikipedia.org/wiki/Crossbar_switch crossbar] complexity<ref name="GrotKeckler"/>.

===Flattened Butterfly===
The flattened butterfly offers the benefits of a tree (less constraints on root-level bandwidth [Solihin 367]) as well as the ability to actually be mapped to a substrate, but because of node concentration<ref name="GrotKeckler"/> the number of channels required for high scalability is cost- and validation-prohibitive.

===Crossbar Switch===
A crossbar switch topology uses a bus arrangement with the bus lines physically perpendicular to each other and whose intersections are connected or disconnected with a switch. In the case of [http://en.wikipedia.org/wiki/Multi-core_(computing) CMPs], this switch is a transistor or, depending on the desired characteristics of the system, a programmable fuse. Due to their ability to be [http://en.wikipedia.org/wiki/Multistage_interconnection_networks multi-staged]<ref name="wikicrossbarsemi">"[http://en.wikipedia.org/wiki/Crossbar_switch#Semiconductor Crossbar switch]." Wikipedia. Last accessed April 24, 2012.</ref>, these topologies lend themselves to being used for memory in large-scale systems. The IBM Cyclops64 architecture is an example of the implementation of this architecture<ref name="cyclops64">Zhang, Ying Ping. "[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1639301 A study of the on-chip interconnection network for the IBM Cyclops64 multi-core architecture]. April 2006. IEEE Xplore.</ref>.

==Design Considerations==
===Energy Consumption===
Multi-processor SoCs require additional energy in order to operate the on-chip interconnection hardware like routers. Too, the links between components can introduce increased losses in regards to required voltages and physical arrangement. Indeed, "on-chip network power has been estimated to consume up to 28% of total chip power" due to "channels, router fifos and router crossbar fabrics"<ref name="GrotKeckler" />. Simple topologies use less power due to simpler routers, but the increased number of hops can lead to overall increased power consumption.

===Scalability===
Scalability ties back to both energy and cost, but also to engineering constraints as well. Specifically, the architecture needs to be sensitive to the power and heat requirements of the design, as well as the physical die size. Further, the design requires the ability to be fabricated predictably and within reasonable costs. To mitigate some of these factors, concentration of network interfaces can be employed, where a network interface is shared by multiple terminals. Efforts to scale more complicated topologies like the butterfly (into a "flattened" butterfly) have yielded promising results, but at the expense of too much energy expenditure<ref name="GrotKeckler" />.

==Modern Implementations==
===Tilera Tile Processor===
Tilera is a fabless semiconductor company that has developed a "tile processor" whereby the fabrication of the multi-processor device is greatly simplified by the placement of processor "tiles" on the die. The technology behind this innovation is iMesh, which is the name of the on-chip interconnection technology used in the Tile Processor's architecture<ref name="Tilera">"On-Chip Interconnection Architecture of the Tile Processor," Wentzlaff, et al. 2007. IEEE Xplore.</ref>. The Tile Processor is innovative due to its highly scalable implementation of an on-chip network that utilizes 2D meshes. These are physically organized (as opposed to logically organized) due to design considerations when scaling and laying out new designs.

Each tile of the Tile Processor is its own self-contained processor and can effectively function by itself; multiple processors can be combined to form an SMP system. The Tile Processor can be further enhanced by using its custom C language-based programming libraries (both POSIX threads and iLib), which fully leverage the processing capabilities of the CMP.

===Intel MIC and IOSF===
[[File:Intelpic.png|frame|Intel's concept for SoC integration]]

One part of Intel's efforts in the multiprocessor research realm revolves its Many Integrated Cores project<ref name="intelmic">Blyler, John. "[http://chipdesignmag.com/sld/blog/2011/09/22/proprietary-on-chip-connections-yield-to-noc-designs/ Proprietary On-Chip Connections Yield To NoC Designs]" System-Level Design Community Blog. September 22, 2011.</ref> These cores would communicate using a Message Parsing Interface. Further, to connect these cores, there is the Intel On-Chip System Fabric, which is a proprietary chassis for its popular Atom computing platform<ref name="inteliosf">Blyler, John. "[http://www.chipestimate.com/blogs/IPInsider/?p=295 Intel Challenges ARM with IP and Interconnect Strategy]" Semiconductor IP Blog. August 26, 2011.</ref>. The architecture of the IOSF lends itself to communication with traditional PCI buses, making it a viable technology for use in backwards-compatible general purpose computers. Additionally, through numerous licensing agreements, Intel has acquired the use of a wide variety of devices from graphics to modems and Wi-Fi Ethernet adapters. Coupled with the IOSF, conceivably entire computing platforms (SoCs) could be made at low cost and small footprint.

===ARM CoreLink Interconnect===
The ARM CoreLink Interconnect is a highly flexible and configurable interconnection network specification that implements the [http://en.wikipedia.org/wiki/Advanced_Microcontroller_Bus_Architecture AMBA] (Advanced Microcontroller Bus Architecture) protocol. The AMBA protocol is "an open standard, on-chip interconnect specification for the connection and management of functional blocks in a System-on-Chip (SoC). It enables development of multi-processor designs with large numbers of controllers and peripherals."<ref name="ambadoc">[http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.set.amba/index.html AMBA] on the ARM Info Center.</ref>

===Other===
The above are examples of modern actual realizations of SoC topologies. Some more examples<ref name="wikicompetitors">[http://en.wikipedia.org/wiki/Advanced_Microcontroller_Bus_Architecture#Competitors AMBA Competitors] on Wikipedia.</ref> of realizations of SoCs include the Opencores [http://en.wikipedia.org/wiki/Wishbone_(computer_bus) Wishbone], [http://www.altera.com/literature/manual/mnl_avalon_spec.pdf Altera Avalon], and [http://en.wikipedia.org/wiki/CoreConnect IBM CoreConnect].

==Summary==
Considering that the AMBA protocol was first published in 1996, it is obvious that the movement toward SoCs is technologically mature. The several competing topologies and technologies, coupled with on-going research and the search for the ultimate in performance and power reduction have led to an exciting amount of innovation in recent years. Meshes and crossbars seem to the scalability option of choice, especially as process sizes shrink which allow for more flexible scaling options.

==Quiz==
'''Question 1)''' What is another name for the physical substrate of an integrated circuit?
# Fabric
# Canvas
# Die
# Matrix

'''Question 2)''' Which of the below companies are ''not'' actively involved in SoC design?
# Altera
# ARM
# IBM
# Cray

'''Question 3)''' Why are mesh topologies generally preferred over ring topologies?
# Lower latency
# Cheaper to implement
# Lower power consumption
# Better reliability

'''Question 4)''' What is meant by "SoCs?"
# Scalability of Connections
# System on a Chip
# Speeds over Capacities
# Shared (memory) on a Cable

'''Question 5)''' What is meant by "NoCs?"
# No Capacitance Effects
# Network on a Chip
# Network Obligation of Channel
# Notification of Cache Sharing

'''Question 6)''' What is the name of a discrete processing unit used in the construction of certain topologies?
# Channel
# Router
# Sentry
# Tile

'''Question 7)''' Which choice best characterizes the number of cores in a "medium scale" system?
# Around 2-8 cores
# Around 8-16 cores
# Around 32-64 cores
# Around 64-128 cores

'''Question 8)''' What is a major prohibitive factor of using butterfly topologies in commercial SoC products for a large number of cores?
# High number of channels
# High link bandwidth
# High latency on cache misses
# Low return on investment

'''Question 9)''' Which of these is the most major factor in limiting physical size in a SoC design?
# Electrical characteristics (capacitance, noise, clock skew, current, voltage)
# Process limitations (required equipment, equipment calibration, material purity)
# Power density (process size, material thermal characteristics, number of substrate layers)
# All of the above have similar magnitude in limitation considerations

'''Question 10)''' Which is the best reason CMPs require special programming libraries for best performance?
# Proprietary code paths for vendor lock-out
# Allow NoC to more effectively coordinate all cores
# Implementation is incompatible with operating system
# Attempt to create new de facto programming standards

-

'''Answers:''' In numerical question order: 3-4-1-2-2-4-2-1-4-2

==Further Reading==
''[http://www.cesr.ncsu.edu/solihin/Main.html Fundamentals of Parallel Computer Architecture]'' by Yan Solihin.

==References==
<references></references>

2012-04-25T03:10:14Z

Ajdavis7: /* ARM CoreLink Interconnect */

On-chip Interconnects

==Introduction==
As the number of processors in multiple-processor systems increases, increasing consideration needs to be given to how those processors communicate. With current technology, for a small number of processors [http://en.wikipedia.org/wiki/Shared_memory shared-memory] arrangements are quite effective. However, as the number of processors increases contention for available resources (memory, bus time, etc) increases, negatively impacting performance of the system. However, keeping these processors all on the same physical piece of hardware is convenient and helps performance due to physical proximity. As such, it is desirable to design hardware where [http://en.wikipedia.org/wiki/Multiprocessing many cores] are part of the same die while allowing for the performance gains possible with [http://en.wikipedia.org/wiki/Computer_network interconnections]. Recently there has been more research into these [http://en.wikipedia.org/wiki/Network_On_Chip on-chip interconnects], and this article will explore the state of those efforts.

==Topologies==
The intracacies of semiconductor design and layout afford many different kinds of possible layouts when creating [http://en.wikipedia.org/wiki/Network_topology networking topologies] on [http://en.wikipedia.org/wiki/System-on-a-Chip SoCs]. Specifically, designs need to be amenable to creation on a two-dimension [http://en.wikipedia.org/wiki/Die_(integrated_circuit) substrate], and as such practically limits the use of some more advanced topologies like hypercubes <ref name="GrotKeckler">Grot and Keckler, [http://www.cs.utexas.edu/~bgrot/docs/CMP-MSI_08.pdf Scalable On-Chip Interconnect Topologies]</ref>.

===Rings===
[http://en.wikipedia.org/wiki/Ring_network Ring topologies] can be effective when the “number of cores is still relatively small but is larger than what can be supported using a bus” [Solihin 409]. Such cases are considered to use “medium-scale” interconnection networks.

===Meshes===
[http://en.wikipedia.org/wiki/Mesh_networking 2D mesh networks] are used when the scale of the network topology breaks into “larger-than-medium” scale. This is especially true when the dimensions are divisible by a factor two, as the benefit in the number of hops versus a traditional ring network can be tremendous.

For example, in a worst-case scenario a sixteen-core multiprocessor would require eight hops to get to the farthest node. In a 2D mesh, however, creating a 4x4 grid guarantees that the maximum number of hops is six. Assuming random data distributed evenly among the cores, the expectation value (1/16 chance for each node) of the number of hops in a ring would be 3.6 (1/16*[0+1+2+3+... hops]), whereas the expectation value for the 2D mesh in minimal path would be 2.8. This benefit, though, comes at the necessary cost of increased power for the extra processing required. A potential solution to this "[http://en.wikipedia.org/wiki/CPU_power_dissipation power problem]" is to group cores together in what is called a concentrated mesh, but even that requires increased [http://en.wikipedia.org/wiki/Crossbar_switch crossbar] complexity<ref name="GrotKeckler"/>.

===Flattened Butterfly===
The flattened butterfly offers the benefits of a tree (less contraints on root-level bandwidth [Solihin 367]) as well as the ability to actually be mapped to a substrate, but because of node concentration<ref name="GrotKeckler"/> the number of channels required for high scalability is cost- and validation-prohibitive.

===Crossbar Switch===
A crossbar switch topology uses a bus arrangement with the bus lines physically perpendicular to each other and whose intersections are connected or disconnected with a switch. In the case of [http://en.wikipedia.org/wiki/Multi-core_(computing) CMPs], this switch is a transistor or, depending on the desired characteristics of the system, a programmable fuse. Due to their ability to be [http://en.wikipedia.org/wiki/Multistage_interconnection_networks multi-staged]<ref name="wikicrossbarsemi">"[http://en.wikipedia.org/wiki/Crossbar_switch#Semiconductor Crossbar switch]." Wikipedia. Last accessed April 24, 2012.</ref>, these topologies lend themselves to being used for memory in large-scale systems. The IBM Cyclops64 architecture is an example of the implementation of this architecture<ref name="cyclops64">Zhang, Ying Ping. "[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1639301 A study of the on-chip interconnection network for the IBM Cyclops64 multi-core architecture]. April 2006. IEEE Xplore.</ref>.

==Design Considerations==
===Energy Consumption===
Multi-processor SoCs require additional energy in order to operate the on-chip interconnection hardware like routers. Too, the links between components can introduce increased losses in regards to required voltages and physical arrangement. Indeed, "on-chip network power has been estimated to consume up to 28% of total chip power" due to "channels, router fifos and router crossbar fabrics"<ref name="GrotKeckler" />. Simple topologies use less power due to simpler routers, but the increased number of hops can lead to overal increased power consumption.

===Scalability===
Scalability ties back to both energy and cost, but also to engineering constraints as well. Specifcally, the architecture needs to be sensitive to the power and heat requirements of the design, as well as the physical die size. Further, the design requires the ability to be fabricated predictably and within reasonable costs. To mitigate some of these factors, concentration of network interfaces can be employed, where a network interface is shared by multipe terminals. Efforts to scale more complicated topologies like the butterfly (into a "flattened" butterfly) have yielded promising results, but at the expense of too much energy expenditure<ref name="GrotKeckler" />.

==Modern Implementations==
===Tilera Tile Processor===
Tilera is a fabless semiconductor company that has developed a "tile processor" whereby the fabrication of the multi-processor device is greatly simplified by the placement of processor "tiles" on the die. The technology behind this innovation is iMesh, which is the name of the on-chip interconnection technology used in the Tile Processor's architecture<ref name="Tilera">"On-Chip Interconnection Architecture of the Tile Processor," Wentzlaff, et al. 2007. IEEE Xplore.</ref>. The Tile Processor is innovative due to its highly scalable implementation of an on-chip network that utilizes 2D meshes. These are physically organized (as opposed to logically organized) due to design considerations when scaling and laying out new designs.

Each tile of the Tile Processor is its own self-contained processor and can effectively function by itself; multiple processors can be combined to form an SMP system. The Tile Processor can be further enhanced by using its custom C language-based programming libraries (both POSIX threads and iLib), which fully leverage the processing capabilities of the CMP.

===Intel MIC and IOSF===
[[File:Intelpic.png|frame|Intel's concept for SoC integration]]

One part of Intel's efforts in the multiprocessor research realm revolves its Many Integrated Cores project<ref name="intelmic">Blyler, John. "[http://chipdesignmag.com/sld/blog/2011/09/22/proprietary-on-chip-connections-yield-to-noc-designs/ Proprietary On-Chip Connections Yield To NoC Designs]" System-Level Design Community Blog. September 22, 2011.</ref> These cores would communicate using a Message Parsing Interface. Further, to connect these cores, there is the Intel On-Chip System Fabric, which is a proprietary chassis for its popular Atom computing platform<ref name="inteliosf">Blyler, John. "[http://www.chipestimate.com/blogs/IPInsider/?p=295 Intel Challenges ARM with IP and Interconnect Strategy]" Semiconductor IP Blog. August 26, 2011.</ref>. The architecture of the IOSF lends itself to communication with traditional PCI buses, making it a viable technology for use in backwards-compatible general purpose computers. Additionally, through numerous licensing agreements, Intel has acquired the use of a wide variety of devices from graphics to modems and Wi-Fi Ethernet adapters. Coupled with the IOSF, conceivably entire computing platforms (SoCs) could be made at low cost and small footprint.

===ARM CoreLink Interconnect===
The ARM CoreLink Interconnect is a highly flexible and configurable interconnection network specification that implements the [http://en.wikipedia.org/wiki/Advanced_Microcontroller_Bus_Architecture AMBA] (Advanced Microcontroller Bus Architecture) protocol. The AMBA protocol is "an open standard, on-chip interconnect specification for the connection and management of functional blocks in a System-on-Chip (SoC). It enables development of multi-processor designs with large numbers of controllers and peripherals."<ref name="ambadoc">[http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.set.amba/index.html AMBA] on the ARM Info Center.</ref>

===Other===
The above are examples of modern actual realizations of SoC topologies. Some more examples<ref name="wikicompetitors">[http://en.wikipedia.org/wiki/Advanced_Microcontroller_Bus_Architecture#Competitors AMBA Competitors] on Wikipedia.</ref> of realizations of SoCs include the Opencores [http://en.wikipedia.org/wiki/Wishbone_(computer_bus) Wishbone], [http://www.altera.com/literature/manual/mnl_avalon_spec.pdf Altera Avalon], and [http://en.wikipedia.org/wiki/CoreConnect IBM CoreConnect].

==Summary==

==See Also==

==References==
<references></references>

CSC/ECE 506 Spring 2012/12b ad

2012-04-25T02:13:01Z

Ajdavis7: /* Modern Implementations */

CSC/ECE 506 Spring 2012/12b ad

2012-04-25T01:46:32Z

Ajdavis7: /* Crossbar Switch */

CSC/ECE 506 Spring 2012/12b ad

2012-04-25T01:43:25Z

Ajdavis7: /* Topologies */

2012-04-17T05:01:19Z

Ajdavis7: /* Modern Implementations */

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T04:55:04Z

Ajdavis7:

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T04:47:04Z

Ajdavis7: /* Topologies */

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T04:46:30Z

Ajdavis7: /* Topologies */

2012-04-17T02:49:52Z

Ajdavis7: /* Energy Consumption */

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T02:46:05Z

Ajdavis7: /* Topologies */

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T02:44:34Z

Ajdavis7:

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T02:10:41Z

Ajdavis7: /* Introduction */

CSC/ECE 506 Spring 2012/12b ad

2012-04-17T02:03:10Z

Ajdavis7:

On-chip Interconnects

==Introduction==

The full content of this article will be posted later today; please check again later.

==Summary==

==See Also==

==References==
<references></references>

CSC/ECE 506 Spring 2012/12b ad

2012-04-16T00:38:42Z

Ajdavis7: Created page with "On-chip Interconnects ==Introduction== ==Summary== ==See Also== ==References== <references></references>"

On-chip Interconnects

==Introduction==

==Summary==

==See Also==

==References==
<references></references>

CSC/ECE 506 Spring 2012/3a df

2012-02-20T22:50:57Z

Ajdavis7: /* Complex Patterns */

Patterns of Parallel Programming

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

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 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 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===
====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.
[[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 [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2012/3a_df#Frameworks below].
=====Code Listing=====
<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
// array. Tested in Microsoft Visual Studio 2010 with /openmp and /TC compile options

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <omp.h>

#define CHUNK_SIZE 4

void OutputData(char *pArray, int size);

int main()
{
int i, j;
char temp;
char *localData;
const char globalData[] =
{ 3, 2, 1, 0,
7, 6, 5, 4,
11, 10, 9, 8,
15, 14, 13, 12 };
char globalResult[CHUNK_SIZE*CHUNK_SIZE];

// Setup and report
omp_set_nested(1);
omp_set_num_threads(4);
printf("Data set: "); OutputData(globalData, CHUNK_SIZE*CHUNK_SIZE); printf("\n");

printf("Running Replicable parallel section...\n");
#pragma omp parallel for private(i,j,localData) schedule(static)
for(i = 0; i < CHUNK_SIZE; i++)
{
// Replicate data for local use
localData = (char *)malloc(sizeof(char)*CHUNK_SIZE);
memcpy(localData, (char *)(globalData+i*CHUNK_SIZE), sizeof(char)*CHUNK_SIZE);

// Reverse the chunk
for(j = 0; j < CHUNK_SIZE/2; j++)
{
temp = localData[CHUNK_SIZE - j - 1];
localData[CHUNK_SIZE - j - 1] = localData[j];
localData[j] = temp;
}

// Merge the results back into the global result and clean up
memcpy((char *)(globalResult+i*CHUNK_SIZE), localData, sizeof(char)*CHUNK_SIZE);
free(localData);
printf("-> Merged result in thread %d/%d\n", omp_get_thread_num()+1, omp_get_num_threads());
}

// Output the results of the parallel section
printf("Results: "); OutputData(globalResult, CHUNK_SIZE*CHUNK_SIZE); printf("\n");

system("pause");
return 0;
}

// Convenience method for reporting the results
void OutputData(const char *pArray, int size)
{
int i;
for(i = 0; i < size; i++) printf("%d,", pArray[i]);
printf("\b ");
}</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.

<pre>
Data set: 3,2,1,0,7,6,5,4,11,10,9,8,15,14,13,12
Running Replicable parallel section...
-> Merged result in thread 1/4
-> Merged result in thread 2/4
-> Merged result in thread 4/4
-> Merged result in thread 3/4
Results: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Press any key to continue . . .
</pre>

===Repository===
[[Image:506-2012-Spring-3a-df-repo.png|right|thumb|200px|Repository pattern]]
The Repository pattern is related to the Replicable pattern in that they both act on a set of data and rely on the result<ref name="kim_ppp_ppt"/>. However, in the Repository pattern all data remains centralized while the computations themselves are performed remotely. In essence, the Repository pattern could be thought of as a continuous Replicable pattern where the global data set is much larger than can be simultaneously replicated. An excellent (simplified) example of this pattern would be distributed computing applications like [http://en.wikipedia.org/wiki/Folding@home Folding@Home] or [http://en.wikipedia.org/wiki/Seti@home SETI@Home], where a central server coordinates the calculations between all available processing units.

===Divide and Conquer===
[[Image:506-2012-Spring-3a-df-dnc.png|right|thumb|none|200px|Divide & Conquer pattern]]The Divide and Conquer pattern is very similar to the Replicable pattern<ref name="kim_ppp_ppt"/>. It involves taking a problem or task and splitting it into subproblems whereupon the required calculations are performed in parallel. A merging action still needs to occur to arrive at the solution, but the advantage of Divide and Conquer over Replicable is that the entire data set does not have to be communicated between the processing units -- only the required data for the computation does. Also, due to the degree of separation of computation and data, there is a non-negligible amount of overhead associated with determining the proper points at which the problems should be split and the overall allocation of resources.

==Common Patterns==
Common patterns solve parallel design tasks that are readily understood and frequently encountered, but whose implementation could benefit from a more formalized and structured approach. Generally, common parallel patterns can be implemented manually or with a framework with a moderate degree of difficulty depending on the programmer's skill level.
===Pipeline===
[[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 [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.

===Recursive Data===
[[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 [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===
[[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 such as cubic or quartic) data set must be analyzed for changes in motion.

===Irregular Mesh===
[[Image:506-2012-Spring-3a-df-irregular.png|right|thumb|200px|Irregular Mesh pattern]]
The Irregular Mesh pattern<ref name="kim_ppp_ppt"/> is a hybrid of the Geometric and Recursive Data patterns (and sub-patterns implied); Geometric because of the boundaries involved with splitting up the shape, and Recursive Data due to the varying hierarchies that might be involved. An example of this kind of operation would be a skeletal/bone structure system for three-dimensional computer models. A difficult task for even serial computation, the Irregular Mesh pattern is difficult to implement in an optimal manner without careful consideration to the algorithm and having insight as to what kind of structure is being analyzed.

===Inseparable===
The Inseparable pattern<ref name="kim_ppp_ppt"/> is more of an anti-pattern in that it is a problem which needs a parallel solution, but whose solution does not seem to fit any of the aforementioned patterns. Frequently, but not always, the Inseparable pattern will utilize the parallel primitives in complex and non-deterministic ways, and may actually be representative of programming errors or a lack of organization. There does not always have to be a negative connotation, however, as a problem may be so complex as to not fit into any of the above patterns.

==Complex Patterns==
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-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
* '''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
* '''Event Driven'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/event_driven.doc Event-Driven Pattern] at UIUC Computer Science Department</ref> - Allow implicated processes to alert each other to re-commence calculation

==Formalization==
Formalization describes the efforts of the programming community to devise tools which can aid programmers in designing software which follows standardized (whether international/documented or by practice) procedures, methods, and templates for performing parallel operations. These tools may be purely documentation pieces, frameworks, examples, academic papers, etc.
===Design Languages===
Design languages allow programmers to define problems in terms of a common vocabulary so that solutions to problems can be readily identified and efficiently shared.<ref name="ortega"/> A brief survey of some current pattern language efforts follows.
====ParLab====
The Pattern Language for Parallel Programming at Berkeley’s ParLab<ref name=”parlab”>[ http://parlab.eecs.berkeley.edu/wiki/patterns/patterns A Pattern Language for Parallel Programming] at Berkely ParLab</ref> describes five major categories of patterns. These patterns are described through a somewhat disparate documentation set and articles:

* '''Structural Patterns''' - Concerned with the arrangement of different processes that can run in parallel
* '''Computation Patterns''' - Concerned with the way parallel processes handle data
* '''Parallel Algorithm Strategy Patterns''' - Descriptions on how different end results can be achieved by using parallel algorithms
* '''Implementation Strategy Patterns''' - Descriptions on the mechanisms that can be used to implement parallel algorithms
* '''Concurrent Execution Patterns''' - Concerned with how parallel processes should be managed

====University of Florida PLPP====
The development efforts of a pattern language for parallel patterns undertaken at the University of Florida resulted in the development of a published text<ref name=”ufl”>Mattson, Timothy G., Beverly A. Sanders, and Berna Massingill. Patterns for Parallel Programming. Boston: Addison-Wesley, 2005. [http://www.cise.ufl.edu/research/ParallelPatterns/index.htm Homepage]</ref>. This book catalogs the major “design spaces,” or “solution to a problem in context,” which are<ref name=”ufl_toc”>Mattson, Timothy G., Beverly A. Sanders, and Berna Massingill. Patterns for Parallel Programming. Boston: Addison-Wesley, 2005. [http://www.cise.ufl.edu/research/ParallelPatterns/contents.htm Table of Contents]</ref>:

* '''Finding Concurrency''' - How a problem can be parallelized in the first place
* '''Algorithm Structure''' - How the processes can be arranged (see Intuitive and Common patterns earlier in this chapter)
* '''Supporting Structures''' - Primitives and data structures useful in managing parallel tasks
* '''Implementation Mechanisms''' - Architecture and resource-specific details on creating parallel solutions

===Frameworks===
Frameworks are any piece of code for a particular programming language which can help a programmer in creating a program which takes advantage of parallel algorithms. A discussion of the frameworks is outside the scope of this chapter, but the interested reader is suggested to investigate the following resources:
* [http://msdn.microsoft.com/en-us/library/dd492418.aspx Parallel Patterns Library] - Programming library for parallel processes in Microsoft's .NET Framework
* [http://openmp.org/wp/ OpenMP] - Application programminf interface for parallel processes in the C/C++ and Fortran programming languages
* [http://www.cc.gatech.edu/~bader/papers/SWARM.html SWARM] - Application programming interface based on [http://en.wikipedia.org/wiki/POSIX_Threads POSIX Threads] that implements several parallel primitives

==Summary==
In conclusion, there are currently many initiatives to standardize the programmer’s experience when designing and maintaining parallel software systems. Through the survey above, it can be noted that there are four key factors in determining which parallel pattern to use:

* '''Physical resources available''' - The amount of processing units, memory, communication bandwidth, etc.
* '''Algorithm data parallelism''' - How well the algorithm’s data can be split up to be used in independent calculations
* '''Algorithm computation parallelism''' - How much each processor must rely on another for its intermediate calculations
* '''Framework/programming language''' - What limiting factors might exist for implementing the desired pattern in the programming language or framework of choice.

Indeed, there is a pattern for nearly every occasion, and the patterns presented above are just the "key" patterns. However, without careful consideration of the above points, the programmer will find difficulty in optimally implementing his or her software.

==See Also==
* [http://www.cs.uiuc.edu/homes/snir/PPP/ Resources on Parallel Patterns] at the UIUC Computer Science Department

==References==
<references></references>

CSC/ECE 506 Spring 2012/3a df

2012-02-20T22:49:52Z

Ajdavis7: /* Geometric */

Patterns of Parallel Programming

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

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 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 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===
====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.
[[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 [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2012/3a_df#Frameworks below].
=====Code Listing=====
<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
// array. Tested in Microsoft Visual Studio 2010 with /openmp and /TC compile options

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <omp.h>

#define CHUNK_SIZE 4

void OutputData(char *pArray, int size);

int main()
{
int i, j;
char temp;
char *localData;
const char globalData[] =
{ 3, 2, 1, 0,
7, 6, 5, 4,
11, 10, 9, 8,
15, 14, 13, 12 };
char globalResult[CHUNK_SIZE*CHUNK_SIZE];

// Setup and report
omp_set_nested(1);
omp_set_num_threads(4);
printf("Data set: "); OutputData(globalData, CHUNK_SIZE*CHUNK_SIZE); printf("\n");

printf("Running Replicable parallel section...\n");
#pragma omp parallel for private(i,j,localData) schedule(static)
for(i = 0; i < CHUNK_SIZE; i++)
{
// Replicate data for local use
localData = (char *)malloc(sizeof(char)*CHUNK_SIZE);
memcpy(localData, (char *)(globalData+i*CHUNK_SIZE), sizeof(char)*CHUNK_SIZE);

// Reverse the chunk
for(j = 0; j < CHUNK_SIZE/2; j++)
{
temp = localData[CHUNK_SIZE - j - 1];
localData[CHUNK_SIZE - j - 1] = localData[j];
localData[j] = temp;
}

// Merge the results back into the global result and clean up
memcpy((char *)(globalResult+i*CHUNK_SIZE), localData, sizeof(char)*CHUNK_SIZE);
free(localData);
printf("-> Merged result in thread %d/%d\n", omp_get_thread_num()+1, omp_get_num_threads());
}

// Output the results of the parallel section
printf("Results: "); OutputData(globalResult, CHUNK_SIZE*CHUNK_SIZE); printf("\n");

system("pause");
return 0;
}

// Convenience method for reporting the results
void OutputData(const char *pArray, int size)
{
int i;
for(i = 0; i < size; i++) printf("%d,", pArray[i]);
printf("\b ");
}</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.

<pre>
Data set: 3,2,1,0,7,6,5,4,11,10,9,8,15,14,13,12
Running Replicable parallel section...
-> Merged result in thread 1/4
-> Merged result in thread 2/4
-> Merged result in thread 4/4
-> Merged result in thread 3/4
Results: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Press any key to continue . . .
</pre>

===Repository===
[[Image:506-2012-Spring-3a-df-repo.png|right|thumb|200px|Repository pattern]]
The Repository pattern is related to the Replicable pattern in that they both act on a set of data and rely on the result<ref name="kim_ppp_ppt"/>. However, in the Repository pattern all data remains centralized while the computations themselves are performed remotely. In essence, the Repository pattern could be thought of as a continuous Replicable pattern where the global data set is much larger than can be simultaneously replicated. An excellent (simplified) example of this pattern would be distributed computing applications like [http://en.wikipedia.org/wiki/Folding@home Folding@Home] or [http://en.wikipedia.org/wiki/Seti@home SETI@Home], where a central server coordinates the calculations between all available processing units.

===Divide and Conquer===
[[Image:506-2012-Spring-3a-df-dnc.png|right|thumb|none|200px|Divide & Conquer pattern]]The Divide and Conquer pattern is very similar to the Replicable pattern<ref name="kim_ppp_ppt"/>. It involves taking a problem or task and splitting it into subproblems whereupon the required calculations are performed in parallel. A merging action still needs to occur to arrive at the solution, but the advantage of Divide and Conquer over Replicable is that the entire data set does not have to be communicated between the processing units -- only the required data for the computation does. Also, due to the degree of separation of computation and data, there is a non-negligible amount of overhead associated with determining the proper points at which the problems should be split and the overall allocation of resources.

==Common Patterns==
Common patterns solve parallel design tasks that are readily understood and frequently encountered, but whose implementation could benefit from a more formalized and structured approach. Generally, common parallel patterns can be implemented manually or with a framework with a moderate degree of difficulty depending on the programmer's skill level.
===Pipeline===
[[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 [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.

===Recursive Data===
[[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 [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===
[[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 such as cubic or quartic) data set must be analyzed for changes in motion.

===Irregular Mesh===
[[Image:506-2012-Spring-3a-df-irregular.png|right|thumb|200px|Irregular Mesh pattern]]
The Irregular Mesh pattern<ref name="kim_ppp_ppt"/> is a hybrid of the Geometric and Recursive Data patterns (and sub-patterns implied); Geometric because of the boundaries involved with splitting up the shape, and Recursive Data due to the varying hierarchies that might be involved. An example of this kind of operation would be a skeletal/bone structure system for three-dimensional computer models. A difficult task for even serial computation, the Irregular Mesh pattern is difficult to implement in an optimal manner without careful consideration to the algorithm and having insight as to what kind of structure is being analyzed.

===Inseparable===
The Inseparable pattern<ref name="kim_ppp_ppt"/> is more of an anti-pattern in that it is a problem which needs a parallel solution, but whose solution does not seem to fit any of the aforementioned patterns. Frequently, but not always, the Inseparable pattern will utilize the parallel primitives in complex and non-deterministic ways, and may actually be representative of programming errors or a lack of organization. There does not always have to be a negative connotation, however, as a problem may be so complex as to not fit into any of the above patterns.

==Complex Patterns==
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-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
* '''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
* '''Event Driven'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/event_driven.doc Event-Driven Pattern] at UIUC Computer Science Department</ref> - Allow implicated processes to alert each other to re-commence calculation

==Formalization==
Formalization describes the efforts of the programming community to devise tools which can aid programmers in designing software which follows standardized (whether international/documented or by practice) procedures, methods, and templates for performing parallel operations. These tools may be purely documentation pieces, frameworks, examples, academic papers, etc.
===Design Languages===
Design languages allow programmers to define problems in terms of a common vocabulary so that solutions to problems can be readily identified and efficiently shared.<ref name="ortega"/> A brief survey of some current pattern language efforts follows.
====ParLab====
The Pattern Language for Parallel Programming at Berkeley’s ParLab<ref name=”parlab”>[ http://parlab.eecs.berkeley.edu/wiki/patterns/patterns A Pattern Language for Parallel Programming] at Berkely ParLab</ref> describes five major categories of patterns. These patterns are described through a somewhat disparate documentation set and articles:

* '''Structural Patterns''' - Concerned with the arrangement of different processes that can run in parallel
* '''Computation Patterns''' - Concerned with the way parallel processes handle data
* '''Parallel Algorithm Strategy Patterns''' - Descriptions on how different end results can be achieved by using parallel algorithms
* '''Implementation Strategy Patterns''' - Descriptions on the mechanisms that can be used to implement parallel algorithms
* '''Concurrent Execution Patterns''' - Concerned with how parallel processes should be managed

====University of Florida PLPP====
The development efforts of a pattern language for parallel patterns undertaken at the University of Florida resulted in the development of a published text<ref name=”ufl”>Mattson, Timothy G., Beverly A. Sanders, and Berna Massingill. Patterns for Parallel Programming. Boston: Addison-Wesley, 2005. [http://www.cise.ufl.edu/research/ParallelPatterns/index.htm Homepage]</ref>. This book catalogs the major “design spaces,” or “solution to a problem in context,” which are<ref name=”ufl_toc”>Mattson, Timothy G., Beverly A. Sanders, and Berna Massingill. Patterns for Parallel Programming. Boston: Addison-Wesley, 2005. [http://www.cise.ufl.edu/research/ParallelPatterns/contents.htm Table of Contents]</ref>:

* '''Finding Concurrency''' - How a problem can be parallelized in the first place
* '''Algorithm Structure''' - How the processes can be arranged (see Intuitive and Common patterns earlier in this chapter)
* '''Supporting Structures''' - Primitives and data structures useful in managing parallel tasks
* '''Implementation Mechanisms''' - Architecture and resource-specific details on creating parallel solutions

===Frameworks===
Frameworks are any piece of code for a particular programming language which can help a programmer in creating a program which takes advantage of parallel algorithms. A discussion of the frameworks is outside the scope of this chapter, but the interested reader is suggested to investigate the following resources:
* [http://msdn.microsoft.com/en-us/library/dd492418.aspx Parallel Patterns Library] - Programming library for parallel processes in Microsoft's .NET Framework
* [http://openmp.org/wp/ OpenMP] - Application programminf interface for parallel processes in the C/C++ and Fortran programming languages
* [http://www.cc.gatech.edu/~bader/papers/SWARM.html SWARM] - Application programming interface based on [http://en.wikipedia.org/wiki/POSIX_Threads POSIX Threads] that implements several parallel primitives

==Summary==
In conclusion, there are currently many initiatives to standardize the programmer’s experience when designing and maintaining parallel software systems. Through the survey above, it can be noted that there are four key factors in determining which parallel pattern to use:

* '''Physical resources available''' - The amount of processing units, memory, communication bandwidth, etc.
* '''Algorithm data parallelism''' - How well the algorithm’s data can be split up to be used in independent calculations
* '''Algorithm computation parallelism''' - How much each processor must rely on another for its intermediate calculations
* '''Framework/programming language''' - What limiting factors might exist for implementing the desired pattern in the programming language or framework of choice.

Indeed, there is a pattern for nearly every occasion, and the patterns presented above are just the "key" patterns. However, without careful consideration of the above points, the programmer will find difficulty in optimally implementing his or her software.

==See Also==
* [http://www.cs.uiuc.edu/homes/snir/PPP/ Resources on Parallel Patterns] at the UIUC Computer Science Department

==References==
<references></references>

CSC/ECE 506 Spring 2012/3a df

2012-02-20T22:49:13Z

Ajdavis7: /* Recursive Data */

Patterns of Parallel Programming

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

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 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 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===
====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.
[[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 [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2012/3a_df#Frameworks below].
=====Code Listing=====
<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
// array. Tested in Microsoft Visual Studio 2010 with /openmp and /TC compile options

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <omp.h>

#define CHUNK_SIZE 4

void OutputData(char *pArray, int size);

int main()
{
int i, j;
char temp;
char *localData;
const char globalData[] =
{ 3, 2, 1, 0,
7, 6, 5, 4,
11, 10, 9, 8,
15, 14, 13, 12 };
char globalResult[CHUNK_SIZE*CHUNK_SIZE];

// Setup and report
omp_set_nested(1);
omp_set_num_threads(4);
printf("Data set: "); OutputData(globalData, CHUNK_SIZE*CHUNK_SIZE); printf("\n");

printf("Running Replicable parallel section...\n");
#pragma omp parallel for private(i,j,localData) schedule(static)
for(i = 0; i < CHUNK_SIZE; i++)
{
// Replicate data for local use
localData = (char *)malloc(sizeof(char)*CHUNK_SIZE);
memcpy(localData, (char *)(globalData+i*CHUNK_SIZE), sizeof(char)*CHUNK_SIZE);

// Reverse the chunk
for(j = 0; j < CHUNK_SIZE/2; j++)
{
temp = localData[CHUNK_SIZE - j - 1];
localData[CHUNK_SIZE - j - 1] = localData[j];
localData[j] = temp;
}

// Merge the results back into the global result and clean up
memcpy((char *)(globalResult+i*CHUNK_SIZE), localData, sizeof(char)*CHUNK_SIZE);
free(localData);
printf("-> Merged result in thread %d/%d\n", omp_get_thread_num()+1, omp_get_num_threads());
}

// Output the results of the parallel section
printf("Results: "); OutputData(globalResult, CHUNK_SIZE*CHUNK_SIZE); printf("\n");

system("pause");
return 0;
}

// Convenience method for reporting the results
void OutputData(const char *pArray, int size)
{
int i;
for(i = 0; i < size; i++) printf("%d,", pArray[i]);
printf("\b ");
}</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.

<pre>
Data set: 3,2,1,0,7,6,5,4,11,10,9,8,15,14,13,12
Running Replicable parallel section...
-> Merged result in thread 1/4
-> Merged result in thread 2/4
-> Merged result in thread 4/4
-> Merged result in thread 3/4
Results: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Press any key to continue . . .
</pre>

===Repository===
[[Image:506-2012-Spring-3a-df-repo.png|right|thumb|200px|Repository pattern]]
The Repository pattern is related to the Replicable pattern in that they both act on a set of data and rely on the result<ref name="kim_ppp_ppt"/>. However, in the Repository pattern all data remains centralized while the computations themselves are performed remotely. In essence, the Repository pattern could be thought of as a continuous Replicable pattern where the global data set is much larger than can be simultaneously replicated. An excellent (simplified) example of this pattern would be distributed computing applications like [http://en.wikipedia.org/wiki/Folding@home Folding@Home] or [http://en.wikipedia.org/wiki/Seti@home SETI@Home], where a central server coordinates the calculations between all available processing units.

===Divide and Conquer===
[[Image:506-2012-Spring-3a-df-dnc.png|right|thumb|none|200px|Divide & Conquer pattern]]The Divide and Conquer pattern is very similar to the Replicable pattern<ref name="kim_ppp_ppt"/>. It involves taking a problem or task and splitting it into subproblems whereupon the required calculations are performed in parallel. A merging action still needs to occur to arrive at the solution, but the advantage of Divide and Conquer over Replicable is that the entire data set does not have to be communicated between the processing units -- only the required data for the computation does. Also, due to the degree of separation of computation and data, there is a non-negligible amount of overhead associated with determining the proper points at which the problems should be split and the overall allocation of resources.

==Common Patterns==
Common patterns solve parallel design tasks that are readily understood and frequently encountered, but whose implementation could benefit from a more formalized and structured approach. Generally, common parallel patterns can be implemented manually or with a framework with a moderate degree of difficulty depending on the programmer's skill level.
===Pipeline===
[[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 [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.

===Recursive Data===
[[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 [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===
[[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.

===Irregular Mesh===
[[Image:506-2012-Spring-3a-df-irregular.png|right|thumb|200px|Irregular Mesh pattern]]
The Irregular Mesh pattern<ref name="kim_ppp_ppt"/> is a hybrid of the Geometric and Recursive Data patterns (and sub-patterns implied); Geometric because of the boundaries involved with splitting up the shape, and Recursive Data due to the varying hierarchies that might be involved. An example of this kind of operation would be a skeletal/bone structure system for three-dimensional computer models. A difficult task for even serial computation, the Irregular Mesh pattern is difficult to implement in an optimal manner without careful consideration to the algorithm and having insight as to what kind of structure is being analyzed.

===Inseparable===
The Inseparable pattern<ref name="kim_ppp_ppt"/> is more of an anti-pattern in that it is a problem which needs a parallel solution, but whose solution does not seem to fit any of the aforementioned patterns. Frequently, but not always, the Inseparable pattern will utilize the parallel primitives in complex and non-deterministic ways, and may actually be representative of programming errors or a lack of organization. There does not always have to be a negative connotation, however, as a problem may be so complex as to not fit into any of the above patterns.

==Complex Patterns==
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-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
* '''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
* '''Event Driven'''<ref>[http://www.cs.uiuc.edu/homes/snir/PPP/patterns/event_driven.doc Event-Driven Pattern] at UIUC Computer Science Department</ref> - Allow implicated processes to alert each other to re-commence calculation

==Formalization==
Formalization describes the efforts of the programming community to devise tools which can aid programmers in designing software which follows standardized (whether international/documented or by practice) procedures, methods, and templates for performing parallel operations. These tools may be purely documentation pieces, frameworks, examples, academic papers, etc.
===Design Languages===
Design languages allow programmers to define problems in terms of a common vocabulary so that solutions to problems can be readily identified and efficiently shared.<ref name="ortega"/> A brief survey of some current pattern language efforts follows.
====ParLab====
The Pattern Language for Parallel Programming at Berkeley’s ParLab<ref name=”parlab”>[ http://parlab.eecs.berkeley.edu/wiki/patterns/patterns A Pattern Language for Parallel Programming] at Berkely ParLab</ref> describes five major categories of patterns. These patterns are described through a somewhat disparate documentation set and articles:

* '''Structural Patterns''' - Concerned with the arrangement of different processes that can run in parallel
* '''Computation Patterns''' - Concerned with the way parallel processes handle data
* '''Parallel Algorithm Strategy Patterns''' - Descriptions on how different end results can be achieved by using parallel algorithms
* '''Implementation Strategy Patterns''' - Descriptions on the mechanisms that can be used to implement parallel algorithms
* '''Concurrent Execution Patterns''' - Concerned with how parallel processes should be managed

====University of Florida PLPP====
The development efforts of a pattern language for parallel patterns undertaken at the University of Florida resulted in the development of a published text<ref name=”ufl”>Mattson, Timothy G., Beverly A. Sanders, and Berna Massingill. Patterns for Parallel Programming. Boston: Addison-Wesley, 2005. [http://www.cise.ufl.edu/research/ParallelPatterns/index.htm Homepage]</ref>. This book catalogs the major “design spaces,” or “solution to a problem in context,” which are<ref name=”ufl_toc”>Mattson, Timothy G., Beverly A. Sanders, and Berna Massingill. Patterns for Parallel Programming. Boston: Addison-Wesley, 2005. [http://www.cise.ufl.edu/research/ParallelPatterns/contents.htm Table of Contents]</ref>:

* '''Finding Concurrency''' - How a problem can be parallelized in the first place
* '''Algorithm Structure''' - How the processes can be arranged (see Intuitive and Common patterns earlier in this chapter)
* '''Supporting Structures''' - Primitives and data structures useful in managing parallel tasks
* '''Implementation Mechanisms''' - Architecture and resource-specific details on creating parallel solutions

===Frameworks===
Frameworks are any piece of code for a particular programming language which can help a programmer in creating a program which takes advantage of parallel algorithms. A discussion of the frameworks is outside the scope of this chapter, but the interested reader is suggested to investigate the following resources:
* [http://msdn.microsoft.com/en-us/library/dd492418.aspx Parallel Patterns Library] - Programming library for parallel processes in Microsoft's .NET Framework
* [http://openmp.org/wp/ OpenMP] - Application programminf interface for parallel processes in the C/C++ and Fortran programming languages
* [http://www.cc.gatech.edu/~bader/papers/SWARM.html SWARM] - Application programming interface based on [http://en.wikipedia.org/wiki/POSIX_Threads POSIX Threads] that implements several parallel primitives

==Summary==
In conclusion, there are currently many initiatives to standardize the programmer’s experience when designing and maintaining parallel software systems. Through the survey above, it can be noted that there are four key factors in determining which parallel pattern to use:

* '''Physical resources available''' - The amount of processing units, memory, communication bandwidth, etc.
* '''Algorithm data parallelism''' - How well the algorithm’s data can be split up to be used in independent calculations
* '''Algorithm computation parallelism''' - How much each processor must rely on another for its intermediate calculations
* '''Framework/programming language''' - What limiting factors might exist for implementing the desired pattern in the programming language or framework of choice.

Indeed, there is a pattern for nearly every occasion, and the patterns presented above are just the "key" patterns. However, without careful consideration of the above points, the programmer will find difficulty in optimally implementing his or her software.

==See Also==
* [http://www.cs.uiuc.edu/homes/snir/PPP/ Resources on Parallel Patterns] at the UIUC Computer Science Department

==References==
<references></references>