waashk/acm huggingface dataset:
rectilinear block placement using sequence-pair  with the recent advent of deep sub-micron technology and new packaging schemes such as multi-chip modules(mcms), integrated circuit components are often not rectangular. most existing block placement approaches, however, only deal with rectangular blocks, resulting in inefficient area utilization. new approaches which can handle arbitrarily shaped blocks are essential to achieve high performance design. in this paper, we present an approach extending the sequence-pair approach for rectangular block placement to arbitrarily sized and shaped rectilinear blocks. experimental results show that our algorithm achieves results with excellent area utilization.  jin xu pei-ning guo chung-kuan cheng
automatic and efficient evaluation of memory hierarchies for embedded systems  automation is the key to the design of future embedded systems as it permits application-specific customization while keeping design costs low. a key problem faced by automatic design systems is evaluating the performance of the vast number of alternative designs in a timely manner. for this paper, we focus on an embedded system consisting of the following components: a vliw processor, instruction cache, data cache, and second-level unified cache. a hierarchical approach of partitioning the system into its constituent components and evaluating each component individually is utilized. the performance of each processor is evaluated independent of its memory hierarchy, and each of the caches is simulated using the traces from a single reference processor. since the changes in the processor architecture do indeed affect the address traces and thus the performance of the memory hierarchy, the overall performance is inaccurate. to overcome this error, the changes in the processor architecture are modeled as a dilation of the reference processor's address trace, where each instruction block in the trace is conceptually stretched out by the dilation coefficient. this approach provides a projected cache performance that more accurately accounts for changes in the processor architecture. in order to understand the accuracy of the dilation model, we separate the possible errors that the model introduces and quantify these errors on a set of benchmarks. the results show the dilation model is effective for most of the design space and facilitates efficient automatic design.  santosh g. abraham scott a. mahlke
von neumann hybrid cellular automata for generating deterministic test sequences  we propose an on-chip test pattern generator that uses an one-dimensional cellular automaton (ca) to generate either a precomputed sequence of test patterns or pairs of test patterns for path delay faults. to our knowledge, this is the first approach that guarantees successful on-chip generation of a given test pattern sequence (or a given test set for path delay faults) using a finite number of ca cells. given a pair of columns (cu, cv) of the test matrix, the proposed method uses alternative "link procedures" pj that compute the number of extra ca cells to enable the generation of (cu, cv) by the ca. a systematic approach uses the link procedures to minimize the total number of needed ca cells. the performance of the scheme depends on an appropriate choice of link procedures pj.  d. kagaris s. tragoudas
code compression as a variable in hardware/software co-design  we present a new way to practice and view handware/software co-design: rather than raising the level of abstraction in order to exploit the highest possible degree of optimization, we use code compression i.e. we practice co-design at the bit-level. through our novel architecture combined with our compression methodology this results in optimization of all major design goals/constraints. in particular, we present a compression methodology that deploys what we call a "post-cache architecture" (i.e. the detached decompression unit is located between the cpu and the instruction cache). we present a design methodology that allows the designer to control parameters like speed, power, and area through the choice of compression parameters. in addition we show that our compression methodology (using a markov model) is more efficient than the widely used huffman compression scheme.  haris lekatsas jörg henkel wayne wolf
a topology for semicustom array-structured lsi devices, and their automatic customisation  this paper describes the design of a topology for array-structured (both gate- array and polycell) semicustom lsi, in the context of a cmos gate-array fabricated to test both the topology and the unique functional cells. design emphasis has been placed on 100% routability, which is achieved by use of interdigitating cell terminals. also described is the structure and operation of an automatic customisation software package which has been developed for the array, and which utilises the topological advantages to achieve track densities which are comparable with state-of-the- art algorithms. examples are cited which show that this methodology is economical in both its speed of operation and its silicon-area utilisation.  p. jennings
area-time efficient addition in charge based technology  using the model developed by mead and conway for charge based technology, a methodology for the production of area-time efficient adders which imbeds the buffering required to drive large loads caused by the carry-lookahead tree has been developed. this methodology can be used to produce an o(logn) time and o(nlogn) area layout. additionally, an algorithm was written to produce minimal silicon area layouts for a given time bound. this algorithm involves optimization at both the cellular level and the layout level in an iterative fashion to allow the relevant technological parameters to play a role in the cellular design phase. results of the algorithm including examples and an area-time curve for a 48 bit adder using typical 5 micron nmos [meco80] are displayed.  robert k. montoye
clock period constrained minimal buffer insertion in clock trees  in this paper we investigate the problem of computing a lower bound on the number of buffers required when given a maximum clock frequency and a predefined clock tree. using generalized properties of published cmos timing models, we formulate a novel non-linear and a simplified linear buffer insertion problem. we solve the latter optimally with an o(n) algorithm. the basic formulation and algorithm are extended to include a skew upper bound constraint. using these algorithms we propose further algorithmic extensions that allow area and phase delay tradeoffs. our results are verified using spice3e2 simulations with mcnc mosis 2.0μ models and parameters. experiments show our buffer insertion algorithms can be used effectively for high-speed clock designs.  gustavo e. tellez majid sarrafzadeh
understanding the backward slices of performance degrading instructions  for many applications, branch mispredictions and cache misses limit a processor's performance to a level well below its peak instruction throughput. a small fraction of static instructions, whose behavior cannot be anticipated using current branch predictors and caches, contribute a large fraction of such performance degrading events. this paper analyzes the dynamic instruction stream leading up to these performance degrading instructions to identify the operations necessary to execute them early. the backward slice (the subset of the program that relates to the instruction) of these performance degrading instructions, if small compared to the whole dynamic instruction stream, can be pre-executed to hide the instruction's latency. to overcome conservative dependance assumptions that result in large slices, speculation can be used, resulting in speculative slices.  this paper provides an initial characterization of the backward slices of l2 data cache misses and branch mispredictions, and shows the effectiveness of techniques, including memory dependence prediction and control independence, for reducing the size of these slices. through the use of these techniques, many slices can be reduced to less than one tenth of the full dynamic instruction stream when considering the 512 instructions before the performance degrading instruction.  craig b. zilles gurindar s. sohi
supporting systolic and memory communication in iwarp  iwarp is a parallel architecture developed jointly by carnegie mellon university and intel corporation. the iwarp communication system supports two widely used interprocessor communication styles: memory communication and systolic communication. this paper describes the rationale, architecture, and implementation for the iwarp communication system.  the sending or receiving processor of a message can perform either memory or systolic communication. in memory communication, the entire message is buffered in the local memory of the processor before it is transmitted or after it is received. therefore communication begins or terminates at the local memory. for conventional message passing methods, both sending and receiving processors use memory communication. in systolic communication, individual data items are transferred as they are produced, or are used as they are received, by the program running at the processor. memory communication is flexible and well suited for general computing; whereas systolic communication is efficient and well suited for speed critical applications.  a major achievement of the iwarp effort is the derivation of a common design to satisfy the requirements of both systolic and memory communication styles. this is made possible by two important innovations in communication: (1) program access to communication and (2) logical channels. the former allows programs to access data as they are transmitted and to redirect portions of messages to different destinations efficiently. the latter increases the connectivity between the processors and guarantees communication bandwidth for classes of messages. these innovations have provided a focus for the iwarp architecture. the result is a communication system that provides a total bandwidth of 320 mbytes/sec and that is integrated on a single vlsi component with a 20 mflops plus 20 mips long instruction word computation engine.  shekhar borkar robert cohn george cox thomas gross h. t. kung monica lam margie levine brian moore wire moore craig peterson jim susman jim sutton john urbanski jon webb
smart memories: a modular reconfigurable architecture  trends in vlsi technology scaling demand that future computing devices be narrowly focused to achieve high performance and high efficiency, yet also target the high volumes and low costs of widely applicable general purpose designs. to address these conflicting requirements, we propose a modular reconfigurable architecture called smart memories, targeted at computing needs in the 0.1μ technology generation. a smart memories chip is made up of many processing tiles, each containing local memory, local interconnect, and a processor core. for efficient computation under a wide class of possible applications, the memories, the wires, and the computational model can all be altered to match the applications. to show the applicability of this design, two very different machines at opposite ends of the architectural spectrum, the imagine stream processor and the hydra speculative multiprocessor, are mapped onto the smart memories computing substrate. simulations of the mappings show that the smart memories architecture can successfully map these architectures with only modest performance degradation.  ken mai tim paaske nuwan jayasena ron ho william j. dally mark horowitz
a survey of boolean matching techniques for library binding  when binding a logic network to a set of cells, a fundamental problem is recognizing whether a cell can implement a portion of the network. boolean matching means solving this task using a formalism based on boolean algebra. in its simplest form, boolean matching can be posed as a tautology check. we review several approaches to boolean matching as well as to its generalization to cases involving don't care conditions and its restriction to specific libraries such as those typical of anti-fuse based fpgas. we then present a general formulation of boolean matching supporting multiple-output logic cells.  luca benini giovanni de micheli
automatic generation of behavioral models from switch-level descriptions  this paper discusses the automatic generation of high-level software models from switch-level circuit descriptions. the proposed algorithms operate directly on the hierarchical description, and incorporate information about the design such as the structure, regularity, functionality, and control signals in the generation process. new algorithms are proposed and have been implemented for combinational modules and bus structures. a significant speedup has been obtained for these modules of a commercially available chip.  d. t. blaauw d. g. saab r. b. mueller-thuns j. a. abraham j. t. rahmeh
proofs: a fast, memory efficient sequential circuit fault simulator  this paper describes proofs, a super fast fault simulator for synchronous sequential circuits. proofs achieves high performance by combining all the advantages of differential fault simulation, single fault propagation, and parallel fault simulation, while minimizing their individual disadvantages. proofs minimizes the memory requirements, reduces the number of events that need to be evaluated, and simplifies the complexity of the software implementation. proofs requires an average of one fifth the memory required for concurrent fault simulation and runs 6 to 67 times faster on the iscas sequential benchmarks.  thomas m. niermann wu-tung cheng janak h. patel
representations for a rule based assistant for designing combinational circuits  a rule based assistant for designing combinational logic circuits is described. the input can be described in terms of truth tables, logic equations, non-logic equations using arithmetic and relational operators or a combination of these three. the strategist analyzes the input and decides on a particular implementation. it uses a set of rules to select a read only memory (rom), programmable logic array (pla) or a random logic (rl) implementation. the constructor synthesizes rl circuits given an input description in a suitable form. using its own set of rules, it detects and attempts to correct constraint violations which are specified in terms of speed, space and power. the hardware elements are chosen from a cell library. the system is designed to be highly extensible so that new rules can be added to the strategist and the constructor to make them more sophisticated. figure 1 illustrates the relationship between the various building blocks of this system  sundaravarathan r. iyengar ravi manghirmalani nancy nettleton joseph borgia
hls: combining statistical and symbolic simulation to guide microprocessor designs  as microprocessors continue to evolve, many optimizations reach a point of diminishing returns. we introduce hls, a hybrid processor simulator which uses statistical models and symbolic execution to evaluate design alternatives. this simulation methodology allows for quick and accurate contour maps to be generated of the performance space spanned by design parameters. we validate the accuracy of hls through correlation with existing cycle-by-cycle simulation techniques and current generation hardware. we demonstrate the power of hls by exploring design spaces defined by two parameters: code properties and value prediction. these examples motivate how hls can be used to set design goals and individual component performance targets.  additionally, these traces are not as susceptible to transient behavior because they are restricted to frequently executed code. empirical results show that on average this mechanism can achieve better instruction fetch rates using only 12kb of hardware than a trace cache requiring 15kb of hardware, while producing long, persistent traces more suited to optimization.  mark oskin frederic t. chong matthew farrens
synchronization with multiprocessor caches  introducing private caches in bus-based shared memory multiprocessors leads to the cache consistency problem since there may be multiple copies of shared data. however, the ability to snoop on the bus coupled with the fast broadcast capability allows the design of special hardware support for synchronization. we present a new lock-based cache scheme which incorporates synchronization into the cache coherency mechanism. with this scheme high-level synchronization primitives as well as low-level ones can be implemented without excessive overhead. cost functions for well-known synchronization methods are derived for invalidation schemes, write update schemes, and our lock-based scheme. to accurately predict the performance implications of the new scheme, a new simulation model is developed embodying a widely accepted paradigm of parallel programming. it is shown that our lock-based protocol outperforms existing cache protocols.  joonwon lee umakishore ramachandran
microcode development tools for a capability-based processor  the monads-pc system is a capability-based computer constructed around a microprogrammed processor designed and implemented at monash university in melbourne, australia. this paper describes a set of tools developed as part of this project in order to simplify the implementation and testing of the microcode and to ensure consistency between the microcode and macro-level machine instruction set. although some of these tools are at present machine specific, the paper demonstrates that they could be generalised into a flexible microcode development system.  j. rosenberg d. a. abramson
test generation for programmable logic arrays  the problem of fault detection and test generation for programmable logic arrays (plas) is investigated. the effect of actual physical failures is viewed in terms of the logical changes of the product terms (growth, shrinkage, appearance and disappearance) constituting the pla. methods to generate a minimal single fault detection test set (ts) from the product term specification of the plas, are presented. it is shown that such a test set can be derived using a set of simple, easily implementable algorithms. methods to augment ts in order to obtain a multiple fault detection test set (tm) are also presented.  pradip bose jacob a. abraham
efficient implementation of retiming  retiming is a technique for optimizing sequential circuits. it repositions the registers in a circuit leaving the combinational cells untouched. the objective of retiming is to find a circuit with the minimum number of registers for a specified clock period. more than ten years have elapsed since leiserson and saxe first presented a theoretical formulation to solve this problem for single-clock edge-triggered sequential circuits. their proposed algorithms have polynomial complexity; however naive implementations of these algorithms exhibit o(n3) time complexitiy and o(n 2) space complexity when applied to digital circuits with n combinational cells. this renders retiming ineffective for circuits with more than 500 combinational cells. this paper addresses the implementation issues required to exploit the sparsity of circuit graphs to allow min-period retiming and constrained min-area retiming to be applied to circuits with as many as 10,000 combinational cells. we believe this is the first paper to address these issues and the first to report retiming results for large circuits.  narendra shenoy richard rudell
power optimization of technology-dependent circuits based on symbolic computation of logic implications  this paper presents a novel approach to the problem of optimizing combinational circuits for low power. the method is inspired by the fact that power analysis performed on a technology mapped network gives more realistic estimates than it would at the technology-independent level. after each node's switching activity in the circuit is determined, high-power nodes are eliminated through redundancy addition and removal. to do so, the nodes are sorted according to their switching activity, they are considered one at a time, and learning is used to identify direct and indirect logic implications inside the network. these logic implications are exploited to add gates and connections to the circuit; this may help in eliminating high-power dissipating nodes, thus reducing the total switching activity and power dissipation of the entire circuit. the process is iterative; each iteration starts with a different target node. the end result is a circuit with a decreased switching power. besides the general optimization algorithm, we propose a new bdd-based method for computing satisfiability and observability implications in a logic network; futhermore, we present heuristic techniques to add and remove redundancy at the technology-dependent level, that is, restructure the logic in selected places without destroying the topology of the mapped circuit. experimental results show the effectiveness of the proposed technique. on average, power is reduced by 34%, and up to a 64% reduction of power is possible, with a negligible increase in the circuit delay.  r. iris bahar ernest t. lampe enrico macii
test generation for mos circuits using d-algorithm  an application of the d-algorithm in generating tests for mos circuit faults is described. the mos circuits considered are combinational and acyclic but may contain transmission gates and buses. tests are generated for both, the stuck type faults and the transistor faults (open and short). a logic model is derived for the mos circuits. in addition to the conventional logic gates, a new type of modeling block is used to represent the "memory" state caused by the "open" transistors. every fault, whether a stuck type fault or a transistor fault, is represented in the model as a stuck fault at a certain gate input. for generating tests, however, the d-algorithm needs modification. the singular cover and the d-cubes for the new gate include some memory states. to handle the memory state, an initialization procedure has been added to the consistency part of the d-algorithm. the procedure of modeling and test generation is finally extended to transmission gates and buses.  sunil k. jain vishwani d. agrawal
a comparative study of two boolean formulations of fpga detailed routing constraints  a boolean-based router expresses the routing constraints as a bool? function which is satisfiable if and only if the layout is routable. compared to traditional routers, boolean-based routers offer two unique features: (1) simultaneous embedding of all nets regardless of net ordering, and (2) ability to demonstrate routing infeasibility by proving the unsatisfiability of the generated routing constraint boolean function. in this paper, we introduce a new boolean-based fpga detailed routing formulation that yields an easy-to- evaluate and more scalable routability boolean function than the previous methods. the routability constraints are expressed in terms of a set of route variables each of which designating a specific detailed route for a given net. experimental results clearly show the superi?ty of this formulation over an earlier formulation that expressed the constraints in terms of track variables.  gi-joon nam fadi aloul karem sakallah rob rutenbar