Live Webcast 15th Annual Charm++ Workshop

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.

Over the last six years, we have developed a machine independent parallel programming system called Charm. The system provides all the support needed by a software support system for irregular computation. Charm has been extensively used for sucessfully solving large irregular computations arising in branch and bound algorithms, CAD problems etc. In this abstract, we describe the basic features of Charm and an example of a branch and bound algorithm that was successfully solved using parallel computers.