Bussed interconnection networks from trees

Pin limitations are a fundamental obstacle in the construction of massively parallel computers. The paper introduces a class of d-dimensional bussed hypercubes that can perform simultaneous bidirectional communication across any dimension using d+1, rather than 2d, ports per node. Each network Q_d (T) is based on a tree T, which specifies the ´shape´ of the busses, and can perform d(d+1)/2 permutations π_ij(x)=x⊕c _ij via a simple global command. This construction is then generalized to any d permutations II=(π₁,. . .,π_d) of any set of nodes X. Given any edge-labeled directed tree T, whose kth arc is associated with the permutation π_k, a bussed network N (II,T) is constructed that can-in one clock tick-perform any of the O(d²) permutations arising from the paths in the tree T