Enhanced Algorithms for Non-Zero Clock Skew Scheduling

Ivan S. Kourtev

July 15, 1999

Abstract

The last three decades have witnessed an explosive development of integrated circuit fabrication technologies. The complexities of current CMOS circuits are reaching beyond the 100 nanometers feature size and multi-hundred million transistors per integrated circuit. To fully utilize this technological potential, circuit designers use sophisticated Computer-Aided Design (CAD) tools. The design of the clock distribution network---typically late in the design process---poses multiple problems in order to satisfy ever increasing performance goals. An automated methodology for synchronous circuit performance optimization is presented that improves the performance and increases the reliability of fully synchronous integrated circuits. Traditional design wisdom historically dictated the use of global zero clock skew. In this dissertation, however, non-zero clock skew scheduling is exploited. Two classes of algorithms are considered.

A strategy is presented to exploit the variation of signal delays within a fully synchronous digital circuit so as to provide an added degree of freedom rather than treat clock skew as a design constraint. Non-zero clock skew scheduling and the topology of the corresponding clock distribution network are simultaneously developed in the proposed methodology. This methodology is based on a constant-load buffer delay model and builds on Linear Programming (LP) solution techniques. The simultaneous clock scheduling and clock tree topology synthesis problem is formulated as a mixed-integer linear programming problem that can be solved efficiently. The proposed algorithms have been evaluated on a variety of benchmark and industrial circuits and synchronous performance improvements of up to 64% have been demonstrated.

For those cases where reliable circuit operation and production yield are the highest level priorities, an alternative QP based problem formulation is developed. This formulation is based on a quadratic (hence the QP---quadratic programming) measure, or cost function, of the tolerance of a clock schedule to parameter variations. A mathematical framework is presented for the solution of the constrained and bounded QP problem. A constrained version of the problem is iteratively solved using the Lagrange multipliers method. As these research issues are topics of great practical importance for input/output interfacing and Intellectual Property (IP) blocks, explicit clock delay and skew requirements are fully integrated into the proposed mathematical model. This methodology has been implemented and demonstrates significant improvements for both benchmark and industrial circuits.

Return to Eby Friedman's WWW home page