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

Pmfernan: /* References and External Links */

2012-02-20T16:28:46Z

References and External Links

← Older revision		Revision as of 16:28, 20 February 2012
Line 339:		Line 339:

	19. [http://www.cs.berkeley.edu/~ejr/GSI/cs267-s04/homework-3-results/knap/hw3.pdf, Knapsack Problem]		19. [http://www.cs.berkeley.edu/~ejr/GSI/cs267-s04/homework-3-results/knap/hw3.pdf, Knapsack Problem]

			20. [http://www.cs.wustl.edu/~schmidt/patterns-ace.html, Patterns for Concurrent, Parallel and Distributed Systems]

	== '''Quiz''' ==		== '''Quiz''' ==

Pmfernan: /* Quiz */

2012-02-20T16:07:31Z

Quiz

← Older revision		Revision as of 16:07, 20 February 2012
Line 354:		Line 354:

	Task parallelism consists of		Task parallelism consists of
	# Having ~~task~~ that come in parallel to the processor.		# Having tasks that come in parallel to the processor.
	# Having tasks that are concurrent.		# Having tasks that are concurrent.
	# Running independent tasks in parallel		# Running independent tasks in parallel
Line 369:		Line 369:

	The application design can iterate between structural and computational patterns,		The application design can iterate between structural and computational patterns,
	# Never, they are completely separate ~~task~~.		# Never, they are completely separate tasks.
	# At times, if the number of processes is more than 1000.		# At times, if the number of processes is more than 1000.
	# All the times. Both patterns frequently complement each other.		# All the times. Both patterns frequently complement each other.
Line 385:		Line 385:
	# When the graphs have been done with a parallel computer.		# When the graphs have been done with a parallel computer.
	# Only in the number of vortexes is a power of 2.		# Only in the number of vortexes is a power of 2.
	# At times, when their ~~strictures~~ allow it.		# At times, when their structures allow it.

			'''Answers'''

			* 1
			* 2
			* 3
			* 3
			* 1
			* 3
			* 1
			* True
			* 3

Pmfernan: /* The Second level - Algorithm Strategy Patterns */

2012-02-20T15:53:52Z

The Second level - Algorithm Strategy Patterns

← Older revision		Revision as of 15:53, 20 February 2012
Line 115:		Line 115:

	The most common algorithm strategy patterns include -		The most common algorithm strategy patterns include -
	**Task parallelism - Simply means running independent tasks parallely. An example of this is the embarrassingly parallel pattern.		*Task parallelism - Simply means running independent tasks parallely. An '''example''' of this is the embarrassingly parallel pattern.
	**Pipeline - Running serial operations on a series of data set in parallel because one data set item does not need to wait for the operations to finish on the data item ahead.		*Pipeline - Running serial operations on a series of data set in parallel because one data set item does not need to wait for the operations to finish on the data item ahead.
	**Discrete event - Multiple tasks interacting via an event handler with the handling of those event run in parallel by each task.		*Discrete event - Multiple tasks interacting via an event handler with the handling of those event run in parallel by each task.
	**Speculation - Speculatively and parallely run a series of tasks ahead and commit some of the parallel task as required by the outcome of previous step.		*Speculation - Speculatively and parallely run a series of tasks ahead and commit some of the parallel task as required by the outcome of previous step.
	**Data parallelism -A single stream of instructions is applied to each element of data structure.		*Data parallelism -A single stream of instructions is applied to each element of data structure.
	**Recursive splitting - Recursively generated task can be optimized by assigning these to parallel processing, using a balanced data structure/fork-join or task queue implementation and improving locality.		*Recursive splitting - Recursively generated task can be optimized by assigning these to parallel processing, using a balanced data structure/fork-join or task queue implementation and improving locality.
	**Geometric decomposition - Breaks the problem into data chunks with each each data chunk processed parallely and data chunks exchanging data at boundaries.		**Geometric decomposition - Breaks the problem into data chunks with each each data chunk processed parallely and data chunks exchanging data at boundaries.

Pmfernan: /* The First Level - Decomposition Strategy Patterns */

2012-02-20T15:52:46Z

The First Level - Decomposition Strategy Patterns

← Older revision		Revision as of 15:52, 20 February 2012
Line 104:		Line 104:
	** Approximations, like Montecarlo, where we use sampling or other approximation techniques, that can allow us to analyze a problem with a reduce complexity.		** Approximations, like Montecarlo, where we use sampling or other approximation techniques, that can allow us to analyze a problem with a reduce complexity.
	** Transformations: where the data is transformed so it can be analyzed or processed in a better way using some mathematical techniques, like, for instance, using a Fourier transform. This process presents lots of opportunities to find parallelization. (Multidomain patterns use transformations to change the domain of the problem where it may be easier to solve it. A common '''example''' of this is in modeling earth's atmospheric conditions using Navier Stokes differential equations. The problem formulation in latitude/longitude dimensions requires very small grid size for better stability and does not capture spherical nature (of earth) accurately. The original problem in latitude/logitude dimension is transformed first to latitude/wave number pair using Fast-Fourier transformation and then to Spectral domain using Legendre transformation. The reverse transformation is used to go back to the original dimensions).		** Transformations: where the data is transformed so it can be analyzed or processed in a better way using some mathematical techniques, like, for instance, using a Fourier transform. This process presents lots of opportunities to find parallelization. (Multidomain patterns use transformations to change the domain of the problem where it may be easier to solve it. A common '''example''' of this is in modeling earth's atmospheric conditions using Navier Stokes differential equations. The problem formulation in latitude/longitude dimensions requires very small grid size for better stability and does not capture spherical nature (of earth) accurately. The original problem in latitude/logitude dimension is transformed first to latitude/wave number pair using Fast-Fourier transformation and then to Spectral domain using Legendre transformation. The reverse transformation is used to go back to the original dimensions).

	** Meshes, which can be structured or not, depending on the geometrical coupling between their components. Meshes are systems that are defined geometrically and are represented by a system of equations. Most typical '''example''' of Meshes is in solving Partial Differential Equations (PDE) with boundary conditions using Finite Difference Methods. PDE based problems are common in physical phenomena (Navier Stokes Equations for fluid dynamics, Maxwell's equations for electromagnetic field, Linear elasticity equations) and financial derivatives modeling (Black Scholes Equations). The following patterns are variants of Meshes -		** Meshes, which can be structured or not, depending on the geometrical coupling between their components. Meshes are systems that are defined geometrically and are represented by a system of equations. Most typical '''example''' of Meshes is in solving Partial Differential Equations (PDE) with boundary conditions using Finite Difference Methods. PDE based problems are common in physical phenomena (Navier Stokes Equations for fluid dynamics, Maxwell's equations for electromagnetic field, Linear elasticity equations) and financial derivatives modeling (Black Scholes Equations). The following patterns are variants of Meshes -
	*** Multigrid pattern - Solves a system of equations by varying the granularity of the grid from course to fine, and vice-versa, at various steps in solution. This avoids oscillatory behavior of the solution		*** Multigrid pattern - Solves a system of equations by varying the granularity of the grid from course to fine, and vice-versa, at various steps in solution. This avoids oscillatory behavior of the solution

Pmfernan: /* The First Level - Decomposition Strategy Patterns */

2012-02-20T15:52:15Z

The First Level - Decomposition Strategy Patterns

← Older revision		Revision as of 15:52, 20 February 2012
Line 84:		Line 84:
	In this section we cover the decomposition strategy using Structural and Computational Design pattern. While many of these patterns may appear familiar, we emphasize, however, the relevance of these paradigms in the parallel programming context, i.e., in splitting the software design into sub-tasks that can be run in parallel.		In this section we cover the decomposition strategy using Structural and Computational Design pattern. While many of these patterns may appear familiar, we emphasize, however, the relevance of these paradigms in the parallel programming context, i.e., in splitting the software design into sub-tasks that can be run in parallel.

	'''Structural Pattern''' is a high level view of program design. They represent the "box and arcs" that a software architect would draw on a whiteboard when describing an application. The "boxes" of the diagram represent the "computational" kernels. The problem may be viewed in terms of any of the structures patterns described in the glossary in section 8. Identifying the pattern of the problem automatically points to parallelization that is possible. For example -		*'''Structural Pattern''' is a high level view of program design. They represent the "box and arcs" that a software architect would draw on a whiteboard when describing an application. The "boxes" of the diagram represent the "computational" kernels. The problem may be viewed in terms of any of the structures patterns described in the glossary in section 8. Identifying the pattern of the problem automatically points to parallelization that is possible. For example -
	** pipe-and-filter views a problem as a series of processing boxes with inputs and outputs. Each of the processing box may be run concurrently/in parallel. ('''Examples''' - Vector Processing (loop level pipelining), processing signal through stages, graphics processing of images through stages, shell programming)		** pipe-and-filter views a problem as a series of processing boxes with inputs and outputs. Each of the processing box may be run concurrently/in parallel. ('''Examples''' - Vector Processing (loop level pipelining), processing signal through stages, graphics processing of images through stages, shell programming)
	** agent-and-repository - views a problem as many independent agents/processes acting on a central data repository. Each of the agents/processes may be run in parallel under the control of a manager. ('''Examples''' - database management system where several users can access/update data, shared file systems).		** agent-and-repository - views a problem as many independent agents/processes acting on a central data repository. Each of the agents/processes may be run in parallel under the control of a manager. ('''Examples''' - database management system where several users can access/update data, shared file systems).
Line 95:		Line 95:
	** arbitrary static task graph - is the most general pattern (when nothing else fits) with a general break-up of problem into tasks that may potentially be run in parallel.		** arbitrary static task graph - is the most general pattern (when nothing else fits) with a general break-up of problem into tasks that may potentially be run in parallel.

	'''Computational Patterns''' They are the structural patterns that describe and represent our application and the operations that it comprehends, that is, the building blocks we can divide it upon to be implemented. They can normally be split into smaller patterns in a hierarchical fashion and be adapted to particular hardware and software architectures. At times, the definition of the computational patterns takes to further iterations of other levels of patterns, most commonly the structural ones, as the software architects start pealing through the layers of the application. Some '''examples''' of this -		*'''Computational Patterns''' They are the structural patterns that describe and represent our application and the operations that it comprehends, that is, the building blocks we can divide it upon to be implemented. They can normally be split into smaller patterns in a hierarchical fashion and be adapted to particular hardware and software architectures. At times, the definition of the computational patterns takes to further iterations of other levels of patterns, most commonly the structural ones, as the software architects start pealing through the layers of the application. Some '''examples''' of this -

	** Backtrack, branch and bound: these are decision patterns that look for values in the history of a group of variable and act according to their value. They will become ours if, switch or threads.		** Backtrack, branch and bound: these are decision patterns that look for values in the history of a group of variable and act according to their value. They will become ours if, switch or threads.
	** Circuits, where the components are Boolean in fashion; like memory, or flip-flops.		** Circuits, where the components are Boolean in fashion; like memory, or flip-flops.

Pmfernan: /* The Third Level - Implementation Strategy Patterns */

2012-02-20T15:50:01Z

The Third Level - Implementation Strategy Patterns

← Older revision		Revision as of 15:50, 20 February 2012
Line 128:		Line 128:
	Here is where the system adapts to the application, and vice-versa. It is in plain words the source code and includes its organization and that of the structures that we need to carry it on. This level is where we define how the threads of our code are going to be executed, and it is where we may map and implement the concurrences that we have found in the upper levels in software procedures. We will have a choice of software kind and language that will determine how our concurrency gets implemented. There are two main groups, depending on what the scope of the pattern is: program structure patterns and data structure patterns.		Here is where the system adapts to the application, and vice-versa. It is in plain words the source code and includes its organization and that of the structures that we need to carry it on. This level is where we define how the threads of our code are going to be executed, and it is where we may map and implement the concurrences that we have found in the upper levels in software procedures. We will have a choice of software kind and language that will determine how our concurrency gets implemented. There are two main groups, depending on what the scope of the pattern is: program structure patterns and data structure patterns.

	'''Program structured:'''		*'''Program structured:'''

	** Single Program Multiple Data, where a single operation is performed over many sets of data and the programs have many instances. These are the patterns to define process and threads IDs and ranks.		** Single Program Multiple Data, where a single operation is performed over many sets of data and the programs have many instances. These are the patterns to define process and threads IDs and ranks.
	** Data Parallel Strictly comprehends a big set of patterns and algorithms for concurrent operations with data.		** Data Parallel Strictly comprehends a big set of patterns and algorithms for concurrent operations with data.
Line 140:		Line 139:
	** Computational structures, like BSP, where the system is organize in steps, each one of it with local data access.		** Computational structures, like BSP, where the system is organize in steps, each one of it with local data access.

	'''Data structures:'''		*'''Data structures:'''
	** Shared queues that manages data streams which tasks are executed at the same time.		** Shared queues that manages data streams which tasks are executed at the same time.
	** Distributed Arrays are a common structure and presents a large number of possibilities for concurrency.The drawback is that managing and maintaining these structures could be cumbersome and require lots of work, in particular when they are shared by a large number of processes.		** Distributed Arrays are a common structure and presents a large number of possibilities for concurrency.The drawback is that managing and maintaining these structures could be cumbersome and require lots of work, in particular when they are shared by a large number of processes.

Pmfernan: /* The Fourth Level - Parallel Execution Patterns */

2012-02-20T15:49:34Z

The Fourth Level - Parallel Execution Patterns

← Older revision		Revision as of 15:49, 20 February 2012
Line 150:		Line 150:
	These patterns deal with how a parallel algorithm is translated into software elements to fully exploit the specific hardware elements. . They are the strategies and facilities to build, support and synchronize our tasks. These include - (1) Process and thread control patterns (2) Coordination pattern		These patterns deal with how a parallel algorithm is translated into software elements to fully exploit the specific hardware elements. . They are the strategies and facilities to build, support and synchronize our tasks. These include - (1) Process and thread control patterns (2) Coordination pattern

	'''Process and thread controls patterns that advance a program counter -'''		*'''Process and thread controls patterns that advance a program counter -'''

	** MIMD pattern - Multiple process with each one acting on their own data and coordinating communication through discrete events		** MIMD pattern - Multiple process with each one acting on their own data and coordinating communication through discrete events
	** Data flow - Computation steps are viewed as direct acylice graph of thread that are mapped to parallel computers		** Data flow - Computation steps are viewed as direct acylice graph of thread that are mapped to parallel computers
Line 159:		Line 158:
	** Digital circuits - Functionality is hard wired for concurrency in digital circuits and available as separate instruction set.		** Digital circuits - Functionality is hard wired for concurrency in digital circuits and available as separate instruction set.

	'''Patterns that deal with coordination of threads or processes (all well known)-'''		*'''Patterns that deal with coordination of threads or processes (all well known)-'''

	** Message passing - Passing messages between process that need to be synchronized		** Message passing - Passing messages between process that need to be synchronized
	** Collective Communication - Message is passed to a group of (rather than individual) threads. Example reductions, broadcasts, prefix sums, and scatter/gather		** Collective Communication - Message is passed to a group of (rather than individual) threads. Example reductions, broadcasts, prefix sums, and scatter/gather

Pmfernan: /* The First Level - Decomposition Strategy Patterns */

2012-02-20T15:48:34Z

The First Level - Decomposition Strategy Patterns

Pmfernan: /* The First Level - Decomposition Strategy Patterns */

2012-02-20T14:44:24Z

The First Level - Decomposition Strategy Patterns

← Older revision		Revision as of 14:44, 20 February 2012
Line 109:		Line 109:
	*** Multigrid pattern - Solves a system of equations by varying the granularity of the grid from course to fine, and vice-versa, at various steps in solution. This avoids oscillatory behavior of the solution		*** Multigrid pattern - Solves a system of equations by varying the granularity of the grid from course to fine, and vice-versa, at various steps in solution. This avoids oscillatory behavior of the solution
	*** Adaptive mesh refinement - Varies the size of the mesh at specific areas depending upon the accuracy requirement in each specific area.		*** Adaptive mesh refinement - Varies the size of the mesh at specific areas depending upon the accuracy requirement in each specific area.
	*** Odd-Even Communication Group - Sequentially dependent points in an algorithm are broken down into odd-even groups and parallelized. Example: Red-Black Dots in Ocean Problem (Gauss-Seidel)		*** Odd-Even Communication Group - Sequentially dependent points in an algorithm are broken down into odd-even groups and parallelized. '''Example:''' Red-Black Dots in Ocean Problem (Gauss-Seidel)
	*** Transpositional Communication Group - Rows and columns of solution points are transposed at different steps in computation with the row dimension split up for parallelization		*** Transpositional Communication Group - Rows and columns of solution points are transposed at different steps in computation with the row dimension split up for parallelization

Pmfernan: /* MapReduce */

2012-02-20T14:39:03Z

MapReduce

← Older revision		Revision as of 14:39, 20 February 2012
Line 209:		Line 209:

	=== '''MapReduce''' ===		=== '''MapReduce''' ===
	As mentioned before, [http://en.wikipedia.org/wiki/MapReduce, MapReduce] is a Google tool oriented to work with clusters of computers. It is another example of Master/workers and it has two steps: '''Map''' , where our problem is divides into sub-problems that are assigned to workers; and '''Reduce''', where the master node processes the results coming from the workers.		As mentioned before, [http://en.wikipedia.org/wiki/MapReduce, MapReduce] is a Google tool oriented to work with clusters of computers, as it adapts very well to distributed systems. It is another example of Master/workers and it has two steps: '''Map''' , where our problem is divides into sub-problems that are assigned to workers; and '''Reduce''', where the master node processes the results coming from the workers.
			Here is an example of the two functions, in pseudocode, that would count the number of times a particular picture 'pic' shows up in a set of documents:

			MAP(pic, setDocuments): // pic is the picture, setDocuments is a group of documents, where we are looking
			for each pic in setDocument:
			send(pic, TRUE);

			REDUCE(pic, picCount): //pic is a picture and picCount is the count.
			sum = 0;
			for each pc in partialCounts:
			sum += pc;
			send(pic, sum);

	== '''Glossary Of Patterns'''==		== '''Glossary Of Patterns'''==

← Older revision		Revision as of 15:48, 20 February 2012
Line 85:		Line 85:

	'''Structural Pattern''' is a high level view of program design. They represent the "box and arcs" that a software architect would draw on a whiteboard when describing an application. The "boxes" of the diagram represent the "computational" kernels. The problem may be viewed in terms of any of the structures patterns described in the glossary in section 8. Identifying the pattern of the problem automatically points to parallelization that is possible. For example -		'''Structural Pattern''' is a high level view of program design. They represent the "box and arcs" that a software architect would draw on a whiteboard when describing an application. The "boxes" of the diagram represent the "computational" kernels. The problem may be viewed in terms of any of the structures patterns described in the glossary in section 8. Identifying the pattern of the problem automatically points to parallelization that is possible. For example -
	** pipe-and-filter views a problem as a series of processing boxes with inputs and outputs. Each of the processing box may be run concurrently/in parallel. (Examples - Vector Processing (loop level pipelining), processing signal through stages, graphics processing of images through stages, shell programming)		** pipe-and-filter views a problem as a series of processing boxes with inputs and outputs. Each of the processing box may be run concurrently/in parallel. ('''Examples''' - Vector Processing (loop level pipelining), processing signal through stages, graphics processing of images through stages, shell programming)
	** agent-and-repository - views a problem as many independent agents/processes acting on a central data repository. Each of the agents/processes may be run in parallel under the control of a manager. (Examples - database management system where several users can access/update data, shared file systems).		** agent-and-repository - views a problem as many independent agents/processes acting on a central data repository. Each of the agents/processes may be run in parallel under the control of a manager. ('''Examples''' - database management system where several users can access/update data, shared file systems).
	** process control - views a state being monitored continuously and actions being taken based on the monitor results. The actions may be run concurrently/in parallel. (Example - auto-pilot navigation systems for airplanes, dynamic range compression software system in audio applications (e.g. hearing aid) that modify signal based on parallel processing of recent history)		** process control - views a state being monitored continuously and actions being taken based on the monitor results. The actions may be run concurrently/in parallel. ('''Example''' - auto-pilot navigation systems for airplanes, dynamic range compression software system in audio applications (e.g. hearing aid) that modify signal based on parallel processing of recent history)
	** event based implicit invocation - this pattern involves agents reacting to events and generating events. This is quite easily amenable to be handled by parallel processors, since handling many events may be viewed as parallel tasks.		** event based implicit invocation - this pattern involves agents reacting to events and generating events. This is quite easily amenable to be handled by parallel processors, since handling many events may be viewed as parallel tasks.
	** model-view-controller - the roles of data processing, controlling the data processing and interaction with the user may be easily separated among different processing functions that may be run in parallel. (Example - typicaly used in GUI displays of data where the data displayed (i.e. the model) is manipulated separately from the view that renders the display and a controller is used to handle multiple requests for display. The model, view and controller tasks may run parallely.)		** model-view-controller - the roles of data processing, controlling the data processing and interaction with the user may be easily separated among different processing functions that may be run in parallel. ('''Example''' - typicaly used in GUI displays of data where the data displayed (i.e. the model) is manipulated separately from the view that renders the display and a controller is used to handle multiple requests for display. The model, view and controller tasks may run parallely.)
	** iterative refinement - An example of this is the ocean problem covered in the class. A process to refine the solution iteratively may be broken out among the parallel tasks e.g. red and black dot and anti-parallel processing for the ocean problem.		** iterative refinement - An '''example''' of this is the ocean problem covered in the class. A process to refine the solution iteratively may be broken out among the parallel tasks e.g. red and black dot and anti-parallel processing for the ocean problem.
	** map-reduce - involves mapping a single function to independent data sets and reducing these execution to solution. The task of running and reducing may be run in parallel. (Examples - used by Google to regenerate index of the World Wide Web, counting of word frequency in a text, distributed grep to test every line of the input files to match a given pattern defined by a regular expression)		** map-reduce - involves mapping a single function to independent data sets and reducing these execution to solution. The task of running and reducing may be run in parallel. ('''Examples''' - used by Google to regenerate index of the World Wide Web, counting of word frequency in a text, distributed grep to test every line of the input files to match a given pattern defined by a regular expression)
	** puppeteer - involves several agents running in parallel and managed by a puppeteer. This differs from "Agent and Repository" pattern to the extent that the puppeteer is mainly involved in managing interaction among agents rather than access to shared data. (Example - Simulation of atmospheric conditions by an "Atmospheric Pupeteer" that handles interaction between "air", "cloud" and "ground" agents).		** puppeteer - involves several agents running in parallel and managed by a puppeteer. This differs from "Agent and Repository" pattern to the extent that the puppeteer is mainly involved in managing interaction among agents rather than access to shared data. ('''Example''' - Simulation of atmospheric conditions by an "Atmospheric Pupeteer" that handles interaction between "air", "cloud" and "ground" agents).
	** arbitrary static task graph - is the most general pattern (when nothing else fits) with a general break-up of problem into tasks that may potentially be run in parallel.		** arbitrary static task graph - is the most general pattern (when nothing else fits) with a general break-up of problem into tasks that may potentially be run in parallel.

	'''Computational Patterns''' They are the structural patterns that describe and represent our application and the operations that it comprehends, that is, the building blocks we can divide it upon to be implemented. They can normally be split into smaller patterns in a hierarchical fashion and be adapted to particular hardware and software architectures. At times, the definition of the computational patterns takes to further iterations of other levels of patterns, most commonly the structural ones, as the software architects start pealing through the layers of the application. Some examples of this -		'''Computational Patterns''' They are the structural patterns that describe and represent our application and the operations that it comprehends, that is, the building blocks we can divide it upon to be implemented. They can normally be split into smaller patterns in a hierarchical fashion and be adapted to particular hardware and software architectures. At times, the definition of the computational patterns takes to further iterations of other levels of patterns, most commonly the structural ones, as the software architects start pealing through the layers of the application. Some '''examples''' of this -

	** Backtrack, branch and bound: these are decision patterns that look for values in the history of a group of variable and act according to their value. They will become ours if, switch or threads.		** Backtrack, branch and bound: these are decision patterns that look for values in the history of a group of variable and act according to their value. They will become ours if, switch or threads.
	** Circuits, where the components are Boolean in fashion; like memory, or flip-flops.		** Circuits, where the components are Boolean in fashion; like memory, or flip-flops.
	** Dynamic programming, which are the typical problems of "size N". It is important to define these structures well to get the best parallelisms. These cases are normally traverses or searches. (Wavefront pattern refers to dynamic programming. It is called as such because it resembles a wave moving across a diagonal of a square with computation points increasing initially till the middle of the diagonal and then decreasing as the opposite vertex is reached. Typical examples of dynamic programming problems that are very amenable to parallel programming are a) shortest path from two vertices of graph using Bellman-Ford/Floyd-Warshall/Dijkstra algorithms, b) string algorithms for finding longest common/increasing subsequence between two strings)		** Dynamic programming, which are the typical problems of "size N". It is important to define these structures well to get the best parallelisms. These cases are normally traverses or searches. (Wavefront pattern refers to dynamic programming. It is called as such because it resembles a wave moving across a diagonal of a square with computation points increasing initially till the middle of the diagonal and then decreasing as the opposite vertex is reached. Typical '''examples''' of dynamic programming problems that are very amenable to parallel programming are a) shortest path from two vertices of graph using Bellman-Ford/Floyd-Warshall/Dijkstra algorithms, b) string algorithms for finding longest common/increasing subsequence between two strings)
	** Linear algebras, where the problems can be organized in mathematical structures, like for instance matrices, and arithmetic expressions. They can be spares or dense, depending if their elements are mostly zeroes or not. Their operations are typically well defined and data can be prefetch, which means normally many opportunities for finding ways to repetition, iteration and parallelization.		** Linear algebras, where the problems can be organized in mathematical structures, like for instance matrices, and arithmetic expressions. They can be spares or dense, depending if their elements are mostly zeroes or not. Their operations are typically well defined and data can be prefetch, which means normally many opportunities for finding ways to repetition, iteration and parallelization.
	** Automatas and Finite State Machines, where the inputs are treated with machines that can be virtual or not. Associated often to hardware, like FPGAs, they are also common in software, like regular expressions, or simulations. Parallelization will strongly depend on the architecture of the machine that manages the application.		** Automatas and Finite State Machines, where the inputs are treated with machines that can be virtual or not. Associated often to hardware, like FPGAs, they are also common in software, like regular expressions, or simulations. Parallelization will strongly depend on the architecture of the machine that manages the application.
	** [https://engineering.purdue.edu/~milind/docs/tr-09-05.pdf, Graphical Algorithms and Models], that comprehend all cases where the applications are better represented as graphs. These graphs nodes, vertices and edges and can be object of a number of operations, like traversing, that can be easily parallelized.		** [https://engineering.purdue.edu/~milind/docs/tr-09-05.pdf, Graphical Algorithms and Models], that comprehend all cases where the applications are better represented as graphs. These graphs nodes, vertices and edges and can be object of a number of operations, like traversing, that can be easily parallelized.
	** Approximations, like Montecarlo, where we use sampling or other approximation techniques, that can allow us to analyze a problem with a reduce complexity.		** Approximations, like Montecarlo, where we use sampling or other approximation techniques, that can allow us to analyze a problem with a reduce complexity.
	** Transformations: where the data is transformed so it can be analyzed or processed in a better way using some mathematical techniques, like, for instance, using a Fourier transform. This process presents lots of opportunities to find parallelization. (Multidomain patterns use transformations to change the domain of the problem where it may be easier to solve it. A common example of this is in modeling earth's atmospheric conditions using Navier Stokes differential equations. The problem formulation in latitude/longitude dimensions requires very small grid size for better stability and does not capture spherical nature (of earth) accurately. The original problem in latitude/logitude dimension is transformed first to latitude/wave number pair using Fast-Fourier transformation and then to Spectral domain using Legendre transformation. The reverse transformation is used to go back to the original dimensions).		** Transformations: where the data is transformed so it can be analyzed or processed in a better way using some mathematical techniques, like, for instance, using a Fourier transform. This process presents lots of opportunities to find parallelization. (Multidomain patterns use transformations to change the domain of the problem where it may be easier to solve it. A common '''example''' of this is in modeling earth's atmospheric conditions using Navier Stokes differential equations. The problem formulation in latitude/longitude dimensions requires very small grid size for better stability and does not capture spherical nature (of earth) accurately. The original problem in latitude/logitude dimension is transformed first to latitude/wave number pair using Fast-Fourier transformation and then to Spectral domain using Legendre transformation. The reverse transformation is used to go back to the original dimensions).

	** Meshes, which can be structured or not, depending on the geometrical coupling between their components. Meshes are systems that are defined geometrically and are represented by a system of equations. Most typical example of Meshes is in solving Partial Differential Equations (PDE) with boundary conditions using Finite Difference Methods. PDE based problems are common in physical phenomena (Navier Stokes Equations for fluid dynamics, Maxwell's equations for electromagnetic field, Linear elasticity equations) and financial derivatives modeling (Black Scholes Equations). The following patterns are variants of Meshes -		** Meshes, which can be structured or not, depending on the geometrical coupling between their components. Meshes are systems that are defined geometrically and are represented by a system of equations. Most typical '''example''' of Meshes is in solving Partial Differential Equations (PDE) with boundary conditions using Finite Difference Methods. PDE based problems are common in physical phenomena (Navier Stokes Equations for fluid dynamics, Maxwell's equations for electromagnetic field, Linear elasticity equations) and financial derivatives modeling (Black Scholes Equations). The following patterns are variants of Meshes -
	*** Multigrid pattern - Solves a system of equations by varying the granularity of the grid from course to fine, and vice-versa, at various steps in solution. This avoids oscillatory behavior of the solution		*** Multigrid pattern - Solves a system of equations by varying the granularity of the grid from course to fine, and vice-versa, at various steps in solution. This avoids oscillatory behavior of the solution
	*** Adaptive mesh refinement - Varies the size of the mesh at specific areas depending upon the accuracy requirement in each specific area.		*** Adaptive mesh refinement - Varies the size of the mesh at specific areas depending upon the accuracy requirement in each specific area.