waashk/dblp huggingface dataset:
minimizing the number of test configurations for fpgas. fpga test cost can be greatly reduced by minimizing the number of test configurations. a test technique is presented for fpgas with multiplexer-based routing architectures in which multiple logical paths through each multiplexer is enabled instead of only one path. it is shown that for xilinx virtex-ii and spartan-3 fpgas only 8 test configurations are required to achieve 100% stuck-at, pip stuck-on, and pip stuck-off fault coverage.
taco: temperature aware clock-tree optimization. in this paper, an efficient linear time algorithm taco is proposed for the first time to minimize the worst case clock skew in the presence of on-chip thermal variation. taco, while tries to minimize the worst case clock skew, also attempts to minimize the clock tree wirelength by building up merging diamonds in a bottom-up manner. as an output, taco provides balanced merging points and the modified clock routing paths to minimize the worst case clock skew under thermal variation. experimental results on a set of standard benchmarks show 50-70% skew reduction with less than 0.6% wirelength overhead.
incremental placement for timing optimization. an incremental timing driven placement algorithm is presented.we introduce a fast path-based analytical approach for timingimprovement. our method achieves timing optimization byreducing the enclosing bounding boxes of selected nets oncritical paths. furthermore, this technique tries to minimizemodifications to the initial placement while improving the delayof the circuit incrementally. two contributions of this work are1) efficient conversion of a path-based timing minimizationproblem to a geometric net-constraint problem and 2) minimalmodification of a placement to improve timing. our techniquecan take an initial placement from any algorithm and improvetiming iteratively. the experiments show that the proposedapproach is very efficient.
frame-based dynamic voltage and frequency scaling for a mpeg decoder. this paper describes a dynamic voltage and frequency scaling (dvfs) technique for mpeg decoding to reduce the energy consumption while maintaining a quality of servic(qos) constraint. the computational workload for an incoming frame is predicted using a frame-based history so that the processor voltage and frequency can be scaled to provide the exact amount of computing power needed to decode the frame. more precisely, the required decoding time for each frame is separated into two parts: a frame-dependent (fd) part and a frame-independent (fi) part. the fd part varies greatly according to the type of the incoming frame whereas the fi part remains constant regardless of the frame type. in the dvfs scheme presented in this paper the fi part is used to compensate for the prediction error that may occur during the fd part such that a significant amount of energy can be saved while meeting the frame rate requirement. the proposed dvfs algorithm has been implemented on a strongarm-1110 based evaluation board. measurement results demonstrate a higher than 50% cpu energy saving as a result of dvfs.
dynamic voltage and frequency scaling under a precise energy model considering variable and fixed components of the system power dissipation. this work presents a dynamic voltage and frequency scaling (dvfs) technique that minimizes the total system energy consumption for performing a task while satisfying a given execution time constraint. we first show that in order to guarantee minimum energy for task execution by using dvfs it is essential to divide the system power into active and standby power components. next, we present a new dvfs technique, which considers not only the active power, but also the standby component of the system power. this is in sharp contrast with previous dvfs techniques, which only consider the active power component. we have implemented the proposed dvfs technique on the bitsyx platform - an intel pxa255-based platform manufactured by ads inc., and report detailed power measurements on this platform. these measurements show that, compared to conventional dvfs techniques, an additional system energy saving of up to 18% can be achieved while satisfying the user-specified timing constraints.
parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation. with the increased significance of leakage power and performance variability, the yield of a design is becoming constrained both by power and performance limits, thereby significantly complicating circuit optimization. in this paper, we propose a new optimization method for yield optimization under simultaneous leakage power and performance limits. the optimization approach uses a novel leakage power and performance analysis that is statistical in nature and considers the correlation between leakage power and performance to enable accurate computation of circuit yield under power and delay limits. we then propose a new heuristic approach to incrementally compute the gradient of yield with respect to gate sizes in the circuit with high efficiency and accuracy. we then show how this gradient information can be effectively used by a non-linear optimizer to perform yield optimization. we consider both inter-die and intra-die variations with correlated and random components. the proposed approach is implemented and tested and we demonstrate up to 40% yield improvement compared to a deterministically optimized circuit.
control generation for embedded systems based on composition of modal processes. in traditional distributed embedded system designs, control information is often replicated across several processes and kept coherent by application-specific mechanisms. consequently, processes cannot be reused in a new system without tailoring the code to deal with the new system's control information. the modal process framework [5] provides a high-level way to specify the coherence of replicated control information independently of the behavior of the processes. thus multiple processes can be composed without internal tailoring and without suffering from errors common in lower-level specification styles. this paper first describes a kernel-language representation for the high-level composition operators; it also presents a synthesis algorithm for the mode manager, the runtime code that maintains control information coherence within and between distributed processors.
interface co-synthesis techniques for embedded systems. abstract: a key aspect of the synthesis of embedded systems is the automatic integration of system components. this entails the derivation of both the hardware and software interfaces that will bind these elements together and permit them to communicate correctly and efficiently. without the automatic synthesis of these interfaces, designers are not able to fully simulate and evaluate their systems. frequently, they are discouraged from exploring the design space of different hardware/software partitions because practical concerns mandate minimizing changes late in the design cycle, thus leading to more costly implementations than necessary. this paper presents a set of techniques that form the basis of a comprehensive solution to the synthesis of hardware/software interfaces. software drivers and glue logic are generated to connect processors to peripheral devices, hardware co-processors, or communication interfaces while meeting bandwidth and performance requirements. we use as examples a set of devices that communicate over an infrared local communications network (highlighting a video wrist-watch display) to explain our techniques and the need for design space exploration tools for embedded systems.
energy-efficient platform designs for real-world wireless sensing applications. real-world wireless sensing applications demand system platforms with a wide range of size, cost, power consumption, connectivity, performance, and flexibility requirements. these goals cannot be achieved without understanding the nature of the sensing functions in the first place, which can be classified into passive vs. active sensing, event detection vs. data acquisition, and real-time monitoring vs. data logging. this paper discusses platform design techniques for supporting these design goals through the trade-offs of sensing devices, wireless interfaces, and computation and control units. we also cover power subsystem design for supply-aware optimizations, including load/supply matching, power defragmentation in multi-supply systems, and use of supercapacitors. to evaluate these system platforms, we describe an emulation-based benchmarking methodology to quantify fitness metrics.
statistical estimation of sequential circuit activity. abstract: in this paper, we present a monte carlo based technique to estimate signal activity at the internal nodes of sequential logic circuits. the technique takes spatial and temporal correlations of logic signals into consideration. the monte carlo based techniques that have been proposed for combinational circuits can not be directly applied to sequential circuits due to the initial transient problem. the proposed approach deals with this problem by gaining insight from markov chain theory. experimental results show that the error (%) of estimated activity of individual nodes is within 3% in comparison to that of long run simulation results.
estimation of circuit activity considering signal correlations and simultaneous switching. this paper presents accurate estimation of signal activity at the internal nodes of cmos combinational logic circuits. the methodology is based on stochastic model of logic signals and takes correlations and simultaneous switching of signals at logic gate inputs into consideration. in combinational logic synthesis, in order to minimize spurious transitions due to finite propagation delays, it is crucial to balance all signal paths and to reduce the logic depth. as a result of balancing delays through different paths, the inputs to logic gates may switch at approximately the same time. we have developed and implemented an technique to calculate signal probability and switching activity of the cmos combinational logic circuits. experimental results show that if simultaneous switching is not considered the switching activities of the internal nodes can be off by more than 100% compared to simulation based techniques. in contrast, our technique is on the average within 2% of logic simulation results.
efficient reduced-order modeling for the transient simulation of three-dimensional interconnect. abstract: multipole-accelerated surface-volume methods have proved to be very efficient techniques for delay and cross-talk simulation of three-dimensional integrated circuit interconnect. however, to be efficiently combined with transistor circuitry in a spice-level simulation, reduced-order models which have accurate low-frequency behavior must be constructed. asymptotic waveform evaluation (awe) or pade-via-lanczos (pvl) algorithms can not be used directly to construct the reduced-order models from the surface-volume formulation, because the formulation generates dense matrices which are too expensive to factor. in this paper we describe a two-level approach to efficiently generating reduced-order models with accurate low frequency behavior. first, reduced-order models which match taylor series terms at s=/spl infin/ are efficiently generated from the surface-volume formulation using an arnoldi method, and then these fairly high-order models are used to efficiently construct lower-order models which snatch taylor series terms at s=0. examples are given to demonstrate the accuracy of the resultant low-order model.
technology mapping for field-programmable gate arrays using integer programming. we show that the fpga technology mapping problem can be efficiently implemented as a mixed integer linear programming (milp) problem which generates truly optimal mappings. the milp approach can handle a wide variety of fpga logic block architectures. we present a compact milp formulation for logic blocks based on lookup tables (luts) multiplexers. we also show that the milp formulation can be easily modified to modified to optimize area, delay, or a combination of both. we demonstrate that moderately large benchmark circuits can be mapped in a reasonable time using the milp approach directly. for larger circuits, we propose a technique of partitioning a circuit prior to mapping, which drastically reduces the computation time with little or no loss in optimality.
a new approach to simultaneous buffer insertion and wire sizing. in this paper, we present a completely new approach to the problem of delay minimization by simultaneous buffer insertion and wire sizing for a wire. we show that the problem can be formulated as a convex quadratic program, which is known to be solvable in polynomial time. nevertheless, we explore some special properties of our problem and derive an optimal and very efficient algorithm to solve the resulting program. given m buffers and a set of n discrete choices of wire width, the running time of our algorithm is o(mn^2) and is independent of the wire length in practice. for example, an instance of 100 buffers and 100 choices of wire width can be solved in 3 seconds. besides, our formulation is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. also, wire capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc. can be used.
retiming with interconnect and gate delay. in this paper, we study the problem of retiming of sequential circuitswith both interconnect and gate delay. most retiming algorithms haveassumed ideal conditions for the non-logical portions of the datapaths, which are not sufficiently accurate to be used in high performancecircuits today. in our modeling, we assume that the delay ofa wire is directly proportional to its length. this assumption is reasonablesince the quadratic component of a wire delay is significantlysmaller than its linear component when the more accurate elmore delaymodel is used. a simple experiment is conducted to illustrate thevalidity of this assumption. we present two approaches to solve thisproblem, both of which have polynomial time complexity. the firstone can compute the optimal clock period while the second one isan improvement over the first one in terms of practical applicability.the second approach gives solutions very close to the optimal (0.13%more than the optimal on average) but in a much shorter runtime.a circuit with more than 22k gates and 32k wires can be optimallyretimed in 83.56 seconds by a pc with an 1.8ghz intel xeon processor.
delay and area optimization for compact placement by gate resizing and relocation. in this paper, we first present an efficient algorithm for the gate sizing problem. then we propose an algorithm which performs delay and area optimization for a given compact placement by resizing and relocating cells in the circuit layout. since the gate sizing procedure is embedded within the placement adjustment process, interconnect capacitance information is included in the gate size selection process. as a result, the algorithm is able to obtain superior solutions.
dynamic power management using adaptive learning tree. dynamic power management (dpm) is a technique to reduce power consumption of electronic systems by selectively shutting down idle components. the quality of the shutdown control algorithm (power management policy) mostly depends on the knowledge of user behavior, which in many in many cases is initially unknown or non-stationary. for this reason, dpm policies should be capable of adapting to changes in user behavior. in this paper, we present a novel dpm scheme based on idle period clustering and adaptive learning trees. we also provide a design guide for applying our technique to components with multiple sleep states. experimental results show that our technique outperforms other advanced dpm schemes as well as simple time-out policies. the proposed approach shows little deviation of efficiency for various workloads having different characteristics, while other policies show that their efficiency changes drastically depending on the trace data characteristics. furthermore, experimental evidence indicates that our workload learning algorithm is stable and has fast convergence.
skew sensitivity minimization of buffered clock tree. given a topology of clock tree and a library of buffers, we propose an efficient skew sensitivity minimization algorithm using dynamic programming approach. our algorithm finds the optimum buffer sizes, its insertion levels in the clock tree, and optimum wire widths to minimize the skew sensitivity under manufacturing variations. careful fine tuning by shifting buffer locations at the last stage preserves the minimum skew sensitivity property and reduces the interconnect length. for a given clock tree of n points and a library of s different buffer sizes, the run time of the presented algorithm is o(log3n&bull;s2).experimental results show a significant reduction of clock skews ranging from 87 times to 144 times compared to the clock skews before applying the proposed algorithm. we also observe a further reduction of the propagation delay of clock signals as a result of applying the proposed skew sensitivity algorithm.
an algorithm for synthesis of system-level interface circuits. we describe an algorithm for the synthesis and optimization of interface circuits for embedded system components such as microprocessors, memory asic, and network subsystems with fixed interfaces. the algorithm accepts the timing characteristics of two system components as input, and generates a combinational interface (glue logic) circuit. the algorithm consists of two parts. in the first part, we determine the direct pin-to-pin connections in the interface circuit employing a 0/1 ilp formulation to minimize wiring area and dynamic power consumption. in the second part, we determine logic subcircuits in the interface circuit, utilizing the timing diagrams of the system components. the proposed algorithm has been implemented in a software package synterface. experimental results are presented to demonstrate the effectiveness of the algorithm.
expected current distributions for cmos circuits. the analysis of cmos vlsi circuit switching current has become an increasingly important and difficult task from both a vlsi design and simulation software perspective. this paper presents a new static switching current estimation algorithm based on the idea of "expected current distributions" (ecds). unlike previous "expected waveform" approaches, ecds model not only the expected value of switching current waveforms over all time, but also the variances and covariances of all waveform segments as well. this extra information allows a switching current wave form to be modeled by a random process with both first and second order ensemble statistics. this specification provides the power spectral density of the switching current and allows the use of traditional frequency domain noise analysis to simulate the behavior of the switching current in the electrical supply network. an ecd simulation procedure is described and results are presented for the iscas85 combinational benchmark circuits. estimated quantities include total average and rms vdd current, the autocorrelation function of the total vdd current waveform and per-gate average and rms vdd currents. the results show speedups of up to 100x and good agreement with respect to figures obtained using dynamic logic simulation and statistical mean estimation.
efficient canonical form for boolean matching of complex functions in large libraries. a new algorithm is developed which transforms the truth table or implicant table of a boolean function into a canonical form under any permutation of inputs. the algorithm is used for boolean matching for large libraries that contain cells with large numbers of inputs and implicants. the minimum cost canonical form is used as a unique identifier for searching for the cell in the library. the search time is nearly constant if a hash table is used for storing the cells' canonical representations in the library. experimental results on more than 100,000 gates confirm the validity and feasible run-time of the algorithm.
hybrid decision diagrams. abstract: functions that map boolean vectors into the integers are important for the design and verification of arithmetic circuits. mtbdds and bmds have been proposed for representing this class of functions. we discuss the relationship between these methods and describe a generalization called hybrid decision diagrams which is often much more concise. we show how to implement arithmetic operations efficiently for hybrid decision diagrams. in practice, this is one of the main limitations of bmds since performing arithmetic operations on functions expressed in this notation can be very expensive. in order to extend symbolic model checking algorithms to handle arithmetic properties, it is essential to be able to compute the bdd for the set of variable assignments that satisfy an arithmetic relation. in our paper, we give an efficient algorithm for this purpose. moreover, we prove that for the class of linear expressions, the time complexity of our algorithm is linear in the number of variables.
concurrent flip-flop and repeater insertion for high performance integrated circuits. for many years, cmos process scaling has allowed a steady increase in the operating frequency and integration density of integrated circuits. only recently, however, have we reached a point where it takes several clock cycles for global signals to traverse a complex digital system such as a modern microprocessor. thus, interconnect latency must be taken into account in current and future design tools at the architectural as well as synthesis level. to this purpose, this work proposes a new latency-aware technique for the performance-driven concurrent insertion of flip-flops and repeaters in vlsi circuits. overwhelming evidence showing an exponential increase in the number of pipelined interconnects with process scaling, for high-performance microprocessors as well as high-end asics, is also presented. this increase indicates a radical change in current design methodologies to cope with this new emerging problem.
dynamic scheduling and synchronization synthesis of concurrent digital systems under system-level constraints. we present in this paper a novel control synthesis technique for system-level specifications that are better described as a set of concurrent synchronous descriptions, their synchronizations and constraints. the proposed synthesis technique considers the degrees of freedom introduced by the concurrent models and by the environment in order to satisfy the design constraints.synthesis is divided in two phases. in the first phase, the original specification is translated into an algebraic system, for which complex control-flow constraints and quantifiers of the design are determined. this algebraic system is then analyzed and the design space of the specification is represented by a finite-state machine, from which a set of boolean formulas is generated and manipulated in order to obtain a solution. this method contrasts with usual high-level synthesis methods in that it can handle arbitrarily complex control-flow structures, concurrency and synchronization by allowing the scheduling of the operations to change dynamically over time.