The Folded Petersen Network : A New Communication-Efficient
Multiprocessor Topology · 1993
We introduce and analyze a new interconnection topology, called the n-dimensional folded Petersen network (FPn), which is constructed by iteratively applying the cartesian product operation on the well-known Petersen graph itself. The FPn topology provides regularity, node- and edgesymmetry, optimal connectivity (maximal fault-tolerance), logarithmic diameter, and permits self-routing and broad¬ casting algorithms even in the presence of faults. With the same node-degree and connectivity, FPn has smaller diam¬ eter and more nodes than the 3ra-dimensional binary hy¬ percube and several other networks. This paper also em¬ beds rings, meshes, hypercubes, and a variety of tree-related structures efficiently into FPn■