Hierarchical FPGA Fabrics using 2D-Benes-BFT-Pyramid Network Layouts with Optimizations

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.