waashk/acm huggingface dataset:
an evaluation of redundant arrays of disks using an amdahl 5890  recently we presented several disk array architectures designed to increase the data rate and i/o rate of supercomputing applications, transaction processing, and file systems [patterson 88]. in this paper we present a hardware performance measurement of two of these architectures, mirroring and rotated parity. we see how throughput for these two architectures is affected by response time requirements, request sizes, and read to write ratios. we find that for applications with large accesses, such as many supercomputing applications, a rotated parity disk array far outperforms traditional mirroring architecture. for applications dominated by small accesses, such as transaction processing, mirroring architectures have higher performance per disk than rotated parity architectures.  peter m. chen garth a. gibson randy h. katz david a. patterson
the second generation motis mixed-mode simulator  this paper describes the second generation motis mixed-mode simulator. in particular, it extends the current modeling capabilities to include resistors, floating capacitors, and bidirectional transmission gates. it employs a relaxation algorithm with local time-step control for timing simulation, and a switch level approach for unit delay simulation. it provides logic and timing verification for general mos circuits in a mixed-mode environment. the new simulator is being used for production chips, and it is more accurate, flexible, and efficient than the existing motis mixed-mode simulator.  c. f. chen c-y lo h. n. nham prasad subramaniam
an o(nlogm) algorithm for vlsi design rule checking  this paper describes a new variant of the segment tree approach for vlsi design rule checking. the best known algorithms to date for flat vlsi design rule checking require o(nlogn) expected time and o( n) expected space, where n is the total number of edges on a mask layer of the chip. we present a new algorithm that can run in o(nlogm) expected time, where m is the maximum feature size on a particular mask layer. since the maximum feature size must be bounded by the height of a chip, i.e. m ≤ o( n), the new algorithm is adaptively more efficient than o(nlogn). for layers such as diffusion or contact windows where the maximum feature size is independent of chip size, i.e. m = o(1), the new algorithm runs in o(n) expected time, a definite improvement. the improved time efficiency is achieved without sacrificing o( n) expected space complexity.  c. r. bonapace c.-y. lo
a data-flow driven resource allocation in a retargetable microcode compiler  a method for global resource allocation is described, which minimizes data movements and optimizes the use of resources like special purpose registers and functional units in complicated bus structures. the algorithm can deal with arbitrary flow graphs and hierarchies of nonrecursive procedures. it is based on a thorough data flow analysis of the source program and a description of the target architecture.  the method has been implemented in a retargetable compiler with front-ends for the system implementation languages c and cdl2.  h. feuerhahn
synthesis of low-power selectively-clocked systems from high-level specification  we propose a technique for synthesizing low-power systems from behavioral specifications. we analyze the control flow of the specification model to detect mutually exclusive sections of the computation. a selectively-clocked interconnection of interacting fsms is automatically generated and optimized, where each fsm controls the execution of one section of computation. only one of the interacting fsms is active for a high fraction of the operation time, while the others are idle and their clocks are stopped. periodically, the active machine releases the control of the system to another fsm and stops. our interacting fsm implementation achieves consistently lower power dissipation than the functionally equivalent monolithic implementation. on average, 37% power savings and 12% speedup are obtained, despite a 30% area overhead.  l. benini g. de micheli
profile-driven code execution for low power dissipation (poster session)  this paper proposes a novel technique for power-performance trade-off based on profile-driven code execution. specifically, we show that there is an optimal level of parallelism for energy consumption and propose a compiler- assisted technique for code annotation that can be used at run-time to adaptively trade-off power and performance. as shown by experimental results, our approach is up to 23% better than clock throttling and is as efficient as voltage scaling (up to 10% better in some cases). the technique proposed in this paper can be used by an acpi-compliant power manager for prolonging battery life or as a passive cooling feature for thermal management.  diana marculescu
a mixed nodal-mesh formulation for efficient extraction and passive reduced- order modeling of 3d interconnects  as vlsi circuit speeds have increased, reliable chip and system design can no longer be performed without accurate three-dimensional interconnect models. in this paper, we describe an integral equation aproach to modeling the impedance of inter-connect structures accounting for both the charge accumulation on the surface of conductors and the current traveling in their interior: our formulation, based on a combination of nodal and mesh analysis, has the required properties to be combined with model order reduction techniques to generate accurate and guaranteed passive low order interconnect models for efficient inclusion in standard circuit simulators. furthermore, the formulation is shown to be more flexible and efficient than previously reported methods.  nuno marques mattan kamon jacob white l. miguel silveira
cache memories: a tutorial and survey of current research directions  the tutorial presents a unified nomenclature for the description of cache memory systems. using this foundation, examples of existing cache memory systems are detailed and compared.  the second presentation discusses a programmable cache memory architecture. in this architecture, intelligence is added to the cache to direct the activity between the cache and the main memory. also to be described are heuristics for programming the cache which allow the additional power to be exploited.  the third presentation deals with innovations involving systems where the cache memory is not used as a simple high speed buffer for main memory. a straight forward example of this appears in ibm's translation lookaside buffer on 370s with dynamic address translation hardware. other examples are to be described include a cache system for the activation stack of a block structured language, a cache system to store subexpressions for an expression oriented architecture, and a multiprocessor architecture that relies on two levels of cache.  robert p. cook cathy j. linn joseph l. linn terry m. walker
analysis of placement procedures for vlsi standard cell layout  this paper describes a study of placement procedures for vlsi standard cell layout. the procedures studied are simulated annealing, min cut placement, and a number of improvements to min cut placement including a technique called terminal propagation which allows min cut to include the effect of connections to external cells. the min cut procedures are coupled with a force directed pairwise interchange (fdpi) algorithm for placement improvement. for the same problem these techniques produce a range of solutions with a typical standard deviation 4% for the total wire length and 3% to 4% for the routed area. the spread of results for simulated annealing is even larger. this distribution of results for a given algorithm implies that mean results of many placements should be used when comparing algorithms. we find that the min cut partitioning with simplified terminal propagation is the most efficient placement procedure studied.  mark r. hartoog
structural gate decomposition for depth-optimal technology mapping in lut- based fpga designs  in this paper we study structural gate decomposition in general, simple gate networks for depth-optimal technology mapping using k-input lookup-tables (k-luts). we show that (1) structural gate decomposition in any k-bounded network results in an optimal mapping depth smaller than or equal to that of the original network, regardless of the decomposition method used; and (2) the problem of structural gate decomposition for depth-optimal technology mapping is np-hard for k-unbounded networks when k≥3 and remains np-hard for k-boundeds networks when k≥5\. based on these results, we propose two new structural gate decomposition algorithms, named dogma and dogma-m, which combine the level-driven node-packing technique (used in flowmap) and the network flow-based labeling technique (used in chortle-d) for depth- optimal technology mapping. experimental results show that (1) among five structural gate decompostion algorithms, dogma-m results in the best mapping solutions; and (2) compared with speed_up(an algebraic algorithm) and tos (a boolean approach), dogma-m completes, decomposition of all tested benchmarks in a short time while speed_up and tos fail in several cases. however, speed_up results in the smallest depth and area in the following technology mapping steps.  jason cong yean-yow hwang
new clock-gating techniques for low-power flip-flops  two novel low power flip-flops are presented in the paper. proposed flip-flops use new gating techniques that reduce power dissipation deactivating the clock signal. presented circuits overcome the clock duty-cycle limitation of previously reported gated flip-flops.  circuit simulations with the inclusion of parasitics show that sensible power dissipation reduction is possible if input signal has reduced switching activity. a 16-bit counter is presented as a simple low power application.  a. g. m. strollo e. napoli d. de caro
the use of inverse layout trees for hierarchical design rule checking  the inverse layout tree concept is used to perform fully hierarchical drc without any constraints on the use of overlapping or incomplete cells that are completed at higher levels of hierarchy. hierarchy is preserved and design rule violations are displayed in the cell where they should be corrected. the drc is corner-based and processes 200-800 corners/second on a vax 11/750.  n. hedenstierna k. o. jeppson
high-performance bidirectional repeaters  _in this paper, we present high-performance bidirectional repeaters that recondition the signal waveform and reduce the signal degradation. we also present the application of these repeaters to the design of high-performance bidirectional busses. spice simulation results for long bidirectional interconnects show an almost linear increase in delay with repeaters compared to a quadratic increase in delay without repeaters. these repeaters are also applied to improve the performance of long and domino gates. spice simulation results show a significant reduction in the delay of long and domino gate with repeaters._  s. bobba i. n. hajj
analysis of rc interconnections under ramp input  we give new methods for calculating the time-domain response for a finite- length distributed rc line that is stimulated by a ramp input. the following are our contributions. first, we obtain the solution of the diffusion equation for a seminfinite distributed rc line with ramp input. we then present a general and, in the limit, exact approach to compute the time-domain response for finite-length rc lines under ramp input by summing distinct diffusions starting at either end of the line. next, we obtain analytical expressions for the finite time-domain voltage response for an open-ended finite rc line and for a finite rc line with capacitive load. the delay estimates using this method are very close to spice-computing delays. finally, we present a general recursive equation for computing the higher-order diffusion components due to reflections at the source and load ends. future work extends our method to response computations in general interconnection trees by modeling both reflection and transmission coefficients at discontinuities.  andrew b. kahng sudhakar muddu
array optimization for vlsi synthesis  we present in this paper an algorithm that solves a general array optimization problem. the algorithm can be used for compacting gate matrix layouts, sla's, weinberger arrays, and for multiple folding of pla's. our approach is based on the technique of simulated annealing. a major contribution of this paper is the formulation of the solution space which facilitates an effective search for an optimal solution. experimental results are very encouraging.  d. f. wong c. l. liu
code transformations to improve memory parallelism  current microprocessors incorporate techniques to exploit instruction-level parallelism (ilp). however, previous work has shown that these ilp techniques are less effective in removing memory stall time than cpu time, making the memory system a greater bottleneck in ilp-based systems than previous- generation systems. these deficiencies arise largely because applications present limited opportunities for an out-of-order issue processor to overlap multiple read misses, the dominant source of memory stalls.  this work proposes code transformations to increase parallelism in the memory system by overlapping multiple read misses within the same instruction window, while preserving cache locality. we present an analysis and transformation framework suitable for compiler implementation. our simulation experiments show substantial increases in memory parallelism, leading to execution time reductions averaging 23% in a multiprocessor and 30% in a uniprocessor. we see similar benefits on a convex exemplar.  vijay s. pai sarita adve
an experimental mos fault simulation program csasim  a prototype version of a new switch-level fault simulator for digital mos ic's is described. the simulation program, which is called csasim, analyzes csa (connector-switch-attenuator) circuit models using multiple logic values. a novel method of signal evaluation is employed, based on the super-position of bidirectional static and dynamic signals. csasim also allows efficient simulation of many different fault types, including stuck-at-constant, open- circuit, short-circuit, and delay faults. the internal structure and fault- simulation mechanisms of the simulator are discussed in this paper.  masato kawai john p. hayes
a module interchange placement machine  the interchange of pairs of modules is used in a number of popular automatic placement routines in which it is the most time-consuming computation. a system for automatic placement based on iterative placement improvement algorithms which use module interchange is presented. the major attribute of this system is in the hardware implementation of the computation of the cost increment for the new placement resulting from the interchange of two modules. the system was constructed and its results indicate that a speed-up could be achieved of one order of magnitude or better in comparison with software implementations.  alexander iosupovicz clarence king melvin a. breuer
a general methodology for synthesis and verification of register-transfer designs  the general relationship between register-transfer synthesis and verification is discussed, and common mechanisms are shown to underlie both tasks. the paper proposes a framework for combined synthesis and verification of hardware that supports any combination of user-selectable synthesis techniques. the synthesis process can begin with any degree of completion of a partial design, and verification of the partial design can be achieved by completing its synthesis while subjecting it to constraints that can be generated from a "template" and user constraints. the driving force was the work done by hafer [3] on a synthesis model. the model was augmented by adding variables and constraints in order to verify interconnections. a multilevel, multidimensional design representation [6] is introduced which is shown to to be equivalent to hafer's model. this equivalence relationship is exploited in deriving constraints off the design representation. these constraints can be manipulated in a variety of ways before being input to a linear program which completes the synthesis/verification process. an example is presented in which verification and synthesis occur simultaneously and the contribution of each automatically varies, depending on the number of previous design decisions.  alice c. parker fadi kurdahi mitch mlinar
contest: a concurrent test generator for sequential circuits  this paper describes the application of a concurrent fault simulator to automatic test vector generation. as faults are simulated in the fault simulator a cost function is simultaneously computed. a simple cost function is the distance (in terms of the number of gates and flip-flops) of a fault effect from a primary output. the input vector is then modified to reduce the cost function until a test is found. the paper presents experimental results showing the effectiveness of this method in generating tests for combinational and sequential circuits. by defining suitable cost functions, we have been able to generate: 1) initialization sequences, 2) tests for a group of faults, and 3) a test for a given fault. even asynchronous sequential circuits can be handled by this approach.  vishwani d. agrawal kwang-ting cheng prathima agrawal
new placement and global routing algorithms for standard cell layouts  new placement and global routing algorithms are proposed for standard cell layouts. the placement algorithm, called the hierarchical clustering with min- cut exchange (hcme), is effective to avoid being trapped in local optimum solutions. the global routing algorithm does not route the nets one by one and therefore, the results are independent of the net order and channel order. in this algorithm, channel width is minimized under a cost function, in which the trade-off between the minimization of net lengths and the minimization of the number of tracks is considered. these algorithms are simple and highly efficient. this is confirmed by computational experiments.  masato edahiro takeshi yoshimura
a "non-restrictive" artwork verification program for printed circuit boards  this paper describes a pcb artwork verification program which imposes virtually no restrictions on the layout designer. the program is capable of making fast and reliable verifications of layouts of any type and style. the concepts and techniques used to achieve the "non- restrictive" feature of the program are discussed. a unique characteristic of the program is the special treatment of nonelectrical elements. the program has been proven by continuous practical use in a dynamic production environment.  david kaplan
cat - caching address tags: a technique for reducing area cost of on-chip caches this paper presents a technique for minimizing chip-area cost of implementing an on-chip cache memory of microprocessors. the main idea of the technique _caching address tags, or_ _cat cache_ for short. the _cat_ cache exploits locality property that exists among addresses of memory references for the purpose of minimizing chip area-cost of address tags. by keeping only a limited number of distinct tags of cached data rather than having as many tags as cache lines, the _cat_ cache can reduce the cost of implementing tag memory by an order of magnitude without noticeable performance difference from ordinary caches. therefore, _cat_ represents another level of caching for cache memories. simulation experiments are carried out to evaluate performance of _cat_ cache as compared to existing caches. performance results of spec92 programs show that the _cat_ cache with only a few tag entries performs as well as ordinary caches while chip-area saving is significant. such area saving will increase as the address space of a processor increases. by allocating the saved chip area for larger cache capacity, or more powerful functional units, _cat_ is expected to have a great impact on overall system performance. hong wang tong sun qing yang
layout based frequency dependent inductance and resistance extraction for on- chip interconnect timing analysis  it is well understood that frequency independent lumped-element circuits can be used to accurately model proximity and skin effects in transmission lines [7]. furthermore, it is also understood that these circuits can be synthesized knowing only the high and the low frequency resistances and inductances [4]. existing vlsi extraction tools however, are not efficient enough to solve for the frequency dependent resistances and inductances on large vlsi layouts, nor do they synthesize circuits suitable for timing analysis. we propose a rules- based method that efficiently and accurately captures the high and low frequency characteristics directly from layout shapes, and subsequently synthesizes a simple frequency independent ladder circuit suitable for timing analysis. we compare our results to other simulation results.  byron krauter sharad mehrotra
transparent repeaters  the concept of a "transparent repeater1," which is an amplifier circuit designed to minimize the delay introduced by highly resistive interconnect lines in high speed digital circuits, is introduced and described in this paper. an insertion methodology for this circuit is also discussed. defining characteristics of this circuit are: the input is connected to the output, the output generates the same sense transition as the corresponding input transition, the buffer output becomes high impedance after every transition, and the buffer may detect input transitions with low threshold voltages.  radu m. secareanu eby g. friedman
microcode compaction via microblock definition  the paper describes a microprogram compaction technique based on a microoperation and microistruction modelling, applicable to different types of target machine. the model describes microoperation semantics by relating them to microcodes used in microinstruction fields, without any explicit description of machine timing. evaluation of the proposed technique is given in terms of efficiency of the automatically generated microcode.  m. mezzalama p. prinetto g. filippi
heterogeneous technology mapping for fpgas with dual-port embedded memory arrays  it has become clear that on-chip storage is an essential component of high- density fpgas. these arrays were originally intended to implement storage, but recent work has shown that they can also be used to implement logic very efficiently. this previous work has only considered single-port arrays. many current fpgas, however, contain dual-port arrays. in this paper we present an algorithm that maps logic to these dual- port arrays. our algorithm can either optimize area with no regard for circuit speed, or optimize area under the constraint that the combinational depth of the circuit does not increase. experimental results show that, on average, our algorithm packs between 29% and 35% more logic than an algorithm that targets single-port arrays. we also show, however, that even with this algorithm, dual-port arrays are still not as area-efficient as single-port arrays when implementing logic.  steven j. e. wilton
parallel algorithms for fpga placement  _fast fpga cad tools that produce high quality results has been one of the most important research issues in the fpga domain. simulated annealing has been the method of choice for placement. however, simulated annealing is a very compute-intensive method. in our present work we investigate a range of parallelization strategies to speedup simulated annealing with application to placement for fpga. we present experimental results obtained by applying the different parallelization strategies to the versatile place and route (vpr) tool, implemented on an sgi origin shared memory multi-processor and an ibm- sp2 distributed memory multi-processor. the results show the tradeoff between execution time and quality of result for the different parallelization strategies._  malay haldar anshuman nayak alok choudhary prith banerjee