Efficient task assignment for distributed computing system
Chiun‐Chieh Hsu, Sheng‐De Wang, Te‐Son Kuo · Journal of the Chinese Institute of Engineers · 1989
In this paper, a cost function considering execution time, communication time and even idle time, is employed to measure the performance of task assignment in a distributed computing system. We successfully develop a new mathematical model to describe this kind of cost function. The task assignment problem is formulated as one of directed‐to‐undirected graph mapping (DU‐mapping) which maps a directed acyclic task graph onto an undirected system graph. The search of optimal DU‐mapping is NP‐complete and is transformed into a state space search problem. Using an underestimation to A* algorithm, we can obtain an optimal DU‐mapping and prune the most nodes in a state space tree. An alternative overesti‐mation is applied to prune more nodes but also obtain a suboptimal DU‐mapping. Results of a wide range of experiments reveal that both estimates perform very well due to close evaluation of the real cost.