waashk/acm huggingface dataset:
fault dictionary compaction by output sequence removal  fault dictionary compaction has been accomplished in the past by removing responses on individual output pins for specific test vectors. in contrast to the previous work, we present techniques for eliminating entire sequences of outputs and for efficiently storing the remaining output sequences. experimental results on the iscas 85 and iscas 89 benchmark circuits show that the sizes of dictionaries proposed are substantially smaller than the full fault dictionary, while the dictionaries retain most or all of the diagnostic capability of the full fault dictionary.  vamsi boppana w. kent fuchs
design and algorithms for parallel testing of random access and content addressable memories  this paper presents a design strategy for efficient and comprehensive parallel testing of both random access memory (ram) and content addressable memory (cam). based on this design for testability approach, parallel testing algorithms for cams and rams are developed for a broad class of pattern sensitive faults. the resulting test procedures are significantly more efficient than previous approaches. for example, the design for testability strategy allows an entire w word cam to be read in just one operation with a resulting speed up in testing as high as w. in the case of an n bit ram, the improvement in test efficiency is by a factor of ( n). the overall reduction in testing time is considerable for large size memories.  p. mazumder j. h. patel w. k. fuchs
an integrated mask artwork analysis system  a new lsi artwork analysis and processing system, called emap, is described with algorithms, a database schema and applications. emap provides the designer with the artwork verification and processing tools which include mask artwork processing, geometrical design rule checking, connectivity analysis and electrical circuit parameter calculation. the circuit connectivity data derived from the mask artwork data is used for input to a logic simulator, a timing simulator, a circuit simulator and a circuit schematic generator.  takashi mitsuhashi toshiaki chiba makoto takashima kenji yoshida
algorithms for library-specific sizing of combinational logic  we examine the problem of choosing the proper sizes from a cell library for the logic elements of a boolean network to meet timing constraints on the propagation delay along every path from the primary input to the primary output. if the boolean network has a tree topology, we show that there exists a pseudo-polynomial time algorithm for finding the optimal solution to this problem. a backtracking-based algorithm for finding feasible solutions for networks that are not trees is also suggested and evaluated.  pak k. chan
on driving many long wires in a vlsi layout  it is assumed that long wires represent large capacitive loads, and the effect on the area of a vlsi layout when drivers are introduced along many long wires in the layout is investigated. a layout is presented for which the introduction of standard drivers along long wires squares the area of the layout; it is shown, however, that the increase in area is never greater than the layout's area squared if the driver can be laid out in a square region. this paper also shows an area-time trade-off for the driver of a single long wire of length / by which the area of the driver from (l), to (lq), q < l, can be reduced if a delay of (ll-q) rather than (log l) can be tolerated. tight bounds are also obtained on the worst-case area increase in general layouts having these drivers.  vijaya ramachandran
fast implementations of secret-key block ciphers using mixed inner- and outer- round pipelining  the new design methodology for secret-key block ciphers, based on introducing an optimum number of pipeline stages inside of a cipher round is presented and evaluated. this methodology is applied to five well-known modern ciphers, triple des, rijndael, rc6, serpent, and twofish, with the goal to first obtain the architecture with the optimum throughput to area ratio, and then the architecture with the highest possible throughput. all ciphers are modeled in vhdl, and implemented using xilinx virtex fpga devices. it is demonstrated that all investigated ciphers can operate with similar maximum clock frequencies, in the range from 95 to 131 mhz, limited only by the delay of a single clb layer and delays of interconnects. rijndael, rc6, twofish, and serpent achieve throughputs in the range from 12.1 gbit/s to 16.8 gbit/s; and triple des achieves the throughput of 7.5 gbit/s. because of the optimum speed to cost ratio, the proposed architecture seems to be very well suited for practical implementations of secret-key block ciphers using both fpgas and custom asics. we also show that using this architecture for comparing hardware performance of secret-key block ciphers, such as aes candidates, operating in non-feedback cipher modes, leads to the more prudent and fairer analysis than comparisons based on other types of pipelined architectures.  pawel chodowiec po khuon kris gaj
a fast algorithm for minimizing fpga combinational and sequential modules  we present a quadratic-time algorithm for minimizing the number of modules in an fpga with combinational and sequential modules (like the c-modules and s-modules of the act2 and act3 architectures). the constraint is that a combinational module can be combined with one flip-flop in a single sequential module, only if the combinational module drives no other combinational modules. our algorithm uses a minimum-cost flow formulation to solve the problem with a significant time improvement over a previous approach that used a general linear program.  dimitrios kagaris spyros tragoudas
design and verification of the rollback chip using hop: a case study of formal methods applied to hardware design  the use of formal methods in hardware design improves the quality of designs in many ways: it promotes better understanding of the design; it permits systematic design refinement through the discovery of invariants; and it allows design verification (informal or formal). in this paper we illustrate the use of formal methods in the design of a custom hardware system called the "rollback chip" (rbc), conducted using a simple hardware design description language called "hop". an informal specification of the requirements of the rbc is first given, followed by a behavioral description of the rbc stating its desired behavior. the behavioral description is refined into progressively more efficient designs, terminating in a structural description. key refinement steps are based on system invariants that are discovered during the design, and proved correct during design verification. the first step in design verification is to apply a program called parcomp to derive a behavioral description from the structural description of the rbc. the derived behavior is then compared against the desired behavior using equational verification techniques. this work demonstrates that formal methods can be fruitfully applied to a nontrivial hardware design. it also illustrates the particular advantages of our approach based on hop and parcomp. last, but not the least, it formally verifies the rbc mechanism itself  . ganesh gopalakrishnan richard fujimoto
functional design for testability of control-dominated architectures  control-dominated architectures are usually described in a hardware description language (hdl) by means of interacting fsms. a vhdl or verilog specification can be translated into an interacting fsm (ifsm) representation as described here. the ifsm model allows us to approach the testable synthesis problem at the level of each fsm. the functionality is modified by the addition of transparency to data flow. the complete testability of the ifsm implementation is thus achieved by connecting fully testable implementations of each modified fsm. in this way, test sequences separately generated for each fsm are directly applied to the ifsm to achieve complete fault coverage. the addition of test functionality to each fsm description, and its simultaneous synthesis with the fsm functionality, produces a lower area overhead than that necessary for the application of a partial-scan technique. moreover, the test generation problem is highly simplified since it is reduced to the test generation for each separate fsm.  f. fummi u. rovati d. sciuto
test generation costs analysis and projections  empirical observations are used to derive analytic formulae for test volumes, parallel fault simulation costs, deductive fault simulation costs, and minimum test pattern generation costs for lssd logic structures. the formulae are significant in projecting growth trends for test volumes and various test generation costs with increasing gate count g. empirical data is presented to support the thesis that test volume grows linearly with g for lssd structures that cannot be partitioned into disjoint substructures. such lssd structures are referred to as "coupled" structures. based on empirical observation that the number of latches in an lssd logic structure is proportional to the gate count g, it is shown that the logic test time for coupled structures grows as g2. it is also shown that (i) parallel fault simulation costs grow as g3, (ii) deductive fault simulation costs grow as g2, and (iii) the minimum test pattern generation costs grow as g2. based on these projections some future testing problems become apparent.  prabhakar goel
design for testability  this presentation will discuss the basics of design for testability. a short review of testing is given along with some reasons why one should test. the different techniques of design for testability are discussed in detail. these include techniques which can be applied to today's technologies and techniques which have been recently introduced and will soon appear in new designs. these techniques include the three main areas of design for testability, 1) ad hoc approaches; 2) structured approaches; and, 3) self test/built-in test approaches.  t. w. williams
power-delay optimizations in gate sizing  the problem of power-delay tradeoffs in transistor sizing is examined using a nonlinear optimization formulation. both the dynamic and the short-circuit power are considered, and a new modeling technique is used to calculate the short-circuit power. the notion of transition density is used, with an enhancement that considers the effect of gate delays on the transition density. when the short-cuircuit power is neglected, the minimum power circuit is idential to the minimum area circuit. however, under our more realistic models, our experimental results on several circuits show that the minimum power circuit is not necessarily the same as the minimum area circuit.  sachin s. sapatnekar weitong chuang
a concept for test and reconfiguration of a fault-tolerant vlsi processor system  the following paper is to present a test and reconfiguration strategy for fault-tolerant vlsi processor systems. this is accomplished with respect to the requirements imposed by the vlsi technology. the proposed concept is exemplified by a model composed of four microprogrammable processors each with a local memory. the test strategy of a gradually expanding hardcore is applied where the central hardcore consists of a small test unit of low complexity. this test unit enables each processor to diagnose autonomously its data path structure and its associated local memory. a particular reconfiguration scheme is proposed for these components. it is implemented at microprogram level. as a result, compared with other fault- tolerance techniques, system reliability is considerably improved.  k. e. grosspietsch j. kaiser e. nett
synthesis of hazard-free multi-level logic under multiple-input changes from binary decision diagrams  we describe a new method for directly synthesizing a hazard-free multilevel logic implementation from a given logic specification. the method is based on free/ordered binary decision diagrams (bdd's), and is naturally applicable to multiple-output logic functions. given an incompletely-specified (multiple- output) boolean function, the method produces a multilevel logic network that is hazard-free for a specified set of multiple-input changes. we assume an arbitrary (unbounded) gate and wire delay model under a pure delay (pd) assumption, we permit multiple-input changes, and we consider both static and dynamic hazards. this problem is generally regarded as a difficult problem and it has important applications in the field of asynchronous design. the method has been automated and applied to a number of examples. the results we have obtained are very promising.  bill lin srinivas devadas
a new efficient approach to statistical delay modeling of cmos digital combinational circuits  this paper presents one of the first attempts to statistically characterize signal delays of basic cmos digital combinatorial circuits using the transistor level approach. hybrid analytical/iterative delay expressions in terms of the transistor geometries and technological process variations are created for basic building blocks. local delays of blocks along specific signal paths are combined together for the analysis of complex combinational vlsi circuits. the speed of analysis is increased by 2 to 4 orders of magnitude relative to spice, with about 5--10% accuracy. the proposed approach shows good accuracy in modeling the influence of the "noise" parameters on circuit delay relative to direct spice-based monte carlo analysis. examples of statistical delay characterization are shown. the important impact of the proposed approach is that statistical evaluation and optimization of delays in much larger vlsi circuits will become possible.  syed a. aftab m. a. styblinski
java consistency: nonoperational characterizations for java memory behavior  the java language specification (jls) [gosling et al. 1996] provides an operational definition for the consistency of shared variables. the definition remains unchanged in the jls 2nd edition, currently under peer review, which relies on a specific abstract machine as its underlying model, is very complicated. several subsequent works have tried to simplify and formalize it. however, these revised definitions are also operational, and thus have failed to highlight the intuition behind the original specification. in this work we provide a complete nonoperational specification for java and for the jvm, excluding synchronized operations. we provide a simpler definition, in which we clearly distinguish the consistency model that is promised to the programmer from that which should be implemented in the jvm. this distinction, which was implicit in the original definition, is crucial for building the jvm. we find that the programmer model is strictly weaker than that of the jvm, and precisely define their discrepancy. moreover, our definition is independent of any specific (or even abstract) machine, and can thus be used to verify jvm implementations and compiler optimizations on any platform. finally, we show the precise range of consistency relaxations obtainable for the java memory model when a certain compiler optimization--- called prescient stores in jls---is applicable.  alex gontmakher assaf schuster
the architecture and operational characteristics of the vmx host machine  the vmx host machine is a hardware-firmware environment for implementation of actual computer systems with a favorable price performance ratio. the article presents the host framework architecture, together with all units which are used to build actual systems. the advantages and future potential of the architecture is briefly discussed. the notion of memory directives within the frame-work of an active (or "intelligent") memory unit is introduced. this notion serves as one example of the possibilities that are built into the architecture of the vmx host.  gideon frieder
predicting the usefulness of a block result: a micro-architectural technique for high-performance low-power processors  this paper proposes a micro-architectural technique in which a prediction is made for some power-hungry units of a processor. the prediction consists of whether the result of a particular unit or block of logic will be useful in order to execute the current instruction. if it is predicted useless, then that block is disabled.  it would be ideal if the predictions were totally accurate, thus not decreasing the instruction- per-cycle (ipc) performance metric. however, this is not the case: the ipc might be degraded which in turn may offset the power savings obtained with the predictors due to the extra cycles to complete the execution of the application being run on the processor.  in general, some logic may determine which of the block(s) that have a predictor associated will be disabled based on the outcome of the predictors and possibly some other signals from the processor. the overall processor power consumption reduction is a function of how accurate the predictors are, what percentage of the total processor power consumption corresponds to the blocks being predicted, and how sensitive to the ipc the different blocks are.  a case example is presented where two blocks are predicted for low power: the on-chip l2 cache for instruction fetches, and the branch target buffer. the ipc vs power- consumption design space is explored for a particular micro- processor architecture. both the average and the peak power consumption are targeted. although the power analysis is beyond the scope of this paper, high- level estimations are done to show that it is plausible that the ideas described might produce a significant reduction in useless block accesses. clearly, this reduction may be exploited to reduce the power consumption demands of high- performance processors.  enric musoll
swami: a flexible logic implementation system  a new system for logic synthesis and vlsi layout, the stanford weinberger array minimizer and implementor (swami), has been developed. this paper describes the system's algorithms and presents preliminary results. the minimization of logic expressions uses local sum-of-products minimization, kernel factorization and common subexpression recognition and generates improved expressions of arbitrary depth. logic expressions are realized in nmos technology using one dimensional weinberger array structures or a new extension of weinberger arrays to two dimensions. the placement phase uses heuristic techniques, including simulated annealing. min-cut linear arrangement and local constructive clustering.  christopher rowen john l. hennessey
apss: an automatic pla synthesis system  an integrated, fully automatic software capability that combines boolean logic translation, boolean minimization, pla folding, pla topology generation, and automatic pla subchip interfacing to the mp2d standard cell automatic placement and routing program in a single, modular software package is described. written in ansi standard fortran, apss permits the designer to input either arbitrarily formed boolean equations or a truth table, and to receive a complete mp2d-compatible pla subchip layout with automatically personalized mp2d subchip interfacing data, as output. as with mp2d, this capability is largely independent of technology and circuit implementation, requiring only an appropriate technology file and cell library consistent with the chosen pla layout style or "floor plan."  m. w. stebnisky m. j. mcginnis j. c. werbickas r. n. putatunda a. feller
optimal test access architectures for system-on-a-chip  test access is a major problem for core-based system-on-a-chip (soc) designs. since embedded cores in an soc are not directly accessible via chip inputs and outputs, special access mechanisms are required to test them at the system level. an efficient test access architecture should also reduce test cost by minimizing test application time. we address several issues related to the design of optimal test access architectures that minimize testing time., including the assignment of cores to test buses, distribution of test data width between multiple test buses, and analysis of test data width required to satisfy an upper bound on the testing time. even though the decision versions of all these problems are shown to be np-complete, they can be solved exactly for practical instances using integer linear programming (ilp). as a case study, the ilp models for two hypothetical but nontrivial systems are solved using a public-domain ilp software package.  krishnendu chakrabarty
unified complete mosfet model for analysis of digital and analog circuits  in this paper, we describe the complete mosfet model developed for circuit simulations. the model describes all transistor characteristics as functions of surface potentials, which are calculated iteratively at each applied voltage under the charge-sheet approximation. the key idea of this development is to put as much physics as possible into the equations describing the surface potentials. since the model includes both the drift and the diffusion contributions, a single equation is valid from the subthreshold to the saturation regions. the unified treatment of our model allows all transistor characteristics to be calculated without any nonphysical fitting parameters. additionally the calculation time is drastically reduced in comparison with a conventional piece-wise model.  m. miura-mattausch u. feldmann a. rahm m. bollu d. savignac
simultaneous functional-unit binding and floorplanning  as device feature size decreases, interconnection delay becomes the dominating factor of system performance. thus it is important that accurate physical information is used during high level synthesis. in this paper, we consider the problem of simultaneously performing functional-unit binding and floorplanning. experimental results indicate that our approach to combine binding and floorplanning is superior to the traditional approach of separating the two tasks.  yung-ming fang d. f. wong
model and analysis for combined package and on-chip power grid simulation  we present new modeling and simulation techniques to improve the accuracy and efficiency of transient analysis of large power dis?bution grids. these include an accurate model for the inherent decoupling capacitance of non- switching devices, as well as a sta?tical switching current model for the switching devices. more?r, three new simulation techniques are presented for problem size-reduction and speed-up. results of application of these tech?ues on three powerpctmmicroprocessors are also presented.  rajendran panda david blaauw rajat chaudhry vladimir zolotov brian young ravi ramaraju
scheduling designs into a time-multiplexed fpga  an algorithm is presented for partitioning a design in time. the algorithm devides a large, technology-mapped design into multiple configurations of a time-multiplexed fpga. these configurations are rapidly executed in the fpga to emulate the large design. the tool includes facilities for optimizing the partitioning to improve routability, for fitting the design into more configurations than the depth of the critical path and for compressing the critical path of the design into fewer configurations, both to fit the design into the device and to improve performance. scheduling results are shown for mapping designs into an 8-configuration time-multiplexed fpga and for architecture investigation for a time-multiplexed fpga.  steve trimberger