New Heuristic for Load-Balanced Assignment of Objects and Minimized NetworkCommunication in Distributed Programs Implemented Through Inverse Remote Procedure Calls

摘要

A load balancing and communication minimizing heuristic used in the InverseRemote Procedure Call (IRPC) system is introduced. The system provides compile and run time support for developing distributed applications, while shielding the programmer from the details of distribution and interconnection. The IRPC graph partitioning heuristic operates in time of O(N) in the number of communicating objects. This complexity is both independent of M, the number of network sites, and considerably better than that of previously known related algorithms, such as the A, which employs backtracking and is potentially exponential of the max-flow/min-cut class of network flow algorithms or heuristics which tend to be at least of O(M(N (exp 4))). In an extensive quantitative evaluation, the heuristic was demonstrated to perform very well, finding on the average 75 percent traffic cost reductions for over 95 percent of the programs. By employing transparent and automatic mechansims and a well performing efficient distributing heuristic, the IRPC system improves significantly on the previous systems, and serves as a useful tool for distributed application development.