The goal of design and technology co-optimization (DTCO) is to find a combination of parameter options (i.e., parameter setting values) of target process technology that enables to produce a target design implementation of optimal PPA (performance, power, area). Since the number of parameters sharply increases as the technology scales, recently, lots of attention has been paid to automating this DTCO process in both semiconductor foundry and academic research community. This paper addresses the problem of a full DTCO automation that deals with analyzing the numerous parameter options at advanced technology nodes. Precisely, we develop a machine learning (ML) based DTCO automation framework, which supports three key features: (1) an effective analysis on the changes of DTCO parameter options within an acceptable runtime; (2) a full exploration of chip/block-level PPA metrics through automatic standard cell (SC) library generation, for which we develop a new technique that enables to accelerate the iterative physical design process; (3) supporting both of Complementary FET (CFET) based SCs and multi-row-height SCs to account for future generation technology. Through experiments with benchmark circuits, it is shown that our DTCO automation framework is able to accurately predict the direction and magnitude of PPA changes of target designs with 5x sampling efficiency. In addition, it is shown that our SC layout generator supporting CFET and multi-rowheight SCs provides a timely DTCO process relevant to ongoing technology advancements.

Finding an optimal tool parameter configuration that achieves optimal design PPA (performance, power, area) through Design Space Optimization (DSO) in Physical Design (PD) has become increasingly important due to the rising complexity of Electronic Design Automation (EDA) tool chains in modern VLSI design. DSO is particularly challenging due to the high dimensionality of tool parameters, the abundance of discrete parameter options, and, most critically, the non-linear relationship between parameters and design PPA. This work overcomes two limitations of the prior state-of-the-art Bayesian Optimization (BO) based DSO methods for EDA tool parameter optimization. The two limitations are (1) a poor correlation of the similarity computation in BO engine between two sampling points with the actual similarity between the corresponding post-layout PPAs, resulting in far from the Pareto-optimal PPA exploration; (2) redundant evaluations occur frequently when discrete parameters are quantized. Precisely, we overcome limitation 1 by training AE (AutoEncoder) model using PPA outcomes of the prior sample points and using it to reshape the latent parameter space such that similarity in latent vectors aligns with the similarity in PPA, thereby justifying the accurate kernel-based similarity function in BO, while we address limitation 2 by reformulating the acquisition function in BO in a way to effectively sample the discrete parameter values in the continuous design space. In the meantime, through experiments, it is shown that using our DSO method with reshaped BO amenable to EDA tool parameter optimization is able to find tool parameter options of 59% larger HyperVolume and up to 16% improvement for single objective (i.e., a weighted sum of PPA) optimization.

3D ICs are renowned for their potential to enable high-performance and low-power designs by utilizing denser and shorter inter-tier connections. In the physical design flow of 3D ICs, the placement stage includes a differentiated design step to assign instances to different tiers, i.e., top or bottom, called tier partitioning. Despite its importance to overall circuit performance, previous tier partitioning approaches have not taken power-performance-area (PPA) optimization into account, leading to degradation in timing and increased power consumption. In this paper, we propose a novel tier partitioning method in 3D IC placement that concurrently optimizes all PPA-relevant aspects, i.e., intertier cuts, overlapping areas, tier transitions along timing-critical paths, and local/global area balance. We first reduce the problem complexity with netlist clustering based on logical and physical relations, and then formulate an integer-linear programming (ILP) model for each cluster to find an optimal solution. Experiments on various benchmarks demonstrate that our method achieves significant improvements over previous tier partitioning results in terms of all PPA metrics, including 1.23% reduction in power consumption, 24.08% reduction in total negative slack (TNS), and 3.44% reduction in wirelength on average.

In deep-submicron technology nodes, I/O pin accessibility on the cells is crucial for successful net routing in physical design. For this reason, the conventional design flows have paid a considerable attention to acquiring the cell library with high pin accessibility to facilitate the net routing task. Nevertheless, the increase in routing failures is inherently unavoidable as the cell size shrinks with the progress of the technology node. In this context, this work proposes a new technique called adaptive pin-pattern modification (APM) to tackle this fundamental problem. Precisely, our proposed ECO-routing method based on adaptive pin-pattern modification makes use of three novel pin-pattern modifications on standard cells, which are referred to as pin-shift-trim (PST), pin-free (PF) and pin-bridge (PB). By applying these pin-pattern modifications adaptively and systematically to suit the circumstances to the individual cell instances with pin access failure, our ECO-router is able to explore the routable paths more extensively and effectively over the sequential, maze-routing based, ECO-routers but spend a much shorter time over the concurrent ECO-routers. Experimental results show that our proposed APM-enabled ECO-router resolves 17.7% of pin inaccessibility cases that a commercial tool has failed to find legal routes, with no penalty of chip PPA, and achieves over 116x speedup compared to the concurrent MCF (multi-commodity flow) based ECO-router.

In this paper, a new approach to the problem of synthesizing standard cells is presented. The top priority objective in the conventional approaches has been invariably placed on minimizing cell area. However, in our approach, we place the top priority on minimizing cell delay as opposed to minimizing cell area, which has never been addressed as yet, but is very valuable and highly important for implementing high-performance chips at advanced technology nodes. Precisely, we propose a totally different approach, developing a cell delay driven layout synthesis method, which is composed of three steps: (1) a critical path driven transistor placement, which is formulated into a search tree based exhaustive placement enumeration, employing an effective pruning technique, followed by (2) an optimal transistor folding, formulating it into an instance of DP (dynamic programming) to reduce cell area by maximizing the occurrences of diffusion sharing and minimizing the oxide diffusion jog rule violations, then (3) an optimal critical net driven in-cell routing, formulating it into an instance of SMT (satisfiability modulo theory) problem. In the meantime, through experiments with benchmarks, it is shown that our cell synthesis approach is able to produce cells with up to 9.3% shorter delay. More importantly, by using those cells, we are able to increase the circuit clock frequency by 7.2% on average while retaining nearly the same chip area and power consumption over that produced by using the conventional cells.

Design technology co-optimization (DTCO) is the process of optimizing design and process technology together to enhance performance, power efficiency, chip utilization, and manufacturing cost/yield. Through DTCO, we are able to evaluate technologies, design rules, and cell architectures using block-level PPA (performance, power, area) analysis, which greatly helps semiconductor fabs reduce cost and shorten time-to-market in advanced process development with substantial architectural innovation.

Utilizing multibit flip-flops (MBFFs) in circuit implementation offers a considerable saving on the dynamic power dissipated at the clock networks. However, indiscreetly allocating MBFFs by grouping single-bit flip-flops at the logic synthesis or placement stage in order to greedily save dynamic power severely hinders a full applicability of useful clock skew scheduling to the individual flip-flops in MBFFs, failing in effectively optimizing circuit timing. This is because the two internal clock inverters, consequently, the clock skew value, in an MBFF are shared by all of the flip-flops in the MBFF. This work overcomes this inherent limitation of inflexibility in MBFFs for useful clock skew scheduling by proposing a comprehensive design and technology co-optimization (DTCO) framework. To this end, we devise a new layout of MBFF cells called multiskewed MBFF layout, in which different clock skew values can be set to the individual internal flip-flops at the cost of additional internal clock inverters. With the multiskewed MBFFs, we propose a three-step DTCO flow: 1) DTCO-based flip-flop clustering at the logic stage, which clusters flip-flops considering multiskewed MBFFs; 2) DTCO based on in-place MBFF debanking technique at the preroute stage to facilitate the full applicability of useful skew scheduling at the subsequent stages; and 3) DTCO utilizing MBFF cell layout diversification at the post-route stage, by which useful clock skew scheduling can effectively resolve timing violations. Through experiments with OpenCores benchmark circuits, it is shown that our proposed DTCO flow of reinforcing the effectiveness of useful clock skew scheduling on circuits with MBFF instances is able to reduce the worst and total negative slacks by 36.73% and 50.76%, respectively, while decreasing the clock and total power consumption by 43.46% and 22.70% over that produced by the conventional flow using a state-of-the-art commercial tool.

Though using multi-bit flip-flop (MBFF) cells provide the benefit of saving dynamic power, its big cell size with many D/Q-pins inherently entails two critical limitations, which are (1) the loss of full flexibility in optimizing the wires connecting to the D/Q-pins in MBFFs and (2) the loss of selectively resizing i.e., controlling the driving strength of internal flip-flops in MBFFs to optimize timing. In this work, we propose a comprehensive solution to resolving those limitations through design and technology co-optimization (DTCO) in physical design flow. Specifically, to address limitation 1, given an input circuit with MBFF allocation and binding, at the post-placement stage we explore diverse layouts of MBFF cells with various D/Q-pin locations and rebind MBFF instances in the circuit to the MBFF cells that are the most suitable for minimizing the wirelength connecting D/Q-pins. Meanwhile, to address limitation 2, at the post-route stage we explore MBFF cell layouts of non-rectangle, precisely, L- and T-shape to control the driving strength of internal flip-flops selectively, by which we rebind MBFF instances with negative slack to the area-minimal rectangle or non-rectangle MBFF cells to optimize timing while increasing the power overhead minimally. Through experiments with benchmark circuits, it is shown that our DTCO driven MBFF rebinding method is able to produce the circuit implementations with 1.42% less wirelength in comparison with that produced by the state-of-the-art commercial EDA tool using MBFFs.

As the VLSI technology continues to scale beyond 5nm, a strong demand on the continuing layout reduction of standard cells is required. However, the standard cells with conventional FinFET or nanosheet-FET structure are becoming much hard to meet this requirement due to the lateral P-FET and N-FET separation. It has been widely accepted that Complementary-FET (CFET) is a promising technology, which stacks P-FET on N-FET or vice versa, to achieve this objective. In comparison with synthesizing the conventional FET based standard cells, two prominent optimization tasks in CFET based multi-row cell synthesis that significantly affect the cell quality, in terms of area and routability, are (1) determining transistor folding shapes and (2) determining placement order of transistors with fully secured vertical i.e., z-directional routing space on the stacked FETs as well as buried power rail (BPR). In this work, we propose an optimal solution to the combined problem of tasks 1 and 2. Precisely, we develop a search tree-based area-optimal method of transistor folding and placement, in which we accelerate the cost computation of partial solutions by formulating it into dynamic programming while performing a strict feasibility checking of securing in-cell vertical routing space of partial solutions by formulating and solving it into an instance of network flow problem. In the meantime, through experiment with benchmark circuits, it is shown that the CFET cells produced by our cell synthesizer are 5% smaller in size on average even with 38% shorter total metal length and 70% less use of metal2 for in-cell routing over the cells produced by the recent state-of-the-art CFET cell generator.

To generate standard cell (SC) layouts of competitive quality, pin accessibility and in-cell routing congestion should be thoroughly taken into account. In this work, we develop a new tool to address this issue. Precisely, we (1) develop a technology compilation module that can convert diverse cell architectures and design rules into grid based design parameters and layer configuration, (2) generate optimal FET placement using metrics that can accurately and efficiently predict intra-cell pin accessibility and in-cell routing congestion, and (3) introduce the concept of ghost-via and ghost-metal, and formulate in-cell routing using satisfiability modulo theory for pin separation and extension. Experimental results show that our system is able to synthesize SC layouts with a routing completion rate of 95~98 %, which is far better than the previous SC layout generator, and produce layouts comparable to the ARM's hand-crafted layouts. In addition, the design implementations produced by using our 2-layer ID SC library exhibit on average 76.6% fewer design rule violations (DRVs) with similar or better quality of timing and area, while in comparison with that produced by using the library of hand-crafted ARM SCs, the implementations produced by using our L-layer 2D SC library exhibit on average 11.7% smaller area with comparable timing and DRV count.

Finding design flow parameters that ensure a high quality of final chip is a very important task, but requires an excessive amount of effort and time. In this work, we automate this task by proposing a machine learning (ML)-based design space optimization (DSO) framework. Rather than simply applying one ML model exclusively or multiple ones in a naive manner, we develop a comprehensive chain of ML engines which is able to explore the design parameter space more economically but effectively to make a fast convergence on finding the best parameter set. Specifically, we solve the DSO problem in three steps: (1) random sampling of parameter sets and then performing design evaluation to produce an initial ML training dataset; (2) iteratively, downsizing parameter dimension through Principal Component Analysis (PCA) followed by sampling through an exploration-centric mechanism which is internally driven by Bayesian Optimization (BO) and then evaluating the sample; (3) iteratively, sampling through an exploitation-centric mechanism driven by XGBoost regression and then checking anomaly by using XGBoost classification followed by evaluating the sample if it's not anomaly. From our experiments with benchmark designs, it is shown that our approach is able to find design parameter sets which are far better than that found by the prior state-of-the-art ML-based approaches, even with fewer number of design evaluations (i.e., EDA tool runs). In addition, in comparison with the designs produced by using the default parameter setting, our DSO framework is able to improve the design PPA metrics by$5\sim 30{\%}$I.

In this paper, we address three core problems in the layout synthesis of multi-row standard cells: transistor folding, row partitioning, and transistor placement. We propose a comprehensive solution to the problem of synthesizing area-optimal multi-row standard cells by seamlessly integrating transistor folding and row partitioning into the transistor placement framework. Additionally, we introduce a systematic methodology to construct a standard cell library. This methodology determines the cell types among single-row, multi-row with VDD-abut, and multi-row with VSS-abut in order to achieve an optimal trade-off between power, performance, and area (PPA) for the target design implementation. Experimental results demonstrate that for 4-routing track standard cells of the advanced technology nodes our multi-row cell generator increases the cell generation completion ratio from 72% to 100% and reduces the metal length for in-cell routing by 11.9% while maintaining comparable cell area compared to the area-minimal single-row cells. Furthermore, using our optimized cell library is able to reduce the target chip area by 4.2% and chip power by 7.0%, while all meeting timing and design rule constraints, compared to the state-of-the-art single-row standard cell library.

The main task of global routing in the physical design flow assigns nets to specific routing bins in a die with the objective of minimizing the total wirelength of the net routes while satisfying the horizontal and vertical track constraints over the bins. Thus, it is very important to tune the net topologies passing over the congested bins with a minimal increase of wirelength. In this work, we propose an effective net topology exploration and route tuning method to mitigate the routing congestion. Precisely, inspired by an encoding concept, called Rectilinear Edge Sequence (RES), developed in the prior work to compactly and conveniently represent a rectilinear Steiner tree (RST) for each net, we propose a method of systematically and effectively exploring alternative RES encodes for the nets in congested regions so as to find the best suited RSTs for reducing the congestion at a minimal cost of wirelength increase. Through experiments with benchmark circuits, it is shown that our net topology exploration and route tuning method is able to reduce the amount of track overflows by 10.7% with only a 1.7% increase in wirelength when compared to using net topologies of minimal wirelength produced by the state-of-the-art prior work.

Resolving the design rule checking (DRC) violations at the pre-route stage is critically important to reduce the time-consuming design closure process at the post-route stage. Recently, noticeable methodologies have been proposed to predict DRC hotspots using Machine Learning based prediction models. However, little attention has been paid to how the predicted DRC violations can be effectively resolved. In this paper, we propose a pre-route DRC violation resolution methodology that is tightly coupled with fully compatible prediction model. Precisely, we devise different resolution strategies for two types of DRC violations: (1) pin accessibility (PA)-related and (2) routing congestion (RC)-related. To this end, we develop a fully predictable ML-based model for both PA and RC-related DRC violations, and propose completely different resolution techniques to be applied depending on the DRC violation type informed by the compatible prediction model such that for (1) PA-related DRC violation, we extract the DRC violation mitigating regions, then improve placement by formulating the whitespace redistribution problem on the regions into an instance of Bayesian Optimization problem to produce an optimal cell perturbation, while for (2) RC-related DRC violation, we manipulate the routing resources within the regions that have high potential for the occurrence of RC-related DRC violation. Through experiments, it is shown that our methodology is able to resolve the number of DRC violations by 26.54%, 25.28%, and 20.34% further on average over that by a conventional flow with no resolution, a commercial ECO router, and a state-of-the-art academic predictor/resolver, respectively, while maintaining comparable design quality.

It is intuitively clear that a circuit to be implemented by selectively utilizing standard cells of various non-integer multiple-heights (NIMH) (e.g., mixed use of 6-track, 7.5-track, and 9-track cells) is able to provide a better opportunity in optimizing power, performance, and area over that by using cells of single-height only or of integer multiple-heights only. However, from the cell placement legalization point of view, the issues to be addressed for placement legalization on NIMH designs are very complex. And this paper primarily focuses on introducing novel ideas for row placement when utilizing NIMH cells, which involves determining the row pattern. The most inter-dependent and critical tasks, which are rather unique to the NIMH cell placement legalization problem, are ( task 1 ) for the cells of the same height, distributing and assigning them to a set of distinct rows on a die and ( task 2 ) determining the location of the rows containing cells of the same height. We solve the legalization problem by, starting from an initial row placement, iteratively solving the two tasks by formulating task 1 into an instance of row-capacity constrained network flow problem, followed by solving task 2 which leads to an optimal vertical displacement of the cells in the rows. Meanwhile, through experiments, it is shown that our network flow driven global cell assignment to rows for NIMH cell placement problem tightly linking the optimal determination of row location is able to reduce the total amount of cell displacements from the global (initial) placement by 9.5% and 51.2% in comparison with that produced by a greedy approach and the conventional state-of-the-art NIMH cell placement legalization method, respectively.

Deep learning (DL) models have recently paid considerable attention to timing prediction in the place-and-route (P&R) flow. As yet, the DL-based prior works are confined to timing prediction at the time-consuming routing stage, and very few have addressed the timing prediction problem at the placement, i.e., at the pre-route stage. Moreover, no work has addressed a seamless link of timing prediction at the pre-route stage to the final timing optimization through commercial P&R tools. In this work, we introduce a novel framework called DTOC-P that seamlessly integrates deep-learning-driven timing optimization into cutting-edge commercial P&R tools. Our framework is composed of two phases: (1) the pre-route timing prediction phase that performs DL-driven arc delay and arc output slew prediction with an elaborated hierarchical model; (2) the timing optimization phase which incorporates commercial P&R tools with DL-driven prediction outcomes to perform timing optimization. In addition, DTOC-P framework achieves enhanced practicality with the application of continual learning in the timing prediction phase, and the concept of anomaly detection in the timing optimization phase. Experimental results show that our DTOC-P framework improves pre-route prediction accuracy by up to 55% and 47% on arc delay and arc output, which are further enhanced to encompass a broader range of designs by continual learning supported in DTOC-P, practically using a tenfold reduced training time compared to re-training all datasets from scratch. In terms of timing optimization, our experiments reveal that DTOC-P framework improves WNS, TNS, and the number of timing violation paths by up to 12%, 41%, and 34%, respectively, which is a remarkable progress compared to its predecessor through the integration of anomaly detection that excludes potential outliers to effectively protects against erroneous timing updates during the timing optimization phase.

The three major tasks in standard cell layout synthesis are transistor folding, transistor placement, and in-cell routing, which are tightly interrelated, but generally performed one at a time to reduce the extremely high complexity of design space. In this article, we propose an integrated approach to the two problems of transistor folding and placement. Precisely, we propose an optimal algorithm of search tree-based design space exploration, devising a set of effective speeding up techniques as well as dynamic programming-based fast cost computation. Our algorithm also incorporates the minimum oxide diffusion (OD) jog constraint, which closely relies on both of transistor folding and placement. To our knowledge, this is the first work that tries to simultaneously solve the two problems. In addition, to make an effective cell layout synthesis flow down to in-cell routing, we provided a fast in-cell routability estimation metric to be used in transistor placement and a method to explore cell layouts by varying the cell size constraint. Through experiments with the transistor netlists and design rules in the ASAP 7-nm library, it is shown that our proposed method is able to synthesize fully routable cell layouts of minimal size within very fast time for each netlist, outperforming the cell layout quality in the ASAP 7-nm library, which otherwise, may take several hours or days to manually complete layouts of the quality level comparable to ours.

Multi-bit flip-flops (MBFFs) are widely used in modern circuit designs to save the power consumption. That is, the benefit of using MBFFs as opposed to single-bit flip-flops is sharing in-cell clock inverters among the master and slave latches in the internal flip-flops of MBFFs. Theoretically, the more flip-flops an MBFF has, the more power saving it can achieve. However, in practice, physically increasing the size of MBFF to accommodate many flip-flops imposes two new challenging problems in physical design: (1) non-flexible MBFF cell flipping for multiple D-to-Q signals and (2) unbalanced or wasted use of MBFF footprint space. In this work, we solve the two problems in a way to enhance routability and timing at the placement and routing stages. Precisely, for problem 1, we make the non-flexible MBFF cell flipping be fully flexible by generating MBFF layouts supporting diverse D-to-Q flow directions in the detailed placement to improve routability and for problem 2, we enhance the setup and clock-to-Q delay on timing critical flip-flops in MBFF through gate upsizing (i.e., transistor folding) by using the unused internal space in MBFF to improve timing slack at the post-routing stage. Through experiments with benchmark circuits, it is shown that our proposed design and technology co-optimization (DTCO) flow for designs with MBFFs is able to produce chip implementations with 20.5% fewer design rule violations and 47.7% reduced worst timing slack with a little power fluctuation in comparison with that produced by the conventional design flow with MBFFs.

Advanced technology nodes face challenges related to DRVs (design rule violations), primarily due to (1) pin inaccessibility and routing on congested region. While various ML (machine learning) techniques have been introduced to address these issues during placement, aggregating data on pin accessibility and routing congestion for ML model training has proven very challenging. This study presents an innovative ML-based approach to DRC (design rule check) hotspot prediction that effectively captures the combined impact of pin accessibility and routing congestion. Specifically, we introduce the concept of pin proximity graph, which accurately represents spatial information regarding cell I/O pins and pin-to-pin disturbance relationships. We then propose a novel ML model called PGNN, which seamlessly integrates GNN (Graph Neural Network) and U-net. In this approach, GNN handles the incorporation of pin accessibility information derived from the pin proximity graph while U-net extracts routing congestion information from grid-based features. Additionally, we solidify the capability of our prediction model toward ensuring the practical applicability and sustainability of our model by integrating two learning methodologies into our model training framework. Those are (1) transfer learning whose objective is to retain the same level of prediction accuracy in spite of not having enough data on the new process node and (2) incremental learning whose objective is to reduce the train time while maintaining the model accuracy in similar quality when new circuits are added.

Recently, deep-learning (DL) models have paid a considerable attention to timing prediction in the placement and routing (P&R) flow. As yet, the DL-based prior works are confined to timing prediction at the time-consuming global routing stage, and very few have addressed the timing prediction problem at the placement, i.e., at the pre-route stage. This is because it is not easy to “accurately” predict various timing parameters at the pre-route stage. Moreover, no work has addressed a seamless link of timing prediction at the pre-route stage to the final timing optimization through making use of commercial P&R tools. In this work, we propose a framework called DTOC, to be used at the pre-route stage for this end. Precisely, the framework is composed of two models: (1) a DL-driven arc delay and arc output slew prediction model, performing in two levels: (level-1) predicting net resistance (R), net capacitance (C), and arc length (Len), followed by (level-2) predicting arc delay and arc output slew from the R/C/Len prediction obtained in (level-1); (2) a timing optimization model, which uses the inference outcomes in our DL-driven prediction model to enable the commercial P&R tools to calculate the full path delays, setting update timing margins on paths, so that the P&R tools should use more accurate margins on timing optimization. Experimental results show that, by using our DTOC framework during timing optimization in P&R, we improve the pre-route prediction accuracy on arc delay and arc output slew by 20~26% on average, and improve the WNS, TNS, and the number of timing violation paths by 50~63 % on average.

Traditionally, the synthesis of standard cells invariably assumes that the gear ratio (GR) between the gate poly pitch in the cells and the metal pitch of the first vertical metal layer (to be used for routing) over the gate poly is 1:1 for chip implementation. However, the scaling trend in sub-10nm node CMOS designs is that GR is changing from 1:1 to 3:2 or 4:3, which means the number and location of pin access points vary depending on the cell placement location, thereby causing hard-to-pin-access if the pin access points were aligned on the off-track routing pattern. This work overcomes the pin inaccessibility problem caused by non-1:1 GR in chip implementation. Precisely, we propose a non-1:1 GR aware DTCO (design and technology co-optimization) flow to generate cells with pin patterns that are best suited to the implementation of target design. To this end, we propose two new tasks to be installed in our DTCO framework: (1) from the existing cells optimized for 1:1 GR, we relocate their pin patterns amenable to non-1:1 GR, so that a maximal pin accessibility should be achieved; (2) we incrementally update the pin patterns of the cell instances with routing failures due to pin inaccessibility in the course of the DTCO iterations to produce the cells with best fitted pin patterns to the implementation of target design. We formulate task 1 into a problem instance of dynamic programming to find an optimal solution of pin positions, considering design rule and access conflict constraints while we solve task 2 by devising an assessment function on the pin accessibility enhanced by pin pattern extension to find out the most suitable direction for the extension. In the meantime, through experiments with benchmark circuits, it is shown that our DTCO methodology optimizing pin patterns amenable to non-1:1 GR is able to produce chip implementations with on average 5.88 × fewer routing failures at no additional wirelength, timing, and power cost.

Conventional standard cell libraries are composed of cells of diverse logic functions, all of which commonly and strictly maintain an equal height i.e., single-row-height. However, as the process technology node advances, large cells such as flip-flops are designed with multi-row-height to balance the horizontal and vertical pin accessibility to the cells. For designs with cell instances of mixed-height i.e., single-row-height and multi-row-height cell instances, the placement legalization problem becomes more difficult since the additional power-rail alignment constraint should be imposed to the multi-row-height cells. In this work, we propose a polynomial-time refinement algorithm amenable to the placement legalization of mixed-height cells. Precisely, from a placement legalization delivered by a state-of-the-art commercial tool, our algorithm iteratively and effectively refines the legalization by employing our comprehensive cell swapping mechanism with efficient internal data structures for cost computation. Through experiments with ISPD2015 benchmark circuits, it is shown that our method is able to simultaneously reduce the total displacement and HPWL by 16.7% and 20.8% on average over the legalization results produced by the state-of-the-art commercial tool for designs with the chip utilization over 0.8, respectively.

Utilizing multi-bit flip-flops (MBFFs) in circuit implementation offers a considerable saving on the dynamic power dissipated at the clock networks. However, indiscreetly allocating MBFFs by grouping single-bit flip-flops at the logic synthesis or placement stage in order to maximally save dynamic power severely hinders a full applicability of useful clock skew scheduling to the individual flip-flops in MBFFs, failing in effectively optimizing circuit timing. This is because the two internal clock inverters, consequently, the clock skew value, in an MBFF are shared by all of the flip-flops in the MBFF. This work overcomes this inherent limitation of inflexibility in MBFFs for useful clock skew scheduling by proposing a comprehensive DTCO (design and technology co-optimization) framework integrating two viable techniques, called in-place MBFF debanking and skew driven cell layout diversification. Precisely, we proposed a two-step DTCO flow: (1) DTCO based on in-place MBFF debanking technique at the pre-route stage to facilitate the full applicability of useful skew scheduling at the subsequent stages and (2) DTCO utilizing MBFF cell layout diversification technique at the post-route stage, by which useful clock skew scheduling can effectively resolve timing violations. Through experiments with OpenCores benchmark circuits, it is shown that our proposed DTCO flow of reinforcing the effectiveness of useful clock skew scheduling on circuits with MBFF instances is able to reduce the worst and total negative slacks by 16.87% and 46.26% at the cost of 1.00% power overhead over that produced by the state-of-the-art conventional flow.

We address a new problem of transforming the long toggling/untoggling sequences of flip-flops' cycle-accurate activities into short embedding vectors, so that the flip-flop grouping for clock gating is practically feasible in terms of the memory usage and run time for checking activity similarity among flip-flops. To this end, we propose a machine learning based generation of embedding vectors which are accurate enough to predict the original flip-flop toggling sequences. Precisely, we develop a neural network model of LSTM (long short-term memory) based AE (autoencoder) model combined with SDAE (stacked denoising autoencoder) to take into account the time-series (i.e., clock cycle) similarity feature among the toggling sequences, which is essential to determine which flip-flops should be grouped together for clock gating. By integrating (1) our LSTM based embedding vector generation model, we propose two additional ML models for clock gating: (2) joint state probability predictor (JSP) model for generating 0-state probability of two embedding vectors, and (3) joint feature predictor (JFP) model for generating a new embedding vector that combines two embedding vectors.

One of the key issues in the synthesis of clock gating is how the flip-flops with similar activity patterns in the target design are identified and grouped, so that all flip-flops in each group should be clock-gated in a way to make a full effectiveness in power saving. As yet, due to the excessive runtime and explosive memory usage demand, the conventional grouping methods have relied on flip-flops‘ toggling probability or toggling pattern of ‘short’ length, which clearly results in the power saving far off that of the optimal grouping. In this work, we overcome this limitation by proposing a machine learning (ML) based flip-flop grouping for clock gating. Precisely, we devise (1) a convolutional autoencoder (CAE) model to produce a ‘short’ embedding vector corresponding to the ‘very long’ input activity pattern of every flip-flop, (2) a convolutional neural network (CNN) based ranker model to predict the degree of flip-flop activity similarity between two input embedding vectors, and (3) a CNN-based model to produce an embedding vector that combines two input embedding vectors. Then, we propose an ML based clock gating synthesis algorithm, which is able to reduce the total dynamic power on circuits by6.3% further on average over that by the conventional state-of-the-art clock gating with no timing violation by the gated logic delay as well as the satisfaction of physical proximity constraint on flip-flops for clock gating.

Minimum implant area (MIA) violation has emerged in the sub-micrometer technology which requires a certain amount of threshold voltage ($V_{\text {t}}$) area for the fabrication. Elimination of MIA violations in the sign-off layout thus becomes an inevitable task for a high-performance multiple-$V_{\text {t}}$design. Conventional approaches as well as the previous efforts to remove MIA violations bring severe defects to the final design in that locally moving cells or reassigning$V_{\text {t}}\text{s}$make the timing constraints unsatisfied or power consumption to be exploded. In this article, we propose a comprehensive MIA violation removal algorithm that fully and systematically controls the timing budget and power overhead with three sequential steps: 1) removing intra-row MIA violations by$V_{\text {t}}$reassignment under timing preservation and minimal power increments; 2) removing inter-row MIA violations with a theoretically optimal$V_{\text {t}}$reassignment while satisfying timing constraints; and 3) refining$V_{\text {t}}$reassignment to recover the power loss without violating both MIA constraints and timing closure. Moreover, we introduce a preprocessing algorithm at the preroute stage to remove a huge amount of MIA violations in advance for an additional runtime reduction without design quality degradation. Experiments through benchmark circuits show that our proposed approach completely resolve MIA violations while ensuring no timing violation and using 34.6% less power overhead on average than the conventional approaches and previous works. In addition, our preprocessing step reduces 45%–88% of MIA violations before the routing stage, which incurs 41% faster MIA removal on average in the final stage with similar design quality.

Fixing minimum implant area (MIA) violations in the post-route layout is an essential and inevitable task for the high-performance designs employing multiple threshold voltages. Unlike the conventional approaches, which have tried to locally move cells or reassign$V_{t}$(threshold voltage) of some cells in a way to resolve the MIA violations with little or no consideration of timing constraint, our proposed approach fully and systematically controls the timing budget during the removal of MIA violations. Precisely, our solution consists of three sequential steps: (1) performing critical path aware cell selection for$V_{t}$reassignment to fix the intra-row MIA violations while considering timing constraint and minimal power increments; (2) performing a theoretically optimal$V_{t}$reassignment to fix the inter-row MIA violations while satisfying both of the intra-row MIA and timing constraints; (3) refining$V_{t}$reassignment to further reduce the power consumption while meeting intra- and inter-row MIA constraints as well as timing constraints. Experiments through benchmark circuits show that our proposed approach is able to completely resolve MIA violations while ensuring no timing violation and achieving much less power increments over that by the conventional approaches.

The significantly increased density of pins of stan-dard cells and the reduced number of routing tracks at sub-10nm nodes have made the pin access problem in detailed routing very difficult. To alleviate this pin accessibility problem in detailed routing, recent works have proposed to make a small perturbation of cell shifting, cell flipping, and adjacent cells swapping in the detailed placement stage. Here, an essential element for the success of pin accessibility aware detailed placement is the installed cost function, which should be sufficiently accurate in predicting the degree of routing difficulty in accessing pins. In this work, we propose a new model of cost function that is comprehensively devised to overcome the limitations of the prior ones. Precisely, unlike the conventional cost functions, our proposed cost function model is based on the empirical routing data in order to fully reflect the potential outcomes of detailed routing. Through experiments with benchmark circuits, it is shown that using our proposed cost function in detailed placement is able to reduce the routing errors by 44 % on average while using the existing cost functions reduce the routing errors on average by at most 15 %.

An accurate DRC (design rule check) hotspot prediction at the placement stage is essential in order to reduce a substantial amount of design time required for the iterations of placement and routing. It is known that for implementing chips with advanced technology nodes, (1) pin accessibility and (2) routing congestion are two major causes of DRVs (design rule violations). Though many ML (machine learning) techniques have been proposed to address this prediction problem, it was not easy to assemble the aggregate data on items 1 and 2 in a unified fashion for training ML models, resulting in a considerable accuracy loss in DRC hotspot prediction. This work overcomes this limitation by proposing a novel ML based DRC hotspot prediction technique, which is able to accurately capture the combined impact of items 1 and 2 on DRC hotspots. Precisely, we devise a graph, called pin proximity graph, that effectively models the spatial information on cell I/O pins and the information on pin-to-pin disturbance relation. Then, we propose a new ML model, called PGNN, which tightly combines GNN (graph neural network) and U-net in a way that GNN is used to embed pin accessibility information abstracted from our pin proximity graph while U-net is used to extract routing congestion information from grid-based features. Through experiments with a set of benchmark designs using Nangate 15nm library, our PGNN outperforms the existing ML models on all benchmark designs, achieving on average 7.8~12.5% improvements on F1-score while taking 5.5× fast inference time in comparison with that of the state-of-the-art techniques.

The benefit of multi-bit flip-flop (MBFF) as opposed to single-bit flip-flop is sharing in-cell clock inverters among the master and slave latches in the internal flip-flops of MBFF. Theoretically, the more flip-flops an MBFF has, the more power saving it can achieve. However, in practice, physically increasing the size of MBFF to accommodate many flip-flops imposes two new challenging problems in physical design: (1) non-flexible MBFF cell flipping for multiple D-to-Q signals and (2) unbalanced or wasted use of MBFF footprint space. In this work, we solve the two problems in a way to enhance routability and timing at the placement and routing stages. Precisely, for problem 1, we make the non-flexible MBFF cell flipping to be fully flexible by generating MBFF layouts supporting diverse D-to-Q flow directions in the detailed placement to improve routability and for problem 2, we enhance the setup and clock-to-Q delay on timing critical flip-flops in MBFF through gate upsizing (i.e., transistor folding) by using the unused space in MBFF to improve timing slack at the post-routing stage. Through experiments with benchmark circuits, it is shown that our proposed design and technology co-optimization (DTCO) flow using MBFFs that solves problems 1 and 2 is very promising.

Since the width of flip-flop standard cells is relatively much longer than that of the cells of primitive gates, the impact of flipping flip-flop cells horizontally in the placement on routing complexity and timing is significant. However, as yet, no work has addressed the issue of how we can effectively exploit the well-known cell flipping technique to multi-bit flip-flop cells in placement. To this end, in this work, we introduce a concept of D-to-Q signal flipping for cell instances of multi-bit flip-flop where the directions of D-t-O signal flow of the individual flip-flop instances can be controlled separately and independently. Then, we propose an effective multi-bit cell flipping methodology based on the D-to-O signal flipping concept with the objective of enhancing routing complexity as well as timing slack in the placement optimization stage.

Clock gating saves dynamic power by shutting off a subtree of clock network during the idle state of the driven logic blocks. This paper proposes a new clock gating methodology based on a precise power saving analysis to overcome the ineffectiveness of the conventional logic structure based clock gating. Two new features exploited in our proposed clock gating are (i) the multiplexer selection signal probability that a flip-flop with multiplexer feedback loop receives a new input and (ii) the joint probability of selection signals that two flip-flops with different multiplexor selection signals both receive new inputs at the same clock cycle.

For implementing chips with sub-7nm technology, it becomes much hard to access I/O pins on the highly dense standard cells to make physical routes for nets connecting cells. To improve the pin accessibility, in this work, we propose a cell layout optimization technique, which is able to trade fins with MOL (middle-of-line) in-cell routing resource, thus providing more M1 (metal-1) resource available to be used for I/O pin pattern extension, thereby improving the cell pin accessibility.

This paper addresses the combined problem of the three core tasks, namely routing on the middle-of-line (MOL) layer, generating I/O pin patterns (PP), and allocating contacts over active gates (COAG) in cell layout synthesis with 7nm and below technology. As yet, the existing cell layout generators have paid partial or little attention to those tasks, even with no awareness of the synergistic effects. This work overcomes this limitation by proposing a systematic and tightly-linked solution to the combined problem to boost the synergistic effects on chip implementation. Precisely, we solve the problem in three steps: (1) fully utilizing the horizontal routing resource on MOL layer by formulating the problem of in-cell routing into a weighted interval scheduling problem, (2) simultaneously performing the remaining horizontal in-cell routing and PP generation on metal 1 layer through the COAG exploitation while ensuring the pin accessibility constraint, and (3) completing in-cell routing by allocating vertical routing resource on MOL layer. Through experiments with benchmark designs, it is shown that our proposed layout method is able to generate standard cells with on average 34.2% shorter total length of metal 1 wire while retaining pin patterns that ensure pin accessibility, resulting in the chip implementations with up to 72.5% timing slack improvement and up to 15.6% power reduction that produced by using the conventional best available cells. In addition, by using less wire and vias, our in-cell router is able to consistently reduce the worst delay of cells, noticeably, reducing the sum of setup time and clock-to-Q delay of flip-flops by 1.2% ∼ 3.0% on average over that by the existing best cells.

Monolithic 3D (M3D) is a revolutionary technology for high-density and high-performance chip design in the post-Moore era. However, it suffers from considerable thermal confinement due to the transistor stacking and insulating materials between the layers. As a way of reducing power, thereby mitigating the thermal problem, we propose a comprehensive physical design methodology that incorporates two new important items, one is blockage aware MIV (monolithic inter-tier via) placement and the other is 3D net ordering for routing, intending to optimize wire length. Precisely, we propose a three-step approach: (1) retrieving the MIV region candidates for each 3D net, (2) fine-tuning placement to secure MIV spots in the presence of blockages, and (3) performing M3D routing with net ordering to consider the fine-tuned placement result. We implement the proposed M3D design flow by utilizing commercial 2D IC EDA tools while providing seamless optimization for cross-tier connections. In the meantime, our experiments confirm that proposed M3D design flow saves wire length per cross-tier net by up to 41.42%, which corresponds to 7.68% less total net switching power, equivalently 36.79% lower energy-delay-product over the conventional state-of-the-art M3D design flow.

In addition to the word-level weight pruning, which excludes the 0-value weights from the neural network inference computation, it is recently demonstrated that the bit-level weight pruning, which excludes the 0-bits in the weight value representation regardless of whether the weight values are zero or not, is very effective to further accelerate the neural network computation without accuracy loss. This work overcomes the inherent limitation of the bit-level weight pruning, that is, the maximal computation speedup is bounded by the total number of nonzero bits of the weights and the bound is invariably considered “uncontrollable” (i.e., constant) for the neural network to be pruned. Precisely, this work, based on the signed-digit encoding 1) proposes a transformation technique which converts the two’s complement representation of every weight into a set of signed-digit representations of the minimal number of essential (i.e., nonzero) bits; 2) formulates the problem of selecting signed-digit representations of weights that maximize the parallelism of bit-level multiplication on the weights into a objective shortest path problem to achieve a maximal digit-index by digit-index (i.e., columnwise) compression for the weights and solves it efficiently using an approximation algorithm; 3) proposes a supporting novel acceleration architecture (DWP) with no additional inclusion of nontrivial hardware; and 4) proposes a variant ofDWPto support bit-level parallel multiplication with the capability of predicting a tight worst-case latency of the parallel processing. Through experiments on several representative models using the ImageNet dataset, it is shown that our proposed approach is able to reduce the number of essential bits by 69% on AlexNet, 74% on VGG-16, and 68% on ResNet-152, by which our accelerator is able to reduce the inference computation time by up to$3.57\times $over the conventional bit-level weight pruning.

Near-threshold computing is essential for energy-efficient operation of VLSI systems, but wide performance variation and nonlinearity to process variations block the proliferation. To cope with this, in this article, we propose a holistic hardware performance monitoring methodology for accurate timing prediction in a near-threshold voltage regime. Precisely, 1) we formulate the problem of finding an efficient configuration of monitoring circuits into an instance of optimal experiment design problem and 2) propose a new timing prediction flow, consisting of statistical estimation of FEOL and BEOL process variations and a neural network-based timing inference model. For accurate control of timing margin and overcoming simulation-silicon discrepancies, 3) we introduce uncertainty learning in the prediction model construction and calibrate it through transfer learning. Furthermore, 4) we avoid time-consuming SPICE simulations in our methodology by employing efficient but accurate surrogate models. Through simulations using a 28-nm industry PDK and DK characterized at 0.6-V operation, it is shown that our methodology is highly effective, reducing the average prediction pessimism of maximum delay by 77.9% over conventional signoff results while respecting target prediction yield. Besides, for test chips fabricated using a 10-nm process, we demonstrated that our holistic approach from design to postsilicon phase in conjunction with adaptive voltage scaling reduces dynamic power consumption by 28.2%–28.8% on average, in comparison with typical supply voltage operation.

As the layout of standard cells is becoming dense, accessing pins is much harder in detailed routing. The conventional solutions to resolving the pin access issue are to attempt cell flipping, cell shifting, cell swapping, and/or cell dilating in the placement optimization stage, expecting to acquire high pin accessibility. However, those solutions do not guarantee close-to-100% pin accessibility to ensure safe manual fixing afterward in the routing stage. Furthermore, there is no easy and effective methodology to fix the inaccessibility in the detailed routing stage as yet. This work addresses the problem of fixing the inaccessibility in the detailed routing stage. Precisely, (1) we produce, for each type of cell, multiple layouts with diverse pin locations and access points by modifying the core engines i.e., gate poly ordering and middle-of-line dummy insertion in the flow of design-technology co-optimization based automatic cell layout generation. Then, (2) we propose a systematic method to make use of those layouts to fix the routing failures caused by pin inaccessibility in the ECO (Engineering Change Order) routing stage. Experimental results demonstrate that our proposed cell layout diversification and replacement approach can fix metal-2 shorts by 93.22% in the ECO routing stage.

We propose an acceleration technique for processing multiplication operations using stochastic computing (SC) in on-device neural networks. Recently, MUX-FSM based SCs, which employ a MUX controlled by an FSM to generate a bit stream for a multiplication operation, considerably reduces the processing time of MAC operations over the traditional stochastic number generator based SC. Nevertheless, the existing MUX-FSM based SCs still do not meet the multiplication processing time required for a wide adoption of on-device neural networks in practice even though it offers a very economical hardware implementation. In this respect, this work proposes a solution to the problem of speeding up the conventional MUX-FSM based SCs. Precisely, we analyze the bit counting pattern produced by MUX-FSM and replace the counting redundancy by shift operation, resulting in shortening the length of the required bit sequence significantly, together with analytically formulating the amount of computation cycles. Through experiments, it is shown that our enhanced SC technique is able to reduce the processing time by 44.1 % on average over the conventional MUX-FSM based SCs.

The three major tasks in standard cell layout synthesis are transistor folding, transistor placement, and in-cell routing, which are tightly inter-related, but generally performed one at a time to reduce the extremely high complexity of design space. In this paper, we propose an integrated approach to the two problems of transistor folding and placement. Precisely, we propose a globally optimal algorithm of search tree based design space exploration, devising a set of effective speeding up techniques as well as dynamic programming based fast cost computation. In addition, our algorithm incorporates the minimum OD (oxide diffusion) jog constraint, which closely relies on both of transistor folding and placement. To our knowledge, this is the first work that tries to simultaneously solve the two problems. Through experiments with the transistor netlists and design rules in the ASAP 7nm library, it is shown that our proposed method is able to synthesize fully routable cell layouts of minimal size within 1 second for each netlist, outperforming the cell layout quality in the ASAP 7nm library, which otherwise, may take several hours or days to manually complete layouts of the quality level comparable to ours.

The synthesis of standard cell layouts is largely divided into two tasks namely transistor placement and in-cell routing. Since the result of transistor placement highly affects the quality of in-cell routing, it is crucial to accurately and efficiently predict in-cell routability during transistor placement. In this work, we address the problem of an optimal transistor placement combined with global in-cell routing with the primary objective of minimizing cell size and the secondary objective of minimizing wirelength for global in-cell routing. To this end, unlike the conventional indirect and complex SMT (satisfiability modulo theory) formulation, we propose a method of direct and efficient formulation of the original problem based on SMT. Through experiments, it is confirmed that our proposed method is able to produce minimal-area cell layouts with minimal wirelength for global in-cell routing while spending much less running time over the conventional optimal layout generator.

The retention flip-flop is an essential component in power gated circuits for retaining state during the sleep mode. In this article, we solve two critical limitations of the conventional approaches to the allocation of state retention storage for power gated circuits. Those are: 1) the long wakeup delay caused by the senseless use of multibit retention flip-flops (MBRFFs) and 2) the inability to optimize retention flip-flops for the flip-flops with mux-feedback loop. It should be noted that the conventional approaches have regarded the long wakeup delay as an inevitable consequence of maximizing the reduction of total storage size for state retention while they have treated the flip-flops with mux-feedback loop (called self-loop flip-flop) as nonoptimizable component, but practically, the self-loop flip-flops synthesized from hardware description language (HDL) code are not far from a small amount and thus, can in no way be negligible. More precisely, for solving: 1), we show that the use of MBRFFs with up to 2 bits, consequently, constraining the wakeup delay to no more than two clock cycles, is enough to maintain the high reduction of total retention storage and for solving 2), we devise a 2-phase retention control mechanism for a pair of flip-flops, one of which has self-loop, by which just a single retention bit can be used to restore state of the two flip-flops. We propose an independent set-based algorithm for maximally extracting the nonconflict pairs from circuits. In addition, to further reduce the power consumption in the sleep mode, we propose a new design of 2-bit MBRFF.

In this work, we address the synthesis problem of two-phase bundled-data asynchronous pipeline controllers, in which the insertion of buffers is essential for guaranteeing the correct handshaking operation on every pipeline stage at the expense of considerable area increase. To lighten the pipeline controllers, we introduce a new logic synthesis concept called delay path sharing and reusing, by which we can significantly reduce the amount of the costly delay buffers. Precisely, first, we propose a technique of synthesizing an asynchronous pipeline controller in a way to share delay buffers among setup timing paths on pipeline stages for minimally allocating total delay buffers. In addition, we devise an area-efficient delay circuit structure called delay path unit (DPU) by extending the proposed delay path sharing concept and propose an in-depth synthesis flow of an asynchronous pipeline controller using DPUs. Through experiments with benchmark circuits using a 45-nm cell library, it is shown that our techniques of synthesizing asynchronous pipeline controllers are able to reduce the controller area by up to 46.3%-59.4% and the leakage power by up to 33.0%-49.0% on average while retaining the same level of performance.

It is generally known that a considerable portion of flip-flops in circuits is occupied by the ones with mux-feedback loop (called self-loop), which is the critical (inherently unavoidable) bottleneck in minimizing total (always-on) storage size for the allocation of nonuniform multibits for retaining flip-flop states in power gated circuits. This is because it is necessary to replace every self-loop flip-flop with a distinct retention flip-flop with at least one-bit storage for retaining its state since there is no clue where the flip-flop state, when waking up, comes from, i.e., from the mux-feedback loop or from the driving flip-flops other than itself. This work breaks this bottleneck by safely treating a large portion of the self-loop flip-flops as if they were the same as the flip-flops with no self-loop. Specifically, we design a novel mechanism of steady-state monitoring, operating for a few cycles just before sleeping, on a partial set of self-loop flip-flops, by which the expensive state retention storage is never be needed for the monitored flip-flops, contributing to a significant saving on the total size of the always-on state retention storage for power gating. Through experiments with benchmark circuits, it is shown that our proposed method is able to reduce the total number of retention bits by 27.12% on average when at most 2-bit retention flip-flop is used, saving standby power by 19.41% compared with the state-of-the-art conventional method.

An elaborate hardware performance monitor (HPM) has become increasingly important for handling huge performance variation of near-threshold computing and recent process technologies. In this paper, we propose a new approach to the problem of predicting critical path delays (CPDs) using HPM. Precisely, for a target circuit or system, we formulate the problem of finding an efficient combination of ring oscillators (ROs) for accurate prediction of CPDs on the circuit as a mixed integer second-order cone programming and propose a method of minimizing the total number of ROs for a given pessimism level of prediction. Then, we propose a prediction flow of CPDs through statistical estimation of process parameters from measurements of the customized HPM and machine learning based delay mapping from the estimation. For a set of benchmark circuits tested using 28nm PDK and 0.6V operation, it is shown that our approach is very effective, reducing the pessimism of CPDs and minimum supply voltages by 6.7~52.9% and 20.6~50.8% over those of conventional approaches, respectively.

A bundled-data asynchronous circuit is a promising alternative to a synchronous circuit for implementing high performance low power systems, but it requires to deploy special circuitry to support the asynchronous communication between every pair of consecutive pipeline stages. This work addresses the problem of reducing the size of asynchronous pipeline controller. Lightening the pipeline controller directly impacts two critical domains: (1) it mitigates the increase of controller area caused by high process-voltage-temperature variation on circuit; (2) it contributes to proportionally reducing the leakage power. (Note that a long delay in circuit between pipeline stages requires a long chain of delay elements in the controller.) Precisely, we analyze the setup timing paths on the conventional asynchronous pipeline controller, and (i) resynthesize new setup timing paths, which allows to share some of the expensive delay elements among the paths while assuring the communication correctness. Then, we (ii) optimally solve the problem of minimizing the number of delay elements by formulating it into a linear programming. For a set of test circuits with a 45nm standard cell library, it is shown that our synthesis and optimization method reduces the total area of delay elements and the leakage power of pipeline controller by 46.4% and 43.6% on average, respectively, while maintaining the same level of performance and dynamic power consumption.

It is generally known that a considerable portion of flip-flops in circuits is occupied by the ones with mux-feedback loop (called self-loop), which are the critical (inherently unavoidable) bottleneck in minimizing total (always-on) storage size for the allocation of non-uniform multi-bits for retaining flip-flop states in power gated circuits. This is because it is necessary to replace every self-loop flip-flop with a distinct retention flip-flop with at least one-bit storage for retaining its state since there is no clue as to where the flip-flop state, when waking up, comes from, i.e., from the mux-feedback loop or from the driving flip-flops other than itself. This work breaks this bottleneck by safely treating a large portion of the self-loop flip-flops as if they were the same as the flip-flops with no self-loop. Specifically, we design a novel mechanism of steady state monitoring, operating for a few cycles just before sleeping, on a partial set of self-loop flip-flops, by which the expensive state retention storage never be needed for the monitored flip-flops, contributing to a significant saving on the total size of the always- on state retention storage for power gating.

This paper proposes a complete and full automation framework of evaluating design rules (DRs) to facilitate the process of design technology co-optimization (DTCO), which is highly demanded in 14-nm and beyond technologies. Our proposed framework explores the changes of DRs and evaluates the impacts on the number and types of DR violations as well as the resulting cell/chip layout area. Precisely, the core engine of our DR evaluation framework for DTCO, the automatic cell layout generator, consists of key enabling techniques for standard cell layout optimization. They are integrated coherently to seamlessly support the advanced process technologies using FinFET transistors, complex DRs, and double patterning (DP) lithography. Also, the tight integration of our automatic cell layout generation into the DR evaluation framework with diverse analysis features enables the DTCO process to be much faster and more efficient. We provide a set of experimental data not only to show how much our proposed enabling techniques are effective in optimizing layouts but also to show how effectively our framework explores and analyzes the DTCO parameters (e.g., ground DRs and DP DRs).

This work addresses the problem of automatically synthesizing compact standard cell layouts with 2D metal-1 routing under design rule constraints. Precisely, we propose a set of new highly impacting techniques dedicated solely to the generation of cell layouts with 2D metal-1 routing completion. Those are (1) netlist decomposition (2) transistor chaining combined with transistor folding, (3) gate poly ordering combined with fast routing congestion estimation, and (4) 2D single-layer routing with minimal resource. It is shown from experiments that our proposed layout generator is able to produce layouts of quality comparable to the expert's manual ones, but spending just one hour for 56 representative cells generation.

This work addresses a new structure optimization of neuromorphic computing architectures. This enables to speed up the DNN (deep neural network) computation twice as fast as, theoretically, that of the existing architectures. Precisely, we propose a new structural technique of mixing both of the dendritic and axonal based neuromorphic cores in a way to totally eliminate the inherent non-zero waiting time between cores in the DNN implementation. In addition, in conjunction with the new architecture we propose a technique of maximally utilizing computation units so that the resource overhead of total computation units can be minimized. We have provided a set of experimental data to demonstrate the effectiveness (i.e., speed and area) of our proposed architectural optimizations: ~2× speedup with no accuracy penalty on the neuromorphic computation or improved accuracy with no additional computation time.

This work firstly investigates the problem of how designing data-driven (i.e., toggling based) clock gating can be closely integrated with the synthesis of flip-flops, which has never been addressed in the prior clock gating works. Our key observation is that some internal part of a flip-flop cell can be reused to generate its clock gating enable signal. Based on this, we propose a newly optimized flip-flop wiring structure, called eXOR-FF, in which an internal logic can be reused for every clock cycle to decide if the flip-flop is to be activated or inactivated through clock gating, thereby achieving area saving (thus, leakage as well as dynamic power saving) on every pair of flip-flop and its toggling detection logic. Then, we propose a comprehensive methodology of placement/timing-aware clock gating exploration that provides two unique strengths: best suited for maximally exploiting the benefit of eXOR-FFs and precise analyses on the decomposition of power consumptions and timing impact, and translating them into cost functions in core engine of clock gating exploration.

This paper proposes a graph-based algorithm for solving the adjustable delay buffer (ADB) allocation problem optimally under useful clock skew scheduling. Our algorithm supports additional features: extending the optimality to the allocation of ADBs with quantized delay values, extending the optimality to the allocation of ADBs with delay upper bound, and extending to the consideration of the delay variability of clock buffers. In addition, we propose two acceleration techniques for speeding up the computation. The first one is speeding up the graph traversal of our optimal solver without sacrificing the optimality while the second one, supplementing our algorithm, is to deal with the extremely large designs at the expense of the allocation quality. The experiments with benchmark circuits show that our algorithm reduces the number of ADBs by 23.3% on average over the results produced by the conventional ADB allocation under useful clock skew scheduling and reduces the number of ADBs by 86.3% on average over that produced by the previous optimal ADB allocation under bounded clock skew constraint. In addition, our optimal algorithm runs 30-460 times faster than the prior work.

Clock trees, which deliver the clock signal to every clock sink in the whole system, are one of the most active components on a chip which makes them one of the most dominant sources of noise. While many clock polarity assignment (PA) techniques were proposed to mitigate the clock noise, no attention has been paid to the PA under useful skew constraints. In this work, we show that the clock PA problem under useful skew constraints is intractable and propose a comprehensive and scalable clique search based algorithm to solve the problem effectively. In addition, we demonstrate the applicability of our solution by effectively extending it for PA under delay variation environment. Through experiments with ISPD'10 benchmark circuits, it is shown that our proposed clock PA algorithm is able to reduce the peak noise by 10.9% further over that of the conventional global skew bound constrained PA.

In this paper, a new approach to the problem of allocating multi-bit flip-flops for data storage is presented. Previous approaches divide the allocation problem into two separate steps: (i) placing single-bit flip-flops under circuit timing constraints and (ii) minimizing the flip-flop and clock tree power by grouping single-bit flip-flops to form multi-bit flip-flops. Yet, there is no easy way to predict the result of step (ii) during step (i). In our approach, we place primary importance on the cost of power consumption. Consequently, we try to minimize power consumption by synthesizing multi-bit flip-flops first and then to place them later. For a number of benchmark circuits, it is shown that our approach of early consideration of synthesizing multi-bit flip-flops is very effective, reducing the clock power by 13.5% while satisfying all the timing constraints.

The portion of clock power in system is rapidly increasing with the continuous increasing of clock frequency and clock resources. Last two decades, a great research attention has been paid to minimizing the clock power. Recently, it is shown that the structure of resonant clock networks is very effective in saving power since it can store electric energy to the inserted inductors rather than dissipate. On the other side, it has been known that dynamic voltage-frequency scaling (DVFS) is one of the most effectively and widely used power reduction techniques. However, so far no works have addressed the design methodology problem of synthesizing resonant clock networks that are able to operate under the designs with DVFS capability even though the problem is potentially very important to maximize the synergy effect on saving power. In this context, this paper proposes a comprehensive solution to the problem. Precisely, we propose a two-phase synthesis algorithm: 1) formulating the problem of inductor allocation, placement, and adjustable-sizing to support DVFS into a weighted set cover problem with the objective of minimizing total area of inductors and 2) followed by performing the task of resizing of adjustable driving buffers to support the switch of driving strength according to the clock frequencies by DVFS. Through experiments with benchmark circuits, it is shown that for designs with DVFS using 1 and 3 GHz, our algorithm synthesizes resonant clock networks with 25.9% less power on the execution of the clock frequency, which is not supported by resonant clocking in the previous no-DVFS aware resonant clock synthesis algorithm.

The portion of clock power in system is rapidly increasing with the continuous increasing of clock frequency and clock resources. Last two decades, a great research attention has been paid to minimizing the clock power. Recently, it is shown that the structure of resonant clock networks is very effective in saving power since it can store electric energy to the inserted inductors rather than dissipate. On the other side, it has been known that dynamic voltage-frequency scaling (DVFS) is one of the most effectively and widely used power reduction techniques. However, so far no works have addressed the problem of synthesizing resonant clock networks that are able to operate under the designs with DVFS capability even though the problem is potentially very important to maximize the synergy effect on saving power. In this context, this work proposes a comprehensive solution to the problem. Precisely, we propose a two-phase synthesis algorithm: (1) formulating the problem of inductor allocation, placement, and adjustable-sizing to support DVFS into a weighted set cover problem with the objective of minimizing total area of inductors followed by (2) performing the task of resizing of adjustable driving buffers to support the switch of driving strength according to the clock frequencies by DVFS. Through experiments with benchmark circuits, it is shown that for designs with DVFS using 1GHz and 3GHz, our algorithm synthesizes resonant clock networks with 17% less power on the execution of the clock frequency, which is not supported by resonant clocking in the previous no-DVFS aware resonant clock synthesis algorithm.

Clock tree and clock mesh are two extreme structures of clock networks. Clock tree is good at saving clock wires and power, but is vulnerable to clock skew variation. On the other hand, clock mesh is good at mitigating clock skew variation, but spends considerable wires and power. Well known intermediate structures are clock tree with cross links and clock spine. This work addresses the problem automating the synthesis of clock spine networks. Unlike the clock tree with links between clock nodes, which is a sort of an incremental modification of the structure of clock tree, clock spine network is a completely separated structure from the structures of tree and mesh. Consequently, it is necessary and essential to develop a synthesis algorithm for clock spines, which will be compatible to the existing synthesis algorithms of clock trees and clock meshes. To this end, this work first addresses the problem of automating the synthesis of clock-gated clock spines with the objective of minimizing total clock power while meeting the clock skew and slew constraints. The key idea of our proposed synthesis algorithm is to identify and group the flip-flops with tight correlation of clock-gating operations together to form a spine while accurately predicting and maintaining clock skew and slew variations through the buffer insertion and stub allocation. Through experiments with benchmark circuits, it is shown our power-aware synthesis for clock spines uses significantly less power consumption compared to that of the conventional clock mesh synthesis algorithm at the expense of a little relaxed or the same constraint of clock skew.

In through-silicon-via (TSV) based 3-D integrated chips (ICs), synthesizing 3-D clock tree is one of the most challenging tasks. Since the clock signal is delivered to clock sinks (e.g., latches, flip-flops) through TSVs, any fault on a TSV in the clock tree may cause a chip failure. Therefore, ensuring the reliability of clock TSVs in 3-D ICs is highly important. To cope with clock TSV reliability problem effectively, we propose a new circuit cell called slew-controlled TSV fault-tolerant unit (SC-TFU) which overcomes the limited capability of the conventional TFUs and propose a full solution to the problem of designing and synthesizing 3-D TSV fault-tolerant clock tree based on SC-TFUs. Precisely, for a presynthesized 3-D clock tree, we solve the problem in three steps: 1) performing a comprehensive TSV pairing algorithm to maximally allocate SC-TFUs; 2) replacing TSV pairs obtained in step 1 with SC-TFUs followed by TSV tripling to maximize TSV fault-tolerance under wire and time constraints; and 3) performing a global clock skew tuning process on the SC-TFU embedded 3-D clock tree produced in step 2. Through out experiments, two outstanding benefits are confirmed: 1) our synthesis using SC-TFUs enables a large number of clock TSVs to be paired or tripled to ensure a very high degree of TSV fault-tolerance and 2) our synthesis flow effectively performs tuning of global clock skew whose variation is caused by the inclusion of TSV fault-tolerant cells into 3-D clock trees.

Recently, many works have shown that adjustable delay buffer (ADB) whose delay is adjustable dynamically can effectively solve the clock skew variation problem in the designs with multiple power modes. However, all the previous works of ADB allocation inherently entail two critical limitations, which are the adjusted delays by ADB are always increments and the low cost buffer sizing has never been or not been primarily taken into account. To demonstrate how much overcoming the two limitations is effective in resolving the clock skew constraint, we characterize the two types of ADBs called CADB (capacitor based ADB) and IADB (inverter based ADB) and show that the adjusted delays by IADB can be decremented, and show that the clock skew violation in some clock trees of multiple power modes can be resolved by applying buffer sizing together with using only a small number of IADBs and CADBs.

The clock buffer polarity assignment is one of the effective design schemes to mitigate the power/ground noise caused by the clock signal propagation in high-speed digital systems. This paper overcomes a set of fundamental limitations of the conventional clock buffer polarity assignment methods, which are: 1) the unawareness of the signal delay (i.e., arrival time) differences to the leaf clock buffering elements; 2) the ignorance of the effect of the current fluctuation of nonleaf clock buffering elements on the total peak current waveform; and 3) the inability of supporting low-power digital designs with multiple (dynamically operating) power modes. Clearly, not addressing 1 and 2 in the polarity assignment may cause a severe inaccuracy on the peak current estimation, which results in unnecessarily high peak current. Moreover, without tackling 3, designs may suffer from clock skew violation in some of the power modes, affecting circuit speed or reliability. To overcome the limitations, we propose a completely new fine-grained approach to the clock buffer polarity assignment combined with buffer sizing, formulating the problem into a multiobjective shortest path problem and solving it effectively for designs with a single power mode, while exploiting the flexibility of our multiobjective shortest path formulation for designs with multiple power modes. Through experiments using benchmark circuits, it is shown that the proposed approach is able to produce designs with 17% lower peak current and 20% lower power noise on average, compared with the results produced by the best ever known method.

The clock distribution network in a synchronous digital circuit delivers a clock signal to every storage element, that is, clock sink in the circuit. However, since the continued technology scaling increases PVT (process-voltage-temperature) variation, the increase of clock-skew variation is highly likely to cause performance degradation or system failure at runtime. Recently, to mitigate the clock-skew variation, many researchers have taken a profound interest in the clock mesh network. However, though the structure of the clock mesh network is excellent in tolerating timing variations, it demands significantly high power consumption due to the use of excessive mesh wire and buffer resources. Thus, optimizing the resources required in the mesh clock synthesis while maintaining the variation tolerance is crucially important. The three major tasks that greatly affect the cost of the resulting clock mesh are: (1) mesh segment allocation , (2) mesh buffer allocation and sizing , and (3) clock sink binding to mesh segments . Previous clock mesh optimization approaches solve the three tasks sequentially, one by one at a time, to manage the runtime complexity of the tasks at the expense of losing the quality of results. However, since the three tasks are tightly interrelated, simultaneously optimizing all three tasks is essential, if the runtime is ever permitted, to synthesize an economical clock mesh network. In this work, we propose an approach that is able to tackle the problem in an integrated fashion by combining the three tasks into an iterative framework of incremental updates and solving them simultaneously to find a globally optimal allocation of mesh resources while taking into account the clock-skew tolerance constraints. The core parts of this work are a precise analysis on the relation among the resource optimization tasks and an establishment of a mechanism for effective and efficient integration of the tasks. In particular, to handle the runtime problem, we propose a set of speedup techniques, that is, modeling the RC circuit for eliminating redundant matrix multiplications, exploiting a sliding-window scheme, and quickly estimating the buffer sizing effect, which are fitted into our context of fast clock-skew estimation in mesh resource optimization as well as an invention of early decision policies. Through extensive experiments with benchmark circuits, it is shown that our proposed clock mesh synthesizer is able to reduce the worst-case clock skew, total mesh wirelength, total size of mesh driving buffers, and total clock mesh power consumption including short-circuit power by 25.0%, 13.2%, 10.9%, and 11.0% on average compared to that produced by the best-known clock mesh synthesis method (MeshWorks), respectively.

Meeting clock skew constraint is one of the most important tasks in the synthesis of clock trees. Moreover, the problem becomes much hard to tackle as the delay of clock signals varies dynamically during execution. Recently, it is shown that adjustable delay buffer (ADB) whose delay can be adjusted dynamically can solve the clock skew variation problem effectively. However, inserting ADBs requires non-negligible area and control overhead. Thus, all previous works have invariably aimed at minimizing the number of ADBs to be inserted, particularly under the environment of multiple power modes in which the operating voltage applied to some modules varies as the power mode changes. In this work, unlike the previous works which have solved the ADB minimization problem heuristically or locally optimally, we propose an elegant and easily adoptable solution to overcome the limitation of the previous works. Precisely, we propose an O(n log n) time (bottom-up traversal) algorithm that (1) optimally solves the problem of minimizing the number of ADBs to be inserted with continuous delay of ADBs and (2) enables solving the ADB insertion problem with discrete delay of ADBs to be greatly simple and predictable. In addition, we propose (3) a systematic solution to an important extension to the problem of buffer sizing combined with the ADB insertion to further reduce the ADBs to be used.

Recently, to cope with clock TSV (Through-Silicon-Via) reliability problem efficiently, a new circuit structure called TSV Fault-tolerant Unit (TFU) and the allocation method of TFUs have been proposed. However, the existing design methods partially or never addressed following key issues: (1) the feasibility of TSV pairing for TFU allocation, (2) maximizing TSV pairing, (3) supporting the slew and delay control capability in TFU for the cases of pre-bond testing as well as post-bond stage, and (4) minimizing the impact of TFU insertion on the clock skew of the whole 3D clock tree. In this work, we propose a full solution to the problem of designing and synthesizing TSV fault-tolerant clock tree from a 3D clock tree, which effectively addresses above key issues.

In 3-D stacked integrated circuit (IC) manufacturing, for the acceptable high yield, it is essential to stack only known good dies by testing the individual dies at the prebond stage. While the postbonded 3-D IC is operated by a low power 3-D clock tree, the prebond testing requires a 2-D clock tree on each die. The previous work provided a prebond testable 3-D clock tree synthesis solution by allocating through-silicon via (TSV) buffers and redundant trees with transmission gates. However, no optimizations on the allocation and design of the resources have been addressed. In this paper, we propose practically viable clock tree optimization techniques under prebond testability: 1) TSV-buffer-aware topology generation techniques that enable an economical buffer allocation by preventing (potentially “bad”) TSV buffers; 2) delay-locked loop (DLL)-based 2-D clock network design method that offers a diverse exploration of 2-D clock tree synthesis and resource allocation for prebond die testing; and 3) a new circuit design technique of transmission gates that completely removes its control line. Compared to the existing topology generation algorithms, our proposed TSV-buffer-aware topology generation uses 68%-88% fewer TSVs, 36%-58% less wire resource, and 35%-69% fewer buffers while consuming 17%-43% less clock power for the benchmark circuits, and our proposed method of clock tree exploration provides many alternative structures of a 2-D clock tree, considering the resource balance between DLLs and wires. In addition, the use of our self-controlled clock transmission gate enables a drastic reduction of the total wirelength, which amounts to 18% on average.

Satisfying a clock skew constraint is one of the most important tasks in clock tree synthesis. Moreover, the task becomes much harder to solve when the clock tree is designed in a multiple power mode environment, in which the voltage applied to some design module varies as the power mode changes. Recently, it has been shown that an adjustable delay buffer (ADB), whose delay can be tuned dynamically, can be used to solve the clock skew problem effectively under multiple power modes. However, due to the area or control overhead by ADBs, it is very important to minimize the number of ADBs to be allocated. This paper provides a complete solution to the problem of clock skew optimization using ADBs under multiple power modes. We propose a linear-time algorithm that simultaneously solves the problems of computing: 1) the minimum (optimal) number of ADBs to be used; 2) the location where each ADB is to be placed; and 3) the delay value of each ADB to be assigned to each power mode. Experimental results show that, in comparison with the previous work, which iteratively performs the ADB allocation, placement, and value assignment, our integrated algorithm produces consistently better designs for all tested benchmarks; it reduces the numbers of ADBs by 9.27% on average under the skew bound of 30-50 ps, even with shorter clock latencies compared to that of previous algorithm of ADB allocation, placement, and delay assignment. To make it practically feasible, we also propose a new ADB design technique and systematic algorithmic solutions to address the problems of discrete delay values, slew rate variation, nonzero initial ADB delay, and a possible exploration of ADB resizing.

Satisfying the timing constraint is the utmost concern in the integrated circuit design and it is true that most critical timing paths in a circuit cover one or more arithmetic components such as adder, subtractor, and multiplier of which addition logic is commonly involved. This work addresses the problem of redesigning the addition logic (in a form of hybrid adder) on a critical timing path to meet the timing constraint while minimally allocating the required addition logic. Unlike the conventional hybrid adder design schemes in which they assume uniform or specific patterns of input signal arrival times and minimize the latest timing of the output signals, our work extracts the required timing of each output signal as well as the input arrival times directly from the circuit and resynthesizes the addition logic by creating a customized hybrid adder that is best suited, in terms of logic area, for meeting the timing constraint of the circuit. Specifically, we propose a systematic approach of hybrid adder design exploration, basically following the principle of dynamic programming with well-controlled pruning techniques. This work is realistic and practically very useful in that it can be used as a timing optimizer to the computation-intensive circuits with a tight timing budget. We provide a set of diverse experimental data to show how much the proposed hybrid adder scheme is effective in meeting or reducing timing while maintaining the circuit area as minimal as possible.

The clock buffer polarity assignment is one of the effective design schemes to mitigate the power/ground noise caused by the clock signal propagation. This work overcomes two fundamental limitations of the conventional clock buffer polarity assignment methods, which are (1) the unawareness of the signal delay (i.e., arrival time) differences to the leaf buffering elements and (2) the ignorance of the effect of the current fluctuation of non-leaf buffering elements on the total peak current waveform. Clearly, not addressing (1) and (2) in polarity assignment may cause a severe inaccuracy on the peak current estimation, which results in unnecessarily high peak current. To overcome the limitations, we propose a completely new fine-grained approach to the clock buffer polarity assignment combined with buffer sizing, formulating the problem into a multi-objective shortest path problem and solving it effectively. The experimental results show that the proposed method is able to produce designs with 17% lower peak current and 20% lower power noise on average compared the results produced by the best ever known method.

In synchronous systems, clock tree causes high peak current at clock edges, increasing power/ground noise significantly, if the clock tree is not carefully designed. This paper addresses the problem of minimizing power/ground noise in the clock tree synthesis. Contrary to the previous approaches which only make use of assigning polarities to clock buffers to reduce power/ground noise, our approach solves a new problem of simultaneous consideration of assigning polarities to clock buffers and determining buffer sizes to fully exploit the effects of buffer sizing together with polarity assignment on the minimization of power/ground noise while satisfying the clock skew constraint. Specifically, the contributions of this paper are: 1) precisely estimating peak currents by clock buffers and reflecting them on the power/ground noise minimization; 2) proposing a pseudo-polynomial time optimal algorithm based on dynamic programming for solving the integrated problem, together with the proof of intractability of the problem; 3) devising a systematic design flow framework for reducing the power/ground noise over the entire chip; and 4) considering the effect of thermal variation on the clock skew bound and the noise minimization.

For the cost-effective implementation of clock trees in through-silicon via (TSV)-based 3D IC designs, we propose core algorithms for 3D clock tree synthesis. For a given abstract tree topology, we propose DLE-3D ( d eferred l ayer e mbedding for 3D ICs), which optimally finds the embedding layers of tree nodes, so that the TSV cost required for a tree topology is minimized, and DME-3D ( d eferred m erge e mbedding for 3D ICs), which is an extended algorithm of the 2D merging segment, to minimize the total wirelength in 3D design space, with the consideration of the TSV effect on delay. In addition, when an abstract tree topology is not given, we propose NN-3D ( n earest n eighbor selection for 3D ICs), which constructs a (TSV and wirelength) cost-effective abstract tree topology for 3D ICs. Through experimentation, we have confirmed that the clock tree synthesis flow using the proposed algorithms is very effective, outperforming the existing 3D clock tree synthesis in terms of the number of TSVs, total wirelength, and clock power consumption.

This paper addresses a fundamental problem of zero skew clock tree embedding problem in 3D ICs. We propose an algorithm, called ZCTE-3D, for solving the zero skew clock tree embedding problem in 3D ICs for a given tree topology. The primary objective is to minimize the cost of TSVs together with finding embedding layers and the secondary objective is to minimize the cost of wirelength. We show that ZCTE-3D solves the problem optimally in polynomial time under the linear delay model, while it solves the problem suboptimally under the Elmore delay model. We also propose an effective 3D clock tree synthesis flow by integrating a multi-layer tree topology generation algorithm, called MMM-3D, into ZCTE-3D. Through an extensive exploitation of ZCTE-3D in experiments, we have analyzed the relation between the number of TSVs, the total wirelength, and tree topology. When compared with the results produced by the previous 3D clock tree synthesis algorithm BURITO, experimental results show that ZCTE-3D uses on average 10% less number of TSVs with similar wirelength and delay for the same tree topologies. Furthermore, by generating tree topologies with MMM-3D, we are able to reduce the number of TSVs by 10% on average even with 4% shorter wirelength and 2% reduced delay.

This paper proposes comprehensive solutions to the clock tree synthesis problem that provides pre-bond testability for 3D IC designs. In 3D ICs, it is essential to stack only good dies by testing the individual dies before stacking. For the clock signaling, the pre-bond testing requires a complete 2D clock tree on each die. The previous work enables the prebond testability by allocating specially designed resources called TSV-buffers and redundant trees with transmission gates. We proposes viable solutions to the two fundamental problems of the previous work: (1) using much less buffer resources by preventing (potentially 'bad') TSV-buffers with a new tree topology generation algorithm; (2) completely removing the transmission gate control lines by using a specially designed component called self controlled clock transmission gate (SCCTG). Compared to the existing 3D tree topology generation algorithms, solution 1 can use 56%--88% less number of TSVs, 53%--67% less number of buffers, 22%--65% less total wirelength, and 26%--43% less clock power for the benchmark circuits with dense sink placements. Moreover, solution 2 reduces the total wirelength of all the benchmark circuits by 17% and 23% on average for the 2-die and 4-die stacked 3D ICs, respectively.

This work addresses the problem of minimizing power/ground noise in the clock tree synthesis. Contrary to the previous approaches which only make use of assigning polarities to clock buffers to reduce power/ground noise, our approach solves a new problem of simultaneous consideration of assigning polarities to clock buffers and determining buffer sizes to fully exploit the effects of buffer sizing together with polarity assignment on the minimization of power/ground noise while satisfying the clock skew constraint. Through experiments with MCNC benchmark circuits, it is shown that the proposed solution produces designs with 19.1% less power and 16.2% less ground noise as well as 15.6% less total peak current over that by the conventional method.

A dynamic monitoring of thermal behavior of hardware resources using thermal sensors is very important to maintain the operation of systems safe and reliable. This article addresses the problem of thermal sensor allocation and placement for reconfigurable systems. For programmable logic arrays, the degree of the use of hardware resources in the systems highly depends on the target application to be implemented, making the allocation of thermal sensors at the manufacturing stage inadequate (or too costly if implemented) due to the unpredictable thermal profile. This means that the thermal sensor allocation could be processed at the time when the reconfigurable logic is implemented (i.e., at the post manufacturing stage). This work proposes an effective solution to the problem of thermal sensor allocation and placement at the post-manufacturing stage. Specifically, we define the Sensor Allocation and Placement Problem (SAPP), and propose a solution which formulates SAPP into the Unate-Covering Problem (UCP) and solves it optimally. Also we combine SAPP with temperature correlation to reduce required sensors more aggressively and propose a solution by applying UCP again. We then provide an extended solution to handle a practical design issue where the hardware resources for the sensor implementation on specific array locations have already been used up by the application logic. Experimental results using MCNC benchmarks show that our proposed technique uses 62.4% and 19.7% less number of sensors to monitor hotspots on the average than that used by the grid-based and the bisection-based approaches while the overhead of auxiliary circuitry is minimized, respectively.

In many embedded systems, particularly those with high data computations, the delay of memory access is one of the major bottlenecks in the system's performance. It has been known that there are high variations in memory-access delays depending on the ways of designing memory configurations and assigning arrays to memories. Furthermore, embedded-DRAM technology that provides efficient access modes is actively being developed, possibly becoming a mainstream in future embedded-system design. In that context, in this paper, the authors propose an effective solution to the problem of (embedded DRAM) memory allocation and mapping in memory-access-code generation with the objective of minimizing the total memory-access time. Specifically, the proposed approach, called memory-access-code optimization (MACCESS-opt), solves the three problems simultaneously: 1) determination of memories; 2) mapping of arrays to memories; and 3) scheduling of memory-access operations, so that the use of DRAM-access modes is maximized while satisfying the storage size constraint of embedded systems. Experimental data on a set of benchmark designs are provided to show the effectiveness of the proposed integrated approach. In short, MACCESS-opt reduces the total memory-access latency by over 18%, from which the authors found that the memory mapping and scheduling techniques in MACCESS-opt contribute about 12% and 6% reductions of the total memory-access latency, respectively

The topic on platform-based system modeling has received a great deal of attention today. One of the important tasks that significantly affect the effectiveness and efficiency of the system modeling is the modeling of IP components and communication between IPs. To be effective, it is generally accepted that the system modeling should be performed in two steps; In the first step, a fast but some inaccurate system modeling is considered to facilitate the simultaneous development of software and hardware. The second step then refines the models of the software and hardware blocks (i.e., IPs) to increase the simulation accuracy for the system performance analysis. Here, one critical factor required for a successful system modeling is a systematic modeling of the IP blocks and bus subsystem connecting the IPs. In this respect, this work addresses the problem of systematic modeling of the IPs and bus subsystem in different levels of refinements. In the experiments, we found that by applying our proposed IP and bus modeling methods to the MPEG-4 application, we are able to achieve 4/spl times/ performance improvement and at the same time, reduce the software development time by 35%, compared to that by conventional modeling methods.

An embedded system is called a multi-mode embedded system if it performs multiple applications by dynamically reconfiguring the system functionality. Further, the embedded system is called a multi-mode multi-task embedded system if it additionally supports multiple tasks to be executed in a mode. In this paper, we address an important HW/SW partitioning problem, that is, HW/SW partitioning of multi-mode multi-task embedded applications with timing constraints of tasks. The objective of the optimization problem is to find a minimal total system cost of allocation/mapping of processing resources to functional modules in tasks together with a schedule that satisfies the timing constraints. The key success of solving the problem is closely related to the degree of the amount of utilization of the potential parallelism among the executions of modules. However, due to an inherently excessively large search space of the parallelism, and to make the task of schedulabilty analysis easy, the prior HW/SW partitioning methods have not been able to fully exploit the potential parallel execution of modules. To overcome the limitation, we propose a set of comprehensive HW/SW partitioning techniques which solve the three subproblems of the partitioning problem simultaneously: (1) allocation of processing resources,(2) mapping the processing resources to the modules in tasks, and (3) determining an execution schedule of modules. Specifically, based on a precise measurement on the parallel execution and schedulability of modules, we develop a stepwise refinement partitioning technique for single-mode multi-task applications, which aims to solve the subproblems 1, 2 and 3 effectively in an integrated fashion. The proposed techniques is then extended to solve the HW/SW partitioning problem of multi-mode multi-task applications (i.e., to find a globally optimized allocation/mapping of processing resources with feasible execution schedule of modules).

It is generally accepted that dynamic voltage scaling (DVS) is one of the most effective techniques of energy minimization for real-time applications. The effectiveness comes from the fact that the amount of energy consumption is quadractically proportional to the voltage applied to the processor. The penalty is the execution delay, which is linearly and inversely proportional to the voltage. According to the granularity of units to which voltage scaling is applied, the DVS problem is divided into two subproblems: inter-task DVS problem, in which the determination of the voltage is carried out on a task-by-task basis and the voltage assigned to the task is unchanged during the whole execution of the task, and intra-task DVS problem, in which the operating voltage of a task is dynamically adjusted according to the execution behavior to reflect the changes of the required number of cycles to finish the task before the deadline. Frequent voltage transitions may cause an adverse effect on energy minimizatuion due to the increase of the overhead of transition time and energy. In this paper, we survey and describe, in a theoretical aspect, state-ofart techniques of dynamic voltage scaling problems, which include: (1) inter-task DVS problem, (2) intra-task DVS problem, (3) integrated inter-task and intra-task DVS problem, and (4) transition-aware DVS problem.

In many of embedded systems, particularly for those with high data computations, the delay of memory access is one of the major bottlenecks in the system's performance. It has been known that there are high variations in memory access delays depending on the ways of designing memory configurations and assigning arrays to memories. Furthermore, embedded DRAM technology that provides efficient access modes is actively developed, possibly becoming a mainstream in future embedded system design. In that context, in this paper we propose an effective solution to the problem of (embedded DRAM) memory allocation and mapping in memory access code generation with the objective of minimizing the total memory access time. Specifically, the proposed approach, called MACCESS-opt, solves the three problems simultaneously: (i) determination of memories, (ii) mapping of arrays to memories, and (iii) scheduling of memory access operations, so that the use of DRAM access modes is maximized while satisfying the storage size constraint of embedded system. Experimental data on a set of benchmark designs are provided to show the effectiveness of the proposed integrated approach. In short, MACCESS-opt reduces the total memory access latency by over 18%, from which we found that our memory mapping and scheduling techniques in MACCESS-opt contribute about 12% and 6% reductions of total memory access latency, respectively.

The delay of memory access is one of the major bottlenecks in embedded systems' performance. In software compilation, it is known that there are high variations in memory access delay depending on the ways of storing/retrieving the variables in code to/from the memories. In this paper, we propose effective storage assignment techniques for variables to maximize the use of memory bandwidth. Specifically, we study the problem of DRAM memory layout for storing the nonarray variables in code to achieve a maximum utilization of page and/or burst modes for the memory accesses. The contributions of our work are, for each page and burst modes: 1) we prove that the problem is NP-hard and 2) we propose an exact formulation of the problem and efficient memory layout algorithms, called Solve-MLP for the page mode and Solve-MLB for the burst mode. From experiments with a set of benchmark programs, we confirm that our proposed techniques use on average 28.2% and 10.1% more page accesses and 82.9% and 107% more burst accesses than those by the order of first use and the technique of Panda et al. in Proc. Int. Conf. Computer-Aided Design, 1997, and Panda et al. in ACM Trans. Design Automation Electron. Syst., 1997, respectively.

Memory-related activity is one of the major sources of energy consumption in embedded systems. Many types of memories used in embedded systems allow multiple operating modes (e.g., active, standby, nap, power-down) to facilitate energy saving. Furthermore, it has been known that the potential energy saving increases when the embedded systems use multiple memory banks in which their operating modes are controlled independently. In this paper, we propose (a compiler-directed) integrated approach to the problem of maximally utilizing the operating modes of multiple memory banks by solving the three important tasks simultaneously: (1) assignment of variables to memory banks, (2) scheduling of memory access operations, and (3) determination of operating modes of banks. Specifically, for an instance of tasks 1 and 2, we formulate task 3 as a shortest path(SP) problem in a network and solved it optimally. We then develop an SP-based heuristic that solves tasks 2 and 3 efficiently in an integrated fashion. We then extend the proposed approach to address the limited register constraint in processor. From experiments with a set of benchmark programs, we confirm that the proposed approach is able to reduce the energy consumption by 15.76 over that by the conventional greedy approach.

This paper presents a set of comprehensive techniques for the intratask voltage scheduling problem to reduce energy consumption in hard real-time tasks of embedded systems. Based on the execution profile of the task, a voltage scheduling technique that optimally determines the operating voltages to individual basic blocks in the task is proposed. The obtained voltage schedule guarantees minimum average energy consumption. The proposed technique is then extended to solve practical issues regarding transition overheads, which are totally or partially ignored in the existing approaches. Finally, a technique involving a novel extension of our optimal scheduler is proposed to solve the scheduling problem in a discretely variable voltage environment. In summary, it is confirmed from experiments that the proposed optimal scheduling technique reduces energy consumption by 20.2 % over that of one of the state-of-the-art schedulers [11] and, further, the extended technique in a discrete voltage environment reduces energy consumption by 45.3 % on average.

This paper presents a new approach to the synthesis of parallel multiplier circuits with an objective of minimizing leakage power consumption under circuit timing constraint. Our leakage power optimization is based on the use of dual-threshold voltage (Vt) technology. From experiments using a set of benchmark designs, it is shown that the approach is quite effective.

We present a new performance and routability driven routing algorithm for symmetrical array-based field-programmable gate arrays (FPGAs). A key contribution of our work is the overcoming of one essential limitation of the previous routing algorithms: inaccurate estimations of routing density that were too general for symmetrical FPGAs. To this end, we formulate an exact routing density calculation that is based on a precise analysis of the structure (switch block) of symmetrical FPGAs and utilize it consistently in global and detailed routings. With an introduction to the proposed accurate routing metrics, we describe a new routing algorithm, called cost-effective net-decomposition-based routing, which is fast and yet produces remarkable routing results in terms of both routability and net/path delays. We performed extensive experiments to show the effectiveness of our algorithm based on the proposed cost metrics.

Ultra-deep submicron technology and system-on-chip have resulted in a considerable portion of power dissipated on buses, in which the major sources of the power dissipation are: 1) the self transition activities on the signal lines and 2) the coupled transition activities of the lines. However, there has been no easy way of optimizing 1 and 2 simultaneously at an early stage of the synthesis process. In this paper, we propose a new (on-chip) bus synthesis algorithm to minimize the total sum of 1 and 2 in the microarchitecture synthesis. Specifically, unlike the previous approaches in which 1 and 2 are minimized sequentially without any interaction between them, or only one of them is minimized, we, given a scheduled dataflow graph to be synthesized, minimize 1 and 2 simultaneously by formulating and solving the two important issues in an integrated fashion: binding data transfers to buses and determining a (physical) order of signal lines in each bus, both of which are the most critical factors that affect the results of 1 and 2. Experimental results on a number of benchmark problems show that the proposed integrated low-power bus synthesis algorithm reduces power consumption by 24.8%, 40.3%, and 18.1% on average over those in (Chang and Pedram 1995, for minimizing 1 only), (Shin and Sakurai 2001, for 2 only) and (Shin and Sakurai 2001 and Chang and Pegram 1995, for 1 and then 2), respectively.

In deep submicrometer (DSM) design, the interconnect delay becomes equally as or more important than that of logic gates. In particular, to achieve timing closure in DSM design, it is essential to consider the interconnect delay at an early stage of the synthesis process. Unfortunately, few successes of achieving a tight link of front-end synthesis to back-end layout have been reported, from a practical point of view, mainly due to the inaccuracy of predicting the layout effects during the synthesis. In this brief, we address a new approach to the problem of synthesis of parallel multiplier circuits combined with the consideration of layout effects. The approach is intended to overcome some of the limitations of the previous works, in which the effects of layout on the synthesis have either not been taken into account or considered only in local and limited ways, or the computation time is extremely large. The proposed approach refines the structure and placement of the circuit by iteratively performing two tasks. Task 1: timing-driven relocation. For a parallel multiplier circuit that was restructured at the prior iteration, we attempt to replace the modules in the structure while retaining the interconnects to find a placement with shorter timing. Task 2: timing-driven resynthesis. We attempt to restructure the interconnect topology of the placement obtained from Task 1 to further reduce the circuit timing, employing two heuristics: a modified version of timing-optimal FA-tree allocation by Stelling et al. (1996), considering interconnect delay, and a critical path-based local interconnect refinement. The iterative mechanism of the two tasks practically tightly integrates the synthesis and placement tasks so that both of the effects of placement on the results of synthesis and the effects of synthesis on the results of placement are taken into account. From experiments using a set of benchmark designs, it is shown that the approach is quite effective and efficient, producing designs with less interconnect delay over the sequential method of synthesis and placement.

The delay of memory access is one of the major bottlenecks in embedded systems' performance. In software compilation, it is known that there is high variations in memory access delay depending on the ways of storing/retrieving the variables in code to/from the memories. In this paper, we propose an effective storage assignment technique for variables to maximize the use of memory bandwidth. Specifically, we study the problem of DRAM memory layout for storing the non-array variables in code to achieve a maximum utilization of page and/or burst modes for the memory accesses. The contributions of our work are, for each of page and burst modes: (1) We prove that the problem is NP-hard; (2) We propose an exact formulation of the problem and efficient memory layout algorithms, called Solve-MLP for the page mode and Solve-MLB for the burst mode; >From experiments with a set of benchmark programs, we confirm that our proposed techniques use on average 20.0% and 9.9% more page accesses and 54.0% and 86.6% more burst accesses than those by OFU (the order of first use) and the technique in [1, 2], respectively.

One of the important issues in embedded system design is to optimize program code for the microprocessor to be stored in ROM. In this paper, we propose an integrated approach to the DSP address-code generation problem for minimizing the number of addressing instructions. Unlike previous works, in which code scheduling and offset assignment are performed sequentially without any interaction between them, our work tightly couples offset assignment problem with code scheduling to exploit scheduling on minimizing addressing instructions more effectively. We accomplish this by developing a fast but accurate two-phase assignment procedure which, for a sequence of code schedules, finds a sequence of memory layouts with minimum addressing instructions. Experimental results with benchmark DSP programs show improvements an average of 5.8% in the whole code size over the existing methods.

In deep submicron technology, wires are equally or more important than logic components since wire-related problems such as crosstalk noise is much critical in system-on-chip design. Recently, a method for generating a partial product reduction tree with optimal-timing using bit-level adders to implement arithmetic circuits has been proposed, which outperforms the current best designs. However, in the conventional approaches, interconnects are not primary components to be optimized in the synthesis of arithmetic circuits, mainly due to its integration complexity or unpredictable wire effects, thereby resulting in unsatisfactory layout results with long and messy wire connections. To overcome the limitation, we propose a new module generation/synthesis algorithm for arithmetic circuits utilizing carry-save-adder (CSA) modules, which not only optimizes the circuit timing but also generates a much more regular interconnect topology of the final circuits. Specifically, we propose a two-step algorithm: (Phase 1: CSA module generation) we propose an optimal-timing CSA module generation algorithm for an arithmetic expression under a general CSA timing model; then (Phase 2: Bit-level interconnect refinements), we optimally refine the interconnects between the CSA modules while retaining the global CSA-tree structure produced by Phase 1. We show that the timing of the circuits produced by our approach is equal or almost close to that in most test cases (even without including the interconnect delay), and at the same time, the interconnects in layout are short and regular.

Minimum delay associated with the hold time requirement is of concern to circuit designers, since race-through hazards are inherent in any multiple clock organization or clock distribution tree irrespective of clock frequency. The monotonic property of domino logic aggravates the min-delay path failure through coupling-induced speedup. To tackle the min-delay problem for domino logic, we propose a min-delay optimization algorithm considering coupling effects. Experimental results indicate that our algorithm yields a significant increase of min-delay without incurring max-delay violation.

Coupling effect due to line-to-line capacitance is of serious concern in timing analysis of circuits in ultra deep submicrometer CMOS technology. Often coupling delay is heavily dependent on temporal correlation of signal switching in relevant wires. Temporal decorrelation by shifting timing window can alleviate performance degradation induced by tight coupling. This paper presents an algorithm for minimizing circuit delay through timing window modulation in dual V/sub t/ technology. Experimental results on the ISCAS85 benchmark circuits indicate that the critical delay will be reduced significantly when low V/sub t/ is applied properly.

We propose an effective algorithm for power optimization in behavioral synthesis. In previous work, it has been shown that several hardware allocation/binding problems for power optimization can be formulated as network flow problems and cand be solved optimally. However, in these formulations, a fixed schedule was assumed. In such a context, one key problem is that given an optimal network flow solution to a hardware allocation/binding problem for a given schedule, how to generate a new optimal network-flow solution rapidly for a local change of the given schedule. To this end, from a comprehensive analysis of the relation between network structure and flow computation, we devise a two-step procedure: Step 1) a max-flow computation step which finds a valid (maximum) flow solution while retaining the previous (maximum flow of minimum cost) solution as much as possible and Step 2) a min-cost computation step which incrementally refines the flow solution obtained in Step 1, using the concept of finding a negative cost cycle in the residual graph for the flow. The proposed algorithm can be applied effectively to several important high-level optimization problems (e.g., allocations/bindings of functional units, registers, buses, and memory ports) when we have the freedom to choose a schedule that will minimize power consumption. Experimental results (for bus synthesis) on benchmark problems show that our designs are 4%-40% more power-efficient over the designs produced by a random-move based solution and a clock-step based optimal solution, which is due to a) exploitation of the effect of scheduling and b) optimal binding for every schedule instance. Furthermore, our algorithm is about 2.6 times faster in run time over the full network flow based (optimal) algorithm, which is due to c) our novel (two-step) mechanism which utilizes the previous flow solution to reduce redundant flow computations.

One of the important issues in embedded system design is to optimize program code for the microprocessor to be stored in ROM. In this paper, we propose an integrated approach to the DSP address code generation problem for minimizing the number of addressing instructions. Unlike previous works in which code scheduling and offset assignment are performed sequentially without any interaction between them, our work tightly couples offset assignment problem with code scheduling to exploit scheduling on minimizing addressing instructions more effectively. We accomplish this by developing a fast but accurate two-phase procedure which, for a sequence of code schedules, finds a sequence of memory layouts with minimum addressing instructions. Experimental results with benchmark DSP programs show improvements of 13%-33% in the address code size over Solve-SOA/GOA [7].

In deep sub-micron (DSM) technology, wires are equally or more important than logic components since wire-related problems such as crosstalk, noise are much critical in system-on-chip (SoC) design. Recently, a method [12] for generating a partial product reduction tree (PPRT) with optimal-timing using bit-level adders to implement arithmetic circuits, which outperforms the current best designs, is proposed. However, in the conventional approaches including [12], interconnects are not primary components to be optimized in the synthesis of arithmetic circuits, mainly due to its high integration complexity or unpredictable wire effects, thereby resulting in unsatisfactory layout results with long and messed wire connections. To overcome the limitation, we propose a new module generation/synthesis algorithm for arithmetic circuits utilizing carry-save-adder (CSA) modules, which not only optimizes the circuit timing but also generates a much regular interconnect topology of the final circuits. Specifically, we propose a two-step algorithm: (Phase 1: CSA module generation) we propose an optimal-timing CSA module generation algorithm for an arithmetic expression under a general CSA timing model;(Phase 2: Bit-level interconnect refinements) we optimally refine the interconnects between the CSA modules while retaining the global CSA-tree structure produced by Phase 1. It is shown that the timing of the circuits produced by our approach is equal or almost close to that by [12] in most testcases (even without including the interconnect delay), and at the same time, the interconnects in layout are significantly short and regular.

Ultra deep submicron (UDSM) technology and system-on-chip (SoC) have resulted in a considerable portion of power dissipated on buses, in which the major sources of the power dissipation are (1) the transition activities on the signal lines and (2) the coupling capacitances of the lines. However, there has been no easy way of optimizing (1) and (2) simultaneously at an early stage of the synthesis process. In this paper, we propose a new (on-chip) bus synthesis algorithm to minimize the total sum of (1) and (2) in the microarchitecture synthesis. Specifically, unlike the previous approaches in which (1) and (2) are minimized sequentially without any interaction between them, or only one of them is minimized, we, given a scheduled dataflow graph to be synthesized, minimize (1) and (2) simultaneously by formulating and solving the two important issues in an integrated fashion: binding data transfers to buses and determining a (physical) order of signal lines in each bus, both of which are the most critical factors that affect the results of (1) and (2). Experimental results on a number of benchmark problems show that the proposed integrated low-power bus synthesis algorithm reduces power consumption by 24.8%, 40.3% and 18.1% on average over those in [12] (for minimizing (1) only), [1] (for (2) only) and [12, 1] (for (1) and then (2)), respectively.

In deep submicron (DSM) technology, the interconnects are equally as or more important than the logic gates. In particular, to achieve timing closure in DSM technology, it is very necessary and critical to consider the interconnect delay at an early stage of the synthesis process. It has been known that resource sharing in high-level synthesis is one of the major synthesis tasks which greatly affect the final synthesis/layout results. In this paper, we propose a new layout-driven resource sharing approach to overcome some of the limitations of the previous works in which the effects of layout on the synthesis have never been taken into account or considered in local and limited ways, or whose computation time is excessively large. The proposed approach consists of two steps: (Step 1) We relax the integrated resource sharing and placement into an efficient linear programming (LP) formulation based on the concept of discretizing placement space; (Step 2) We derive a feasible solution from the solution obtained in Step 1. Then, we employ an iterative mechanism based on the two steps to tightly integrate resource sharing and placement tasks so that the slack time violation due to interconnect delay (determined by placement) as well as logic delay (determined by resource sharing) should be minimized. From experiments using a set of benchmark designs, it is shown that the approach is effective, and efficient, completely removing the slack time violation produced by conventional methods.

In this paper, we present a new approach to the problem of inverter elimination in domino logic synthesis. A small piece of static CMOS logic is introduced to the circuit to avoid significant area penalty resulting from duplication. To maximize the domino logic part and to minimize the static CMOS logic part, a generalized automatic test pattern generation (ATPG)-based logic transformation is proposed to eliminate or relocate a target inverter. Based on the new concept of dominating set of mandatory assignment (DSMA) and the corresponding implication graph, we propose algorithms to identify a minimum candidate set for a target inverter. Experimental results show that logic transformation based on the implication graph can reduce transistor counts by 25% on average, while the delay increases less than 3%.

In this article we present a new approach to the problem of local logic transformation for reducing power dissipation in logic circuits. The proposed approach overcomes one of the critical limitations common to the previous approaches of local logic transformations for low power, namely, a sequential greedy transformation that identifies signals with high switching activities and then resynthesizes the signals one by one. Instead, we identify a set of signal lines as a group for logic transformation, and determine an order of transformation of the signals with the maximum reduction of power dissipation in the circuit. As a practically feasible solution to this problem, we develop a power model called a finite state input transition (FIT) model, which allows the efficient measurement of the change of power dissipation of the circuit for every possible sequence of logic transformations among the signal lines. Experimental results show that the proposed approach performs an extensive local logic transformation, reducing power consumption by 33% on average without any increase of circuit delay.

Timing and area of circuits are two of the most important design criteria to be optimized in data path synthesis. In addition, carry-save-adder (CSA) has been proven to be one of the most efficient implementation units in optimizing timing and/or area of arithmetic circuits. However, the existing approaches are restricted in using CSAs, i.e., optimizing operation trees separately without any interaction between them, resulting in a locally optimized CSA circuit. To overcome this limitation, we propose a practically efficient solution to the problem of an accurate exploration of timing and area trade-offs in optimizing arithmetic circuits in the presence of multiple operation trees using CSAs. The application of our approach is able to find a best CSA implementation of circuit in terms of timing and area.

In this paper, we study a new problem of statically estimating the power sensitivity of a given logic circuit with respect to the primary inputs. The power sensitivity defines the characteristics of power dissipation due to changes in state of primary inputs, Consequently, estimating the power sensitivity among the inputs is essential not only to measure the power consumption of the circuit efficiently but also to provide potential opportunities of redesigning the circuit for low power, In this context, we propose a fast and reliable static estimation technique for power sensitivity based on a new concept called power equations, which are then collectively transformed into a table called power table. Experimental data on MCNC benchmark examples show that the proposed technique is useful and effective in estimating power consumption. In summary, the relative error for the estimation of maximum power consumption is 9.4% with a huge speed-up in simulation.

Article Share on An accurate evaluation of routing density for symmetrical FPGAs Authors: Nak-Woong Eum Electronics & Telecommunications Res. Institute, Taejon, Korea Electronics & Telecommunications Res. Institute, Taejon, KoreaView Profile , Taewhan Kim Dept. of EECS, KAIST, Taejon, Korea Dept. of EECS, KAIST, Taejon, KoreaView Profile , Chong-Min Kyung Dept. of EECS, KAIST, Taejon, Korea Dept. of EECS, KAIST, Taejon, KoreaView Profile Authors Info & Claims GLSVLSI '01: Proceedings of the 11th Great Lakes symposium on VLSIMarch 2001 Pages 51–55https://doi.org/10.1145/368122.368794Online:01 March 2001Publication History 0citation151DownloadsMetricsTotal Citations0Total Downloads151Last 12 Months0Last 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 new performance and routability driven routing algorithm for symmetrical array based field-programmable gate arrays (FPGAs). A key contribution of our work is to overcome one essential limitation of the previous routing algorithms: inaccurate estimations of routing density which were too general for symmetrical FPGAs. To this end, we derive an exact routing density calculation that is based on a precise analysis of the structure (switch block) of symmetrical FPGAs, and utilize it consistently in global and detailed routings. With an introduction of the proposed accurate routing metrics, we design a new routing algorithm called a cost-effective net-decomposition based routing which is fast, and yet produces remarkable routing results in terms of both mutability and path/net delays. We performed an extensive experiment to show the effectiveness of our algorithm based on the proposed cost metrics.

We propose an effective algorithm for power optimization in behavioral synthesis. In previous work, it has been shown that several hardware allocation/binding problems for power optimization can be formulated as network flow problems and be solved optimally. However, in these formulations, a fixed schedule was assumed. In such context, one key problem is: given an optimal network flow solution to a hardware allocation/binding problem for a schedule, how to generate a new optimal network flow solution rapidly for a local change of the schedule. To this end, from a comprehensive analysis of the relation between network structure and flow computation, we devise a two-step procedure: (Step 1) max-flow computation step which finds a valid (maximum) flow solution while retaining the previous (maximum flow of minimum cost) solution as much as possible; (Step 2) min-cost computation step which incrementally refines the flow solution obtained in Step 1, using the concept of finding a negative cost cycle in the residual graph for the flow. The proposed algorithm can be applied effectively to several important high-level data path optimization problems (e.g., allocations/bindings of functional units, registers, buses, and memory ports) when we have the freedom to choose a schedule that will minimize power consumption. Experimental results (for bus synthesis) on benchmark problems show that our designs are 5.2% more power-efficient over the best known results, which is due to (a) exploitation of the effect of scheduling and (b) optimal binding for every schedule instance. Furthermore, our algorithm is about 2.8 times faster in run time over the full network flow based (optimal) bus synthesis algorithm, which is due to (c) our novel (two-step) mechanism which utilize the previous flow solution to reduce redundant flow computations.

Carry-save-adder (CSA) is one of the most widely used components for fast arithmetic in industry. This paper provides a solution to the problem of finding an optimal-timing allocation of CSAs in arithmetic circuits. Namely, we present a polynomial time algorithm which finds an optimal-timing CSA allocation for a given arithmetic expression. We then extend our result for CSA allocation to the problem of optimizing arithmetic expressions across the boundary of design hierarchy by introducing a new concept, called auxiliary ports. Our algorithm can be used to carry out the CSA allocation step optimally and automatically and this can be done within the context of a standard RTL synthesis environment.

Article Free Access Share on A timing-driven synthesis of arithmetic circuits using carry-save-adders (short paper) Authors: Taewhan Kim Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science & Technology, Taejon, 305-701, Korea Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science & Technology, Taejon, 305-701, KoreaView Profile , Junhyung Um Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science & Technology, Taejon, 305-701, Korea Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science & Technology, Taejon, 305-701, KoreaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 313–316https://doi.org/10.1145/368434.368656Published:28 January 2000Publication History 3citation201DownloadsMetricsTotal Citations3Total Downloads201Last 12 Months9Last 6 weeks2 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 SiteeReaderPDF

Wallace-tree compressor style has been widely recognized as one of the most effective implementation schemes for arithmetic computation sin VLSI design. However, the scheme has been applied only in a rather restrictive way, that is, for implementing fast multipliers and for generating fixed structures without considering the characteristic of the input signals. The contributions of our work are (1) to extend the applicability of the Wallace scheme to any arithmetic circuit which consists of additions/substractions/multiplications globally (instead of applying it to each operation) to produce a globally efficient architecture of the circuit; (2) to optimize the timing of the circuit for uneven signal arrival profiles; (Specifically, we present an efficient algorithm for generating a delay-optimal (bit-level) carry-save addition structure of an arithmetic circuit.) (3) to provide a comprehensive analysis of the switching activity of a (bit-level) carry-save addition structure, and based on which we derive an effective algorithm for synthesizing low power circuits. Putting these arithmetic optimization solutions together, a circuit designer will be able to fully understand the synthesis of arithmetic circuit based on the bit-level carry-save addition.

In this paper, we study the problem of behavioral-level partitioning for low power design. By behavioral-level partitioning, we mean a partitioning which is done at the behavioral description where scheduling and allocation have not been carried out. The motivation is that turning on/off individual operations cycle-by-cycle is very expensive, thereby we provide a partitioning solution so that all operations in the same partition can be controlled by the same gated clock signal. Our partitioning algorithm is specifically focused on the applications which contain many nested conditional branches and loops.

Carry-save-adder (CSA) is one of the most widely used types of operation in implementing a fast computation of arithmetics. An inherent limitation of the conventional CSA applications is that the applications are confined to the sections of arithmetic circuit that can be directly translated into addition expressions. To overcome this limitation, from the analysis of the structures of arithmetic circuits found in industry, we derive a set of simple, but effective CSA transformation techniques other than the existing ones. These are 1) optimization across multiplexers, 2) optimization across design boundaries, and 3) optimization across multiplications. Based on the techniques, we develop a new timing-driven CSA transformation algorithm that is able to utilize CSA's extensively throughout all circuits. Experimental data for practical testcases are provided to show the effectiveness of our algorithm.

Carry-save-adder(CSA) is one of the most widely used schemes for fast arithmetic in industry. This paper provides a solution to the problem of finding an optimal-timing allocation of CSAs. Specifically, we present a polynomial time algorithm which finds an optimal-timing CSA allocation for a given arithmetic expression. In addition, we extend our result for CSA allocation to the problem of optimizing arithmetic expressions across the boundary of design hierarchy by introducing a new concept, called auxiliary ports. Our algorithm can be used to carry out the CSA allocation step optimally and automatically, and this can be done within the context of a standard HDL synthesis environment.

Carry-save-adder(CSA) is the most often used type of operation in implementing a fast computation of arithmetics of register-transfer level design in industry. This paper establishes a relationship between the properties of arithmetic computations and several optimizing transformations using CSAs to derive consistently better qualities of results than those of manual implementations. In particular, we introduce two important concepts, operation-duplication and operation-split, which are the main driving techniques of our algorithm for achieving an extensive utilization of CSAs. Experimental results from a set of typical arithmetic computations found in industry designs indicate that automating CSA optimization with our algorithm produces designs with significantly faster timing and less area.

Carry-save-adder (CSA) is the most often used type of operation in implementing a fast computation of arithmetics of register-transfer-level design in industry. This paper establishes a relationship between the properties of arithmetic computations and several optimizing transformations using CSAs to derive consistently better qualities of results than those of manual implementations. In particular, we introduce two important concepts, operation duplication and operation split, which are the main driving techniques of our algorithm for achieving an extensive utilization of CSAs. Experimental results from a set of typical arithmetic computations found in industry designs indicate that automating CSA optimization with our algorithm produces designs with up to 53% faster timing and up to 42% smaller area.

A new scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an "equivalent" one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Our approach is particularly effective when there is a large number of nested conditional branches in a dataflow graph.>

In this paper, a new approach to the problem of allocating multiport memory modules for data storage is presented. Previous approaches divide the allocation problem into two separate steps: (i) grouping the variables (or registers) to form memory modules and (ii) determining the interconnections between the memory modules and functional units. Yet, there is no easy way to predict the result of step (ii) during step (i). In our approach, we place primary importance on the cost of interconnections. Consequently, we try to minimize the cost of interconnections first and then to group the variables to form memory modules later. For a number of benchmark problems, it has been shown that this approach is quite effective.

A novel scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an 'equivalent' one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Experimental results demonstrated that such an approach is quite effective. The proposed bottom-up hierarchical approach is computationally more effective than a global nonhierarchical one.>