Re-engineering of timing constrained placements for regular architectures

ABSTRACT

Abstract: In a typical design flow, the design may be altered slightly several times after the initial design cycle according to minor changes in the design specification either as a result of design debugging or as a result of changes in engineering requirements. These modifications are usually local and are referred to as engineering changes. In this paper we study the problem of timing driven placement re-engineering: the problem of altering the placement of a circuit to incorporate engineering changes without degrading the timing performance of the circuit. We focus on the re-engineering problem for regular architectures such as FPGAs and gate arrays. Our algorithms exploit the locality of the re-engineering design changes and use the current placement to generate the new placement for the altered circuit. Our experiments on the Xilinx 3000 FPGA architecture demonstrate the effectiveness of our algorithm in handling engineering changes efficiently.

REFERENCES

• 1: Shih-Chieh Chang , Kwang-Ting Cheng , Nam-Sung Woo , Malgorzata Marek-Sadowska, Layout driven logic synthesis for FPGAs, Proceedings of the 31st annual conference on Design automation, p.308-313, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196388]
• 2: C. CHOY, T. CHEUNG, An Algorithm to Deal with Incremental Layout Alteration, Proc. 3~th Midwest Symposium on 6,ircuits and Systems, Vol. 2, 2992, pp. 850- 853.
• 3: Bruno Codenotti , Roberto Tamassia, A Network Flow Approach to the Reconfiguration of VLSI Arrays, IEEE Transactions on Computers, v.40 n.1, p.118-121, January 1991 [doi>10.1109/12.67329]
• 4: Yun-Cheng Ju, Incremental circuit simulation and timing analysis techniques, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 5: Anmol Mathur , C. L. Liu, Compression-relaxation: a new approach to performance driven placement for regular architectures, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.130-136, November 06-10, 1994, San Jose, California, United States
• 6: Anmol Mathur , K. C. Chen , C. L. Liu, Applications of slack neighborhood graphs to timing driven optimization problems in FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.118-124, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201329]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
FPGAs, Xilinx 3000 FPGA architecture, design cycle, design debugging, design flow, design specification, engineering requirements, field programmable gate arrays, gate arrays, logic CAD, logic arrays, program debugging, regular architectures, systems re-engineering, timing constrained placements reengineering, timing performance