Heuristic task allocation algorithms in hypercube computer architecture

Abstract

Two heuristic algorithms are proposed in this thesis for solving the task allocatin problem encountered in distributed computing systems. A cost function defined in terms of a single unit, time, is proposed for evaluating the effectiveness of task allocation. This cost function represents the maximum time for a task to complete module execution and communication in all the processors. The proposed approaches allow various system constraints to be included for consideration. Graphs are used to represent the module relationship of a given task and the processor structure of a distributed computing system. Contrary to an optimal approach which is computationally complex and inefficient, the proposed heuristic approaches find near-optimal solutions very fast and, thus, are more practical than the optimal approach. Algorithm I formulates the task allocation problem as a graph partitioning probpartition a given problem graph. Algorithm II formulates the task allocation problem as a state space search problem, and solves it with a best first strategy to find a suboptimal solution fast. A useful heuristic evaluation function based on the greedy-method is used to estimate the upper-bound h(n) of h*(n). Illustrative examples and some experimental results are also included to show the effectiveness of the proposed algorithms. The final goal of this thesis is to give the facility of task allocation to the hypercube computer currently being developed in our laboratory. The hardware structure of our hypercube computer is presented, and some illustrative examples applicated to the hypercube structures are also included. The proposed algorithms work well enough even though they do not always guarantee optimal solutions.,