waashk/acm huggingface dataset:
speeding up symbolic model checking by accelerating dynamic variable reordering  symbolic model checking is a widely used technique in sequential verification. as the size of the obdds and also the computation time depends on the order of the input variables, the verification may only succeed if a well suited variable order is chosen. since the characteristics of the represented functions are changing, the variable order has to be adapted dynamically. unfortunately, dynamic reordering strategies are often very time consuming and sometimes do not provide any improvement of the obdd representation. this paper presents adaptions of reordering techniques originally intended for combinatorial verification to the specific requirements of symbolic model checking. the techniques are orthogonal in the way that they use either structural information about the obdds or semantical information about the represented functions. the application of these techniques substantially accelerates the reordering process and makes it possible to finish computations, that are too time consuming, otherwise.  christoph meinel christian stangier
design aids for the simulation of bipolar gate arrays  this paper describes a system of design aids which are used in the modeling and simulation of bipolar gate arrays for applications where the delays cannot be neglected. prewired function blocks composed of circuit elements such as transistors, resistors, diodes, etc. are automatically converted to logic gate descriptions. the transistor level model of a function block is analyzed with a circuit simulation program to obtain delay values for the gate level model. the gate equivalent circuits and the delay values produced by these methods provide accurate digital simulation of bipolar gate arrays.  p. kozak a. k. bose a. gupta
low-cost single-layer clock trees with exact zero elmore delay skew  we give the first single-layer clock tree construction with exact zero skew according to the elmore delay model. the previous linear-planar-dme method guarantees a planar solution under the linear delay model. in this paper, we use a linear-planar-dme variant connection topology to construct a low-cost zero skew tree (zst) according to the elmore delay model. while a linear-delay zst is trivially converted to an elmore-delay zst by "detouring" wires, the key idea is to defer this detouring as much as possible to reduce tree cost. costs of our planar zst solutions are comparable to those of the best previous non-planar zst solutions, and substantially improve over previous planar clock routing methods.  andrew b. kahng chung-wen albert tsao
differential fault simulation - a fast method using minimal memory  a new, fast fault simulator called differential fault simulator, dsim, for sequential circuits is described. unlike the concurrent fault simulation, dsim simulates each machine by simulating its machine differences from the other machine just simulated instead of simulating its input differences from the previous status of the same machine. in this manner, dsim simulates each machine (good or bad) separately for every test vector. therefore, dsim dramatically reduces the dynamic memory requirement and the overhead in the memory management in the concurrent fault simulation. also unlike the single fault propagation which simulates each bad machine by simulating its machine difference from the good machine, the overhead to restore the good machine status before each bad machine simulation is eliminated in dsim. our experiments show that dsim runs 3-12 times faster than an existing concurrent fault simulator and an experimental single fault propagation simulator. furthermore, owing to the straightforward operations, dsim is very easy to implement and maintain. implementation consists of less than 300 lines of "c" language statements added to the event-driven true- value simulator in an existing sequential test generation system, stg. currently dsim uses a zero- delay timing model, while inclusion of other delay models is under development.  w.-t. cheng m.-l. yu
dynamic vectorization: a mechanism for exploiting far-flung ilp in ordinary programs several ilp limit studies indicate the presence of considerable ilp across dynamically far-apart instructions in program execution. this paper proposes a hardware mechanism, _dynamic vectorization (dv),_ as a tool for quickly building up a large logical instruction window. dynamic vectorization converts repetitive dynamic instruction sequences into vector form, enabling the processing of instructions from beyond the corresponding program loop to be overlapped with the loop. this enables vector-like execution of programs with relatively complex static control flow that may not be amenable to static, compile time vectorization. experimental evaluation shows that a large fraction of the dynamic instructions of four of the six specint92 programs can be captured in vector form. three of these programs exhibit significant potential for ilp improvements from dynamic vectorization, with speedups of more than a factor of 2 in a scenario of realistic branch prediction and perfect memory disambiguation. under perfect branch prediction conditions, a fourth program also shows well over a factor of 2 speedup from dv. the speedups are due to the overlap of post-loop processing with loop processing. sriram vajapeyam p. j. joseph tulika mitra
a crosstalk-aware timing-driven router for fpgas  as integrated circuits are migrated to more advanced technologies, it has become clear that crosstalk is an important physical phenomenon that must be taken into account. crosstalk has primarily been a concern for asics, multi- chip modules, and custom chips, however, it will soon become a concern in fpgas. in this paper, we describe the first published crosstalk-aware router that targets fpgas. we show that, in a representative fpga architecture implemented in a 0.18mm technology, the average routing delay in the presence of crosstalk can be reduced by 7.1% compared to a router with no knowledge of crosstalk. about half of this improvement is due to a tighter delay estimator, and half is due to an improved routing algorithm.  steven j. e. wilton
the hughes automated layout system - automated lsi/vlsi layout based on channel routing  the hughes automated layout system (hal) is intended to provide fast, accurate, and efficient layout of lsi/vlsi circuits. the hal development plan calls for an evolutionary development in three phases, with each phase providing a usable design system. hal(i) is limited to standard cell layout and is now operational. hal(ii), which will permit more complex geometries, and hal(iii), which will add hierarchical capabilities, are in initial development. this paper discusses the features of hal(i), and the concepts of decomposition and ordering of routing domains that underlie the more advanced systems.  g. persky c. enger d. m. selove
transmission gate modeling in an existing three-value simulator  existing three value (0, 1, x,) logic simulators cannot support the use of mos transmission gates, but this deficiency can be easily eliminated by the addition of one logic value - the high impedance (z) state. this paper demonstrates that complete transmission gate modeling, including bi- directional operation and ratio logic, can be accomplished with this single z state and explicit node models; and, since four states require the same internal storage as three states, such an enhancement would not require a major software rewrite.  robert m. mcdermott
multiway fpga partitioning by fully exploiting design hierarchy  in this paper, we present a new integrated synthesis and partitioning method for multiple-fpga applications. our approach bridges the gap between hdl synthesis and physical partitioning by fully exploiting the design hierarchy. we propose a novel multiple-fpga synthesis and partitioning method which is performed in three phases: (1) fine-grained synthesis, (2) functional-based clustering, and (3) hierarchical set-covering partitioning. this method first synthesizes a design specification in a fine-grained way so that functional clusters can be preserved based on the structural nature of the design specification. then, it applies a hierarchical set-covering partitioning method to form the final fpga partitions. experimental results on a number of benchmarks and industrial designs demonstrate that i o limits are the bottleneck for clb utilization when applying a traditional multiple-fpga synthesis method on flattened netlists. in contrast, by fully exploiting the design structural hierarchy during the multiple-fpga partitioning, our proposed method produces fewer fpga partitions with higher clb and lower i o-pin utilizations.  wen-jong fang allen c.-h. wu
fault diagnosis based on effect-cause analysis: an introduction  this paper presents the basic concepts of a new fault diagnosis technique which has the following features: 1) is applicable to both single and multiple faults, 2) does not require fault enumeration, 3) can identify faults which prevent initialization, 4) can indicate the presence of nonstuck faults in the d.u.t., 5) can identify fault-free lines in the d.u.t. our technique, referred to as effect-cause analysis, does not require a fault dictionary and it is not based on comparing the obtained response of the d.u.t. with the expected response, which is not assumed to be known. effect- cause analysis directly processes the actual response of the d.u.t. to the applied test (the effect) to determine the possible fault situations (the causes) which can generate that response.  miron abramovici melvin a. breuer
fast timing simulation of transient faults in digital circuits  transient fault simulation is an important verification activity for circuits used in critical applications since such faults account for over 80% of all system failures. this paper presents a timing level transient fault simulator that bridges the gap between electrical and gate-level transient fault simulators. a generic mos circuit primitive and analytical solutions of node differential equations are used to perform transistor level simulation with accurate mos-fet models. the transient fault is modeled by a piecewise quadratic injected current waveform; this retains the electrical nature of the transient fault and provides spice-like accuracy. detailed comparisons with spice3 show the accuracy of this technique and speedups of two orders of magnitude are observed for circuits containing up to 2000 transistors. latched error distributions of the benchmark circuits are also provided.  a. dharchoudhury s. m. kang h. cha j. h. patel
kahlua: a hierarchical circuit disassembler  a new tool called a circuit disassembler has been developed to transform a mask level layout into an equivalent symbolic layout. this technique has been implemented in the program called kahlua that can handle mask layout containing arbitrary manhattan geometry and is independent of the circuit technology. circuits designed using physical layout systems can be automatically disassembled into a symbolic environment. once converted, the disassembled cells can be manipulated further by any existing symbolic design or verification tools. in particular, these cells can be automatically remapped for a new technology. our formulation of the problem consists of two major stages: device extraction, and net decomposition. in the first stage the transistors and contacts are extracted from the layout to form leaf cells. in the second stage a set of symbolic wires is derived from the remaining interconnect geometry. kahlua has been tested on a wide range of physical cells and has produced high quality results with modest execution times. an additional feature of the technique include the ability to disassemble hierarchically, which makes disassembling large layouts feasible.  b. lin a. r. newton
hardware acceleration of gate array layout  in this paper we describe the hardware and software of a system which we have implemented to accelerate the physical design of gate arrays. in contrast to nearly all other reported approaches, our approach to hardware acceleration is to augment a single-user host workstation with a general-purpose microprogrammable slave processor having a large private memory. one or more such slaves can be attached. we have implemented placement improvement on the system, achieving a 20 x speedup vs. a high-level host implementation. we give performance results, which are comparable to those reported elsewhere for mainframe implementations.  philip m. spira carl hage
an analytical method for compacting routing area in integrated circuits  an analytical method is proposed for solving a routing area compaction problem in building block integrated circuits. related minimization is performed with a linear programming technique. minimum channel dimensions are calculated for a preliminary routing; these dimensions are used to construct routing constraints. placement constraints are added for the interrelations between placement and routing. this combined set of constraints leads to a least overestimation of routing area and under certain conditions guarantees routing feasibility. computational complexity and existence of a solution are discussed.  m. j. ciesielski e. kinnen
a methodology for hardware verification based on logic simulation  a logic simulator can prove the correctness of a digital circuit if it can be shown that only circuits fulfilling the system specification will produce a particular response to a sequence of simulation commands.this style of verification has advantages over the other proof methods in being readily automated and requiring less attention on the part of the user to the low- level details of the design. it has advantages over other approaches to simulation in providing more reliable results, often at a comparable cost.  this paper presents the theoretical foundations of several related approaches to circuit verification based on logic simulation. these approaches exploit the three-valued modeling capability found in most logic simulators, where the third-value x indicates a signal with unknown digital value. although the circuit verification problem is np-hard as measured in the size of the circuit description, several techniques can reduce the simulation complexity to a manageable level for many practical circuits.  randal e. bryant
balance scheduling: weighting branch tradeoffs in superblocks  since there is generally insufficient instruction level parallelism within a single basic block, higher performance is achieved by speculatively scheduling operations in superblocks. this is difficult in general because each branch competes for the processor's limited resources. previous work manages the performance tradeoffs that exist between branches only indirectly. we show here that dependence and resource constraints can be used to gather explicit knowledge about scheduling tradeoffs between branches. the first contribution of this paper is a set of new, tighter lower bounds on the execution times of superblocks that specifically accounts for the dependence and resource conflicts between pairs of branches. the second contribution of this paper is a novel superblock scheduling heuristic that finds high performance schedules by determining the operations that each branch needs to be scheduled early and selecting branches with compatible needs that favor beneficial branch tradeoffs. performance evaluations for superblocks from specint95 indicate that our bounds are very tight and that our scheduling heuristic outperforms well known superblock scheduling algorithms.  alexandre e. eichenberger waleed m. meleis
a simultaneous technology mapping, placement, and global routing algorithm for field-programmable gate arrays  technology mapping algorithms for lut (look up table) based fpgas have been proposed to transfer a boolean network into logic-blocks. however, since those algorithms take no layout information into account, they do not always lead to excellent results. in this paper, a simultaneous technology mapping, placement and global routing algorithm for fpgas, maple, is presented. mapleis an extended version of a simultaneous placement and global routing algorithm for fpgas, which is based on recursive partition of layout regions and block sets. maple inherits its basic processes and executes the technology mapping simultaneously in each recursive process. therefore, the mapping can be done with the placement and global routing information. experimental results for some benchmark circuits demonstrate its efficiency and effectiveness.  nozomu togawa masao sato tatsuo ohtsuki
the tlb slice - a low-cost high-speed address translation mechanism  the mips r6000 microprocessor relies on a new type of translation lookaside buffer --- called a tlb slice \\--- which is less than one-tenth the size of a conventional tlb and as fast as one multiplexer delay, yet has a high enough hit rate to be practical. the fast translation makes it possible to use a physical cache without adding a translation stage to the processor's pipeline. the small size makes it possible to include address translation on-chip, even in a technology with a limited number of devices.  the key idea behind the tlb slice is to have both a virtual tag and a physical tag on a physically-indexed cache. because of the virtual tag, the tlb slice needs to hold only enough physical page number bits --- typically 4 to 8 --- to complete the physical cache index, in contrast with a conventional tlb, which needs to hold both a virtual page number and a physical page number. the virtual page number is unnecessary because the tlb slice needs to provide only a hint for the translated physical address rather than a guarantee. the full physical page number is unnecessary because the cache hit logic is based on the virtual tag. furthermore, if the cache is multi-level and references to the tlb slice are "shielded" by hits in a virtually indexed primary cache, the slice can get by with very few entries, once again lowering its cost and increasing its speed. with this mechanism, the simplicity of a physical cache can been combined with the speed of a virtual cache.  george taylor peter davies michael farmwald
a preprocessor for the via minimization problem  the objective of the via minimization is to assign wire segments into different layers to minimize the number of vias required. several algorithms have been proposed for the constrained via minimization (cvm) problem where the topology of the given layout is fixed. in a cvm problem, some vias may be "essential" to the given layout. that is, they have to be selected and cannot be replaced by other vias. in this paper we present a procedure to find most of the essential vias. this procedure can be used as a preprocessor for the algorithms for cvm problems. experimental results show that the procedure is efficient and can identify most of essential vias.  k. c. chang h. c. du
managing pipeline-reconfigurable fpgas  while reconfigurable computing promises to deliver incomparable performance, it is still a marginal technology due to the high cost of developing and upgrading applications. hardware virtualization can be used to significantly reduce both these costs. in this paper we describe the benefits of hardware virtualization, and show how it can be achieved using a combination of pipeline reconfiguration and run-time scheduling of both configuration streams and data streams. the result is piperench, an architecture that supports robust compilation and provides forward compatibility. our preliminary performance analysis predicts that piperench will outperform commercial fpgas and dsps in both overall performance and in performance per mm2.  srihari cadambi jeffrey weener seth copen goldstein herman schmit donald e. thomas
memory access scheduling  the bandwidth and latency of a memory system are strongly dependent on the manner in which accesses interact with the "3-d" structure of banks, rows, and columns characteristic of contemporary dram chips. there is nearly an order of magnitude difference in bandwidth between successive references to different columns within a row and different rows within a bank. this paper introduces memory access scheduling, a technique that improves the performance of a memory system by reordering memory references to exploit locality within the 3-d memory structure. conservative reordering, in which the first ready reference in a sequence is performed, improves bandwidth by 40% for traces from five media benchmarks. aggressive reordering, in which operations are scheduled to optimize memory bandwidth, improves bandwidth by 93% for the same set of applications. memory access scheduling is particularly important for media processors where it enables the processor to make the most efficient use of scarce memory bandwidth.  scott rixner william j. dally ujval j. kapasi peter mattson john d. owens
a case for redundant arrays of inexpensive disks (raid)  increasing performance of cpus and memories will be squandered if not matched by a similar performance increase in i/o. while the capacity of single large expensive disks (sled) has grown rapidly, the performance improvement of sled has been modest. redundant arrays of inexpensive disks (raid), based on the magnetic disk technology developed for personal computers, offers an attractive alternative to sled, promising improvements of an order of magnitude in performance, reliability, power consumption, and scalability. this paper introduces five levels of raids, giving their relative cost/performance, and compares raid to an ibm 3380 and a fujitsu super eagle.  david a. patterson garth gibson randy h. katz
virtual grid symbolic layout  free form or "stick" type symbolic layout provides a means of simplifying the design of ic subcircuits. to successfully utilize this style of layout, a complete design approach and the necessary tools to support this methodology are required. in particular, one of the requirements of such a design method is the ability to "compact" the loosely specified topology to create a set of valid mask data. this paper presents a new compaction strtegy which uses the concept of a virtual grid. the compaction algorithm using the virtual grid is both simple and fast, an veniently interact with the algorithm to optimize a layout. in addition to the compaction algorithm, methods used to create large building blocks will be described. the work described here is part of a complete symbolic layout system called mulga which is written in the c programming language and resides on the unix operating system.  neil weste
mossim: a switch-level simulator for mos lsi  the logic simulator mossim is designed specifically to serve the needs of the mos lsi designer. it models a mos circuit as a network of field-effect transistor "switches", with node states 0, 1, and x (unknown) and transistor states "open", "closed", and "unknown". mossim has proved quite versatile and accurate in simulating a variety of mos designs including ones for which the network was extracted automatically from the mask specifications. because it models the network at a logical level, it has a performance comparable to conventional logic gate simulators.  randal e. bryant
automatic test bench generation for simulation-based validation  in current design practice synthesis tools play a key role, letting designers to concentrate on the specification of the system being designed by carrying out repetitive tasks such as architecture synthesis and technology mapping. however, in the new design flow, validation still remains a challenge: while new technologies based on formal verification are only marginally accepted for large designs, standard techniques based on simulation are beginning to fall behind the increased system complexity. this paper proposes an approach to simulation-based validation, in which an evolutionary algorithm computes useful input sequences to be included in the test bench. the feasibility of the proposed approach is assessed with a preliminary implementation of the proposed algorithm.  m. lajolo l. lavagno m. rebaudengo m. sonza reorda m. violante