Topological Properties of Some Interconnection Network Graphs.
Robert J. Cimikowski · 1996
Interconnection networks play a vital role in parallel computing architectures. We investigate topological properties of some networks proposed for parallel computation, based on their underlying graph models. The vertices of the graph correspond to processors and the edges represent communication links between processors. Parameters such as crossing number and thickness strongly affect the area required to lay out the corresponding circuit on a VLSI chip. In particular, we give upper bounds for the skewness, crossing number, and thickness of several networks including the mesh of trees, reduced mesh of trees, 2-dimensional torus, butterfly, wrapped butterfly, and Benes graph.