The clock latency scheduling problem is usually solved on the sequential graph, also called register-to-register graph. In practice, the the extraction of the sequential graph for the given circuit is much more expensive than computing the clock latency schedule for the sequential graph. In this paper we present a new algorithm for clock latency scheduling which does not require the complete sequential graph as input. The new algorithm is based on the parametric shortest paths algorithm by Young, Tarjan and Orlin. It extracts the sequential timing graph only partly, that is in the critical regions, through a call back. It is still guaranteed that the algorithm finds the critical cycle and the minimum clock period. As additional input the algorithm only requires for every register the maximum delay of any outgoing combinational path. Computing these maximum delays for all the registers is equivalent to the timing analysis problem, hence they can be computed very efficiently. Computational results on recently released public benchmarks and industrial designs show that in average only 20.0 % of the edges in the sequential graph need to be extracted and this reduces the overall runtime to 5.8 %.

Physical design EDA research in academia has historically been based on infrastructure developed independently by individual contributors. This has led to fragmentation in the community, where interaction, data interchange and comparison of results between tools are difficult. We discuss our early experience with the OpenAccess Gear system, an open source software initiative intended to provide pieces of the critical integration and analysis infrastructure that are taken for granted in proprietary tools, but often wholly absent in research tools. Built on top of the widely available OpenAccess database, OA Gear provides components such as industrial-strength static timing analysis and extensible layout and netlist visualization. We discuss preliminary results from two on-going research efforts that have adopted OA Gear as their infrastructure: retrofitting the University of Michigan Capo placer into this environment, and the addition of a timing-driven capability to the Carnegie Mellon Warp placer.

Bounding the load capacitance at gate outputs is a standard element in today's electrical correctness methodologies for high-speed digital very large scale integration design. Bounds on load caps improve coupling-noise immunity, reduce degradation of signal transition edges, and reduce delay uncertainty due to coupling noise (Kahng et al. 1998). For clock and test distribution, an additional design requirement is bounding the buffer skew, i.e., the difference between the maximum and the minimum number of buffers over all of the source-to-sink paths in the routing tree, since buffer skew is one of the main factors affecting delay skew (Tellez and Sarrafzadeh 1997). In this paper, we consider algorithms for buffering a given tree with the minimum number of buffers under given load cap and buffer skew constraints. We show that the greedy algorithm proposed by Tellez and Sarrafzadeh is suboptimal for nonzero buffer-skew bounds and give examples showing that no bottom-up greedy algorithm can achieve optimality. The main contribution of the paper is an optimal dynamic programming algorithm for the problem. Experiments on test cases extracted from recent industrial designs show that the dynamic programming algorithm has practical running time and saves up to 37.5% of the buffers inserted by Tellez and Sarrafzadeh's algorithm.

We show how the new approximation algorithms by Garg and Konemann with extensions due to Fleischer for the multicommodity flow problem can be modified to solve the linear programming relaxation of the global routing problem. Implementation issues to improve the performance, such as a discussion of different functions for the dual variables and how to use the Newton method as an additional optimization step, are given. It is shown that not only the maximum relative congestion is minimized, but the congestion of the edges is distributed equally such that the solution is optimal in a well-defined sense: the vector of the relative congestion of the edges sorted in nonincreasing order is minimal by lexicographic order. This is an important step toward improving signal integrity by extra spacing between wires. Finally, we show how the weighted netlength can be minimized. Our computational results with recent IBM processor chips show that this approach can be used in practice even for large chips and that it is superior on difficult instances where ripup and reroute algorithms fail.

Article Free Access Share on Provably good global routing by a new approximation algorithm for multicommodity flow Author: Christoph Albrecht Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, Germany Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, GermanyView Profile Authors Info & Claims ISPD '00: Proceedings of the 2000 international symposium on Physical designMay 2000 Pages 19–25https://doi.org/10.1145/332357.332368Published:01 May 2000Publication History 61citation699DownloadsMetricsTotal Citations61Total Downloads699Last 12 Months33Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the problem of finding an optimal clock schedule, i.e. optimal arrival times for clock signals at latches of a VLSI chip. We describe a general model which includes all previously considered models. Then we show how to optimize the cycle time and optimally balance slacks on data paths and on clocktree paths. The problem of finding a clock schedule with the optimum cycle time was solved before, either by linear programming or by binary search, using a test for negative circuits in a digraph as a subroutine. We show for the first time that a direct combinatorial algorithm solves this problem optimally. Incidentally, this yields a new efficient method for timing analysis with transparent latches. Moreover, we extend this algorithm to the slack balancing problem: To make the chip less sensitive to routing detours, process variations and manufacturing skew it is desirable to have as few critical paths as possible. We show how to find the clock schedule with minimum number of critical paths (optimum slack distribution) in a well-defined sense. Rather than fixed dock arrival times we show how to obtain as large as possible intervals for the clock arrival times. This can be considered as slack on clocktree paths. Indeed, we can find the global optimum of simultaneous optimization of slacks on all data paths and clocktree paths. All the above is done by very efficient network optimization algorithms, based on parametric shortest paths. Our computational results with recent IBM processor chips show that the number of critical paths decreases dramatically, in addition to a considerable improvement of the cycle time. The running times are reasonable even for the largest designs.