Formal Specification of Interconnection Networks

Interconnection networks are an important and well-studied topic in parallel computing and architecture, but a homogeneous and general method for defining and classifying the topologies and behaviors of interconnection networks is lacking. Topologies are usually specified informally by picture or more formally by permutations of wire enumerations. This paper presents an improved method for specifying multistage networks via permutations, along with two styles of formal functional specification of the entire network, using both a standard multistage organization and a generalized fat tree organization. This method is applied to two specific indirect multistage switch networks: the baseline and the butterfly. The functional specification emphasizes the similarities between the networks, and also captures the functionality provided by general-purpose network nodes.