The timing-convergence problem arises because estimations made during logic synthesis may not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of this approach is that the existing placement solution is left intact throughout the optimization. A linear-time algorithm is proposed to detect functional symmetries in the Boolean network which are then used as the basis for rewiring. Integration with an existing gate-sizing algorithm further proves the effectiveness of our technique. Three applications are demonstrated: delay, power, and reliability optimization.

Redundancy addition and removal is a rewiring technique which, for a given target wire w/sub t/, finds a redundant alternative wire w/sub a/. The addition of w/sub a/ makes w/sub t/ redundant and, hence, removable without changing the overall circuit functionality. Incremental logic restructuring based on this technique has been used in many applications. However, in the earlier methods, the search for valid alternative wires required trial-and-error redundancy testing of a potentially large set of candidate wires. Here, we study the fundamental theory behind this technique and propose a new reasoning scheme (RAMFIRE), which directly identifies alternative wires without performing trial-and-error tests. Experimental results show speedup of up to 15 times than that of the best techniques in the literature.

The ultimate goal of logic synthesis is to explore implementation flexibility toward meeting design targets, such as area, power, and delay. Traditionally, such flexibility is expressed using "don't cares" and we seek the best implementation that does not violate them. However, the calculation and storing of don't care information is CPU and memory-intensive. In this paper, we give an overview of logic synthesis approaches based on techniques developed for Automatic Test Pattern Generation (ATPG). Instead of calculating and storing don't cares explicitly, ATPG-based logic synthesis techniques calculate the flexibility implicitly. Low CPU and memory usage make those techniques applicable for practical industrial circuits. Also, the basic ATPG-based logic level operations create predictable, small layout perturbations, making an ideal foundation for efficient physical synthesis. Theoretical results show that an efficient, yet simple add-a-wire-and-remove-a-wire operation covers all possible complex logic transformations.

The rapid advances in semiconductor manufacturing technology have created tough reliability problems. Failure mechanisms such as hot-carrier effect, dielectric breakdown, electrostatic discharge and electromigration have posed tremendous threats to the longterm reliability of VLSI circuits. As a result, designers not only need analysis tools to locate the problem, but also design-for-reliability tools to correct it. However, these problems often surface when the physical layout is done and relatively few logic changes can be made. In this paper, we target the performance optimization issues in the context of hot-carrier induced degradation. A layout driven approach combining rewiring, discrete gate resizing, and pin reordering is proposed. Experimental results show that rewiringbased incremental logic restructuring is a very powerful technique in post-layout design for reliability 1.

In-Place Optimization (IPO) has become the backend methodology of choice to resolve the gap between logic synthesis and physical design as the optimization can be guided by accurate physical information. To perform optimization without perturbing too much the placed netlist, only buffer insertion and gate sizing are commonly used in current design tools. In this paper, we address the problem of delay-constrained power optimization by introducing another degree of freedom: functional symmetry based rewiring. Theoretical results on the effect of using functional symmetry on transition density for power estimation is also derived. Experimental results show that, under the same delay constraint, our technique achieves much better power reduction as compared to the discrete gate sizing only technique.

Article Share on Who are the alternative wires in your neighborhood? (alternative wires identification without search) Authors: Chih-Wei Jim Chang Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA Department of Electrical and Computer Engineering, University of California, Santa Barbara, CAView Profile , Malgorzata Marek-Sadowska Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA Department of Electrical and Computer Engineering, University of California, Santa Barbara, CAView Profile Authors Info & Claims GLSVLSI '01: Proceedings of the 11th Great Lakes symposium on VLSIMarch 2001 Pages 103–108https://doi.org/10.1145/368122.368880Published:01 March 2001Publication History 13citation344DownloadsMetricsTotal Citations13Total Downloads344Last 12 Months6Last 6 weeks0 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 SiteGet Access

Redundancy-addition-and-removal is a rewiring technique which for a given target wire w/sub t/ finds a redundant alternative wire w/sub a/. Addition of w/sub a/ makes w/sub t/ redundant and hence removable without changing the overall circuit functionality. Incremental logic restructuring based on this technique has been used in many applications. However, the search for valid alternative wires requires trial-and-error redundancy testing of a potentially large set of candidate Wires. We study the fundamental theory behind this technique and propose a new reasoning scheme which directly identifies alternative wires without performing trial-and-error tests. Experimental results show up to 15 times speedup in comparison to the best techniques in literature.

Timing convergence problem arises when the estimations made during logic synthesis can not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of this approach is that the existing placement solution is left intact throughout the optimization. A linear time algorithm is proposed to detect functional symmetries in the Boolean network and is used as the basis for rewiring. Integration with an existing gate sizing algorithm further proves the effectiveness of our technique. Experimental results are very promising.

An array grid model based on single-track switches is proposed. A reconfigurability theorem is developed to provide the theoretical footing for novel reconfiguration algorithms for the fabrication-time and run-time processing. For fabrication-time yield enhancement, the problem of finding a feasible reconfiguration using global control can be reformulated as a maximum independent set problem. An existing algorithm in graph theory is adopted to solve this problem. The simulations conducted indicate that the algorithm is computationally very efficient; therefore, it may also be applicable to certain run-time fault tolerance. In real-time fault tolerance, the propagation time of data/control signals between the host computer incurred in the global control is often prohibitively long; therefore, only distributed processing is feasible. Based on the same reconfigurability theorem, a distributive reconfiguration algorithm is developed for (asynchronous) array processors.>