Metrics and techniques for automatic partitioning and assignment of object-based concurrent programs

The software crises is defined as the inability to meet the demands for new software systems, due to the slow rate at which systems can be developed. To address the crisis, object-based design and implementation techniques and domain models have been developed. However, object-based techniques do not address an additional problem that plagues systems engineers-the effective utilization of distributed and parallel hardware platforms. This problem is partly addressed by program partitioning languages that allow engineers to specify how software components should be partitioned and assigned to the nodes of concurrent computers. However, very little has been done to automate the tasks of partitioning and assignment at the task and object level of granularity. Thus, this paper describes automated techniques for distributed/parallel configuration of object-based applications, and demonstrates the technique on Ada programs. The granularity of partitioning is at the level of the Ada program unit (a program unit is an object, a class, a task, a package (possibly a generic template) or a subprogram). The partitioning is performed by constructing a call-rendezvous graph (CRG) for an application program. The nodes of the graph represent the program units, and the edges denote call and task interaction/rendezvous relationships. The CRG is augmented with edge weights depicting inter-program-unit communication relationships and concurrency relationships, resulting in a weighted CRG (WCRC). The partitioning algorithm repeatedly "cuts" edges of the WCRG with the goal of producing a set of partitions among which (1) there is a small amount of communication and (2) there is a large degree of potential for concurrent execution. Following the partitioning of the WCRG into tightly coupled clusters, a random neural network is employed to assign clusters to physical processors.