Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T02:30:38Z

Mbdills: /* Assignment */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, the advancements in measurement technologies, and a better understanding of environmental physics, more intricate (and thus realistic) environmental models are developed every year. With all of these factors to consider, it is no surprise that the number of parameters for computation increase each year as well.

The Department of Environmental Physics at Utrecht University [http://www.uu.nl/uupublish/homeuu/1main.html] (specifically the writers of the paper this is based upon: Vrugt, Nuallain, Robinson, Bouten, Dekker and Sloot) thus propose the use of an algorithm, the Shuffled Complex Evolution Metropolis (SCEM-UA). The SCEM-UA algorithm is used for global optimization of the estimation of environmental models. With the amount of information and calculations needed to obtain a proper model, a parallel implementation of this algorithm is a great alternative. This algorithm, when implemented in a parallel structure, can be used for several model intricate case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the example of migratory birds, this task may be divided into different data sets such as population size, locations, etc. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment [http://en.wikipedia.org/wiki/Assignment_(computer_science)#Parallel_assignment] ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes.

The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points in each complex. While this is happening, all of the related data is kept together, so as to avoid confusion. The data is kept together through each array that it is stored in during the decomposition phase. During that phase arrays are created using matching data. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T02:29:53Z

Mbdills: /* Assignment */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, the advancements in measurement technologies, and a better understanding of environmental physics, more intricate (and thus realistic) environmental models are developed every year. With all of these factors to consider, it is no surprise that the number of parameters for computation increase each year as well.

The Department of Environmental Physics at Utrecht University [http://www.uu.nl/uupublish/homeuu/1main.html] (specifically the writers of the paper this is based upon: Vrugt, Nuallain, Robinson, Bouten, Dekker and Sloot) thus propose the use of an algorithm, the Shuffled Complex Evolution Metropolis (SCEM-UA). The SCEM-UA algorithm is used for global optimization of the estimation of environmental models. With the amount of information and calculations needed to obtain a proper model, a parallel implementation of this algorithm is a great alternative. This algorithm, when implemented in a parallel structure, can be used for several model intricate case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the example of migratory birds, this task may be divided into different data sets such as population size, locations, etc. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes.

The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points in each complex. While this is happening, all of the related data is kept together, so as to avoid confusion. The data is kept together through each array that it is stored in during the decomposition phase. During that phase arrays are created using matching data. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T02:12:27Z

Mbdills: /* Assignment */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, the advancements in measurement technologies, and a better understanding of environmental physics, more intricate (and thus realistic) environmental models are developed every year. With all of these factors to consider, it is no surprise that the number of parameters for computation increase each year as well.

The Department of Environmental Physics at Utrecht University [http://www.uu.nl/uupublish/homeuu/1main.html] (specifically the writers of the paper this is based upon: Vrugt, Nuallain, Robinson, Bouten, Dekker and Sloot) thus propose the use of an algorithm, the Shuffled Complex Evolution Metropolis (SCEM-UA). The SCEM-UA algorithm is used for global optimization of the estimation of environmental models. With the amount of information and calculations needed to obtain a proper model, a parallel implementation of this algorithm is a great alternative. This algorithm, when implemented in a parallel structure, can be used for several model intricate case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the example of migratory birds, this task may be divided into different data sets such as population size, locations, etc. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes.

The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T02:03:33Z

Mbdills: /* Decomposition */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, the advancements in measurement technologies, and a better understanding of environmental physics, more intricate (and thus realistic) environmental models are developed every year. With all of these factors to consider, it is no surprise that the number of parameters for computation increase each year as well.

The Department of Environmental Physics at Utrecht University [http://www.uu.nl/uupublish/homeuu/1main.html] (specifically the writers of the paper this is based upon: Vrugt, Nuallain, Robinson, Bouten, Dekker and Sloot) thus propose the use of an algorithm, the Shuffled Complex Evolution Metropolis (SCEM-UA). The SCEM-UA algorithm is used for global optimization of the estimation of environmental models. With the amount of information and calculations needed to obtain a proper model, a parallel implementation of this algorithm is a great alternative. This algorithm, when implemented in a parallel structure, can be used for several model intricate case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the example of migratory birds, this task may be divided into different data sets such as population size, locations, etc. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T01:59:49Z

Mbdills: /* Overview */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, the advancements in measurement technologies, and a better understanding of environmental physics, more intricate (and thus realistic) environmental models are developed every year. With all of these factors to consider, it is no surprise that the number of parameters for computation increase each year as well.

The Department of Environmental Physics at Utrecht University [http://www.uu.nl/uupublish/homeuu/1main.html] (specifically the writers of the paper this is based upon: Vrugt, Nuallain, Robinson, Bouten, Dekker and Sloot) thus propose the use of an algorithm, the Shuffled Complex Evolution Metropolis (SCEM-UA). The SCEM-UA algorithm is used for global optimization of the estimation of environmental models. With the amount of information and calculations needed to obtain a proper model, a parallel implementation of this algorithm is a great alternative. This algorithm, when implemented in a parallel structure, can be used for several model intricate case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T01:58:41Z

Mbdills: /* Overview */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, the advancements in measurement technologies, and a better understanding of environmental physics, more intricate (and thus realistic) environmental models are developed every year. With all of these factors to consider, it is no surprise that the number of parameters for computation increase each year as well.

The Department of Environmental Physics (specifically the writers of the paper this is based upon: Vrugt, Nuallain, Robinson, Bouten, Dekker and Sloot) thus propose the use of an algorithm, the Shuffled Complex Evolution Metropolis (SCEM-UA). The SCEM-UA algorithm is used for global optimization of the estimation of environmental models. With the amount of information and calculations needed to obtain a proper model, a parallel implementation of this algorithm is a great alternative. This algorithm, when implemented in a parallel structure, can be used for several model intricate case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T01:51:08Z

Mbdills: /* Flow Chart Overview of Parallelization */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]
This flowchart illustrates the implementation of the SCEM-UA algorithm in a parallel scheme. A "master" computer (illustrated by the left side of the flowchart) perform the SCEM-UA algorithmic steps. A slave computer (illustrated by the right side of the flowchart) run the simulation model.

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-29T01:47:08Z

Mbdills: /* Overview */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences [http://en.wikipedia.org/wiki/Environmental_science] increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:26:11Z

Mbdills: /* References */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[http://www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:25:06Z

Mbdills: /* References */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Candidate points are generated and then sent to different nodes. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =
[www.science.uva.nl/research/scs/papers/archive/Vrugt2006b.pdf Application of Parallel Computing to Stochastic Parameter Estimation in Environmental Models]

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:24:06Z

Mbdills: /* Mapping */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:21:56Z

Mbdills: /* Mapping */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. Since each node is working on it's own set of data, and said data is stored into array ''D'' , there is no need for communication between processors (as described in "'''Orchestration'''").

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:20:08Z

Mbdills: /* Steps of Parallelization */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors! Because data sets are so large that the majority of computational time is alloted toward running the model code and/or generating the desired output.

Since data is stored into an array (referenced here as ''D'' ), once computations are complete, the array is sorted based upon decreasing posterior density.

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. This allows for no communication between the different nodes. By having each node work on a different set of data without the need for communication allows for huge efficiency gains because one is not concerned with sequential execution. Instead, the majority of computation time is alloted toward running model code and generating the desired output.

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:15:41Z

Mbdills: /* Orchestration */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
The orchestration phase of parallelization is concerned with process communication and synchronization. Interestingly, this algorithm is not concerned with communication between processors, and in fact does not concern itself with communication among the processors!

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. This allows for no communication between the different nodes. By having each node work on a different set of data without the need for communication allows for huge efficiency gains because one is not concerned with sequential execution. Instead, the majority of computation time is alloted toward running model code and generating the desired output.

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:07:21Z

Mbdills: /* Decomposition */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

Each processor is then assigned a different subset of ''s'' to evaluate. Once this is accomplished, an array ''D''[1:s,1:n+1] (where n = number of parameters) is created. Finally, the ''k'' sequences are used to initialize starting locations for each sequence using the first ''k'' elements in ''D'' such that Sk = D[k,1:n+1] (again where n = # of parameters).

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
In the orchestration stage of parallelization, processes take the necessary actions of data access, communication and synchronization. In this example,

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. This allows for no communication between the different nodes. By having each node work on a different set of data without the need for communication allows for huge efficiency gains because one is not concerned with sequential execution. Instead, the majority of computation time is alloted toward running model code and generating the desired output.

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T04:01:52Z

Mbdills: /* Decomposition */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==
The scope of environmental sciences increases significantly each year. With the advancement of computer systems, more intricate (and thus realistic) models are developed every year. As with in advancement in technology, the number of parameters for computation increase each year as well. The Shuffled Complex Evolution Metropolis (SCEM-UA) algorithm is used for global optimization of the estimation of environmental models. This algorithm is then implemented in a parallel in a very user-friendly way for further optimization. The algorithm can be used for several model case studies, such as the prediction of migratory bird flight paths.

= Steps of Parallelization =
== Flow Chart Overview of Parallelization ==
[[Image:Fig3.jpg|center|thumb|500px]]

== Decomposition ==
Decomposition in parallel processes is described as the division of the computation into various tasks. In the SCEM-UA algorithm, a dimension (''n'' ), number of complexes (''k'' ) and a population size (''s'' ) are taken. The number of points, ''m'', is then calculated using the formula:

'''m = s/k'''

== Assignment ==
Once the algorithm is completed and split into different parts, it is then partitioned into different complexes. The ''s'' points of ''D'' are partitioned into ''k'' different complexes {C1 ... Ck}. Each different complex contains ''m'' points. The first complex contains every k(j-1)+1 point of ''D'', the second contains k(j-1)+2 and so on (where j = 1,...m).

== Orchestration ==
In the orchestration stage of parallelization, processes take the necessary actions of data access, communication and synchronization. In this example,

== Mapping ==
In the mapping of the SCEM-UA algorithm, it is vital that each processor has a different data set on which to work. This allows for no communication between the different nodes. By having each node work on a different set of data without the need for communication allows for huge efficiency gains because one is not concerned with sequential execution. Instead, the majority of computation time is alloted toward running model code and generating the desired output.

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:57:27Z

Mbdills: /* Decomposition */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:49:52Z

Mbdills: /* Mapping */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:37:58Z

Mbdills: /* Orchestration */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:23:56Z

Mbdills: /* Assignment */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:16:35Z

Mbdills: /* Graphical Overview */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:16:11Z

Mbdills: /* Steps of Parallelization */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:15:38Z

Mbdills: /* Overview */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T03:12:22Z

Mbdills: /* Overview */

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:23:54Z

Mbdills: /* Steps of Parallelization */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==

= Steps of Parallelization =
[[Image:Fig3.jpg|center|thumb|500px]]
== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:22:32Z

Mbdills: /* Steps of Parallelization */

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==

= Steps of Parallelization =
[[Image:Fig3.jpg]]
== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

= References =

File:Fig3.jpg

2007-09-25T02:21:42Z

Mbdills:

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:19:00Z

Mbdills:

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==

= Steps of Parallelization =

== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

= References =

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:18:37Z

Mbdills:

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Overview ==

= Steps of Parallelization =

== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:18:22Z

Mbdills:

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Summary ==

= Steps of Parallelization =

== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:18:14Z

Mbdills:

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Summary ==

= Steps of Parallelization ==

== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:18:02Z

Mbdills:

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Summary ==

= Steps of Parallelization

== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:17:32Z

Mbdills:

= Parallel Application: Shuffled Complex Evolution Metropolis =

== Summary ==

== Decomposition ==

== Assignment ==

== Orchestration ==

== Mapping ==

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:15:52Z

Mbdills:

== Parallel Application: Shuffled Complex Evolution Metropolis ==

File:Image.jpg

2007-09-25T02:14:34Z

Mbdills:

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:13:28Z

Mbdills:

CSC/ECE 506 Fall 2007/wiki2 4 md

2007-09-25T02:12:05Z

Mbdills:

[[Image:Fig. 3.jpg]]

File:Fig. 3.jpg

2007-09-25T02:08:49Z

Mbdills:

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:54:16Z

Mbdills: /* Systolic Architecture Currently */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
'''Systolic architecture''' sought to replace the uniprocessor architecture by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29]) and work is done in-between each heartbeat. Each processor produces a new data item after each heartbeat. Those items are then either continued on the journey toward completion, or returned to the main memory. The systolic architecture's ability to put highly specialized computation under simple, regular and highly localized communication patterns are the key to the systolic architecture. [http://www.gigaflop.demon.co.uk/comp/chapt2.htm]

== New Developments in Dataflow and Systolic Architectures ==

=== Dataflow Architecture Currently ===
Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the programming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow

=== Systolic Architecture Currently ===
There are several limitations to systolic architecture that have held back it's progress:
#They are restricted to applications with strictly regular data dependencies.
#They have a general lack of flexibility.
#They are only suitable, once designed, to support only one application problem, not several.[http://delivery.acm.org/10.1145/1150000/1142156/p251-ayala_rincon.pdf?key1=1142156&key2=4040698811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]

The majority of advancements in the realm of systolic architecture focus more on the ''application'' of the architecture as opposed to ''advancement'' of the architecture itself. Several papers propose different applications for systolic architecture:

#One such paper, '''A Unified Systolic Architecture for Combined Inter and Intra Predictions in H.264/AVC Decoder''', focuses on the efficiency of video coding. Presented by three professors, Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, of the Cheng-Kung University in Taiwain, this 2000 paper presents an increase in hardware utilization and minimization of cost using a combination of inter and intra predictions. These predictions are produced via a re-programmable FIR filter. A systolic array is used in the further implementation of this process. The three conclude that the use of systolic architecture greatly reduce the cost of processing and improved performance. They argue that their design, in comparison to other designs, produces a lower cost and power (but a higher throughput). [http://delivery.acm.org/10.1145/1150000/1143566/p73-li.pdf?key1=1143566&key2=9464598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]
#Another paper, '''High-Speed Systolic Architectures for Finite Field Inversion and Division''', written in combination by Dilip V. Sarwate of University of Illinois at Urbana-Champaign and Zhiyuan Yan of Lehigh University. The two propose the use of systolic architectures for finite field inversion and division. They claim that the systolic architecture shows a marked performance when compared to other, previously used, architectures, achieving an O(m2) area-time complexity, O(m) latency and a critical path delay on two logic gates. [http://delivery.acm.org/10.1145/990000/989064/p462-yan.pdf?key1=989064&key2=9865598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:45:43Z

Mbdills: /* Systolic */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
'''Systolic architecture''' sought to replace the uniprocessor architecture by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29]) and work is done in-between each heartbeat. Each processor produces a new data item after each heartbeat. Those items are then either continued on the journey toward completion, or returned to the main memory. The systolic architecture's ability to put highly specialized computation under simple, regular and highly localized communication patterns are the key to the systolic architecture. [http://www.gigaflop.demon.co.uk/comp/chapt2.htm]

== New Developments in Dataflow and Systolic Architectures ==

=== Dataflow Architecture Currently ===
Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the programming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow

=== Systolic Architecture Currently ===
The majority of advancements in the realm of systolic architecture focus more on the ''application'' of the architecture as opposed to ''advancement'' of the architecture itself. Several papers propose different applications for systolic architecture:

#One such paper, '''A Unified Systolic Architecture for Combined Inter and Intra Predictions in H.264/AVC Decoder''', focuses on the efficiency of video coding. Presented by three professors, Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, of the Cheng-Kung University in Taiwain, this 2000 paper presents an increase in hardware utilization and minimization of cost using a combination of inter and intra predictions. These predictions are produced via a re-programmable FIR filter. A systolic array is used in the further implementation of this process. The three conclude that the use of systolic architecture greatly reduce the cost of processing and improved performance. They argue that their design, in comparison to other designs, produces a lower cost and power (but a higher throughput). [http://delivery.acm.org/10.1145/1150000/1143566/p73-li.pdf?key1=1143566&key2=9464598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]
#Another paper, '''High-Speed Systolic Architectures for Finite Field Inversion and Division''', written in combination by Dilip V. Sarwate of University of Illinois at Urbana-Champaign and Zhiyuan Yan of Lehigh University. The two propose the use of systolic architectures for finite field inversion and division. They claim that the systolic architecture shows a marked performance when compared to other, previously used, architectures, achieving an O(m2) area-time complexity, O(m) latency and a critical path delay on two logic gates. [http://delivery.acm.org/10.1145/990000/989064/p462-yan.pdf?key1=989064&key2=9865598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:45:09Z

Mbdills: /* Systolic Architecture Currently */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
'''Systolic architecture''' sought to replace the uniprocessor architecture by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29]) and work is done in-between each heartbeat. Each processor produces a new data item after each heartbeat. Those items are then either continued on the journey toward completion, or returned to the main memory. The systolic architecture's ability to put highly specialized computation under simple, regular and highly localized communication patterns are the key to the systolic architecture.

== New Developments in Dataflow and Systolic Architectures ==

=== Dataflow Architecture Currently ===
Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the programming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow

=== Systolic Architecture Currently ===
The majority of advancements in the realm of systolic architecture focus more on the ''application'' of the architecture as opposed to ''advancement'' of the architecture itself. Several papers propose different applications for systolic architecture:

#One such paper, '''A Unified Systolic Architecture for Combined Inter and Intra Predictions in H.264/AVC Decoder''', focuses on the efficiency of video coding. Presented by three professors, Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, of the Cheng-Kung University in Taiwain, this 2000 paper presents an increase in hardware utilization and minimization of cost using a combination of inter and intra predictions. These predictions are produced via a re-programmable FIR filter. A systolic array is used in the further implementation of this process. The three conclude that the use of systolic architecture greatly reduce the cost of processing and improved performance. They argue that their design, in comparison to other designs, produces a lower cost and power (but a higher throughput). [http://delivery.acm.org/10.1145/1150000/1143566/p73-li.pdf?key1=1143566&key2=9464598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]
#Another paper, '''High-Speed Systolic Architectures for Finite Field Inversion and Division''', written in combination by Dilip V. Sarwate of University of Illinois at Urbana-Champaign and Zhiyuan Yan of Lehigh University. The two propose the use of systolic architectures for finite field inversion and division. They claim that the systolic architecture shows a marked performance when compared to other, previously used, architectures, achieving an O(m2) area-time complexity, O(m) latency and a critical path delay on two logic gates. [http://delivery.acm.org/10.1145/990000/989064/p462-yan.pdf?key1=989064&key2=9865598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:44:47Z

Mbdills: /* Systolic Architecture Currently */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
'''Systolic architecture''' sought to replace the uniprocessor architecture by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29]) and work is done in-between each heartbeat. Each processor produces a new data item after each heartbeat. Those items are then either continued on the journey toward completion, or returned to the main memory. The systolic architecture's ability to put highly specialized computation under simple, regular and highly localized communication patterns are the key to the systolic architecture.

== New Developments in Dataflow and Systolic Architectures ==

=== Dataflow Architecture Currently ===
Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the programming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow

=== Systolic Architecture Currently ===
The majority of advancements in the realm of systolic architecture focus more on the ''application'' of the architecture as opposed to ''advancement'' of the architecture itself. Several papers propose different applications for systolic architecture:

#One such paper, '''A Unified Systolic Architecture for Combined Inter and Intra Predictions in H.264/AVC Decoder''', focuses on the efficiency of video coding. Presented by three professors, Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, of the Cheng-Kung University in Taiwain, this 2000 paper presents an increase in hardware utilization and minimization of cost using a combination of inter and intra predictions. These predictions are produced via a re-programmable FIR filter. A systolic array is used in the further implementation of this process. The three conclude that the use of systolic architecture greatly reduce the cost of processing and improved performance. They argue that their design, in comparison to other designs, produces a lower cost and power (but a higher throughput). [http://delivery.acm.org/10.1145/1150000/1143566/p73-li.pdf?key1=1143566&key2=9464598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]
#Another paper, '''High-Speed Systolic Architectures for Finite Field Inversion and Division''', written in combination by Dilip V. Sarwate of University of Illinois at Urbana-Champaign and Zhiyuan Yan of Lehigh University. The two propose the use of systolic architectures for finite field inversion and division. They claim that the systolic architecture shows a marked performance when compared to other, previously used, architectures, achieving an O(m2) area-time complexity, O(m) latency and a critical path delay on two logic gates.

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:42:31Z

Mbdills: /* Systolic Architecture Currently */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
'''Systolic architecture''' sought to replace the uniprocessor architecture by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29]) and work is done in-between each heartbeat. Each processor produces a new data item after each heartbeat. Those items are then either continued on the journey toward completion, or returned to the main memory. The systolic architecture's ability to put highly specialized computation under simple, regular and highly localized communication patterns are the key to the systolic architecture.

== New Developments in Dataflow and Systolic Architectures ==

=== Dataflow Architecture Currently ===
Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the programming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow

=== Systolic Architecture Currently ===
The majority of advancements in the realm of systolic architecture focus more on the ''application'' of the architecture as opposed to ''advancement'' of the architecture itself. Several papers propose different applications for systolic architecture:

#One such paper, '''A Unified Systolic Architecture for Combined Inter and Intra Predictions in H.264/AVC Decoder''', focuses on the efficiency of video coding. Presented by three professors, Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, of the Cheng-Kung University in Taiwain, this 2000 paper presents an increase in hardware utilization and minimization of cost using a combination of inter and intra predictions. These predictions are produced via a re-programmable FIR filter. A systolic array is used in the further implementation of this process. The three conclude that the use of systolic architecture greatly reduce the cost of processing and improved performance. They argue that their design, in comparison to other designs, produces a lower cost and power (but a higher throughput). [http://delivery.acm.org/10.1145/1150000/1143566/p73-li.pdf?key1=1143566&key2=9464598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]

#Another paper, '''High-Speed Systolic Architectures for Finite Field Inversion and Division''', written in combination by Dilip V. Sarwate of University of Illinois at Urbana-Champaign and Zhiyuan Yan of Lehigh University. The two propose the use of systolic architectures for finite field inversion and division. They claim that the systolic architecture shows a marked performance when compared to other, previously used, architectures, achieving an O(m2) area-time complexity, O(m) latency and a critical path delay on two logic gates.

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:31:00Z

Mbdills: /* Systolic Architecture Currently */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
'''Systolic architecture''' sought to replace the uniprocessor architecture by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29]) and work is done in-between each heartbeat. Each processor produces a new data item after each heartbeat. Those items are then either continued on the journey toward completion, or returned to the main memory. The systolic architecture's ability to put highly specialized computation under simple, regular and highly localized communication patterns are the key to the systolic architecture.

== New Developments in Dataflow and Systolic Architectures ==

=== Dataflow Architecture Currently ===
Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the programming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow

=== Systolic Architecture Currently ===
The majority of advancements in the realm of systolic architecture focus more on the ''application'' of the architecture as opposed to ''advancement'' of the architecture itself. Several papers propose different applications for systolic architecture:

#One such paper, '''A Unified Systolic Architecture for Combined Inter and Intra Predictions in H.264/AVC Decoder''', focuses on the efficiency of video coding. Presented by three professors, Chih-Hung Li, Chih-Chieh Chen, Wei-Chi Su, of the Cheng-Kung University in Taiwain, this 2000 paper presents an increase in hardware utilization and minimization of cost using a combination of inter and intra predictions. These predictions are produced via a re-programmable FIR filter. A systolic array is used in the further implementation of this process. The three conclude that the use of systolic architecture greatly reduce the cost of processing and improved performance. They argue that their design, in comparison to other designs, produces a lower cost and power (but a higher throughput). [http://delivery.acm.org/10.1145/1150000/1143566/p73-li.pdf?key1=1143566&key2=9464598811&coll=ACM&dl=ACM&CFID=33984329&CFTOKEN=34545580]

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:17:46Z

Mbdills: /* New Developments in Dataflow and Systolic Architectures */

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:15:32Z

Mbdills: /* Dataflow & Systolic Architectures */

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T02:14:30Z

Mbdills: /* Systolic */

CSC/ECE 506 Fall 2007/wiki1 10 mt

2007-09-05T01:55:32Z

Mbdills: /* Systolic */

== Dataflow & Systolic Architectures ==

The dataflow and systolic models are two of the many possible parallel computer architectures. Unlike [http://en.wikipedia.org/wiki/Shared_memory shared address], [http://en.wikipedia.org/wiki/Message_passing message passing] and [http://en.wikipedia.org/wiki/Data_parallelism data parallel processing], the dataflow and systolic architectures were not as commonly used for parallel programming systems although they recieved a considerable amount of analysis from both private industry and academia.

===Dataflow===

Dataflow architecture is in oppostion to the [http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann] or control flow architecture which has memory, and I/O subsystem, an arithmetic unit and a control unit. The one shared memory is used for both program instructions and data with a data bus and address bus between the memory and processing unit. Because instructions and data must be fetched in sequential order, a bottleneck may occur limiting the throughput between the CPU and the memory.

The dataflow model of architecture, in contrast, is a distributive model where there is no single point of control and the execution of an instructions takes place only when the required data is available. Dataflow models are typically represented as a graph of nodes where each node in the graph is an operation to be executed when its operands become available along with the address of the subsequent nodes in the graph that need the results of the operation.

Included in the dataflow model of architecture there is also static and dynamic dataflow. The static dataflow model is characterized by the use of the memory address to specify the destination nodes that are data dependent. The dynamic model uses content-addressable memory which searches the computer memory for specific tags. Each subprogram or subgraph should be able to execute in parallel as separate instances. In the dynamic dataflow model, programs are executed by dealing with tokens which contain both data and a tag. A node is executed when incoming tokens with identical tags are present.

===Systolic===
Systolic architecture sought to replace a uniprocessor by stringing together a system of processing elements in arrays, known as '''systolic arrays'''. Their initial birth came from the bottleneck that can occur between a Central Processing Unit (CPU) and a memory request to the main-memory. A uniprocessor must sit and wait for the result from main memory to return or request another data item. In a systolic architecture, the data moves through a system via regular, timed "heartbeats" (the term systolic actually refers to the systolic contraction of heartbeats [http://en.wikipedia.org/wiki/Systole_%28medicine%29].

The reasoning behind this architecture centres around the bottleneck between a CPU and its main-memory. Having issued a memory request, a processor has to wait a short time for the memory system to deliver the data item. Once they have a piece of data uniprocessors perform one calculation with it and then either return the result to main-memory or request another data item. Systolic arrays, however, use that data item to perform a calculation at every processor in the chain before returning a it back to main-memory, see figure 2.4-1. The memory access penalty is not paid for every instruction, and so, systolic arrays are much faster than uniprocessors.
On every beat of a global system clock, each processor passes its results to the next processor in the chain, and receives another data item from the previous processor in the chain. Each processor produces a result every clock cycle, and so complex multi-cycle instructions are not implemented. Systolic arrays are said to be 'lock-stepped' or synchronous. There is no master controller, as found with array processors, and so control is effectively distributed across the network.
The periodic pumping of data around the systolic array is the feature by which systolic arrays get their name. A systole is the name given to a contraction of the heart. When the heart contracts blood moves along the vanes and arteries coming to rest at the end of the contraction. During the brief pause between beats the blood does its work - distributing oxygen and nutrients. When the work is being done the network of vanes and arteries is still. This is followed by another contraction and the whole cycle starts again. Note that when the network is active no 'work' is being done and vice-versa.

Systolic architectures are designed by using linear
mapping techniques on regular dependence graphs (DG).
• Regular Dependence Graph : The presence of an edge in
a certain direction at any node in the DG represents
presence of an edge in the same direction at all nodes
in the DG.
• DG corresponds to space representation à no time
instance is assigned to any computation Þ t=0.
• Systolic architectures have a space-time
representation where each node is mapped to a certain
processing element(PE) and is scheduled at a particular
time instance.
• Systolic design methodology maps an N-dimensional DG
to a lower dimensional systolic architecture.
• Mapping of N-dimensional DG to (N-1) dimensional
systolic array is considered.

== New Developments in Dataflow and Systolic Architectures ==

Since the 1990's, little advancement has been made in the field of dataflow architecture. Dataflow was primarily abandoned due to several problems.
#The dynamic dataflow model requires some sort of '''associative memory''' to store the tokens waiting to be matched. Unfortunately, even in moderate size programs the required memory needed for storage tends to be large and therefore not very cost efficient.
#Dataflow programs typically made use of multiple threads since parallel functions and loops were frequently used in the progamming. Therefore, if there wasn't enough of a workload for multiple threads, '''single threaded execution''' of a program provided poor performance.
#The dataflow model failed to take advantage of locality such as the usage of '''local registers and cache'''. Since all information for the tokens (data and tags) moves through the network, it is difficult to transfer all that information in a timely efficient manner over a large parallel system.

Regardless of the problems that the dataflow model of machine design encountered, today ''out of order execution'', which is a form of restricted dataflow is one of the most successful models of microprocessor design. AMD and Intel both implemented an architecture where after decoding into RISC instructions instructions are placed in a central pool where they are allowed to execute in the order which is best matched to the current resources available.

Explicit token store approach(monsoon)

Enhancing data flow with control flow