Search

Since the first release in 2015, OpenTimer v1 has been used in many industrial and academic projects for analyzing the timing of custom designs. After four-year research and developments, we have announced OpenTimer v2—a major release that efficiently supports: 1) a new task-based parallel incremental timing analysis engine to break through the performance bottleneck of existing loop-based methods; 2) a new application programming interface (API) concept to exploit high degrees of parallelisms; and 3) an enhanced support for industry-standard design formats to improve user experience. Compared with OpenTimer v1, we rearchitect v2 with a modern C++ programming language and advanced parallel computing techniques to largely improve the tool performance and usability. For a particular example, OpenTimer v2 achieved up to $5.33\times $ speedup over v1 in incremental timing, and scaled higher with increasing cores. Our contributions include both technical innovations and engineering knowledge that are open and accessible to promote timing research in the community.

Recent years have seen rapid growth in data-driven distributed systems, such as Hadoop MapReduce, Spark, and Dryad. However, the counterparts for high-performance or compute-intensive applications including large-scale optimizations, modeling, and simulations are still nascent. In this paper, we introduce DtCraft, a modern C++ based distributed execution engine to streamline the development of high-performance parallel applications. Users need no understanding of distributed computing and can focus on high-level developments, leaving difficult details, such as concurrency controls, workload distribution, and fault tolerance handled by our system transparently. We have evaluated DtCraft on both micro-benchmarks and large-scale optimization problems, and shown the promising performance from single multicore machines to clusters of computers. In a particular semiconductor design problem, we achieved ${30\times }$ speedup with 40 nodes and ${15\times }$ less development efforts over hand-crafted implementation.

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.

Open source has started energizing both industrial and academic research and development in electronic design automation (EDA) systems. By moving to open source, we can speed up our effort and work with others who are working toward the same goals, while reducing costs and improving end products. However, building an open-source project is much more than placing the codebase on the web. In this paper, we will talk about essential building blocks to create an impactful open-source project, including source repository, project landing page, documentation, and continuous integration. We will also cover the use of web-based frameworks to design a showcase project to bring community's attention. We will then share our experience in developing an open-source timing analyzer (OpenTimer) and a parallel task programming library (Cpp-Taskflow), both of which are being used in many industrial and academic EDA research projects.

Physically unclonable functions (PUFs) provide a device-unique challenge–response mapping and are employed for authentication and encryption purposes. Unpredictability and reliability are the core requirements of PUFs: unpredictability implies that an adversary cannot sufficiently predict future responses from previous observations. Reliability is important as it increases the reproducibility of PUF responses and hence allows validation of expected responses. However, advanced machine-learning algorithms have been shown to be a significant threat to the practical validity of PUFs, as they are able to accurately model PUF behavior. The most effective technique was shown to be the XOR-based combination of multiple PUFs, but as this approach drastically reduces reliability, it does not scale well against software-based machine-learning attacks. In this paper, we analyze threats to PUF security and propose PolyPUF, a scalable and secure architecture to introduce polymorphic PUF behavior. This architecture significantly increases model-building resistivity while maintaining reliability. An extensive experimental evaluation and comparison demonstrate that the PolyPUF architecture can secure various PUF configurations and is the only evaluated approach to withstand highly complex neural network machine-learning attacks. Furthermore, we show that PolyPUF consumes less energy and has less implementation overhead in comparison to lightweight reference architectures.

In this paper we present DtCraft, a distributed execution engine that enables a new powerful programming model to streamline cluster computing. Applications are described in a set of data-parallel streams, leaving difficult execution details and concurrency controls handled by our system kernel transparently. Compared with existing systems, DtCraft is unique in (1) an efficient stream-oriented programming paradigm using modern C++17, (2) an in-context resource controller and task executor based on Linux container technology, and (3) ease of development from prototyping machines to production cloud environments. These capabilities power industry applications and create new research directions in machine learning, stream processing, and distributed multimedia systems.

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.

Given ever-increasing circuit complexities, recent trends are driving the requirement for distributed timing analysis (DTA) in electronic design automation (EDA) tools. However, DTA has received little research attention so far and remains a critical problem. In this paper, we introduce a DTA framework for large designs. Our framework supports (1) general design partitions in distributed file systems, (2) non-blocking IO with event-driven loop for effective communication and computation overlap, and (3) an efficient messaging interface between application and network layers. The effectiveness and scalability of our framework has been evaluated on large hierarchical industry designs over a cluster with hundreds of machines.

Emerging technologies such as the Internet of Things (IoT) heavily rely on hardware security for data and privacy protection. However, constantly increasing integration complexity requires automatic synthesis to maintain the pace of innovation. We introduce the first High-Level Synthesis (HLS) flow that produces a security enhanced hardware design to directly prevent Hardware Trojan Horse (HTH) injection by a malicious foundry. Through analysis of entropy loss and criticality decay, the presented algorithms implement highly efficient resource-targeted information dispersion to counter HTH insertion. The flow is evaluated on existing HLS benchmarks and a new IoT-specific benchmark and shows significant resource savings.

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.

Escape routing for packages and printed circuit boards (PCBs) has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

The increasing complexity of electronic systems has made PCB routing a difficult problem. A large amount of research effort has been dedicated to the study of this problem. In this paper, we provide an overview of recent research results on the PCB routing problem. We focus on the escape routing problem and the length-matching routing problem, which are the two most important problems in PCB routing. Other relevant works are also briefly introduced.

With the thermal effect, improper analog placements may degrade circuit performance because the thermal impact from power devices can affect electrical characteristics of the thermally-sensitive devices. There is not much previous work that considers the desired placement configuration between power and thermally-sensitive devices for a better thermal profile to reduce the thermally-induced mismatches. This paper first introduces the properties of a desired thermal profile for better thermal matching of the matched devices. It then presents a thermal-driven analog placement methodology to achieve the desired thermal profile and to consider the best device matching under the thermal profile while satisfying the symmetry and the common-centroid constraints. Experimental results based on real analog circuits show that the proposed approach can achieve the best analog circuit performance/accuracy with the least impact due to the thermal gradient, among existing works.

Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

Design for low power has become a key requirement in today's System-on-a-Chip design, particularly for mobile applications. Multi-Vdd (MSV) is an effective method to reduce both leakage and dynamic powers. In a MSV design, cells of different supply voltages are often grouped into a small number of voltage islands, in order to avoid complex power-supply system and excessive amount of level shifters. In 2005, Wu et al proposed an elegant algorithm for voltage-island grouping based on the physical proximity of the critical cells in a postplacement voltage assignment and, in 2006, proposed an efficient algorithm for voltage assignment which not only meets timing but also forms good proximity of the critical cells. However, due to insufficient slack, a few isolated critical cells (called outliers) may still exist in the resulting voltage assignment, causing disproportionately expensive penalty to the final voltage-island grouping. In this paper, we propose a novel approach to improve the voltage assignment by automatic outlier detection followed by incremental placement. The outlier detection is based on a modified algorithm for the facility-location problem and proper parameter setting. We also propose a novel partial-sort technique which speeds up this algorithm significantly (up to 3times in our experiments). The incremental placement is guided by setting proper constraints on the paths containing the detected outliers, such that the outliers can be eliminated later. Our experiments on industry designs show that our algorithm leads to 12%-54% improvement in the final voltage-island grouping, with quick turn-around time.

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask-layout uniformity/evenness is highly desired, and it is usually measured by the feature densities within defined feasible ranges determined by the manufacturing-process design rules. To address the density-control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum/minimum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/long hours to a few minutes/seconds. Moreover, it is even faster than the existing approximate algorithms in the literature.

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.

High power consumption not only leads to short battery life for hand-held devices but also causes on-chip thermal and reliability problems in general. As power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. Multi-supply voltage (MSV) has previously been introduced to provide finer grain power and performance tradeoff. In this paper, we propose a methodology on top of a set of algorithms to exploit nontrivial voltage island boundaries for optimal power versus design-cost tradeoff under performance requirement. Our algorithms are efficient, robust, and error-bounded and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. Our experiment on real industry designs shows a tenfold improvement of our method over current logical-boundary-based industry approach.

Recently, block copolymer directed self-assembly (DSA) has demonstrated great advantages in patterning contacts/vias for the 7 nm technology node and beyond. The high throughput and low process cost of DSA makes it the most promising candidate in patterning tight pitched dense patterns for the next generation lithography. Since DSA is very sensitive to the shapes and distributions of the guiding templates, it is necessary to develop new EDA algorithms and tools to address the patterning rules and constraints of the process. This paper presents a set of DSA-aware optimization techniques targeting the most urgent problems for DSA technology, including layout optimization and template pattern verification.

Input-output (I/O) placement has always been a concern in modern integrated circuit design. Due to flip-chip technology, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints in design cost (DC) and performance, I/O buffer planning becomes a pressing problem. During the early stages of circuits and package co-design, I/O layout should be evaluated to optimize DC and to avoid product failures. The objective of this brief is to improve the existing/initial standard cell placement by I/O clustering, considering DC reduction and signal integrity preservation. The authors formulate it as a minimum cost flow problem that minimizes alphaW+betaD, where W is the I/O wirelength of the placement and D is the total voltage drop in the power network and, at the same time, reduces the number of I/O buffer blocks. The experimental results on some Microelectronics Center of North Carolina benchmarks show that the author's method averagely achieves better timing performance and over 32% DC reduction when compared with a conventional rule-of-thumb design that is popularly used by circuit designers

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good for meeting other objectives such as minimizing the total wire length, which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. This paper first shows that the problem can be formulated by linear programming. Thereafter, instead of using the general, but slow, linear programming, this paper proposes an efficient minimum-cost flow-based approach to solve it. This approach guarantees to obtain the minimum total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. This paper also shows that the approach can be easily extended to handle constraints such as fixed frame (fixed area), input-output (IO) pins, preplaced blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient that it finishes in less than 0.4 s for all Microelectronics Center of North Carolina (MCNC) benchmarks of block placement. It is also very effective. Experimental results show that the wire length of very compact floorplans can even be improved by 4.2%. Thus, it provides an ideal way for postfloorplanning refinement

Engineering change order changes are almost inevitable in the late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of redoing the whole process and can minimize the disturbance on the existing converged design. The coupling-capacitance violation elimination (CVE) problem is addressed. Due to the changes in the multiple layer routing design, the total coupling capacitance on some signal wire segments on a layer may be larger than their allowable bounds after postlayout timing/noise analysis. The target is to find a new routing solution without coupling-capacitance violations under certain constraints, which helps to keep the new design close to the original one. This paper proposes a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of this algorithm

Dramatic rises in the power consumption and integration density of contemporary systems-on-chip (SoCs) have led to the need for careful attention to chip-level thermal integrity. High temperatures or uneven temperature distributions may result not only in reliability issues, but also timing failures, due to the temperature-dependent nature of chip time-to-failure and delay, respectively. To resolve these issues, high-quality, accurate thermal modeling and analysis, and thermally oriented placement optimizations, are essential prior to tapeout. This paper first presents an overview of thermal modeling and simulation methods, such as finite-difference time domain, finite element, model reduction, random walk, and Green-function based algorithms, that are appropriate for use in placement algorithms. Next, two-dimensional and three-dimensional thermal-aware placement algorithms such as matrix-synthesis, simulated annealing, partition-driven, and force directed are presented. Finally, future trends and challenges are described

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints any more. In this paper, the authors focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing, and use those resources for length extension afterwards. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are shown to be scalable for large circuits, since the respective time complexities are O(A) and O(AlogA), where A is the area of the intermediate region between chips.

With today's advanced integrated circuit manufacturing technology in deep submicron (DSM) environment, we can integrate entire electronic systems on a single system on a chip. However, without careful power supply planning in layout, the design of chips will suffer from local hot spots, insufficient power supply, and signal integrity problems. Postfloorplanning or postroute methodologies in solving power delivery and signal integrity problems have been applied but they will cause a long turnaround time, which adds costly delays to time-to-market. In this paper, we study the problem of simultaneous power supply planning and noise avoidance as early as in the floorplanning stage. We show that the problem of simultaneous power supply planning and noise avoidance can be formulated as a constrained maximum flow problem and present an efficient yet effective heuristic to handle the problem. Experimental results are encouraging. With a slight increase of total wirelength, we achieve almost no static IR (voltage)-drop requirement violation in meeting the current and power demand requirement imposed by the circuit blocks compared with a traditional floorplanner and 45.7% of improvement on a /spl Delta/I noise constraint violation compared with the approach that only considers power supply planning.

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.

Manufacturability of a design that is processed with shallow-trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish for which all previous studies on dummy-feature placement for single-material polish by Kahng et al. (1999), Tian et al. (2000), and Chen et al. (2000) are not applicable. Based on recent semiphysical models of polish-pad bending by Ouma et al (1998), local polish-pad compression by Grillaert (1999) and Smith (1999), and different polish rates for materials present in a dual-material polish by Grillaert (1999) and Tugbawa et al. (1999), this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy-feature placement for CMP in STI is given as a nonlinear-programming problem. An iterative approach is proposed to solve the dummy-feature placement problem. Computational experience on four layouts from Motorola is given.

Embedded systems continue to provide the core for a wide range of applications, from smart-cards for mobile payment to smart-meters for power-grids. The resource and power dependency of embedded systems continues to be a challenge for state-of-the-art security practices. Moreover, even theoretically secure algorithms are often vulnerable in their implementation. With decreasing cost and complexity, physical attacks are an increasingly important threat. This threat led to the development of Physically Unclonable Functions (PUFs) which are disordered physical systems with various applications in hardware security. However, consistent security oriented design of embedded systems remains a challenge, as most formalizations and security models are concerned with isolated physical components or high-level concept. We provide four unique contributions: (i) We propose a system-level security model to overcome the chasm between secure components and requirements of high-level protocols; this enables synergy between component-oriented security formalizations and theoretically proven protocols. (ii) An analysis of current practices in PUF protocols using the proposed system-level security model; we identify significant issues and expose assumptions that require costly security techniques. (iii) A System-of-PUF (SoP) that utilizes the large PUF design-space to achieve security requirements with minimal resource utilization; SoP requires 64% less gate-equivalent units than recently published schemes. (iv) A multilevel authentication protocol based on SoP which is validated using our system-level security model and which overcomes current vulnerabilities. Furthermore, this protocol offers breach recognition and recovery.

In detailed routing for integrated circuit (IC) designs, vias are usually randomly inserted in order to connect between di erent routing layers. In the 7 nm technology node and beyond, the wire pitch is below 40 nm, and consequently, the vias become very dense, making via layer printing a challenging problem. Recently block copolymer directed self-assembly (DSA) technology has demonstrated great advantages for via layer patterning using guiding templates. To pattern vias with DSA process, guiding templates are usually printed rst with conventional lithography, e:g:, 193 nm immersion lithography (193i) that has a coarser pitch resolution. Then the guiding templates will guide the placement of the DSA patterns (e:g:, vias) inside, and these patterns have a ner resolution than the templates. Di erent template shapes have di erent control on the overlay accuracy of the inside vias. By performing DSA experiments, the guiding templates can be classi ed as feasible and infeasible templates according to the overlay requirement of the technology node. The templates that meet the overlay requirement are feasible templates, and other templates are infeasible. Without considering the DSA template constraints in detailed routing, randomly distributed vias may require infeasible templates to be patterned, which makes the via layers incompatible with the DSA process. In this paper, we propose a DSA-aware detail routing algorithm to optimize the via layers such that only feasible templates are needed for via layer patterning. In addition, among all the feasible templates, the one with better overlay accuracy has higher priority to be picked up by the router for via patterning, which further improves the yield. By enabling DSA process for via layer patterning in the 7 nm technology node, the proposed detailed routing strategy tremendously reduces the manufacturing cost and improves the throughput for IC fabrication.

In floorplanning, it is common that a designer wants to have certain modules abutting with one another in the final packing. The problem of controlling the relative positions of an arbitrary number of modules in floorplan design is nontrivial. Slicing floorplan has an advantageous feature in which the topological structure of the packing can be found without knowing the module dimensions. This feature is good for handling placement constraints in general. In this paper, we make use of it to solve the abutment problem in the presence of L- and T-shaped modules. This is done by a procedure which explores the topological structure of the packing and finds the neighborhood relationship between every pair of modules in linear time. Our main contribution is a method that can handle abutment constraints in the presence of L- or T-shaped modules in such a way that the shape flexibility of the soft modules can still be fully exploited to obtain a tight packing. We tested our floorplanner with some benchmark data and the results are promising.

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.

With the minimum feature size keeps shrinking, there are increasing difficulties to print these small features using one exposure (LE) or double exposures (LELE). To resolve the inherent physical limitations for current lithography techniques, triple patterning lithography (LELELE) has been widely recognized as one the most promising options for 14/10nm technology node. For triple patterning lithography (TPL), the designers are more interested in finding a decomposition with none of the three masks overwhelms the other. This color balancing issue is of crucial importance to ensure that consistent and reliable printing qualities can be achieved. In our previous work,18 a simple color balancing scheme is proposed to handle designed without stitches, which is not capable of handling complex designs with stitches. In this paper, we further extend the previous approach to be able to simultaneously optimizing the number of stitches and balancing the color usage in the three masks. This new approach is very efficient and robust, and guarantees to find a color balancing decomposition while achieving the optimal number of stitches. For the largest benchmark with over 10 million features, experimental results show that the new approach achieves almost perfect color balancing with reasonable runtime.

Directed self-assembly (DSA) technology has already demonstrated its capability for isolated and grouped contact/via pattern for 1D gridded design. If we reverse the resist tune, this technique can also be used to implement the cut printing. However, for this purpose, we need to redistribe the cuts by extending the real wires to form the desired cut distribution for template mask making. Based on this assumption, we propose an algorithm to redistribute the original cuts such that they form groups of non-conflict DSA templates. Experimental results demonstrate that our method can effectively redistribute the cuts and improve the layout manufacturability.

Self-aligned double patterning (SADP) lithography is a leading technology for 10nm node Metal layer fabrication. In order to achieve successful decomposition, SADP-compliant design becomes a necessity. Spacer-Is-Dielectric (SID) is the most popular flavor of SADP with higher flexibility in design. This paper makes a careful study on the challenges for SID-compliant detailed routing and proposes a graph model to capture the decomposition violations and SID intrinsic residue issues. Then a negotiated congestion based scheme is adopted to solve the overall routing problem. The proposed SID-compliant detailed routing algorithm simultaneously assigns colors to the routed wires, which provides valuable information guiding SID decomposition. In addition, if one pin has multiple candidate locations, the optimal one will be automatically determined during detailed routing. The decomposability of the conflict-free routing layers produced by our detailed router is verified by a commercial SADP decomposition tool.

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.

Extreme ultraviolet lithography (EUVL) is a leading candidate for next generation lithography (NGL). At 11nm technology node, the size of the minimum printable multi-layer (ML) mask defect is as small as 20nm. As a result, it is extremely difficult to produce defect-free ML mask blanks. Instead, by allowing a certain number of printable defects on the blank, the EUVL cost of ownership can be tremendously reduced. However, those printable blank defects must be mitigated later in the mask fabrication process in order not to sacrifice yield. One effective defect mitigation approach is to cover the defects by device patterns, such that the defects will no longer be printable. However, there can be billions of device patterns in one single layer which have to be shifted together within a certain margin due to the exposure alignment requirement. Thus an efficient way to cover all defects simultaneously via global device pattern shifting is sorely needed. In addition, it is very difficult to measure the position of each defect accurately with the current blank inspection tool, so the defect position inaccuracy has to be taken into consideration at the same time. This paper formulates the blank defect coverage problem into a rectilinear polygon shrinking and intersection problem and develops a highly efficient algorithm whose time complexity is linear with respect to the density of device patterns. In addition, within the shift margin there are usually multiple positions to locate a layout on a defective blank where all defects are simultaneously covered by the device patterns; our algorithm is able to report the optimal layout location with the maximum tolerance for the inspection inaccuracy.

Blank defect mitigation is crucial for extreme ultraviolet (EUV) lithography. One of the existing options is to relocate patterns to avoid defect impact. However, when the defect number increases, only pattern shift in X-Y directions becomes far from enough, requiring the reticle holder rotate a small angle to provide a third exploring dimension. This non-trivial extension from 2D to 3D exploration requests efficient runtime as well as enough accuracy to handle different defect sizes and locations on the different features. In this paper, we present the first work with a detailed algorithm to find the optimal shift and rotation for layout patterns on blanks. Compared to the straightforward method, which is to check every pair of defect and feature at every possible relocation position, our proposed algorithm can significantly reduce the runtime complexity to scale linearly with the size of the full solution space. The experimental results validate our method and show a largely increased success rate of defect mitigation by shift and rotation.

Due to the rapid advances of integrated circuit technology, the size of power distribution network (power grid) is becoming larger and larger. There are usually multi-million nodes on a power grid. Analyzing these huge power grids has become very expensive in terms of both time and memory. This paper presents an efficient parallel implementation of the Additive Schwarz Method (ASM) for IR-drop analysis of large-scale power grid. Based on distributed memory system, a new data storage method is proposed to overcome memory bottleneck of traditional methods. Techniques including overlapping in multiple layer and irregular power grid, via detection and grouping are utilized to accelerate the simulation. Moreover, a new communication strategy exhibiting minimum communication overhead is proposed. The proposed method is very accurate in the final solution, with the maximum error less than 0.1mv. Experimental results on industrial medium size benchmarks show that the proposed method achieves more than 110X speedup over a state-of-the-art direct LU solver. The proposed approach can easily solve very large-scale benchmarks, while LU solver fails to obtain the solution because of system memory limitation. It is the first time reported in literature that IR-drop analysis of power grid with over 190M nodes is successfully solved within 5 minutes.

In this paper, we propose PGT_SOLVER - an effecient solver for power grid transient analysis. It is based on direct solver. The conductance matrix is SPD and is generated by modifying the matrix for DC analysis. Modified sparse vector technique is proposed to obtain solutions of interested nodes by performing partial forward and backward substitutions. Smart mapping technique is presented to obtain correct solutions without reordering the right-hand-side vector. Moreover, memorized supernode technique is utilized to speed up the substitution process. A effortless but effective parallel strategy with multiple threads is introduced to further accelerate the simulation. This software won the 1st place at "TAU 2012 Power Grid Simulation Contest". Experimental results on several industrial benchmarks show that this solver can get solutions fast without introducing any error. The memory consumption is also very affordable.

As technology continues to scale to 14nm node, Double Patterning Lithography (DPL) is pushed to near its limit. Triple Patterning Lithography (TPL) is a considerable and natural extension along the paradigm of DPL. With an extra mask to accommodate the features, TPL can be used to eliminate the unresolvable conflicts and minimize the number of stitches, which are pervasive in DPL process, and thus smoothen the layout decomposition step. Considering TPL during routing stage explores a larger solution space and can further improve the layout decomposability. In this paper, we propose the first triple patterning aware detailed routing scheme, and compare its performance with the double patterning version in 14nm node. Experimental results show that, using TPL, the conflicts can be resolved much more easily and the stitches can be significantly reduced in contrast to DPL.

As the lithography continues to be the biggest challenge in 20 nm technology node, the process windows become a serious concern to handle more severe process variations for better printability and yield. The mask pattern modification that is to set the printing target as the original designed patterns under the best focus, such as OPC and SRAF, becomes insufficient. With the random space and width existing in the low level interconnect layer, a process called "retargeting" to change the original line width or space for better process windows becomes much more important and noticeable. Therefore, a study of retargeting impact on interconnect becomes a must. In this paper, we are focusing on the low level metal layer to demonstrate the retargeting impact on the delay. By the test benches that we build to enumerate all the possible changes during retargeting, we analyze the worst case scenario impact for a worry-free retargeting process. We also successfully generate a compact model to predict the retargeting impact. Experimental results verify our estimation model for the retargeting's impact on the preferred and non-preferred direction, and little error is found for our compact model.

Simulated annealing was first introduced in 1983 as a generic stochastic algorithmic approach to solve optimization problems. Prof. C. L. Liu and his students H. W. Leong and D. F. Wong were among the earliest EDA researchers who applied simulated annealing to EDA. They solved a wide range of EDA problems with successes and reported their results in a series of papers at premier EDA conferences such DAC and ICCAD. Liu, Leong, and Wong later summarized their works in a research monograph entitled Simulated Annealing for VLSI Design, published in 1988 by Kluwer Academic Publishers. In the Preface of their book, the authors wrote "We hope that our experiences with the techniques we employed, some of which indeed bear certain similarities for different problems, could be useful as hints and guides for other researchers in applying the method to the solutions of other problems". Indeed, there were "similarities in techniques" among Liu's works that had influenced the design of simulated annealing EDA algorithms in the past 20 some years. To better understand Liu's contributions in simulated annealing, one should note that a typical simulated annealing algorithm uses a solution space and a cost function that come directly with the problem. Although computation time may be high, the algorithm is straightforward to design, making simulated annealing an attractive option for difficult problems where clever algorithms are hard to come by. On the contrary, Liu's simulated annealing algorithms have a completely different style: They resemble clever algorithms that attempt to solve difficult problems in polynomial time, and they often have a strong algorithmic flavor with a significant effort spent on optimizing the solution space and cost function. In this talk, we will discuss Prof. Liu's pioneering contributions in simulated annealing for EDA.

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.

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.