There has been significant recent progress to reduce the computational effort of static IR drop analysis using neural networks, and modeling as an image-to-image translation task. A crucial issue is lack of sufficient data from real industry designs to train these networks. In this work, we first propose a number of improvements to the state-of-the-art U-Net neural network model to achieve better IR drop prediction. First, we propose U-Net with attention gates which allows selective emphasis on relevant parts of the input data without supervision. This is desired because of the often sparse nature of the IR drop map. We also embed the U-Net model with a preprocessing convolutional block which introduces an initial perimage filter to better handle the multi-image to single-image nature of the problem. Next, to address lack of sufficient data we propose a two-phase training process which utilizes a mix of artificially-generated data and a limited number of points from real designs with custom learning and dropout rates at each phase, and a custom loss function. We also propose a data augmentation step based on image transformations to augment the training data. Based on the ICCAD 2023 contest setup, our results are on-average, 38% (64%) better in MAE and 26% (142%) in F1 score compared to the winner of the ICCAD 2023 contest (and U-Net only [3]) when only tested on the set of real designs in the testing set.

In this paper, we introduce ReBERT, a specialized large language model (LLM) based on BERT, fine-tuned specifically for grouping bits into words within gate-level netlists. By treating the netlist as a form of language, we encode bits and their fan-in cones into sequences that capture structural dependencies. A novel contribution is augmenting BERT's embedding with a tree-based embedding strategy which mirrors the hierarchical nature of circuit designs in hardware. Leveraging the powerful representational learning capabilities of LLMs, we interpret hardware circuits at a higher level of abstraction. We evaluate ReBERT on various hardware designs, demonstrating that it significantly outperforms a state-of-the-art work based on partial structural matching in recovering word-level groupings. Our improvements are on average between 12.2% to 218.1% depending on degree of corrupting the structural patterns.

This work is the first to formulate distributed inference in deep neural networks (DNNs) when considering frequency selection of an edge/hub/cloud device as an additional knob of control which can impact the global latency and/or energy. Specifically, each device in the network may have a set of discrete operating frequencies which we utilize to formulate the problem of layer-wise partitioning of a DNN in a distributed execution environment. We first develop a procedure for profiling energy and latency of a device, based on its operating frequencies, to execute a subset of DNN layers. We then propose an Integer Linear Programming (ILP) formulation for distributed inference which incorporates frequency-dependent energy and latency profiles. In our experiments, we demonstrate variations of ILP including energy-, and latency-constrained, when aiming to find the transition layer from the edge to a cloud device. We consider NVIDIA Jetson Nano and LePotato as edge device options to explore frequency selection. We show better energy and/or latency of our ILP, compared to a recent work (JointDNN).

Distributed inference allows minimizing metrics such as latency by offloading some computations from an edge device. It is commonly formulated and solved as an Integer Linear Program (ILP) for layer-wise partitioning of a Deep Neural Network (DNN) to decide transition points from an edge device to a hub and/or cloud devices. The formulation requires parameters reflecting latencies to execute different bundles of consecutive layers of DNN on each device. Profiling is the main way to measure these bundle latencies accurately on a device. In this work, we show a recent ILP of the layer-wise partitioning (JointDNN) cannot in fact always generate an optimal solution. As we show, this happens due to profiling behavior seen in some devices. We propose DIME (Distributed Inference Model Estimation) with novel modifications to accurately estimate the latency of a bundle within the ILP formulation. It guarantees generating the optimal solution regardless of the type of device in the network. Additionally, DIME incorporates a new input parameter within the ILP to control the tradeoff between solution quality and the profiling effort. In our experiments we show solving DIME always results in the optimal solution, sometimes with significantly less profiling effort.

No abstract available.

We propose$\text{Edge}^{n}$AI, a framework to decompose a complex deep neural networks (DNN) over$n$available local edge devices with minimal communication overhead and overall latency. Our framework creates small DNNs (SNNs) from an original DNN by partitioning its classes across the edge devices, while taking into account their available resources. Class-aware pruning is applied to aggressively reduce the size of the SNN on each edge device. The SNNs perform inference in parallel, and are configured to generate a ‘Don't Know’ response when an unassigned class is identified. Our experiments show up to 17X inference speedup compared to a recent work, on devices of at most 150 MB memory when distributing a variant of VGG-16 over 20 parallel edge devices.

We propose a framework for Class-aware Personalized Neural Network Inference (CAP’NN), which prunes an already-trained neural network model based on the preferences of individual users. Specifically, by adapting to the subset of output classes that each user is expected to encounter, CAP’NN is able to prune not only ineffectual neurons but also miseffectual neurons that confuse classification, without the need to retrain the network. CAP’NN also exploits the similarities among pruning requests from different users to minimize the timing overheads of pruning the network. To achieve this, we propose a clustering algorithm that groups similar classes in the network based on the firing rates of neurons for each class and then implement a lightweight cache architecture to store and reuse information from previously pruned networks. In our experiments with VGG-16, AlexNet, and ResNet-152 networks, CAP’NN achieves, on average, up to 47% model size reduction while actually improving the top-1(5) classification accuracy by up to 3.9%(3.4%) when the user only encounters a subset of the trained classes in these networks.

This is the first work that incorporates recent advancements in "explainability" of machine learning (ML) to build a routing obfuscator called ObfusX. We adopt a recent metric---the SHAP value---which explains to what extent each layout feature can reveal each unknown connection for a recent ML-based split manufacturing attack model. The unique benefits of SHAP-based analysis include the ability to identify the best candidates for obfuscation, together with the dominant layout features which make them vulnerable. As a result, ObfusX can achieve better hit rate (97% lower) while perturbing significantly fewer nets when obfuscating using a via perturbation scheme, compared to prior work. When imposing the same wirelength limit using a wire lifting scheme, ObfusX performs significantly better in performance metrics (e.g., 2.4 times more reduction on average in percentage of netlist recovery).

Logic synthesis is a fundamental step in hardware design whose goal is to find structural representations of Boolean functions while minimizing delay and area. If the function is completely-specified, the implementation accurately represents the function. If the function is incompletely-specified, the implementation has to be true only on the care set. While most of the algorithms in logic synthesis rely on SAT and Boolean methods to exactly implement the care set, we investigate learning in logic synthesis, attempting to trade exactness for generalization. This work is directly related to machine learning where the care set is the training set and the implementation is expected to generalize on a validation set. We present learning incompletely-specified functions based on the results of a competition conducted at IWLS 2020. The goal of the competition was to implement 100 functions given by a set of care minterms for training, while testing the implementation using a set of validation minterms sampled from the same function. We make this benchmark suite available and offer a detailed comparative analysis of the different approaches to learning.

Recent years have seen promising studies on machine learning (ML) techniques applied to approximate logic synthesis (ALS), especially based on logic reconstruction from samples of input-output pairs. This “sampling-based ALS” supports integration with conventional logic synthesis and optimization techniques, as well as synthesis for a constrained input space (e.g., when primary input values are restricted using Boolean relations). To achieve an effective sampling-based ALS, for the first time, this paper proposes the use of adaptive decision trees (ADTs), and in particular variations guided by explainable ML. We adopt SHAP importance, which is a feature importance metric derived from a recent advance in explainable ML to guide the training of ADTs. We also include approximation techniques for ADT which are specifically designed for ALS, including don't-care bit assertion and instantiation. Comprehensive experiments show that we can achieve 39%-42% area reduction with 0.20%-0.22% error rate on average, based on 15 logic functions in the IWLS'20 benchmark suite.

In this work, we propose AirNN, a novel framework which enables dynamic approximation of an already-trained convolutional neural network (CNN) in hardware during inference. AirNN enables input-dependent approximation of the CNN to achieve energy saving without much degradation in its classification accuracy at runtime. For each input, AirNN uses only a fraction of the CNN’s weights based on that input (with the rest remaining 0) to conduct the inference. Consequently, energy saving is possible due to fewer number of fetches from off-chip memory as well as fewer multiplications for majority of the inputs. To achieve per-input approximation, we propose a clustering algorithm that groups similar weights in the CNN based on their importance, and design an iterative framework that decides dynamically how many clusters of weights should be fetched from off-chip memory for each individual input. We also propose new hardware structures to implement our framework on top of a recently proposed FPGA-based CNN accelerator. In our experiments with popular CNNs, we, on average, show 49% energy saving with less than 3% degradation in classification accuracy due to doing inference with only a fraction of the weights for the majority of the inputs. We also propose a greedy interleaving scheme, implemented in hardware, in order to improve the performance of the iterative procedure and compensate for its latency overhead.

We propose CAP’NN, a framework for Class-Aware Personalized Neural Network Inference. CAP’NN prunes an already-trained neural network model based on the preferences of individual users. Specifically, by adapting to the subset of output classes that each user is expected to encounter, CAP’NN is able to prune not only ineffectual neurons but also miseffectual neurons that confuse classification, without the need to retrain the network. CAP’NN achieves up to 50% model size reduction while actually improving the top-l(5) classification accuracy by up to 2.3%(3.2%) when the user only encounters a subset of VGG-16 classes.

With advanced technology nodes, resolving design rule check (DRC) violations has become a cumbersome task, which makes it desirable to make predictions at earlier stages of the design flow. In this paper, we show that the Random Forest (RF) model is quite effective for the DRC hotspot prediction at the global routing stage, and in fact significantly outperforms recent prior works, with only a fraction of the runtime to develop the model. We also propose, for the first time, to adopt a recent explanatory metric-the SHAP value-to make accurate and consistent explanations for individual DRC hotspot predictions from RF. Experiments show that RF is 21%-60% better in predictive performance on average, compared with promising machine learning models used in similar works (e.g. SVM and neural networks) while exhibiting good explainability, which makes it ideal for DRC hotspot prediction.

This paper is the first to analyze the security of split manufacturing using machine learning (ML), based on data collected from layouts provided by industry, with eight routing metal layers and significant variation in wire size and routing congestion across the layers. Many types of layout features are considered in our ML model, including those obtained from placement, routing, and cell sizes. Since the runtime cost of our basic ML procedure becomes prohibitively large for lower layers, we propose novel techniques to make it scalable with little sacrifice in the effectiveness of the attack. Moreover, we further improve the performance in the top routing layer by making use of higher quality training samples and by exploiting the routing convention. We also propose a validation-based proximity attack procedure, which generally outperforms our recent prior work. In the experiments, we analyze the ranking of the features used in our ML model and show how features vary in importance when moving to the lower layers. We provide comprehensive evaluation and comparison of our model with different configurations and demonstrate dramatically better performance of attacks compared to the prior work.

This paper presents a structure simplification procedure that allows efficient energy and accuracy tradeoffs in implementation of trained deep neural networks (DNNs). This structure simplification procedure identifies and eliminates redundant neurons in any layer of the DNN based on the trained weights connected from these neurons. This procedure may be applied to all layers of a DNN. For each layer different configurations with Pareto-optimal accuracy and energy consumption are realized. Our work is the first to use energy-accuracy trade-offs to guide optimal structure realization of trained DNNs. After redundant neurons are discarded, the weights of remaining neurons will be updated using matrix multiplication without retraining. Yet, retraining may still be applied if desired to further fine tune the performance. In our experiments, we show energy-accuracy tradeoff provides clear guidance to achieve efficient realization of trained DNNs. We also observe significant implementation cost reductions with up to 33X in energy and 12X in memory while the performance (accuracy) loss is negligible.

This work is the first to analyze the security of split manufacturing using machine learning, based on data collected from layouts provided by industry, with 8 routing metal layers, and significant variation in wire size and routing congestion across the layers. We consider many types of layout features for machine learning including those obtained from placement, routing, and cell sizes. For the top split layer, we demonstrate dramatically better results in proximity attack compared to a recent prior work. We analyze the ranking of the features used by machine learning and show the importance of how features vary when moving to the lower layers. Since the runtime of our basic machine learning becomes prohibitively large for lower layers, we propose novel techniques to make it scalable with little sacrifice in effectiveness of the attack.

Local nets are by default ignored during global routing but can contribute to a high percentage (up to 30%) of total number of nets in the design. Prior work proposed simple models for how local nets are routed and showed benefits such as better congestion analysis post-placement, integration with global routing, and better track assignment. In this work we study local net modeling using machine learning. Our model predicts utilization by local routes inside each global cell. We model this as a regression problem and as reference use local route utilization data from the detailed routing stage using a commercial tool. To solve the problem we identify suitable machine learning algorithms. Within our modeling, we study and rank different features which utilize various layout attributes. We identify the most beneficial features and show our model performs superior to prior work which were based on pin density and Steiner tree models. Our model also performs better for the subset of local nets which are routed in more than one global cell.

This is the first work to propose generation of the network model of a convolutional neural network (CNN) specifically for power-efficient implementation using the ReRAM technology. State-of-the-art in this area is based on implementation of an already fixed CNN model. It uses parallel crossbar structures to achieve a desired precision quantization of the edge weights using the limited precision provided by individual ReRAM devices. In contrast, in this work we keep the ReRAM crossbar structure in mind during model generation, and target altering a base CNN model such that the resulting implementation will be more power efficient. This is by means of eliminating the parallel crossbars as much as possible, thus reducing the number of required analog-to-digital and digital-to-analog converters which are dominant sources of power consumption. We propose four architectural techniques which are applicable to convolutional and fully-connected layers in a CNN and alter the network model to work with lower precision of the weights with negligible loss in accuracy. In our experiments, we achieve at least 50% power savings with almost no loss in accuracy for popular CNNs compared to ReRAM implementation of the base model.

In 2.5D ICs, the number of metal layers in the interposer contributes strongly to its manufacturing costs. Many systems implemented as 2.5D ICs include component dies, e.g. FPGA dies, that have flexible interconnect that increase connectivity options within the 2.5D IC. We present the first work to leverage flexible interconnect in FPGA dies within a 2.5D IC to decrease routing metal layers in the interposer. This is done by performing 3D global routing and reassigning flexible pins in the FPGA dies. In our experiments, we reduce the number of metal layers by up to 33% versus the number of layers required before reassigning flexible pins.

We propose a framework to quickly analyze track congestion inside each g-cell at the global routing stage. A distinguishing feature of our framework compared to prior work is estimating the locations of vias and partial track utilization by a global segment inside each g-cell for a given global routing solution. We integrate this model with a proposed track assignment algorithm which we show can more effectively reduce track overlaps compared to prior work. A strength of this work is to evaluate the accuracy with respect to an accurate congestion map generated by a commercial detailed router as reference. This work is a step towards bridging the gap between global and detailed routing which is an important obstacle facing modern IC design.

This work is the first to propose a technology mapping algorithm for All Spin Logic (ASL) device. The ASL is the most actively-pursed one among spintronic devices which themselves fall under emerging post-CMOS nano-technologies. We identify the shortcomings of directly applying classical technology mapping with ASL devices, and propose techniques to extend it to handle these shortcomings. Our results show that our ASL-aware technology mapping algorithm can achieve on-average 9.15% and up to 27.27% improvement in delay (when optimizing delay) with slight improvement in area, compared to the solution generated by classical technology mapping. In a broader sense, our results show the need for developing circuit-level CAD tools that are aware of and optimized for emerging nano-technologies in order to better assess their promise as we move to the post-CMOS era.

We study the impact of using 3D monolithic (3DM) standard cells on improving detailed routability and pin access. We propose a design flow which transforms standard rows of single-tier "2D" cells into rows of standard 3DM cells folded into two tiers. The transformation preserves layout characteristics such as overall area and number of metal layers for signal routing (i.e., M2 and above). It also creates redundant pins and free routing tracks in the two tiers used by the 3DM cells. We then propose an Integer Linear Program which routes as many nets as possible on the free 3DM routing tracks, leaving the rest of the nets to be routed via a standard global and detailed router on the metal layers dedicated for signal routing. Our experiments show significant improvement in detailed routability metrics using 3DM cells compared to using 2D standard cells.

This paper proposes global routing models for capturing the impact of local congestion caused by varying-size vias. The models are then incorporated to dynamically drive a proposed layer assignment algorithm. A typical characteristic of advanced technology nodes is significantly high variation in wire sizes that may exist between adjacent metal layers. Routing from a global cell (g-cell) to its top metal layer results in using a via which may be up to twice the size of unit wire track within that g-cell. This results in significant decrease in the available routing tracks that could pass the boundaries of the g-cell. Ignoring this issue hampers the effectiveness of traditional global routing algorithms due to mismatch with the detailed routing stage. Based on these observations, we propose “via-aware edge overflow” and “edge-aware via overflow” models for capturing the impact of both unstacked and stacked vias of arbitrary sizes during global routing. Our models can be used to drive any layer assignment algorithm and replace the traditional edge overflow and via overflow metrics. To show the impact of our models, we also incorporate them in a proposed two-stage layer assignment algorithm and compare with a competitive layer assignment technique. This is also the first work to actually evaluate the impact of global routing solutions using a commercial detailed router. In our experiments we report fewer number of design rule check violations by only changing the layer assignment during global routing, and detail routing with Olympus-SoC of Mentor Graphics.

Split manufacturing is a technique that allows manufacturing the transistor-level and lower metal layers of an integrated circuit (IC) at a high-end, untrusted foundry, while manufacturing only the higher metal layers at a smaller, trusted foundry. Using split manufacturing is only viable if the untrusted foundry cannot reverse engineer the higher metal layer connections (and thus the overall IC design) from the lower layers. This paper studies the effectiveness of proximity attack as a key step to reverse engineer a design at the untrusted foundry. We propose and study different proximity attacks based on how a set of candidates are defined for each broken connection. The attacks use both placement and routing information along with factors which capture the router's behavior such as per-layer routing congestion. Our studies are based on designs having millions of nets routed across nine metal layers and significant layer-by-layer wire size variation. Our results show that a common, Hamming distance-based proximity attack seldom achieves a match rate over 5%. But our proposed attack yields a relatively small list of candidates which often contains the correct match. Finally, we propose a procedure to artificially insert routing blockages in a design at a desired split level, without causing any area overhead, in order to trick the router to make proximity-based reverse engineering significantly more challenging.

This work is the first to present global routing models for capturing the impact of local congestion caused by varying-size vias. The models are then incorporated to dynamically drive a proposed layer assignment algorithm. A typical characteristic of advanced technology nodes is significantly-high variation in wire sizes that may exist between adjacent metal layers. Routing from a global cell (g-cell) to its top metal layer results in using a via which may be up to twice the size of unit wire track within that g-cell. This results in significant decrease in the available routing tracks that could pass the boundaries of the g-cell. Ignoring this issue hampers the effectiveness of traditional global routing algorithms due to acting as, now, a significant source of mismatch with the detailed routing stage. Based on these observations, we propose “via-aware edge overflow” and “edge-aware via overflow” models for capturing the impact of both unstacked and stacked vias of arbitrary sizes during global routing. Our models can be used to drive any layer assignment algorithm and replace the traditional edge overflow and via overflow metrics. To show the impact of our models, we also incorporate them in a proposed two-stage layer assignment algorithm and compare with a competitive layer assignment technique. This is also the first work to actually evaluate the impact of global routing solutions using a commercial detailed router. In our experiments we report less number of DRC violations by only changing the layer assignment at global routing, and detailed route using the Olympus-SoC of Mentor Graphics.

Split manufacturing is a technique that allows manufacturing the transistor-level and lower metal layers of an IC at a high-end, untrusted foundry, while manufacturing only the higher metal layers at a smaller, trusted foundry. Using split manufacturing is only viable if the untrusted foundry cannot reverse engineer the higher metal layer connections (and thus the overall IC design) from the lower layers. This work studies the effectiveness of proximity attack as a key step to reverse engineer a design at the untrusted foundry. We propose and study different proximity attacks based on how a set of candidates are defined for each broken connection. The attacks use both placement and routing information along with factors which capture the router's behavior such as per-layer routing congestion. Our studies are based on designs having millions of nets routed across 9 metal layers and significant layer-by-layer wire size variation. Our results show that a common, Hamming Distance-based proximity attack seldom achieves a match rate over 5%. But our proposed attack yields a relatively-small list of candidates which often contains the correct match. Finally, we propose a procedure to artificially insert routing blockages in a design at a desired split level, without causing any area overhead, in order to trick the router to make proximity-based reverse engineering significantly more challenging.

No abstract available.

This work tackles the problem of reverse engineering a gate-level netlist in order to identify groups of wires corresponding to words. It serves as the major step to find high-level modules and analyze their correct functionality in the presence of Hardware Trojans. Our core idea is to find and utilize control signals to more effectively identify words. Specifically, modern designs provide ample opportunities because they contain numerous control signals which are automatically inserted by the CAD tools. But finding control signals is itself an unresolved challenge. We propose a procedure to identify words which at its core finds and utilizes a small subset of relevant control signals by exploiting partial structural similarity. In our experiments, we show the effectiveness of our procedure by showing a high number of identified words with high accuracy using many benchmarks with already-identified words as the reference case.

This work presents a framework which detects online and at operand level of granularity all the vectors which excite a set of diagnosed failures in combinational modules. The failures may be of various types and may change over time. We propose to utilize this ability to detect failures at operand level of granularity to improve yield, by not discarding those chips containing failing and redundant computational units as long as they are not failing at the same time. The main challenge in realization of such a framework is the ability for on-chip storage of all the (test) vectors which excite the set of diagnosed failures. A major contribution of this work is to significantly minimize the number of stored test cubes by inserting only a few but carefully-selected "false alarm" vectors. As a result, a computational unit may be mis-diagnosed as failing for a given operand however we show such cases are rare and the chip may continue to be used.

Advanced technology nodes have engendered new challenges in the design of integrated circuits (ICs), which can only be addressed through innovations in physical design techniques and algorithms. These challenges stem from factors such as increasingly complex manufacturing design rules, cell pin access in technologies utilizing multiple patterning and FinFETs, various types of restrictions and blockages on the routing layers, and complexity of the physical floorplan, for example due to irregular shapes of placeable areas. This issue and the next issue feature the special section on physical design aimed at addressing these challenges.

Trace buffers are used during post-silicon debug to increase the visibility to the internal signals of a chip via online tracing of a few state elements within a capture window. Due to the small bandwidth of the trace buffer, only a few state elements can be selected or tracing in order to restore the states of the remaining state elements as many as possible. In this work, we show that the quality of restoration corresponding to a set of trace signals selected for a single operating mode, may significantly degrade over the remaining operating modes of a design; an operating mode refers to specific values taken by control signals such as signals for mode selection and scan enable. This is the first work to study the multi-mode trace signal selection problem in order to maximize the restoration over all the operating modes of a design. We propose algorithmic strategies for this problem as well as a procedure to reduce the number of modes by merging the ones with “similar” restoration maps; merging improves the runtime scalability of our multi-mode trace selection algorithm with increase in the number of modes, without much loss in the solution quality.

A major challenge in post-silicon debug is the lack of observability to the internal signals of a chip. Trace buffer technology provides one venue to address this challenge by online tracing of a few selected state elements. Due to the limited bandwidth of the trace buffer, only a few state elements can be selected for tracing. Recent research has focused on automated trace signal selection problem to maximize restoration of the untraced state elements using the few traced signals. Existing techniques can be categorized into high quality but slow simulation-based techniques and lower quality but much faster metric-based techniques. This paper presents a new trace signal selection technique which has comparable or better quality than simulation-based while it has a fast runtime, comparable to the metric-based techniques.

The main challenge in post-silicon debug is the lack of observability to the internal signals of a chip. Trace buffer technology provides one venue to address this challenge by online tracing of a few selected state elements. Due to the limited bandwidth of the trace buffer, only a few state elements can be selected for tracing. Recent research has focused on automated trace signal selection problem in order to maximize restoration of the untraced state elements using the few traced signals. Existing techniques can be categorized into high quality but slow “simulation-based”, and lower quality but much faster “metric-based” techniques. This work presents a new trace signal selection technique which has comparable or better quality than simulation-based while it has a fast runtime, comparable to the metric-based techniques.

Local nets are a major contributing factor to mismatch between the global routing (GR) and detailed routing (DR) stages. A local net has all its terminals inside one global cell (gcell) and is traditionally ignored during global routing. This work offers two contributions in order to estimate and manage the local nets at the GR stage. First, a procedure is given to generate gcells of non-uniform size in order to reduce the number of local nets and thus the cumulative error associated with ignoring or approximating them. Second, we approximate the resource usage of local nets at the GR stage by introducing a capacity for each gcell in the GR graph. With these two complementary approaches, we offer a mathematical model for the congestion-aware GR problem that captures local congestion with non-uniform gcells along with other complicating factors of modern designs including variable wire sizes, routing blockages, and virtual pins. A practical routing procedure is presented based on the mathematical model that can solve large industry instances. This procedure is integrated with the CGRIP congestion analysis tool. In the experiments, we evaluate our techniques in planning for local nets during GR while accounting for other sources of congestion using the ISPD11 benchmarks.

Many combinatorial optimization problems in the embedded systems and design automation domains involve decision making in multidimensional spaces. The multidimensional multiple-choice knapsack problem (MMKP) is among the most challenging of the encountered optimization problems. MMKP problem instances appear for example in chip multiprocessor runtime resource management and in global routing of wiring in circuits. Chip multiprocessor resource management requires solving MMKP under real-time constraints, whereas global routing requires scalability of the solution approach to extremely large MMKP instances. This article presents a novel MMKP heuristic, CPH (for Compositional Pareto-algebraic Heuristic), which is a parameterized compositional heuristic based on the principles of Pareto algebra. Compositionality allows incremental computation of solutions. The parameterization allows tuning of the heuristic to the problem at hand. These aspects make CPH a very versatile heuristic. When tuning CPH for computation time, MMKP instances can be solved in real time with better results than the fastest MMKP heuristic so far. When tuning CPH for solution quality, it finds several new solutions for standard benchmarks that are not found by any existing heuristic. CPH furthermore scales to extremely large problem instances. We illustrate and evaluate the use of CPH in both chip multiprocessor resource management and in global routing.

This paper presents a collaborative procedure for multiobjective global routing. Our procedure takes multiple global routing solutions, which are generated independently (e.g., by one router that runs in different modes concurrently or by different routers running in parallel), as input. It then performs multiobjective optimization based on Pareto algebra and quickly generates multiple global routing solutions with a tradeoff between the considered objectives. The user can control the number of generated solutions and the degree of exploring the tradeoff between them by constraining the maximum allowable degradation in each objective. This paper then considers the following three multiobjective case studies: 1) minimization of interconnect power and wirelength; 2) minimization of routing congestion and wirelength; and 3) minimization of wirelength with respect to the (finite-capacity) routing resources. The maximum allowable degradation in wirelength is specified in all cases. Our multiobjective procedure runs in only a few minutes for each of the International Symposium on Physical Design 2008 benchmarks, even the unroutable ones, which imposes a tolerable overhead in the design flow. In our simulations, we demonstrate the effectiveness of our procedure using five modern academic global routers.

Cloud computing for EDA requires a client to send problem instances containing confidential design information to an untrusted distributed network. To preserve the design information in such a framework, this work focuses on obfuscating the global routing problem modeled as an Integer Linear Program (ILP) for large industry benchmarks. Multiple transformations are introduced in a proposed framework in which the client masks the ILP instance before it is sent to the cloud. The cloud solves the masked instance and the client unmasks the generated solution. No approximations are involved in this process. The masked instance is shown to be substantially more immune to various introduced attacks. Otherwise layout statistics and even detailed connectivity information can easily be deciphered. When applying the transformation, the increase in immunity can be traded off with the induced runtime overhead.

This work offers a framework which does not rely on a Golden IC (GIC) during hardware Trojan (HT) detection. GIC is a Trojan-free IC which is required, in all existing HT frameworks, as a reference point to verify the responses obtained from an IC under authentication. However, identifying a GIC is not a trivial task. A GIC may not even exist, since all the fabricated ICs may be HT-infected. We propose a framework which is based on adding a set of detection sensors to a design which are integrated in the free spaces on the layout and fabricated on the same die. After fabrication, a self-authentication procedure is proposed in order to determine if a Trojan is inserted in a set of arbitrarily-selected paths in the design. The detection process uses on-chip measurements on the sensors and the design paths in order to evaluate the correlation between a set of actual and predicted delay ranges. Error in the on-chip measurement infrastructure is considered. If our framework determines that a Trojan is (or is not) inserted on a considered path, then it is accurate. In our computational experiments, conducted for challenging cases of small Trojan circuits in the presence of die-to-die and within-die process variations, we report a high detection rate to show its effectiveness in realizing a self-authentication process which is independent of a GIC.

This work offers a framework for predicting the delays of individual design paths at the post-silicon stage which is applicable to post-silicon validation and delay characterization. The prediction challenge is mainly due to limited access for direct delay measurement on the design paths after fabrication, combined with the high degree of variability in the process and environmental factors. Our framework is based on using on-chip delay sensors to improve timing prediction. Given a placed netlist at the pre-silicon stage, an optimization procedure is described which automatically generates the sensors subject to an area budget and available whitespace on the layout, in the presence of process variations. Each sensor is then generated as a sequence of logic gates with an approximate location on the layout at the pre-silicon stage. The on-chip sensor delay is then measured to predict the delays of individual design paths with less pessimism. In our experiments, we show that custom on-chip sensors can significantly increase the rate of predicting if a specified set of paths are failing their timing requirements.

This paper introduces a novel approach for isolating the failing paths for a fabricated chip. Failing paths are defined as the paths violating the timing constraint at the post-silicon stage, in the presence of process variations. To achieve this goal, a framework is suggested in which, first, a large number of statistically critical paths are extracted at the pre-silicon stage. These paths are those with the highest probability to violate the timing and therefore can form a “good” candidate set for failing paths. Next, a small set of representative paths are selected from those in the candidate set. These selected paths have their delays highly correlated with the delays of the remaining statistically critical paths. By directly measuring the delays of these selected representative paths at the post-silicon stage, the post-silicon delays of the remaining candidate failing paths can be predicted accurately that allows further isolating the failing paths for each fabricated chip. Simulation results show that up to a few thousand candidate failing paths can be accurately predicted using the post-silicon delays of less than 150 representative paths in the presence of more than 1000 independent process parameter variations for the ISCAS89 benchmark circuits. For each fabricated chip, the isolated failing paths are guaranteed to include all the “actual” failing paths in the candidate set. The proportion of the “actual” nonfailing paths from the isolated failing paths is shown to be very small.

This work presents a method for global routing (GR) to minimize interconnect power. We consider design with multi-supply voltage, where level converters are added to nets that connect driver cells to sink cells of higher supply voltage. The level converters are modeled as additional terminals during GR. Given an initial GR solution obtained with the objective of minimizing wirelength, we propose a GR method to detour nets to further save the interconnect power. When detouring routes via this procedure, overflow is not increased, and the increase in wirelength is bounded. The power saving opportunities include: 1) reducing the area capacitance of the routes by detouring from the higher metal layers to the lower ones, 2) reducing the coupling capacitance between adjacent routes by distributing the congestion, and 3) considering different power-weights for each segment of a routed net with level converters (to capture its corresponding supply voltage and activity factor). We present a mathematical formulation to capture these power saving opportunities and solve it using integer programming techniques. In our simulations, we show considerable saving in an interconnect power metric for GR, without any wirelength degradation.

This work presents a fast and flexible framework for congestion analysis at the global routing stage. It captures various factors that contribute to congestion in modern designs. The framework is a practical realization of a proposed parameterized integer programming formulation. The formulation minimizes overflow inside a set of regions covering the layout which is defined by an input resolution parameter. A resolution lower than the global routing grid-graph creates regions that are larger in size than the global-cells. The maximum resolution case simplifies the formulation to minimizing the total overflow which has been traditionally used as a metric to evaluate routability. A novel contribution of this work is to demonstrate that for a small analysis time budget, regional minimization of overflow with a lower resolution allows a more accurate identification of the routing congestion hotspot locations, compared to minimizing the total overflow. It allows generating a more accurate congestion heatmap. The other contributions include several new ideas for a practical realization of the formulation for industry-sized benchmark instances some of which are also improvements to existing global routing procedures. This work also describes coalesCgrip, a simpler variation of our framework which was used to evaluate the ISPD 2011 contest.

This paper introduces GRIP, a global routing technique via integer programming. GRIP optimizes wirelength and via cost directly without going through a traditional layer assignment phase. Candidate routes spanning all the metal layers are generated using a linear programming pricing phase that formally accounts for the impact of existing candidate routes when generating new ones. To make an integer-programming-based approach applicable for today's large-scale global routing instances, the original problem is decomposed into smaller subproblems corresponding to rectangular subregions on the chip together with their net assignments. Route fragments of nets that fall in adjacent subproblems are connected in a flexible manner. In case of overflow, GRIP applies a second-phase optimization that explicitly minimizes overflow. By using integer programming in an effective manner, GRIP obtains high-quality solutions. Specifically, for the ISPD 2007 and 2008 benchmarks, GRIP obtains an average improvement in wirelength and via cost of 9.23% and 5.24%, respectively, when compared to the best result in the open literature.

This paper introduces a bound-based approach to extract a pre-specified number of statistically-critical paths under process variations. These are the paths with the highest “violation probability,” which indicates the probability that a path would violate a given timing constraint. Our approach requires pre-computation of the violation probability of all the nodes and edges in the circuit timing graph, which can be done using two rounds of block-based statistical static timing analysis. Given these node/edge violation probabilities, we derive tight upper and lower bounds for any arbitrary segment of consecutive nodes and edges, which is the major contribution of this paper. We further utilize these bounds to extract the statistically-critical paths and show constant-time for incremental update of the bounds when extending a segment to a longer one. If our goal is to extract the single most statistically-critical path, we show a bound-based reduction that can prune a large portion of circuit without losing optimality. In our simulations, we verify the correctness and accuracy of our bounds for individual paths, and compare with exact path extraction using Monte-Carlo-based simulation, and an alternative which incorporates path-based statistical static timing analysis.

Technology scaling has allowed integration of multiple cores into a single die. However, high power consumption of each core leads to very high heat density, limiting the throughput of thermal-constrained multi-core processors. To maximize the throughput, various software-based dynamic thermal management and optimization techniques have been proposed, many of which depend on accurate temperature sensing of each core. However, the decision for dynamic thermal management and throughput optimization only based on the temperature of each core can result in less optimal throughput in certain circumstances according to our investigation. In this paper, we propose 1) a dynamic power estimation method using a single thermal sensor for each core in multi-core processors, 2) a die temperature reconstruction method using the estimated power, and 3) a throughput optimization method based the estimated power instead of the temperature. According to our experiment using 90nm technology, the proposed method results in less than 3% error in estimating power and hot-spot temperature of a multi-core processor. Furthermore, the proposed throughput optimization method based on the estimated power leads to up to 4% higher throughput than a temperature-based optimization method.

We propose a parallel global routing algorithm that concurrently processes routing subproblems corresponding to rectangular subregions covering the chip area. The algorithm uses at it core an existing integer programming (IP) formulation---both for routing each subproblem and for connecting them. Concurrent processing of the routing subproblems is desirable for effective parallelization. However, achieving no (or low) overflow global routing solutions without strong, coordinated algorithmic control is difficult. Our algorithm addresses this challenge via a patching phase that uses IP to connect partial routing solutions. Patching provides feedback to each routing subproblem in order to avoid overflow, later when attempting to connect them. The end result is a flexible and highly scalable distributed algorithm for global routing. The method is able to accept as input target runtimes for its various phases and produce high-quality solution within these limits. Computational results show that for a target runtime of 75 minutes, running on a computational grid of few hundred CPUs with 2GB memory, the algorithm generates higher quality solutions than competing methods in the open literature.

The identification of speedpaths is required for post-silicon (PS) timing validation, and it is currently becoming time-consuming due to manufacturing variations. In this paper we propose a method to find a small set of representative paths that can help monitor a large pool of target paths which are more prone to fail the timing at PS stage, to reduce with the validation effort. We first introduce the concept of effective rank to select a small set of representative paths to predict the target paths with high accuracy. To handle the large dimension and degree of independent random parameter variations, we then allow modeling target path delays using segment delays and formulate it as a convex problem. The identification of segments can be incorporated in design of custom test structures to monitor PS circuit timing behavior. Simulations show that we can use the actual timing information of less than 100 paths or segments to accurately predict up to 3,500 target paths (statistically-critical ones) with more than 1,000 process variables.

We study diagnosis of segments on speedpaths that fail the timing constraint at the post-silicon stage due to manufacturing variations. We propose a formal procedure that is applied after isolating the failing speedpaths which also incorporates post-silicon path-delay measurements for more accurate analysis. Our goal is to identify segments of the failing speedpaths that have a post-silicon delay larger than their estimated delays at the pre-silicon stage. We refer to such segments as "failing segments" and we rank them according to their degree of failure. Diagnosis of failing segments alleviates the problem of lack of observability inside a path. Moreover, root-cause analysis, and post-silicon tuning or repair, can be done more effectively by focusing on the failing segments. We propose an Integer Linear Programming formulation to breakdown a path into a set of non-failing segments, leaving the remaining to be likely-failing ones. Our algorithm yields a very high "diagnosis resolution" in identifying failing segments, and in ranking them.

Trace buffer technology allows tracking the values of a few number of state elements inside a chip within a desired time window, which is used to analyze logic errors during post-silicon validation. Due to limitation in the bandwidth of trace buffers, only few state elements can be selected for tracing. In this work we first propose two improvements to existing “signal selection” algorithms to further increase the logic restorability inside the chip. In addition, we observe that different selections of trace signals can result in the same quality, measured as a logic visibility metric. Based on this observation, we propose a procedure which biases the selection to increase the restorability of a desired set of critical state elements, without sacrificing the (overall) logic visibility. We propose to select the critical state elements to increase the “timing visibility” inside the chip to facilitate the debugging of timing errors which are perhaps the most challenging type of error to debug at the post-silicon stage. Specifically, we introduce a case when the critical state elements are selected to track the transient fluctuations in the power delivery network which can cause significant variations in the delays of the speedpaths in the circuit in nanometer technologies. This paper proposes to use the trace buffer technology to increase the timing visibility inside the chip, without sacrificing the logic visibility.

This paper proposes a framework for (signal) interconnect power optimization at the global routing stage. In a typical design flow, the primary objective of global routing is minimization of wirelength and via consumption. Our framework takes a global routing solution that is optimized for this objective, and quickly generates a new solution that is optimized for signal power, with only a small, controlled degradation in wirelength. Our model of signal power includes layer-dependent fringe and area capacitances of the routes, and their spacing. Our framework is fast compared to the existing global routing procedures, thereby not causing much overhead and fitting well in the design flow to optimize signal power after wirelength minimization. The framework is based on Pareto-algebraic operations and generates multiple global routing solutions to provide a tradeoff between power and wirelength, thereby allowing the user to optimize power with a controlled degradation in wirelength. The generated solution remains free of overflow in routing resource usage. We experiment with large benchmarks from the ISPD 2008 suite and a 45nm technology model. We show on average 19.9% dynamic power saving with at most 3% wirelength degradation using the existing wirelength optimized solutions from the open literature.

We introduce a bound-based technique to identify the top M timing-violating paths in a circuit under variability. These are the paths with the highest violation probability (i.e., Cp) which is the probability that a path (i.e., p) violates the timing constraint. To compute Cp, we require the violation probabilities of the nodes (i.e., Cn) and edges (i.e., Ce) on the path. First, we show computing Cnand Ceof all the nodes and edges requires only two rounds of Statistical Static Timing Analysis and then for each node/edge we need one table lookup for probability calculation using a technique known as Pearson Curve. Given Cnand Ce, our major contribution is in computing upper and lower bounds for Cpof an arbitrary path segment. We show constant-time for incremental update of the bounds when extending a path segment to a longer one. These bounds can be used toexactlyconstruct the top violating paths. If the goal is to find the single most-violating path, we show a bound-based formulation that can prune a large portion of circuit without losing optimality. In our simulations, we verify the correctness and accuracy of our bounds for individual paths. We also verify identification of selected paths using Monte Carlo simulation. We obtain near-optimal accuracy with fast runtimes.

We propose GRIP, a scalable global routing technique via Integer Programming (IP). GRIP optimizes wirelength and via cost without going through a layer assignment phase. GRIP selects the route for each net from a set of candidate routes that are generated based on an estimate of congestion generated by a linear programming pricing phase. To achieve scalability, the original IP is decomposed into smaller ones corresponding to balanced rectangular subregions on the chip. We introduce the concept of a floating terminal for a net, which allows flexibility to route long nets going through multiple subregions. We also use the IP to plan the routing of long nets, detouring them from congested subregions. For ISPD 2007 benchmarks, we obtain 3.9% and 11.3% average improvement in wirelength and via cost for the 2D and 3D versions respectively, compared to the best results reported in the open literature.

This paper is the first to study the impact of fluctuations in virtual power supply rail (vvdd) of power-gated designs on the circuit timing, where the vvdd fluctuations are due to process-induced leakage variability. We present a Monte Carlo-based statistical static timing analysis (SSTA) framework which accurately accounts for process-induced leakage variability and its impact on vvdd fluctuations and timing. For vvdd computation we propose an efficient and fast converging iterative analysis, which we explore to result in minimal additional complexity to traditional SSTA where leakage variability is not considered during analysis. We provide separate discussions for the two cases of SSTA for power-gated ASICs and microprocessors; in the latter we also consider process-induced dynamic power variability. In our simulations, we show significant error in traditional SSTA. We also study the impact of number of power-gated clusters on leakage variability, vvdd fluctuations and timing variations. We show that increase in the number of power-gated clusters reduces the circuit timing variance.

Effects of fluctuations in circuit timing due to process and environmental variations are becoming increasingly important as we move into sub-45 nm technology. Since the delay of each gate is dependent on its input vectors, the timing yield, the probability that the circuit meets the given timing constraint, varies with different primary input patterns. Traditional timing yield estimation approaches assumed worst case delay models for each gate over all its input vectors, which results in much pessimism. To overcome the aforementioned problems, this paper proposes a Monte Carlo based approach which can obtain a much tighter lower bound on the circuit timing yield compared to the existing timing yield estimation techniques. Specifically, our approach builds multiple input-vector-dependent variation-aware delay models for each logic gate, and considers the impact of false paths, both static and dynamic false paths, which are carefully selected from the likely timing-critical paths under variability. We demonstrate gradual improvement in the estimated timing yield in the simulation results, and show that the timing yield computed using traditional worst-case delay models is highly pessimistic.

We propose Parallel and Randomized cell Sizing (PaRS), a parallel and randomized algorithm and tool to solve the discrete gate sizing (cell sizing) problem on a grid. PaRS is formulated based on an optimization framework known as nested partitions which we adopt for the first time in the computer-aided design area. PaRS uses parallelism from a novel perspective to better identify the optimization direction. It achieves near-optimal solutions (under 1%) for minimizing the total power subject to meeting a delay constraint. The embarrassingly parallel nature of PaRS makes it highly scalable. We show small algorithm runtimes, in at most minutes for large benchmarks featuring over 47 000 cells. We make comparison with the optimal solution which we are able to generate using customized and parallel branch-and-bound implementation on a grid. Consequently, we are able to generate the optimal solution within hours. While the optimal algorithm uses up to 200 central processing units (CPUs) on our grid, PaRS achieves significant speedups and near-optimal solutions using only 20 CPUs. We also study the impact of varying number of CPUs in PaRS. Finally, we discuss a grid-based implementation using the ldquomaster-workerrdquo framework.

This paper presents an adjustment-based modeling framework for timing analysis under variability. Instead of building a complex model (such as polynomial one) directly between the circuit timing and parameter variability, we propose to build a model that adjusts an approximate variation-aware timing into an accurate one. The idea is that it is easier to build a model that adjusts an approximate estimate into an accurate one. In addition, it is more efficient to obtain an approximate circuit timing model. The combination of these two observations makes the use of an adjustment-based model a better choice for statistical static timing analysis with high dimension of parameter variability (e.g., at sign-off stage). It can also be used at the postsilicon stage to predict the circuit timing from a smaller subcircuit. To build the adjustment model, we use a simulation-driven approach based on Gaussian Process. Combined with the intelligent sampling, we show that an adjustment-based model can more effectively capture the nonlinearity of the circuit timing with respect to parameter variability compared to polynomial models. Simulation results show that with 42 independent device and interconnect parameter variations, our proposed adjustment-based model obtained using 200 circuit timing samples can achieve much higher accuracy than quadratic model obtained using 2000 samples.

We propose PaRS, a parallel and randomized tool which solves the discrete gate sizing (cell sizing) problem on a grid. PaRS is formulated based on an optimization framework known as Nested Partitions which uses parallelism and randomization from a novel perspective to better identify the optimization direction. It achieves near-optimal solutions for minimizing total power and area subject to meeting a delay constraint. The embarrassingly-parallel nature of PaRS makes it highly efficient. We show small algorithm run-times, in at most minutes for circuits with over 47,000 cells. We make comparison with the optimal solution generated by a custom and parallel branch-and-bound algorithm. Consequently, we are able to generate the optimal solution within hours. While the optimal algorithm uses up to 200 nodes in our grid, PaRS achieves its speedups and near-optimal solutions using only 20 nodes.

This paper presents an adjustment-based modeling framework for statistical static timing analysis (SSTA) when the dimension of parameter variability is high. Instead of building a complex model between the circuit timing and parameter variability, we build a model which adjusts an approximate variation-aware timing into an accurate one. The intuition is that it is simpler to build a model which adjusts an approximate estimate into an accurate one. It is also more efficient to obtain an approximate circuit timing model. The combination of these two observations makes the use of an adjustment-based model a good choice for SSTA with high dimension of parameter variability. To build the adjustment model, we use a simulation-based approach, which is based on Gaussian Process. Combined with intelligent sampling, we show that an adjustment-based model can more effectively capture the nonlinearity of the circuit timing with respect to parameter variability compared to polynomial modeling. We also show that with only 200 samples of the circuit timing and 42 independent parameter variations, adjustment-based modeling obtains higher accuracy than direct SSTA using quadratic modeling.

We present SynECO, a framework to achieve predictable timing improvement via incremental resynthesis and replacement. We target timing-critical paths postplacement and resynthesize and replace promising gates. We show since the wire delays are the non-negligible contributors to a critical-path delay, it is crucial to accurately estimate them to make a predictable synthesis modification. For this purpose, we incorporate an accurate timing analysis tool which uses fast detail routing for wire delay estimation. This allows generating timing estimates that correlate much better with post-routing values compared to Steiner-tree-based estimate of wiring tree and using D2M delay model. Detail routing information allows incorporation of factors such as crosstalk, metal layer assignment and via delays which are crucial for accurate analysis. For fast synthesis, we constrain our logical modifications to be from the physical neighborhood of target gates on the critical paths. Our synthesis framework is completely integrated with the Cadence Encounter tools for physical design.

This paper presents a dual-VtSRAM array design which is robust to process variations. After reviewing a cell-level analysis to compare various dual-Vtconfigurations under variations, an algorithm is introduced which assigns a configuration to each cell in an SRAM array to meet a target read delay with minimum leakage at a desired probability. Two versions of the algorithm are discussed which trade off accuracy in wire delay estimation with granularity of assignment. Simulation results show the probability of meeting a target read delay at various locations is at least 0.93 using our proposed techniques.

We propose a parallel and randomized algorithm to solve the problem of discrete dual-Vt assignment combined with continuous gate sizing which is an important low power design technique in high performance domains. This combinatorial optimization problem is particularly difficult to solve on large-sized circuits. We first introduce a hybrid algorithm which combines the existing heuristics and convex formulations for this problem to achieve a better tradeoff between the runtime of the algorithm and the quality of generated solution. We then extend our algorithm to include parallelism and randomization. We introduce a unique utilization of parallelism to better identify the optimization direction. Consequently, we can reduce both the number of iterations in optimization as well as improve the quality of solution. We further use random sampling to avoid being trapped in local minima and to focus the optimization effort on the more "promising" regions of the solution space. Our algorithm improves the average power by 37% compared to an approach which is based on solving a continuous convex program and applying discretization. Power improvement is over 50% for larger benchmarks for an implementation on a grid of 9 computers.

This paper illustrates the application of a novel theory, namely, the distributional robustness theory (DRT), to compute the worst-case timing yield of a circuit. The assumption is that the probability distributions of the process variables are unknown, and only their intervals and their ldquoclassrdquo of distributions are available. This paper considers practical classes to describe potential distributions which match with partial statistical information that might be available. Some classes are suitable for independent distributions that have symmetrical or asymmetrical shapes, while others can account for correlations. These classes have high flexibility to include various shapes of the distributions of the process variations. At a higher level, they can also capture the case when uncertainty in their correlation coefficients exists. The contributions of this paper are on formulating the DRT for different cases of variations and in deriving conditions (e.g., acceptable bounds on timing constraint, acceptable intervals of variations) that allow applying the results of the DRT. Compared with other recent works, the presented approach can include correlations among process variations and does not require knowledge of the exact function form of their joint distribution function. The presented approach is also applicable to other types of parametric yield.

High performance applications are highly affected by process variations due to considerable spread in their expected frequencies after fabrication. Typically ldquobinningrdquo is applied to those chips that are not meeting their performance requirement after fabrication. Using binning, such failing chips are sold at a loss (e.g., proportional to the degree that they are failing their performance requirement). This paper discusses a gate-sizing algorithm to minimize ldquoyield-lossrdquo associated with binning. We propose a binning yield-loss function as a suitable objective to be minimized. We show this objective is convex with respect to the size variables and consequently can be optimally and efficiently solved. These contributions are yet made without making any specific assumptions about the sources of variability or how they are modeled. We show computation of the binning yield-loss can be done via any desired statistical static timing analysis (SSTA) tool. The proposed technique is compared with a recently proposed sensitivity-based statistical sizer, a deterministic sizer with worst-case variability estimate, and a deterministic sizer with relaxed area constraint. We show consistent improvement compared to the sensitivity-based approach in quality of solution (final binning yield-loss value) as well as huge run-time gain. Moreover, we show that a deterministic sizer with a relaxed area constraint will also result in reasonably good binning yield-loss values for the extra area overhead.

We have developed a new statistical timing analysis approach that does not impose any assumptions on the nature of manufacturing variability and takes into account an arbitrary model of spatial correlation as well as all types of functional correlations (e.g. reconvergence-based correlations). The starting point for statistical timing analysis is small scale Monte Carlo (MC) simulation. In order to speed-up the MC simulation process we use stratified balanced sampling and postprocessing of the simulation data using non-parametric kernel estimation. The MC simulation and the statistical analysis procedure are interleaved with the calculation of the critical paths. In order to speed up simulation, we identify and simulate only gates relevant for calculation of the clock cycle time. The application of statistical techniques enable not only accurate statistical timing analysis, but also stability and scalability analysis. The approach is evaluated using MCNC benchmarks and yields more than six orders of magnitude speed improvement compared with the standard MC simulation.

This paper is a case study of dual-14 configurations of an SRAM cell considering process-induced Vtvariations. Dual threshold voltage assignment is an effective technique to reduce leakage power without any area overhead, however as we will show the quality of a dual-threshold assignment highly varies due to process parameter variations in deca-nanometer designs of today. We analyze and compare the effects of process-induced Vtvariations in 11 dominant dual-14 cell configurations. Under process variations each configuration is evaluated based on the probability density functions (pdfs) of its read delay, leakage current and read stability, accurately obtained using Monte Carlo simulations for 90nm generic process design kit of Cadence. Comparison of different cell configurations is based on evaluating these pdfs at points corresponding to a desired yield. We show that the choice of the best dual-Vtconfiguration varies depending on a given yield, and show tradeoff plots between read delay, leakage and read margin of different configurations under variations.

Process variations result in a considerable spread in the frequency of the fabricated chips. In high performance applications, those chips that fail to meet the nominal frequency after fabrication are either discarded or sold at a loss which is typically proportional to the degree of timing violation. The latter is called binning. In this paper we present a gate sizing-based algorithm that optimally minimizes the binning yield-loss. Specifically we make the following contributions: 1) prove the binning yield function to be convex, 2) the proof does not make any assumptions about the sources of variability, their distributions (Gaussian/Non-Gaussian) or correlation, 3) by using Kelley's cutting-plane method for convex programs, we integrate our strategy with statistical timing analysis tools (STA), without making any assumptions about how STA is done, 4) if the objective is to optimize the traditional yield (and not binning yield) our approach can still optimize the same to a very large extent. Comparison of our approach with sensitivity-based approaches under fabrication variability shows an improvement of on average 72% in the binning yield-loss with an area overhead of an average 6%, while achieving a 2.69 times speedup under a stringent timing constraint. Moreover we show that a worstcase deterministic approach fails to generate a solution for certain delay constraints. We also show that optimizing the binning yield-loss minimizes the traditional yield-loss (although it is not a direct objective) with a 61% improvement from a sensitivity-based approach.

VLSI design optimization requires evaluation of different solutions, to compare superiority of one over the other. Typically, a solution is superior if it has a better associated timing and cost. In the presence of fabrication variability, the timing and cost of a solution become random variables with spatial and functional correlations. Therefore the evaluation of solutions shall be performed probabilistically to determine the probability that a solution has better cost and timing. In this paper we propose and evaluate three methods for fast and accurate probabilistic comparison of solutions: 1) regular Monte Carlo simulation (as a basis of comparison), 2) joint-pdf approximation using moment matching, and 3) bound-based Conditional Monte Carlo simulation.We integrated these methods in a variability-driven leakage optimization framework using dual threshold voltages. Experimental results show that joint-pdf based approximation is very fast, however it results in sub-optimal solutions due to lower accuracy. Conditional Monte Carlo method is on average 25 times faster than regular Monte Carlo, but slower than approximating joint-pdf. It also results in additional improvement in expected leakage, when compared to joint-pdf method. Monte Carlo simulation is extremely slow and inapplicable to an optimization framework. Deterministic approaches that are based on worst-case estimates had the highest expected leakage.

Very large-scale integration design optimization requires comparison of different solutions to evaluate superiority of one over the other. Typically, a solution is superior if it has a better associated timing and cost. In the presence of fabrication variability, the timing and cost of a solution become random variables with spatial and functional correlations. Therefore, the evaluation of solutions shall be performed probabilistically to determine the probability that a solution has better cost and timing. In this paper, the authors propose/evaluate three methods for fast and accurate computation of this probability: 1) regular Monte Carlo (MC) simulation (as a basis of comparison); 2) joint probability density function (jpdf) approximation using moment matching; and 3) bound-based conditional-MC simulation. They integrated these methods in a variability-driven leakage optimization framework using dual threshold voltages. Their results show that jpdf approximation is efficient; however, it results in suboptimal solutions due to lower accuracy approximating jpdf

In this paper, the classic wire-length estimation problem is addressed and a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing is proposed. These types of models are highly instrumental in formalizing a complete and consistent probabilistic approach to design automation and design closure where, along with optimizing the pertinent cost function, the associated prediction error is also considered. The wire-length prediction model was developed using a combination of parametric and nonparametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics after placement will have a particular length. The model is validated using the learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound, and therefore realistic, instances of designs. The net models were applied to the probabilistic buffer-insertion problem and substantial improvement was obtained in net delay after routing (~ 20%) when compared to a traditional bounding box (BBOX)-based buffer-insertion strategy

This article proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First, the generalized low power binding problem is formulated as an Integer Linear Programming (ILP) problem that happens to be an NP-complete task to solve. Then two polynomial-time heuristics are proposed that provide a speedup of up to 13.7 with an extremely low penalty for power when compared to the optimal ILP solution for our selected benchmarks.

In this work we present a probabilistic approach to simultaneous floorplanning and resource binding for low power. Traditional approaches iteratively perform floorplanning and resource binding while using crude deterministic wire-length estimates like bounding box (since we do not have routing information for inter module inter-connect). Non-availability of accurate wire-length results in suboptimal design and failure of timing closure. In this work we model the wire-lengths as probability distributions and propose a novel probabilistic optimization methodology. Experimental results using state of the art commercial and academic tools were conducted. The novelty in this work is in the higher chance of ending with a feasible design that is synthesizable without losing in overall power (interconnect + module + register). Experimental results show that on-average the number of unsynthesized modules after routing for Mediabench benchmarks were 2 in the conventional case, while on average our probabilistic approach had all modules synthesized after routing.

This paper proposes strategies to control the wake-up noise for circuits implemented in MTCMOS technology. In MTCMOS circuits, during the switchings between the active and standby modes, sudden surges in current happens due to floating voltages at the nodes. These surges might violate the reliability of the circuit. In this paper we address the above problem by developing wake-up strategies to control these current surges as the circuit is getting turned on. Through gradually turning on a circuit a smaller current will be drawn from the power-grid network. A novel partitioning technique is proposed for MTCMOS circuits under a given constraint of maximum drawn-current from the power-grid network. Two approaches are proposed in this paper; the optimal ILP-based formulation and a polynomial-time heuristic. Experimental results show that up to 90.7% improvement in peak drawn-current is obtained with a maximum of 4 clock cycles time to turn on the circuit. Also result show the effectiveness of the heuristic in terms of the quality of solution and a run-time of up to 6600 times faster than the ILP approach for larger circuits.

In this work, we investigate the buffer insertion problem under process variations. Sub 100-nm fabrication process causes significant variations on many design parameters. We propose a probabilistic buffer insertion method assuming variations on both interconnect and buffer parameters and consider their correlations due to common sources of variation. Our proposed method is compatible with the more accurate DSM wire-delay model, as well as the Elmore delay model. In addition, a probabilistic pruning criterion is proposed to evaluate potential solutions, while considering their correlations. Experimental results demonstrate that considering correlations using the more accurate DSM delay model results in meeting the timing constraint with an average probability of 0.63. However probabilistic buffer insertion ignoring correlations and deterministic methods, meet the timing constraint with an average probability of 0.25 and 0.19 respectively.

In this paper we address the problem of growing leakage variability through effective dual-threshold voltage assignment. We propose a probabilistic dynamic programming-based method to assign dual-threshold voltages such that the overall expected leakage is minimized under a given probability of violating the timing constraint (timing yield). The key characteristics of our strategy are two pruning criteria that stochastically identify pareto-optimal solutions and prune the sub-optimal ones. Compared to other variability-driven dual-threshold voltage assignment schemes, the main advantages of our approach are 1) considering correlations due to common sources of variation, 2) providing controllable runtime, which in one of the proposed strategies is comparable to the deterministic algorithm, and 3) performing optimization based on all the signal paths simultaneously, as opposed to one path at a time. Experimental results indicate that the proposed probabilistic scheme is significantly better than a comparable deterministic dual-threshold voltage assignment, both in terms of expected leakage and the probability of violating the timing constraint

This article addresses the problem of voltage scheduling in unpredictable situations. The voltage scheduling problem assigns voltages to operations such that the power is minimized under a clock delay constraint. In the presence of unpredictabilities, meeting the clock latency constraint cannot be guaranteed. This article proposes a novel risk management based technique to solve this problem. Here, the risk management paradigm assigns a quantified value to the amount of risk the designer is willing to take on the clock cycle constraint. The algorithm then assigns voltages in order to meet the expected value of clock cycle constraint while keeping the maximum delay within the specified “risk” and minimizing the power. The proposed algorithm is based on dynamic programming and is optimal for trees. Experimental results show that the traditional voltage scheduling approach is incapable of handling unpredictabilities. Our approach is capable of generating an effective tradeoff between power and “risk”: the more the risk, the less the power. The results show that a small increase in design risk positively affects the power dissipation.

Floorplanning information is integrated during resource binding for better modeling of the interconnect effects on timing and power. Although this integration improves the estimation of the interconnect effects, nonavailability of exact net-lengths can result in suboptimal solutions, because global routing is not yet performed. In this work we propose a probabilistic approach to integrate floorplanning and resource binding by modeling the distribution of the net-lengths from a given floorplan. The advantage of this approach is that a probabilistic technique can better capture the inaccuracy associated with net-length estimation, and consequently, the inaccuracy in estimation of net-delay and net-power. The result is higher chance of successful synthesis, and therefore faster timing closure. Additionally, due to better management of uncertainty, it has a better overall post-synthesis power. These results are illustrated in our experiments that were conducted using state of the art commercial and academic tools.

This paper presents a novel approach for leakage optimization through simultaneous V/sub t/ selection and assignment. V/sub t/ selection implies deciding the right value for V/sub t/ and assignment implies deciding which gates should be assigned a particular threshold voltage. We also include the effect of variability in threshold voltage on delay and leakage due to fabrication process variations in our formulations and present a scheme that lets the designer control the leakage and delay variability in his design. The proposed algorithm is a general mathematical formulation that has been shown to trivially extend to multiple threshold voltages.

Power-grid networks are very important aspects of large scale integrated systems. In the modern deep sub-micron era these networks are prone to many sources of noise hence making the voltage supply uctuate. This Vdd-Ground noise can have detrimental effect on design quality. This paper presents a unique strategy of achieving noise immunity through voltage scheduling in Data Flow Graphs (DFGs). A dynamic programming based approach is applied to obtain noise immunity by imposing a grid on the voltage axis. We also present a unique way of including resource binding information into the algorithm. Experimental results indicated that considerable amount of Vdd-noise immunity is achieved for the selected benchmarks.

Given a directed acyclic graph and different possible implementations for each node, the implementation selection problem (ISP) selects the appropriate implementation for each node such that a given global design objective is optimized, ISP is a generic formulation that is explicitly or implicitly solved in several design automation problems like leakage optimization using dual V/sub th/, gate sizing, etc. An implementation of a node results in an associated delay and perhaps cost for the node. In the presence of different sources of uncertainty and fabrication variability, fixed estimates of delays and costs of a node are extremely erroneous. We investigate a probabilistic approach to solve ISP by considering probability density functions for delays and costs of a node. We propose a dynamic-programming based approach in a probabilistic sense and introduce effective pruning criteria when dealing with probability distributions for identifying co-optimal solution at each stage. A case study of leakage optimization using dual V/sub th/ is presented where we show the effectiveness of a probabilistic approach considering V/sub th/ variability over a traditional deterministic one.

We propose a technique for optimizing the runtime in statistical timing analysis. Given a global acceptable error budget at the primary output which signifies the difference in the area of the accurate and approximate timing CDFs, we propose a formulation of budgeting this global error across all nodes in the circuit. This node error budget is used to simplify the computation of arrival time CDFs at each node using approximations. This simplification reduces the runtime of statistical timing analysis. We investigate two ways of exploiting this node error budget, firstly through piecewise linear approximation (see ibid., A. Devgan and C. Kashyap, 2003) and secondly though hierarchical quadratic approximation. Experimental results on ISCAS/MCNC benchmarks show that our approach is at most 3 times faster than accurate statistical timing analysis and had a very small error. We also found quadratic piecewise approximation to be more accurate than linear approximation but at lesser gains in runtime.

We address the classic wire-length estimation problem and propose a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing. The wire-length prediction model was developed using a combination of parametric and non-parametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics obtained after placement will have a particular length. The model is validated using both learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound and therefore realistic instances of designs. We applied the net models to the probabilistic buffer insertion problem and obtained substantial improvement in net delay after routing.

In this paper, we propose a novel, empirical, and parameterizable model for estimating the probability distribution of wire length for each net in a placed netlist. The model is simple and fast to compute. We did extensive experimentation with state-of-the-art commercial (Cadence) and academic (Parquet and Labyrinth) tools and validated our model. Our distribution model was around three times more accurate than assuming half-perimeter bounding box as the fixed net-length estimate. Since the model is parameterizable it can be easily tailored for different routing tools and benchmarks. This model would be very useful in defining a full fledged probabilistic design automation methodology in which various design metrics are optimized from a probabilistic point of view. We also discuss the application of our model in a novel probabilistic approach to the buffer insertion problem.

This paper proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First the generalized low power binding problem is formulated as an Integer Linear Programming(ILP) problem which happens to be an NP-complete task to solve. Then two polynomial-time heuristics are proposed that provide a speedup of up to 13.7 with an extremely low penalty for power when compared to the optimal ILP solution for our selected benchmarks.

This paper addresses the problem of voltage scheduling in unpredictable situations. The voltage scheduling problem assigns voltages to operations such that the power is minimized under a clock cycle constraint. In presence of unpredictabilities meeting the clock constraint cannot be guaranteed. This paper proposes a novel risk management based technique to solve this problem. The risk management paradigm assigns a quantified value to the amount of risk the designer is willing to take on the clock cycle constraint. The algorithm then assigns voltages in order to meet the expected value of clock cycle constraint while keeping the maximum delay within the specified "risk" and minimizing the power.