MARYLAND: CHAOS Library

Runtime library

For parallelizing Fortran and C programs with irregular data access patterns

Target Systems

Any distributed memory system that supports message passing or distributed shared memory
(currently implemented on Intel iPSC/860 and Paragon, IBM SP1/2, TMC CM5, Cray T3D, Stanford DASH, network of workstations via PVM)

Implementation

C + message passing (or shared memory puts and gets)

Functionality

The Chaos library is a set of software primitives that are designed to efficiently handle irregular problems on distributed memory systems. It is a superset of the Parti library. These primitives have been designed to ease the implementation of computational problems on parallel architecture machines by relieving users of low-level machine specific issues. The design philosophy has been to leave the original (sequential) source codes essentially unaltered, with the exception of the introduction of various calls to the Chaos primitives which are embedded in the codes at the appropriate locations. These primitives allow the distribution and retrieval of data from the numerous processor local memories.

In distributed memory systems, arrays can be partitioned among local memories of processors. These partitioned arrays are called distributed arrays . Users can either partition arrays regularly, e.g. in block or cyclic, or specify irregular mapping of arrays to processors. The distributions of data arrays have significant impact on performance because they determine the patterns of communication between processors. It is frequently advantageous to partition arrays in appropriate irregular distributions. Chaos provides primitives to map arrays onto processors and uses translation tables to describe the distributions of distributed arrays.

Chaos also provides a set of primitives that carry out optimizations at runtime to reduce both the number of messages and the volume of interprocessor communication. The runtime primitives examine the data accesses made by each processor, calculate what off-processor data have to be fetched and where the data will be stored, and then generate communication schedules to specify the patterns of communication for exchanging data. Once the communication schedules are ready, efficient gather and scatter routines can be used to exchange data between processors.

Library Interface

The library provides routines for using the translation tables for address translation and for interprocessor communication (gather/scatter) using communication schedules.

Distributed Array Descriptors

The translation table uses several data structures that effectively serve as a descriptor. Their definition in C is as follows:

typedef struct DsChunk {
  int *Proc,*Offset;
} PAGE, *PAGEPTR;

/* 
 * structure for distributed translation table 
 */
typedef struct DsTable {
  int  pageSize;       /* Size of a single page in the translation table */ 
  int  LastBlock;      /* Remainder in the block distribution of pages */
  int  Replication;    /* Number of blocks replicated in the processor */
  int  numPages;       /* Total number of pages in the table */
  int *Loffset;        /* Buffer space for the storage of offsets */
  int *Lproc;          /* Buffer space for the storage of procs */
  int  nMyIndices;     /* size of portion of translation table allocated to my indices */
  float repFactor;     /* Replication factor */
  PAGEPTR *pageTable;  /* Pointer to the chunks stored in the table */
} DSTABLE, *DSTABLEPTR;

/*
 * Structure for regular translation, which does not need enumeration -
   this is only for simple regular distributions in CHAOS
 */
typedef struct regTable {
  int   dist_type ;
  int   data_size ;
  int   block_size ;
}  REG_TABLE, *REGTABLEPTR ;

/*
 * Structure for User Translation Table
 */
typedef struct trans_table {
  int             type;
  DSTABLE        *tabptr; 
  REG_TABLE      *regptr;
} TTABLE, *TTABLEPTR;

Status

Completed.

Availability

The library is available at Maryland via ftp ; no restrictions.

Reusability

Implementations have been done for both distributed memory and distributed shared memory systems, using much of the same code.

Documentation

The documentation is available as part of the library distribution