Abstract
In this paper, a class of hierarchically structured multistage interconnection networks is proposed. It is shown that the routing schemes of the proposed networks are simple. In the environment with high locality of accesses, performance analysis of the proposed networks shows that the acceptance (free of collision) probability is increased and the average path length (delay) is less than that of conventional multistage interconnection networks, such as delta networks. In general, the performance of the proposed networks is superior to the conventional multistage interconnection networks when the accesses locality ≥ 0.5. The cost of the proposed networks is analyzed and is found to be comparable to that of conventional ones.