Even though Benes/BFT multi-stage networks offer O(N*Log N) crosspoint complexity compared to 2D-Mesh Networks with O(N^2) crosspoint complexity, lack of known 2D-Mesh-like 2D layouts for multi-stage networks is the first main hurdle to exploit them as an FPGA fabric and consequently 2D-Mesh based fabrics have become prevalent. First, we present a fundamental layout for Benes/BFT networks making them implementable as simple as 2D-Mesh Networks, with all the wires between different logic blocks as either horizontal wires or vertical wires only, so we named them 2D-Benes or 2D-BFT Networks or 2D-Multi-stage networks in general. We apply several isomorphic transformations, and adapt Pyramid network properties. We also provide locality or nearest neighborhood connectivity, so that each logic block is directly connected its four neighbors and each logic block is connected to all its neighbors with the same path length or delay by bringing nearest neighbor connections to lower stages. Since fully connected Benes/BFT Networks is an over-kill as an FPGA fabric, we adapt several ways of crossbar depopulation and wire segmentation. We implemented various hierarchical multi-stage networks based FPGA fabric architectures, replicable at tile level, in a commercial FPGA and achieved ~2X area savings with significant power and performance improvements over 2D-Mesh based fabrics. We conclude with a summary of the benefits and drawbacks of these multi-stage networks based Hierarchical FPGA fabrics compared to prevailing 2D-Mesh network based fabrics. The foregoing Hierarchical FPGA Fabric technology was patent protected since May 25, 2007 in US8269523, US8898611, US9374322, US9509634 and their continuation patents.

Hierarchical FPGA fabrics based on 2D-BFT-Pyramid networks with transformations and optimizations even though offer significant area, power and performance savings still have several drawbacks compared to 2D-Mesh based FPGA fabrics. For example, hierarchical multi-stage fabrics are replicated at tile level of certain tile size do not offer consistent results regardless of the placement of the benchmarks emulated and certain precious routing resources are usable only if the signal traverses that particular hierarchy. We present several enhancements, techniques, and optimizations to transform hierarchical multi-stage networks into flat multi-stage networks i.e., make them replicable for each logic block in both multiplexers and wires. We also propose techniques to provide cascadable wires of arbitrary length with single multiplexer delay to traverse several wires of signal path or same stage connections, to enable multiple signal U-turns as opposed to only one U-turn inherent in a multi-stage network. We achieved the goal of making multi-stage network based FPGA fabric to seamlessly replace any existing 2D-Mesh based fabric, yet keeping everything else intact including placement, routing and all CAD Tools. We implemented the flat multi-stage networks based FPGA fabrics in a few commercial FPGAs with ~3X area savings and significant improvements in other dimensions and also the routing runtime in parity. We conclude with illustration of the benefits and absolutely no drawbacks for multi-stage network based Flat FPGA fabrics compared to prevailing 2D-Mesh network based fabrics. The foregoing Flat FPGA Fabric technology was patent protected since September 7, 2011 in US9374322, US9509634 and their continuation patents.