Distributed routing and task allocation in multicomputer systems.

In this dissertation, we propose and analyze several strategies for routing and task allocation in multicomputer systems. The reduction and elimination of looping effects in computer networks is investigated. It is shown that the network's adaptability is improved by incorporating more information in routing messages. Depending on the network structure, the order of a routing strategy required for each node to eliminate looping completely can be determined. Routing in multicomputer networks with regular topology is also addressed. We present a systematic method for wrapping hexagonal meshes to achieve the homogeneity of the network and propose a new addressing scheme for wrapped H-meshes. Efficient routing and broadcasting algorithms under the new addressing scheme are developed. In addition, we develop two fault-tolerant routing schemes for hypercube multicomputers on the basis of depth-first search and network delay tables. An assignment from a task graph to a processor graph is said to be acceptable if every two adjacent task nodes are assigned to two processor nodes whose distance from each other is no more than a prespecified integer value. We address the problem of obtaining the number of acceptable task assignments for given task and processor graphs, and use it to simplify state-space search as well as reduce the size of the state-space to be searched. Two subcube allocation strategies, the buddy strategy using the buddy system and the GC strategy using the binary reflected Gray code, are investigated. Both strategies are proven to be statically optimal. We show that the number of subcubes recognizable by the GC strategy is twice that recognizable by the buddy strategy. Furthermore, we prove that the GC strategy is optimal in terms of the subcube recognition ability of a sequential search. A tight upper bond for the number of Gray codes required for complete subcube recognition is derived. Also, we propose the procedure for task migration under the GC strategy to eliminate fragmentation in a hypercube. We drive the goal configuration, the node-mapping between the source and destination subcubes, and a shortest deadlock-free routing scheme for task migration.PhDComputer scienceUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/162025/1/8907010.pd