waashk/dblp huggingface dataset:
testing delay faults in asynchronous handshake circuits. as a class of asynchronous circuits, handshake circuits are designed to tolerate variation of gate delays. however, certain timing constraints, such as the bundled data assumption, are exploited in the single-rail implementation of these circuits in order to simplify them. therefore, any delay fault in the circuit may cause one of two problems, namely performance degradation or logic errors. to address the challenges incurred by the autonomous behavior of handshake circuits during at-speed test, we propose test methods for both types of delay faults based on a dft strategy which greatly simplifies the complexity of test generation. the efficiency of the proposed methodology is demonstrated through experimental results on several handshake circuits.
voltage island aware floorplanning for power and timing optimization. power consumption is a crucial concern in nanometer chip design. researchers have shown that multiple supply voltage (msv) is an effective method for power consumption reduction. the underlying idea behind msv is the trade-off between power saving and performance. in this paper, we present an effective voltage assignment technique based on dynamic programming. given a netlist without reconvergent fanouts, the dynamic programming can guarantee an optimal solution for the voltage assignment. we then generate a level shifter for each net that connects two blocks in different voltage domains, and perform power-network aware floorplanning for the msv design. experimental results show that our floorplanner is very effective in optimizing power consumption under timing constraints.
practical variation-aware interconnect delay and slew analysis for statistical timing verification. interconnects constitute a dominant source of circuit delay for modern chip designs. the variations of critical dimensions in modern vlsi technologies lead to variability in interconnect performance that must be fully accounted for in timing verification. however, handling a multitude of inter-die/intra-die variations and assessing their impacts on circuit performance can dramatically complicate the timing analysis. in this paper, a practical interconnect delay and slew analysis technique is presented to facilitate efficient evaluation of wire performance variability. by harnessing a collection of computationally efficient procedures and closed-form formulas, process and input signal variations are directly mapped into the variability of the output delay and slew. since our approach produces delay and slew expressions parameterized in the underlying process variations, it can be harnessed to enable statistical timing analysis while considering important statistical correlations. our experimental results have indicated that the presented analysis is accurate regardless of location of sink nodes and it is also robust over a wide range of process variations.
temperature-aware leakage minimization technique for real-time systems. in this paper, we study the interdependency between leakage energy and chip temperature in real-time systems. we observe that the temperature variation on chip has a large impact on the system's leakage energy. by incorporating the temperature information, we propose an online temperature-aware leakage minimization algorithm for real-time systems. the basic idea is to run tasks when the system is cool and the workload is high, and put the system into sleep when it is hot and the workload is light. this online algorithm has low run-time complexity and improve the leakage energy saving by 34% on average in both real life and artificial benchmarks over traditional dvs approaches. finally, our algorithm can be combined with existing dynamic voltage scaling methods to further improve the total energy efficiency.
conjoining soft-core fpga processors. soft-core programmable processors on field-programmable gate arrays (fpgas) can be custom synthesized to instantiate only those hardware units, such as multipliers and floating-point units, that an application requires to meet performance demands, thus minimizing soft-core size on the fpga. conjoining processors, meaning to share hardware units among two or more processors, can further reduce soft-core size, leaving more resources for other circuits such as custom coprocessors. using xilinx microblaze coprocessors and standard embedded system benchmarks, we show that conjoining two processors can provide 16% processor size reductions on average, with less than 1% cycle count overhead. we introduce an efficient dynamic-programming-based exploration method to find the best custom instantiation of hardware units, considering both standalone and conjoined options, for soft-core processors.
design automation for analog: the next generation of tool challenges. the decade of the 1990s saw the first wave of practical "post-spice" tools for analog designs. a range of synthesis, optimization, layout and modeling techniques made their way from academic prototypes to first-generation commercial offerings. we offer some pragmatic prognostications for what the next wave might (or, more bluntly, should) focus on next, as pressure to improve ams design productivity grows.
performance analysis of concurrent systems with early evaluation. early evaluation allows to execute operations when enough information at the inputs has been received to determine the value at the outputs. systems that can tolerate variable-latency units, such as latency-insensitive or asynchronous systems, can enhance their performance by using early evaluation. the most relevant example of a unit with early evaluation is the multiplexor: the output can be determined as soon as the information of the selected channel arrives, without waiting for the other channels. this paper analyzes the potential impact of early evaluation in concurrent systems. an analytical model, based on a petri net extension with early firing is proposed to estimate the performance. the reduction of the analytical model to a linear programming formulation for an efficient estimation of the upper bound for the system throughput is proposed. the results show the accuracy of the model and the benefits of early evaluation.
an optimal simultaneous diode/jumper insertion algorithm for antenna fixing. as technology enters the nanometer territory, the antenna effect plays an important role in determining the yield and reliability of a vlsi circuit. diode insertion and jumper insertion are the most effective techniques to fix the antenna effect. however, due to the increasing design complexity and the limited routing resource, applying diode or jumper insertion alone cannot achieve a high antenna fixing rate. in this paper, we give a polynomial-time antenna violation detection/fixing algorithm by simultaneous diode/jumper insertion with minimum cost, based on a minimum-cost networkflow formulation. experimental results show that our algorithm consistently achieves much higher antenna fixing rates than the state-of-the-art jumper insertion and diode insertion algorithms alone.
efficient boolean characteristic function for fast timed atpg. circuit timing analysis is important in various aspects of circuit optimization. the problem of finding input vectors achieving functional and temporal requirements is known as timed automatic test pattern generation (timed atpg). a timed atpg algorithm will return an input vector that satisfies functional and temporal requirements simultaneously when evaluated. several previous works use timed atpg as a core engine for solving problems related to timing analysis, such as crosstalk and maximum instantaneous current analysis. despite the usefulness of timed atpg, traditional timed atpg is slow and unscalable for large circuits. in this paper, we present a very efficient way for timed atpg. on average, our results are 8 times faster than the most recent work, and in some cases, up to 32 times faster.
uml for esl design: basic principles, tools, and applications. this paper starts with a brief introduction to the uml 2.0 and application-specific uml customizations via profiles. after a discussion of uml design tools with focus on eda support, we present a hw/sw co-design approach and demonstrate how hw architectures are described together with application sw in a unique uml based environment. using a dedicated profile providing support for systemc in uml, and a systemc wrapper for the simit instruction set simulator of a strongarm, an executable model of the complete architecture is generated which can be simulated by the systemc kernel. the physical layer of an 802.11a system is used as an application example.
optimal memoryless encoding for low power off-chip data buses. off-chip buses account for a significant portion of the total system power consumed in embedded systems. bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. in this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful.
post-placement voltage island generation. high power consumption will shorten battery life for handheld devices and cause thermal and reliability problems. one way to lower the dynamic power consumption is to reduce the supply voltage. multi-supply voltage (msv) is introduced to provide higher flexibility in controlling the power and performance trade-off in region-based msv, circuits are partitioned into "voltage islands" where each island occupies a contiguous physical space and operates at one supply voltage. in a very recent work [6], this supply voltage partitioning problem is addressed, and the input circuit is partitioned into a slicing structure with every voltage island rectangular in shape. this unnecessary restriction on the structure and island shapes has caused a significant degradation in the solution quality. in this paper, we propose a method to solove this voltage island generation problem without these restrictions. experimental results have shown that our approach is fast and can improve the solution quality significantly. in some data sets, only two voltage islands are needed to satisfy the same power consumption bound while the approach in [6] will generate nineteen.
handling inductance in early power grid verification. as part of integrated circuit design verification, one should check if the voltage drop on the power grid exceeds some critical threshold. one way to do this is by simulation, but that is computationally expensive and gets prohibitive for large circuits with a large variety of possible operational modes. another limitation of a simulation-based approach is that it requires complete knowledge of the logic circuitry drawing current from the grid, thus precluding grid verification early in the design process. in this paper, we model the grid as an rlc circuit and we propose three verification techniques that can be applied in the early stages of the design process. these techniques do not require exact knowledge of the circuit currents. instead, the currents drawn by the logic beneath the power grid are described by means of current constraints that capture the uncertainty about circuit details and activity. the first verification approach gives the exact worst-case voltage drop at every node of the grid, but it is slow. a second faster approach gives conservative bounds on the worst-case voltage drop at every node of the grid. the third approach is much faster; it is a conservative approach which simply checks if the grid voltage drop exceeds some pre-defined thresholds, without actually computing the worst-case voltage drop at every node.
optimizing yield in global routing. we present the first efficient approach to global routing that takes spacing-dependent costs into account and provably finds a near-optimum solution including these costs. we show that this algorithm can be used to optimize manufacturing yield. the core routine is a parallelized fully polynomial approximation scheme, scaling very well with the number of processors. we present results showing that our algorithm reduces the expected number of defects in wiring by more than 10 percent on state-of-the-art industrial chips.
timing model reduction for hierarchical timing analysis. in this paper, we propose a timing model reduction algorithm for hierarchical timing analysis based on a bicliquestar replacement technique. in hierarchical timing analysis, each functional block is characterized into an abstract timing model. the complexity of analysis is linear to the number of edges in the abstract timing model for timing propagation. we propose a biclique-star replacement technique to minimize the number of edges in the timing model. the experiments on industry test cases show that by allowing acceptable errors, the proposed algorithm can largely reduce the number of edges in the timing model.
a bitmask-based code compression technique for embedded systems. embedded systems are constrained by the available memory. code compression techniques address this issue by reducing the code size of application programs. dictionary-based code compression techniques are popular because they offer both good compression ratio and fast decompression scheme. recently proposed techniques [8, 9] improve standard dictionary-based compression by consideringmismatches. this paper makes two important contributions: i) it provides a cost-benefit analysis framework for improving the compression ratio by creating more matching patterns, and ii) it develops an efficient code compression technique using bitmasks to improve the compression ratio without introducing any decompression penalty. to demonstrate the usefulness of our approach we have used applications from various domains and compiled for a wide variety of architectures. our approach outperforms the existing dictionary-based techniques by an average of 15%, giving a compression ratio of 55% - 65%.
loop pipelining for high-throughput stream computation using self-timed rings. we present a technique for increasing the throughput of stream processing architectures by removing the bottlenecks caused by loop structures. we implement loops as self-timed pipelined rings that can operate on multiple data sets concurrently. our contribution includes a transformation algorithm which takes as input a high-level program and gives as output the structure of an optimized pipeline ring. our technique handles nested loops and is further enhanced by loop unrolling. simulations run on benchmark examples show a 1.3 to 4.9x speedup without unrolling and a 2.6 to 9.7x speedup with twofold loop unrolling.
dynamic power management using machine learning. dynamic power management (dpm) work proposed to date places inactive components into low power states using a single dpm policy. in contrast, we instead dynamically select among a set of dpm policies with a machine learning algorithm. we leverage the fact that different policies outperform each other under different workloads and devices. our algorithm adapts to changes in workloads and guarantees quick convergence to the best performing policy for each workload. we performed experiments with a policy set representing state of the art dpm policies on a hard disk drive and a wlan card. our results show that our algorithm adapts really well with changing device and workload characteristics and achieves an overall performance comparable to the best performing policy at any point of time.
exploring linear structures of critical path delay faults to reduce test efforts. it has been shown that the delay of a target path can be composed linearly of other path delays. if the later paths are robustly testable (with known delay values), the target path can then be validated through simple calculation. yet, no decomposition process is available to find paths that satisfy the above property. in this paper, given a set of target critical paths, we propose a two-stage method to find a set of robust-testable paths (with smaller number than the original set). the first stage constructs a necessary subset for critical robust paths, and the second stage identifies remaining functional sensitizable segments and their corresponding composing robust paths. the experiments show that a large percentage (several benchmarks close to 100%, 75% on average) of critical paths can be covered for most circuits. all paths and coverage are verified to match the best possible results. the data also indicate that the remaining hard-to-test (functional sensitizable) paths actually result from only a few tens of segments in the circuit (except for one circuit, s35932). dft technique can then be applied to these uncovered segments for full testability with small overheads.
mapping arbitrary logic functions into synchronous embedded memories for area reduction on fpgas. this work describes a new mapping technique, ram-map, that identifies parts of circuits that can be efficiently mapped into the synchronous embedded memories found on field programmable gate arrays (fpgas). previous techniques developed for mapping into asynchronous embedded memories cannot be used because modern fpgas do not have asynchronous embedded memories. after technology mapping, an area-prediction cost function is used to guide the selection of logic cones to be placed in embedded memories. extra logic is added to compensate for missing asynchronous functionality on the synchronous memories. experiments conducted on altera's stratix device family indicate that this embedded memory mapping technique can provide an average area reduction of 6.2% and up to 32.5% on a large set of industrial designs. a small architecture change that increases the size of the fpga fabric by 0.05% can increase the average area reduction to 14.1% and up to 59.1% on the same design set.
exploiting soft redundancy for error-resilient on-chip memory design. memory design is facing the upcoming challenges due to a combination of technology scaling and higher levels of integration and system complexity. in particular, memory circuits become vulnerable to transient (soft) errors caused by particle strikes and process spread. in this paper, we propose a new error-tolerance technique referred to as the soft redundancy for on-chip memory design. program runtime variations in memory spatial locality cause wasted memory spaces occupied by the irrelevant data. the proposed soft-redundancy allocated memory exploits these wasted memory spaces to achieve efficient memory access and effective error protection in a coherent manner. simulation results on the spec cpu2000 benchmarks demonstrate 73.7% average error protection coverage ratio on the 23 benchmarks, with average of 52% and 48.3% reduction in memory miss rate and bandwidth requirement, respectively, as compared to the existing techniques.
layer minimization of escape routing in area array packaging. we devise a central triangular sequence to minimize the escape routing layers in area array packaging. we use a network flow model to analyze the bottleneck of the routable pins. the triangular patterns are generated in a reverse order from the last to the first layer. we demonstrate that the triangular pin sequence maximizes the sum of escape pins in the accumulated layers and thus minimize the number of escape routing layers. a test case is presented to illustrate the approach.
fast decap allocation based on algebraic multigrid. decap (decoupling capacitor) is an effective technique for suppressing power supply noise. nevertheless, over-usage of decap usually causes excessive power dissipation. therefore, the total decap area needs to be minimized subject to power supply noise constraints. this is a complicated nonlinear optimization problem that may have as many as millions of variables. we propose an algebraic multigrid (amg) based method to handle the high complexity. an error compensation scheme is developed to compensate the accuracy loss during the amg reduction. a charge based back-mapping method and a few other techniques are suggested to further improve the computation efficiency. our method is flexible to use and can be easily integrated with other existing decap allocation works. when compared to several previous works, the results from our method are usually the closest to the optimum. our method also runs fast and can solve circuits with up to 1 million nodes in about 11 minutes. in addition, it has better scalability than the previous works.
thermal sensor allocation and placement for reconfigurable systems. temperature monitoring using thermal sensors is an essential tool for evaluating the thermal behavior and sustaining the reliable operation in high-performance and high-power systems. with current technology scaling and integration trends timely and accurate detection of localized heating will be evermore important. in this work, we address the creation of a resource efficient sensor infrastructure for computing systems that are of regular nature, such as logic array-based computing platforms. we propose algorithms to embed thermal sensors into a regular structure to minimize the number of sensors and determine sensor locations required to maintain a given accuracy in temperature sensing for a given design. our algorithms are tailored for minimal usage of thermal sensors to suit a variety of architectural conditions. for programmable logic arrays the highly application-specific usage of the hardware resources leads to unpredictable thermal profiles. as a result, post-manufacture instantiation of thermal sensors is desired, which in turn demands the use of native hardware resources, which can be scarce. we demonstrate that using our techniques the number of sensors required to monitor a set of hotspots is reduced by 75% on an average, across different sizes of logic arrays for different hotspot distributions compared to a uniform distribution of sensors throughout the fabrics.
leveraging protocol knowledge in slack matching. stalls, due to mis-matches in communication rates, are a major performance obstacle in pipelined circuits. if the rate of data production is faster than the rate of consumption, the resulting design performs slower than when the communication rate is matched. this can be remedied by inserting pipeline buffers (to temporarily hold data), allowing the producer to proceed if the consumer is not ready to accept data. the problem of deciding which channels need these buffers (and how many) for an arbitrary communication profile is called the slack matching problem; the optimal solution to this problem has been shown to be np-complete. in this paper, we present a heuristic that uses knowledge of the communication protocol to explicitly model these bottlenecks, and an iterative algorithm to progressively remove these bottlenecks by inserting buffers. we apply this algorithm to asynchronous circuits, and show that it naturally handles large designs with arbitrarily cyclic and acyclic topologies, which exhibit various types of control choice. the heuristic is efficient, achieving linear time complexity in practice, and produces solutions that (a) achieve up to 60% performance speedup on large media processing kernels, and (b) can either be verified to be optimal, or the approximation margin can be bounded.