The Clock Deviation Planning Key Issues Of Effective Algorithms

The rapid development of semiconductor industry introduces a lot of challenges to the integrated circuit (IC) design. On one hand, with the quick scaling down of feature size, process variations have more and more impact on circuits. State-of-the-art IC design must take new factors including practicality and yield into consideration. Existing optimization techniques, such as clock skew scheduling, need further study and improvement. On the other hand, the exponential increase of integration capability demands higher performance for the algorithms in computer aided design (CAD). Many optimization problems need new solving methods to meet the requirements of very large scale integrated circuits.As one of the most powerful sequential optimization techniques, clock skew scheduling optimizes the performance of circuits by deliberately assigning different clock delays to flip-flops. Conventional clock skew scheduling can be transformed into a minimum cycle ratio problem and solved by efficient network flow algorithms. In practice, the clock delays are implemented through the interconnects and additional buffers in clock distribution network. Conventional clock skew scheduling may need a large set of clock delays, which causes several potential issues in the implementation of clock network. On one hand, the excessive demand of buffers in clock network may introduce unacceptable area and power overhead. On the other hand, with the impact of process variations, it becomes more and more difficult to reliably implement a large set of clock delays simultaneously. Consequently, the application of clock skew scheduling in industrial field is greatly limited.Multi-domain clock skew scheduling tackles the reliable implementation of clock network by assigning flip-flops to several clocking domains while optimizing the per-formance of circuits. However, due to the introduction of discrete clocking domains, the complexity of the problem becomes NP-complete, which makes it unsolvable using traditional approacheso Existing algorithms are either computationally too expensive or poor in solution quality. The multi-domain clock skew scheduling necessitates effi- cient algorithms that are good at both performance and accuracy. In this thesis, efficient algorithms for the multi-domain clock skew scheduling problem are studied.First, a fast algorithm for multi-domain clock skew scheduling is proposed. The contributions include:●The problem is transformed into an approximate and solvable mixed integer linear programming (MILP) problem. The advantage of this transformation is that, it considers the clocking domain assignment globally and can be solved optimally once and for all.●For the MILP problem, based on the monotonicity in the constraints, a generalized Howard’s algorithm is proposed to efficiently solve it.●An incremental critical-cycle-oriented refinement is proposed to further improve the domain assignment.●To further improve the performance of algorithms for the multi-domain clock skew scheduling problem, a graph pruning algorithm is developed to preprocess the timing constraint graph and effectively decrease the input size.The fast algorithm is able to obtain near-optimal solutions. It obtains optimal so-lutions for88of the93(=94.6%) tests on ISCAS89benchmarks. In addition, it has a performance of at least an order faster than existing algorithms. For the graph pruning algorithm, experimental results also validate the effectiveness. Its application on the fast algorithm shows a further performance speedup of1.43X-4.76X (2.66X on average).To obtain the theoretically-guaranteed optimal solutions for multi-domain clock skew scheduling, an exact algorithm is developed to search for the optimal clocking domain assignment. The main contributions include:●An algorithm based on branch-and-bound is proposed to search for the optimal domain assignment of flip-flops.●Three strategies are proposed to improve the efficiency of the search, including min-slack-first-branching strategy, negative-path-aware confinement and min-cost-first-process strategy.●Efficient bounding algorithms are adopted, in which the fast algorithm is used to compute lower bounds of branches.Experimental results validate the accuracy and efficiency of the exact algorithm. For example, it obtains optimal solutions for all the ISCAS89benchmarks in3.15sec-onds.Process variations not only have impact on clock network, but also on the delays in circuits themselves. The uncertainty of delays in circuits may cause the sequential yield issue. Therefore, how to assign the clock delays such that the yield is optimized is also a critical problem in clock skew scheduling techniques. Integrated with the prevalent sta-tistical static timing analysis techniques, General yield driven clock skew scheduling considers the distribution of path delays accurately, and thus has natural advantage in yield optimization, In this thesis, general yield driven clock skew scheduling is studied. The main contributions include:●Theoretically, a clear statement about the special property in the general yield-driven clock skew scheduling problem is provided, that is, it is actually a gener-alized network flow problem.●To efficiently solve the problem, two generalized network flow algorithms, are proposed, including generalized Howard’s algorithm (V2) and generalized mini-mum balance algorithm.Experimental results validate the advantage of the proposed algorithms in perfor-mance compared with the existing algorithm, especially on large circuits. The new algorithms show speedups of up to157.55X.