Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search |
| |
Authors: | Ling-Ling Wang Wen-Hsiang Tsai |
| |
Affiliation: | (1) Institute of Computer Engineering, National Chiao Tung University, Hsinchu, Taiwan 30050, Republic of China;(2) Department of Information Science, National Chiao Tung University, Hsinchu, Taiwan 30050, Republic of China |
| |
Abstract: | A graph matching approach to optimal assignment of task modules with varying lengths and precedence relationship in a distributed computing system is proposed. Inclusion of 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 relationship, respectively. Assignment of the task modules to the system processors is transformed into a type of graph matching. The search of optimal graph matching corresponding to optimal task assignment is formulated as a state-space search problem which is then solved by theA* algorithm in artificial intelligence. Illustrative examples and experimental results are included to show the effectiveness of the proposed approach. |
| |
Keywords: | D.4.1 I.2.8 |
本文献已被 SpringerLink 等数据库收录! |
|