A synthesis oriented omniscient manual editor

ABSTRACT

The cost functions used to evaluate logic synthesis transformations for FPGAs are far removed from the final speed and routability determined after placement, routing and timing analysis. This distance has given rise to the field of physical synthesis, which attempts to improve logic synthesis by employing cost functions that contain placement, routing and/or timing analysis information.In this work we take this notion to an extreme that we call omniscience, in which post-routing timing analysis is provided in the context of a manual editor in which the user selects logical and physical transformations. After each incremental circuit modification, the user is informed of the circuit performance after routing and timing analysis. Since the computations involved in providing this level of information are large, we restrict the application to relatively small circuits, no larger than 1000 logic elements.Using this approach on a commercial FPGA, we propose a set of logic transformations specific to the logic and routing architecture of the Xilinx Virtex-E device. On a set of 10 circuits we have achieved an average performance improvement of 10% when both logical and physical changes are used. Another value of the editor is that it reveals new types of automatable physical-synthesis transformations and optimization strategies that arise from architectural properties of the target device.

REFERENCES

• 1: Jinan Lou , Wei Chen , Massoud Pedram, Concurrent logic restructuring and placement for timing closure, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.31-36, November 07-11, 1999, San Jose, California, United States
• 2: Joey Y. Lin , Ashok Jagannathan , Jason Cong, Placement-driven technology mapping for LUT-based FPGAs, 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.611836]
• 3: Deshanand P. Singh , Stephen D. Brown, Incremental placement for layout driven optimizations on FPGAs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.752-759, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774683]
• 4: J. Cong and Y. Ding, "FlowMap: an optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 13, issue 1, 1994, pp. 1--12.
• 5: T. Kutzschebauch , L. Stok, Layout Driven Decomposition with Congestion Consideration, Proceedings of the conference on Design, automation and test in Europe, p.672, March 04-08, 2002
• 6: William Chow , Jonathan Rose, EVE: a CAD tool for manual placement and pipelining assistance of FPGA circuits, 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.503061]
• 7: Xilinx Inc., "Virtex-E Production Product Specification", Online: http://direct.xilinx.com/bvdocs/publications/ds022.pdf, accessed on July 7, 2003.
• 8: A. Roopchansingh and J. Rose, "Nearest Neighbour Interconnect in Deep Submicron FPGAs", Proc. of IEEE CICC, May 2002, pp. 59--62.
• 9: Srinivas Devadas , Abhijit Ghosh , Kurt Keutzer, Logic synthesis, McGraw-Hill, Inc., New York, NY, 1994
• 10: Combining Technology Mapping with Post-Placement Resynthesis for Performance Optimization, Proceedings of the International Conference on Computer Design, p.616, October 05-05, 1998
• 11: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 12: Xilinx XC4000 device data sheet, Online: http://direct.xilinx.com/bvdocs/publications/4000.pdf. Accessed September 22, 2003.
• 13: Karl Schabas , Stephen D. Brown, Using logic duplication to improve performance in FPGAs, 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.611838]
• 14: Scott Hauck , Matthew M. Hosler , Thomas W. Fry, High-performance carry chains for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.223-233, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275142]
• 15: J. Cong and Y. Hwang, "Boolean Matching for LUT-Based Logic Blocks With Applications to Architecture Evaluation and Technology Mapping," IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 20, No. 9, September 2001, pp. 1077--1090.
• 16: T. Czajkowski, "A Synthesis Oriented Omniscient Manual Editor for FPGA Circuit Design," Master of Applied Science thesis, University of Toronto, 2004.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms

Keywords:
manual, synthesis, virtex-e