waashk/dblp huggingface dataset:
enhancing high-level control-flow for improved testability. in this study, we present a controllability measure for high-level circuit descriptions and a high-level synthesis-for-testability technique. unlike many recent studies in the area of high-level synthesis for testability that focus on improving the testability of data paths, the objective of our approach is to improve the testability of synthesized circuits by enhancing the controllability of the control flow. experimental results on several high-level synthesis benchmarks show that when this approach is used prior to logic synthesis, a shorter atpg time, a smaller test set, and better fault coverage and atpg efficiency are often achieved. implementation of this technique requires minimal logic and performance overheads and allows test vectors to be applied at clock-speed.
a precorrected-fft method for simulating on-chip inductance. the simulation of on-chip inductance using peec-based circuit analysis methods often requires the solution of a subproblem where an extracted inductance matrix must be multiplied by a current vector, an operation with a high computational cost. this paper presents a highly accurate technique, based on a precorrected-fft approach, that speeds up this calculation. instead of computing the inductance matrix explicitly, the method exploits the properties of the inductance calculation procedure while implicitly considering the effects of all of the inductors in the layout. an optimized implementation of the method has been applied to accurately simulate large industrial circuits with up to 121,000 inductors and nearly 7 billion mutual inductive couplings in about 20 minutes. techniques for trading off the cpu time with the accuracy using different approximation orders and grid constructions are also illustrated. comparisons with a block diagonal sparsification method in terms of accuracy, memory and speed demonstrate that our method is an excellent approach for simulating on-chip inductance in a large circuit.
efficient generation of monitor circuits for gste assertion graphs. generalized symbolic trajectory evaluation (gste) is a powerful,new method for formal verification that combines the industrially-provenscalability and capacity of classical symbolic trajectoryevaluation with the expressive power of temporal-logic modelchecking. gste was originally developed at intel and hasbeen used successfully on intel's next-generation microprocessors.however, the supporting algorithms and tools for gste are stillrelatively immature.gste specifications are given as assertion graphs, an extensionof ¿-automata. this paper presents a linear-time, linear-size translationfrom gste assertion graphs into monitor circuits, which canbe used with dynamic verification both as a quick "sanity check" ofthe specification before effort is invested in abstraction and formalverification, and also as means to reuse gste specifications withother validations methods. we present experimental results usingreal gste assertion graphs for real industrial circuits, showing thatthe circuit construction procedure is efficient in practice and that themonitor circuits impose minimal simulation overhead.
application-specific buffer space allocation for networks-on-chip router design. we present a system-level buffer planning algorithm that can be used to customize the router design in networks-on-chip (nocs). more precisely, given the traffic characteristics of the target application and the buffering space budget, our algorithm automatically assigns the buffer depth for each input channel, in different routers across the chip, to match the communication pattern, such that the overall performance is maximized. this is in deep contrast with the uniform assignment of buffering resources (currently used in noc design) which can significantly degrade the overall system performance. for instance, for a complex audio/video application, about 85% savings in buffering resources can be achieved by smart buffer allocation using our algorithm without any reduction in performance.
optimum loading dispersion for high-speed tree-type decision circuitry. with increasing density and capacity due to technology scaling, augmenting data (especially in semiconductor memories) burden selection circuitry with exponentially growing capacitive loads. this tendency violates stringent timing requirements.this work ameliorates the situation for k-stage tree-type decision circuitry. we show that for a k-stage binary decision tree, there always exists an optimum solution such that, after the select-signal arrangement, the worst case loading among select signals equals a lower bound. our proposed procedure not only provides an optimum solution but also minimizes the loading variance. the worst case loading can be reduced up to nearly k/2 times, thus speeding up and saving power up to k/2 times or so for the select signal with the heaviest loading. in contrast, excluding one unit-loading select signal, the empirical variance of the remaining (k - 1) signals is always less than 1 instead of diverging. hence, our approach, for timing-driven layout synthesis, is competent to design high-performance tree-type decision circuitry with more accurate timing and power prediction. in addition, by the presented approach, we can have the alternative of optimizing either for k-stage or for (k-1)-stage, meanwhile possibly minimizing the other. our algorithm, also, can easily be extended for a general k-stage decision tree with r descendants per node, not restricted to a binary tree; the resultant worst case loading could be quite close to the lower bound and reduced up to nearly k(r - 1)/r times.
a timing-constrained algorithm for simultaneous global routing of multiple nets. in this paper, we propose a new approach for vlsi interconnect global routing that can optimize both congestion and delay, which are often competing objectives. our approach provides a general framework that may use any single-net routing algorithm and any delay model in global routing. it is based on the observation that there are several routing topology flexibilities under timing constraints. these flexibilities are exploited for congestion reduction through a network flow based hierarchical bisection and assignment process. experimental results on benchmark circuits are quite promising.
on breakable cyclic definitions. in the course of hardware system design or real-time process control, high-level specifications may contain simultaneous definitions of concurrent modules whose information flow forms cyclic dependencies without the separation of state-holding elements. the temporal behavior of these cyclic definitions may be meant to be combinational rather than sequential. most prior approaches to analyzing cyclic combinational circuits were built upon the formulation of ternary-valued simulation at the circuit level. this work shows the limitation of this formulation and investigates, at the functional level, the most general condition where cyclic definitions are semantically combinational. it turns out that the prior formulation is a special case of our treatment. our result admits strictly more flexible high-level specifications. furthermore, it allows a higher-level analysis of combinationality, and, thus, no costly synthesis of a high-level description into a circuit netlist before combinationality analysis can be performed. with our formulation, when the target is software implementations, combinational cycles need not be broken as long as the execution of the underlying system obeys a sequencing execution rule. for hardware implementations, combinational cycles are broken and replaced with acyclic equivalents at the functional level to avoid malfunctioning in the final physical realization.
fast-yet-accurate pvt simulation by combined direct and iterative methods. the operations and performances of deep-submicron integrated circuits are affected significantly by the variations of process parameters, power supply voltages and operating temperatures. circuit simulation for all the combinations of process-voltage-temperature (pvt) conditions, known as pvt simulation, is emerging as a must not only for analog and rf circuit designs, but also for the designs of digital library cells and critical paths. with the number of pvt conditions in the range of hundreds and even thousands, existing solution of invoking a simulator repeatedly for all these pvt conditions is becoming extremely time consuming. this paper presents a new simulation approach capable of simulating hundreds and thousands pvt corners with the computational cost comparable to or even less than that of a few corner simulations, yet with the same simulation accuracy and robustness. the proposed approach is based on the combination of the lu-factorization based direct method and krylov subspace based iterative methods to explore the common characteristics shared by a circuit under all pvt corners. the key novelty is a systematic method that uses as few lu based direct solving as possible for underlying linearized systems, and then solves the rest of linearized systems across the entire pvt linear system space using krylov subspace based iterative methods with preconditioners computed from those lu factors.
forward model checking techniques oriented to buggy designs. forward model checking is an efficient symbolic model checking method for verifying realistic properties of sequential circuits and protocols. in this paper, we present the techniques that modify the order of state traversal on forward model checking, and that dramatically improve average cpu time for finding design errors. a failing property has to be checked again and again to analyze the bug until it is corrected. the techniques, therefore, can have significant impacts on actual verification tasks. we use a modified regular/omega-regular expression to represent a set of illegal state transition sequences of an fsm. it makes the problem clear and gives us a sense of depth-first traversal, not on the state space, but on the property.
approaching the maximum energy saving on embedded systems with multiple voltages. dynamic voltage scaling (dvs) is arguably the most effectiveenergy reduction technique. the multiple-voltage dvs systems,which can operate only at pre-determined discrete voltages, arepractical and have been well studied. however, one importantunsolved problem is how many levels and at which values shouldvoltages be implemented on a multiple-voltage dvs system toachieve the maximum energy saving. we refer this as the voltageset-up problem. in this paper, (1) we derive analytical solutionsfor dual-voltage system. (2) for the general case that does nothave analytic solutions, we develop efficient numerical methods.(3) we demonstrate how to apply the proposed algorithms onsystem design. (4) interestingly, the experimental results suggestthat the multiple-voltage dvs system, when the voltages are setup properly, can reach dvs techniqueýs full potential in energysaving. specifically, on the design of an ad hoc application-specificsystem and the design of the mpeg video encoder, wefind that the best single-voltage systems consume 150% and 20%more energy than the tight theoretical lower bounds, respectively.however, our approach gives dual-, 3-, and 4-voltage dvs systemsettings that are only 17.6%, 4.9%, and 2.6% for the ad hocsystem, and 4.0%, 1.1%, and 0.2% for the mpeg video encoder,over the same lower bounds.
automatic test program generation for pipelined processors. simulation-based verification has both advantages and disadvantages compared with formal verification. our demand is to find a practical way to verify actual microprocessors. this paper presents an efficient test program generation method for simulation-based verification using techniques developed for formal verification. our test program generator enumerates all reachable states of a processor pipeline and generates instruction sequences for every reachable test care. the program covers complicated test cases that are difficult to cover with random instructions and impossible to cover with conventional test program generation methods. our test program generator also works for larger microprocessor designs than formal verifiers have done.
ctl model checking based on forward state traversal. we present a ctl model checking algorithm based mainly on forward state traversal, which can check many realistic ctl properties without doing backward state traversal. this algorithm is effective in many situations where backward state traversal is more expensive than forward state traversal. we combine it with bdd-based state traversal techniques using partitioned transition relations. experimental results show that our method can verify actual ctl properties of large industrial models which cannot be handled by conventional model checkers.
generating instruction sets and microarchitectures from applications. the design of application-specific instruction set processor(asip) system includes at least three interdependent tasks: microarchitecture design, instruction set design, and instruction set mapping for the application. we present a method that unifies these three design problems with a single formulation: a modified scheduling/allocation problem with an integrated instruction formation process. micro-operations (mops) representing the application are scheduled into time steps. instructions are formed and hardware resources are allocated during the scheduling process. the assembly code for the given application is obtained automatically at the end of the scheduling process. this approach considers mop parallelism, instruction field encoding, delay load/store/branch, conditional execution of mops and the retargetability to various architecture templates. experiments are presented to show the power and limitation of our approach. performance improvement over our previous work is significant.
metamorphosis: state assignment by retiming and re-encoding. this paper presents metamorphosis -- a novel technique for optimal state assignment targeting multi-level logic implementations. we present an elegant matrix formulation and a graph partitioning based synthesis technique which permits both bit-constrained and unconstrained encoding of a symbolic finite state machine (fsm) represented initially with a one-hot code. optimal state encoding is achieved by controlled retiming/re-encoding and resynthesis of the symbolic fsm. the synthesis is guided directly by the cost function (optimization criterion) rather than speculative estimates of the encoding heuristics on the final design cost. the technique is illustrated through performance driven synthesis of fsm and extensions to handle other cost metrics is outlined.
compatible class encoding in roth-karp decomposition for two-output lut architecture. roth-karp decomposition is one of the most popular techniques for lut-based fpga technology mapping because it can decompose a node into nodes with fewer numbers of fanins. in this paper, we show how to formulate the compatible class encoding problem in roth-karp decomposition as a symbolic-output encoding problem in order to exploit the feature of the two-output lut architecture. based on this formulation, we also develop an encoding algorithm to minimize the number of lut's required to implement the logic circuit. experimental results show that our encoding algorithm can produce promising results in the logic synthesis environment for the two-output lut architecture.
an iterative area/performance trade-off algorithm for lut-based fpga technology mapping. in this paper, we propose an iterative area/performance trade-off algorithm for lut-based fpga technology mapping. first, it finds an area-optimized performance-considered initial network by a modified area optimization technique. then, an iterative algorithm consisting of several resynthesizing techniques is applied to trade the area for the performance in the network gracefully. experimental results show that this approach can provide a complete set of mapping solutions from the area-optimized one to the performance-optimized one for the given design. furthermore, these two extreme solutions, the area-optimized one and the performance-optimized one, produced by our algorithm outperform the results of most existing algorithms. therefore, our algorithm is very useful for the timing driven fpga synthesis.
phantom redundancy: a high-level synthesis approach for manufacturability. abstract: phantom redundancy, an area-efficient technique for fabrication-time reconfigurability is presented. phantom redundancy adds extra interconnect so as to render the resulting microarchitecture reconfigurable in the presence of any (single) functional unit failure. the proposed technique yields partially good chips in addition to perfect chips. a genetic algorithm is used to incorporate phantom redundancy constraints into microarchitecture synthesis. the algorithm minimizes tire performance degradation due to any faulty functional unit of the resulting microarchitecture. the effectiveness of the technique is illustrated on benchmark examples.
clock period minimization of non-zero clock skew circuits. it is known that the clock skew can be exploited as a manageableresource to improve the circuit performance. however, due to thelimitation of race condition, the optimal clock skew schedulingdoes not achieve the lower bound of the clock period. in thispaper, we propose a polynomial time complexity algorithm, whichincorporates optimal clock skew scheduling and delay insertion,for the synthesis of non-zero clock skew circuits. the mainadvantages of our algorithm include two parts. first, it guaranteesto achieve the lower bound of the clock period. secondly, it alsotries to minimize the required inserted delays under the lowerbound of the clock period. experimental data shows that, eventhough we only use the buffers in a standard cell library toimplement the delay insertion, our approach still works well.
power efficiency of voltage scaling in multiple clock, multiple voltage cores. due to increasing clock speeds, increasing design sizes and shrinking technologies, it is becoming more and more challenging to distribute a single global clock throughout a chip. in this paper we study the effect of using a globally asynchronous locally synchronous (gals) organization for a superscalar, out-of-order processor, both in terms of power and performance. to this end, we propose a novel modeling and simulation environment for multiple clock cores with static or dynamically variable voltages for each synchronous block. using this design exploration environment we were able to assess the power/performance tradeoffs available for multiple clock, single voltage (mcsv), as well as multiple clock, dynamic voltage (mcdv) cores. our results show that mcsv processors are 10% more power efficient when compared to single-clock single voltage designs with a performance penalty of about 10%. by exploiting the flexibility of independent dynamic voltage scaling the various clock domains, the power efficiency of gals designs can be improved by 12% on average, and up to 20% more in select cases. the power efficiency of mcdv cores becomes comparable with the one of single clock, dynamic voltage (scdv) cores, while being up to 8% better in some cases. our results show that mcdv cores consume 22% less power at an average 12% performance loss.
improving the proportion of at-speed tests in scan bist. a method to select the lengths of functional sequences in a bist scheme for scan designs is proposed in this paper. a functional sequence is a sequence of primary input vectors applied when the circuit operates as a sequential circuit, without using scan. these sequences can be applied at-speed, i.e., at the normal circuit clock speed. the objectives set for choosing the lengths of the functional sequences are to increase the number of vectors applied at-speed, and to reduce the number of settings of functional sequence lengths, without compromising the fault coverage achieved. the experimental results presented demonstrate that compared to earlier methods, the proposed method achieves the above objectives while also achieving higher fault coverages for most of the benchmark circuits considered.
satori - a fast sequential sat engine for circuits. we describe the design and implementation of satori - a fast sequentialjustification engine based on state-of-the-art sat and atpg techniques.we present several novel techniques that propel satori to ademonstrable 10x improvement over a commercial engine. traditionalsequential justification based on atpg or, on a bounded model of thesequential circuit using sat, has diverging strengths and weaknesses. inthis paper, we contrast these techniques and describe how their strengthsare combined in satori. we use conflict-based learning in each time-frameand illegal state learning across time-frames. this enables bothcombinational and sequential back-jumping. we experimentally analyzethe main features of satori by comparing satori's performanceagainst a state-of-the-art sat solver - zchaff using a boundedmodel, and a commercial sequential atpg engine performing justification.additional results are presented for satori versus the commercialatpg engine and vis on iscas ý89 and itc'99 benchmark circuitsfor an application to assertion checking.
achieving fast and exact hazard-free logic minimization of extended burst-mode gc finite state machines. this paper presents a new approach to two-level hazard-free logic minimization in the context of extended burst-mode finite state machine synthesis targeting generalized c-elements (gc). no currently available minimizers for literal-exact two-level hazard-free logic minimization of extended burst-mode gc controllers can handle large circuits without synthesis times ranging up over thousands of seconds. even existing heuristic approaches take too much time when iterative exploration over a large design space is required and do not yield minimum results. the logic minimization approach presented in this paper is based on state graph exploration in conjunction with single-cube cover algorithms, an approach that has not been considered for minimization of extended burst-mode finite state machines previously. our algorithm achieves very fast logic minimization by introducing compacted state graphs and cover tables and an efficient single-cube cover algorithm for single-output minimization. our exact logic minimizer finds minimal number of literal solutions to all currently available benchmarks, in less than one second on a 333 mhz microprocessor -- more than three orders of magnitude faster than existing literal exact methods, and over an order of magnitude faster than existing heuristic methods for the largest benchmarks. this includes a benchmark that has never been possible to solve exactly in number of literals before.