Processor networks and interconnection networks without long wires
C. P. Beigel, Clyde P. Kruskal · 1989
One processor network that is especially attractive for parallel processing is the Butterfly network.A very closely related interconnection network is the Bidelta (or Omega) network.It is well known how to lay out these networks with minimal area, but these layouts use long wires.We show how to lay them out with optimal area and short wires.We also introduce the Mesh-Connected Cycles network, which has optimal area (in the sense of AT 2) for a broad range of running times when executing "ascend-descend" algorithms.The length of its longest wire is nearly optimal, and its layout area has very modest constants.