Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

As the variations of shrunk processes increasing at rapid rate, the performances of analog/mixed-signal chips remarkably fluctuate. It is necessary to take the yield as a design objective in design optimization. This paper presents a novel method to generate yield-embedded Pareto-front to simultaneously optimize both the yield and performances. Unlike the traditional approaches which generate the yield-aware Pareto-front to optimize performances for the fixed yield, this work embeds the yield as an objective of the optimization and evolutionarily optimizes both yield and performances by the so-called yield-embedded NSGA. The experiments demonstrate the gradual evolutions and global searching for the better performances and higher yields under PVT variations. The generation accelerated by parallel computations gains 4.8x speedup with 80% efficiency.

Simultaneous escape routing on dense circuit boards is a very challenging task and great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems.

This paper presents a new method using multi-objective optimization algorithm to automatically find the best solution from a topology library of analog circuits. Firstly this method abstracts the Pareto-front of each topology in the library by SPICE simulation. Then, the Pareto-front of the topology library is abstracted from the Pareto-fronts of topologies in the library followed by the theorem we proved. The best solution which is defined as the nearest point to specification on the Pareto-front of the topology library is then calculated by the equations derived from collinearity theorem. After the local searching using Nelder-Mead method maps the calculated best solution back to design variable space, the non-dominated best solution is obtained.

In this paper, an efficient framework is proposed to analyze the worst case of voltage variation of power network considering multidomain clock gating. First, a frequency-domain-based simulation method is proposed to obtain the time-domain voltage response. With the vector fitting technique, the frequency-domain responses are approximated by a partial fraction expression, which can be easily converted to a time-domain waveform. Then, an algorithm is proposed to find the worst-case voltage variation and corresponding clock gating patterns, through superimposing the voltage responses caused by all domains working separately. The major computation of the whole framework is solving the frequency-domain equation system, whose complexity is about$O(N^{\alpha}D\log f_{\max})$, where$\alpha$is between one and two if using an iterative solver from the PETSc library.$N$is the node number,$f_{\max}$is the upper bound of frequency, and$D$is the number of clock domains. Numerical results show that the proposed simulation method is up to several hundred times faster than commercial fast simulators, like HSPICE and MSPICE. In addition, the proposed method is able to analyze large-scale power networks that the commercial tools are not able to afford.

Statistical timing analysis (SSTA) is a method that calculates circuit delay statistically with process parameter variations, die-to-die (D2D) and within-die (WID) variations. In this paper, we model that WID parameter variations are independent for each cell and line in a chip and D2D variations are governed by one variation on a chip. We propose a new method of computing a full chip delay distribution considering both D2D and WID parameter variations. Experimental results show that the proposed method is more accurate than previous methods on actual chip designs.

This paper proposes an efficient method to find the worst case of voltage violation by multi-domain clock gating in an on-chip power network. We first present a voltage response in an arbitrary multi-domain clock gating pattern, using a superposition technique. Then, an integer linear programming (ILP) formulation is proposed to identify the worst-case gating pattern and the maximum variation area. The ILP based method is significantly faster than a conventional method based on enumeration. The experimental results are also compared with a case where peak voltage variation is induced, which shows the latter technique largely underestimated the overall variation effect.

This paper proposes an efficient analysis flow and an algorithm to identify the worst case noise for power networks with multiple clock domains. First, we apply the Laplace transform on the input current sources to derive the analytical formula. Then, we calculate the circuit frequency response with logarithmic scale frequency components. The frequency domain response is approximated by a rational function using vector fitting modeling. The rational function is used to derive the natural frequency of the power ground networks, and can be converted back into time domain easily. Based on the analysis results, we then present the worst case clock gating pattern algorithm to analyze the power networks with multiple clock domains. The most expensive part of the proposed algorithm is the matrix solving: O(F(N) ldr log f ldr D). Function F is the complexity of iterative solution of complex matrix with dimension N. We assume that there are D clock domains and the frequency spans from 0 to f Hz. Experimental results show that our method is up to 60X faster than HSPICE, and can analyze large circuits which are not affordable by HSPICE.

The notion of design for manufacturability is blurring the separation between the tasks of design and manufacture. In the era of nano-technologies, the description of the design rules has retreated back to an early stage form of many conditional cases and even an art. Thus, it is important to set the metrics for the manufacturability. However, who is going to be held accountable for the final outcomes? Should the designer, the EDA developer, the manufacture engineer, or a new breed of experts take the lead to tackle the problem?

In this paper, we present an efficient Iterative Improvement based Partitioning (IIP) algorithm called LSR/MFFS, that combines signal flow based Maximum Fanout Free Subgraph (MFFS) clustering algorithm with Loose and Stable net Removal (LSR) partitioning algorithm. The MFFS algorithm generalizes existing MFFC decomposition method from combinational circuits to general sequential circuits in order to handle cycles naturally. We also study the properties of the nets that straddle the cutline carefully, and introduce the concepts of the loose and stable nets as well as effective ways to remove them out of the cutset. The LSR/MFFS algorithm first applies LSR algorithm to clustered netlist generated by MFFS algorithm for global-level cutsize optimization and then declusters netlist for further cutsize refinement. As a result, the LSR/MFFS algorithm has achieved the best cutsize result among all the bipartitioning algorithms published in the literatures with very promising runtime performance. In particular, it outperforms the recent state-of-the-art IIP algorithms LA3-CDIP, CLIP-PROP/sub f/, Strawman, hMetis-FM, and MLc by 17.4%, 12.1%, 5.9%, 3.1%, and 1.9%, respectively. It also outperforms the state-of-the-art non-IIP algorithms Paraboli, FEB, and PANZA by 32.0%, 21.4%, and 1.4%, respectively.

A novel general routing algorithm is presented. Each net is routed to minimize the cost function defined by a weighted sum of penalties. Two types of design rule violations, touches and crosses, are factors of the cost function. Using these violations enables the algorithm to achieve 100% completion even when routing problems have nets which must be considered simultaneously. This type of problem could not be routed completely by conventional rip-up routers. The algorithm was implemented on a newly developed massively parallel computer. Experimental results on Burstein's difficult switch box problem and several small printed circuit boards show that the algorithm is as powerful as a human expert designer. >