Skew-programmable clock design for FPGA and skew-aware placement

ABSTRACT

In this paper, we propose a skew-programmable clock-routing architecture. The skews can be adjusted using programmable delay elements (PDEs) which we insert into the clock trees. We develop efficient, shortest-path-based algorithms for programming PDEs to optimize timing. Unlike previous methods for FPGA skew optimization which require large power and routing penalty, our method can achieve large timing improvement with small overhead. Typically, if timing requirements are tight, placers make efforts to satisfy them, often at a cost of compromising routability, total wire length, and power. In this work, we propose novel clock-skew-aware placement algorithms which allow us to relax the timing constraints during placement. Timing can be later optimized as a post process. Even though we demonstrate the efficiency of our approach using FPGAs, the new skew optimization method and the new placement algorithm are quite general and can be applied to any general, topology-constrained skew optimization problem. Experimental results indicate that using the new clock-architecture we can obtain a 22% timing improvement for post-layout skew optimization and an additional 21% improvement from our skew-aware placement algorithm. In one fabric, the cost of added logic is 2.19% as measured by dynamic power dissipation, and 0.85% in terms of area overhead.

REFERENCES

• 1: ITC'99 benchmarks, www.cerc.utexas.edu/itc99-benchmarks
• 2: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 3: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 4: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 5: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
• 6: Li Shang , Alireza S. Kaviani , Kusuma Bathala, Dynamic power consumption in Virtex™-II FPGA family, 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.503072]
• 7: 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]
• 8: A. Srinivasan, K. Chaudhary, E.S. Kuh, "RITUAL: a performance driven placement algorithm", Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on, Volume: 39 Issue: 11, Nov. 1992 pp: 825--840.
• 9: Deshanand P. Singh , Stephen D. Brown, Constrained clock shifting for field programmable gate arrays, 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.503067]
• 10: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
• 11: S. Tam, S. Rusu, U. N. Desai, R. Kim, J. Zhang and I. Young, "Clock Generation and Distribution for the First IA-64 Microprocessor", IEEE journal of solid-state circuits, vol. 35, no. 11, november 2000.
• 12: Kaushik Ravindran , Andreas Kuehlmann , Ellen Sentovich, Multi-Domain Clock Skew Scheduling, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.801, November 09-13, 2003 [doi>10.1109/ICCAD.2003.100]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms

Keywords:
clock architecture, placement, skew optimization