waashk/dblp huggingface dataset:
dynamic voltage scaling for the schedulability of jitter-constrained real-time embedded systems. jitter is a critical problem for the design of both distributed embedded systems and real-time control systems. this work considers meeting the completion jitter constraints of a set of independent, periodic, hard real-time tasks scheduled according to a preemptive fixed-priority scheme. control over completion jitter is achieved by judiciously applying dynamic voltage scaling (dvs). through simulation, the proposed method is shown to be an effective tool to meet jitter constraints on a variety of systems.
a new approach for factorizing fsm's. exact factors as defined in [2], if present in an fsm can result in most effective way of factorization. however, it has been found that most of the fsm's are not exact factorizable. in this paper, we have suggested a method of making fsm's exact factorizable by minor changes in the next state space while maintaining the functionality of the fsm. we have also developed a new combined state assignment algorithm for state encoding of factored and factoring fsm's. experimental results on mcnc benchmark examples, after running misii on the original fsm, factored fsm and factoring fsm have shown a reduction of 40% in the worst case signal delay through the circuit in a multilevel implementation. the total number of literals, on an average is the same after factorization as that obtained by running misii on the original fsm. for two-level implementation, our method has been able to factorize benchmark fsm's with a 14% average increase in overall areas, while the areas of combinational components of factored and factoring fsm's have been found to be significantly less than the area of the combinational component of the original fsm.
new methods for parallel pattern fast fault simulation for synchronous sequential circuits. the authors present combined, a super fast fault simulator for synchronous sequential circuits. combined is based on coupling a parallel pattern simulator with a non-parallel simulator. combined runs substantialy faster on iscas-89 benchmark circuits than a state-of-the-art single fault propagation simulator
bit-level scheduling of heterogeneous behavioural specifications. this paper presents a heuristic scheduling algorithm for heterogeneous specifications, those formed by operations of different types and widths. the algorithm extracts the common operative kernel of the operations, and binds afterwards operations to cycles with the aim of distributing uniformly the number of bits calculated per cycle. in consequence, operations may be fragmented and executed during a set of non-necessarily consecutive cycles, and over a set of several linked simple hardware resources. the proposed algorithm, in combination with allocation algorithms able to guarantee bit-level reuse of hardware resources, obtains considerably smaller datapaths than the ones proposed by conventional synthesis algorithms. in the datapaths produced the type, number, and width of the hardware resources are independent of the type, number, and width of the specification operations and variables.
fredkin/toffoli templates for reversible logic synthesis. reversible logic has applications in quantum computing, lowpower cmos, nanotechnology, optical computing, and dnacomputing. the most common reversible gates are the toffoli gate and the fredkin gate. our synthesis algorithm first finds a cascade of toffoli and fredkin gates with no back-tracking and minimal look-ahead. next we apply transformations that reduce the size of the circuit. transformations are accomplished via template matching. the basis for atemplate is a network with m gates that realizes the identity function. if a sequence in the network to be synthesized matches more than half of a template, then a transformationthat reduces the gate count can be applied. in this paper weshow that toffoli and fredkin gates behave in a similar manner. therefore, some gates in the templates may not needto be specified-they can match a toffoli or a fredkin gate.we formalize this by introducing the box gate. all templateswith less than six gates are enumerated and classified. wesynthesize all three input, three output reversible functionsand compare our results to those obtained previously.
fastmag: a 3-d magnetostatic inductance extraction program for structures with permeable materials. in this paper we present a fast and efficient program for extraction of the frequency dependent inductance of structures with permeable materials. the program, fastmag, uses a magnetic surface charge formulation, efficient techniques for evaluating the required integrals, and a preconditioned gmres method to solve the resulting linear system. results from examples are presented to demonstrate the accuracy and versatility of the fastmag program.
scheduling and binding bounds for rt-level symbolic execution. generalizes alap (as late as possible) bounds for the exact scheduling problem on a pre-defined data path. conventional bounds are inapplicable because of the possible requirement of re-computing operands for minimal schedule length. efficient techniques are presented for constructing the new bounds which are sensitive to point-to-point delays via transitive memory units. an efficient operand mapping bound is also described. based on these two bounds, time improvement factors of 50 have demonstrated in exact scheduling results.
reducing pessimism in rlc delay estimation using an accurate analytical frequency dependent model for inductance. the increasing demand for high performance ics and system on chip necessitates reliable methodologies for reducing pessimism in chip design. in this paper, we investigate how the frequency dependence of loop self inductance affects the rlc delay. we show that the pessimism in the estimation of rlc propagation delay could be as high as 30% if the frequency dependence of inductance is not considered properly. as a means of efficiently computing less pessimistic rlc delay values, we present an analytical model of frequency dependent loop self inductance that can be applied to model a wide range of real design scenarios. we demonstrate that our approach is computationally efficient and produces accurate and realistic (less pessimistic) delay values that lead to significantly improved system performance.
re-engineering of timing constrained placements for regular architectures. abstract: in a typical design flow, the design may be altered slightly several times after the initial design cycle according to minor changes in the design specification either as a result of design debugging or as a result of changes in engineering requirements. these modifications are usually local and are referred to as engineering changes. in this paper we study the problem of timing driven placement re-engineering: the problem of altering the placement of a circuit to incorporate engineering changes without degrading the timing performance of the circuit. we focus on the re-engineering problem for regular architectures such as fpgas and gate arrays. our algorithms exploit the locality of the re-engineering design changes and use the current placement to generate the new placement for the altered circuit. our experiments on the xilinx 3000 fpga architecture demonstrate the effectiveness of our algorithm in handling engineering changes efficiently.
compression-relaxation: a new approach to performance driven placement for regular architectures. we present a new iterative algorithm for performance driven placement applicable to regular architectures such as fpgas. our algorithm has two phases in each iteration: a compression phase and a relaxation phase. we employ a novel compression strategy based on the longest path tree of a cone for improving the timing performance of a given placement. compression might cause a feasible placement to become infeasible. the concept of a slack neighborhood graph is introduced and is used in the relaxation phase to transform an infeasible placement to a feasible one using a mincost flow formulation. our analytical results regarding the bounds on delay increase during relaxation are validated by the rapid convergence of our algorithm on benchmark circuits. we obtain placements that have 13% less critical path delay (on the average) than those generated by the xilinx automatic place and route tool (apr) on technology mapped mcnc benchmark circuits with significantly less cpu time than apr.
least fixpoint approximations for reachability analysis. the knowledge of the reachable states of a sequential circuit can dramatically speed up optimization and model checking. however, since exact reachability analysis may be intractable, approximate techniques are often preferable. cho et al. presented the machine-by-machine (mbm) and frame-by-frame (fbf) methods to perform approximate fsm traversal. fbf produces tighter upper bounds than mbm; however, it usually takes much more time and it may have convergence problems. in this paper, we show that there exists a class of methods&mdash;least fixpoint approximations&mdash;that compute the same results as rfbf (reached fbf, one of the fbf methods). we show that one member of this class, which we call least fixpoint mbm (lmbm), is as efficient as mbm, but provably more accurate. therefore, the trade-off that existed between mbm and rfbf has been eliminated. lmbm can compute rfbf-quality approximations for all the large iscas-89 benchmark circuits in a total of less than 9000 seconds.
real time analysis and priority scheduler generation for hardware-software systems with a synthesized run-time system. we present a tool, called clara, that performs real-time analysis and priority assignment for software tasks in a mixed hardware-software system with a custom run-time scheduler. we start from a system described in tasks/threads consisting of hardware specified in verilog and software specified in c. we obtain the worst case execution time for each individual task. then, based on the control flow of the application, clara uses a dynamic programmming algorithm to automatically find optimal priorities for the software tasks assuming no interrupts. assuming the set of software tasks runs on a microprocessor in a target architecture using a template we provide for the priority scheduler and interrupt code, clara then finds the worst case execution time for the application with interrupts allowed. thus, this tool brings real-time analysis to a system level for a particular run-time system. clara helps a designer minimize the worst case execution time of a mixed hardware-software application.
event driven simulation without loops or conditionals. the past several years have seen much research in event driven logic simulation[1]. various logic and delay models have been explored[2]. most simulation research has focused on improving simulation performance. new approaches to both compiled and event driven simulation have been explored[3,4,5].the internal operations of event-driven simulators can be divided into two categories, scheduling, and gate simulation. much effort has been focused on reducing the cost of scheduling[3,4,5]. there has also been effort to reduce the cost of gate simulation[6,7]. it has also been shown that explicit computation of gate outputs is unnecessary, as long as event-propagation is computed correctly[7].even though research has reduced the complexity of both scheduling and gate simulation, it is still necessary to test for event propagation and cancellation, and it is necessary to perform some computations during gate simulation.this paper will show that none of these computations are necessary. most computations are devoted testing internal states and computing new internal states. in our technique, subroutine addresses are used to maintain states. this permits the elimination of all state-testing and state-computation code. our technique is significantly faster than conventional event-driven simulation[1]. unlike earlier methods[7], our approach can easily be extended to any logic model or any delay model.
a novel design methodology for high performance and low power digital filters. presents novel design methodologies which can be used to dramatically reduce the complexity of parallel implementations of digital fir filters. these approaches are also applicable to iir filters. two ideas are presented. first, we remove the redundant computation by using a graph-theoretic framework in which we find the optimal re-ordering of computations for maximal computation sharing. second, we present the novel approach of searching for a quantization which improves the computation sharing when the frequency-domain transfer function is allowed to deviate within given bounds. a simple search scheme is presented and it is shown that, by appropriate perturbation of the filter coefficients, one can dramatically reduce the number of adders required in the filter implementation. using these approaches, on an average, less than one adder per coefficient is required, in contrast to a full-width multiplier. hence, the presented methodologies are a useful compliment to the existing design approaches of high-performance and low-power digital filters for future mobile computing and communication systems
the inversion algorithm for digital simulation. the inversion algorithm is an event-driven algorithm, whose performance rivals or exceeds that of levelized compiled code simulation, even at activity rates of 50% or more. the inversion algorithm has several unique features, the most remarkable of which is the size of the run-time code. the basic algorithm can be implemented using no more than a page of run-time code, although in practice it is more efficient to provide several different variations of the basic algorithm. the run-time code is independent of the circuit under test, so the algorithm can be implemented either as a compiled code or an interpreted simulator with little variation in performance. because of the small size of the run-time code, the run-time portions of the inversion algorithm can be implemented in assembly language for peak efficiency, and still be retargeted for new platforms with little effort.
design automation issues for biofluidic microchips. biotechnologists have started to exploit the ic industry's planar microfabrication technology. the state of the art in planar biofluidic microdevices is reviewed as a way of introducing biochip design issues. as with transistor ics, design aids that span the entire iccad program from modeling and simulation to synthesis and physical design are needed to address these issues. hierarchical design representations, modeling abstractions, and algorithms pertaining to biochip design will be reviewed. potential future challenges will be identified to motivate how the iccad community can contribute to this emerging area.
an efficient and robust technique for tracking amplitude and frequency envelopes in oscillators. envelope-following methods face special challenges when applied to oscillators because of their fundamental property of dynamically-changing frequencies. in this paper, we present a novel and robust approach for oscillator envelope following. our method combines, unifies and extends ideas from two prior oscillator envelope-following approaches, petzold's method and the wampde. our technique uses two extra system unknowns, as well as two extra "phase condition" equations, to track quantities related to dynamical frequency/time-period changes. these advances confer significant robustness without appreciable computational overhead. we validate our method on lc, ring and crystal oscillators, predicting frequency and amplitude modulations as well as transient startup envelopes accurately. speedups of 1-2 orders of magnitude are obtained over traditional alternatives.
a general s-domain hierarchical network reduction algorithm. this paper presents an efficient method to reduce complexities ofa linear network in s-domain. the new method works on circuitmatrices directly and reduces the circuit complexities by eliminatingsubcircuits in a hierarchical way. the resulting admittancesin the reduced networks are kept as rational functions of s withreduced order. some theoretical results are characterized for thepresence of common factors coming from the suppression of subcircuits.a novel common factor removal (de-cancellation) strategybased on a graph-based hierarchical subcircuit reduction processis proposed. the resulting reduction algorithm is applicableto any linear circuits in s-domain. the stability of the reduced systemis enforced by applying the hurwitz polynomial approximation.the reduced systems can be used for fast s-domain analysisand for time domain waveform evaluation. experimental resultson both linear analog circuits and rlc circuits, and comparisonwith spice in s-domain analysis are also provided.
synthesis of manufacturable analog circuits. we describe a synthesis system that takes operating range constraints and inter- and intra-circuit parametric manufacturing variations into account while designing a sized and biased analog circuit. previous approaches to cad for analog circuit synthesis have concentrated on nominal analog circuit design, and subsequent optimization of these circuits for statistical fluctuations and operating point ranges. our approach simultaneously synthesizes and optimizes for operating and manufacturing variations by mapping the circuit design problem into an infinite programming problem and solving it using an annealing within annealing formulation. we present circuits designed by this integrated synthesis system, and show that they indeed meet their operating range and parametric manufacturing constraints.
a symbolic simulation-based methodology for generating black-box timing models of custom macrocells. we present a methodology for generating black-box timing models for full-custom transistor-level cmos circuits. our approach utilizes transistor-level ternary symbolic timing simulation to explore the input arrival time space and determine the input arrival time windows that result in proper operation. this approach integrates symbolic timing simulation into existing static timing analysis flows and allows automated modelling of the timing behavior of aggressive full-custom circuit design styles.
on testable multipliers for fixed-width data path architectures. the usage of multipliers in the increasingly demanding fixed-width data path architectures poses serious testability problems. their truncated outputs not only degrade the fault observability, but the output responses of multipliers are inadequate to completely test functional blocks that are driven by them. in this paper, we propose a new design for testability scheme to improve the overall testability of data paths. the methodology takes into account the truncated least significant bits of the product in the test mode to increase the variety of patterns at the output of a multiplier. the proposed techniques are part of the arithmetic built-in self test methodology and can be incorporated with a minimal performance degradation and area overhead.
symbolic functional and timing verification of transistor-level circuits. we introduce a new method of verifying the timing of custom cmos circuits. due to the exponential number of patterns required, traditional simulation methods are unable to exhaustively verify a medium-sized modern logic block. static analysis can handle much larger circuits but is not robust with respect to variations from standard circuit structures. our approach applies symbolic simulation to analyze a circuit over all input combinations without these limitations. we present a prototype simulator (sirsim) and experimental results. we also discuss using sirsim to verify an industrial design which previously required a special-purpose verification methodology.
statistical design and optimization of sram cell for yield enhancement. we have analyzed and modeled the failure probabilities of sram cells due to process parameter variations. a method to predict the yield of a memory chip based on the cell failure probability is proposed. the developed method is used in an early stage of a design cycle to minimize memory failure probability by statistically sizing of sram cell.
fast discrete function evaluation using decision diagrams. abstract: an approach for fast discrete function evaluation based on multi-valued decision diagrams (mdd) is proposed. the mdd for a logic function is translated into a table on, which function evaluation is performed by a sequence of address lookups. the value of a function for a given input assignment is obtained with at most one lookup per input. the main application is to cycle-based logic simulation of digital circuits, where the principal difference from other logic simulators is that only values of the output and latch ports are computed. theoretically, decision-diagram based function evaluation offers orders-of-magnitude potential speedup over traditional logic simulation methods. in practice, memory bandwidth becomes the dominant consideration on large designs. we describe techniques to optimize usage of the memory hierarchy.
rectangle-packing-based module placement. the first and the most critical stage in vlsi layout design is the placement, the background of which is the rectangle packing problem: given many rectangular modules of arbitrary size, place them without overlapping on a layer in the smallest bounding rectangle. since the variety of the packing is infinite (two- dimensionally continuous) many, the key issue for successful optimization is in the introduction of a p-admissible solution space, which is a finite set of solutions at least one of which is optimal. this paper proposes such a solution space where each packing is represented by a pair of module name sequences. searching this space by simulated annealing, hundreds of modules could be successfully packed as demonstrated. combining a conventional wiring method, the biggest mcnc benchmark ami49 is challenged.
adaptive designs for power and thermal optimization. a processor designed to continuously monitor environmental conditions, such as its own power consumption, temperature, and operating frequency, has the potential to dynamically optimize its operating point for maximal power efficiency in real time. the implementation of montecito's power and thermal control system (foxton), which is nearing production, provides a basis for discussing opportunities for increasing power efficiency and robustness.