Torus k-ary n-cube Topologies for Inter-Chip Networks

W.J. Dally. "Performance Analysis of k-ary n-cube Interconnection Networks." IEEE Transactions on Computers, 13(6):775–785, June 1990.

This classic paper uses a combination of analytical modeling and simulation to make an argument for low-dimensional networks when constrained by two-dimensional VLSI packaging. Focus on understanding how each of the equations are derived. Based on our topology lectures, everyone should be able to follow the paper without too much trouble, with the possible exception of the probability analysis in Section 3.B. It is worthwhile, however, to spend some time on this section in order to understand the general approach used for the analytical results in Figures 14–15. Section 23.2 of Dally's text provides useful background information on this type of analysis. Note that the paper assumes unidirectional channels between switching nodes as opposed to the bidirectional channels we have been using in class. Students might also be interested in skimming the later TOC'91 paper which illustrates a technique for reducing the hop count in low-dimensional torus networks without resorting to increasing the dimensionality.