Paul Metzgen
ABSTRACT
This paper presents a novel synthesis algorithm that reduces the area needed for implementing multiplexers on an FPGA by an average of 18%. This is achieved by reducing the number of Lookup Tables (LUTs) needed to implement multiplexers. The algorithm relies on reimplementing 2:1 multiplexer trees using efficient 4:1 multiplexers. The key to the algorithm's performance lies in exploiting the observation that most multiplexers occur in busses. New optimizations are employed which pay a small cost in logic that is shared across the bus to achieve a reduction in the logic required for every bit of the bus.
- A High Performance 32-bit ALU for Programmable Logic. P. Metzgen. Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field Programmable Gate Arrays. Pp 61--70. 2004. Google Scholar
Digital Library
- FPGA Performance Benchmarking Methodology, White Paper, http://www.altera.comGoogle Scholar
- The Stratix Device Handbook (Vol 1). Altera Corporation, 2004.Google Scholar
- E. M. Sentovich et al. "SIS: A System for Sequential Circuit Synthesis." Technical Report, University of California at Berkeley, 1992, Memorandum No. UCB/ERL M92/41Google Scholar
- J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table based FPGA Designs", IEEE Trans. CAD Vol 13, No 1, pp. 1--12, 1994.Google ScholarDigital Library
- V. Manohararajah, S.D. Brown and Z. Vranesic, "Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping" http://sj-wiki/twiki/pub/SJSW/AlteraPublications/tmap.pdf, in Proc. of the Int'l Workshop on Logic Synthesis 2004Google Scholar
- D. Lewis et al, C. Wysocki and R. Cliff, "The Stratix Routing and Logic Architecture" http://sj-wiki/twiki/pub/SJSW/AlteraPublications/stratix.pdf, in Proc. ACM/SIGDA Int'l Symposium on FPGAs (FPGA 2003), pp.12--20, 2003 Google ScholarDigital Library
- David Lewis et al, "The Stratix-II Routing and Logic Architecture" http://sj-wiki/twiki/pub/SJSW/AlteraPublications/f84-lewis.pdf. 2005 Int'l Symposium on FPGAs (FPGA 2005) Google ScholarDigital Library
Index Terms
- Multiplexer restructuring for FPGA implementation cost reduction
Recommendations
Combinational logic synthesis for LUT based field programmable gate arrays
The increasing popularity of the field programmable gate-array (FPGA) technology has generated a great deal of interest in the algorithmic study and tool development for FPGA-specific design automation problems. The most widely used FPGAs are LUT based ...
A STAFAN-like functional testability measure for register-level circuits
ATS '95: Proceedings of the 4th Asian Test SymposiumSTAFAN (statistical fault analysis) is a well known testability analysis program which predicts the fault coverage of a digital circuit under the stuck-at fault model, without actually performing fault simulation. STAFAN offers speed advantage over ...
Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs
In this paper we study structural gate decomposition in general, simple gate networks for depth-optimal technology mapping using K-input Lookup-Tables (K-LUTs). We show that (1) structural gate decomposition in any K-bounded network results in an ...
Comments