waashk/acm huggingface dataset:
an improved pass transistor synthesis method for low power, high speed cmos circuits  a synthesis method for generating hybrid pass gate circuits is presented. these circuits combine features from both complementary cmos and pass gates architectures. the simulation results using a 0.7 μm technology show that circuits synthesized according to the proposed method may achieve significant improvements in terms of area, power and delay over traditional full swing pass transistor logic and complementary cmos.  tudor vinereanu sverre lidholm
automated rip-up and reroute techniques  the ultimate goal of all automated routing systems is to interconnect 100% of the necessary point-to- point electrical connections. however, most automated routing systems fail to find acceptable paths for all required connections because of limited routing resources or problem complexity. therefore, a cleanup phase is often necessary. during this cleanup phase, connectivity can be improved through a variety of manual and automated techniques. this paper concentrates on one automated technique, rip-up and reroute. various rip-up and reroute strategies are discussed and evaluated, and experimental results are provided.  william a. dees patrick g. karger
decomposition methods for library binding of speed-independent asynchronous designs  we describe methods for decomposing gates within a speed- independent asynchronous design. the decomposition step is an essential part of the library binding process, and is used both to increase the granularity of the design for higher quality mapping and to ensure that the design can be implemented. we present algorithms for simple hazard-free gate decomposition, and show results which indicate that we can decompose most of the gates in our benchmark set by this simple method. we then extend these algorithms to work for those cases in which no simple decomposition exists.  polly siegel giovanni de micheli
power-aware design synthesis techniques for distributed real-time systems  this paper presents an end-to-end synthesis technique for low-power distributed real-time system design. this technique synthesizes supply voltages of resources to optimize system-level power consumption while satisfying end-to-end hard real-time latency bounds. a system is modeled as a set of distributed task chains (or pipelines). each task chain is given its own end-to-end constraints. task chains may share resources. our approach searches the space of the trade-off between end-to-end latency and supply voltages of resources to minimize system-level power consumption. a power optimization algorithm is proposed for simple distributed real-time systems that do not have any resource sharing between task chains, and its optimality is shown. for more general systems, a heuristic based on the same techniques is proposed.  dong-in kang stephen crago jinwoo suh
electronic chip-in-place test  electronic chip-in-place test (ecipt) is a design approach and a test methodology for vlsi packages containing multiple semi-conductor chips.  shift register latches are used in such a way that each chip on a package is accessible for testing from the package pins without in-circuit probing. a means is therefore provided, whereby tests generated for a chip can be reapplied at the package level. the ecipt methodology additionally provides a mechanism for simplified tests of failures associated with interchip wiring and chip i/o connections.  p. goel m. t. mcmahon
optimal latch mapping and retiming within a tree  we propose a technology mapping algorithm that takes existing structural technology-mapping algorithms based on dynamic programming and extends them to retime pipelined circuits. if the circuit to be mapped has a tree structure, our algorithm generates an optimal solution compatible with that structure. the algorithm takes into account gate delays and capacitive loads as latches are moved across the logic. it also supports latches with embedded logic: i.e., cells that combine a d latch with a combinational gate at little extra cost in latch delay.  joel grodstein eric lehman heather harkness herve touati bill grundmann
state assignment for hardwired vlsi control units  finding a binary encoding of symbolic control states, such that the implementation area of a digital control unit is minimized is well known to be np-complete. many heuristic algorithms have been proposed for this state assignment problem. the objective of this article is to present a comprehensive survey and systematic categorization of the various techniques, in particular, for synchronous sequential circuits with nonmicroprogrammed implementations. the problem is partitioned into the generation and the satisfaction of coding constraints. three types of coding constraints--- adjacency, covering, and disjunctive constraints---are widely used. the constraint satisfaction algorithms are classified into column-based, row- based, tree-based, dichotomy-based, and global minimization approaches. all of them are illustrated with examples. special coding requirements and testability-related aspects of state assignment are considered in a separate section. different implementations of the algorithms presented are also compared.  bernhard eschermann
rout: a design automation teaching tool  rout is a computer program written in fortran which simulates some of the characteristics of a mazerunning router for a two-layer printed circuit board. the objective of this program is not to actually route from-tos, but rather to aid in studying the effects of various wiring rules. for this reason, from-to points and wire segments are generated and placed using pseudo-random techniques. no actual connections are made. rather, congestion is developed on the board as if the pseudo-randomly generated from-tos had actually been routed. rout has been developed and implemented on the university of texas, austin's cdc cyber computer system for use in a graduate course in digital design automation.  kirti parmar robert j. smith
multiple-block ahead branch predictors a basic rule in computer architecture is that a processor cannot execute an application faster than it fetches its instructions. this paper presents a novel cost-effective mechanism called the two-block ahead branch predictor. information from the current instruction block is not used for predicting the address of the next instruction block, but rather for predicting the block following the next instruction block.this approach overcomes the instruction fetch bottle-neck exhibited by wide- dispatch "brainiac" processors by enabling them to efficiently predict addresses of two instruction blocks in a single cycle. furthermore, pipelining the branch prediction process can also be done by means of our predictor for "speed demon" processors to achieve higher clock rate or to improve the prediction accuracy by means of bigger prediction structures.moreover, and unlike the previously-proposed multiple predictor schemes, multiple-block ahead branch predictors can use any of the branch prediction schemes to perform the very accurate predictions required to achieve high-performance on superscalar processors. andre seznec stephan jourdan pascal sainrat pierre michaud
simulation of digital circuits in the presence of uncertainty  current extended value set dynamic timing analyzers are not sophisticated enough to detect the subtle timing relationships upon which timing-critical systems depend, and exhaustive simulation achieves very accurate results but at tremendous computational cost. mtv is a simulator that strikes a balance between accuracy and efficiency.  mtv is more accurate than other extended value set simulators because it respects the ordering of events. it is more efficient than exhaustive simulators because it efficiently simulates overlapping events and requires only a single waveform to represent a signal. features of mtv include: elimination of common ambiguity, symbolic delays, correlated delays, and sophisticated algorithms to detect ordered events. this paper concludes with simulation results from the iscas85 benchmark suite.  mark linderman miriam leeser
a new approach to derive robust sets for stuck-open faults in cmos combinational logic circuits  in this paper, we address the problem of deriving robust tests for single stuck-open faults in cmos combinational circuits. we first examine the characteristics of the transition of the two patterns belonging to a two- pattern test. then, a sufficient and necessary condition for a test to be robust is given. according to the given condition, we propose a new method to derive robust tests. robustness verification of the derived tests is no longer required when using our approach.  j. f. wang t.-y. kuo j.-y. lee
co-design of interleaved memory systems  memory interleaving is a cost-efficient approach to increase bandwidth. improving data access locality and reducing memory access conflicts are two important aspects to achieve high efficiency for interleaved memory. in this paper, we introduce a design framework that integrates these two optimizations, in order to find out minimal memory banks and channels required in the embedded system under performance restriction. several important techniques, loop and data layout transformations for data access locality, extracting data streams, conflict cache miss reduction as well as data placement and optimally reordered access for interleaved memories, are incorporated in the design framework. experiments show that our co-design method results in substantially less hardware requirement compared to the implementations without optimization.  hua lin wayne wolf
circular self-test path: a low-cost bist technique  a new technique for designing self-testing vlsi circuits, referred to as circular self-test path, is presented the circular self-test path is a feedback shift register (output of the last flip-flop is supplied to the first flip-flop) with a data compaction capability. a distinguishing attribute of self-testing chips designed using this technique is a low silicon area overhead, slightly exceeding that of scan path designs. a theoretical analysis and comprehensive simulation experiments we performed to demonstrate that the effectiveness of test pattern generation for the circular self-test path is comparable to that of an ideal pseudorandom test generator.  a. krasniewski s. pilarski
run-time defect tolerance using jbits  the ability to tolerate defects in semiconductor devices has the potential for both increasing yields of devices being manufactured and making it economically feasible to manufacture even larger devices. while fpga devices appear to be well suited to providing defect tolerance, practical application of existing research and techniques has been somewhat elusive. one barrier to acceptance is that existing defect tolerance techniques for fpgas have tended to rely on either modifications to device architectures or modifications to design tools. we describe a software- based technique for providing defect tolerance which requires neither changes to device hardware or software tools. this approach uses the xilinx jbits$^{(tm)}$ toolkit and operates at the core library level. addressing defect tolerance locally using core library elements rather than taking a global approach helps provide direct support for run-time reconfiguration. circuits may be configured and reconfigured rapidly in the presence of these defects. this rapid configuration also provides a path for practical use in more traditional manufacturing environments.  prasanna sundararajan steven a. guccione
folding and unrolling systolic arrays (preliminary version)  this paper is about two constructions for transforming planar systolic arrays. by a systolic array we mean a uniformly structured processor configuration that allows only local communication (between neighbour processors) and supports high throughout by pipelining. such configurations are suitable for vlsi implementation [4, 5].  we show how new connections in a systolic array can be established by folding the array along a line; and how computations in one-dimensional arrays unroll to two-dimensional structures resembling trellis automata [2]. we construct systolic arrays for computing large powers of a matrix; for matching keywords; for recognizing square-free words; and for finding the controlled product of matrices.  k. culik j. pachl
relax: a new circuit for large scale mos integrated circuits  algorithms and techniques used in relax are described. relax is a time domain mos digital circuit simulator based on a new analysis method called waveform relaxation method [1] which exploits decomposition techniques. preliminary comparisons between relax and the standard circuit simulator spice2 have shown that relax is a fast and reliable circuit simulator.  e. lelarasmee a. sangiovanni-vincentelli
high-speed dynamic logic styles for scaled-down cmos and mtcmos technologies  a new high-speed domino circuit, called hs-domino is developed. hs- domino resolves the trade-off between performance and noise margins in conventional cd-domino logic while dissipating low dynamic power with minimal area overhead. a dual-threshold (mtcmos) implementation of hs-domino and ddcvs logic is also devised. this implementation achieves low leakage values during standby, while maintaining high performance and lowdynamic power during the active mode.  mohamed w. allam mohab h. anis mohamed i. elmasry
a method of delay fault test generation  it has been observed that random testing for delay faults can result in test sets of excessive length and high simulation costs. consequently, we propose an efficient deterministic method of delay fault test generation. for most common circuits, our proposed technique has a time complexity which is polynomial in the size of the circuit, as opposed to existing deterministic methods which, for nearly all circuits, are exponential. we define a type of transition path, the fully transitional path, ftp, and demonstrate that it has several useful properties. an ftp can be created by applying a vector pair derived from a stuck-at test for a primary input, a technique introduced in [1]. we extend this method by using an alternate representation for switching functions, the binary decision diagram, to generate graphs representing stuck- at tests. the concept of free variables is defined as a tool for deriving several ftps from one stuck-at test. preliminary results are presented which indicate that our method provides a higher robust delay fault coverage than psuedorandom patterns at less than one-fifth the cost. also, since vector pairs cannot be applied to combinational circuits using standard scan design, a simple scannable latch is introduced to facilitate this task.  c. thomas glover m. ray mercer
bifest: a built-in intermediate fault effect sensing and test generation system for cmos bridging faults  this paper presents bifest, an atpg system that employs the built-in intermediate voltage test technique in an efficient atpg process to deal with cmos bridging faults. fast and accurate calculations of the intermediate bridging voltages and the variant threshold tolerance margins on a resistive bridging fault model are presented. a podem- like, ppsfp-based atpg process is developed to generate test patterns for faults that are conventionally logic- testable. the remaining faults are then dealt with by special circuits, called built-in intermediate voltage sensors (bivss). by this methodology, almost the same fault coverage as that employing iddq testing can be achieved with only logic monitoring required.  kuen-jong lee jing- jou tang tsung-chu huang
fractal symbolic analysis  modern compilers perform wholesale restructuring of programs to improve their efficiency. _dependence analysis_ is the most widely used technique for proving the correctness of such transformations, but it suffers from the limitation that it considers only the memory locations read and written by a statement, and does not assume any particular interpretation for the operations in that statement. exploiting the semantics of these operations permits more transformations to be proved correct, and is critical for automatic restructuring of codes such as lu with partial pivoting.  one approach to exploiting the semantics of program operations is _symbolic analysis and comparison_ of programs. in principle, this technique is very powerful, but in practice, it is intractable for all but the simplest programs.  in this paper, we propose a new form of symbolic analysis and comparison of programs which is appropriate for use in restructuring compilers. _fractal_ symbolic analysis compares a program and its transformed version by repeatedly simplifying these programs until symbolic analysis becomes tractable while ensuring that equality of the simplified programs is sufficient to guarantee equality of the original programs.  fractal symbolic analysis combines some of the power of symbolic analysis with the tractability of dependence analysis. we discuss a prototype implementation of fractal symbolic analysis, and show how it can be used to solve the long- open problem of verifying the correctness of transformations required to improve the cache performance of lu factorization with partial pivoting.  nikolay mateev vijay menon keshav pingali
synthesis for fpgas with embedded memory blocks  embedded memory blocks (embs) are used in modern field programmable gate arrays (fpgas) for implementation of on-chip memories or specialized logic functions[1]. in this paper, we propose an integrated approach with structural clustering and functional decomposition to minimize the circuit area using embs while preserving the circuit delay. the structural clustering method is based on the concepts of maximum fanout free cone (mffc)[5] and maximum fanout free subgraph (mffs)[5]. in order to effectively use emb in large clusters, single- output and multiple-output functional decompositions are used to decompose large clusters so that the encoding functions or base functions can be implemented by embs. it also considers multiple embs for individual large cluster so that better area reduction can be obtained. we have developed an algorithm called emb_syn that can be used as a postprocessing tool in the fpga synthesis flow. mcnc benchmarks are used to test emb_syn on altera's flex10k device family and the experimental results are compared with those by emb_pack[8] and smap[10]. when emb_syn is used as postmapping processing, it shows 45.06% and up to 5.23% improvements over emb_pack and smap, respectively, in terms of the covered area by embs.  jason cong kenneth yan
inexpensive implementations of set-associativity  the traditional approach to implementing wide set-associativity is expensive, requiring a wide tag memory (directory) and many comparators. here we examine alternative implementations of associativity that use hardware similar to that used to implement a direct-mapped cache. one approach scans tags serially from most- recently used to least-recently used. another uses a partial compare of a few bits from each tag to reduce the number of tags that must be examined serially. the drawback of both approaches is that they increase cache access time by a factor of two or more over the traditional implementation of set- associativity, making them inappropriate for cache designs in which a fast access time is crucial (e.g. level one caches, caches directly servicing processor requests).  these schemes are useful, however, if (1) the low miss ratio of wide set- associative caches is desired, (2) the low cost of a direct-mapped implementation is preferred, and (3) the slower access time of these approaches can be tolerated. we expect these conditions to be true for caches in multiprocessors designed to reduce memory interconnection traffic, caches implemented with large, narrow memory chips, and level two (or higher) caches in a cache hierarchy.  r. e. kessler r. jooss a. lebeck m. d. hill
chip layout optimization using critical path weighting  a chip layout procedure for optimizing the performance of critical timing paths in a synchronous digital circuit is presented. the procedure uses the path analysis data produced by a static timing analysis program to generate weights for critical nets on clock and data paths. these weights are then used to bias automatic placement and routing in the layout program. this approach is shown to bring the performance of the chip significantly closer to that of an ideal layout which is assumed to have no delay due to routing between cells.  a. e. dunlop v. d. agrawal d. n. deutsch m. f. jukl p. kozak m. wiesel
on error correction in macro-based circuits  we consider the problem of correcting errors in a macro-based circuit. our formulation of the problem allows the correction of errors that arise both in the context of design error correction, before the circuit is realized, and in the context where a physical circuit needs to be corrected. two error classes are defined, namely, component errors and line errors. both single and multiple errors are considered. accurate correction procedures are given for single errors. heuristics are given for correcting multiple errors. experimental results are given to demonstrate the correction procedures presented.  irith pomeranz sudhakar m. reddy
podem-x: an automatic test generation system for vlsi logic structures  multiple test generation algorithms and techniques described in this paper have been integrated into a unified system which has successfully produced tests for unpartitioned lssd logic structures of up to 50,000 logic gates. the design concepts behind the creation of a unified system are presented, as are actual results obtained on large logic structures. system usability was significantly enhanced by the same concepts that facilitated the integration of multiple algorithms and techniques.  prabhakar goel barry c. rosales
experimental evaluation of on-chip microprocessor cache memories  advances in integrated circuit density are permitting the implementation on a single chip of functions and performance enhancements beyond those of a basic processors. one performance enhancement of proven value is a cache memory; placing a cache on the processor chip can reduce both mean memory access time and bus traffic. in this paper we use trace driven simulation to study design tradeoffs for small (on-chip) caches. miss ratio and traffic ratio (bus traffic) are the metrics for cache performance. particular attention is paid to sub-block caches (also known as sector caches), in which address tags are associated with blocks, each of which contains multiple sub-blocks; sub-blocks are the transfer unit. using traces from two 16-bit architectures (z8000, pdp-11) and two 32-bit architectures (vax-11, system/370), we find that general purpose caches of 64 bytes (net size) are marginally useful in some cases, while 1024-byte caches perform fairly well; typical miss and traffic ratios for a 1024 byte (net size) cache, 4-way set associative with 8 byte blocks are: pdp-11: .039, .156, z8000: .015, .060, vax 11: .080, .160, sys/370: .244, .489. (these figures are based on traces of user programs and the performance obtained in practice is likely to be less good.) the use of sub-blocks allows tradeoffs between miss ratio and traffic ratio for a given cache size. load forward is quite useful. extensive simulation results are presented.  mark d. hill alan jay smith