OPTIMAL ASS IGNMENT OF TASK MODULES WITH PRECEDENCE FOR D ISTRIBUTED PROCESSING BY GRAPH MATCHING AND STATE-SPACE SEARCH

A graph matching approach to optimal assignment of task modules with varying lengths and precedence relationship in a distributed computing system is proposed. Inclusion f module precedence into the optimal solution is made possible by the use of topological module orderings. Two graphs are defined to represent the processor structure and the module precedence r lationship, respectively. Assignment of the task modules to the system processors i transformed into a type of graph matching. The search of optimal graph matching corresponding to optimal task assignment is formulated as a state-space s arch problem which is then solved by the A * algorithm in artificial intelligence. Illustrative xamples and experimental results are included to show the effectiveness of the proposed approach. C.R. Cate#ories: D.4.1, 1.2.8. Index Terms. " Task assignment, distributed processing, raph matching, topological tree, minima