Brief History of Multi-stage Networks Leading up to today’s FPGA Fabrics

• Multi-stage networks were invented/used for Telephone switching since 1950s:
  • Clos network is a 3-stage network invented by Charles Clos in 1951, at AT&T Bell Laboratories, for telephone switching to save area compared to a crossbar switch.
  • Clos network uses high-radix switches.
  • Benes networks were invented using radix-2 switches
  • Benes networks were extended to any size radix switches with 2N*logN stages.

• Multi-stage networks were used as interconnection networks for parallel and distributed computing since 1980s:
  • Clos and Benes networks were used as interconnection networks for parallel and distributed computing.
  • Tree networks, Fat Tree Networks and Butterfly Fat Tree Networks were invented.
    • Butterfly Fat Tree networks are Folded Benes Networks with U-turn switches at every stage.
  • Pyramid networks which have same level connections (also known as mesh connections) in addition to hierarchical connections were also employed in parallel and distributed computing. And also Fat-Pyramid networks.

• Multi-stage networks were used as switch Fabric since 1990s:
  • Clos and Benes networks were used as cross connects and switch fabrics in networking equipment.

• Early attempts of Multi-stage networks as FPGA Fabrics:
  • Multi-stage networks inherently have tree topology with processing elements connected to the leaf stage.
  • However FPGA fabric requires processing elements and switching stages arranged in a 2D grid.
  • Many failed attempts of 2D-layouts such as H-tree structures, L structures etc.

• In 2007, Konda invented an elegant and seminal layout for Multi-stage networks:
  • We invented/patented elegant 2D layouts to implement Benes network (and other Multi-stage Networks) as FPGA fabric just as simple as a 2D-Mesh network using only horizontal and vertical wires.
  • We coined the terms “2D Benes Network”, “2D Multi-stage Network”, “2D BFT Network” and “2D BFT Pyramid Network” etc.