CSC/ECE 506 Fall 2007/wiki 11 e4

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)

[1] 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.