Up: Issues in Irregular Computations
Previous: Reducing communication costs
CHAOS Library
Solving irregular problems on
distributed memory machines that was introduced in CHAOS
runtime support usually involves
six major phases. The first four phases concern mapping data
and computations onto processors. The next two steps concern analyzing
data access patterns in a loop and generating optimized communication
calls. A brief description of these phases follows:
-
Data distribution phase
calculates how data arrays
are to be
partitioned by making use of partitioners
provided by CHAOS or by the user. CHAOS supports a number of parallel
partitioners that return
an irregular assignment of array elements to processors, which is stored
as a CHAOS construct called the translation table.
A translation table is
a globally accessible data structure which lists the home processor and
offset address of each data array element.
During investigation on various partitioning methods it was discovered
that partitioners provided by CHAOS are not fully parallel and
thus not very efficient. Therefore, it was crucial to
design algorithms that not only satisfy mentioned requirements,
but also support partitioning of out-of-core data. One of the major goals
of the authors of the LIP library was to design and implement data distribution
functions
and augment them with an inspector phase.
The idea of translation table taken from CHAOS served as a basis
for that purpose.
-
Data remapping phase
remaps data arrays from the current
distribution to the newly calculated irregular distribution. The CHAOS
procedure remap is used to generate an
optimized communication schedule for moving data array elements from their
original distribution to the new distribution. Other CHAOS procedures,
gather, scatter, and scatter.append, use the
communication schedule to
perform data movement.
This idea was extended by the authors of the LIP library to support
out-of-core remapping.
- Loop iteration partitioning
phase
determines how loop
iterations should be partitioned across
processors. CHAOS uses the almost-owner-computes rule to assign
loop iterations to processors and also supports the owner-computes
rule.
-
Remapping loop iterations phase
is similar to data remapping phase. Elements of indirect
arrays are remapped
to conform with the loop iteration partitioning.
- Inspector phase
carries out the preprocessing needed
for communication optimizations and index translation.
The general concept that was retained in the library
was the idea of a communication schedule that serves as a description
of the communication pattern which should take place between
computing nodes .
- Executor phase
carry
out the computation and communication. Communication is carried out by
CHAOS data transportation primitives which use communication schedules
constructed in Phase
Created by Katarzyna Zając