CSC/ECE 506 Fall 2007/wiki 11 e4

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)

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