Application-level software self-balancing

The authors propose a hybrid static/dynamic scheduling scheme on distributed-memory multiple-processor systems, e.g., distributed systems and multicomputers. Using this self-balancing scheme, computations are first scheduled statically, and then dynamically redistributed to adapt to the run-time environments. The rescheduling operations are directed by a number of program parameters, which can be directly accessed from within the program and will serve as processor load indices. As a result the self-balancing operations can be implemented entirely at the application level, which requires minimal system supports. To illustrate the concept, the self-balancing technique is applied to the asynchronous iterative methods. Various design tradeoffs are discussed, and preliminary performance results on an NCUBE multicomputer are presented