A Generalized Processor Allocation Scheme for Recursively Decomposable Interconnection Networks

概要

論文の詳細を見る
The Recursively Decomposable Interconnection Network (RDIN) is a set of interconnection networks that can be recursively decomposed into smaller substructures whose topologies and properties are similar to the original one. The examples of the RDIN are hypercubes, star graph, mesh, tree, pyramid, pancake, and WK-recursive network. This paper proposed a uniform and simple model to represent the RDIN inside computers at first. Based on the model, a generalized and efficient allocation scheme capable of being applied to all the members of the RDIN is developed. The proposed scheme can fully recognize the sub-structures (such as subcube, substar, subtree, ... ) more easily than ever, and it is the first one that can fully recognize all the in-complete substructures. The best-fit allocation is also proposed. The criterion aims at keeping the largest free parts from being destroyed, as is the philosophy of the best-fit allocation. More-over, the proposed scheme can be performed in an injured RDIN with its processors and/or links faulty. Finally, the mathematical analysis and simulations for two instances, hypercubes and star graphs, of the RDIN are presented. The results show that the generalized scheme outperforms or is comparable to the other proprietary allocation schemes designed for the specific structure.
社団法人電子情報通信学会の論文
2002-04-01