This paper presents a 6.78-MHz inductive wireless power transfer (WPT) system designed for implantable medical devices (IMDs). To meet the stringent IMD limits on form factor, power conversion efficiency (PCE), and regulation, the proposed system adopts a resonant current-mode (RCM) method. A compact RX coil, under spatial constraints, necessitates the adoption of the RCM method, which provides a voltage conversion ratio greater than unity, enabling efficient transfer of the energy stored in the LC tank to the output. To achieve high regulation performance, a deficit-energy-quantifying (DEQ) resonant regulating rectifier (3R) is introduced. The DEQ-3R operates by quantifying the energy deficit to reach the target output voltage and comparing it with the LC-tank energy. Comparison result detects the transition timing from the resonance phase to the charging phase with a delay-compensated comparator (DCC) adaptive to the LC-tank energy level. The proposed DEQ-3R is implemented in a 180-nm CMOS process, occupying 1.04 mm2 active area. Experiment results using an 80-nH RX coil demonstrate regulated 2.5-V operation over a coupling-coefficient range of 0.1-0.16 and a load power range of 5-45 mW. The prototype achieves a peak PCE of 81.28%, reflecting a 6.08% improvement over a counterpart without the DEQ, while reducing the VOUT ripple from 432mVPP to 168mVPP with a 20-nF output capacitor.

Since Large Language Models or LLMs have demonstrated high-quality performance on many complex language tasks, there is a great interest in bringing these LLMs to mobile devices for faster responses and better privacy protection. However, the size of LLMs (i.e., billions of parameters) requires highly effective compression to fit into storage-limited devices. Among many compression techniques, weight-clustering, a form of non-linear quantization, is one of the leading candidates for LLM compression, and supported by modern smartphones. Yet, its training overhead is prohibitively significant for LLM fine-tuning. Especially, Differentiable KMeans Clustering, or DKM, has shown the state-of-the-art trade-off between compression ratio and accuracy regression, but its large memory complexity makes it nearly impossible to apply to train-time LLM compression. In this letter, we propose a memory-efficient DKM implementation, eDKM powered by novel techniques to reduce the memory footprint of DKM by orders of magnitudes. For a given tensor to be saved on CPU for the backward pass of DKM, we compressed the tensor by applying uniquification and sharding after checking if there is no duplicated tensor previously copied to CPU. Our experimental results demonstrate that eDKM can fine-tune and compress a pretrained LLaMA 7B model from 12.6 GB to $2.5 \mathrm{~GB}(3 \mathrm{~b} /$ weight) with the Alpaca dataset by reducing the train-time memory footprint of a decoder layer by $130 \times$, while delivering good accuracy on broader LLM benchmarks (i.e., $77.7 \%$ for PIQA, $66.1 \%$ for Winograde, and so on).

User-defined keyword spotting on a resource-constrained edge device is challenging. However, keywords are often bounded by a maximum keyword length, which has been largely under-leveraged in prior works. Our analysis of keyword-length distribution shows that user-defined keyword spotting can be treated as a length-constrained problem, eliminating the need for aggregation over variable text length. This leads to our proposed method for efficient keyword spotting, SLiCK (exploiting Subsequences for Length-Constrained Keyword spotting). We further introduce a subsequence-level matching scheme to learn audio-text relations at a finer granularity, thus distinguishing similar-sounding keywords more effectively through enhanced context. In SLiCK, the model is trained with a multi-task learning approach using two modules: Matcher (utterance-level matching task, novel subsequence-level matching task) and Encoder (phoneme recognition task). The proposed method improves the baseline results on Libriphrase hard dataset, increasing AUC from 88.52 to 94.9 and reducing EER from 18.82 to 11.1.

With the rapid expansion in the scale of large language models (LLMs), enabling efficient distributed inference across multiple computing units has become increasingly critical. However, communication overheads from popular distributed inference techniques such as Tensor Parallelism pose a significant challenge to achieve scalability and low latency. Therefore, we introduce a novel optimization technique, Sync-Point Drop (SPD), to reduce communication overheads in tensor parallelism by selectively dropping synchronization on attention outputs. In detail, we first propose a block design that allows execution to proceed without communication through SPD. Second, we apply different SPD strategies to attention blocks based on their sensitivity to the model accuracy. The proposed methods effectively alleviate communication bottlenecks while minimizing accuracy degradation during LLM inference, offering a scalable solution for diverse distributed environments: SPD offered about 20% overall inference latency reduction with $<$ 1% accuracy regression for LLaMA2-70B inference over 8 GPUs.

Keivan Alizadeh, Seyed Iman Mirzadeh, Dmitry Belenko, S. Khatamifard, Minsik Cho, Carlo C Del Mundo, Mohammad Rastegari, Mehrdad Farajtabar. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Spotting user-defined/flexible keywords represented in text frequently uses an expensive text encoder for joint analysis with an audio encoder in an embedding space, which can suffer from heterogeneous modality representation (i.e., large mismatch) and increased complexity. In this work, we propose a novel architecture to efficiently detect arbitrary keywords based on an audio-compliant text encoder which inherently has homogeneous representation with audio embedding, and it is also much smaller than a compatible text encoder. Our text encoder converts the text to phonemes using a grapheme-to-phoneme (G2P) model, and then to an embedding using representative phoneme vectors, extracted from the paired audio encoder on rich speech datasets. We further augment our method with confusable keyword generation to develop an audio-text embedding verifier with strong discriminative power. Experimental results show that our scheme outperforms the state-of-the-art results on Libriphrase hard dataset, increasing Area Under the ROC Curve (AUC) metric from 84.21% to 92.7% and reducing Equal-Error-Rate (EER) metric from 23.36% to 14.4%.

Streaming neural network models for fast frame-wise responses to various speech and sensory signals are widely adopted on resource-constrained platforms. Hence, increasing the learning capacity of such streaming models (i.e., by adding more parameters) to improve the predictive power may not be viable for real-world tasks. In this work, we propose a new loss, Streaming Anchor Loss (SAL), to better utilize the given learning capacity by encouraging the model to learn more from essential frames. More specifically, our SAL and its focal variations dynamically modulate the frame-wise cross entropy loss based on the importance of the corresponding frames so that a higher loss penalty is assigned for frames within the temporal proximity of semantically critical events. Therefore, our loss ensures that the model training focuses on predicting the relatively rare but task-relevant frames. Experimental results with standard lightweight convolutional and recurrent streaming networks on three different speech based detection tasks demonstrate that SAL enables the model to learn the overall task more effectively with improved accuracy and latency, without any additional data, model parameters, or architectural changes.

Large Language Model or LLM inference has two phases, the prompt (or prefill) phase to output the first token and the extension (or decoding) phase to the generate subsequent tokens. In this work, we propose an efficient parallelization scheme, KV-Runahead to accelerate the prompt phase. The key observation is that the extension phase generates tokens faster than the prompt phase because of key-value cache (KV-cache). Hence, KV-Runahead parallelizes the prompt phase by orchestrating multiple processes to populate the KV-cache and minimizes the time-to-first-token (TTFT). Dual-purposing the KV-cache scheme has two main benefits. First, since KV-cache is designed to leverage the causal attention map, we minimize computation and computation automatically. Second, since it already exists for the extension phase, KV-Runahead is easy to implement. We further propose context-level load-balancing to handle uneven KV-cache generation (due to the causal attention) and to optimize TTFT. Compared with an existing parallelization scheme such as tensor or sequential parallelization where keys and values are locally generated and exchanged via all-gather collectives, our experimental results demonstrate that KV-Runahead can offer over 1.4× and 1.6× speedups for Llama 7B and Falcon 7B respectively.

Streaming keyword spotting is a widely used solution for activating voice assistants. Methods based on Deep Neural Networks with Hidden Markov Model (DNN-HMM) have proven to be efficient and widely adopted in this space, primarily because of the ability to detect and identify the start and end of the wake-up word at low compute cost. However, such hybrid systems suffer from loss metric mismatch when the DNN and HMM are trained independently. Sequence discriminative training cannot fully mitigate the loss-metric mismatch due to the inherent Markovian style of the operation. We propose an low footprint CNN model, called HEiMDaL, to detect and localize keywords in streaming conditions. We introduce an alignment-based classification loss to detect the occurrence of the keyword along with an offset loss to predict the start of the keyword. HEiMDaL shows 73% improvement in detection metrics along with equivalent localization accuracy and with the same memory footprint as existing DNN-HMM style models for a given wake-word.

This paper explores the possibility of using visual object detection techniques for word localization in speech data. Object detection has been thoroughly studied in the contemporary literature for visual data. Noting that an audio can be interpreted as a 1-dimensional image, object localization techniques can be fundamentally useful for word localization. Building upon this idea, we propose a lightweight solution for word detection and localization. We use bounding box regression for word localization, which enables our model to detect the occurrence, offset, and duration of keywords in a given audio stream. We experiment with LibriSpeech and train a model to localize 1000 words. Compared to existing work [1], our method reduces model size by 94%, and improves the F1 score by 6.5%.

DNN pruning is a popular way to reduce the size of a model, improve the inference latency, and minimize the power consumption on DNN accelerators. However, existing approaches might be too complex, expensive or ineffective to apply to a variety of vision/language tasks, DNN architectures and to honor structured pruning constraints. In this paper, we propose an efficient yet effective train-time pruning scheme, Parameter-free Differentiable Pruning (PDP), which offers state- of-the-art qualities in model size, accuracy, and training cost. PDP uses a dynamic function of weights during training to generate soft pruning masks for the weights in a parameter-free manner for a given pruning target. While differentiable, the simplicity and efficiency of PDP make it universal enough to deliver state-of-the-art random/structured/channel pruning results on various vision and natural language tasks. For example, for MobileNet-v1, PDP can achieve 68.2% top-1 ImageNet1k accuracy at 86.6% sparsity, which is 1.7% higher accuracy than those from the state-of-the-art algorithms. Also, PDP yields over 83.1% accuracy on Multi-Genre Natural Language Inference with 90% sparsity for BERT, while the next best from the existing techniques shows 81.5% accuracy. In addition, PDP can be applied to structured pruning, such as N:M pruning and channel pruning. For 1:4 structured pruning of ResNet18, PDP improved the top-1 ImageNet1k accuracy by over 3.6% over the state-of-the-art. For channel pruning of ResNet50, PDP reduced the top-1 ImageNet1k accuracy by 0.6% from the state-of-the-art.

Voice trigger detection is an important task, which enables activating a voice assistant when a target user speaks a keyword phrase.A detector is typically trained on speech data independent of speaker information and used for the voice trigger detection task.However, such a speaker independent voice trigger detector typically suffers from performance degradation on speech from underrepresented groups, such as accented speakers.In this work, we propose a novel voice trigger detector that can use a small number of utterances from a target speaker to improve detection accuracy.Our proposed model employs an encoder-decoder architecture.While the encoder performs speaker independent voice trigger detection, similar to the conventional detector, the decoder is trained with metric learning and predicts a personalized embedding for each utterance.A personalized voice trigger score is then obtained as a similarity score between the embeddings of enrollment utterances and a test utterance.The personalized embedding allows adapting to target speaker's speech when computing the voice trigger score, hence improving voice trigger detection accuracy.Experimental results show that the proposed approach achieves a 38% relative reduction in a false rejection rate (FRR) compared to a baseline speaker independent voice trigger model.

An energy-harvesting interface that incorporates a continuously scalable-conversion-ratio (CSCR) switched-capacitor (SC) dc-dc converter with maximum power point tracking (MPPT) is introduced in this paper. By exploiting unique characteristics of a CSCR SC converter, an MPPT based on the hill climbing algorithm is implemented with a real-time power monitoring scheme with a frequency-mapped sampling capacitor DAC, allowing variation-tolerant MPPT for various types of energy sources. The harvestable voltage range is significantly extended by a step-up/down convertible CSCR SC converter, and the voltage conversion efficiency is further improved with matrix-structured and load-mapped power switches. With the test chip fabricated in 28nm FDSOI technology, the proposed energy harvesting interface shows peak conversion efficiency of 89% and average efficiency of > 80% for 60-2,$794~\mu \text{W}$. MPPT efficiency of > 97 % is confirmed with energy harvesting measurement with a solar cell.

Neural Architecture Search (NAS) is an open and challenging problem in machine learning. While NAS offers great promise, the prohibitive computational demand of most of the existing NAS methods makes it difficult to directly search the architectures on large-scale tasks. The typical way of conducting large scale NAS is to search for an architectural building block on a small dataset (either using a proxy set from the large dataset or a completely different small scale dataset) and then transfer the block to a larger dataset. Despite a number of recent results that show the promise of transfer from proxy datasets, a comprehensive evaluation of different NAS methods studying the impact of different source datasets has not yet been addressed. In this work, we propose to analyze the architecture transferability of different NAS methods by performing a series of experiments on large scale benchmarks such as ImageNet1K and ImageNet22K. We find that: (i) The size and domain of the proxy set does not seem to influence architecture performance on the target dataset. On average, transfer performance of architectures searched using completely different small datasets (e.g., CIFAR10) perform similarly to the architectures searched directly on proxy target datasets. However, design of proxy sets has considerable impact on rankings of different NAS methods. (ii) While different NAS methods show similar performance on a source dataset (e.g., CIFAR10), they significantly differ on the transfer performance to a large dataset (e.g., ImageNet1K). (iii) Even on large datasets, random sampling baseline is very competitive, but the choice of the appropriate combination of proxy set and search strategy can provide significant improvement over it. We believe that our extensive empirical analysis will prove useful for future design of NAS algorithms.

We propose FlexReduce, an efficient and flexible all-reduce algorithm for distributed deep learning under irregular network hierarchies. With ever-growing deep neural networks, distributed learning over multiple nodes is becoming imperative for expedited training. There are several approaches leveraging the symmetric network structure to optimize the performance over different hierarchy levels of the network. However, the assumption of symmetric network does not always hold, especially in shared cloud environments. By allocating an uneven portion of gradients to each learner (GPU), FlexReduce outperforms conventional algorithms on asymmetric network structures, and still performs even or better on symmetric networks.

Deep neural networks (DNNs) have achieved significant success in a variety of real world applications, i.e., image classification. However, tons of parameters in the networks restrict the efficiency of neural networks due to the large model size and the intensive computation. To address this issue, various approximation techniques have been investigated, which seek for a light weighted network with little performance degradation in exchange of smaller model size or faster inference. Both low-rankness and sparsity are appealing properties for the network approximation. In this paper we propose a unified framework to compress the convolutional neural networks (CNNs) by combining these two properties, while taking the nonlinear activation into consideration. Each layer in the network is approximated by the sum of a structured sparse component and a low-rank component, which is formulated as an optimization problem. Then, an extended version of alternating direction method of multipliers (ADMM) with guaranteed convergence is presented to solve the relaxed optimization problem. Experiments are carried out on VGG-16, AlexNet and GoogLeNet with large image classification datasets. The results outperform previous work in terms of accuracy degradation, compression rate and speedup ratio. The proposed method is able to remarkably compress the model (with up to 4.9X reduction of parameters) at a cost of little loss or without loss on accuracy.

Convolution is a critical component in modern deep neural networks, thus several algorithms for convolution have been developed. Direct convolution is simple but suffers from poor performance. As an alternative, multiple indirect methods have been proposed including im2col-based convolution, FFT-based convolution, or Winograd-based algorithm. However, all these indirect methods have high memory overhead, which creates performance degradation and offers a poor trade-off between performance and memory consumption. In this work, we propose a memory-efficient convolution or MEC with compact lowering, which reduces memory overhead substantially and accelerates convolution process. MEC lowers the input matrix in a simple yet efficient/compact way (i.e., much less memory overhead), and then executes multiple small matrix multiplications in parallel to get convolution completed. Additionally, the reduced memory footprint improves memory sub-system efficiency, improving performance. Our experimental results show that MEC reduces memory consumption significantly with good speedup on both mobile and server platforms, compared with other indirect convolution algorithms.

In-place radix sort is a popular distribution-based sorting algorithm for short numeric or string keys due to its linear run-time and constant memory complexity. However, efficient parallelization of in-place radix sort is very challenging for two reasons. First, the initial phase of permuting elements into buckets suffers read-write dependency inherent in its in-place nature. Secondly, load balancing of the recursive application of the algorithm to the resulting buckets is difficult when the buckets are of very different sizes, which happens for skewed distributions of the input data. In this paper, we present a novel parallel in-place radix sort algorithm, PARADIS, which addresses both problems: a) "speculative permutation" solves the first problem by assigning multiple non-continuous array stripes to each processor. The resulting shared-nothing scheme achieves full parallelization. Since our speculative permutation is not complete, it is followed by a "repair" phase, which can again be done in parallel without any data sharing among the processors. b) "distribution-adaptive load balancing" solves the second problem. We dynamically allocate processors in the context of radix sort, so as to minimize the overall completion time. Our experimental results show that PARADIS offers excellent performance/scalability on a wide range of input data sets.

In this paper, we present a novel algorithm for latch placement, LatchPlanner which enables a placement engine to deliver high quality placement for datapath-oriented design. Datapath-oriented VLSI designs are in general hand-crafted by human at high cost, as understanding and capturing datapath structure is critical for the performance. The conventional placement algorithms by itself cannot exploit the underlying datapath due to lack of logic structure recognition and inaccurate/approximated wirelength estimation. LatchPlanner addresses such drawbacks by placing and fixing latches in the datapath context, a key element in datapath structure. By taking placed/fixed latches as constraints, a placer can find a more datapath-friendly placement effectively, which results in higher-quality hardware. LatchPlanner begins latch clustering/sizing/ordering to prepare the following steps, a) global latch placement based on linear programming to place latch clusters, and b) local latch placement based on network flow optimization to place latches within each cluster. Experimental results on eighteen industrial benchmarks show that LatchPlanner improves total wirelength by 32%, total negative slack by 25%, and area by 3% without CPU overhead over a commercial placement engine, and delivers near semi-custom-quality solutions.

In deep sub-micro designs, more functions are integrated into one chip, and datapath has become a critical part of the design. Typical datapath consists an array of bit slices. The inherent high degree regularity of datapaths is especially attractive to the placement and routing to achieve regular layout with high density and high performance. However, the current design methodology may generate inferior datapath designs because the datapath regularity cannot be well understood by the traditional design tools. In previous works, several techniques are proposed to preserve/re-identify datapath structures. However, they either restrict the datapath optimization or have little tolerance on bit slice difference.

As the CMOS feature enters the era of extreme scaling (14nm, 11nm and beyond), manufacturability challenges are exacerbated. The nanopatterning through the 193nm lithography is being pushed to its limit, through double/triple or more general multiple patterning, while non-conventional lithography technologies such as extreme ultra-violet (EUV), e-beam direct-write (EBDW), and so on, still have grand challenges to be solved for their adoption into IC volume production. This tutorial will provide an overview of key overarching issues in nanometer IC design for manufacturability (DFM) with these emerging lithography technologies, from modeling, mask synthesis, to physical design and beyond.

Double patterning technology (DPT) is regarded as the most practical solution for the sub-22nm lithography technology. DPT decomposes a single layout into two masks and applies double exposure to print the shapes in the layout. DPT requires accurate overlay control. Thus, the primary objective in DPT decomposition is to minimize the number of stitches (overlay) between the shapes in the two masks. The problem of minimizing the number of stitches in DPT decomposition is conjectured to be NP-hard. Existing approaches either apply Integer Linear Programming (ILP) or use heuristics. In this paper, we show that the problem is actually in P and present a method to decompose a layout for DPT and minimize the number of stitches optimally. The complexity of the method is O(n1.5log n). Experimental results show that the method is even faster than the fast heuristics.

As double patterning lithography(DPL) becomes the leading candidate for sub-30 nm lithography process, we need a fast and lithography friendly decomposition framework. In this paper, we propose a multi-objective min-cut based decomposition framework for stitch minimization, balanced density, and overlay compensation, simultaneously. The key challenge of DPL is to accomplish high quality decomposition for large-scale layouts under reasonable runtime with the following objectives: a) the number of stitches is minimized, b) the balance between two decomposed layers is maximized for further enhanced patterning, c) the impact of overlay on coupling capacitance is reduced for less timing variation. We use a graph theoretic algorithm for minimum stitch insertion and balanced density. An additional decomposition constraints for self-overlay compensation are obtained by integer linear programming(ILP). With the constraints, global decomposition is executed by our modified FM graph partitioning algorithm. Experimental results show that the proposed framework is highly scalable and fast: we can decompose all 15 benchmark circuits in five minutes in a density balanced fashion, while an ILP-based approach can finish only the smallest five circuits. In addition, we can remove more than 95% of the timing variation induced by overlay for tested structures.

In VLSI placement, legalization is an essential step where the overlaps between gates/macros must be removed. In this paper, we introduce a history-based legalization algorithm with min-cost network flow optimization. We find a legal solution with the minimum deviation from a given placement to fully honor/preserve the initial placement, by solving a gate-centric network flow formulation in an iterative manner. In order to realize a flow into gate movements, we develop efficient techniques which solve an approximated Subset-sum problem. Over the iterations, we factor into our formulation the history which captures a set of likely-to-fail gate movements. Such a history-based scheme enables our algorithm to intelligently legalize highly complex designs. Experimental results on over 740 real cases show that our approach is significantly superior to the existing algorithms in terms of failure rate (no failure) as well as quality of results (55% less max-deviation).

Clock mesh is popular in high performance VLSI design because it is more robust against variations than clock tree at a cost of higher power consumption. In this paper, we propose novel techniques based on binary linear programming for clock mesh synthesis for the first time in the literature. The proposed approach can explore both regular and irregular mesh configurations, adapting to non-uniform load capacitance distribution. Our synthesis consists of two steps: mesh construction to minimize total capacitance and skew, and balanced sink assignment to improve slew/skew characteristics. We first show that mesh construction can be analytically formulated as binary polynomial programming (a class of nonlinear discrete optimization), then apply a compact linearization technique to transform into binary linear programming, significantly reducing computational overhead. Second, our balanced sink assignment enables a sink to tap the least loaded mesh segment (not the nearest one) with another binary linear programming which reduces both slew and skew. Experiments show that our techniques improve the worst skew and total capacitance by 14% and 15% over the state-of-the-art clock mesh algorithm on ISPD09 benchmarks.

A symmetric-function fan-in tree (SFFT) is a fanout-free cone of logic that computes a symmetric function, so that all of the leaf nets in its support set are commutative. Such trees are frequently found in designs, especially when the design originated as two-level logic.These trees are usually created during logic synthesis, when there is no knowledge of the locations of the tree root or of the source gates of the leaf nets. Because of this, large SFFTs present a challenge to placement algorithms. The result is that the tree placements are generally far from optimal, leading to wiring congestion, excess buffering, and timing problems. Restructuring such trees can produce a more placeable and wire-efficient design.In this paper, we propose algorithms to identify and to restructure SFFTs during physical design. The key feature of an SFFT is that it can be implemented with various structures of a uniform set of gates with commutative inputs, i.e. AND, OR, or XOR. Drawing on the flexibility of SFFT logic structures, the proposed tree restructuring algorithm uses existing placement information to rebuild the SFFTs with reduced tree wire lengths. The experimental results demonstrate the efficiency and effectiveness of the algorithms.

In this paper, we present an efficient lithography aware detailed (ELIAD) router to enhance silicon image after optical proximity correction (OPC) in a correct-by-construction manner. We first quantitatively show that a pre-OPC litho-metric is highly uncorrelated with a post-OPC metric, which stresses the importance of a post-OPC litho-metric for design-time optimization. We then propose a compact post-OPC litho-metric for a detailed router (DR) based on statistical characterization, where the interferences among predefined litho-prone shapes are captured as a lookup table. Our litho-metric derived from the characterization shows high fidelity to the total edge placement error (EPE) in large scale, compared with Calibre OPC/optical rule check. Therefore, ELIAD powered by the proposed litho-metric can enhance the overall post-OPC printed silicon image. Experimental results on 65-nm industrial circuits show that ELIAD outperforms a rip-up/rerouting approach such as Resolution-enhancement-technique-Aware Detailed Routing with 8times more EPE hot spot reduction and 12times speedup. Moreover, compared with a conventional DR, ELIAD is only about 50% slower.

In this article, we present BoxRouter 2.0, and discuss its architecture and implementation. As high-performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose a global router which has a strong ability to improve routability and minimize the number of vias with blockages, while minimizing wirelength. BoxRouter 2.0 is extended from BoxRouter 1.0, but can perform multi-layer routing with 2D global routing and layer assignment. Our 2D global routing is equipped with two ideas: node shifting for congestion-aware Steiner tree and robust negotiation-based A* search for routing stability. After 2D global routing, 2D-to-3D mapping is done by the layer assignment which is powered by progressive via/blockage-aware integer linear programming. Experimental results show that BoxRouter 2.0 has better routability with comparable wirelength than other routers on ISPD07 benchmark, and it can complete (no overflow) the widely used ISPD98 benchmark for the first time in the literature with the shortest wirelength. We further generate a set of harder ISPD98 benchmarks to push the limit of BoxRouter 2.0, and propose the hardened ISPD98 benchmarks to map state-of-the-art solutions for future routing research.

Nanometer IC designs are increasingly challenged by manufacturing closure, i.e., being fabricated with high product yield, mainly due to aggressive technology scaling and increasing process/environmental variations. Realizing the criticality of addressing manufacturabitity for higher yield and tolerance to variations during design, there has been a surge of research activities recently from both academia and industry. In this paper, we will survey the key activities in synergistic physical synthesis and shed tights on some of the future research directions.

In this paper, we present ELIAD, an efficient lithography aware detailed router to optimize silicon image after optical proximity correction (OPC) in a correct-by-construction manner. We first propose a compact post-OPC litho-metric for a detailed router based on statistical characterization. We characterize the interferences among weak grids filled with one of predefined litho-prone shapes (e.g., jog-corner, via, line-end). Our litho-metric derived from the characterization shows high fidelity to total edge placement error (EPE) in large scale, compared with Calibre-OPC/ORC. As a chip itself is in the largest scale, ELIAD powered by the proposed metric can enhance the overall post-OPC printed silicon image. Experimental results on 65nm industrial circuits show that ELIAD outperforms a ripup/rerouting approach such as RADAR [17] with 8x more EPE hotspot reduction and 12x speedup. Also, compared with a conventional detailed router, ELIAD is only about 50% slower.

Double patterning technology (DPT) is a most likely lithography solution for 32/22nm technology nodes as of 2008 due to the delay of Extreme Ultra Violet lithography. However, it should hurdle two challenges before being introduced to mass production, layout decomposition and overlay error. In this paper, we present the first detailed routing algorithm for DPT to improve layout decomposability and robustness against overlay error, by minimizing indecomposable wirelength and the number of stitches. Experimental results show that the proposed approach improves the quality of layout significantly in terms of decomposability and the number of stitches with 3.6x speedup, compared with a current industrial DPT design flow.

In this paper, we propose the first metal-density driven placement algorithm to reduce CMP variation and achieve higher routability. Based on an analytical placement framework, we use a probabilistic routing model to estimate the wire density during the placement. Then, the metal density and thickness are predicted by a predictive CMP model. The spreading forces are adjusted according to the metal density map to reduce the metal density variation. Experimental results show that our method reduces the topography variation by 12% and the number of dummy fills by 6% and achieves much better routability, compared with wirelength-driven placement

In this paper, we propose a high-performance droplet router for digital microfluidic biochip (DMFB) design. Due to recent advancements in bio-MEMS, the design complexity and the scale of a DMFB are expected to explode in near future, thus requiring strong support from CAD as in conventional VLSI design. Among multiple design stages of a DMFB, droplet routing which schedules the movement of each droplet in a time-multiplexed manner is a critical challenge due to high complexity as well as large impacts on performance. Our algorithm first routes a droplet with higher bypassibility which less likely blocks the movement of the others. When multiple droplets form a deadlock, our algorithm resolves it by backing off some droplets for concession. A final compaction step further enhances timing as well as fault-tolerance by tuning each droplet movement greedily. Experimental results on hard benchmarks show that our algorithm achieves over 35x and 20x better routability with comparable timing and fault-tolerance than the popular prioritized A* search [2] and the state-of-the-art network-flow based algorithm [18], respectively

In this paper, we propose the first metal-density-driven (MDD) placement algorithm to reduce chemical-mechanical planarization/polishing (CMP) variation and achieve higher routability. To efficiently estimate metal density and thickness, we first apply a probabilistic routing model and then a predictive CMP model to obtain the metal-density map. Based on the metal-density map, we use an analytical placement framework to spread blocks to reduce metal-density variation. Experimental results based on BoxRouter and NTUgr show that our method can effectively reduce the CMP variation. By using our MDD placement, for example, the topography variation can be reduced by up to 38% (23%) and the number of dummy fills can be reduced by up to 14% (8%), compared with those using wirelength-driven (cell-density-driven) placement. The results of our MDD placement can also lead to better routability.

In this paper, we propose a high-performance droplet router for a digital microfluidic biochip (DMFB) design. Due to recent advancements in the biomicro electromechanical system and its various applications to clinical, environmental, and military operations, the design complexity and the scale of a DMFB are expected to explode in the near future, thus requiring strong support from CAD as in conventional VLSI design. Among the multiple design stages of a DMFB, droplet routing, which schedules the movement of each droplet in a time-multiplexed manner, is one of the most critical design challenges due to high complexity as well as large impacts on performance. Our algorithm first routes a droplet with higher by passibility which is less likely to block the movement of the others. When multiple droplets form a deadlock, our algorithm resolves it by backing off some droplets for concession. The final compaction step further enhances timing as well as fault tolerance by tuning each droplet movement greedily. The experimental results on hard benchmarks show that our algorithm achieves over 35 x and 20 x better routability with comparable timing and fault tolerance than the popular prioritized A* search and the state-of-the-art network-flow-based algorithm, respectively.

In this paper, we propose track routing and optimization for yield (TROY), the first track router for the optimization of yield loss due to random defects. As the probability of failure (POF), which is an integral of the critical area and the defect size distribution, strongly depends on wire ordering, sizing, and spacing, track routing can play a key role in effective wire planning for yield optimization. However, a straightforward formulation of yield-driven track routing can be shown to be integer nonlinear programming, which is a nondeterministic polynomial-time complete problem. TROY overcomes the computational complexity by combining two effective techniques, i.e., the minimum Hamiltonian path (MHP) from graph theory and the second-order cone programming (SOCP) from mathematical optimization. First, TROY performs wire ordering to minimize the critical area for short defects by finding an MHP. Then, TROY carries out optimal wire sizing/spacing through SOCP optimization based on the given wire order. Since the SOCP can be optimally solved in near linear time, TROY efficiently achieves globally optimal wire sizing/spacing for the minimal POF.

In this paper, we introduce a novel substrate noise estimation technique during early floorplanning for mixed signal system-on-chip (SOC), based on block preference directed graph (BPDG). Given a set of analog and digital blocks, BPDG is constructed based on their inherent noise characteristics to capture the preferred relative locations for substrate noise minimization. For each instance of floorplan in sequence pair orB*-tree, we efficiently count the number of violations against BPDG which correlates remarkably well with accurate but computation-intensive substrate noise modeling. Thus, our BPDG-based model can guide fast substrate noise-aware floorplanning and layout optimization for mixed signal SOC. Our experimental results show that the proposed approach is significantly faster than conventional full-blown substrate model-based floorplanning.

In this paper, we propose TROY, the first track router with yield-driven wire planning to optimize yield loss due to random defects. As the probability of failure (POF) computed from critical area analysis and defect size distribution strongly depends on wire ordering, sizing, and spacing, track routing plays a key role in effective wire planning for yield optimization. TROY formulates wire ordering into a preference-aware minimum Hamiltonian path problem. For simultaneous wire sizing and spacing optimization, TROY solves it optimally by formulating the problems into a second order conic programming (SOCP). Experimental results show that TROY can reduce the random-defect yield loss by 18% on average without any overhead in wirelength, compared with the widely used greedy approach.

In this paper, we present BoxRouter 2.0, a hybrid and robust global router with discussion on its architecture and implementation. As high performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose BoxRouter 2.0 which has strong ability to improve routability and minimize the number of vias with blockages, while minimizing wirelength. BoxRouter 2.0 is improved over [1], but can perform multi-layer routing with 2D global routing and layer assignment. Our 2D global routing is equipped with two ideas: robust negotiation- based A∗ search for routing stability, and topology-aware wire ripup for flexibility. After 2D global routing, 2D-to-3D mapping is done by the layer assignment which is powered by progressive via/blockage-aware integer linear programming. Experimental results show that BoxRouter 2.0 has better routability with comparable wirelength than other routers on ISPD07 benchmark, and it can complete (no overflow) ISPD98 benchmark for the first time in the literature with the shortest wirelength.

In this paper, we propose a new global router, BoxRouter, powered by the concept of box expansion, progressive integer linear programming (PILP), and adaptive maze routing (AMR). BoxRouter first uses a simple prerouting strategy to predict and capture the most congested region with high fidelity as compared to the final routing. Based on progressive box expansion initiated from the most congested region, BoxRouting is performed with PILP and AMR. Our PILP is shown to be much more efficient than the traditional ILP in terms of speed and quality, and the AMR based on multisource multitarget with bridge model is effective in minimizing the congestion and wirelength. It is followed by an effective postrouting step, which reroutes without rip-up to enhance the routing solution further and obtain smooth tradeoff between wirelength and routability. Our experimental results show that the BoxRouter significantly outperforms the state-of-the-art published global routers, e.g., 91 % better routability than Labyrinth (with 14% less wirelength and 3.3times speedup), 79% better routability than Chi-dispersion router (with similar wirelength and 2times speedup), and 4.2% less wirelength and 16times speedup than a multicommodity flow-based router (with similar routability). Additional enhancement in box expansion and postrouting further improves the result with similar wirelength but much better routability than the latest work in global routing.

In this paper, we introduce a novel substrate noise estimation technique during early floorplanning, based on the concept of block preference directed graph (BPDG) and the classic sequence pair (SP) floorplan representation. Given a set of analog and digital blocks, the BPDG is constructed based on their inherent noise characteristics to capture their preferred relative orders for substrate noise minimization. For each sequence pair generated during floorplanning evaluation, we can measure its violation against BPDG very efficiently. We observe that by simply counting the number of violations obtained in this manner, it correlates remarkably well with accurate but computation-intensive substrate noise modeling. Thus, our BPDG-based model has high fidelity to guide the substrate noise-aware floorplanning and layout optimization, which become a growing concern for mixed-signal/RF system on chips (SOC). Our experimental results show that the proposed approach is over 60/spl times/ faster than conventional floorplanning with even very compact substrate noise models. We also obtain less area and total substrate noise than the conventional approach.

In this paper, we propose a new global router, BoxRouter, powered by the concept of box expansion and progressive integer linear programming (ILP). BoxRouter first uses a simple PreRouting strategy which can predict and capture the most congested regions with high fidelity compared to the final routing. Based on progressive box expansion initiated from the most congested region, BoxRouting is performed with progressive ILP and adaptive maze routing. It is followed by an effective PostRouting step which reroutes without rip-up to obtain smooth tradeoff between wirelength and routability. Our experimental results show that BoxRouter significantly outperforms the state-of-the-art published global routers, e.g., 79% better routability than [1(with similar wirelength and 2x speedup), 4.2% less wirelength and 16x speedup than [2](with similar routability). Given the fundamental importance of routing, such dramatic improvement shall sparkle renewed interests in routing which plays a key role in nanometer design and manufacturing closure.

In this paper, we propose the first wire density driven global routing that considers CMP variation and timing. To enable CMP awareness during global routing, we propose a compact predictive CMP model with dummy fill, and validate it with extensive industry data. While wire density has some correlation and similarity to the conventional congestion metric, they are indeed different in the global routing context. Therefore, wire density rather than congestion should be a unified metric to improve both CMP variation and timing. The proposed wire density driven global routing is implemented in a congestion-driven global router [5] for CMP and timing optimization. The new global router utilizes several novel techniques to reduce the wire density of CMP and timing hotspots. Our experimental results are very encouraging. The proposed algorithm improves CMP variation and timing by over 7% with negligible overhead in wirelength and even slightly better routability, compared to the pure congestion-driven global router [5].

In this paper, an algorithm for scan vector ordering, PEAKASO, is proposed to minimize the peak temperature during scan testing. Given a circuit with scan and the scan vectors, hotspot is predicted by window-based power analysis. The peak temperature on the hotspot is minimized by global scan vector ordering which expedites heat dissipation to ambient air through large thermal gradient. Further peak temperature reduction is achieved by local scan vector reordering based on overheat precompensation. As an output, PEAKASO provides a scan vector order with lower peak temperature. Note that the scan vectors themselves are not changed at all (only the order is changed), and thus there is no impact on fault coverage and no design overhead. Experimental results on benchmark circuits show that 4.3 - 9.7% peak temperature reduction can be achieved, compared with a scan vector order that is optimized only for average power consumption. Such temperature reduction can be very significant in terms of test time reduction (by 40-60%) under the same peak temperature constraint.

In this paper, an efficient linear time algorithm TACO is proposed for the first time to minimize the worst case clock skew in the presence of on-chip thermal variation. TACO, while tries to minimize the worst case clock skew, also attempts to minimize the clock tree wirelength by building up merging diamonds in a bottom-up manner. As an output, TACO provides balanced merging points and the modified clock routing paths to minimize the worst case clock skew under thermal variation. Experimental results on a set of standard benchmarks show 50-70% skew reduction with less than 0.6% wirelength overhead.