A Portable Software Support System for Irregular Computations
PPL Technical Report 1993
Publication Type: Paper
Repository URL:
Abstract
In the last decade, parallel programming has emerged as a powerful
new technology. Many large commercial parallel machines are
available today, such as Intel iPSC/860 (and soon, the Paragon),
NCUBE's 1024 processor machines, CM-5, etc. A large class of
algorithms in science, engineering, operations research, and
artificial intelligence can potentially benefit from parallel
processing. However most of the applications that have been
successfully solved using parallel machines have a very regular
structure. Irregular computations, such as branch and bound,
adaptive grids, are an important class of algorithms. The effective
parallel solution of irregular computations poses greater problems
because of the need for facilities for dynamic creation of work,
and dynamic load balancing. The features required of any software
support for irregular computations are:
- Portability: The application program should be portable across the wide variety of parallel machines that are currently available.
- Dynamic load balancing: The system should provide support for automatically balancing load, in addition to the capabilities of user-controlled load balancing.
- Dynamic creation of work: A large number of irregular computations could be more easily solved using parallel computers if tasks could be inexpensively created dynamically. The support system should allow inexpensive, dynamic creation of tasks.
- Modularity and reuse: An application program could consist of different modules that may be written by different programmers; therefore the system should allow programs to be written in a modular fashion and the reuse of modules.
- Prioritization: In irregular computations, there may exist many different tasks in the system at the same time. Additionally, the order of processing of these tasks may be important. In such cases, the system should provide support for the prioritized execution of tasks.
TextRef
Laxmikant V. Kale, Amitabh B. Sinha, Attila Gursoy, "A portable software
support system for irregular computations", Parallel Programming Laboratory,
Department of Computer Science, University of Illinois at Urbana-Champaign, 1993.
People
Research Areas