waashk/acm huggingface dataset:
a global, dynamic register allocation and binding for a data path synthesis system  we developed a new algorithm for efficient register allocation and binding used in data path synthesis. our algorithm determines both the number of registers and the mapping from variables to registers simultaneously during data path allocation so that the cost, i.e., area, of the registers and connections to/from the registers can be minimized. the algorithm selects the "best" register for each input and/or output variable of operations. this register allocation/binding algorithm is used with a data path allocation algorithm that exploits trade- off among all kinds of hardware elements. we present experimental results of our algorithm.  nam-sung woo
associative table lookup processing for multioperand residue arithmetic  this paper investigates the complexity of multioperand residue addition and multiplication implemented by associative table lookup processing. the complexity measure used is the size of the associative memory, that is, the number of matching words in memory. this measure largely depends on the residue recurrencies, or multiplicities, in the addition and multiplication tables module m. the major effort in this work is to evaluate the recurrencies in simultaneous multioperand residue addition and multiplication. the evaluation is simple in case of addition mod m, and also in multiplication mod m if m is prime. to treat the more difficult case of m nonprime, a recursive procedure was developed for computing the 2-operand multiplication recurrencies mod m. the basis of this technique is the precedence relationships associated with a tree representation of the factors of m. it is then shown that the general d-operand multiplication mod m, d > 2 and m nonprime, can be reduced to the 2-operand case by isomorphic transformation. computation results of 2-operand residue arithmetic operations are provided. applications to rns arithmetic implementation are discussed.  christos a. papachristou
mixed-level simulation from a hierarchical chdl  a system for mixed- level design simulation from a comprehensive chdl is introduced. the chdl supports hierarchical design descriptions at behavioral, logic and electrical levels. a design is described as a set of interconnected blocks, where each block may be described at any of the three levels. a mixed- level simulation capability is described. designs may be simulated at any of these levels, or at a mixture of levels. simulateneous simulation of a given block at two levels is also supported. problems related to implementation of such a system are discussed.  william a. johnson jeri jane crowley j. d. ray
an efficient procedure for the synthesis of fast self-testable controller structures  the bist implementation of a conventionally synthesized controller in most cases requires the integration of an additional register only for test purposes. this leads to some serious drawbacks concerning the fault coverage, the system speed and the area overhead. a synthesis technique is presented which uses the additional test register also to implement the system function by supporting self-testable pipeline-like controller structures. it will be shown, that if the need of two different registers in the final structure is already taken into account during synthesis, then the overall number of flipflops can be reduced, and the fault coverage and system speed can be enhanced. the presented algorithm constructs realizations of a given finite state machine specification which can be trivially implemented by a self- testable structure. the efficiency of the procedure is ensured by a very precise characterization of the space of suitable realizations, which avoids the computational overhead of previously published algorithms.  sybille hellebrand hans-joachim wunderlich
dummy feature placement for chemical-mechanical polishing uniformity in a shallow trench isolation process  manufacturability of a design that is processed with shallow trench isolation (sti) depends on the uniformity of the chemical-mechanical polishing (cmp) step in sti. the cmp step in sti is a dual-material polish, for which all previous studies on dummy feature placement for single-material polish [3, 11, 1] are not applicable. based on recent semi-physical models of polish pad bending [5], local polish pad compression [2, 10], and different polish rates for materials present in a dual-material polish [2, 13], this paper derives a time-dependent relation between post-cmp topography and layout pattern density for cmp in sti. using the dependencies derived, the first formulation of dummy feature placement for cmp in sti is given as a nonlinear programming problem. an iterative approach is proposed to solve the dummy feature placement problem. computational experience on four layouts from motorola is given.  ruiqi tian xiaoping tang d. f. wong
algorithms for multiple-criterion design of microprogrammed control hardware  this paper describes two algorithms designed to optimize memory size and controller performance for a microprogrammed controller. the algorithms accept two inputs: a set of interconnected registers and logical operators called the data paths, and a control flow graph which describes how these data paths are to be exercised. the autonomy algorithm identifies data path elements which should be controlled directly from the microword without encoding. this algorithm aids the effectiveness of the subsequent encoding algorithm by eliminating some signals from consideration. a second algorithm, the attraction algorithm, determines which microoperations will execute in parallel and which will be encoded into separate microinstruction formats. this algorithm accepts a microword width constraint and implements parallel operations in the microcode and the corresponding encoding. both the parallelism and the encoding are determined by the algorithm. application of these algorithms to an example, the pdp**-11/40, has produced a control store design 14 percent wider and equal in parallelism to an equivalent portion of the human design.  andrew w. nagle alice c. parker
selective value prediction value prediction is a relatively new technique to increase instruction-level parallelism by breaking true data dependence chains. a value prediction architecture _produces_ values, which may be later _consumed_ by instructions that execute speculatively using the predicted value.this paper examines selective techniques for using value prediction in the presence of predictor capacity constraints and reasonable misprediction penalties. we examine prediction and confidence mechanisms in light of these constraints, and we minimize capacity conflicts through instruction filtering. the latter technique filters which instructions put values into the value prediction table. we examine filtering techniques based on instruction type, as well as giving priority to instructions belonging to the longest data dependence path in the processor's active instruction window. we apply filtering both to the producers of predicted values and the consumers. in addition, we examine the benefit of using different confidence levels for instructions using predicted values on the longest dependence path. brad calder glenn reinman dean m. tullsen
cycle-accurate energy consumption measurement and analysis: case study of arm7tdmi  we introduce an energy consumption analysis of complex digital systems through a case study of arm7tdmi risc processor by using a new energy measurement technique. we developed a cycle-accurate energy consumption measurement system based on charge transfer which is robust to spiky noise and is capable of collecting a range of power consumption profiles in real time. the relative energy variation of the risc core is measured by changing the opcode, the instruction fetch address, the register number, in each pipeline stage, respectively. we demonstrated energy characterization of a pipelined risc processor for high-level power reduction.  naehyuck chang kwanho kim hyung gyu lee
a new approach to the rectilinear steiner tree problem  we discuss a new approach to constructing the rectilinear steiner tree (rst) of a given set of points in the plane, starting from a minimum spanning tree (mst). the main idea in our approach is to determine l-shaped layouts for the edges of the mst, so as to maximize the overlaps between the layouts, thus minimizing the cost (i.e., wire length) of the resulting rst. we describe a linear time algorithm for constructing a rst from a mst, such that the rst is optimal under the restriction that the layout of each edge of the mst is an l-shape. the rst's produced by this algorithm have 8-33% lower cost than the mst, with the average cost improvement, over a large number of random point sets, being about 9%. the running time of the algorithm on an ibm 3090 processor is under 0.01 seconds for point sets with cardinality 10. we also discuss a property of rst's called stability under rerouting, and show how to stabilize the rst's derived from our approach. stability is a desirable property in vlsi global routing applications.  jan-ming ho g. vijayan c. k. wong
a mos/lsi oriented logic simulator  a logic simulator capable of efficiently modelling complex mos/lsi circuits is presented. the circuit is simulated at the combinational logic and transmission gate level using a set of six node-states. gate models have inertial delay and assignable nominal rise and fall delays. both unidirectional and bidirectional transmission gates are accurately simulated, and functional models are provided for rom, ram, etc.  dan holt dave hutchings
paola: a tool for topological optimization of large plas  this paper presents a tool, called paola, for optimizing the layout of large plas used as decoders in vlsi systems.  the optimization techniques it uses are heuristic. they involve compacting the and/or matrices by cutting and reorganizing the input/output lines in order to reduce the number of columns in these matrices. they also allow the lengthening of the shape of the pla and the lateral access to the input/output segments. this eases the topological adaptation of different blocks in order to reduce the surface of the interconnection network between them.  the layout of the pla uses internal topological conflicts and ground refresh lines positions to improve accessibility to the input/output segments created inside the and/or matrices.  this system has been tested on several examples including industrial plas. it gives an area reduction of the or matrix of up to 50% on plas having 3000 to 5000 positions in the or matrix with a computing time of 4 to 5 minutes on a main frame hb-68 computer running with the multics operating system.  samuel chuquillanqui tomas perez segovia
efficient floorplan area optimization  the floorplan area optimization problem is to determine the shape and dimensions of all the modules when the topology of the floorplan is given. the objective is to minimize the area of the resulting floorplan. existing methods only apply to slicing floorplans. we present in this paper an algorithm for general hierarchical floorplans. our algorithm combines the curve-adding technique used in the case of slicing floorplans and a new technique that computes shape curves by iterative modification of the shape and dimensions of individual modules. we also present an optimal points selection algorithm using the technique of dynamic programming to further enhance the process of shape curves construction.  d. f. wong p. s. sakhamuri
a graphical hardware design language  gdl is a graphical hardware design language that separates design decisions into three interrelated, but distinct domains: behavioral, structural and physical. specific language features are provided to represent a design in each of these domains. this report describes the process model for gdl. functional behavior is separated into distinct activities called "processes" (autonomous control centers.) the computations performed by a process are specified in its behavior graph. processes may communicate with each other through ports where the channel between two ports may be an abstract logical link or may be a physical bus. provisions are made for synchronization. the paper concludes with an evaluation of gdl and suggestions for future research.  paul j. drongowski jwahar r. bami ranganathan ramaswamy sundar iyengar tsu-hua wang
automatic layout of silicon-on-silicon hybrid packages  in modern, high speed computer systems, performance and density limits are being set more by interconnection and packaging constraints than by transistor characteristics. the most severe limitation comes from the single-chip packages that carry the vlsi circuits. multichip, silicon-on-silicon hybrid packages can significantly improve performance by eliminating this level of packaging. a system has been developed to automatically generate hybrid layouts given a schematic description and layouts of the vlsi circuits. this paper describes the hybrid technology, the design automation system foundation, and the hybrid layout system. this layout method, in combination with the fabrication technology, produces layouts that are 5 to 8 times more dense than the same circuits implemented with single-chip packages on printed circuit boards. simulations show that clock speeds can be increased by a factor of two.  b. preas m. pedram d. curry
bridging fault detection in fpga interconnects using iddq  this paper presents a vector generation approach for testing interconnects in configurable (sram-based) field programmable gate arrays (fpgas). the proposed approach detects bridging faults and is based on quiescent current (iddq monitoring. compared with previous voltage-based methods, iddq testing has the advantage of utilizing a small number of programming phases for configuring the fpga during the test process with negligible observability requirements, even under multiple faults. algorithms for test generation which exploit the homogeneous nature of the fpga array, are described. an example using the xc4000 is described in detail. for testing the xc4000 series interconnect, a total of 20 phases and 11 vectors are required: 11 phases for s (switch) block testing, and 9 phases for c (connection) block testing.  l. zhao d. m. h. walker f. lombardi
architectural support for reduced register saving/restoring in single-window register files  the use of registers in a processor reduces the data and instruction memory traffic. since this reduction is a significant factor in the improvement of the program execution time, recent vlsi processors have a large number of registers which can be used efficiently because of the advances in compiler technology. however, since registers have to be saved/restored across function calls, the corresponding register saving and restoring (rsr) memory traffic can almost eliminate the overall reduction. this traffic has been reduced by compiler optimizations and by providing multiple-window register files. although these multiple-window architectures produce a large reduction in the rsr traffic, they have several drawbacks which make the single-window file preferable. we consider a combination of hardware support and compiler optimizations to reduce the rsr traffic for a single-window register file, beyond the reductions achieved by compiler optimizations alone. basically, this hardware keeps track of the registers that are written during execution, so that the number of registers saved is minimized. moreover, hardware is added so that a register is saved in the activation record of the function that uses it (instead of in the record of the current function); in this way a register is restored only when it is needed, rather than wholesale on procedure return. we present a register saving and restoring policy that makes use of this hardware, discuss its implementation, and evaluate the traffic reduction when the policy is combined with intraprocedural and interprocedural compiler optimizations. we show that, on the average for the four general- purpose programs measured, the rsr traffic is reduced by about 90 percent for a small register file (i.e., 32 registers), which results in an overall data memory traffic reduction of about 15 percent.  miquel huguet tomás lang
compression-relaxation: a new approach to performance driven placement for regular architectures  we present a new iterative algorithm for performance driven placement applicable to regular architectures such as fpgas. our algorithm has two phases in each iteration: a compression phase and a relaxation phase. we employ a novel compression strategy based on the longest path tree of a cone for improving the timing performance of a given placement. compression might cause a feasible placement to become infeasible. the concept of a slack neighborhood graph is introduced and is used in the relaxation phase to transform an infeasible placement to a feasible one using a mincost flow formulation. our analytical results regarding the bounds on delay increase during relaxation are validated by the rapid convergence of our algorithm on benchmark circuits. we obtain placements that have 13% less critical path delay (on the average) than those generated by the xilinx automatic place and route tool (apr) on technology mapped mcnc benchmark circuits with significantly less cpu time than apr.  anmol mathur c. l. liu
a defect-tolerant and fully testable pla  this paper presents a defect-tolerant and fully testable pla allowing for the repair of a defective chip. the repair process is described. special emphasis is devoted to the location of defects inside a pla. the defect location mechanism is completely topological and circuit independent and therefore easy to adapt to existing pla generators. yield considerations for this type of plas are presented.  n. wehn m. glesner k. caesar p. mann a. roth
mixing buffers and pass transistors in fpga routing architectures  the routing architecture of an fpga consists of the length of the wires, the type of switch used to connect wires (buffered, unbuffered, fast or slow) and the topology of the interconnection of the switches and wires. fpga routing architecture has a major influence on the logic density and speed of fpga devices. previ? work [] based on a 0.35um cmos process has suggested that an architecture consisting of length 4 wires (where the length of a wire is measured in terms of the number of logic blocks it passes before being switched) and half of the programmable switches are active buffers, and half are pass transistors. in that work, however, the topology of the routing architecture prevented buffered tracks from connecting to pass-transistor tracks. this restriction prevents the creation of interconnection trees for high fanout nets that have a mixture of buffers and pass transistors. electrical simulations sug?t that connections closer to the leaves on interconnection trees are faster using pass transistors, but it is essential to buffer closer to the source. this latter effect is well known in regular asic routing [2].  in this work we propose a new routing architecture that allows liberal switching between buffered and pass transistor tracks. we explore various versions of the architecture to determine the den?y-speed trade-off. we show that one version of the new architec?e results in fpgas with 10% faster critical path delay yet uses the same area as the previous architecture that does not allow such switching. we also show that the new architecture allows a useful area-speed trade off and several versions of the new architecture result in fpgas with 8% gain in area- delay product than the previ? architecture that does not allow the switching.  mike sheng jonathan rose
esp: a new standard cell placement package using simulated evolution  esp (evolution-based standard cell placement) is a new program package designed to perform standard cell placement and includes macro-block placement capabilities. it uses the new heuristic method of simulating an evolutionary process in order to minimize the cell interconnection wire length. while achieving results comparable to or better than the popular simulated annealing algorithm, esp performs its task about ten times faster.  r.-m. kling p. banerjee
the theory of signature testing for vlsi  several methods for testing vlsi chips can be classified as signature methods. both conventional and signature testing methods apply a number of test patterns to the inputs of the circuit. the difference is that a conventional method examines each output, while a signature method first accumulates the outputs in some data compression device, then examines the signature - the final contents of the accumulator - to see if it agrees with the signature produced by a good chip. signature testing methods have several advantages, but they run the risk that masking may occur. masking is said to occur if a faulty chip and a good chip behave differently on the test patterns, but the signatures are identical. when masking occurs, the signature testing method will incorrectly conclude that the chip is good, whereas a conventional method would discover that the chip is defective.  this paper gives theoretical justification to the use of several signature testing techniques. we show that for these methods, the probability that masking will occur is small. an important difference between this and other work is that our results require very few assumptions about the behavior of faulty chips. they hold even in the presence of so-called correlated errors or even if the circuit were subject to sabatoge.  when we speak of the probability of masking, we use the probabilistic approach of gill, rabin and others. that is, we introduce randomness into the testing method in a way which can be controlled by the designer. thus, one theorem assumes that the order of the input patterns - or the patterns themselves - is random; another assumes that the connections between the chip and the signature accumulator are made randomly, and a third assumes that the signature accumulator itself incorporates a random choice.  most of the results of this paper use a particularly simple and practical signature accumulator based on a linear feedback shift register.  j. lawrence carter
architecture of centralized field-configurable memory  as the capacities of fpgas grow, it becomes feasible to implement the memory portions of systems directly on an fpga together with logic. we believe that such an fpga must contain specialized architectural support in order to implement memories efficiently. the key feature of such architectural support is that it must be flexible enough to accommodate many different memory shapes (widths and depths) as well as allowing different numbers of independently- addressed memory blocks. this paper describes a family of centralized field- configurable memory architectures which consist of a number of memory arrays and dedicated mapping blocks to combine these arrays. we also present a method for comparing these architectures, and use this method to examine the tradeoffs involved in choosing the array size and mapping block capabilities.  steven j. e. wilton jonathan rose zvonko g. vranesic