Using bus-based connections to improve field-programmable gate array density for implementing datapath circuits

ABSTRACT

As the logic capacity of Field-Programmable Gate Arrays (FPGAs) increases, they are being increasingly used to implement large arithmetic-intensive applications, which often contain a large proportion of datapath circuits. Since datapath circuits usually consist of regularly structured components (called bit-slices) which are connected together by regularly structured signals (called buses), it is possible to utilize datapath regularity in order to achieve significant area savings through FPGA architectural innovations. This paper describes such an FPGA routing architecture, called the multi-bit routing architecture, which employs bus-based connections in order to exploit datapath regularity. It is experimentally shown that, comparing to conventional FPGA routing architectures, the multi-bit routing architecture can achieve 14% routing area reduction for implementing datapath circuits, which represents an overall FPGA area savings of 10%. This paper also empirically determines the best values of several important architectural parameters for the new routing architecture including the most area efficient granularity values and the most area efficient proportion of bus-based connections.

REFERENCES

• 1: D. Chen and J. Rabaey, "A Reconfigurable Multiprocessor IC for Rapid Prototyping of Algorithmic-Specific High-Speed DSP Data Paths," JSSC, Dec. 1992, pp.1895--1904.
• 2: A. Yeung and J. Rabaey, "A Reconfigurable Data Driven Multi-Processor Architecture for Rapid Prototyping of High Throughput DSP Algorithms," HICCS, Jan. 1993, pp.169--178.
• 3: Ray Bittner , Peter Athanas, Wormhole run-time reconfiguration, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.79-85, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258315]
• 4: D. Cherepacha and D. Lewis, "DP-FPGA: An FPGA Architecture Optimized for Datapaths," VLSI Design, 1996, pp.329--343.
• 5: Carl Ebeling , Darren C. Cronquist , Paul Franklin, RaPiD - Reconfigurable Pipelined Datapath, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.126-135, September 23-25, 1996
• 6: J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
• 7: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
• 8: Takashi Miyamori , Kunle Olukotun, A Quantitative Analysis of Reconfigurable Coprocessors for Multimedia Applications, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.2, April 15-17, 1998
• 9: Alan Marshall , Tony Stansfield , Igor Kostarnov , Jean Vuillemin , Brad Hutchings, A reconfigurable arithmetic array for multimedia applications, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.135-143, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296444]
• 10: Ahmad Alsolaim , Janusz Starzyk , Jürgen Becker , Manfred Glesner, Architecture and Application of a Dynamically Reconfigurable Hardware Array for Future Mobile Communication Systems, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.205, April 17-19, 2000
• 11: Seth Copen Goldstein , Herman Schmit , Mihai Budiu , Srihari Cadambi , Matt Moe , R. Reed Taylor, PipeRench: A Reconfigurable Architecture and Compiler, Computer, v.33 n.4, p.70-77, April 2000 [doi>10.1109/2.839324]
• 12: Katarzyna Leijten-Nowak , Jef L. van Meerbergen, An FPGA architecture with enhanced datapath functionality, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611846]
• 13: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 14: Altera Documentation Library, Sep. 2004, Altera Corporation.
• 15: Xilinx Data Sheets, 2004, Xilinx Inc.
• 16: J. Rose and S. Brown, "Flexibility of Interconnection Structures for Field-Programmable Gate Arrays," JSSC, Mar. 1991, pp.277--282.
• 17: S. Brown, G. Lemieux, and M. Khellah, "Segmented Routing for Speed-Performance and Routability in Field-Programmable Gate Arrays," J-VLSI, 1996, pp.275--291.
• 18: V. Betz and J. Rose, "Effect of the Prefabricated Routing Track Distribution on FPGA Area-Efficiency," Trans. on VLSI, Sep. 1998, pp.445--456.
• 19: Vaughn Betz , Jonathan Rose, FPGA routing architecture: segmentation and buffering to optimize speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.59-68, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296428]
• 20: Mike Sheng , Jonathan Rose, Mixing buffers and pass transistors in FPGA routing architectures, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.75-84, February 2001, Monterey, California, United States [doi>10.1145/360276.360302]
• 21: Guy Lemieux , David Lewis, Circuit design of routing switches, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503052]
• 22: A. Ye, J. Rose, and D. Lewis, "Synthesizing Datapath Circuits for FPGAs with Emphasis on Area Minimization," FPT, Dec. 2002, pp.219--227.
• 23: A. Ye and J. Rose, "Using Multi-Bit Logic Blocks and Automated Packing to Improve Field-Programmable Gate Array Density for Implementing Datapath Circuits," FPT, Dec. 2004, pp.129--136.
• 24: Andy Gean Ye , Jonathan Rose , David Lewis, Field-programmable gate array architectures and algorithms optimized for implementing datapath circuits, University of Toronto, Toronto, Ont., Canada, 2004
• 25: A. Ye, J. Rose, and D. Lewis, "Architecture of Datapath-Oriented Coarse-Grain Logic and Routing for FPGAs," CICC, Sep. 2003, pp.61--64.
• 26: H. Hseih, et al, "Third-Generation Architecture Boosts Speed and Density of Field-Programmable Gate Arrays," CICC, May 1990, pp.31.2.1--31.2.7.
• 27: Vaughn Betz , Jonathan Rose, How Much Logic Should Go in an FPGA Logic Block?, IEEE Design & Test, v.15 n.1, p.10-15, January 1998 [doi>10.1109/54.655177]
• 28: J. Rose, R. Francis, D. Lewis, and P. Chow, "Architecture of Field-Programmable Gate Arrays: The Effect of Logic Block Functionality on Area Efficiency," JSSC, Oct. 1990, pp.1217--1225.
• 29: E. Ahmed and J. Rose, "The Effect of LUT and Cluster Size on Deep-Submicron FPGA Performance and Density," Trans. on VLSI, Mar. 2004, pp.288--298.
• 30: Guy Lemieux , David Lewis, Using sparse crossbars within LUT, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.59-68, February 2001, Monterey, California, United States [doi>10.1145/360276.360299]
• 31: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 32: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Speed and area tradeoffs in cluster-based FPGA architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.1, p.84-93, Feb. 2000 [doi>10.1109/92.820764]
• 33: P. Leventis, et al, "Cyclone: A Low-Cost, High-Performance FPGA," CICC, Nov. 2003, pp.49--52.
• 34: Pico-Java Processor Design Documentation, Sun Microsystems, 1999.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.0 General

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
FPGA architecture, area efficiency, datapath regularity, reconfigurable fabric, routing architecture