The 2023 International Symposium on Physical Design lifetime achievement award goes to Professor Malgorzata Marek-Sadowska for her outstanding contributions to the field.

We investigate the effect of electrically induced thermal load on interconnect reliability and aging. We propose new models for uniform and non-uniform temperature evolution and its steady state distribution in interconnects considering Joule heating and heat convection. The models are verified by comparing the results against those of finite element experiments. We apply our models to study material migration induced aging and failures. We discuss how different non-uniform temperature profiles affect interconnect lifetime. We propose new formulas for accurate temperature aware assessment of the mortality of interconnects. We demonstrate that neglecting thermal effects in modern technologies may lead to incorrect conclusions about interconnect mortality. We also provide a method for modeling the true mean time to failure based on underlying physics.

In this paper, we study the main interconnect aging processes: electromigration, thermomigration and stress migration and propose comprehensive yet compact models for transient and steady states based on hydrostatic stress evolution. Our model can be expressed in terms of voltages only which abstracts away the hydrostatic stress. The model also explains some experimental observations, introduces temperature-dependent Blech's length criterion and a new time-to-failure formula replacing Black's empirical model. A tool is developed based on the proposed model which assesses reliability of multi-segment complex interconnect networks. Experimental results obtained on IBM benchmarks validate the model.

In this paper, we propose a current waveform estimation algorithm for signal lines without the necessity of SPICE simulation. Unlike previous methods, we do not use function fitting or compute the effective capacitance. Instead, the proposed algorithm predicts the current waveform by using current responses of a driver for multiple fixed capacitances provided by the foundry. We demonstrate usefulness of the proposed method for evaluating electromigration reliability of signal lines. Experimental results indicate excellent accuracy and run times as compared to the golden results obtained from SPICE.

Today many design houses must outsource their design fabrication to a third party which is often an overseas foundry. Split-fabrication is proposed for combining the FEOL capabilities of an advanced but untrusted foundry with the BEOL capabilities of a trusted foundry. Hardware security in this business model relates directly to the front-end foundry's ability to interpret the partial circuit design it receives in order to reverse engineer or insert malicious circuits. The published experimental results indicate that a relatively large percentage of the split nets can be correctly guessed and there is no easy way of detecting the possibly inserted Trojans. In this paper, we propose a secure split-fabrication design methodology for the Vertical Slit Field Effect Transistor (VeSFET) based integrated circuits. We take advantage of the VeSFET's unique and powerful two-side accessibility and monolithic 3D integration capability. In our approach the design is manufactured by two independent foundries, both of which can be untrusted. We propose the design partition and piracy prevention, hardware Trojan insertion prevention, and Trojan detection methods. In the 3D designs, some transistors are physically hidden from the front-end foundry_1's view, which causes that it is impossible for this foundry to reconstruct the circuit. We designed 10 MCNC benchmark circuits using the proposed flow and executed an attack by an in-house developed proximity attacker. With 5% nets manufactured by the back-end foundry_2, the average percentage of the correctly reconstructed partitioned nets is less than 1%.

In this paper, a fast, fully verifiable, and hardware predictable ASIC design methodology is proposed and demonstrated for the Vertical Slit FET (VeSFET) based integrated circuits. The key enablers of this methodology are the unique and powerful capabilities of pillar-based two-side accessible transistor arrays and monolithic 3D integration. VeSFET is a successfully fabricated transistor of this kind. In the proposed methodology, the circuit is first designed on a 3D FPGA platform using a conventional FPGA design flow. With a little extra Back End of Line (BEOL) masking cost, the design implemented on the 3D FPGA is migrated to the final 2D ASIC, which has exactly the same performance and the verification tasks performed on the 3D FPGA platform remain valid for the final 2D ASIC. The 2D ASIC has the same layout as the silicon-proven 3D FPGA, which greatly mitigates the unpredictable factors of fabrication. The proposed methodology retains all the benefits of FPGA design flow. Eleven MCNC benchmark circuits were implemented. Comparing to the 2D FPGA, the performance of the final 2D ASIC implementation as well as the performance of the 3D FPGA design platform are on average 15% faster, consume 17% less power and 44% less area.

Electromigration (EM) greatly affects the long-term reliability of VLSI chips. Not only power/ground lines but also bitlines of SRAM arrays may be damaged by EM. In this paper, we analyze current flow on SRAM bitline, demonstrate that it may suffer EM due to the pulsed dc pattern, and conclude that bitline's EM reliability can dramatically be worsened by process variation due to a significant increase of subthreshold leakage current. We statistically model the effects of process variation that includes both transistor parameter fluctuation and interconnect line roughness, propose an atomic flux divergence-based current conversion scheme for applying Blech criterion, and develop a procedure for preventing EM failure by modifying the width of bitlines. Considering the effect of bitline width modification on cell stability and performance, we propose a tradeoff between functional and EM failures and indicate an optimal bitline width that maximizes the yield of SRAM arrays.

The majority of the existing experimental, theoretical and modeling works on electromigration (EM) are focused on simple, via-to-via structures, but complex interconnect structures have not been studied well. The lack of correct models for such interconnects may result in either conservative or weak design decisions which may result in catastrophic reliability failures. This paper proposes a physical model which holds for material migration as well as for lattice vacancy generation/annihilation. Using the developed model, well known circuit level EM assessment methods are examined by finite element modeling and simulation. The paper provides a compact model for EM analysis which can be easily implemented in CAD tools. We also explain some recent experimental results and empirical models published by other researchers.

This paper describes two separate learning flows for improving the efficiency of simulation-based design analysis. Machine learning concepts and methods are explained in the context of realizing the two learning flows. Experimental results are presented to demonstrate their feasibility. Generality of the proposed learning flows is illustrated using the kernel-based learning concept.

Electromigration (EM) has become a major power grid reliability problem in VLSI. In this paper, we first demonstrate that EM reliability analysis of a power grid can be converted to analyzing EM reliability of the grid vias. We develop a model for calculating EM lifetime of via-arrays and observe that making power grid EM-immortal carries a huge metal area overhead and possibly makes routing of both power and signal networks too difficult to complete. We propose a method for trading off power grid integrity and reliability to minimize the total metal area overhead needed to achieve the desired grid life time under power integrity constraints. Experimental results show that using our method, both EM reliability and power integrity can be met, while the additional metal area used is significantly reduced.

In this brief, a temperature- and variation-aware electromigration analysis (T-VEMA) tool for power grid wires is described. First, T-VEMA performs a two-stage interconnect thermal analysis on a full chip. Next, the tool extracts the effective jL product values and performs an electromigration (EM) lifetime calculation on ideally manufactured mortal wires on the basis of thermal effects. Finally, T-VEMA analyzes process variation effects on EM reliability at global and local levels and reports variation tolerances of EM-sensitive power grid wires.

Thermal management becomes a huge challenge for modern IC designers, especially when chips go 3-D. Vertical slit field-effect transistor (VeSFET) technology provides an alternative thermal-friendly design choice. VeSFET-based chips not only have a much lower power density but also a better vertical thermal conductivity than their CMOS counterparts. For a VeSFET chip with ten stacked dies, the temperature increase is only 30% of that for CMOS-based chip. Assuming the same scaling trend for CMOS and VeSFET, VeSFET 3-D chips can postpone the appearance of dark silicon by three technology nodes compared with CMOS implementations. For VeSFET-based designs, different topologies of transistor arrays may result in different thermal behaviors. We perform thermal characterization of two-transistor array topologies.

Conventional, pre-RTL SoC architectural design space exploration does not account for the chip's floorplan. However, the power and performance of integrated CPU-GPUs are highly dependent not only on architectural specifications and workload characteristics but also on the underlying floorplan. We develop a floorplanaware system-level analysis framework for integrated CPU-GPUs and demonstrate that the overall energy efficiency can be over/under estimated by up to 25% when floorplan is not accounted for. The floorplan-aware system-level exploration tool allows us to observe interesting dependencies between architectural choices and physical design. These observations guide the framework in determining energy efficient floorplans for wide-range of workloads.

In this paper, we demonstrate that standard cell design methodology can be applied to design vertical slit field effect transistor (VeSFET)-based ASICs with modern CMOS EDA tools. We study a family of VeSFET canvases-chain canvases that improve performance and power consumption of circuits mapped to them compared to circuits implemented with VeSFET canvases composed of isolated transistors. We compare the designs implemented with a commercial low power CMOS library and corresponding VeSFET libraries. VeSFET-based designs demonstrate significant power reduction as compared to the CMOS-based designs at the same performance.

Medium volume VeSFET-based ASICs can fill the gap between high cost microprocessors and low performance FPGAs. Circuits can be customized onto pre-manufactured VeSFET canvases by properly designed interconnects. In this paper, we propose chain canvases, a family of VeSFET canvases for which CMOS-oriented EDA tools can be easily adapted. Footprint area, wire length, via usage, performance and power are compared between chain canvas- and basic canvas-mapped benchmarks. Experimental results show that chain canvas-mapped circuits outperform those mapped to basic canvases.

Footprint scaling may reduce wire lengths when more metal layers are available for routing. To achieve optimal wire length, footprint should be very small in which case pin density will be extremely high. However, high pin density may lead to detailed routing failure. We demonstrate that there is a threshold pin density beyond which standard routing heuristics fail to access pins on the bottom layer, even with unlimited number of metal layers available for routing. Future technologies, such as vertical slit field-effect transistor (VeSFET), may have layouts with pin density exceeding the threshold. We show that VeSFET layouts are still routable within footprint using two-sided routing. Compared to one-sided routing, two-sided routing achieves shorter wire lengths and fewer vias, hence lower interconnect capacitance and better performance.

If pin density exceeds a certain threshold, pin access becomes a challenge for inter-cell signal routing and increasing the number of metal layers cannot improve routability. CMOS and FinFET layouts may never reach this threshold, but Vertical Slit Field Effect Transistor (VeSFET) ICs may exceed it. We demonstrate that VeSFET layouts are still routable within footprint using two-sided routing which achieves better wire length and via usage than one-sided routing with or without white space inserted.

Printability of layout objects becomes increasingly dependent on neighboring shapes within a larger and larger context window. In this paper, we propose a two-level hotspot pattern classification methodology that examines both central and peripheral patterns. Accuracy and runtime enhancement techniques are proposed, making our detection methodology robust and efficient as a fast physical verification tool that can be applied during early design stages to large-scale designs. We position our method as an approximate detection solution, similar to pattern matching-based tools widely adopted by the industry. In addition, our analyses of classification results reveal that the majority of non-hotspots falsely predicted as hotspots have printed CD barely over the minimum allowable CD threshold. Our method is verified on several 45 nm and 32 nm industrial designs.

Fine grain 3D integration of commonly used components appears to be an attractive architectural solution. But finely partitioned, highly regular blocks face unique layout level challenges due to uneven scaling of Through Silicon Vias (TSVs) and circuit elements. We show that for high yielding TSVs and decreasing transistor sizes, the mismatch between the TSV dimension and the feature size affects the outcome of 3D design space exploration, especially for fine grain partitioned, highly regular microprocessor blocks such as SRAM registers and caches. For a 4-layer implementation of an SRAM register in 45nm technology, we show that improving the TSV yield from 20% to 90% requires layout modifications that worsen register's performance up to four times. Moreover, the same 4-layer register that performs three times as fast as its single layer equivalent at 20% yield becomes twice slower at 70% yield when layout effects are considered. We also explore some non-conventional physical design schemes for 3D architectural blocks in which performance deterioration is much slower even for very high TSV yields.

Due to shrinking wire dimensions, higher current density, and process variations, electromigration (EM) has become a major reliability problem. The existing backend design flows use the maximum allowed current density as the only practical guidance to prevent EM. There is a need for tools capable of performing comprehensive EM analyses. In this paper, we first explain why current density alone does not determine wire's susceptibility to EM. We introduce our variation-aware EM analysis tool, VEMA, for power/ground networks, which are typically the EM-critical parts of a chip. Our tool considers two types of variations: circuit-level and wire geometry-level. VEMA reports distributions of wire lifetimes for circuit-level variations. Compared to existing EM analyzer SysRel, VEMA filters out EM-immortal wires more efficiently and provides detailed feedback for EM violation corrections. VEMA also provides information of geometry-level tolerance for EM-mortal wires.

Long wires degrade significantly the performance of network-on-chip (NoC) communication fabric in large multicore processors. 3D network-on-chip architecture alleviates the problem of long wires, but practical limitations of CMOS technology restrict such structures to two active layers only. In this work, we study a heterogeneous 3D chip with processor cores and cache blocks implemented in CMOS and NoC fabric in VeSFET technology. Such a 3D architecture shows significant improvements in all network parameters including latency, power and energy consumption compared to existing 3D NoCs.

The objective of this paper is to commemorate Professor Ernest S. Kuh's contributions to EDA and to bring attention to his research group's many accomplishments in physical design area. The focus is on routing and our goal is to trace the effects that the ideas which originated in Kuh's group have had on researchers then and now.

In this paper, we study circuits implemented using high-density arrays composed of vertical slit field effect transistors. This layout style could dramatically increase transistor density and, therefore, reduce fabrication cost. However, its geometrical restrictions, imposed by the super-regular transistor arrangement and strictly parallel metal tracks, pose new design challenges. Our experiments reveal that very dense cell-level interconnect pattern may be responsible for unnecessary 15% increase of the circuit level, critical path delays. We demonstrate that these extra delays can be avoided by constructing appropriate cell interconnect layouts and by more flexible usage of available metal layers for intra-cell routing. To balance the performance and metal layer usage, we propose a linear programming-based technique for critical net re-routing.

In many designs, the worst-case delay of a critical path may be activated infrequently. Traditional optimization approaches assume the worst-case conditions, which could lead to an inefficient resource usage. It is possible to improve the throughput of such designs by introducing variable latency. One existing realization of the variable-latency design style is based on telescopic units. The design of the hold logic in telescopic units influences the circuit's throughput. In this paper, we show that the traditionally designed hold logic may be inaccurate. We use the short path activation conditions to obtain more accurate hold logic and improve the efficiency of telescopic units. To reduce the overhead for large circuits, we propose an efficient heuristic methodology of constructing non-exact hold logic. We also discuss how to choose the telescopic unit's timing constraint. On average, our approach achieves the performance gain of 21.67% compared to 13.99%, reported in the previous work.

Power gating is an efficient technique for reducing the leakage power of electronic devices by disconnecting the power supply from blocks idle for long periods of time. Disconnecting gated blocks causes changes in the current densities of the grid branches and vias. For some gating configurations, dc current densities may increase in some grid locations to the extent that they violate electromigration (EM) constraints. In this paper, we analyze the EM and infrared (IR) voltage drop effects in gated global power grids. Based on our analyses, we develop a global grid sizing algorithm to satisfy the reliability constraints on grid branches and vias for all feasible gating configurations. Our experimental results indicate that a grid initially sized for all blocks connected to it may be modified to fulfill EM and IR constraints for multiple gating schedules with only a small area increase.

As the industry moves from single- to multicore processors, the challenges of how to reliably design and analyze power delivery for such systems arise. We study various workload assignments to cores and their effect on the global power supply noise and ground bounce. We provide a detailed analysis of single and multiple cores and develop analytical formulas to capture the power supply noise and ground bounce of the system. We introduce metrics to estimate the amount of noise propagated from core to core and propose a supply noise aware workload assignment method. In our experiments, we show that timing constraints can be significantly affected if workload assignments are not properly made.

In this paper, we study circuits implemented using high-density arrays composed of Vertical Slit Field Effect Transistors. This layout style could dramatically increase transistor density and therefore reduce fabrication cost. However, its geometrical restrictions, imposed by the super-regular transistor arrangement and strictly parallel metal tracks pose new design challenges. Our experiments reveal that very dense cell-level interconnect pattern may be responsible for unnecessary 15% increase of the circuit-level, critical path delays. We demonstrate that these extra delays can be avoided by constructing appropriate cell interconnect layouts and by more flexible usage of available metal layers for intra-cell routing. To balance the performance and metal layer usage, we propose a linear programming-based technique for critical net re-routing.

In this paper, we describe an automatic place and route strategy for a high-density, super-regular, double-gate, transistor-array-based layout. Interconnects on all metal layers are strictly parallel and can be manufactured by an optical proximity correction free process. Our objective is to achieve a circuit layout area equal to the transistor footprint. Such layout constraints limit routing flexibility and render traditional approaches impractical. Our tools automatically generate circuits with several tens of transistors. Experimental results demonstrate both the efficiency of the proposed algorithms and the high quality of the layouts produced.

International audience

In this paper, we describe an automatic place and route strategy for a high-density, super-regular, double-gate transistor-array-based layout. Interconnects on all metal layers are uni-directional and can be manufactured by an OPC-free process [4]. Our objective is to achieve a circuit layout area equal to the transistor footprint. Such layout constraints limit routing flexibility and render traditional approaches impractical. Our tools automatically generate circuits with several tens of transistors. Experimental results demonstrate both the efficiency of the proposed algorithms and the high quality of the layouts produced.

Engineering change (EC) is the process of modifying a VLSI design implementation to eliminate design errors, to add new specifications, or to correct design constraint violations. Usually, an EC problem is resolved by using spare cells that have been inserted into unused spaces on a chip. In this paper, we describe an iterative method to determine feasible mapping solutions for an EC problem considering spare cells whose inputs can be connected toVddorGnd. Setting some of the cell inputs to fixed values is referred to asconstantinsertion. Constant insertion can increase cells' functional flexibility. Our experimental results suggest that constant insertion reduces the area required to find a feasible mapping solution to 80% of that with no constant insertion for the selected EC equations. We also show a procedure for modifying the initial feasible EC solution such that the routing or timing improves.

With feature sizes steadily shrinking, manufacturing defects and parameter variations often cause design timing failures. It is essential that those errors be correctly and quickly diagnosed. In this paper, we analyze the multiple-delay-fault diagnosis problem and propose a novel approach to solve it. We enhance the diagnostic resolution by processing failure logs at various slower-than-nominal clock frequencies. We evaluate the utility ofn-detection and timing-aware automatic-test-pattern-generated (ATPG) sets. Experimental results show that using timing-aware ATPG sets yields better diagnostic resolution and results in better delay-defect-size estimations compared ton-detection ATPG sets. We experimentally determined our diagnosis algorithm's sensitivity to delay variations.

Power gating is a technique for efficiently reducing leakage power by disconnecting idle blocks from the power grid. When gated blocks are woken up, large amounts of switching currents are drawn in a short period of time that may introduce severe noise on the power delivery mesh. In this paper, we propose a GA-based approach to schedule power gating considering power/ground noise. We introduce a simulation-based method to accurately and efficiently estimate the worst case noise, taking all the current sources, inductance and decaps' effects into consideration. We also present an incremental scheduling procedure considering the dynamic changes of decap configuration. Experimental results show that by optimally scheduling the wake-up order under time constraints, our technique can reduce noise up to 50% compared to waking gated blocks simultaneously. The quality of results depends upon the total wake-up time constraint, locations of gated blocks, current densities of gated blocks, and decap distribution.

As the industry moves from single- to multicore processors, the challenges of how to reliably design and analyze power delivery for such systems also arise. We study various workload assignments to cores and their impact on the global power grid noise. We develop metrics to estimate the amount of noise propagated from core to core and propose a power supply noise aware workload assignment method. In our experiments, we show that performance loss can be significant if workload assignment is not properly made.

In this paper, we study the circuits built from super-regular, high-density transistor arrays that can be prefabricated and customized using an OPC-free interconnect manufacturing process. The super-regular layout style greatly enhances the chippsilas manufacturability. Unlike other regular fabrics that sacrifice area and performance to improve regularity, the new layout style, combined with a new 3-D geometry transistor, enables to produce circuits with timing and power density comparable to or better than that of conventional CMOS circuits and using less chip area.

With transistor mask costs soaring and the delays associated with full design re-spins escalating, post-mask Engineering Change Orders (ECOs) - design changes after the masks have been prepared - are increasingly carried out by keeping transistor masks intact and revising only the metal masks. In this paper, we propose a novel design flow for achieving technology remapping for post-mask ECOs. In contrast to conventional technology mapping and placement algorithms that have no notion of the quantity for each gate type and the location of placed spare/recycled cells, our flow ECO-Map provides an ideal scalable framework for achieving global optimization in a post-mask ECO scenario. Given the changed logic due to a functional ECO and a limited number of placed spare/recycled cells, ECO-Map finds a resource-feasible Boolean cover and optimally fits the changed logic into the available resources. This ensures minimal perturbation of the existing solution and keeps transistor masks intact, thus reducing non-recurring engineering (NRE) costs. Experiments performed on MCNC benchmarks show the effectiveness of our approach.

In this paper, we present a reliability study of clock mesh distribution networks. We analyze the electromigration (EM) phenomena and demonstrate their occurrence in clock mesh networks (CMN). Due to shrinking feature sizes in more advanced technologies, EM is becoming a more prominent reliability issue. Process variation, power supply noise, and clock gating are some of the factors that can increase electromigration in the clock mesh. We identity the potential EM branches by investigating current flows under various conditions. Our study shows that a clock mesh optimized for certain configurations of clock sinks may experience electromigration due to asymmetrical bidirectional currents flowing in some grid segments.

IR drop noise has become a critical issue in advanced process technologies. Traditionally, timing analysis in which the IR drop noise is considered assumes a worst-case IR drop for each gate; however, using this assumption provides unduly pessimistic results. In this paper, we describe a timing analysis approach for power gating designs. To improve the accuracy of the gate delay calculation we determine the virtual voltage level by taking into account the IR drop waveforms across the sleep transistors. These can be obtained efficiently using a linear programming approach. Our experimental results are very promising.

With feature sizes steadily shrinking, manufacturing defects and parameter variations often cause design-timing failures. It is essential that those errors be correctly and quickly diagnosed. The existing delay-fault diagnosis algorithms cannot identify delay faults that require nonrobust test patterns due to incorrect emulation of the failure analyzer's behavior. We propose a novel approach to performing delay-fault diagnosis for robust and nonrobust tests. We enhance the diagnostic resolution by utilizing passing patterns, processing failure logs at various slower frequencies, and applying n-detection and timing-aware automatic test pattern generation sets. Experimental results show that our approach can diagnose delay faults with good resolution. The algorithm is stable with respect to delay variations that manufactured chips might experience.

Advancements in IC manufacturing technologies allow for building very large devices with billions of transistors and with complex interactions between them encapsulated in a huge number of design rules. To ease designers' efforts in dealing with electrical and manufacturing problems, regular layout style seems to be a viable option. In this paper we analyze regular layouts in an IC manufacturability context and define their desired properties. We introduce the OPC-free IC design methodology and study properties of cells designed for this layout style that have various degrees of regularity.

In many designs, the worst-case-delay path may never be exercised or may be exercised infrequently. For those designs, a strategy of optimizing a circuit for the worst-case conditions could lead to inefficient resource use. It is possible to improve the throughput of such circuits by introducing variable latency. One of the existing realizations of variable-latency design style is based on Telescopic Units. The design of the hold logic in telescopic units influences the circuit's throughput. In this paper, we show that the traditionally-designed hold logic in telescopic units may be inaccurate. We make use of the short path activation conditions to obtain more accurate hold logic than that commonly applied in the telescopic units. On average, our approach achieves a performance gain of 25.79% compared to 14.04%, which was reported in the previous works.

In the VLSI design process, a design implementation often needs to be corrected because of new specifications or design constraint violations. This correction process is referred to as engineering change (EC). Usually, an EC problem is resolved by using spare cells, which have been inserted into the unused spaces of a chip. In this paper, we propose an iterative method to generate feasible mapping solutions for an EC problem considering spare cells whose inputs may be tied to Vdd or Gnd, called constant insertion. Applying constant insertion can increase a cell's flexibility in aspect of functionalities, so far-away spare cells need not be used just for some specific functionality. Our experimental results show that the area in which there are enough spare cells for a mapping solution with constant insertion is only 82% of the area without constant insertion.

Power gating is an efficient technique for reducing leakage power in electronic devices by disconnecting blocks idle for long periods of time from the power supply. Disconnecting gated blocks causes changes in densities of currents flowing through a grid. Even in DC conditions, current densities in some grid branches may increase for some gating configurations to the extent of violating electromigration (EM) constraints. The existing DC methods for grid sizing optimize the grid area under voltage drop (IR) and EM constraints for one configuration of circuit blocks connected to the grid. We show that these methods cannot be directly applied for optimizing power-gated grids. We analyze the effects of EM and IR voltage drop in power grids with multiple power gating configurations. Based on our analyses, we develop a grid sizing algorithm to satisfy all reliability constraints for all feasible gating configurations. Our experimental results indicate that a grid initially sized for all blocks present may be modified to fulfill EM and IR constraints for multiple gating schedules with only a small area increase.

Power gating is an efficient technique for reducing leakage power by disconnecting idle blocks from power supply. Gated blocks cause changes in current densities on the grid. Even in DC conditions for some power gating configuration (PGC), current densities in some branches may increase to the extent of violating electromigration (EM) constraints. The existing DC methods optimize the grid under voltage drop (IR) and EM constraints for a single configuration of blocks. We analyze the effects of power gating and develop a grid sizing algorithm to satisfy all reliability constraints for multiple PGCs with only a small increase in area.

We describe a placement-level decoupling capacitance (decap) insertion technique whose objective is to reduce power noise, taking into account circuit timing. Our approach consists of prediction and correction steps. Before placement, we estimate the power noise of each cell considering switching frequency of cells that, after placement, will most likely be in the neighborhood. If a frequently switching cell has neighbors that switch infrequently, it is unlikely that this cell will suffer from a power-noise problem. Based on the cell power-noise estimation, we add decap padding to each cell. Then, we invoke a standard cell placement tool and perform power grid analysis. We eliminate the power grid noise by gate sizing. Our technique can allocate decaps to improve power noise, power consumption, and timing. We propose two gate-sizing algorithms. The first one uses a sequence of linear programs (SLP) formulation, and the second one uses a budgeting-based heuristic algorithm. The SLP algorithm can produce better power-noise results than the heuristic, at the expense of runtime. Experimental results show that our techniques can effectively reduce power noise and still meet timing constraints

Power-gating is a technique for efficiently reducing leakage power by shutting off the idle blocks. However, the presence of power-gating may also introduce negative effects on power supply network, which have not been considered in the earlier design stages. Ignoring those effects may result in suboptimal power supply network designs and could potentially even nullify the intended power savings. In this paper, we analyze mutual dependencies between the sleep transistors and the P/G network, and we present a general flow to optimize the P/G supply network for power-gating. Experimental results show that sizing sleep transistor and power network separately cannot achieve optimal solution in terms of power. By compromising only 1% of the total area, our optimization method allows us to save 10% of power dissipated on decaps and sleep transistors, which is a practical solution for a power-gated system. We also report results of a study on optimal solutions for various gated areas and current densities.

With feature sizes shrinking, manufacturing defects and parameter variations often cause design timing failures. Crosstalk coupling is one of such causes. It is essential that timing failures be correctly and quickly diagnosed. The authors present a methodology to diagnose the delay-defect in presence of crosstalk, given the physical information such as crosstalk coupling capacitance, neighborhood information and SDF delay information. The authors provide diagnosis results for 180, 130, 90 and 65 nm technologies

A new concept for wire-length prediction, the semi-individual wire-length prediction, is introduced. Structural metrics, such as mutual contraction and net range, are used to predict which interconnects have a tendency to be long or short in the final layout. The very good correlation of the prelayout measures with the postlayout interconnect lengths is demonstrated. The prelayout wire-length-prediction techniques are applied in logic synthesis, targeting wiring cost, and congestion minimization. This paper focuses on technology mapping and fan-out optimization. Experiments on LGSyn93 and ITC'99 benchmark suites show that the wire-length-prediction-based technology mapping and fan-out-optimization algorithms produce layout-friendly netlists. After placement and global routing, the netlists yield smaller total wire length, are more routable, and achieve better timing than the netlists obtained using traditional logic-synthesis flow in SIS.

In this paper, we propose a multiple-fault-diagnosis methodology based on the analysis of failing patterns and the structure of diagnosed circuits. We do not consider the multiple-fault behavior explicitly, but rather partition the failing outputs and use an incremental simulation-based technique to diagnose failures one at a time. Our methodology can be further improved by selecting appropriate diagnostic test patterns. The n-detection tests allow us to apply a simple single-fault-based diagnostic algorithm, and yet achieve good diagnosability for multiple faults. Experimental results demonstrate that our technique is highly efficient and effective. It has an approximately linear time complexity with respect to the fault multiplicity and achieves a high diagnostic resolution for multiple faults. Real manufactured industrial chips affected by multiple faults can be diagnosed in minutes of central processing unit (CPU) time.

In this paper, we describe the design process of a via-configurable logic block for regular fabric. The block consists of a via-configurable functional cell and two via-configurable inverter arrays. A via-configurable functional cell can efficiently implement most commonly used CMOS static cells, and a via-configurable inverter array is efficient in implementing inverters, repeaters, and some pass-transistor logic. The cells have prefabricated transistors, contacts, and M1 wires. The M2 mask is fixed. All of the functions can be realized by customizing only an M1-M2 via mask. We construct a general-purpose fabric based on the via-configurable block and show its great flexibility in implementing a variety of functions. Compared to other fabrics based on look-up tables or programmable logic arrays, our fabric has much higher performance, smaller area, and lower power consumption.

In this paper, we describe a new via-configurable routing architecture which shows a much better throughput and performance than the previous structures. We demonstrate how to construct a single-via-mask fabric to reduce the mask cost further, and we analyze the penalties which it incurs. To solve the routability problem commonly existing in fabric-based designs, an efficient white-space allocation and an incremental cell movement scheme are suggested, which help to provide a fast design convergence and early prediction of circuit's mappability to a given fabric

In this paper, we propose a skew-programmable clock-routing architecture. The skews can be adjusted using programmable delay elements (PDEs) which we insert into the clock trees. We develop efficient, shortest-path-based algorithms for programming PDEs to optimize timing. Unlike previous methods for FPGA skew optimization which require large power and routing penalty, our method can achieve large timing improvement with small overhead. Typically, if timing requirements are tight, placers make efforts to satisfy them, often at a cost of compromising routability, total wire length, and power. In this work, we propose novel clock-skew-aware placement algorithms which allow us to relax the timing constraints during placement. Timing can be later optimized as a post process. Even though we demonstrate the efficiency of our approach using FPGAs, the new skew optimization method and the new placement algorithm are quite general and can be applied to any general, topology-constrained skew optimization problem. Experimental results indicate that using the new clock-architecture we can obtain a 22% timing improvement for post-layout skew optimization and an additional 21% improvement from our skew-aware placement algorithm. In one fabric, the cost of added logic is 2.19% as measured by dynamic power dissipation, and 0.85% in terms of area overhead.

In this paper, we address the problem of estimating clock-skew bounds in presence of power supply and process variations. We present a novel technique based on sequence of linear programs to compute the upper and lower bounds of clock skew. We apply our method to pairs of sinks between which logic paths in the circuit exist. When spatial correlations of process variations are known, our method provides more accurate results which reflect the real design. We use accurate models and time-domain analysis ts calculate the clock network delay and delay sensitivity. The experimental results demonstrate that our technique is capable of providing very accurate skew bounds estimation (within 10% error as compared to Monte-Carlo method) in acceptable run-times.

In this paper, we present a novel congestion-driven placement methodology. We analyze netlist structure and perform local congestion prediction to determine the amount of white space which will be attached to each cell. We place the modified netlist using a total-wire-length-driven placer and obtain an initial legal placement. We extract the congestion information and determine the target white space distribution. Finally, we apply placement migration, an incremental placement technique, to transform the initial placement into a placement which satisfies the target white space distribution. We provide experimental data to demonstrate the effectiveness of our congestion driven placement framework. Compared with the recent academic routability-driven placer Dragon [12], we achieve significant routability improvements in much shorter cpu run time.

In this paper, we describe a new via-configurable routing architecture which shows much better throughput and performance than the previous structures. We demonstrate how to construct a single-via-mask fabric to reduce further the mask cost, and we analyze the penalties which it incurs. To solve the routability problem commonly existing in fabric-based designs, an efficient white-space allocation scheme is suggested, which provides a fast design convergence and early prediction of the circuit mappability to a given fabric.

In this paper, we propose a timing-aware power-noise reduction technique. Our approach consists of prediction and correction steps. Before placement, we estimate the power noise of each cell considering switching frequency of cells which, after placement, will most likely be in the neighborhood. If a frequently switching cell has neighbors which switch infrequently, it is unlikely that this cell will suffer from a power noise problem. Based on the cell power noise estimation, we add decap padding to each cell. Then we invoke a standard cell placement tool and perform power grid analysis. We eliminate the power grid noise by gate sizing. Our technique can reallocate decaps to improve power noise, power consumption, and timing. The gate sizing is based on the sequence of linear programs (SLP) formulation, and it can be solved efficiently. Experimental results show that our techniques can effectively reduce power noise and meet timing constraints.

Power-gating is a technique for saving leakage power by shutting off the idle blocks. However, without good understanding and careful design, negative effects of power gating may overwhelm the potential gain and may make the technique not worth the effort. In this paper, we report on our study of the benefits and costs of the power-gating technique in terms of power, area, and performance. We model and analyze several strongly related parameters such as sleep-transistor size, decap area, and supply voltage level. We also report on our experiments to demonstrate how the gated area, circuit behavior and power mesh granularity affect the power gating technique at the system level. Experimental results show that, by compromising 4% of the total area and 5% of the dynamic power, we can achieve 47% leakage power saving while maintaining the same performance. With technology scaling down, the saving is significant. We conclude that we can benefit from the power-gating technique in future technology nodes.

In this paper, we introduce a structural metric, logic contraction, for pre-layout physical connectivity prediction. For a given set of nodes forming a cluster in a netlist, we can predict their proximity in the final layout based on the logic contraction value of the cluster. We demonstrate a very good correlation of our pre-layout measure with the post-layout physical distances between those nodes. We show an application of the logic contraction to circuit clustering. We compare our seed-growth clustering algorithm with the existing efficient clustering techniques. Experimental results demonstrate the effectiveness of our new clustering method.

A placement problem can be formulated as a quadratic program with non-linear constraints. Those constraints make the problem hard. Omitting the constraints and solving the unconstraint problem results in placement with substantial cell overlaps. To remove the overlaps, we introduce fixed points into the non-constrained quadratic-programming formulation. Acting as pseudo cells at fixed locations, they can be used to pull cells away from the dense regions to reduce overlapping. In this paper, we present a large-scale placement algorithm based on fixed-point addition.

In modern VLSI systems early wire optimization is essential in achieving required performance, routability, and power. The cost functions optimized during traditional logic synthesis do not capture interconnect effects, which may lead to sub-optimal designs. In this paper, we propose a method for applying pre-layout wire-length prediction techniques in logic synthesis, targeting wiring cost and ways to minimize congestion. Specifically, we focus on technology mapping and fanout optimization. Experimental results show that our wire-length-prediction-based technology mapping (WP-Map) and fanout optimization (WP-Fanout) result in 8.7% improvement in average congestion, 17.2% improvement in peak congestion, and 3.3% improvement in timing performance.

A placement problem can be formulated as a quadratic program with nonlinear constraints. Those constraints make the problem hard. Omitting the constraints and solving the unconstrained problem results in a placement with substantial cell overlaps. To remove the overlaps, we introduce fixed points into the nonconstrained quadratic-programming formulation. Acting as pseudocells at fixed locations, they can be used to pull cells away from the dense regions to reduce overlapping. We present an in-depth study of the placement technique based on fixed-point addition and prove that fixed points are generalizations of constant additional forces used previously to eliminate cell overlaps. Experimental results on public-domain benchmarks show that the fixed-point-addition-based placer produces better results than the placer based on constant additional forces. We present an efficient multilevel placer based upon the fixed-point technique and demonstrate that it produces competitive results compared to the existing state-of-the-art placers.

In this paper, we examine the relationship between netlist structure and the efficiency of placers measured in terms of quality and stability of results. We analyze three types of placers: analytic, simulated-annealing based, and partition based. We have tested these placers on industrial and synthetic benchmarks. Based on our observations and analyzes of experimental results, we draw several useful conclusions: 1) Various placers favor netlists with different structural characteristics; 2) placement efficiency correlates with interconnection complexity of the circuits; 3) global nets increase the effort to eliminate overlaps of cells and degrade the efficiency of analytic placers; and 4) global nets can improve placement stability of partition-based placers.

Noise affects circuit operation by varying circuit delays and causing latches to capture incorrect values. Conventional noise analysis techniques can detect some of such noise faults, but accurate analysis requires a careful examination of timing and functional properties of the circuit. In this paper, a method of characterizing correlation of signal transitions in nets by considering in a unified way both timing and functionality of the signals is proposed. An analysis procedure to eliminate noise faults that cannot actually happen when such correlations are considered is described. The timed-Boolean logic is used to characterize signal transitions in a time interval, and correlations are checked by solving Boolean satisfiability (SAT) between aggressor and victim transitions under the min-max delay model for gates. The method is applicable for checking noise faults at a single net, on a path, or in a cone of logic. The proposed technique is scalable as it keeps the size of Boolean formulation linear to the size of the modeled circuit. It has been applied on a set of large circuits, eliminating up to 50% of noise delay faults reported by a conventional noise-analysis method.

In this paper, we present a novel multigrid-based technique for the problem of on-chip power-supply network optimization. The multigrid-based technique is applied to reduce a large-scale network to a much coarser one. The reduced network can be efficiently optimized. The solution for the original network is then quickly computed using a back-mapping process. Due to the adoption of an accurate resistance-inductance-capacitance power-supply network and time-varying switching-current model, our technique is capable of optimizing power grid and decoupling capacitance simultaneously. Experimental results show that large-scale power-supply networks with millions of nodes can be solved in a few minutes. The proposed technique not only speeds up significantly the optimization process, without compromising the quality of solutions, but also brings up a possibility of incorporating the power-supply network optimization into other physical design stages such as signal routing.

In modern technologies, process variations can be quite substantial, often causing design timing failures. It is essential that those errors be correctly and quickly diagnosed. Unfortunately, the resolution of the existing delay-fault diagnostic methodologies is still unsatisfactory. In this paper, the feasibility of using the circuit timing information to guide the delay-fault diagnosis is investigated. A novel and efficient diagnostic approach based on the delay window propagation (DWP) is proposed to achieve significantly better diagnostic results than those of an existing delay-fault diagnostic commercial tool. Besides locating the source of the timing errors, for each identified candidate the proposed method determines the most probable delay defect size. The experimental results indicate that the new method diagnoses timing faults with very good resolution.

We investigate the problem of clock network sizing subject to general skew constraints. A novel approach based on sequential linear programming is presented. The original nonlinear programming problem is transformed into a sequence of linear programs by taking the first-order Taylor's expansion of clock path delay with respect to buffer and/or wire widths. For each linear program, the sensitivities of clock path delay, with respect to buffer and/or wire widths, are efficiently updated by applying time-domain analysis to the clock network in a divide-and-conquer fashion. Our technique can take into account power supply and process variations. We demonstrate experimentally that the proposed technique is not only capable of optimizing effectively the skew and area of clock network, but also of providing more accurate delay and skew results compared to the traditional approaches.

In this paper, we study the pre-layout wire length and congestion estimation. We find that two structural metrics, mutual contraction and net range, can be used to predict wire lengths. These metrics have different application ranges and complement each other. We also propose a new metric, the structural pin density, to capture the peak routing congestion of designs. Larger maximum pin densities usually lead to larger peak congestions in circuits with similar average congestions. We demonstrate experimentally very good correlation of our pre-layout measures with post layout interconnect lengths. We also isolate the structural netlist properties which cause the peak congestion.

In this paper we describe the design process of a via-configurable block for regular fabrics. The block consists of via-configurable functional cells, via-decomposable flip-flops, and via-configured sizable repeaters. The fabric has fixed layers up to M2. An M1-M2 via mask is used to define the block's functionality. The upper-level metals are customized. Compared to other structures based on LUTs or PLAs, and fixed flip-flops, our block has much smaller area, higher performance and lower power consumption.

In this paper, we investigate the problem of buffer sizing for clock power minimization subject to general skew constraints. A novel approach based on sequential linear programming is presented. By taking the first-order Taylor's expansion of clock path delay with respect to buffer widths, the original nonlinear problem is transformed to a sequence of linear programs, which incorporate clock skew scheduling and buffer sizing to minimize clock power dissipation. For each linear program, the sensitivities of clock path delay with respect to buffer widths are efficiently updated by applying time-domain analysis to the clock network in a divide-and-conquer fashion. Our approach can take process variations and power supply noise into account. We demonstrate experimentally that the proposed technique is not only capable of effectively reducing clock power consumption, but also able to provide more accurate delay and skew results compared to the traditional approach.

Noise affects circuit operation by increasing gate delays and causing latches to capture incorrect values. Noise analysis techniques can detect some of such noise faults, but accurate analysis requires a careful examination of timing and functional properties of the circuit. This paper proposes a method to check the "true" noise impact on path delay. It uses four-variable Boolean logic to characterize signal transitions in a time interval, and formulates Boolean satisfiability between aggressors and a victim under the min-max delay model for gates. The proposed technique is scalable as it keeps the size of Boolean formulation linear to the size of the modeled circuit. By applying it to a set of large circuits, it has eliminated up to 50% of noise delay faults reported by conventional noise analysis method.

The rapid growth of system-on-chip designs makes it a necessity for physical design tools to efficiently handle the coexistence of large intellectual property (IP) blocks and small standard cells in a single design. In this work, we present an efficient expansion-based placer to address standard-cell placement problem in the presence of blockages induced by pre-placed IP blocks. Expansion refers to the process during which cells are gradually distributed over a specified region. We implement expansion in a new placer by enhancing a quadratic placement technique based on fixed-point addition originally presented by B. Hu and M. Marek-Sadowska (2003), where fixed points were defined as dimensionless pseudo cells, and were deliberately introduced into the circuit to pull cells from one location to another. The new placer not only produces very competitive placement results over multiple sets of public-domain benchmarks with conventional rectangle-like chip boundary, but also efficiently handles the existence of blockages. Especially, we develop three expansion strategies and use them under different blockage settings.

In This work we present a complete physical design flow for a via-configurable gate array (VCGA). The VCGA is an array of prefabricated logic blocks and fixed metal masks. The block consists of via-configurable functional cells and a via-decomposable flip-flop. An M1-M2 via mask is used to define the block's functionality. Interconnects are customized using via masks. We developed a physical design flow for VCGA, which integrates a set of effective techniques. Here, we highlight the packing, cell-binding, and detailed-routing problems. We use our design flow to compare the VCGA-based and standard-cell/FPGA-based designs. Experimental results show the efficiency of our flow.

In this paper, we provide a comprehensive study of the mappability of a via-configurable gate array (VCGA). Although, the base cell of the VCGA is simple, by customizing only via masks it can implement various combinational logic functions, sequential elements, and SRAM cells. Our VCGA can be efficiently configured into SRAM arrays, adders and multipliers. The strong configurability of our VCGA allows us to minimize the number of fixed parts in a general-purpose VCGA fabric, which greatly improves area utilization.

Potential slack is an effective metric of circuit's possible performance improvement. It is equal to the maximal amount of slack that can be potentially used for optimization. In this paper, we first present a new, linear programming-based approach for potential slack calculation. Our method produces an optimal solution with significant runtime speedup compared to previous methods. Then, we formulate and solve the problem of global potential slack budgeting by clock-skew optimization. We demonstrate experimentally that the potential slack can be significantly improved by appropriate clock skew assignment.

In modern technologies, process variations can be quite substantial, often causing design timing failures. It is essential that those errors be correctly and quickly diagnosed. In this work, we analyze failures caused by the hold-time-violations. We investigate the feasibility of using circuit-timing information to guide the hold-time-fault diagnosis. We propose a novel and efficient diagnostic approach based on timing window propagation. For each identified candidate, our method locates the source of the hold-time violation and determines the most probable defect size. Experimental results indicate that the new method diagnoses hold-time related defects with very good resolution.

In this paper, we study the relationship between netlist structure and the efficiency of placers measured in terms of quality and stability of results. We analyze three types of placers: analytic, simulated-annealing-based and partition-based. We test the placers on industrial and synthetic benchmarks. Based on the observations and analyses of experimental results, we obtain several useful conclusions about relationships between netlist structure and placement efficiency of different types of placers.

In this paper, we present a novel approach to the problem of clock skew minimization by buffer and wire sizing. The original nonlinear programming problem is transformed to a sequence of linear programs, by taking the first order Taylor's expansion of clock path delay with respect to buffer and wire widths. The sensitivities of clock path delay, with respect to buffer and wire widths, are efficiently updated for each linear program by applying time domain analysis to the clock network in a divide-and-conquer fashion. Our technique can take into account the power supply variations, which have significant impact on clock skew. We demonstrate experimentally that in several iterations, the proposed technique is capable of reducing substantially the skew of clock networks.

We address the problem of designing very high-throughput finite-state machines (FSMs). The presence of loops in sequential circuits prevents a straightforward application of pipelining to increase performance. We observe that appropriate extensions of the "wave steering" technique can partially overcome the problem. We find that FSM decomposition theory is useful for decoupling the state-variable dependencies. Experiments on MCNC benchmarks show a 217 percent improvement in throughput, at the expense of a similar increase in area (2.15 times). Latency loss is relatively small, on the order of 20 percent, as compared to standard cell implementations.

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.

In this paper, we address the problem of improving the efficiency of placement algorithms. We employ a fine granularity clustering technique to reduce the original placement problem size. The reduction is feasible because a global placer may not need to operate on the bottom level netlist in order to achieve a competitive result. In general, placement algorithm efficiency is well correlated with the number of nodes in the netlist. Reducing the size of the placement problem (the number of nodes to be placed) leads to greater efficiency. We propose two new clustering algorithms. One applies net absorption, and the other is based on wire-length prediction. We have integrated those algorithms into our fast placer implementation (FPI) framework. We demonstrate experimentally that FPI achieves significant speedup while maintaining placement quality comparable to the state-of-the-art standard cell placer.

In this paper, we address the problem of individual wire-length prediction and demonstrate its usefulness in timing-driven placement. Many researchers have observed that different placement algorithms produce different individual wire lengths. We postulate that to obtain accurate results, individual wire-length prediction should be coupled with the placement flow. We embed the wire-length prediction into the clustering step of our fast placer implementation (FPI) framework . The predicted wire lengths act as constraints for the simulated annealing refinement stage, which guides the placement toward a solution fulfilling them. Experimental results show that our prediction process yields accurate results without loss of quality and incurs only a small cost in placement effort. We successfully apply the wire-length prediction technique to timing-driven placement. Our new slack assignment algorithm with predicted wire lengths (p-SLA) gives on average an 8% improvement in timing performance compared with the conventional modified zero-slack algorithm (m-ZSA).

Delay budgeting is a process of determining upper bounds for net delays to guide timing-driven placement. The existing approaches deal de facto only with combinational circuits. However, incorporating retiming into delay budgeting introduces more freedom to optimize sequential circuits. In this paper, we propose an approach for budgeting sequential circuits. We propose a new linear programming formulation for timing-aware sequential budgeting, which guarantees that the clock period constraints are met. We demonstrate the usefulness of our approach in the context of field-programmable gate arrays placement flow. We have performed two experiments. The first experiment compares sequential budgeting with traditional budgeting and retiming. The results show that the new placement flow reduces budget violations by 16% and improves timing by 9%. In the second experiment, we demonstrate methods of interconnect length prediction that are useful to estimate delay and to decide net weighting in sequential budgeting. We compare net delay predictions using traditional delay budgeting, the Donath's method, and mutual contraction. The results from this experiment show that sequential budgeting, using the new net weighting and predicted delays, can improve circuit speeds on average by 12.29%, compared to traditional timing-driven placement. The new net weighting method also performs better than a uniform weighting method.

Noise a#ects circuit operation by increasing gate delays and causing latches to capture incorrect values. This paper proposes a method of characterizing correlation of signal transitions in multiple nets by considering both timing and functionality of the signals, and uses it in an analysis procedure to eliminate noise faults that cannot actually happen when such correlations are considered. It uses four-variable Boolean logic to characterize signal transitions in a time interval, and formulates Boolean satisfiability between aggressors and a victim under the min-max delay model for gates. The technique has been successfully applied to commercial ASIC designs and has eliminated up to 35% of delay noise faults reported by a state-of-the-art noise analysis tool.

In this paper, we introduce a metric to evaluate proximity of connected elements in a netlist. Compared to connectivity by S. Hauck and G. Borriello (1997) and edge separability by J. Cong and S.K. Lim (2000), our metric is capable of predicting short connections more accurately. We show that the proposed metric can also predict relative wire length in multipin nets. We develop a fine-granularity clustering algorithm based on the new metric and embed it into the Fast Placer Implementation (FPI) framework by B. Hu and M. Marek-Sadowska (2003). Experimental results show that the new clustering algorithm produces better global placement results than the net absorption of Hu and M. Marek-Sadowska (2003) algorithm, connectivity of S. Hauck and G. Borriello (1997), and edge separability of J. Cong and S.K. Lim (2000) based algorithms. With the new clustering algorithm, FPI achieves up to 50% speedup compared to the latest version of Capo8.5 in http://vlsicad.ucsd.edu/Resources/SoftwareLinks/PDtools/, without placement quality losses.

In this paper we describe a technology mapping technique based on the logical effort theory [13]. First, we appropriately characterize a given standard cell library and extract from it a set of cell classes. Each cell-class is assigned a constant-delay model and corresponding load-bounds, which define the conditions of the delay model's validity. Next, we perform technology mapping using the classes determined in the first step. We propose several effective area-optimization heuristics which allow us to apply our algorithm directly to general graphs. Experimental results show that our gain-based mapping algorithm achieves reduced delay with less area, compared to the mapper in SIS [15]. By adjusting the constant delay model associated with each class, we determine the area-delay trade-off curve. We achieve the best area-delay trade-off using a design-specific constant delay models.

In recent years, due to rapid advances in VLSI manufacturing technology capable of packing more and more devices and wires on a chip, crosstalk has emerged as a serious problem affecting circuit reliability. Even though FPGAs are more immune to crosstalk noise than their ASIC counterparts manufactured in the same technological process, we have reached the point where FPGAs have become affected by crosstalk as well. Because FPGAs have regular interconnect structures, crosstalk noise can be more easily controlled. In this paper, we investigate the crosstalk noise in FPGAs and propose new strategies to reduce its impact on delay. Our methods can reduce crosstalk noise by statistically significant amounts with no penalty in performance, power, or area.

In this paper, we present a novel multigrid-based technique for on-chip power supply network optimization. We reduce a large-scale network to a much coarser one which can be efficiently optimized. The solution for the original network is then quickly computed using a back-mapping process. We model the power grid by an RLC network and use time-varying current sources to capture the on-chip switching. Our technique is capable of optimizing power grid and decoupling capacitance simultaneously. Experimental results show that the proposed technique provides more robust and area-efficient solutions than those obtained by the earlier approaches. It also provides a significant speed-up and brings up a possibility of incorporating power supply network optimization into other physical design stages such as signal routing.

Delay budgeting is a process of determining upper bounds for net delays to guide timing-driven placement. The existing approaches deal de facto only with combinational circuits. However, incorporating retiming into delay budgeting introduces more freedom to optimize sequential circuits. In this paper, we propose an approach for budgeting sequential circuits. We propose a new algorithm, T-SBGT, which uses an LP formulation to solve the budgeting problem in sequential circuits and guarantees that the clock period constraints are met. We then utilize the skew-retiming equivalence relation [9] and retime the circuit. We demonstrate usefulness of our approach in the context of FPGA placement flow. An effective algorithm to minimize Flip-Flops (FFs) number after placement using the net slack is also proposed. The results show the placement flow improves timing by 9%, and reduces budget violations by 16% compared to the traditional flow. The post-placement FF reduction algorithm decreases the FF count by 19% on average.

We study the relationship between multiple fault diagnosability and fault detection count. Instead of developing a complex diagnostic algorithm for multiple fault behavior, we change the test sets used in test and diagnosis. This allows us to apply a simple single-fault based diagnostic algorithm, and yet achieve very good diagnosability for the failure test cases caused by multiple faults. We have verified experimentally the effectiveness of n-detection tests for multiple-fault cases and explained the results in probabilistic terms.

In this paper we present the Gain-based Logic Block Array (GLA), a new via-programmable regular fabric. GLA is an array of Gain-based Logic Blocks (GLBs). The GLB is a semi-universal logic block designed based on logical effort theory[12]. Customization of the GLBs is provided by programmable vias. To achieve the best performance, appropriate fabric has to be selected from a family of GLAs with different performance-area trade-offs. We describe a synthesis and placement flow which, for a given design to be implemented, allows us to select the best GLA from the candidate family.

In this paper we present a linear-time Fine Granularity Clustering (FGC) algorithm to reduce the size of large scale placement problems. FGC absorbs as many nets as possible into Fine Clusters. The absorbed nets are expected to be short in any good placement; therefore the clustering process does not affect the quality of results. We compare FGC with a connectivity-based clustering algorithm proposed in [1] and simulated-annealing-based algorithm in TimberWolf [2], both of which also reduce the number of external nets between clusters. The experimental results show that our algorithm achieves better net absorption than the previous approaches while using much less CPU time for large scale problems. With our FGC algorithm, we propose a Fast Placer Implementation (FPI) framework, which combines our FGC-based size reduction with traditional placement techniques to handle large-scale placement problems. We compared FPI placement results with a public-domain fast standard cell placer Capo[4] on large scale benchmarks. The results show that FPI can reduce CPU time for large scale placement by a factor of 3~5x while obtaining placement results of comparable or better quality.

In this paper, we analyze failing circuits and propose a multiple-fault diagnosis approach. Our methodology has been validated experimentally and has proved to be highly efficient and effective in diagnosing multiple faults. We do not consider the multiple-fault behavior explicitly, but rather use an incremental simulation-based approach to diagnose failures one at a time. Furthermore, to improve the diagnosability, we propose a failing-primary-output partitioning algorithm. Experimental results show that our approach has approximately linear time complexity, and it achieves high diagnosability and resolution. Our approach has also been validated on data collected from manufactured chips. The diagnosis time is within minutes for real industrial chips that failed because of multiple faults. 1.

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.

Variations of power and ground levels affect very large scale integration circuit performance. Trends in device technology and in packaging have necessitated a revision in conventional delay models. In particular, simple scalable models are needed to predict delays in the presence of uncorrelated power and ground noise. In this paper, we analyze the effect of such noise-on-signal propagation through a buffer and present simple, closed-form formulas to estimate the corresponding change of delay. The model captures both positive (slowdown) and negative (speedup) delay changes. It is consistent with short-channel MOSFET behavior, including carrier velocity saturation effects. An application shows that repeater chains using buffers instead of inherently faster inverters tend to have superior supply-level-induced jitter characteristics. The expressions can be used in any existing circuit performance optimization design flow or can be combined into any delay calculations as a correction factor.

Wave steering is a unified logic and physical synthesis scheme that algorithmically generates high-throughput circuits with fast turn-around times. Binary decision diagram (BDD)-type structures are altered to satisfy certain electrical constraints, embedded in silicon with pass transistor logic (PTL), and pipelined to very fine granularity using a novel two-phase clocking scheme. This direct PTL mapping of a logic representation provides good electrical estimations to a front-end tool like the logic synthesizer at an early phase of the design cycle. We apply our wave steering technique to high throughput computation-intensive datapath combinational circuits. We achieve an average speedup of 4.2 times compared to standard cell (SC) implementations of high performance arithmetic circuits at the cost of only about 76% average increase in area. The results look extremely encouraging; all the more so, considering that we also achieve an average reduction of 27% in latency and 15% in power compared to SC circuits.

In this paper, we present a novel, high throughput field-programmable gate array (FPGA) architecture, PITIA, which combines the high-performance of application specific integrated circuits (ASICs) and the flexibility afforded by the reconfigurability of FPGAs. The new architecture, which targets datapath circuits, uses the concepts of wave steering and pipelined interconnects. We discuss the FPGA architecture and show results for performance, power consumption, clock network performance, and routability. Results for some commonly used datapath designs are encouraging with throughputs in the neighborhood of 625MHz in 0.25-/spl mu/m 2.5-V CMOS technology. Results for random benchmark circuits are also shown. We characterize designs according to their Rent's exponents and argue that designs with predominantly local interconnects are the best fit in PITIA. We also show that as technology scales down toward deep submicron, PITIA shows an increasing throughput performance.

Variation of power and ground levels affect VLSI circuit performance. Trends in device technology and in packaging have necessitated a revision in conventional delay models. In particular, simple scalable models are needed to predict delays in the presence of uncorrelated power and ground noise. In this paper, we analyze the effect of such noise on signal propagation through a buffer and present simple, closed-form formulas to estimate the corresponding change of delay. The model captures both positive (slowdown) and negative (speedup) delay changes. It is consistent with short-channel MOSFET behavior, including carrier velocity saturation effects. An application shows that repeater chains using buffers instead of inherently faster inverters tend to have superior supply level-induced jitter characteristics.

In this paper we present efficient closed-form formulas to estimate capacitive coupling-induced crosstalk noise for distributed RC coupling trees. The efficiency of our approach stems from the fact that only the five basic operations are used in the expressions: addition (x+y), subtraction (x-y), multiplication (x/spl times/y), division (x/y) and square root (/spl radic/x). The formulas do not require exponent computation or numerical iterations. We have developed closed-form expressions for the peak crosstalk noise amplitude, the peak noise occurring time and the width of the noise waveform. Our approximations are conservative and yet achieve acceptable accuracy. The formulas are simple enough to be used in the inner loops of performance optimization algorithms or as cost functions to guide routers. They capture the influence of coupling direction (near-end and far-end coupling) and coupling location (near-driver and near-receiver).

This paper presents a new formulation and an efficient solution of the power and ground mesh sizing problem. We use the key observations that (1) the drops in power and ground node potentials are due not only to currents drawn by the computing blocks, but also to those drawn by the clock buffers, and (2) changes of circuit component delays are linearly proportional to the power/ground IR-drops. This leads to a linear quantification of the timing relations between the clocking and computing components in terms of the power/ground IR-drops. Our method removes all IR-drop related timing violations that occur in about 2% of paths when grids are sized using the existing methods that satisfy the maximum IR-drop constraints. In addition, we achieve supply mesh area improvements of the order of 30% while simultaneously reducing the power dissipated in the circuits by about 6.6% compared to traditional grid sizing methods.

We present a routability-driven bottom-up clustering technique for area and power reduction in clustered FPGAs. This technique uses a cell connectivity metric to identify seeds for efficient clustering. Effective seed selection, coupled with an interconnect-resource aware clustering and placement, can have a favorable impact on circuit routability. It leads to better device utilization, savings in area, and reduction in power consumption. Routing area reduction of 35% is achieved over previously published results. Power dissipation simulations using a buffered pass-transistor-based FPGA interconnect model are presented. They show that our clustering technique can reduce the overall device power dissipation by an average of 13%.

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.

This paper presents a new congestion minimization technique for standard cell global placement. The most distinct feature of this approach is that it does not follow the traditional "estimate-then-eliminate" strategy. Instead, it avoids the excessive usage of routing resources by the "local" nets so that more routing resources are available for the uncertain "global" nets. The experimental results show that our new technique, SPARSE, achieves better routability than the traditional total wire length (Bounding Box) guided placers, which had been shown to deliver the best routability results among the placers optimizing different cost functions [2]. Another feature of SPARSE is the capability of allocating white space implicitly. SPARSE exploits the well known empirical Rent's rule and is able to improve the routability even more in the presence of white space. Compared to the most recent academic routability-driven placer Dragon[8], SPARSE is able to produce solutions with equal or better routability.

In this paper we present efficient closed-form formulas to estimate the incremental delay change induced by capacitive interconnect coupling. We also analyze temporal correlations among switching signals and develop criteria for timing window alignment. Our approximations are conservative and yet achieve acceptable accuracy. The formulas are simple enough to be used in the inner loops of static timing analysis. Categories & Subject Descriptors: J.6 [Computer-Aided Engineering]: Computer-aided design

In this paper we describe the Fixed-points Addition and Relaxation (FAR) based placement technique. Fixed point is a pseudo cell connected to a movable cell. By introducing fixed points, the placement can be maintained in a force equilibrium state and further transformed into another equilibrium state. By relaxing some of the previously introduced fixed points, we can partially or completely collapse the current placement in order to reposition the cells, or incrementally perturb the existing good solution to fulfill additional requirements. We apply the FAR-based approach to global placement for total wire length minimization, and to incremental placement for Buffer Site Generation (BSG). For global placement, our experimental results show that the FAR method achieves 54.4% CPU speedup and total wire length comparable to that achieved by the constant force based approach [1]. Experimental results indicate that to accommodate buffers in specific regions, FAR is able to perturb incrementally a given solution in a well-controlled way.

We utilize Rent's rule as an empirical measure for efficient clustering and placement of circuits in clustered Field Programmable Gate Arrays (FPGAs). We show that careful matching of resource availability and design complexity during the clustering and placement processes can contribute to spatial uniformity in the placed design, leading to overall device decongestion after routing. We present experimental results to show that appropriate logic depopulation during clustering can have a positive impact on the overall FPGA device area. Our clustering and placement techniques can improve the overall device routing area by as much as 62%, 35% on average, for the same array size, when compared to state-of-the-art FPGA clustering, placement, and routing tools. Power dissipation simulations using a typical buffered pass-transistor-based FPGA interconnect model are also presented. They show that our clustering and placement techniques can reduce the overall device power dissipation by approximately 13%.

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.

Wave Steering is a new design methodology that realizes high throughput circuits by embedding layout friendly synthesized structures in silicon. Wave Steered circuits inherently utilize latches in order to guarantee the correct signal arrival times at the inputs of these synthesized structures and maintain the high throughput of operation. In this paper, we show a method of reor-dering signals to achieve minimum circuit latency for Wave Steered circuits and propose an Integer Linear Programming(ILP) formulation for scheduling and retiming these circuits to minimize the number of latches for minimum latency. Experimental results show that in 0.25mm CMOS technology, as much as 33.2% reduc-tion in latch count, at minimum latency, can be achieved over unoptimized Wave Steered circuits operating at 500 MHz.

In deep submicron digital circuits capacitive couplings make delay of a switching signal highly dependent on its neighbors switching times and switching directions. A long path may have a large num-ber of coupling neighbors with difficult to determine interdepen-dencies. Ignoring the mutual relationship among the signals may result in a very pessimistic estimation of circuit delay. In this paper, we apply efficient functional correlation analysis techniques to identify critical paths caused by crosstalk delay effects. We also discuss applications to static timing optimization. Experiments demonstrate efficacy of the proposed technique.

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.

Wave-Steering is a new circuit design methodology to realize high throughput circuits by embedding layout friendly structures in silicon. Latches guarantee correct signal arrival times at the input of synthesized modules and maintain the high throughput of operation. This paper presents a global routing technique for networks of wave-steered blocks. Latches can be distributed along interconnects. Their number depends on net topologies and signal ordering at the inputs of wave steered blocks. here, we route nets using Steiner tree heuristics and determine signal ordering and latch positions on interconnect. The problem of total latch number minimization is solved using SAT formulation. Experimental results on benchmark circuits show the efficiency of our technique. We achieve on average a 40% latch reduction at minimum latency over un-optimized circuits operating at 250 MHz in 0.25 /spl mu/m CMOS technology.

Wave-steering is a new design methodology that realizes high throughput circuits by embedding layout friendly synthesized structures in silicon. In the wave-steering design methodology, cir?cuits inherently utilize latches. Inside the synthesized structures they are used for signal skewing, and on the interconnects to guar?antee the correct arrival times at the inputs. Recently, we proposed a novel high-throughput FPGA architecture based on the wave-steering design principle to handle throughput-intensive applica?tions. Previously our work was focussed mainly on the Logic Block (LB) design. In this paper we discuss a pipelined intercon?nect scheme to support the strict timing requirements that is neces?sitated by the wave-steered design style. We characterize designs that best fit the new architecture and show that as technology scales down towards deep submicron (DSM), this FPGA fabric shows an increasing throughput performance.

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.

Utilizes Rent's rule as an empirical measure for efficient clustering and placement of circuits on hierarchical FPGAs. We show that careful matching of design complexity and architecture resources of hierarchical FPGAs can have a positive impact on the overall device area. We propose a circuit placement algorithm based on Rent's parameter and show that our clustering and placement techniques can improve the overall device routing area by as much as 21% for the same array size, when compared to a state-of-art FPGA placement and routing tool.

Digital circuits manufactured in deep sub-micron technologies may experience crosstalk-induced delay and noise signals. Crosstalk-induced delay can be quite significant and sensitive to the driver strength of coupling neighbors. In this paper, we propose gate-sizing techniques to reduce delay in presence of crosstalk effects. The techniques are based on our (2001) previously proposed crosstalk aware static timing analysis. Our experiments show that the proposed techniques are effective and may help designers achieve faster timing closure.

In this paper, we study signal alignment resulting in maximum peak interconnect coupling noise. We consider three cases. In the first one, we assume that arbitrary arrival times of input signals are feasible. In the second case, we assume that timing windows are given for each aggressor input. The victim is quiet for the above two cases. In the third case, the victim net has a propagated noise from the previous stage and timing windows are given for both the propagating noise and the aggressor inputs. We propose a simple procedure to find aggressor alignment for worst-case coupling in all the cases.

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.

In this paper we address the problem of pipelining FSMs by extending wave-steering scheme from combinational to sequential realm. A unified approach employs direct mapping of State Transition Graph into a circuit realization. Experimental result on MCNC benchmarks show performance improvement of 2 to 4 times at the cost of an average area increase of 2.9 times.

In this paper we address the problem of designing very high throughput finite state machines (FSMs). The presence of loops in sequential circuits prevents a straightforward and generalized application of pipelining techniques, which work so well for combinational circuits, to increase FSM performance. We observe that appropriate extensions of the "wave steering" technique are possible to partially overcome the problem. Additionally we use FSM decomposition theory to decouple state variable dependencies. Application of these two techniques to MCNC benchmarks resulted in a factor of 3 average throughput increase as compared to a standard cell implementation, at the expense of factor 3.7 area and less than factor 2 latency penalties.

With increased logic density due to the shift towards Deep Submicron technologies (DSM), FPGAs have become a viable option for implementing large designs. However, most commercial FPGAs, due to their general purpose architectural nature, cannot handle designs which require very high throughput. In this paper, we propose a novel high throughput FPGA architecture which tries to combine the high-performance of Application Specific Integrated Circuits (ASICs) and the flexibility afforded by the reconfigurability of FPGAs. This architecture utilizes the concept of 'Wave-Steering' and works best for designs which are highly regular and have almost equal delays along all paths. It has enormous potential in Digital Signal and Image Processing applications since a good portion of these applications are regular in nature. Preliminary results for some commonly used DSP designs are encouraging and yield throughputs in the neighborhood of 770 MHz in 0.5μ CMOS technology.

Digital circuits manufactured in deep sub-micron technologies may experience crosstalk induced delay and noise signals. Crosstalk induced delay can be quite significant and difficult to determine because of dependency on switching time of the neighboring signals. We study the problem of computing signal earliest and latest arrival time when timing windows and slew rate ranges of the inputs and coupling neighbors' inputs are known. We propose a complexity O(n log n) algorithm to solve this problem. The proposed method has been applied in crosstalk aware static timing analysis to guide timing driven layout synthesis. Experimental results have demonstrated its efficacy and efficiency.

In this paper we study signal alignment resulting in maximum peak interconnect crosstalk noise. We consider two cases. In the first one we assume that arbitrary arrival times of input signals are feasible. In the second case we assume that timing windows are given for each aggressor input. We propose a simple procedure to find aggressor alignment for worst-case coupling in both cases. Keywords Crosstalk noise, aggressor alignment, interconnect coupling, signal integrity, timing window. 1. INTRODUCTION With technology shrinking to deep submicron regime coupling noise becomes a common effect. It is therefore essential to develop techniques that allow estimating accurately worst-case crosstalk conditions. In this paper we study the problem of how crosstalk noise is affected by the switching times of aggressors acting on a victim net. We assume that driver strengths, wire spacing, spatial positions of aggressors and victim are given and not changing. Signal arrival times can be adjust...

In this paper, we analyze the basic properties of some Boolean function classes and propose a low complexity OBDD variable ordering algorithm, which is exact (optimum) to some classes of functions and very effective to general two-level form functions. We show that the class of series-parallel functions, which can be expressed by a factored form where each variable appears exactly once, can yield exact OBDD variable orderings in polynomial time. We also study the thin Boolean functions whose corresponding OBDDs can be represented by the form of thin OBDDs in which the number of nonterminal nodes is equal to the number of input variables. We show,that a thin Boolean function always has an essential prime cube cover and the class of series-parallel functions is a proper subset of thin Boolean functions. We propose a heuristic viewing OBDDs as evaluation machines with function cube covers as their inputs and apply a queuing principle in the algorithm design. Our heuristic, the augmented Dynamic Shortest Cube First algorithm, is proven to be optimum for the series-parallel functions and also be very effective for general two-level form functions. Experimental results on a large number of two-level form benchmark circuits show that the algorithm yields an OBDD total size reduction of over 51 percent with only 7 percent CPU time compared to the well-known network-based Fan-in Heuristic implemented in the SIS package. Comparing to the known exact results, ours is only 49 percent larger in size while only uses 0.001 percent CPU time.

In this paper, we introduce a hierarchical test set structure called star test, derived from the experimental observation of the fault clustering phenomena. Based on the concept of star test, two applications are studied: one applied to built-in-self-test (BIST); the other to automatic test pattern generation (ATPG). First, a very high quality and low-cost BIST scheme, named STAR-BIST is proposed. Experimental results have demonstrated that a very high fault coverage can be obtained without any modification of the logic under test, no test data to store and very simple BIST hardware which does not depend on the size of the circuit. Second, an efficient test generator, named STAR-ATPG, is developed which speeds up the ATPG performance by a factor of up to five for large industrial circuits.

In this paper we consider transistor sizing to reduce crosstalk. First, crosstalk noise dependency on wire width, wire spacing, driver and receiver sizes are discussed, and validated by experiments. Then transistor sizing for timing and noise is discussed and solved using optimization techniques. Experimental results suggest that crosstalk violations can be removed by transistor sizing with very small area overhead.

Article Wave steering in YADDs: a novel non-iterative synthesis and layout technique Share on Authors: Arindam Mukherjee Dept. of ECE, University of California, Santa Barbara, CA Dept. of ECE, University of California, Santa Barbara, CAView Profile , Ranganathan Sudhakar Dept. of ECE, Stanford University, Stanford, CA Dept. of ECE, Stanford University, Stanford, CAView Profile , Malgorzata Marek-Sadowska Dept. of ECE, University of California, Santa Barbara, CA Dept. of ECE, University of California, Santa Barbara, CAView Profile , Stephen I. Long Dept. of ECE, University of California, Santa Barbara, CA Dept. of ECE, University of California, Santa Barbara, CAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 466–471https://doi.org/10.1145/309847.309981Online:01 June 1999Publication History 22citation205DownloadsMetricsTotal Citations22Total Downloads205Last 12 Months1Last 6 weeks1 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

We present a circuit clustering technique based on graph coloring.A given netlist is modeled as an undirected graph and its vertices are colored.Based on this coloring information and the notion of rank of a node and the number of adjacent unique colors it sees, we derive cost functions for the graph edges.We identify cliques in the graph and use these cliques, starting from the maX_CliqUe.as building blocks for our clusters.A cost function is derived using the cluster density notion and edge costs.Finally, we use this Cost function to identify the critical edges, which when deleted yield good clusters in the original circuit.

Star test is a novel test pattern generation technique in which a few test vectors serve as centers of clusters for other test vectors which are derived by complementing at random their coordinates. By properly selecting the deterministic patterns as centers, the star tests have very high probability to detect most of the faults in a circuit. This paper presents an efficient algorithm to combine the star test approach with a traditional test pattern generator yielding a significant speed up of the ATPG process. With the new STAR-ATPG methodology, the major effort of the test generation is transferred from an computationally more complex test pattern generation process into simpler fault simulation. Experimental results on several large industrial designs demonstrate that a factor of 1.5-2.5 average speed up is achieved by the new method with the same abort limit. Also, STAR-ATPG achieves higher fault coverage than traditional ATPG under the same abort limit. To achieve the same fault coverage as STAR-ATPG, it requires the traditional method to increase the abort limit significantly and result in 5 times slower.

Presents a very efficient optimization method suitable for multi-level combinational circuits. The optimization is based on incremental restructuring of a circuit through a sequence of additions and removals of redundant wires. Our algorithm applies the techniques of automatic test pattern generation (ATPG), which can efficiently detect redundancies. During the ATPG process, certain nodes in the circuit must have particular logic assignments for a test to exist. Based on the properties of these mandatory assignments, we have developed theorems to eliminate unnecessary wire redundancy checking. This results in a significant performance improvement. The fast run time and the excellent scaling to large circuits make our Boolean optimization method practical for industrial applications.

A fundamental feature of Dynamically Reconfigurable FPGAs (DRFPGAs) is that the logic and interconnect are time-multiplexed. Thus, for a circuit to be implemented on a DRFPGA, it needs to be partitioned such that each subcircuit can be executed at a different time. In this paper, the partitioning of sequential circuits for execution on a DRFPGA is studied. To determine how to correctly partition a sequential circuit and what are the costs in doing so, we propose a new gate-level model that handles time-multiplexed computation. We also introduce an enchanced force directed scheduling (FDS) algorithm to partition sequential circuits that finds a correct partition with low logic and communication costs, under the assumption that maximum performance is desired. We use our algorithm to partition seven large ISCAS'89 sequential benchmark circuits. The experimental results show that the enhanced FDS reduces communication costs by 27.5 percent with only a 1.1 percent increase in the gate cost compared to traditional FDS.

During the process of very large scale integration design, specifications are often changed. To preserve as large a portion of the engineering effort as possible, it is desirable that such changes will not lead to a very different design. In this work, we consider logic synthesis algorithms for handling engineering changes. To solve it, we propose a combination of multiple-error diagnosis and logic minimization techniques. Given a new specification and an existing synthesized network, our algorithms first identify the candidate signals in the network, and then synthesize the candidate functions. The synthesis step utilizes the existing network as much as possible so that the new specification can be realized with minimal changes.

We address the problem of crosstalk computation and reduction using circuit and layout techniques in this paper. We provide easily computable expressions for crosstalk amplitude and pulse width in resistive, capacitively coupled lines. The expressions hold for nets with arbitrary number of pins and of arbitrary topology under any specified input excitation. Experimental results show that the average error is about 10% and the maximum error is less than 20%. The expressions are used to motivate circuit techniques, such as transistor sizing, and layout techniques, such as wire ordering and wire width optimization to reduce crosstalk.

Functional scan chains are scan chains that have scan paths through a circuit's functional logic and flip-flops. Establishing functional scan paths by test point insertion (TPI) has been shown to be an effective technique to reduce the scan overhead. However, once the scan chain is allowed to go through functional logic, the traditional alternating test sequence is no longer enough to ensure the correctness of the scan chain. We identify the faults that affect the functional scan chain, and show a methodology to find tests for these faults. Our results have the number of undetected faults at only 0.006% of the total number of faults, or 0.022% of the faults affecting the scan chain.

A fundamental feature of Dynamically Reconfigurable FP-GAs (DRFPGAs) is that the logic and interconnect is time-multiplexed. Thus for a circuit to be implemented on a DRFPGA, it needs to be partitioned such that each subcircuit can be executed at a different time. In this paper, the partitioning of sequential circuits for execution on a DRF-PGA is studied. To determine how to correctly partition a sequential circuit, and what are the costs in doing so, we propose a new gate-level model that handles time-multiplexed computation. We also introduce an enchanced force directed scheduling (FDS) algorithm to partition sequential circuits that finds a correct partition with low logic and communication costs, under the assumption that maximum performance is desired. We use our algorithm to partition seven large ISC AS'89 sequential benchmark circuits. The experimental results show that the enhanced FDS reduces communication costs by 27.5% with only a 1.1% increase in the gate cost compared to traditional FDS.

In this paper, we propose a hybrid approach for estimating the switching activities of the internal nodes in logic circuits. The new approach combines the advantages of the simulation-based techniques and the probability-based techniques. We use the user-specified control sequence for simulation, and treat the weakly correlated data inputs using the probabilistic model. The new approach, on one hand, is more accurate than the probabilistic approaches because the strong temporal and spatial correlations among control inputs are well taken into consideration. On the other hand, the new approach is much more efficient than the simulation-based approaches because the weakly correlated data inputs are not explicitly simulated. We also discuss the situation where BDD's are built in terms of internal nodes so that large circuits can he handled. Extensive experimental results are presented to show the effectiveness and efficiency of our algorithms.

Conventional scan design imposes considerable area and delay overheads. To establish a scan chain in the test mode, multiplexers at the inputs of flip-flops and scan wires are added to the actual design. We propose a low-overhead scan design methodology that employs a new test-point insertion technique. Unlike the conventional test-point insertion, where test points are used directly to increase the controllability and observability of the selected signals, the test points are used here to establish scan paths through the functional logic. The proposed technique reuses the functional logic for scan operations; as a result, the design-for-testability overhead on area or timing can be minimized. We show an algorithm that uses the new test-point insertion technique to reduce the area overhead for the full-scan design. We also discuss its application to the timing-driven partial-scan design.

Conventional scan design imposes considerable area and delay overheads. To establish a scan chain in the test mode, multiplexers at the inputs of flip-flops and scan wires are added to the actual design. However, the functionality of the functional logic has not been utilized for the test purposes. We propose a low-overhead scan design methodology, called cost-free scan, which exploits the controllability of primary inputs to establish scan paths through the functional logic. We show how to analyze the circuit to determine all the free-scan flip-flops and select the best input vector to establish the maximum number of free-scan flip-flops for the scan chain design. Significant reduction in the scan overhead is achieved on ISCAS89 benchmarks. In full-scan designs, as many as 89% of the flip-flops are found free-scannable. In the partial-scan designs, we assume that selecting flip-flops for scan to break sequential cycles is used to increase circuit testability. Reduction can be as high as 97% in scan flip-flops needed to break sequential cycles.

It has been observed experimentally that the mapping of global to detailed routing in a conventional FPGA routing architecture (2D array) yields unpredictable results. A different class of FPGA structures called greedy routing architectures (GRAs), where a locally optimal switch box routing can be extended to an optimal entire-chip routing, were investigated by Wu et al. (1994), Takashima et al. (1996) and Wu et al. (1996). It was shown that GRAs have good mapping properties. An H-tree GRA with W/sup 2/+2W switches per switch box (SpSB) and a 2D array GRA with 4W/sup 2/+2W SpSB were proposed by those authors (W is the number of tracks in each switch box). We continue this work by introducing an H-tree GRA with W/sup 2//2+2W SpSB and a 2D array GRA with 3.5 W/sup 2/+2 W SpSB. These new GRAs have the same good mapping properties but use fewer switches. We also show a class of FPGA architectures in which the mapping problem remains NP-complete, even with 6(W-1)/sup 2/+6W/sup 2/ SpSB (this is close to the maximum number of SpSB, which is 6W/sup 2/). Thus, more switches do not necessarily result in more routability.

In this paper, we present a test synthesis approach which integratesBALLAST (BALAnced structure Scan Test) withan enhanced test point insertion (TPI) algorithm to functionallyscan the flip-flops chosen by BALLAST.BALLASTis an attractive partial scan technique in that it offers combinationalATPG efficiency while promising to reduce full scanoverhead.However, the practical problem with BALLASTis it typically requires more scan flip-flops than other partialscan techniques.The TPI enhancements enable TPI toaim at the reduction of BALLAST overhead.The enhancementsinclude a more flexible test point insertion heuristic,a modified gain function which enables TPI to target a selectedset of flip-flops, and a more efficient procedure toremove redundant test points.The experimental results onnine benchmark circuits show the proposed test synthesisapproach can achieve on average 38% area saving comparedto full scan, while BALLAST alone achieves 17%.

We propose a new methodology based on incremental logic restructuring for post-layout performance improvement. The new post-layout logic restructuring technique allows to use accurate interconnection delays for performance optimization, while the incremental nature of the technique guarantees convergence between logic synthesis and layout. The technique can be further integrated with other post-layout optimization techniques such as gate sizing and buffer insertion. Experimental results show that this technique combined with post-layout buffer insertion can achieve an additional 15% improvement in performance compared to designs produced by timing-driven logic optimization followed by pre-layout buffer insertion followed by timing-driven physical design. 1. Introduction Performance-driven logic synthesis followed by performance -driven layout [1] has become a necessity for designing high performance circuits. However, this loosely coupled two-phase timing optimization methodology has...

This paper presents a new scan-based BIST schemewhich achieves very high fault coverage without the deficienciesof previously proposed schemes. This approach utilizes scan orderand polarity in scan synthesis, effectively converting the scanchain into a ROM capable of storing some "center" patterns fromwhich the other vectors are derived by randomly complementingsome of their coordinates. Experimental results demonstrate that avery high fault coverage can be obtained without any modificationof the mission logic, no test data to store and very simple BISThardware which does not depend on the size of the circuit.

We investigate the hardware implications when combinational logic is implemented on Dynamically Reconfigurable FPGAs (DRFPGAs). We first investigate the number of communication buffers needed by a DRFPGA. These buffers are needed because the time-multiplexednature of DRFPGAs means that only a portion of the circuit implemented on the chip is present at any given time instance. Thus there is a need to store OT buffer signals until they are no longer needed. The hardware cost in a DRFPGA is the maximum number of buffers (plus associated routing) needed at any given time. We show experimentally that this number is almost as large as the number of computation nodes needed at any given time, and in some circuits twice as large. We also give a heuristic algorithm based on rescheduling nodes that reduces the number of buffers needed by 23%. Next we investigate time-multiplexed I/0 on a DRFPGA. We show that by using time-multiplexed 1/0pins, the number of physical I/0pins needed can be reduced by up to 83%.

This paper presents an improved scan-based BIST scheme which achieves very high fault coverage without any modification of the mission logic, i.e. no test point insertion, no test data to store and very simple BIST hardware which does not depend on the size of the circuit. The approach utilizes scan order and its polarity in scan synthesis, effectively converting it into a ROM encoding a few test vectors which serve as centers of clusters from which the other vectors are derived by complementing at random their coordinates. The proposed method successfully tests the random pattern resistant faults, which is the major problem of traditional LFSR-based BIST, with lower hardware cost and a more efficient algorithm than previous methods. Experimental results demonstrate that a very high fault coverage can be achieved with much smaller test set than other pseudorandom pattern generation methods published so far.

In this paper, we present a new method to characterize completely specified Boolean functions. The central theme of the classification is the functional equivalence (a.k.a. Boolean matching). Two Boolean functions are equivalent if there exists input permutation, input negation, or output negation that can transform one function to the other. We have derived a method that can efficiently identify equivalence classes of Boolean functions. The well-known canonical Fixed Polarity Reed-Muller (FPRM) forms are used as a powerful analysis tool. The necessary transformations to derive one function from the other are inherent in the FPRM representations. To identify uniquely each equivalence class, a set of well-known characteristics of Boolean functions and their variables (including linearity, symmetry, total symmetry, self-complement, and self-duality) are employed. It is shown that all the equivalence classes of four-variable functions are uniquely identified where majority of the classes have a single FPRM form as their representative. The Boolean matching has applications in technology mapping and in design of standard cell libraries.

In this paper, we propose a layout-driven synthesis approach for field programmable gate arrays (FPGA's). The approach attempts to identify alternative wires and alternative functions for wires that cannot be routed due to the limited routing resources in FPGA. The alternative wires (in the logic level) that can be routed through less congested areas substitute the unroutable wires without changing the circuit's functionality. Allowing the logic blocks to have alternative functions also increases the chance of successful routing. A redundancy addition and removal technique is used to identify such alternative wires. Experimental results are presented to demonstrate the usefulness of this approach. For a set of randomly selected benchmark circuits, on the average, 30-50% of wires have alternative wires. These results indicate that the routing flexibility can be substantially increased by considering these alternative wires. Our prototype system successfully completed routing for two AT&T designs that cannot be handled by an FPGA router alone. The proposed synthesis technique can also be applied to standard cell and gate array designs to reduce the routing area.

We present a general methodology to determine the logic function of a programmable cell. It is based on the concept of universal logic gate (ULG) that is capable of being configured to a given set of functions. The cells studied here can be configured to the desired functionality by applying input permutation, negation, bridging or constant assignment, or output negation. One application of this technique is to select an appropriate programmable cell structure for FPGA architecture. The Actel 2 and the three-input look-up table cells are studied and compared to the cell that has been designed using the approach described here. Experimental results suggest that the new cell behaves as well as the Actel 2 cell in terms of logic power, but requires substantially less area and wiring overhead.

The performance of high-speed electronic systems is limited by interconnect-related failure modes such as coupled noise. We propose new techniques for alleviating the problems caused by coupling between signal lines on integrated circuits. We show that models used by previous work on coupled noise-constrained layout synthesis do not allow the use of several important degrees of freedom. These degrees of freedom include the ability to utilize dynamic noise margins rather than static noise margins, the dependence of coupled noise on drive strength, and the possibility of using overlaps to reduce susceptibility to noise. We derive an expression for the coupled noise integral and a bound for the peak coupled noise voltage which shows order of magnitude improvements in both accuracy and fidelity compared to the charge sharing model used in previous work. We use the new bounds to guide a greedy channel router, which manipulates exact adjacency information at every stage, allowing it to introduce jogs or doglegs when necessary for coupled noise reduction. Experimental results indicate that our algorithm compares favorably to previous work. The coupled noise is significantly reduced on benchmark instances.

We address the problem of low-power reliable clock tree design in this paper. We study the scaling of clock power dissipation with increasing die sizes, number of receivers, and operating frequencies. The analysis shows that buffering only at the root of the tree is not scalable. However, when buffered clock trees are allowed, the classical H tree is suboptimal in terms of both area and power dissipation. We show that the new power minimization problem is NP hard, and we propose a novel algorithm for low-power clock network design. Our algorithm designs the tree topology and inserts buffers simultaneously. The clock skew is guaranteed to be small in the presence of correlated process variations. Wire sizing is used when necessary, and clock skew can be inserted intentionally if required. The results obtained by our algorithm on benchmark problem instances are significantly better than previous approaches in terms of power dissipation, wire length, rise times, and buffer area. We report HSPICE simulation results for the clock trees designed by the new algorithm.

In this paper, the routing problem for two-dimensional (2-D) field programmable gate arrays of a Xilinx-like architecture is studied. We first propose an efficient one-step router that makes use of the main characteristics of the architecture. Then we propose an improved approach of coupling two greedy heuristics designed to avoid an undesired decaying effect, a dramatically degenerated router performance on the near completion stages. This phenomenon is commonly observed on results produced by the conventional deterministic routing strategies using a single optimization cost function. Consequently, our results are significantly improved on both the number of routing tracks and routing segments by just applying low-complexity algorithms. On the tested MCNC and industrial benchmarks, the total number of tracks used by the best known two-step global/detailed router is 28% more than that used by our proposed method.

In this paper, we propose a hybrid approach for estimating the switching activities of the internal nodes in logic circuits.The new approach combines the advantages of the simulation-based t e chniques and the probability-based t e chniques.We use the user-speci ed control sequence for simulation and treat the weakly correlated data inputs using the probabilistic model.The new approach, on one hand, is more a c curate than the probabilistic approaches because the strong temporal and spatial correlations among control inputs are well taken into consideration.On the other hand, the new approach is much more ecient than the simulation-based approaches because the weakly correlated data inputs are not explicitly simulated.In addition, we also propose a heuristic that builds BDDs in terms of internal nodes such that large circuits can be handled.Extensive experimental results are p r esented to show the eectiveness and eciency of our algorithms.

We propose a low-overhead scan design methodology which employs a new test point insertion technique to establish scan paths through the functional logic.The technique re-uses the existing functional logic; as a result, the design-for-testability (DFT) overhead on area or timing can be minimized.In this paper we show an algorithm which considers the test point insertion for reducing the area overhead for the full scan design.We also discuss its application to timing-driven partial scan design.

Article Multilevel logic synthesis for arithmetic functions Share on Authors: Chien-Chung Tsai Mentor Graphics Corporation, Wilsonville, OR and University of California, Santa Barbara Mentor Graphics Corporation, Wilsonville, OR and University of California, Santa BarbaraView 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 DAC '96: Proceedings of the 33rd annual Design Automation ConferenceJune 1996 Pages 242–247https://doi.org/10.1145/240518.240563Online:01 June 1996Publication History 8citation376DownloadsMetricsTotal Citations8Total Downloads376Last 12 Months4Last 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

This paper presents a multilevel logic synthesis method that achieves 100% single stuck-at fault testability. We assume any cell library composed of AND/OR gates. The Fixed Polarity Reed-Muller forms are used to build the initial design. Algebraic factorizations and redundancy removal are two major steps that are used in deriving the final circuit. A predetermined set of input patterns is applied to identify redundancies and serves as the test set for the resulting circuit. Therefore, test pattern generation is not needed. Experimental results show that our method produces circuits with area comparable to Berkeley SIS 1.2.

This paper presents a very efficient Boolean logic optimization method. The boolean optimization is achieved by adding and removing redundant wires in a circuit. Our algorithm applies the reasoning of Automatic Test Pattern Generation (ATPG) which can detect redundancy efficiently. During the ATPG process, mandatory assignments are assignments which must be satisfied. Our algorithm analyzes different characteristics of mandatory assignments during the ATPG process. New theoretical results based on the analysis are presented which lead to significant performance improvements. The fast run time and the excellent scaling to large problems make our Boolean optimization method practical for industrial applications. Experiments show that the optimization results are comparable to those of Kunz and Pradhan (1994) while the run time is two orders of magnitude faster (average 126/spl times/ speed up). Furthermore, we report optimization results for several large examples, which were previously thought to be too large to be handled by Boolean optimization methods.

High speed synchronous digital systems require large switching currents to facilitate rapid signal transitions. These large currents create voltage drops on the power distribution network and necessitate expensive chip packaging with a large number of supply pins. In this paper we propose a novel technique to reduce the dynamic transient current drawn from the supply pins. Our approach is based on sub-dividing the synchronous clocking into multiple sub-clocks with relative skew. This spreads the computation across the entire clock cycle instead of largely occurring at the beginning. Timing constraints must also be obeyed, so that no races or timing errors are introduced. We propose an exact algorithm based on integer linear programming to solve this problem. We have used our method in the design of a 5 GHz ECL encoder chip to achieve a factor of two reduction in ground bounce, as shown by HSPICE simulations. We also obtained order-of-magnitude improvements in ground bounce on benchmarks laid our in submicron CMOS technology. The approach potentially leads to significant reductions in packaging costs.

In this paper, we present a new method for detecting groups of symmetric variables of completely specified Boolean functions. The canonical Generalized Reed-Muller (GRM) forms are used as a powerful analysis tool. To reduce the search space we have developed a set of signatures that allow us to identify quickly sets of potentially symmetric variables. Our approach allows for detecting symmetries of any number of inputs simultaneously. Totally symmetric functions can be detected very quickly. The traditional definitions of symmetry have also been extended to include more types. This extension has the advantage of grouping input variables into more classes. Experiments have been performed on MCNC benchmark cases and the results verify the efficiency of our method.

In this paper, we present logic optimization techniques for multilevel combinational networks. Our techniques apply a sequence of perturbations which result in simplification of the circuit. The perturbation and simplification is achieved through wires/gates addition and removal which are guided by the Automatic Test Pattern Generation (ATPG) based reasoning. The main operations of our approaches are incremental transformations of the circuit (such as adding wires/gates and changing gate's functionality) to remove some particular wire, At each iteration, a summary information of such wires/gates addition and removal is precomputed first. Then, a transformation is chosen to remove several wires at once. We have performed experiments on MCNC benchmarks and compared the results to those of misII and RAMBO. Experimental results are very encouraging.

This paper proposes an efficient algorithm for technology mapping targeting table look-up (TLU) blocks. It is capable of minimizing either the number of TLUs used or the depth of the produced circuit. Our approach consists of two steps. First a network of super nodes, is created. Next a Boolean function of each super node with an appropriate don't care set is decomposed into a network of TLUs. To minimize the circuit's depth, several rules are applied on the critical portion of the mapped circuit.

In this paper, we study the two-dimensional FPGA, Xilinx-like routing architectures and present the first known computational complexity results for them. The routing problem is formulated as a two-dimensional interval packing problem and is proved to be NP-complete with or without doglegs. Next, we consider other routing structures obtained from the industrial one by arbitrarily changing switch box connection topology while maintaining the same connection flexibility. There is an exponentially large number of such routing structures. We further prove that there does not exist a better routing architecture among the members of this large domain. In addition, we prove that there is no constant bound on the mapping ratio of a track number required by a detailed routing to a global routing channel density for the studied architectures. Finally, we show two directions of changing the routing architectures which yield polynomial time mapping solutions and constant bounded mapping ratios. Our theoretical analysis is intended to give some insight to, and understanding of this new routing problem's fundamental properties.

No abstract available.

No abstract available.

Local don't cares of an internal node expressed in terms of its immediate inputs are usually of interest. One can directly apply any two-level minimizer on the on-set and the local don't cares set to simplify an internal node. In this paper, we propose a memory efficient technique to calculate local don't cares of internal nodes in a combinational circuit. Our technique of calculating local don't cares makes use of automatic test pattern generation (ATPG) approach which allows us to identify quickly whether a cube in the local space is a don't care or not. Unlike other approaches which construct an intermediate form of don't cares in terms of the primary inputs, our technique directly computes the don't care cubes in the local space. This gives us a significant advantage over the previous approaches in memory usage. Experimental results on MCNC benchmarks are very encouraging.

In the process of VLSI design, specifications are often changed. It is desirable that such changes will not lead to a very different design so that a large part of engineering effort can be preserved. We consider synthesis algorithms for handling such engineering changes. Given a synthesized network, our algorithm modifies it minimally to realize a new specification.

Article Power optimal buffered clock tree design Share on Authors: Ashok Vittal 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 DAC '95: Proceedings of the 32nd annual ACM/IEEE Design Automation ConferenceJanuary 1995 Pages 497–502https://doi.org/10.1145/217474.217577Published:01 January 1995 32citation571DownloadsMetricsTotal Citations32Total Downloads571Last 12 Months3Last 6 weeks1 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

We propose topology design of power distribution nets using a novel method for capturing the temporal characteristics of sink currents -the current compatibility graph.This graph carries information necessary for net area optimization.We propose a new algorithm for simultaneous topology design and wire sizing that can handle large designs.Our techniques result in significant area improvements on benchmark instances.

We propose a novel optimization scheme that can improve the routing by reducing a newly observed router decaying effect.A pair of greedy-grow algorithms, each emphasizing a different optimization target are designed.By applying one algorithm first and then switching to the other when the first one approaches its decaying stage, the undesired effect can be significantly reduced and thus better results are produced.On the tested MCNC and industry benchmarks, in addition to our very low segment consumption the total number of tracks used by our scheme is 37% less than a published conventional maze router and 22% less than the best known 2-step global/detailed router [4,5].Our results show that complicated multi-objective problems could be effectively attacked by coupling low complexity algorithms that traverse the solution space in orthogonal directions.This idea is applicable on both algorithmic and architectural optimization approaches [7].

Traditionally, the circuit partitioning problem is done by first modeling a circuit as a graph and then partitioning is performed on the modeling graph. Using the concept of alternative wires, we propose an efficient method that is able to preserve a local optimal solution in the graph domain while a different graph, representing the same circuit, is generated. When a conventional graph partitioning technique reaches a local optimal solution, our proposed technique generates a different graph that is logically equivalent to the original circuit, and that has equal or better partitioning solution. Faced with a different graph which is newly generated together with a currently good partitioning solution, a conventional graph partitioning technique may then escape from the optimum and continue searching for better solutions in a different graph domain. The proposed technique can be combined with almost any graph partitioner. Experiments show encouraging results.

Conventional scan design imposes considerable area and delay overhead by using larger scan flip-flops and additional scan wires without utilizing the functionality of the combinational logic. We propose a novel low-overhead scan design methodology, called cost-free scan, which exploits the controllability of primary inputs to establish scan paths through the combinational logic. The methodology aims at reducing scan overhead by (1) analyzing the circuit to determine all the cost-free scan flip-flops, and (2) selecting the best primary input vector to establish the maximum number of cost-free scan flip-flops on the scan chain. Significant reduction in the scan overhead is achieved on ISCAS89 benchmarks, where in full scan environment, as many as 89% of the total flip-flops are found cost-free scannable, while in partial scan environment, reduction can be as high as 97% in scan flip-flops needed to break sequential loops.

In this paper we study the problem of "properly" distributing the set of crossings (i.e., intersection of nets), of a given global routing, among the regions. Each region is assigned a quota, being the maximum number of crossings allowed in that region, which depends on its area and its complexity (e.g., the number of wets going through it and the number of terminals it contains). The crossing distribution problem (CDP) is to find a net ordering at each boundary as to minimize the total number of crossings and to satisfy the quotas. We propose an O(mn/sup 2/+m/spl xi//sup 3/2/) time algorithm for CDP, where m is the number of modules, n is the number of nets, and /spl xi/ is the number of crossings.>

In this paper, we propose a layout driven synthesis approach for Field Programmable Gate Arrays (FPGAs). The approach attempts to identify alternative wires and alternative functions for wires that cannot be routed due to the limited routing resources in FPGA. The alternative wires (in the logic level) that can be routed through less congested areas substitute the unroutable wires without changing the circuit's functionality. Allowing the logic blocks to have alternative functions also increases the flexibility of routing. The redundancy addition and removal techniques are used to identify such alternative wires. Experimental results are presented to demonstrate the usefulness of this approach. For a set of randomly selected benchmark circuits, on the average, 30%-50% of wires have alternative wires. These results indicate that the routing flexibility can be substantially increased by considering these alternative wires. Our prototype system successfully completed the routing for two AT&T designs that cannot be handled by an FPGA router alone. The proposed synthesis technique can also be applied to standard cell and gate array designs to reduce the routing area.

In this paper we present a new method for Boolean matching of completely specified Boolean functions.The canonical Generalized Reed-Muller forms are used as a powerful analysis tool.Input permutation, as well as input and output negation for matching are handled simultaneously.To reduce the search space for input correspondence, we have developed a method that can detect symmetries of any number of inputs simultaneously.Experiments on MCNC benchmark circuits are very encouraging.

We propose a new algorithm for the performancedriven interconnect design problem, based on alphabetic trees.The interconnect topology is determined in a global manner and does not greedily add edges as in conventional approaches.The algorithm can handle cases where the sink capacitances are different.Good results are obtained while running two to sixty times faster than three existing algorithms on practical instances.

In this paper, we consider the problem of mapping a given global route to a detailed route for two dimensional homogeneous FPGAs. It has been shown that this problem is NP-complete on a popular Xilinx-4000-like routing architecture. Here, we further prove that this problem remains NP-complete for an arbitrary fixed switch box topology of the same connection flexibility, with or without doglegs allowed in detailed routes.>

We present a new method for detecting groups of symmetric variables in completely specified Boolean functions. The canonical Generalized Reed-Muller forms are used as a powerful analysis tool. To reduce the search space a set of signatures which identify quickly sets of potentially symmetric variables has been developed. Detecting symmetries of any number of inputs is done simultaneously. Totally symmetric functions can be detected very quickly. The traditional definitions of symmetry have been extended to include more types allowing the grouping of input variables into more classes. Experiments have been performed on MCNC benchmark circuits and the results are very encouraging.>

Each Boolean function with fixed polarity of variables can be represented uniquely in a two-level AND/XOR form, called the generalized Reed-Muller (GRM) form. The minimization problem is to find the optimal polarity that requires the least number of product terms in the GRM representation. An efficient algorithm was developed to extract product terms of Boolean function, given a polarity of variables. It achieves the lower bound complexity. A heuristic algorithm targeting the minimization problem is proposed. It derives the polarity for every variable and extracts all product terms simultaneously. It is based on the concept of a Boolean center for minterms, which emulates the center of gravity concept in geometry. The experimental results are very encouraging.>

A circuit simulation technique based on a stepwise equivalent conductance model of a nonlinear resistive device is introduced. The major advantage of this technique is that it eliminates the need to employ Newton-Raphson iterations for the implicit integration. The technique, when applicable, is consistent, absolutely stable, and convergent. It is demonstrated that a second order of accuracy (the local truncation error for integration is of the cubic order of the time step used) is achieved by solving linear equations for each integration step. When applied to digital MOS circuits, the technique takes advantage of the fact that voltage waveforms can be modeled to a good approximation as piecewise-linear functions and thus provides further speedup in the simulation. The program, called SWEC, has been implemented, and has proved to be accurate and efficient on a large number of circuit examples. The results are compared with those for Relax2.3.iSPLICE3.0 XPsim. and SPECS2.>

The authors address the problem of how to realize a given combinational circuit described by means of Boolean equations using the minimum number of blocks of the target TLU table lookup architecture. Their Boolean decomposition scheme works directly on a reduced ordered binary decision diagram (ROBDD) of a subject function, using two techniques. The first, referred to as cutting, is an efficient implementation of Roth-Karp decomposition. The second technique is referred to as a substitution. The idea is to replace subgraphs of ROBDD by new variables. The substitution process is accompanied by certain reductions of the resulting ROBDD graph, which further decreases its size.>

The authors study the problem of 'properly' distributing the set of crossings (i.e., intersection of nets) of a given global routing among the regions. Each region is assigned a quota, being the maximum number of crossings allowed in that region, which depends on its area and its complexity (e.g., the number of nets going through it and the number of terminals it contains). The crossing distribution problem (CDP) is to find a net ordering at each boundary so as to minimize the total number of crossings and to satisfy the quotas. The authors propose an O(mn/sup 2/+m zeta /sup 3/2/) time algorithm for CDP, where m is the number of modules, n is the number of nets, and zeta is the number of crossings.>

This paper presents a heuristic approach to the optimal selection of standard cells in VLSI circuit design. We are considering a cell library composed of several templates (3-5) for each type of cell. These templates differ in area, driving capabilities, intrinsic delay, and capacitive loading. When realizing a logically synthesized circuit, we select the best templates from the cell library to minimize the total area of the cells under delay constraints. We have found a very successful heuristic approach to attack this discrete optimization problem.

A hierarchical technique is presented for floorplanning and pin assignment of general cell layouts. Given a set of cells with their shape lists, a layout aspect ratio, relative positions of the external I/O pads and upper bound delay constraints for a set of critical nets, the authors determine shapes and positions of the cells, locations of the floating pins on cells and a global routing solution such that a linear combination of the layout area, the total interconnection length and constraint violations for critical nets is minimized. Floorplanning, pin assignment and global routing influence one another during the hierarchical steps of the algorithm. The pin assignment algorithm is flexible and allows various user specified constraints such as pre-specified pin locations, feedthrough pins, length-critical nets and planar net topologies. Placement, timing and floorplanning results for a Xerox general cell benchmark are reported.>

Chip performance optimization is a crucial task in the modern design process. A method to improve the longest delay in a circuit built for standard cells is discussed. The method used to improve the designs is attractive because it does not require an increase in active area. All the improvements are achieved by a careful pin assignment. An efficient pin assignment algorithm is proposed. It has been implemented and the results are very encouraging.>

This paper presents a fast and efficient method for sizing power/ground networks. No restrictions on network topology or number of supplying pads are imposed. Wire widths are calculated such that the weighted area of wire segments is minimized while electromigration and voltage drops constraints are fulfilled. The algorithm proposed here runs 50% faster than the best methods reported for tree type network topologies.

The authors address the problem of incorporating timing constraints into the physical design of integrated circuits. First they formulate the problem and discuss graph models suitable for its analysis. Next, they describe algorithms resulting in placements of improved performance in comparison to placements whose objective is to minimize the summation of wire lengths on the chip. Finally, the authors show preliminary results of their placement programs for the sea-of-gates designs.>

This paper deals with the problem of single layer routing of power nets in building-block-style layout. It is assumed that power-supplying terminals are placed on the boundary of the chip and that each module within the chip has to be supplied by two or three different sources. The problem considered here is how to assign the power pads on the boundary of the chip so that their number is minimum while maintaining the planar routability of the power nets.

A heuristic algorithm for two dimensional routing utilizing two distinct layers is presented. It is assumed that all terminals are on the boundary of a rectilinear routing region with or without initial routes present. The router produces a Manhattan-style routing collapsed into one layer. Another program decides the layering, however, it is not described here. By default, when the layering program is not used, vertical segments of routes are placed on one layer, horizontal on the other.

We propose a new approach to the global routing of gate arrays. The method can handle any channel capacities and pin distributions on the chip. The global router first finds unique routes, then pushes connections to the periphery. As outer wiring capacity is consumed, the routing continues inward, connecting pins and making global cell assignments for nets by a centrifugal layering process. The goal is to avoid congestion in the center of the chip, a common problem with conventional methods.

Based on graph theory, a study of via minimization problem is presented. We show that the simplest problem of this type is NP-complete and propose a heuristic algorithm for topological via minimization.

In this paper, we present a heuristic algorithm for single-row routing. Our approach is based on the interval graphical representation of the given net list. The objective function for minimization is the street congestion. The problem is known to be intractable in the sense of NP-completeness, thus a polynomial-time heuristic algorithm is proposed. It has been implemented and tested with various examples. So far it has always produced optimal solutions.

In this paper we present a discussion of planarity testing and detailed single-layer routing. A program which implements the proposed algorithms for routing nets inside an arbitrarily shaped region has been written and tested. The results from this program are shown as examples.