A STOCHASTIC-MODEL FOR HETEROGENEOUS COMPUTING AND ITS APPLICATION INDATA RELOCATION SCHEME DEVELOPMENT

In a dedicated, mixed-machine, heterogeneous computing (HC) system, an application program may be decomposed into subtasks, then each subtas k assigned to the machine where it is best suited for execution. Data relocation is defined as selecting the sources for needed data items. It is assumed that multiple independent subtasks of an application pro gram can be executed concurrently on different machines whenever possi ble. A theoretical stochastic model for HC is proposed, in which the c omputation times of subtasks and communication times for intermachine data transfers can be random variables. The optimization problem for f inding the optimal matching, scheduling, and data relocation schemes t o minimize the total execution time of an application program is defin ed based on this stochastic HC model. The global optimization criterio n and search space for the above optimization problem are described. I t is validated that a greedy algorithm-based approach can establish a local optimization criterion for developing data relocation heuristics . The validation is provided by a theoretical proof based on a set of common assumptions about the underlying HC system and application prog ram. The local optimization criterion established by the greedy approa ch, coupled with the search space defined for choosing valid data relo cation schemes, can help developers of future practical data relocatio n heuristics.