Topological Properties of Stretched Graphs
Pooya Shareghi, Hamid Sarbazi‐Azad · IEEE International Conference on Computer Systems and Applications, 2006. · 2006
We study a class of interconnection networks for multiprocessors, called the Stretched-G network, which is based on the base graph G by replacing each edge of the base network with an array of processors. Two interesting features of the proposed topology are its area-efficient VLSI layout and superior scalability over the underlying base network while preserving most of its desirable properties. We conduct a general study on the topological properties of stretched networks. We first obtain their basic topological parameters, after that we present an optimal routing algorithm. We also present a unified approach to obtain the topological properties and the VLSI-layout of an arbitrary stretched network based on the properties of the corresponding base network G.