West Home

West Team --- IDOLE
A Former Project of the West Team

IDOLE: Irregular structures in data-parallel languages

Many scientific computation algorithms require the use of irregular data structures (irregular meshes, sparse matrix). Such structures are not yet handled by standard data-parallel languages which mostly consider regular data sets. IDOLE (Irregular Data-parallel Object LanguagE) is a C++ extension, specially designed to manage irregular data structures. It implements the HELP model: based on a referential semantics, it allows programmers to manipulate Data-Parallel Objects (aggregates of elements) on collections (virtual machines defined by a set of virtual processors and interprocessor connections). Using object language concepts, methods are associated to collections and DPOs. Collections are configured in the program and can be modified at runtime. Such irregular dynamic collections fit strongly the requirements of scientific algorithms. Moreover, DPOs are also dynamic. To embody irregular and sparse computations, they can be defined on a whole collection as well as on a subset of a collection.

Semantics à la HELP

Collections, considered as a set of interconnected processor, can be seen as referentials in which DPOs are declared. Unlike the languages à la C*, DPOs are not necessarily defined on the whole referential, but can be defined on a subset of virtual processors (See Fig.1). The elements of DPOs defined in one point of the referential, are allocated on the same virtual processor. Point to point interaction between elements of two different DPOs may only occur if the DPOs are defined on the point.

 
Figure 1: Collection and DPO

The IDOLE language

IDOLE is a C++ extension. The main new features are collection classes and DPOs.

Collection classes

In accordance with the HELP model, collections are sets of virtual processors. We have defined two basic collection types: grid (nD grid of processors) and bag (unstructured set of processors) with which programmers can build their own collections i.e., their own machines. Programmers can specify the number of processors and their interconnections. Collections can be declared dynamic i.e., collection size and processor connections can change at runtime.

At the language level, collections are instances of collection classes. The definition of a collection class consists in defining collection attributes and collection methods:

• attributes are internal variables of each collection, instance of the collection class;
• methods are functions that will be executed on the collections.

Data-Parallel Objects

DPOs are aggregates of elements defined through a collection, a shape, and a type, which is a standard C++ class. A shape represents the allocation domain of a DPO. Shapes are built by the programmer using special methods: adding or suppressing sets of processors, or building union or intersection with already built shapes. By default, DPOs are allocated on the whole collection. As collections, DPOs can be dynamic i.e., their shapes can be modified at runtime. Invoking a method of the type of a DPO, will execute this method through all the active elements of the DPO. Methods are defined to alter the shape of a DPO, or to operate on elements using a global view of the DPO (e.g., scan, prefix).

Irregular computations

Irregular computations can be performed in two ways:

• using an irregular set of processors. For instance, to describe an irregular mesh, programmer can define a collection whose processors are each a node of the mesh (See Fig.2-a);
• using objects defined on a part of a virtual machine. For instance, programmer can define a shape describing the edges of a grid (See Fig.2-b).

These two levels can be mixed inside the same collection.

 
Figure 2: Two types of irregular structures

An irregular computation archetype is the adaptative mesh algorithm. Each node of the mesh is represented by a virtual processor and the nodes concentration is not the same on the whole mesh. Moreover, the adaptative mesh technique relies on refinement of the mesh to concentrate points where error contributions are large. Using those irregular meshes, the number of points needed for the computation is reduced to accurately capture regions where a high calculus precision is required. This technique can be expressed in IDOLE by creating new processors on the fly and modifying interprocessor connections.

Irregular DPOs can also be easily defined, using the shape concept. Shapes in IDOLE have neither to be rectangular regions of collections nor be defined on connected sets of processors. With irregular DPOs, programmers can execute instructions on only a part of a collection.

Publications and Documentation

An IDOLE Project Overview, 1995.

IDOLE Presentation at SuperComputing'95.

Supporting Irregular and Dynamic Computations in Data-Parallel Languages, LNCS Tutorial Serie, volume 1132, 1996.

Irregular Data-parallel Objects in C++, Vecpar 96, LNCS 1215, 1996.

Copyright © 2000-2008 LIFL.

Mar 17 2000, 16:34.