In this paper, we propose a new timing-driven detailed placement technique for FPGAs based on optimizing critical paths. Our approach extends well beyond the previously known critical path optimization approaches and explores a significantly larger solution space. It is also complementary to single-net based timing optimization approaches. The new algorithm models the detailed placement improvement problem as a shortest path optimization problem, and optimizes the placement of all elements in the entire timing critical path simultaneously, while minimizing the costs of adjusting the placement of adjacent non-critical elements. Experimental results on industrial circuits using a modern FPGA device show an average placement clock frequency improvement of 4.5%.

As integrated circuit technologies are scaled down to the nanometer regime, process variations have increasing impact on circuit timing. To address this issue, parameterized statistical static timing analysis (SSTA) has been recently developed. In parameterized SSTA, process variations are represented as random variables (RVs) and timing quantities (delays and others) are expressed as functions of these variables. Most of the existing algorithms to compute theMAX/MINoperations in parameterized SSTA model spatial and path-based statistical dependencies of variation sources using the second-order statistical methods. Unfortunately, such methods have limited capabilities to determine statistical relations between RVs. This results in decreasing the accuracy of theMAX/MINalgorithms, especially when process parameters follow non-Gaussian probability density functions (PDFs) and/or affect timing quantities nonlinearly. In contrast, information theory (IT) provides powerful techniques that allow a natural PDF-based analysis of probabilistic relations between RVs. So, in this paper, we propose a new framework to perform theMAX/MINoperations based on IT concepts. The key ideas behind our framework are: 1) exploiting information entropy to measure unconditional equivalence between an actualMAX/MINoutput and its approximate parameterized representation, and 2) using mutual information to measure equivalence of actual and parameterizedMAX/MINoutputs from the viewpoint of their statistical relations to process variations. We construct a general IT-basedMAX/MINalgorithm that allows a number of particular realizations accounting for statistical properties of parameterized RVs. The experimental results validate the correctness and demonstrate a high accuracy of the new IT-based approach to compute theMAX/MIN.

Subcircuit recognition (SR) is a problem of identifying instances of a small subcircuit in a larger circuit. Despite recent progress toward linear optimization-based SR algorithms, finding a large set of subcircuits in a multimillion transistor or gate-level netlist may still be too slow for many integrated-circuit computer-aided design applications. This paper describes a new high-performance method to identify subcircuits using a nonlinear graph optimization strategy. The method uses an advanced nonlinear technique to find a global minimum of the objective function associated with the SR problem. Unlike linear graph optimization, this method does not approximate the objective function by the first-order terms in its Taylor series expansion. In contrast, to increase the recognition rate, the second-order terms are exploited to form a set of nonlinear equations that describe the net and device match probabilities. Consequently, computing the match probabilities in the new approach is based on the nonlocal structure of connections between nets and devices. An iterative nonlinear version of the Kaczmarz method (KM) is used to solve the obtained set of nonlinear equations. The KM efficiency is improved by making an important modification in its updating scheme, which leads to fast and stable convergence of the recognition process. The experimental results show that the new method is on average three times faster than linear graph optimization algorithms such as the probabilistic match assignment algorithm

The recognition of subcircuit instances in a larger circuit is widely used in the simulation, verification, and testing of integrated circuit computer-aided designs. Subcircuit recognition (SR) can be stated as a problem of finding images of a small model bipartite graph (BG) corresponding to a subcircuit in a large object BG corresponding to a circuit. The best-known SR algorithms are based on the search-oriented subgraph isomorphism methods. Unfortunately, these methods may require a long runtime for large and highly symmetrical circuits. The authors develop a new high-performance probabilistic recognition method for solving the SR problem. This method combines: 1) the graduated assignment matching technique; 2) two well-known concepts from pattern recognition theory, namely, the error propagation and the delayed decision making; and 3) an efficient probabilistic BG labeling algorithm. In contrast to the search-based algorithms, the new recognition method solves the SR problem as an optimization task and, as a consequence, allows extremely fast simultaneous finding of subcircuit images. The experimental results show that this approach recognizes all the subcircuit instances orders of magnitude faster than the search-oriented algorithms.