Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-29T02:14:00Z

Sbhanna: /* MSIMD applications */

== MSIMD applications ==

Multiple-SIMD (MSIMD) architectures expand on SIMD architecture abilities, and alleviate some of their weaknesses. Since a single array control unit controls all processing elements in a SIMD architecture, processing elements (PE) are often under-utilized when a process comes in, but does not require the use of all the PEs. MSIMD architectures are formed with clusters of virtual SIMD machines, so there are multiple array control units to control the PEs. This allows other programs and users to utilize idle PEs.

Below are some examples, based on published papers, of research involving MSIMD architectures and the types of applications for which they have been found useful.

=== The GPA Machine ===

The GPA machine has shown to be beneficial to algorithms based on dynamic data structures and fragmented partitions. These algorithms will show substantial speedup on this architecture. Multi-user operating system development will also benefit from this architecture. A main benefit of the GPA machine architecture is the ability to allocate resources based on availability and need.

=== The Warwick Pyramid Machine ===

The Warwick Pyramid Machine (WPM) allows for the faster tracking of features within images. Each SIMD cluster within the WPM works on a region of the image. Iconic data is processed in the MSIMD array.

The WPM has been used for image analysis techniques such as: motion estimation, segmentation, object detection, edge extraction and enhancement, feature extraction and graphics, and Hough transforms. The Hough transform is used to detect specific shapes in images. Most commonly, it is used to detect straight lines and circles, which might signify a man made object in an image. These transforms cost a significant amount of time and resources, though straight line and circle detection takes fewer parameters than most other shapes. Programming a Hierarchical Hough Transform (which is more thorough and improves upon the original Hough Transform) is more complex on a M-SIMD architecture, but the relatively small amount of extra complexity pays off in enhanced performance and increased programming capability. Advantages include having adjacent clusters work on seperate instruction streams, local associativity, and improved vertical communication bandwidth.

=== Artificial Neural Networks ===

In this architecture, Processing Elements are set up locally as SIMD vector processors with local ring communication. This setup is particularly good for recognition and optimization programs.

== References ==
[http://carbon.cudenver.edu/csprojects/CSC5809S01/Simd/archi.html]Alaghband, Gita. "SIMD Architectures." University of Colorado at Denver.

[http://www.lib.ncsu.edu:2178/iel2/294/2914/00089460.pdf?tp=&arnumber=89460&isnumber=2914]The GPA Machine: A Generally Partitionable MSIMD Architectures

[http://www.lib.ncsu.edu:2178/iel3/1599/4340/00168054.pdf?tp=&arnumber=168054&isnumber=4340]A MSIMD Architecture for Feature Tracking

[http://www.lib.ncsu.edu:2178/iel2/301/3418/00119413.pdf?tp=&arnumber=119413&isnumber=3418]Performance Evaluation of the Hierarchical Hough Transform on an Associative M-SIMD Architecture

[http://www.lib.ncsu.edu:2178/iel2/665/6720/00271809.pdf?tp=&arnumber=271809&isnumber=6720] A Massively Parallel, Multiple-SIMD Architecture for Implementing Artificial Neural Networks

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-24T18:54:52Z

Sbhanna:

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-24T02:42:48Z

Sbhanna:

Wiki: MSIMD applications MSIMD architectures have garnered quite a bit of contention recently. Read a few papers on these architectures and write a survey of applications for which they would be suitable. If possible, talk about the steps in parallelizing these applications (decomposition, assignment, orchestration, and mapping).

[http://www.lib.ncsu.edu:2178/iel2/294/2914/00089460.pdf?tp=&arnumber=89460&isnumber=2914]The GPA Machine: A Generally Partitionable MSIMD Architectures

The GPA machine has shown to be beneficial to algorithms based on dynamic data structures and fragmented partitions. These algorithms will show substatial speedup on this architecture. Multi-user operating system development will also benefit from this architecture. A main benefit of the GPA machine architecture is the ability to allocate resources based on availability and need.

[http://www.lib.ncsu.edu:2178/iel3/1599/4340/00168054.pdf?tp=&arnumber=168054&isnumber=4340]A MSIMD Architecture for Feature Tracking
[http://www.lib.ncsu.edu:2178/iel2/301/3418/00119413.pdf?tp=&arnumber=119413&isnumber=3418]Performance Evaluation of the Hierarchical Hough Transform on an associative M-SIMD architecture

The Warwick Pyramid Machine (WPM) allows for the faster tracking of features within images. Each SIMD cluster within the WPM works on a region of the image. Iconic data is processed in the MSIMD array.

The WPM has been used for image analysis techniques such as: motion estimation, segmentation, object detection, edge extraction and enhancement, feature extraction and graphics, and Hough transforms. The Hough transform is used to detect specific shapes in images. Most commonly, it is used to detect straight lines and circles, which might signify a man made object in an image. These transforms cost a significant amount of time and resources, though straight line and circle detection takes fewer parameters than most other shapes. Programming a Hierarchical Hough Transform (which is more thorough and improves upon the original Hough Transform) is more complex on a M-SIMD architecture, but the relatively small amount of extra complexity pays off in enhanced performance and increased programming capability. Advantages include having adjacent clusters work on seperate instruction streams, local associativity, and improved vertical communication bandwidth.

[http://www.lib.ncsu.edu:2178/iel2/665/6720/00271809.pdf?tp=&arnumber=271809&isnumber=6720] A Massively Parallel, Multiple-SIMD Architecture for Implementing Artificial Neural Networks

In this architecture, Processing Elements are set up locally as SIMD vector processors with local ring communication. This setup is particularly good for recognition and optimization programs.

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-24T02:18:12Z

Sbhanna:

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-24T02:17:54Z

Sbhanna:

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-23T19:03:16Z

Sbhanna:

CSC/ECE 506 Fall 2007/wiki2 6 sbh

2007-09-23T02:47:21Z

Sbhanna:

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-11T02:03:00Z

Sbhanna: /* Ordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.

Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model, and exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.

Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependency, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

The programming model examples above employ different reordering techniques for processes and data. These techniques are listed and explained below.

* Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

* Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

* Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

* DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS). [3] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

== Synchronization ==

Synchronization types have expanded to further facilitate reordering over the past several years. These methods now include:

* Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

* Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

* Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

There is a small collection of tools that are commonly used for synchronization in parallel architectures. These include:

* Locks - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

* Semaphores - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

* Critical regions - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

* Barriers - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

* Atomic operations - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.
New mechanisms, like that of a monotonic counter (see references), only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. The goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

== References: ==

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf, 2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

4. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

5. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

6. Apple Threading Libraries, http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

== External Links: ==

* [http://www.intel.com/cd/ids/developer/asmo-na/eng/segments/hpc/95223.htm?page=12 Trends in Distributed Computing]
* [http://www.ddj.com/hpc-high-performance-computing/199100439;jsessionid=4WBRUFR1BVGECQSNDLPCKH0CJUNN2JVN DDJ: What's different about multiprocessor programming]
* [http://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 Wikipedia: Synchronization]
* [http://users.actcom.co.il/~choo/lupg/tutorials/parallel-programming-theory/parallel-programming-theory.html Parallel Programming - Basic Theory for the unwary]

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-11T02:02:26Z

Sbhanna: /* Ordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.

Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model, and exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.

Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependency, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

The programming model examples above employ different reordering techniques for processes and data. These techniques are listed and explained below.

* Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

* Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

* Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

* DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS) [3] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

== Synchronization ==

Synchronization types have expanded to further facilitate reordering over the past several years. These methods now include:

* Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

* Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

* Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

There is a small collection of tools that are commonly used for synchronization in parallel architectures. These include:

* Locks - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

* Semaphores - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

* Critical regions - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

* Barriers - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

* Atomic operations - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.
New mechanisms, like that of a monotonic counter (see references), only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. The goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

== References: ==

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf, 2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

4. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

5. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

6. Apple Threading Libraries, http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

== External Links: ==

* [http://www.intel.com/cd/ids/developer/asmo-na/eng/segments/hpc/95223.htm?page=12 Trends in Distributed Computing]
* [http://www.ddj.com/hpc-high-performance-computing/199100439;jsessionid=4WBRUFR1BVGECQSNDLPCKH0CJUNN2JVN DDJ: What's different about multiprocessor programming]
* [http://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 Wikipedia: Synchronization]
* [http://users.actcom.co.il/~choo/lupg/tutorials/parallel-programming-theory/parallel-programming-theory.html Parallel Programming - Basic Theory for the unwary]

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-11T01:47:17Z

Sbhanna: /* Synchronization */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.

Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model, and exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.

Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependency, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

== Synchronization ==

Synchronization types have expanded to further facilitate reordering over the past several years. These methods now include:

* Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

* Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

* Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

There is a small collection of tools that are commonly used for synchronization in parallel architectures. These include:

* Locks - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

* Semaphores - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

* Critical regions - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

* Barriers - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

* Atomic operations - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.
New mechanisms, like that of a monotonic counter (see references), only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. The goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

== References: ==

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf, 2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

4. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

5. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

6. Apple Threading Libraries, http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

== External Links: ==

* [http://www.intel.com/cd/ids/developer/asmo-na/eng/segments/hpc/95223.htm?page=12 Trends in Distributed Computing]
* [http://www.ddj.com/hpc-high-performance-computing/199100439;jsessionid=4WBRUFR1BVGECQSNDLPCKH0CJUNN2JVN DDJ: What's different about multiprocessor programming]
* [http://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 Wikipedia: Synchronization]
* [http://users.actcom.co.il/~choo/lupg/tutorials/parallel-programming-theory/parallel-programming-theory.html Parallel Programming - Basic Theory for the unwary]

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T16:54:03Z

Sbhanna: /* '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.

Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model, and exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.

Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependency, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

== Synchronization ==

Synchronization types have expanded to further facilitate reordering over the past several years. These methods now include:

* Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

* Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

* Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

* Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

* Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

* Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

* DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS) [3] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

There is a small collection of tools that are commonly used for synchronization in parallel architectures. These include:

* Locks - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

* Semaphores - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

* Critical regions - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

* Barriers - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

* Atomic operations - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.
New mechanisms, like that of a monotonic counter (see references), only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. The goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

== References: ==

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf, 2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

4. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

5. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

6. Apple Threading Libraries, http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T16:53:46Z

Sbhanna: /* Ordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.

Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model, and exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.

Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependency, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

== Synchronization ==

Synchronization types have expanded to further facilitate reordering over the past several years. These methods now include:

* Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

* Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

* Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

* Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

* Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

* Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

* DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS) [3] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

There is a small collection of tools that are commonly used for synchronization in parallel architectures. These include:

* Locks - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

* Semaphores - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

* Critical regions - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

* Barriers - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

* Atomic operations - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.
New mechanisms, like that of a monotonic counter (see references), only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. The goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

== References: ==

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf, 2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

4. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

5. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

6. Apple Threading Libraries, http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T16:53:30Z

Sbhanna: /* Synchronization */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.
Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model, and exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.
Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependency, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

== Synchronization ==

Synchronization types have expanded to further facilitate reordering over the past several years. These methods now include:

* Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

* Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

* Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

* Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

* Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

* Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

* DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS) [3] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

There is a small collection of tools that are commonly used for synchronization in parallel architectures. These include:

* Locks - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

* Semaphores - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

* Critical regions - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

* Barriers - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

* Atomic operations - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.
New mechanisms, like that of a monotonic counter (see references), only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. The goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

== References: ==

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf, 2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

4. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

5. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

6. Apple Threading Libraries, http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T16:52:12Z

Sbhanna: /* Ordering */

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T16:42:02Z

Sbhanna: /* Reordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== Ordering ==

In parallel programming models, ordering is key to coordinating the activity of all threads. Ordering will ensure that dependencies are maintained and that specified threads remain synchronized via explicit synchronization operations.

Parallel Programming models have developed to take advantage of shared memory multiprocessors and distributed memory systems. Nanothreads Programming Model (NPM) is one such programming model that exploits multiple levels of loop and functional parallelism. This model results in a runtime environment that has dynamic program adaptability, allowing the program to adjust the granularity of the generated parallelism to the available resources. The main ordering and scheduling objective of this model is that application scheduling, at the user level, and virtual process scheduling, at the kernel level, be tightly coordinated. The result is high performance.

Other programming models combine loop directives and message passing to maintain order and facilitate reordering. An example of a program using this method is the GeoFEM on the Earth Simulator Supercomputer in Japan. This is part of a parallel finite-element platform for solid earth simulation being studied. A special reordering technique was used to create parallel iterative solvers with localized preconditioning. This allows GeoFEM to attain concurrent local operations, no global dependancy, continuous memory access, and sufficiently long innermost loops to take advantage of the vector processors on Earth Simulator.

Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS)
[3] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

'''References:'''

1. Hadjidoukas, P. et all, Integrating MPI and the Nanothreads Programming Model, http://citeseer.ist.psu.edu/cache/papers/cs/27581/http:zSzzSzwww.hpclab.ceid.upatras.grzSzpgroupzSzmemberszSzpehzSzpubszSzpdp02.pdf/hadjidoukas02integrating.pdf,
2002.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

3. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

== Synchronization ==

There is a small collection of tools that are commonly used for synchronization in parallel architectures.
These include:

''Locks'' - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

''Semaphores'' - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

''Critical regions" - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

''Barriers'' - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

''Atomic operations'' - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.

This list is short, has not changed much in the recent past and is unlikely to change any time soon. Any new mechanisms like that of a monotonic counter(see references) only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. These goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

''References''

1. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

2. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

3. Apple Threading Libraries,
http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T03:21:58Z

Sbhanna: /* Reordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== Reordering ==

Reordering strategies include:

Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS)
[1] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

'''References:'''

1. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

== Synchronization ==

There is a small collection of tools that are commonly used for synchronization in parallel architectures.
These include:

''Locks'' - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

''Semaphores'' - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

''Critical regions" - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

''Barriers'' - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

''Atomic operations'' - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.

This list is short, has not changed much in the recent past and is unlikely to change any time soon. Any new mechanisms like that of a monotonic counter(see references) only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. These goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

''References''

1. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

2. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

3. Apple Threading Libraries,
http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T03:21:12Z

Sbhanna: /* Reordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== Reordering ==

Reordering strategies in the book include:

Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS)
[1] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

'''References:'''

1. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.

2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

== Synchronization ==

There is a small collection of tools that are commonly used for synchronization in parallel architectures.
These include:

''Locks'' - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

''Semaphores'' - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

''Critical regions" - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

''Barriers'' - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

''Atomic operations'' - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.

This list is short, has not changed much in the recent past and is unlikely to change any time soon. Any new mechanisms like that of a monotonic counter(see references) only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. These goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

''References''

1. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

2. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

3. Apple Threading Libraries,
http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-10T03:20:49Z

Sbhanna: /* Reordering */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== Reordering ==

Reordering strategies in the book include:

Implicit ordering – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

Mutual Exclusion – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

Automatic Mutual Exclusion - In a simplified model, Automatic Mutual Exclusion consists of asynchronous method calls and guarantees that the program execution is essentially executing each of the calls in some serialized order. It achieves concurrency because the async construct is similar to forking a thread in thread-like systems. The system attempts to execute the method calls concurrently and is subject to strategies that prevent excessive transaction aborts. In more complicated models, the asynchronous methods may be fragmented, using a Yield function to synchronize the fragments prior to blocks.

Events – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

Explicit Reordering – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

Reverse Cuthill-McKee (RCM) Reordering - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

DJDS reordering- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS)
[1] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

'''References:'''

1. Nakajima, K. et al, Parallel Iterative Solvers for Finite-Element Methods using a Hybrid Programming Model on SMP Cluster Architectures, http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf, March 2003.
2. Isard, M. et al, Automatic Mutual Exclusion, http://research.microsoft.com/users/misard/papers/hotos2007.pdf, 2007.

== Synchronization ==

There is a small collection of tools that are commonly used for synchronization in parallel architectures.
These include:

''Locks'' - Locks limit access to shared resources by identifying each resource as being available or unavailable. Successful acquisition of a lock means that your code now has the right to use the protected resource.

''Semaphores'' - A semaphore is a flag that signals the presence of a specific condition in your program. Semaphores offer a way to synchronize the execution of code.

''Critical regions" - A critical region is a section of code that can be executed by only one thread at a time. You might designate a block of code as a critical region to prevent modification of a common data structure or to prevent race conditions as two threads execute the same code.

''Barriers'' - Deadlock occurs whenever a thread is blocked waiting on a resource of another thread that will never become available.

''Atomic operations'' - The x86 bit test and set is an example of Instruction Set Architecture support for synchronization. They simplify synchronization by eliminating the need to locks altogether.

This list is short, has not changed much in the recent past and is unlikely to change any time soon. Any new mechanisms like that of a monotonic counter(see references) only build on existing process synchronization constructs. Most of the effort and research seems to be going in the way of building threading libraries that will allow software developers to build scalable applications that can optimally utilize massively parallel architectures. These goal of these libraries is to reduce the amount of time spent on dealing with the low-level without compromising on the performance of the applications. Intel, for example, has gone public with an open source threading building block library with promises that it will become the STL(Standard Template Library) for multi-threaded applications. These libraries allow rapid application development of new applications while hiding the low-level thread synchronization mechanics. A few years ago, distributed computing was the talk of the town but with the movement of PC architecture toward multiple cores per processor, these threading libraries will have a big role to play in getting the best performance out of these new architectures.

''References''

1. John Thornley, K. Mani Chandy, "Monotonic Counters: A New Mechanism for Thread Synchronization," ipdps, p. 573, 14th International Parallel and Distributed Processing Symposium (IPDPS'00), 2000

2. Intel Threading Building Blocks 2.0, http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm?cid=cim:ggl|spd_us_tbb|k7A3E|s

3. Apple Threading Libraries,
http://developer.apple.com/documentation/Cocoa/Conceptual/Multithreading/articles/ThreadLocking.html

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-05T16:16:05Z

Sbhanna: /* How have reordering strategies evolved to accommodate larger multicomputers? */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== How have reordering strategies evolved to accommodate larger multicomputers? ==

Reordering strategies in the book include:

''Implicit ordering'' – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

''Mutual Exclusion'' – Certain operations on certain data are performed by only one thread/process at a time. The processes are sequential, but without a specific order or events.

''Events'' – Specific events allow other processes to start. An event may trigger a single process or a group of processes.

In more recent years, advances have been made to accommodate larger multicomputers. These advances include developments in reordering both processes and the data being used by the processes.

'''Process Ordering'''

''Explicit Reordering'' – Programs avoid overhead by explicitly assigning and ordering processes to take advantage of data locality. This approach works well when there is complicated data dependency.

'''Data Reordering''':

''Reverse Cuthill-McKee (RCM) Reordering'' - RCM is a typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

''DJDS reordering''- Reorders data to produce arrays of coefficients with continuous memory access. Vector programming is made more efficient by providing sufficient length for innermost loops. Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS)

[http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf] provides a good explanation and comparison of RCM/PDJDS re-ordering techniques.

'''Have new kinds of synchronization operations been developed?'''

'''I doubt that other topics covered in these sections have changed much, but do check.'''

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-05T02:28:14Z

Sbhanna: /* How have reordering strategies evolved to accommodate larger multicomputers? */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

== How have reordering strategies evolved to accommodate larger multicomputers? ==

Strategies in the book include:

''Implicit ordering'' – Operations in a thread are in program order. When multiple threads access the same data, there is no guarantee that they will not reach the data too late/too soon.

''Mutual Exclusion'' – Certain operations on certain data are performed by only one thread/process at a time. Sequential without the specific order or events.

''Events'' – Specific events allow other processes to start. “Events may be point to point, involving a pair of processes, or they may be global,” involving all or a group of processes.

Updated information

'''Process Ordering'''

''Explicit Reordering'' – Avoid overhead by explicitly assigning and ordering to take advantage of data locality. Complicated Data Dependency

'''Data Reordering''':

''Reverse Cuthill-McKee (RCM) Reordering'' - Typical level set reordering method. Elements of a level set are traversed from the nodes of the highest degree to those of the lowest degree, according to dependency relationships. Degree refers to the number of nodes connected to each node.

''Multicoloring reordering'' –

''DJDS reordering''- “For efficient vector processing, producing 1D arrays of coefficients with continuous memory access and sufficient length of innermost loops.”
Descending-order jagged diagonal storage (DJDS) involves permuting rows into an order of decreasing number of non-zeros. Can be modified to split and permute arrays to be distributed across an SMP node (parallel DJDS or PDJDS)

[http://geofem.tokyo.rist.or.jp/report_common/GeoFEM03_003.pdf] provides a good explanation and comparison of RCM/CM/PDJDS re-ordering techniques.

'''Have new kinds of synchronization operations been developed?'''

'''I doubt that other topics covered in these sections have changed much, but do check.'''

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-05T02:27:48Z

Sbhanna: /* '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' */

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-04T02:18:13Z

Sbhanna: /* '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

'''How have reordering strategies evolved to accommodate larger multicomputers?'''

Strategies in the book include:

''Implicit ordering''

''Mutual Exclusion''

''Events''

*Will add more detail on Tues*

'''Have new kinds of synchronization operations been developed?'''

'''I doubt that other topics covered in these sections have changed much, but do check.'''

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-04T01:58:44Z

Sbhanna: /* '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' */

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

'''How have reordering strategies evolved to accommodate larger multicomputers?'''

Strategies in the book include:
Implicit ordering
Mutual Exclusion
Events

'''Have new kinds of synchronization operations been developed?'''

'''I doubt that other topics covered in these sections have changed much, but do check.'''

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-04T01:27:15Z

Sbhanna:

== '''Sections 1.3.1 and 1.3.2: Communication and programming model.''' ==

'''How have reordering strategies evolved to accommodate larger multicomputers?'''

'''Have new kinds of synchronization operations been developed?'''

'''I doubt that other topics covered in these sections have changed much, but do check.'''

CSC/ECE 506 Fall 2007/wiki 11 e4

2007-09-03T18:02:58Z

Sbhanna:

Something to start with