Search

Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by $543\times$ on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by $25-45\times$.

Work-stealing is a key component of many parallel task graph libraries such as Intel Threading Building Blocks (TBB) FlowGraph, Microsoft Task Parallel Library (TPL) Batch .Net, Cpp-Taskflow, and Nabbit. However, designing a correct and effective work-stealing scheduler is a notoriously difficult job, due to subtle implementation details of concurrency controls and decentralized coordination between threads. This problem becomes even more challenging when striving for optimal thread usage in handling parallel workloads with complex task graphs. As a result, we introduce in this paper an effective work-stealing scheduler for execution of task dependency graphs. Our scheduler adopts a simple and efficient strategy to adapt the number of working threads to available task parallelism at any time during the graph execution. Our strategy is provably good in preventing resource underutilization and simultaneously minimizing resource waste when tasks are scarce. We have evaluated our scheduler on both micro-benchmarks and a real-world circuit timing analysis workload, and demonstrated promising results over existing methods in terms of runtime, energy efficiency, and throughput.

In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

Composability is a key component to improve programmers’ productivity in writing fast market-expanding applications such as parallel machine learning algorithms and big data analytics. These applications exhibit both regular and irregular compute patterns, and are often combined with other functions or libraries to compose a larger program. However, composable parallel processing has taken a back seat in many existing parallel programming libraries, making it difficult to achieve modularity in large-scale parallel programs. In this paper, we introduce a new parallel task programming library using composable tasking graphs. Our library efficiently supports task parallelism together with an intuitive task graph construction and flexible execution API set to enable reusable and composable task dependency graphs. Developers can quickly compose a large parallel program from small and modular parallel building blocks, and easily deploy the program on a multicore machine. We have evaluated our library on real-world applications. Experimental results showed our library can achieve comparable performance to Intel Threading Building Blocks with less coding effort.

High-performance computing systems, especially 3D ICs, are yet facing thermal exacerbation. Inter-tier liquid cooling microchannel layers have been introduced into 3D ICs as an integrated cooling mechanism to tackle thermal degradation. Many research works optimize microchannel designs based on runtime-expensive numerical simulations or inaccurate thermofluid models. In this work, we propose accurate closed-form models on tapered microchannel to capture the relationship between channel geometry and heat transfer performance. To improve the accuracy, our correlation is based on developing flow model and derived from numerical simulation using a subset of multiple channel parameters. Our models reduce error by 57 % in Nusselt number and 45 % in pressure drop for channels with inlet width 100-400µm compared to commonly used fully developed flow based models in optimization. Obtained correlations show potential as solid foundation to achieve close to optimal design through runtime-efficient microchannel design optimization.

This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wirelength and density which are widely used as cost and constraint in nonlinear analytical placement. For wirelength gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute-intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High-Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straightforward GPU implementation.

The rapid evolution of modern C++ programming language has completely changed the way developers write high-performance and robust applications. By modern, we mean C++17, which has revolutionized the “old-fashion” C++98 in many aspects such as meta-programming, concurrency controls, and functional programming. Despite the tremendous progress in language innovation, research on how these advanced features can improve EDA programs is still nascent. In this paper, we introduce a novel routing framework using the technique of generalized constant expression in C++17. Our framework allows a router to take advantage of compile-time computation and thus can save a significant amount of engineering effort that would otherwise be issued every time the program runs. By prescribing computation at compile time, the compiler is able to further produce more optimized codes to run faster than ever before. We have evaluated our framework on classic routing problems and have demonstrated promising performance gain over which is done solely at runtime. Our framework has the potential to change many fundamental EDA building blocks and thus can achieve better tool performance and engineering productivity.

The Internet of Things (IoT) and cloud computing rely on strong confidence in security of confidential or highly privacy sensitive data. Therefore, side-channel leakage is an important threat, but countermeasures require expert-level security knowledge for efficient application, limiting adoption. This work addresses this need by presenting the first High-Level Synthesis (HLS) flow with primary focus on side-channel leakage reduction. Minimal security annotation to the high-level C-code is sufficient to perform automatic analysis of security critical operations with corresponding insertion of countermeasures. Additionally, imbalanced branches are detected and corrected. For practicality, the flow can meet both resource and information leakage constraints. The presented flow is extensively evaluated on established HLS benchmarks and a general IoT benchmark. Under identical resource constraints, leakage is reduced between 32% and 72% compared to the reference. Under leakage target, the constraints are achieved with 31% to 81% less resource overhead.

As the technology advances to 14/10 nm technology nodes and beyond, multiple patterning lithography (MPL) is no longer an option but a necessity. For advanced technology nodes, process variations have significant influences on the quality of fabricated circuits, and often lead to unexpected power/timing degenerations. For example, a 6 nm misalignment causes a 15% error in coupling capacitance and a 5% error on total capacitance, whereas a 2 nm displacement creates approximately a 5% error for coupling capacitance and 2% error for total capacitance [1]. Mask misalignment would increase the coupling capacitance for a given layout and further complicate the way of simulating timing closure. In this paper, we studied the coupling capacitance variations due to mask misalignment in MPL, and mathematically proved that worst case coupling capacitance scenarios for all MPL decompositions. Our algorithm is able to identify a decomposition with a tight upper bound on the worst case coupling capacitance, which can be used in timing/power analysis. Our approach is expected to help the engineers to quickly evaluate the quality of different decompositions, and better understand the pros and cons brought by MPL decompositions.

Multiple patterning lithography has been widely adopted for today's circuit manufacturing. However, increasing the number of masks will make the manufacturing process more expensive. More importantly, towards 7 nm technology node, the accumulated overlay in multiple patterning will cause unacceptable edge placement error (EPE). Recently, directed self-assembly (DSA) has been shown to be an effective lithography technology that can pattern contact/via/cuts with high throughput and low cost. DSA is currently aiming at 7 nm technology, where the guiding template generation needs either double patterning EUV or multiple patterning DUV process. By incorporating DSA into the multiple patterning process, it is possible to reduce the number of masks and achieve a cost effective solution. In this paper, we study the decomposition problem for contact layer in row-based standard cell layout with DSA-MP complementary lithography. We explore several heuristic-based approaches, and propose an algorithm that decomposes a standard cell row optimally in polynomial-time. Our experiments show that our algorithm guarantees to find a minimum cost solution if one exists, while the heuristic cannot or only finds a sub-optimal solution. Our results show that the DSA-MP complementary approach is very promising for the future advanced nodes.

Incremental path-based timing analysis (PBA) is a pivotal step in the timing optimization flow. A core building block analyzes the timing path-by-path subject to a critical amount of incremental changes on the design. However, this process in nature demands an extremely high computational complexity and has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable algorithm of incremental PBA with MapReduce – a recently popular programming paradigm in big-data era. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can not only easily analyze huge deisgns in a few minutes, but also quickly revalidate the timing after the incremental changes. Our results are beneficial for speeding up the lengthy design cycle of timing closure.

Directed Self-Assembly (DSA) is a promising technique for contacts/vias patterning in 7 nm technology nodes. In DSA process, groups of contact holes/vias are generated by the self-assembly process guided by the ‘guiding templates’. The guiding templates are patterned by conventional optical lithography process such as 193 nm immersion lithography. As a result, the patterning fidelity and variation in the template shapes is very likely to affect the final contact holes/vias. While feasible in principle, rigorous DSA process simulation is unacceptably slow for full chip verification in practice. This paper proposes a machine learning based verification that can predict the pitch size of the contact holes and the hole centers. Given a set of training data that consists of simulated template and contact hole patterns, our method is able to learn a highly accurate predictive model for pitch size and hole location. To build a statistical model for prediction, we utilize computer vision techniques to extract various geometric and image features. We conduct extensive experiments to explore the effectiveness of the proposed features, and compare several machine learning algorithms to achieve an effective and efficient prediction. The experimental results show that compared to the minutes or even hours of simulation time in rigorous methods, our best prediction model achieves very promising results (RMSE = 0.135 pitch grid) with less than one second of training and predicting runtime overhead.

Electron beam lithography (EBL) is a very promising candidate for integrated circuit (IC) fabrication beyond the 10 nm technology node. To address its throughput issue, the Character Projection (CP) technique has been proposed, and its stencil planning can be optimized with aware of overlapping characters. However, the top level 2D stencil planning problem has been proved to be an NP-hard problem. As its most essential step, the 1D row ordering is believed hard as well, and no polynomial time optimal solution has been provided so far. In this paper, we propose a polynomial time optimal algorithm to solve the row ordering problem, which serves as the major subroutine for the entire stencil planning problem. Proof and experimental results are also provided to verify the correctness and efficiency of our algorithm.

IR-drop values of power grid can be reduced through inserting on-chip low-dropout voltage regulators (LDO). In this paper, we explore the optimization of LDOs to meet the IR-drop constraint, where the maximum IR-drop value is less than 10% of power supply. With Cholesky direct solver and SPICE, we propose a method to simulate power grid with LDOs. Based on the simulation method, we develop an efficient flow to optimize the number and locations of the LDOs. Effectiveness of the proposed method is verified by the experimental results. To the best of our knowledge, this is the first work optimizing the number and locations of LDOs to meet the IR-drop constraint.

Physically Unclonable Functions (PUFs) are used to provide identification, authentication and secret key generation based on unique and unpredictable physical characteristics. Carbon Nanotube Field Effect Transistors (CNFETs) were shown to have excellent electrical and unique physical characteristics and are promising candidates to replace silicon transistors in future Very Large Scale Integration (VLSI) designs. We present Carbon Nanotube PUF (CNPUF), the first PUF design that takes advantage of unique CNFET characteristics. CNPUF achieves higher reliability against environmental variations and increased resistance against modeling attacks. Furthermore, CNPUF has a considerable power and energy reduction in comparison to previous ultra-low power PUF designs of 89.6% and 98%, respectively. Additionally, CNPUF allows power-security tradeoff.

This tutorial session presented the nature of the optimization problem challenges in physical synthesis. These are large-scale and highly complex nonlinear, discrete optimization problems. They offer the controls and numerical optimization communities a rich template for research into scalable and highly efficient algorithm.

Summary form only given. The control of signalized intersection plays an important role in the safety and efficiency of urban traffic. The last decades a lot of resources were spent on ITS for the detection of vehicles at traffic lights. Today not only the efficiency of traffic is of interest but also the safety of pedestrians is becoming a priority. To respond to this need two new traffic video sensors are proposed specifically designed for the detection of pedestrians in an urban setting.

In this paper, we propose a novel and efficient iterative method for pad placement optimization of power grid with flip chip technology. Power grid with optimized pad placement has less IR-drop values. We develop a new method to calculate new locations of all pads. Placing pads at the new locations reduces local IR-drop values. In order to reduce global IR-drop values, we develop a graph-based strategy to decide which pads are moved to the new locations. After each movement of the pads, a static IR-drop analysis is performed. We develop multigrid accelerated modified Simulated Annealing method (MG_SA) and compare it with the proposed method on a set of test cases. Experimental results show that the proposed method outperforms MG_SA with similar or less IR-drop values and much less runtime.

Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm.

Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board.

Due to the absence of defect-free blanks in extreme ultraviolet (EUV) lithography, defect mitigation is necessary before mass production. One effective defect mitigation approach is to cover defects by device features, such that the defects will no longer be printable. Normally die size is much smaller than the exposure field on the blank, such that one blank can accommodate multiple copies of a die, each of which can be placed independently within the exposure field. For thorough utilization of blank area, the number of valid dies that are not impacted by any defects should be maximized. To do so, all relocation positions to place a single valid die on a defective blank must be determined first [1]. To the best of our knowledge, no existing work can find all relocation positions throughout the whole blank in a reasonable amount of time. In this paper, we develop an efficient algorithm to solve this problem. The time complexity of our algorithm is linear in the number of features in the die. Experimental results with full die layouts generated from a standard cell library validate the efficiency of our algorithm. Comparing to the algorithm in [2] which runs more than one week without termination, our algorithm only takes several hours to find all relocation positions for a die with millions of features.

Conventional CMOS devices are facing an increasing number of challenges as the feature sizes scale down. In the meantime, new nanoscale materials, like graphene nanoribbons (GNR), have been shown to have large integration capability, and thus will probably replace CMOS devices in the future. However, in practice, the GNR wire segments can have a connection defective rate. Particularly, each wire segment has a survival probability, and thus has a chance to fail. This makes the routing in traditional ways very unreliable. In this paper, we study the routing reliability problem and propose an algorithm flow to solve it. Given a s-t routing path on a routing graph, we try to reinforce the reliability of the routing path by adding redundant wiring segments in such a way that its survival probability is maximized with a reasonable overhead of routing resources. Our proposed algorithm flow is two-fold: (1) generation of candidate redundancy segment via min-cost max-flow; (2) optimal selection among the candidates by dynamic programming. The results of extensive experiments confirm the effectiveness and efficiency of our approach.

3D IC, a novel packaging technology, is heavily studied to realize improved performance with denser packaging and reduced wirelength. Despite numerous advantages, thermal management is the biggest bottleneck to realize device stacking technology. In this paper, we propose a thermal-aware physical design for three-dimensional integrated circuits (3D IC). We aim to mitigate localized hotspots to ensure functionality by adding thermal fin geometry to existing thermal through silicon via (TTSV). We analyze various ways to insert thermal fin for single TTSV as well as TTSV cluster designs with the goal of maximizing heat dissipation while minimizing the interference with routing and area consumption. An analytical model of a three-dimensional system is developed and a thermal resistance circuit is built for accurate and time-efficient 3D thermal analysis.

R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30× speedup on R-tree query and more than 20× speedup on R-tree construction are achieved.

Blank defect mitigation is a critical step for extreme ultraviolet (EUV) lithography. Targeting the defective blank, a layout relocation method, to shift and rotate the whole layout pattern to a proper position, has been proved to be an effective way to reduce defect impact. Yet, there is still no published work about how to find the best pattern location to minimize the impact from the buried defects with reasonable defect model and considerable process variation control. In this paper, we successfully present an algorithm that can optimally solve this pattern relocation problem. Experimental results validate our method, and the relocation results with full scale layouts generated from Nangate Open Cell Library has shown great advantages with competitive runtimes compared to the existing commercial tool.

Since some of major IC industry participants are moving to the highly regular 1D gridded designs to enable scaling to sub-20nm nodes, how to manufacture the randomly distributed cuts with reasonable throughput and process variation becomes a big challenge. With the help of hybrid lithography, people can apply different types of processes for one single layer manufacturing such that the advantages from different technologies can be combined together to further benefit manufacturing. In this paper, targeting cut printing difficulties and hybrid lithography with electron beam (E-Beam) and 193 nm immersion (193i) processes, we propose a novel algorithm to optimally assign cuts to 193i or E-Beam processes with proper modifications on cut distribution, in order to maximize the overall throughput. To validate our method, we construct our algorithm based on the forbidden patterns obtained from the optical simulation; then we formulate the redistribution problem into a well defined ILP problem and finally call a reliable solver to solve the whole problem. Experimental results show that the throughput is dramatically improved by the cut redistribution. Besides that, for sparser layers, the EBL process can be totaly saved, which largely reduces the fabrication cost.

As advances in process technology continue to scale down transistors, low power design is becoming more critical. Clock gating is a dynamic power saving technique that can freeze some flip-flops and prevent portion of the circuit from unneeded switching. In this paper, we consider fine-grained clock gating through pipelining, in which control signals from one pipeline stage are used to freeze some logic in the next pipeline stage. We present a novel BDD-based decomposition algorithm to restructure the circuit and expose possible control signals that would maximize power saving. We then use ILP formulation to select the optimal set of control signals for the circuit. We show that the constraint matrix is totally unimodular, and solve this selection problem optimally using linear programming. Comparing to a previous work [7], we get similar and 9% better dynamic power saving for small and medium circuits, respectively. For the largest MCNC circuits, which the previous technique cannot handle, we get an average of 19% dynamic power saving with 9.3% area overhead comparing to the original, non-restructured circuits.

The negotiated congestion based routing scheme finds success in FPGA routing and IC global routing. However, its application in simultaneous escape routing, a key problem in PCB design, has never been reported in previous literature. In this paper, we investigate how well the negotiated congestion based router performs on escape routing problems. We propose an underlying routing graph which correctly models the routing resources of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compare the performance of NCER with that of Cadence PCB router Allegro on 14 industrial test cases, and experimental results show that the two routers have comparable routability: each of them completely routes 7 test cases. Moreover, we observe that NCER and Allegro exhibit complementary behaviors: each is able to solve most of the test cases that the other cannot solve. Together, they completely route 11 test cases. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of escape routing problems.

Due to the extremely large sizes of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. In order to design scalable algorithms to handle ever increasing power-grid sizes, the most promising approach is to use a “divide-and-conquer” strategy such as domain decomposition. Such an approach not only decomposes a large problem into manageable sub-problems, it also naturally allow a parallel processing solution for further speedup in computation time. As a result, a power-grid analysis algorithm based upon the traditional domain decomposition method has been reported in [9]. Unfortunately, the method in [9] has strong limitation on the size of the interfaces between the sub-problems and therefore severely limits its capability in solving very large problems. In this paper, we present a block-iterative domain-decomposition algorithm which effectively combines the advantages of direct solvers and iterative methods. With a carefully chosen domain decomposition strategy, our approach does not suffer from the difficulties of [9]. While the algorithm in [9] fails to analyze a power grid of 4 millions nodes, our algorithm solves a power grid of 42 millions nodes accurately in 1.5 hours.