Dynamic matching and scheduling algorithms for a multiuser heterogeneous computing environment
F. Özgüner, M.A. Iverson · 1999
In heterogeneous distributed computing (HDC), a network of dissimilar machines is used to execute a given application in parallel. With the advent of advanced networking technologies, the scale where heterogeneous computing can be practically applied is growing to a global scale, thus making it possible to collect high performance computers across the globe into a single computational resource. Multiple users are able to simultaneously use this computational resource to execute a variety of large, parallel applications. This research develops algorithms to allow multiple users to execute applications in a large, decentralized, failure-prone, heterogeneous computing environment. Due to the dynamic and uncertain nature of this environment, the algorithms emphasize the use statistical techniques to make decentralized decisions in a highly dynamic system. This research is split into three distinct problems. In the first problem, a method is developed that statistically obtains an estimate of the execution time of a task on an arbitrary target machine. This execution time estimate is constructed from data gathered from past executions of the task, and the method compensates for varying parameters that affect the execution time of the task. Next, a dynamic matching and scheduling method for heterogeneous machines is developed, where each application is self-scheduling and makes decisions without direct knowledge of the other applications executing in the environment. Knowledge of the other applications is obtained indirectly from machine and network load estimates. In this manner, each application competes for the computational resources of the network. Finally, a cost function is developed that can be used to allow a matching and scheduling algorithm to consider reliability when making an assignment. This is important, since, in a large distributed system, the probability of experiencing a machine or network failure is significant, and large, long-running applications are particularly sensitive to failures.