Placement plays a crucial role in the timing closure of integrated circuit (IC) physical design. This paper presents an efficient and effective calibration-based differentiable timing-driven global placement engine. Our key innovation is a calibration technique that approximates a precise but expensive reference timer, such as a signoff timer, using a lightweight simple timer. This calibrated simple timer inherently accounts for intricate timing exceptions and common path pessimism removal (CPPR) prevalent in industry designs. Extending this calibrated simple timer into a differentiable timing engine enables ultrafast yet accurate timing optimization in non-linear global placement. Experimental results on various industry designs demonstrate the superiority of the proposed framework over the latest AMD Vivado and traditional net-weighting methods across key metrics including maximum clock frequency, wirelength, routability, and overall back-end runtime.

For crosstalk noise calculation, computing switching windows of a net helps us identify noise sources accurately. Traditional approaches use a single continuous switching window for a net. Under this model, signal switching is assumed to happen any time within the window. Although conservative and sound, this model can result in too much pessimism since in reality the exact timing of signal switching is determined by a path delay up to the net, i.e. the underlying circuit structure does not always allow signal switching at arbitrary time within the continuous switching window. To address this inherent inaccuracy of the continuous switching window, we propose a refinement of the traditional approaches, where signal switching is characterized by a set of discontinuous switching windows instead of a single continuous window. Each continuous switching window is divided into multiple windows, called time slots, and the signal switching activity of each slot is analyzed separately to calculate the maximum noise with more accuracy. By controlling the size of a time slot we can trade off accuracy and runtime, which makes this approach highly scalable. We have confirmed by experiments on industrial circuits that up to 90% of the noise violations detected by the traditional approach can be unreal.

Detecting overlapping of switching windows between coupling nets is a major static technique to accurately locate crosstalk noise. However, due to the mutual dependency between switching windows, the computation requires iterations to converge. In this paper, we discuss the issues and provide answers to the important questions involved in convergence and numerical properties, including the effect of coupling models, multiple convergence points, convergence rate, computational complexity, non-monotonicity, continuity and the effectiveness of bounds. Numerical fixed point computation results are used to explain these properties. Our contribution here builds a theoretical foundation for static crosstalk noise analysis.

A combinational module is a combinational circuit that can be used under any arrival time condition at the primary inputs. An intellectual property (IP) module, if combinational, is one such example. The false-path-aware delay characterization of a combinational module without disclosing its internal structural detail is crucial for accurate timing analysis of IP-based designs. We address three related issues on delay characterization of combinational modules. We first introduce a new notion called timing-safe replaceability as a way of comparing the timing characteristics of two combinational modules formally. This notion allows us to determine whether a new module is a safe replacement of an original module under any surrounding environment with respect to timing. Second, we consider false path detection of combinational modules. Although false path detection is essential in accurate delay modeling, we argue that the conventional definition of false paths such as floating mode analysis is not appropriate for defining the falsity of a path for a combinational module since the falsity is relative to an arrival time condition. A new definition of false paths, termed strongly false paths, is introduced to resolve this issue. Strongly false paths are those paths that are guaranteed to be false under any arrival time condition, and thus uniquely defined independent of arrival time conditions. Finally, we propose a new algorithm that removes strongly false paths from a combinational module by a circuit transformation. We prove that the resulting circuit is a timing-safe replacement of the original.

We propose a hierarchical timing analysis technique for combinational circuits under the tightest known sensitization criterion, the XBDO delay model. Given a hierarchical combinational circuit, a generalized delay model of each left module is characterized first. Since this timing characterization step takes into account false paths in each module, the delay model is more accurate than the one obtained by topological analysis. Then topological delay analysis is performed on the circuit composed of generalized gates replacing the leaf modules, where the “gate” delay model is the derived one. As far as the authors know, this is the first result that shows that hierarchical analysis is possible under state-of-the-art tight sensitization criteria. We demonstrate by experimental results that loss of accuracy in using the hierarchical approach is very minimal in practice. The theory developed in this paper also provides a foundation for incremental timing analysis under accurate sensitization criteria.

We propose an algorithm for minimal-delay technology mapping for library-based designs. We show that subject graphs need not be decomposed into trees for delay minimization; they can be mapped directly as DAGs. Experimental results demonstrate that significant delay improvement is possible by this new approach.

We present a new combinational verification technique where the functional specification of a circuit under verification is utilized to simplify the verification task. The main idea is to assign to each primary input a general function, called a coordinate function, instead of a single variable function as in most BDD-based techniques. BDDs of intermediate nodes are then constructed based on these coordinate functions in a topological order from primary inputs to primary outputs. Coordinate functions depend on primary input variables and extra variables. Therefore combinational verification is performed not over the set of primary input variables but over the extended set of variables. Coordinate functions are chosen in such a way that in the process of computing intermediate functions the dependency on the primary input variables is gradually replaced with that on the extra variables, thereby making Boolean functions associated with primary outputs simple functions only in terms of the extra variables. We show that such a smart choice of coordinate functions is possible with the help of the high-level functional specification of the circuit.

This paper addresses how to compute required times at intermediatenodes in a combinational network given required times atprimary outputs. The simplest approach is to compute them basedon topological delay analysis without any consideration of falsepaths. In this paper, however, we take into account false pathsbetween the intermediate nodes and the primary outputs explicitlyto characterize the timing constraints at the nodes more accurately.We show that this approach leads to a technique for computing amore refined and relaxed timing constraint than that obtained bytopological analysis. We generalize the notion of required timesfrom a single constant to a relation where a signal is required atdifferent times depending on the values of the other signals.

This paper is concerned with approximate delay computation algorithms for combinational circuits. As a result of intensive research in the early 90's efficient tools exist which can analyze circuits of thousands of gates in a few minutes or even in seconds for many cases. However, the computation time of these tools is not so predictable since the internal engine of the analysis is either a SAT solver or a modified ATPG algorithm, both of which are just heuristic algorithms for an NP-complete problem. Although they are highly tuned for CAD applications, there exists a class of problem instances which exhibits the worst-case exponential CPU time behavior. In the context of timing analysis, circuits with a high amount of reconvergence, e.g. C6288 of the ISCAS benchmark suite, are known to be difficult to analyze under sophisticated delay models even with state-of-the-art techniques. To make timing analysis of such corner case circuits feasible we propose an approximate computation scheme to the timing analysis problem as an extension to the exact analysis method proposed previously. Sensitization conditions are conservatively approximated in a selective fashion so that the size of SAT problems solved during analysis is controlled. Experimental results show that the approximation technique is effective in reducing the total analysis time without losing accuracy for the case where the exact approach takes much time or cannot complete.

A method to rectify lookup-table-type field-programmable gate array (FPGA) designs is presented. Instead of changing the netlist, only the functionality realized by lookup tables in a chip is modified and the netlist is retained so that there is no change in the delay of the chip. The problem is formalized using characteristic functions, and a redesign technique based on Boolean relations is presented.>

The authors present various applications of Boolean unification to combinational logic synthesis. Three topics of combinational logic synthesis are discussed: redesign, multilevel logic minimization, and minimization of Boolean relations. All of these problems can be uniformly formalized as Boolean unification problems. Experimental results are also reported.>

A practical design assistance system at the register transfer level is proposed. The unique characteristic of this system is that users are allowed to modify a register-level design manually. At first, the designer gives an initial behavioral description and an initial structure of a data path to be designed. The initial structure is formed through the designers' intuition. The final design is obtained by modifying the initial design manually. Consistency between the data path and its behavioral specification is verified automatically. The verifier was implemented and applied to an ASIC chip design.>