SEINE: high performance SharEd INformation-spacE
Overview
People
Publication
River SEINE
There are several main programming models that service parallel programming, including Shared-Memory model, Message-Passing model, Data-Parallel model and Implicit Model. Among them, Shared-Memory and Message-Passing are the two most widely adopted models in Scientific Computing/High Performance Computing community. The two models are different, each having its own advantage and disadvantage. However when problem size/complexity increases, which is a definite trend for scientific applications, both models fail in some way: As problem size increases, requirement for more computing power increases as well, which is a problem for Shared-Memory model due to the limited scalability of current Shared-Memory machines; As problem complexity increases, requirement for more powerful and dynamic communication mechanism also increases, which cannot be met in a pure Message-Passing model.
Tuple space model, proposed in the 1980’s, provides a very flexible and powerful mechanism for supporting extremely dynamic communication and coordination patterns, which we want to adopt to get out of the dilemma described above. As can be seen, Tuple space presents a powerful mechanism for setting up dynamic communication/coordination patterns. However, similar to the problem of Shared-Memory model, scalable implementation of Tuple space is still a challenge.
The idea is to base on Tuple space
concept, provide a model meant for scientific applications, and enable scalable
implementation of such model. Scalable implementation
of a general Tuple space is an unsolved problem. However, we realized the
model's scalability by taking general properties of scientific applications into
its design. These properties are: (a) formulations of most scientific and
engineering applications are based on a geometric multi-dimension domain (e.g.,
a grid or a mesh) and (b) interactions in these applications are typically
between entities that are geometrically close in this domain (e.g., neighboring
cells, nodes or elements).
Introduction
While large-scale parallel/distributed simulations are rapidly becoming critical research modalities in academia and industry, their efficient and scalable parallel implementation presents many challenges. A key challenge is the dynamic and complex communication and coordination patterns required by these applications. These communication/coordination patterns depend on state of the phenomenon being modeled and are determined by the specific numerical formulation, and domain decomposition and/or sub-domain refinement algorithms used, and are known only at runtime. To solve above problems, we propose a geometry-based dynamic shared-space interaction framework for scientific applications.
A Driving Application
We use parallel multiblock oil-reservoir simulation as the driving application to motivate the interaction framework. In these simulations, the oil reservoir is discretized as a series of blocks and interfaces between blocks. The target domain consists of a coupled system of highly nonlinear transient partial differential equations. Its geometrical and geological features induce a multi-block decomposition so that each block is discretized by cell-centered finite differences on logically rectangular grids. Flux matching conditions are imposed on the interfaces and a non-overlapping domain decomposition algorithm is exploited so that solving the interface problem only requires in-block solves and an exchange of interface values between neighboring blocks. We refer to the face sharing described above as neighbor-neighbor relationship. Figure 1 presents a 3-D view of the total problem domain and a 2-D view of decomposed domains in a 2-dimensional coordinate system. This application presents two challenges: first, when the decomposed sub-blocks are distributed across nodes in the system, locating the processor assigned to a neighboring block is non trivial, specially dynamic load-balancing is used; second, communication between blocks as a main communication requirement in this particular environment is highly localized, integrated on interfaces of neighboring blocks.
Figure 1. 3-D view of overall problem domain and 2-D view of decomposed domains with interface sharing
The Concept
We propose a dynamic geometry-based shared space model. The model adopts Tuple space as its basic concept. Communication entities interact with each other by sharing objects in the virtual shared space. This model supports for dynamic and flexible interaction/coordination while enabling scalable realizations and is based on the geometric nature of the computational domain and the local nature of communications, which are typical of most scientific applications. The geometric nature is due to the observation that formulations of scientific applications are based on a geometric descretization of the physical domain. Communication locality is due to the observation that interaction and coordination are defined by problem domains, and are typically local to sub regions of this domain. As a result, operations on an object shared in a geometric-based dynamic shared space only require communication within the space. Coordinates from the geometric domain define the geometry-based associative semantics for accessing the spaces. The shared space is dynamic in the sense that it is created/destroyed at runtime and is constructed on top of a changing set of nodes according to changes of communication-integrated sub-domains. Using this model we automate the communication setup procedure among partitioned tasks, thus releasing programmers from the complicated and tiresome work of manually arranging all coordination patterns for every node during application development, facilitate localized communication, thus ensuring scalability of the model and benefit most scientific applications through its support for geometry semantics.
The Architecture
The runtime creation of dynamic shared space is based on an underlying distributed directory layer on each node, which enables the system to detect geometry relationship between registered regions. The distributed directory is constructed by evenly partitioning 1-dimensional index intervals mapped from the multi-dimensional coordinate space that defines the applications domain. A transformation process is used to map the 3-dimensional coordinate space into 1-dimensional index intervals by exploiting the technique of Hilbert space filling curve. A space-filling curve (SFC) is a continuous mapping from a d-dimensional space to a 1-dimensional space. The construction of SFCs is recursive. Figure 2 (left part) shows the recursive construction of a 3-dimensional SFC. Another important property of SFCs is that it is locality preserving. Points that are close together in the d-dimensional space are mapped to points that are close together in the 1-dimensional space.
Figure 2. Recursive property and locality preserving property of Hilbert SFC
Status
Currently we have developed a prototype system of SEINE interaction framework and done experiments on a 64-node Beowulf cluster. The preliminary experiment results proved its scalability. Next step we plan to test it on a larger scale computing environments. We also need to complete the concept part for the proposed programming model, including its definition, interface, architecture, possible extension and after that its complete implementation. In current phase it is implemented as an interaction framework.
Dr.Manish Parashar Associate Professor
"A Dynamic Geometry-based Shared Space Interaction Framework for Parallel Scientific Applications", L.Zhang, M.Parashar, Proceedings of the 11th Annual International Conference on High Performance Computing (HiPC 2004) , Bangalore, India, December 2004