Search

Flow-based microfluidic biochips are attracting increasing attention with successful applications in biochemical experiments, point-of-care diagnosis, etc. Existing works in design automation consider the flow-layer design and control-layer design separately, lacking a global optimization and hence resulting in degraded routability and reliability. This paper presents a novel integrated physical co-design methodology, which seamlessly integrates the flow-layer and control-layer design stages. In the flow-layer design stage, a sequence-pair-based placement method is presented, which allows for an iterative placement refinement based on routing feedbacks. In the control-layer design stage, the minimum cost flow formulation is adopted to further improve the routability. Besides that, effective placement adjustment strategies are proposed to iteratively enhance the solution quality of the overall control-layer design. Experimental results show that compared with the existing work, the proposed design flow obtains an average reduction of 40.44% in flow-channel crossings, 31.95% in total chip area, and 22.02% in total flow-channel length. Moreover, all the valves are successfully routed in the control-layer design stage. [ABSTRACT FROM PUBLISHER]

Analog CMOS integrated circuits (ICs) designs depend typically on designer knowledge and experience, as such problems are multivariate and multiobjective, presenting many combinations of input variables to be investigated in order to meet the required specifications. Nowadays, the a posteriori approach is widely used to perform the optimization processes of analog CMOS ICs using evolutionary algorithms. However, these techniques are not totally able to explore potential solutions in specific regions of the Pareto front. Designers then have difficulty in choosing the best solution capable of achieving all desired specifications simultaneously among all the ones found. In this context, the a priori approach using fitness functions has become an important alternative method to overcome these issues of the a posteriori methodology. This paper aims to compare different fitness function profiles used in the a priori optimization processes to boost the effectiveness of the search processes in relation to robustness, accuracy, and yield in analog CMOS ICs designs. We show that the Gaussian profile, proposed here, applied to the lower limit, center value, and upper limit fitness functions is able to improve all the a priori optimization evolutionary techniques investigated, including the genetic, imperialist competitive, and shuffled frog leaping algorithms. [ABSTRACT FROM PUBLISHER]

Neuro-inspired architectures based on synaptic memory arrays have been proposed for on-chip acceleration of weighted sum and weight update in machine/deep learning algorithms. In this paper, we developed NeuroSim, a circuit-level macro model that estimates the area, latency, dynamic energy, and leakage power to facilitate the design space exploration of neuro-inspired architectures with mainstream and emerging device technologies. NeuroSim provides flexible interface and a wide variety of design options at the circuit and device level. Therefore, NeuroSim can be used by neural networks (NNs) as a supporting tool to provide circuit-level performance evaluation. With NeuroSim, an integrated framework can be built with hierarchical organization from the device level (synaptic device properties) to the circuit level (array architectures) and then to the algorithm level (NN topology), enabling instruction-accurate evaluation on the learning accuracy as well as the circuit-level performance metrics at the run-time of online learning. Using multilayer perceptron as a case-study algorithm, we investigated the impact of the “analog” emerging nonvolatile memory (eNVM)’s “nonideal” device properties and benchmarked the tradeoffs between SRAM, digital, and analog eNVM-based architectures for online learning and offline classification. [ABSTRACT FROM AUTHOR]

Current trends in high performance and embedded computing include design of increasingly complex hardware architectures with high parallelism, heterogeneous processing elements, and nonuniform communication resources. In order to take hardware and software design decisions, early evaluations of the system nonfunctional properties are needed. These evaluations of system efficiency require electronic system-level information on both algorithms and architecture. Contrary to algorithm models for which a major body of work has been conducted on defining formal models of computation (MoCs), architecture models from the literature are mostly empirical models from which reproducible experimentation requires the accompanying software. In this paper, a precise definition of a model of architecture (MoA) is proposed that focuses on reproducibility and abstraction and removes the overlap previously existing between the notions of MoA and MoC. A first MoA, called the linear system-level architecture model (LSLA), is presented. To demonstrate the generic nature of the proposed new architecture modeling concepts, we show that the LSLA model can be integrated flexibly with different MoCs. LSLA is then used to model the energy consumption of a state-of-the-art multiprocessor system-on-chip (MPSoC) when running an application described using the synchronous dataflow MoC. A method to automatically learn LSLA model parameters from platform measurements is introduced. Despite the high complexity of the underlying hardware and software, a simple LSLA model is demonstrated to estimate the energy consumption of the MPSoC with a fidelity of 86%. [ABSTRACT FROM AUTHOR]

In this paper, we propose Lagrangian relaxation (LR)-based algorithms to optimize both circuit performance and total wirelength at the global placement stage. We introduce a general timing-driven global placement problem formulation that is applicable to three different circuit design styles: 1) synchronous circuits; 2) synchronous circuits with sequential optimization techniques; and 3) asynchronous circuits. LR is applied to handle the timing constraints of the formulated problem. Based on how the cell spreading constraints are handled, two different approaches are proposed: one approach handles the spreading constraints inside the LR framework and transforms the timing-driven placement (TDP) problem into a series of weighted wirelength minimization problems, which can be solved by directly leveraging existing wirelength-driven placers. The other approach handles the spreading constraints outside the LR framework. Thus, only timing constraints need to be taken care of in the LR framework and better solutions can be expected. In both approaches, we simplified the LR subproblem using Karush–Kuhn–Tucker conditions. Our algorithms are implemented based on a state-of-the-art wirelength-driven quadratic placer. The experiments demonstrate that the proposed algorithms are able to achieve significant improvements on circuit performance compared with a commercial wirelength-driven placement flow and a commercial asynchronous TDP flow. [ABSTRACT FROM PUBLISHER]

This paper explores the use of discrete optimization techniques for variability-aware analog circuit synthesis, with an observation that the continuous design space can be effectively covered by a finite number of discrete points when parameter variation is present. Three algorithms are described that can leverage a discretized design space yet mitigate its dimensionality scaling problem: an isotropic discretization scheme, which can fill the neighborhood of any given point with only quadratically-increasing number of nearest neighbors placed at equal distances as the space dimension increases, a stochastic hill-climbing algorithm, which evaluates only a partial set of nearest neighbors yet finds the local optimum at the reduced cost, and an incremental Monte Carlo sampling algorithm, which draws the minimal number of Monte Carlo samples just enough to determine the superior design point during the local search process. These algorithms help in finding the optimal design of analog circuits efficiently. For instance, for a digitally-controlled oscillator example, its discretized design space consists of 5 565 907 points but the optimal point was found by evaluating only 40 design points and running only 21 Monte Carlo simulations per point in average (824 in total). [ABSTRACT FROM PUBLISHER]

Bit-width allocation has a crucial impact on hardware efficiency and accuracy of fixed-point arithmetic circuits. This paper introduces a new accuracy-guaranteed word-length optimization approach for feed-forward fixed-point designs. This method uses affine arithmetic, which is a well-known analytical technique, for both range and precision analyses. This paper introduces an acceleration technique and two new semianalytical algorithms for precision analysis. While the first algorithm follows a progressive search strategy, the second one uses a tree-shaped search method for fractional width optimization. The algorithms offer two different time-complexity/cost efficiency tradeoffs. The first algorithm has polynomial complexity and achieves comparable results with existing heuristic approaches. The second algorithm has exponential complexity, but it achieves near-optimal results compared to the exhaustive search method. A commonly used set of case studies is used to evaluate the efficiency of the proposed techniques and algorithms in terms of optimization time and hardware cost. The first and second algorithms achieve 10.9% and 13.1% improvements in area, respectively, over uniform fractional width allocation. The proposed acceleration technique reduces the complexity of the fractional width selection problem by an average of 20.3%. [ABSTRACT FROM PUBLISHER]

Functional engineering change order (ECO) is a popular technique for rectifying design errors after synthesis and placement stages. We present a new approach to generating the patch circuits for multierror circuit rectification. In this paper, we propose a two-phase approach of: 1) discovering the functional matches in two circuits followed by 2) determining the final patch circuits from the matches. The ECO engine in this paper discovers functional and structural matches in two circuits by coordinating the SAT-sweeping and the cut-matching algorithms. Then, the patch selection is conducted by the combinational equivalence checking technique and a linear-time selection heuristic. The experimental results on public benchmark and industrial circuits demonstrate that this ECO engine outperforms state-of-the-art interpolation-based engines. [ABSTRACT FROM AUTHOR]

Coarse-grained reconfigurable arrays (CGRAs) are a promising class of architectures conjugating flexibility and efficiency. Devising effective methodologies to map applications onto CGRAs is a challenging task, due to their parallel execution paradigm and constrained hardware resources. In order to handle complex applications, it is important to devise efficient strategies to partition a kernel into pieces that obey resource constraint and methodologies to schedule them on the underlying hardware. In this paper, we tackle these problems by proposing algorithms to address partitioning based on recursive searches over abstract trees. A novel scheduling strategy is also described that, leveraging differences in delays of various operations, is able to efficiently map operations on CGRA architectures. Experimental evidence on kernels derived from a diverse set of data flow graphs and EEMBC benchmarks demonstrate the efficacy of the described methods, which, when combined, achieve a higher runtime performance on a given mesh size than state-of-the-art approaches (as much as 38% for the benchmark applications considered). [ABSTRACT FROM AUTHOR]

IC3 is one of the most successful algorithms for hardware model checking. Since its invention in 2010, several variants of the original algorithm have been published, proposing optimizations and/or alternative procedures for many different steps of the algorithm. In this paper, we present a thorough empirical comparison of a large set of optimizations and procedures for the steps of IC3, considering “high-level” variants/extensions to the basic algorithm, as well as “low-level” optimizations/configuration settings. We implemented each of them in the same tool, optimizing the implementations to the best of our knowledge. This enabled for a flexible experimentation in a controlled environment, and to gain new insights about their most important differences and commonalities, as well as about their performance characteristics. We conducted the experiments using as benchmarks the problems used in the last four editions of the hardware model checking competition. The analysis helped us to identify several settings leading to significant improvements with respect to a basic implementation of IC3. [ABSTRACT FROM AUTHOR]

Secure masking schemes have been proven in theory to be secure countermeasures against side-channel attacks. The security framework proposed by Ishai, Sahai, and Wagner, known as the Ishai–Sahai–Wagner scheme, is one of the most acceptable secure models of the existing $d$ th-order masking schemes, where $d$ represents the masking order and plays the role of a security parameter. However, a gap may exist between scheme and design. Several analyses have determined that the glitch has been regarded as the main challenge of masking in hardware designs. A practical method of locating the precise position of leakage points (LPs) in the original hardware design is very rare. Existing research on this glitch mainly focuses on the first-order leakages; however, higher-order analysis can combine several shares to recover the secret key. In this paper, we propose a practical method, sensitive glitch location (SGL) method to locate the less order leakage in hardware design. Specifically, the SGL method can locate any-order of LP in the hardware implementation of $d$ th-order masking schemes. We conducted experiments and verified that the time complexity of SGL on the $d$ th-order masking schemes is ${O(nm)}$ , where $m$ is the number of signals and $n$ is the number of shares in masking scheme. It can therefore be regarded as an efficient tool for the masking designs. In addition, we analyzed the $d$ th-order masking scheme proposed by Rivain and Prouff (2010) along with the SecMult algorithm from the Rivain–Prouff countermeasure, which has been analyzed by our SGL. The experimental results verified that a higher-order leakage may exist in certain hardware designs, even the masking scheme has been proven as a secure countermeasure. To the best of our knowledge, SGL is the first tool that can be used to locate any-order of power/electromagnetic LP in hardware designs. It thus shows the weakness in the original design file of hardware implementations. This property can help designers directly improve the real security of the designs. Moreover, SGL returns the path of the leakages, which can elucidate the original cause and propagation of the weakness. [ABSTRACT FROM AUTHOR]

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists. [ABSTRACT FROM AUTHOR]

Routing for high-speed boards is still achieved manually today. There have recently been some related works to solve this problem; however, a more practical problem has not been addressed. Usually, the packages or components are designed with or without the requirement from board designers, and the boundary pins are usually fixed or advised to follow when the board design starts. In this paper, we describe this fixed ordering boundary pin routing problem, and propose a practical approach to solve it. Not only do we provide a way to address, we also further plan the wires in a better way to preserve the precious routing resources in the limited number of layers on the board, and to effectively deal with obstacles. Our approach has different features compared with the conventional shortest-path-based routing paradigm. In addition, we consider length-matching requirements and wire shape resemblance for high-speed signal routes on board. Our results show that we can utilize routing resources very carefully, and can account for the resemblance of nets in the presence of the obstacles. Our approach is workable for board buses as well. [ABSTRACT FROM AUTHOR]

This paper presents an efficient, scalable, and optimal slack-driven shaping algorithm for soft blocks in nonslicing floorplan. The proposed algorithm is called SDS. SDS is specifically formulated for fixed-outline floorplanning. Given a fixed upper bound on the layout width, SDS minimizes the layout height by only shaping the soft blocks in the design. Iteratively, SDS shapes some soft blocks to minimize the layout height with the guarantee that the layout width would not exceed the given upper bound. Rather than using some simple heuristic as in previous work, the amount of change on each block is determined by systematically distributing the global total amount of available slack to individual block. During the whole shaping process, the layout height monotonically reduces and eventually converges to an optimal solution. Two optimality conditions are presented to check the optimality of a shaping solution for fixed-outline floorplanning. In practice, to terminate the process of convergence early, we propose two different stopping criteria. We also extend SDS to handle other floorplanning problems, e.g., classical floorplanning. To validate the efficiency and effectiveness of SDS, comprehensive experiments are conducted on MCNC and HB benchmarks. Compared with previous work, SDS achieves the best experimental result with a significantly faster runtime. [ABSTRACT FROM AUTHOR]

Symbolic circuit analysis is concerned with analytical construction of circuit response in the frequency (or time) domain, for which an efficient data structure is required. Recent research has justified that the binary decision diagram (BDD) is a superior data structure with the following distinguishing feature: a large number of product terms can be compactly represented by a BDD, on which numerical computations and analytical deductions can be performed directly. Using BDD for symbolic circuit analysis requires an efficient method for construction. In this paper, a graph-based construction method, called graph-pair decision diagram (GPDD), is developed. Given a small-signal circuit, a pair of graphs representing the circuit is created, from which a GPDD is constructed by successively reducing the graph pair. The GPDD algorithm, which generates cancellation-free symbolic terms, differs from the existing determinant decision diagram (DDD) algorithm. Detailed theory and implementable algorithms for the GPDD construction are developed, and a runtime performance comparison to DDD is made. It is demonstrated that the runtime performance using GPDD is comparable to that of DDD in terms of time and memory complexity for exact symbolic analysis, although the GPDD algorithm has to generate a much larger number of symbolic product terms. [ABSTRACT FROM AUTHOR]

Due to the rapidly increasing design complexity in modern integrated circuit design, more and more timing failures are detected at late stages. Without deferring time-to-market, metal-only engineering change order (ECO) is an economical technique to correct these late-found failures. Typically, a design might need to undergo many ECO runs in design houses; consequently, the usage of spare cells for ECO is of significant importance. In this paper, we aim at timing ECO by using as few spare cells as possible. We observe that a path with good timing is desired to be geometrically smooth. Unlike negative slack and gate delay used in most prior work, we propose a new metric of timing criticality, fixability, by considering the smoothness of timing violating paths. To measure the smoothness of a path, we use the Bézier curve as the golden path. Furthermore, in order to concurrently fix timing violations, we derive a propagation property to divide violating paths into independent segments. Based on Bézier curve smoothing, fixability identification, and the propagation property, we develop an efficient algorithm to fix timing violations. Experimental results show that we can effectively resolve all timing violations with significant speedups over the state-of-the-art works. [ABSTRACT FROM AUTHOR]

Clocks are known to be major source of power consumption in digital circuits. In this paper, we propose a clustering algorithm for the minimization of power in a local clock tree. Given a set of sequentials and their locations, clustering is performed to determine the clock buffers that are required to synchronize the sequentials, where a cluster implies that a clock buffer drives all the sequentials in the cluster. The results produced by the algorithm are often within 1.3\times of the lower bound and have 32% lower costs, on average, than those due to an approximation algorithm with 2.5\times faster runtimes. Compared to competitive heuristic from a vendor tool, the results due to the algorithm on several blocks in microprocessor designs in advanced nanometer technologies show 14% reduction, on average, in clock tree power while meeting skew or slew constraints. The algorithm has been employed for clock tree synthesis for several microprocessor designs across process generations due to consistently significant clock tree power savings over the results due to competitive alternatives. [ABSTRACT FROM AUTHOR]

There has been considerable focus recently on research on developing assertion checking capability with analog and mixed-signal (AMS) simulators. Such tools must be able to detect failures of assertions in simulation traces and report the windows in which failures have been detected. Due to the dense real time semantics of AMS assertions, the task of identifying the minimal debugging window for each failure is not a trivial problem. This paper addresses the problem of computing the minimal debugging window in failure traces for AMS assertions and presents an algorithm which is linear in regards to the size of the assertion and the size of the trace. [ABSTRACT FROM AUTHOR]

Complementary synthesis can automatically synthesize the decoder circuit of an encoder. However, its user needs to manually specify an assertion on some configuration pins to prevent the encoder from reaching the nonworking states. To avoid this tedious task, this paper propose an automatic approach to infer this assertion, by iteratively discovering and removing cases without decoders. To discover all decoders that may exist simultaneously under this assertion, a second algorithm based on functional dependency is proposed to decompose \BBR, the Boolean relation that uniquely determines the encoder's input, into all possible decoders. To help the user select the correct decoder, a third algorithm is proposed to infer each decoder's precondition formula, which represents those cases that lead to this decoder's existence. Experimental results on several complex encoders indicate that our algorithm can always infer assertions and generate decoders for them. Moreover, when multiple decoders exist simultaneously, the user can easily select the correct one by inspecting their precondition formulas. [ABSTRACT FROM AUTHOR]

The ongoing scaling of semiconductor technology is causing severe increase of on-chip power density and temperature in microprocessors. This urgently requires both power and thermal management during system design. In this paper, we propose a model checking-based technique using extended timed automata to solve the processor frequency assignment problem in a temperature and energy-constrained multitasking system. We also develop a polynomial time-approximation algorithm to address the state-space explosion problem caused by symbolic model checker. Our approximation scheme is guaranteed to not generate any false-positive answer, while it may return false-negative answer in rare cases. Our method is universally applicable since it is independent of any system and task characteristics. Experimental results demonstrate the usefulness of our approach. [ABSTRACT FROM AUTHOR]

Complementary synthesis automatically synthesizes the decoder circuit of an encoder. It determines the existence of the decoder by checking whether the encoder's input can be uniquely determined by its output. However, this algorithm will not halt if the decoder does not exist. To solve this problem, a novel halting algorithm is proposed. For every path of the encoder, this algorithm first checks whether the encoder's input can be uniquely determined by its output. If yes, the decoder exists; otherwise, this algorithm checks if this path contains loops, which can be further unfolded to prove the non-existence of the decoder for all those longer paths. To illustrate its usefulness and efficiency, this algorithm has been run on several complex encoders, including PCI-E and Ethernet. Experimental results indicate that this algorithm always halts properly by distinguishing correct encoders from incorrect ones, and it is more than three times faster than previous ones. [ABSTRACT FROM AUTHOR]

For modern designs, delay optimization significantly facilitates success in design closure owing to its more realistic metric than wirelength in routing. Obstacle-avoiding rectilinear Steiner tree (OARST) construction is an essential routing problem. With the trends toward Internet protocol-block-based system-on-chip designs, OARST with buffer insertion has been surveyed to diminish the delay of long wires. Previous works on performance-driven (PD) OARST without and with buffer insertion can only handle small circuits. This paper develops a novel routing algorithm in obstacle-avoiding spanning graph to construct OARST with optimized delay efficiently. The proposed multisource single-target maze routing is first employed to identify the critical trunks, and the critical-trunk-based tree growth mechanism connects the unconnected pins to critical trunks under delay constraints of every sink. We apply the proposed critical-trunk-based tree growth mechanism to solve PD and slack-driven (SD) OARST problems. The proposed algorithms are extended to consider buffer insertion during PD and SD OARST constructions. Experimental results demonstrate that the proposed algorithms achieve an average 25.84% improvement in the maximum delay over obstacle-avoiding rectilinear Steiner minimal tree in the PD OARST problem and successfully solve 66.67% worst negative slack violations in the SD OARST problem. Compared to the simultaneous routing and buffer insertion approach, the proposed buffer-aware (BA) algorithm generates satisfactory timing results with almost identical wire length (WL). Moreover, the proposed BA SD OARST algorithm utilizes less WL than the BA rectilinear Steiner tree construction does by 17.99% on average. The runtime comparison with previous works shows the efficiency and scalability of this paper. [ABSTRACT FROM PUBLISHER]

Technology mapping and placement have a significant impact on delays in standard cell-based very large scale integrated circuits. Traditionally, these steps are applied separately to optimize the delays, possibly since efficient algorithms that allow the simultaneous exploration of the mapping and placement solution spaces are unknown. In this paper, we present an exact polynomial time algorithm for delay-optimal placement of a tree and extend the same to simultaneous technology mapping and placement for the optimal delay in the tree. We extend the algorithm by employing Lagrangian relaxation technique, which assesses the timing criticality of paths beyond a tree, to optimize the delays in directed acyclic graphs. Experimental results on benchmark circuits in a 70 nm technology show that our algorithms improve timing significantly with remarkably less runtimes compared to a competitive approach of iterative conventional timing-driven mapping and multilevel placement. [ABSTRACT FROM PUBLISHER]

Clock mesh networks are well known for their variation tolerance. But their usage is limited to high-end designs due to the significantly high resource requirements compared to clock trees and the lack of automatic mesh synthesis tools. Most existing works on clock mesh networks either deal with semi-custom design or perform optimizations on a given clock mesh. However, the problem of obtaining a good initial clock mesh has not been addressed. Also, the problem of achieving a smooth tradeoff between variation tolerance and resource requirements has not been addressed adequately. In this paper, we present our MeshWorks framework, the first comprehensive automated framework for planning, synthesis, and optimization of clock mesh networks that addresses the above issues. Experimental results suggest that our algorithms can achieve an additional reduction of 31% in buffer area, 21% in wirelength, and 23% in power, compared to the best previous work, with similar worst case maximum frequency. We also demonstrate the effectiveness of our framework under several practical issues such as blockages, multiple clocks, uneven load distribution, and electromigration violations. [ABSTRACT FROM AUTHOR]

In synchronous circuit designs, clock skew is difficult to minimize because a single physical layout of a clock tree must satisfy multiple constraints in a complicated power mode environment where certain modules may operate with different voltages. In this paper, we use adjustable delay buffers (ADB) whose delays can be tuned or adjusted to minimize clock skew under different power modes. Assuming that the positions of k ADBs are already determined, we first propose a linear-time optimal algorithm which assigns the values of ADBs so that the skew is optimal among all possible ADB assignments with a possibility of latency penalty. Then, we propose a modified optimal algorithm without latency penalty. We also propose an efficient heuristic to determine good positions for ADBs. Our results show significant improvement when compared to cases without ADBs. [ABSTRACT FROM AUTHOR]

Side channel attacks allow an attacker to retrieve secret keys with far less effort than other attacks. Countermeasures against these attacks should be considered during cryptosystem design. This paper presents a novel low-cost error detection and recovery scheme (LOEDAR) to counter fault attacks. The proposed architecture retains the efficiency of the Montgomery ladder algorithm and shows strong resistance to both environmental-induced faults as well as attacker-introduced faults. Moreover, the proposed LOEDAR scheme is compatible with most existing countermeasures against various power analysis attacks including differential power analysis and its variants, which makes it extendable to a comprehensive countermeasure against both fault attacks and power analysis attacks. [ABSTRACT FROM PUBLISHER]

As process technologies advance to the subwavelength era, the 1-D design style is regarded as one of the most effective ways to continue scaling down the minimum feature size. To improve the printability of 1-D cell design, it is essential to insert dummy patterns and optimize line-end gap distribution for each layer. This paper presents novel 1-D cell generation algorithms that simultaneously minimize 1-D cell area and enhance the printability. Experimental results show that the proposed algorithms can effectively and efficiently reduce the number of diffusion gaps, minimize used routing tracks, insert sufficient dummy patterns, and eliminate stage-like line-end gaps without power and timing overhead. Consequently, the 1-D cell area is minimized and the printability of the cell is enhanced. To the best of our knowledge, this is also the first work in the literature that considers line-end gap distribution during 1-D cell generation. [ABSTRACT FROM AUTHOR]

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

Unknown or X-values during test applications may originate from uncontrolled sequential cells or macros, from clock or A/D boundaries, or from tristate logic. The exact identification of X-value propagation paths in logic circuits is crucial in logic simulation and fault simulation. In the first case, it enables the proper assessment of expected responses and the effective and efficient handling of X-values during test response compaction. In the second case, it is important for a proper assessment of fault coverage of a given test set and consequently influences the efficiency of test pattern generation. The commonly employed n-valued logic simulation evaluates the propagation of X-values only pessimistically, i.e., the X-propagation paths found by n-valued logic simulation are a superset of the actual propagation paths. This paper presents an efficient method for overcoming this pessimism and for determining accurately the set of signals that carry an X-value for an input pattern. As examples, it investigates the influence of this pessimism on the two applications, X-masking and stuck-at fault coverage assessment. The experimental results on benchmark and industrial circuits assess the pessimism of classic algorithms and show that these algorithms significantly overestimate the signals with X-values. The experiments show that overmasking of test data during test compression can be reduced by an accurate analysis. In stuck-at fault simulation, the coverage of the test set is increased by the proposed algorithm without incurring any overhead. [ABSTRACT FROM AUTHOR]

Wire bonding is currently the most popular method for connecting signals between dies in system-in-package (SiP) design. Pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for SiP design because the quality of a pad assignment solution affects both the cost and the performance of an SiP design. In this paper, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wirelength, for die-stacking SiP design. We first consider the two-die cases and die-stacks with a bridging die, and present a minimum-cost flow-based approach to optimally solve them in polynomial time. We then describe an approach, which uses a modified left-edge algorithm and an integer linear programming technique, for pyramid die-stacks with no bridging die. Finally, we discuss extensions of the two approaches to handle additional design constraints. Encouraging experimental results are shown to support our approaches. [ABSTRACT FROM AUTHOR]

Level-sensitive latches are widely used in high-performance designs. For such circuits, efficient statistical timing analysis algorithms are needed to take increasing process variations into account. The existing methods for solving this problem are still computationally expensive and can only provide the yield at a given clock period. In this paper, we propose a method combining reduced iterations and graph transformations. The reduced iterations extract setup time constraints and identify a subgraph for the following graph transformations handling the constraints from nonpositive loops. The combined algorithms are very efficient, more than ten times faster than other existing methods, and result in a parametric minimum clock period, which, together with the hold-time constraints, can be used to compute the yield at any given clock period very easily. [ABSTRACT FROM AUTHOR]

Placement is the process of determining the exact locations of circuit elements within a chip. It is a crucial step in very large scale integration (VLSI) physical design, because it affects routability, performance, and power consumption of a design. In this paper, we develop a new analytical placer to solve the VLSI standard cell placement problem. The placer consists of two phases, multilevel global placement (GP) and detailed cell placement (DP). In the stage of GP, during the clustering stage, we use a nonlinear programming technique and a best-choice clustering algorithm to take a global view of the whole netlist and placement information, and then use an iterative local refinement technique during the declustering stage to further distribute the cells and reduce the wirelength. In the stage of DP, we develop a fast legalization algorithm to make the solution by global placement legal and use a cell order polishing to improve the legal solution. The proposed algorithm is tested on the IBM standard cell benchmark circuits and Peko suites. Experimental results show that our placer obtains high-quality results in a reasonable running time. [ABSTRACT FROM AUTHOR]

This paper presents a new approach for automatic computation of matching constraints for analog sizing. The method automatically analyzes a circuit netlist to generate sizing constraints. These sizing constraints are considered during a subsequent numerical optimization. It is the first method that computes symmetry constraints for sizing, based on the hierarchical structure of the circuit and a qualitative signal flow. As a unique feature, the method is capable of handling multiple signal and feedback paths, leading to multiple symmetry axes. It can be applied to linear and nonlinear circuits and any available sizing algorithm. Experimental results show that the runtime of analog sizing, as well as of result quality, are greatly improved. [ABSTRACT FROM AUTHOR]

Built-in self-repair (BISR) techniques are widely used for the repair of embedded memories. One of the key components of a BISR circuit is the built-in redundancy-analysis (BIRA) module, which allocates redundancies according to the designed redundancy analysis algorithm. Thus, the BIRA module affects the repair rate of the BISR circuit. Existing BIRA schemes for RAMs can provide the optimal repair rate (the ratio of the number of repaired RAMs to the number of defective RAMs), but they require either high area cost or multiple test runs. This paper proposes a BIRA scheme for RAMs, which can provide the optimal repair rate using very low area cost and single test run. Furthermore, the BIRA is designed as reconfigurable such that it can be shared by multiple RAMs. Experimental results show that the area cost for implementing the proposed BIRA scheme is much lower than that of existing BIRA schemes with optimal repair rate. A test chip is also implemented to demonstrate the proposed BIRA scheme. [ABSTRACT FROM PUBLISHER]

Due to the increasing chip temperature and the strong dependency of leakage power on temperature, thermal aware power management has received a considerable amount of attention recently in energy efficient system design. In this paper, we propose a temperature-aware intra-task scheduling algorithm to minimize leakage energy in real-time systems. The basic idea of our algorithm is to run tasks at full speed when the chip temperature is low or the work urgency is high, and switch the processor to a low-power state when the chip temperature is high or the workload is light. Our offline algorithm can achieve the optimal leakage reduction for a given task with the worst-case execution time, while the online algorithm has a very low runtime complexity. The simulation results show that the online algorithm is able to reduce 34% of total leakage energy on average in both real-world and artificial benchmarks. Finally, we demonstrate how to combine our algorithm with existing dynamic voltage scaling technique to optimize the overall energy consumption. [ABSTRACT FROM AUTHOR]

Vectorless power grid verification makes it possible to evaluate worst-case voltage noises without enumerating possible current waveforms. Under linear current constraints, the vectorless power grid verification problem can be formulated and solved as a linear programming (LP) problem. However, previous approaches suffer from long runtime due to the large problem size. In this paper, we design two dual algorithms that efficiently evaluate voltage noises in a resistor/capacitor power grid. Our algorithms combine novel dual approaches to solve the LP problem, and a preconditioned conjugate gradient power grid analyzer. The first algorithm exploits the structure of the problem to simplify its dual problem into a convex problem, which is then solved by the cutting-plane method. The second algorithm formulates a reduced-size LP problem for each node to compute upper bound of voltage noise. Experimental results show that both algorithms are highly efficient. [ABSTRACT FROM AUTHOR]

This paper presents a robust global router called NTHU-Route 2.0 that improves the solution quality and runtime of NTHU-Route by the following enhancements: 1) a new history based cost function; 2) new ordering methods for congested region identification and rip-up and reroute; and 3) two implementation techniques. We report convincing experimental results to show the effectiveness of each individual enhancement. With all these enhancements together, NTHU-Route 2.0 solves all ISPD98 benchmarks with very good quality. Moreover, NTHU-Route 2.0 routes 7 of 8 ISPD07 benchmarks and 12 of 16 ISPD08 benchmarks without any overflow. Compared with other state-of-the-art global routers, NTHU-Route 2.0 is able to produce better solution quality and/or run more efficiently. [ABSTRACT FROM PUBLISHER]

In interposer-based 2.5-D integrated circuits, the passive silicon interposer is the least expensive component in the chip. Thus, it is desirable to test the interposer before bonding to ensure that more expensive and defect-free dies are not stacked on a faulty interposer. We present an efficient method to locate defects in a passive interposer before stacking. The proposed test architecture uses e-fuses that can be programmed to connect or disconnect functional paths inside the interposer. The concept of die footprint is utilized for interconnect testing, and the overall assembly and test flow is described. Moreover, the concept of weighted critical area is defined and utilized to reduce test time. In order to fully determine the location of each e-fuse and the order of functional interconnects in a test path, we also present a test-path design algorithm. The proposed algorithm can generate all test paths for interconnect testing. We present HSPICE simulation results to demonstrate the effectiveness of the prebond test solution. Test-path designs are also presented to highlight the efficiency of the test-path design algorithm. The benefit of using weighted critical area is demonstrated using a commercial interposer from industry. [ABSTRACT FROM AUTHOR]

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

We present algorithms for routing in advanced technology nodes, used by BonnRoute (BR) to obtain efficient and almost design rule clean wire packings and pin access solutions. Designs with dense standard cell libraries in presence of complex industrial design rules, with a special focus on multiple patterning lithography are considered. The key components of this approach are a multilabel interval-based shortest path algorithm for long on-track connections, and a dynamic program for computing packings of pin access paths and short connections between closely spaced pins. The multilabel path search implementation is very general and is driven with different labeling rules, allowing to trade-off runtime against accuracy in terms of obeyed design rules. We combine BR with an industrial router for cleaning up the remaining design rule violations, and demonstrate superior results over that industrial router in our experiments in terms of wire length, number of vias, design rule violations, and runtime. [ABSTRACT FROM PUBLISHER]

We propose a self-contained, flat, quadratic global placer that is simpler than existing placers and easier to integrate into timing-closure flows. It maintains lower-bound and upper-bound placements that converge to a final solution. The upper-bound placement is produced by a novel look-ahead legalization algorithm. Our placer SimPL outperforms mPL6, FastPlace3, NTUPlace3, APlace2, and Capo simultaneously in runtime and solution quality, running 7.10 times faster than mPL6 (when using a single thread) and reducing wirelength by 3% on the ISPD 2005 benchmark suite. More significant improvements are achieved on larger benchmarks. The new algorithm is amenable to parallelism, and we report empirical studies with SSE2 instructions and up to eight parallel threads. [ABSTRACT FROM PUBLISHER]

There is an increasing trend toward application specific processing, particularly in embedded computing devices that have stringent performance requirements. Achieving the desired area and throughput constraints requires careful tuning of the underlying architecture and high-level design tools are gaining increasing acceptance to achieve this goal while decreasing the design time. Most existing tools employ a bottom-to-top methodology, which piece together functional units, interconnect, and control logic based on the given application; this tends to scale poorly. We developed a tool, simulate and eliminate (S&E), that is fundamentally different from the existing high-level design tools as it employs a top-to-bottom methodology. S&E provides automatic generation of a variety of general purpose processing cores with different parameterization options. Then, the provided application(s) are simulated on this general-purpose architecture and the unneeded functionality is eliminated resulting in application specific architecture. S&E generates completely synthesizable hardware description language for an input C and/or MATLAB code. S&E provides different design methods and parameterization options to enable the user to study area and performance tradeoffs over a large number of different architectures and find the optimum architecture for the desired objective. [ABSTRACT FROM PUBLISHER]

Retention registers have been widely used in power gated designs to store data during sleep mode. However, their excessive area and leakage power render it imperative to minimize the total retention storage size. The current industry practice replaces all registers with singlebit retention ones, which significantly limits the design freedom and yields suboptimal designs. Toward this, for the first time in the literature, we propose the concept and the design of multibit retention registers, with which only selected registers need to be replaced. The technique can significantly reduce the number of bits that need to be stored and thus the leakage power, but needs several clock cycles for mode transition. In addition, an efficient assignment algorithm is developed to minimize the total retention storage size subject to mode transition latency constraint. Experimental results show that our framework on average can reduce the leakage power in sleep mode by 84% along with additional mode transition latency of 6 to 11 clock cycles, compared with the singlebit retention register-based design. [ABSTRACT FROM PUBLISHER]

We describe BonnPlaceLegal, an algorithm for VLSI placement legalization. Based on a minimum-cost flow algorithm that iteratively augments flows along paths, our approach ensures that only augmentations are considered that can be realized exactly by cell movements. Hence, this method avoids realization problems that are inherent to previous flow-based legalization algorithms. As a result, it combines the global perspective of minimum-cost flow approaches with the efficiency of local search algorithms. The tool is mainly designed to minimize total and maximum cell movement, but it is flexible enough to optimize other objective functions provided that the effect of single cell movements on them can be estimated efficiently. We compare our approach to legalization tools from industry and academia by experiments on dense recent real-world designs and public benchmarks. The results show that we are much faster and produce significantly better results in terms of average (linear and quadratic) and maximum movement than any other tool. The experiments also demonstrate that by minimizing squared movement we also produce a smaller increase in net length than the other tools. [ABSTRACT FROM AUTHOR]

A floating random walk (FRW) solver, called RWCap, is presented for the capacitance extraction of very-large-scale integration (VLSI) interconnects. An approach, including the numerical characterization of the cross-interface transition probability and weight value, is proposed to accelerate the extraction of structures with multiple dielectric layers. A comprehensive variance reduction scheme based on the importance sampling and stratified sampling is proposed to improve the convergence rate of the FRW algorithm. Finally, the space management technique using an octree data structure and the parallel computing technique are presented to further improve the efficiency. Numerical experiments are carried out with the test cases generated under the 180 and 45-nm process technologies. They demonstrate that the proposed multidielectric FRW algorithm achieves up to 160\times speedup over the FRW algorithm using spherical transition domains to cross dielectric interface, with very small memory overhead. The variance reduction techniques further bring 3\times or more speedup without memory overhead and the loss of accuracy. The RWCap also outperforms other existing FRW algorithm and fast boundary element method solvers in terms of computational time or scalability. The experiments on an 8-core CPU machine show that the parallel RWCap is over 6\times faster than its serial-computing version. [ABSTRACT FROM AUTHOR]

An efficient filter synthesis algorithm is proposed to minimize the number of adders required in the design of finite-impulse response filters. Given a specification, a filter can be synthesized by conducting two main steps: coefficient generation and multiplier-block synthesis. While most of previous works have focused on only one of the steps, the proposed algorithm integrates the two steps in an interleaved manner so as to take into account the effect of multiplier-block synthesis in generating coefficients. In addition, the concept of sensitivity is developed to reduce the complexity of computing the variable ranges of coefficients. Experimental results show that the proposed algorithm outperforms previous algorithms in terms of adder cost and takes a relatively short computation time. [ABSTRACT FROM AUTHOR]

A flow is presented for the automatic synthesis of an analog circuit layout based on a schematic and a list of circuit design parameter values. The flow is driven by design, placement, and routing constraints—no layout template is necessary. Every possible layout for each device in the circuit is investigated; the layouts with the best geometric features and smallest quantization error (due to manufacturing grid alignment) are kept. For circuit placement, a complete enumeration of possible circuit placements, limited only by usual constraints of symmetry, proximity, and common centroid, is performed. Out of this enumeration a final circuit placement is selected and routed. The new flow is integrated with a deterministic nonlinear optimization algorithm to perform layout-driven circuit sizing; layouts are synthesized during both gradient approximation and next step determination. Layout-driven circuit sizing was applied to two example circuits. Sizing of the first circuit example took 8\times the amount of CPU time needed for traditional circuit sizing, but remained feasible at 2.1 h of wall clock time on a contemporary workstation. [ABSTRACT FROM PUBLISHER]

As memory capacity and density grow, a corresponding increase in the number of defects decreases the yield and quality of embedded memories for systems-on-chip as well as commodity memories. For embedded memories, built-in redundancy analysis (BIRA) is widely used to solve quality and yield issues by replacing faulty cells with healthy redundant cells. Many BIRA approaches require extra hardware overhead in order to achieve optimal repair rates, or they suffer a loss of repair rate in minimizing the hardware overhead. An innovative BIRA approach is proposed to achieve optimal repair rates, lower area overhead, and increase analysis speed. The proposed BIRA minimizes area overhead by eliminating some storage coverage for only must-repair faulty information. The proposed BIRA analyzes redundancies quickly and efficiently by evaluating all nodes of a branch in parallel with a new analyzer which is simple and easy-to-implement. Experimental results show that the proposed BIRA allows for a much faster analysis speed than that of the state-of-the-art BIRA, as well as the optimal repair rate, and relatively small area overhead. [ABSTRACT FROM AUTHOR]