waashk/acm huggingface dataset:
integrating superscalar processor components to implement register caching  a large logical register file is important to allow effective compiler transformations or to provide a windowed space of registers to allow fast function calls. unfortunately, a large logical register file can be slow, particularly in the context of a wide-issue processor which requires an even larger physical register file, and many read and write ports. previous work has suggested that a register cache can be used to address this problem. this paper proposes a new register caching mechanism in which a number of good features from previous approaches are combined with existing out-of-order processor hardware to implement a register cache for a large logical register file. it does so by separating the logical register file from the physical register file and using a modified form of register renaming to make the cache easy to implement. the physical register file in this configuration contains fewer entries than the logical register file and is designed so that the physical register file acts as a cache for the logical register file, which is the backing store. the tag information in this caching technique is kept in the register alias table and the physical register file. it is found that the caching mechanism improves ipc up to 20% over an un-cached large logical register file and has performance near to that of a logical register file that is both large and fast.  matthew postiff david greene steven raasch trevor mudge
an optimal clock period selection method based on slack minimization criteria  an important decision in synthesizing a hardware implementation from a behavioral description is selecting the clock period to schedule the datapath operations into control steps. prior to scheduling, most existing behavioral synthesis systems either require the designer to specify the clock period explicitly or require that the delays of the operators used in the design be specified in multiples of the clock period. an unfavorable choice of clock period could result in operations being idle for a large portion of the clock period and, consequently, affect the performance of the synthesized design. in this article, we demonstrate the effect of clock slack on the performance of designs and present an algorithm to find a slack-minimal clock period. we prove the optimality of our method and apply it to several examples to demonstrate its effectiveness in maximizing design performance.  en-shou chang daniel d. gajski sanjiv narayan
a fast approach to computing exact solutions to the resource-constrained scheduling problem this article presents an algorithm that substantially reduces the computational effort required to obtain the exact solution to the resource constrained scheduling (rcs) problem. the reduction is obtained by (a) using a branch-and-bound search technique, which computes both upper and lower bounds, and (b) using efficient techniques to accurately estimate the possible time-steps at which each operation can be scheduled and using this to prune the search space. results on several benchmarks with varying resource constraints indicate the clear superiority of the algorithm presented here over traditional approaches using integer linear programming, with speed-ups of several orders of magnitude. m. narasimhan j. ramanujam
average interconnection length and interconnection distribution based on rent's rule  in this paper we show that it is necessary to utilize different partitioning coefficients in interconnection length analyses which are based on rent's rule, depending on whether one- or two-dimensional placement strategies are used. β, the partitioning coefficient in the power-law relationship αΒβ, provides a measure of the number of interconnections which cross a boundary enclosing Β blocks. the partitioning coefficients are β=p/2 and β=p for two- and one-dimensional arrays, respectively, where p is the experimental coefficient of the rent relationship t=αΒ~~p. based on these separate partitioning coefficients, an average interconnection length prediction is presented for rectangular arrays that outperforms existing predictions. examples are given to support this theory.  c. v. gura j. a. abraham
futures for partitioning in physical design (tutorial)  the context for partitioning in physical design is dominated by two concerns: top-down design and the focus on spatial embedding. the role of partitioning is exactly that of a facilitator of divide-and-conquer metaheuristics for floorplanning, timing and placement optimization. formulations or optimization objectives for partitioning follow from its context and role. finally, the available algorithm technology determines how effectively we can address a given partitioning formulation and optimize a given objective. this invited paper considers the future of partitioning for physical design in light of these factors, and proposes a list of technology needs. a living version of this paper can be found at vlsicad.cs.ucla.edu.  andrew b. kahng
an asynchronous matrix-vector multiplier for discrete cosine transform  this paper proposes an efficient asynchronous hardwired matrix-vector multiplier for the rwo-dimensional discrete cosine transform and inverse discrete cosine transform (dct/idct). the design achieves low power and high performance by taking advantage of the typically large fraction of zero and small-valued data in dct and idct applications. in particular, it skips multiplication by zero and dynamically activates/deactivates required bit- slices of fine-grain bit-partitioned adders using simplified, static-logic- based speculative completion sensing. the results extracted by both bit-level analysis and hspice simulations indicate significant improvements compared to traditional designs.  kyeounsoo kim peter a. beerel youpyo hong
parallel logic simulation on a network of workstations using parallel virtual machine  this paper explores parallel logic simulation on a network of workstations using a parallel virtual machine (pvm). a novel parallel implementation of the centralized-time event-driven logic simulation algorithm is carried out such that no global controlling workstation is needed to synchronize the advance of simulation time. further advantages of our new approach include a random partitioning of the circuit onto available workstations and a pipelined execution of the different phases of the simulation algorithm. to achieve a better load balance, we employ a semioptimistic scheme for gate evaluations (in conjunction with a centralized- time algorithm) such that no rollback is required. the performance of this implementation has been evaluated using the iscas benchmark circuits. speedups improve with the size of the circuit and the activity level in the circuit. analyses of the communication overhead show that the techniques developed here will yield even higher gains as newer networking technologies like atm are employed to connect workstations.  maciek kormicki ausif mahmood bradley s. carlson
a hardware switch level simulator for large mos circuits  the hss is a hardware switch level simulator that has been designed and built to be a useful and cost effective addition to a mos circuit designers tool set. the hss is based on the mossim software simulator, but has been further developed to include hardware for simulating pass transistor circuits and for doing timing simulation. by using dynamic ram for internal list storage, a single hss processor can accommodate a circuit of up to 262,144 mos devices. the hss can be interfaced to a variety of host computers via a general purpose parallel interface, and in its current form offers a 25 times speed improvement compared to mossim ii running on a vax 11-780. timing mode offers similar speed advantages, with delay calculations that are sufficiently accurate for many simulation tasks.  m. t. smith
generation of universal series-parallel boolean functions  the structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. in order to make good use of this mapping technique in ftga design, it is desirable to design fpga logic modules based on boolan functions which can be represented by a tree of gates (i.e., series- parallel or sp functions). thakur and wong [1996a; 1996b] studied this issue and they demonstrated the advantages of designing logic modules as universal sp functions, that is, sp functions which can implement all sp functions with a certain number of inputs. the number of variables in the universal function corresponds to the number of inputs to the fpga module, so it is desirable to have as few variables as possible in the constructed functions. the universal sp functions presented in thakur and wong [1996a; 1966b] were designed manually. recently, there is an algorithm that can generate these functions automatically [young and wong 1997], but the number of variables in the generated functions grows exponentially. in this paper, we present an algorithm to generate, for each n > 0, a universal sp function fn for implementing all sp functions with n inputs or less. the number of variables in fn is less than n2.376 and the constructions are the smallest possible when n is small (n ≤ 7). we also derived a nontrival lower bound on the sizes of the optimal universal sp functions ( (n log n)).  f. y. young chris c. n. chu d. f. wong
a comparison of four two-dimensional gate matrix layout tools  a comparison of four layout tools is presented. the layout style is a two- dimensional gate matrix. the first layout tool discussed uses "standard" simulated annealing. annealing on gate clusters instead of individual gates can be used to improve the layout results. two different ways of determining good gate clusters for use in the annealing process are compared. the first way uses clusters derived from user specified gate hierarchies, while the second determines clusters based on gate connectivity. the fourth layout tool uses a decomposition scheme based on quadrisection. layout results for a set of benchmark circuits are presented for each of the tools.  m. j. irwin r. m. owens
excl  this paper describes excl, an automated circuit extraction program that transforms an ic layout into a circuit representation suitable for detailed circuit simulation. the program has built-in, general extraction algorithms capable of accurate computations of interconnection resistance, internodal capacitance, ground capacitance, and transistor sizes. however, where possible, the general algorithms are replaced with simple techniques, thereby improving execution speed. a basic component of the extractor is a procedure that decomposes regions into domains appropriate for specialized or simple algorithms. the paper describes the decomposition algorithm, the extraction algorithms and discusses how they connect with the rest of excl.  steven p. mccormick
nes: the behavioral model for the formal semantics of a hardware design language udl/i  this paper describes a new behavioral model of hardware, named nes (nondeterministic event sequence) model, which was developed for the purpose of defining formal semantics of the gate level and the register transfer level hardware description languages. the nes model is a generalization of the event driven simulation, and can be a basis of synthesis and verification as well as simulation. we introduce basic concepts, formal definition, and a description method of the nes model.  nagisa ishiura hiroto yasuura shuzo yajima
gate matrix layout of random control logic in a 32-bit cmos cpu chip adaptable to evolving logic design  previously the gate matrix technique was used to lay out the ralu section of a cmos 32-bit cpu chip. it took 1.2 engineer-years to complete the layout of the ralu that contained more than 20,000 transistors with multiple-bus structure. the average packing density was 840 μm2 per transistor in 2.5 μm design rules. recently we have applied the gate matrix technique to lay out the highly complex "random control logic" of the cpu. with a well-structured layout strategy, the gate matrix layout provided (1) adaptability to evolving logic design with short turnaround times, (2) compatibility with computer aids in layout verification, (3) high packing density competitive with hand layout, and (4) compatibility with a team approach to layout. it took 6.5 engineer- years to complete the error-free layout of over 7,000 transistors although the logic design was continuously evolving during the layout period. more than half of the layout efforts were due to logic changes. the average packing density in the final layout of the random control logic was about 1,500 μm2 per transistor with 2.5 μm design rules.  s. m. kang r. h. krambeck h. f. s. law
digital cmos logic operation in the sub-threshold region  numerous efforts in balancing the trade-off between power, area and performance have been carried out in the medium performance, medium power region of the design spectrum. however, not much study has been done at the two extreme ends of the design spectrum, namely, the ultra-low power with acceptable performance at one end, and high performance with power within limit at the other. in this paper, we focus on the ultra-low power end of the spectrum where performance is of secondary importance. one solution to achieve the ultra-low power requirement is to operate the digital logic gates in sub- threshold region. in this paper, we analyze both cmos and pseudo-nmos logic operating in sub- threshold region. we compare the results with cmos in normal strong inversion region and with other known low-power logic, namely, energy recovery logic. results show energy/switching reduction of two orders of magnitude from an 8×8 carry-save array multiplier when it is operated in the sub- threshold region.  hendrawan soeleman kaushik roy
universal logic gate for fpga design  in this paper the problem of selecting an appropriate programmable cell structure for fpga architecture design is addressed. the cells studied here can be configured to the desired functionality by applying input permutation, negation, bridging or constant assignment, or output negation. a general methodology to determine logic description of such cells, which are capable of being configured to a given set of functions is described.  experimental results suggest that the new cell behaves as well as the actel 2 cell in terms of logic power but requires substantially less area and wiring overhead.  chih-chang lin malgorzata marek-sadowska duane gatlin
re-encoding sequential circuits to reduce power dissipation  we present a fully implicit encoding algorithm for minimization of average power dissipation in sequential circuits, based on the reduction of the average number of bit changes per state transition.  we have studied two novel schemes for this purpose, one based on recursive weighted non- bipartite matching, and one on recursive minicut bi- partitioning. we employ adds (algebraic decision diagrams) to computate the transition probabilities, to measure the potential area saving, and in the encoding algorithms themselves.  our experiments show the effectiveness of our method in reducing power dissipation for large sequential designs.  gary d. hachtel mariano hermida abelardo pardo massimo poncino fabio somenzi
will your bridge stand the load? (position paper)  the successful exploitation of lsi for creating products with greater function at reduced cost per operation is critically dependent on the availability of design systems that comprehend the job to be done. as system and component technologies continue their rapid rate of development, there is an increasingly higher probability that our ability to capitalize on them will be severely impacted by the lack of appropriate design system technology development. these impacts will take the form of our inability to deliver an affordable product to the marketplace while the demand still exists and before the technology is completely absolete.  this position statement is not intended as an indictment of those who presently plan and implement "da" but rather it is a warning to both users and developers of da indicating where we will end up unless we look beyond the activities that engage us today and change our focus from "design automation tools" to "product design systems".  a. e. fitch
a vlsi view of microprogrammed system design  in this paper, the possible effects of vlsi technology on the design and development process of microprogrammed systems are explored. the function architectures of future microprogrammed vlsi systems are expected to be very complex, and most of them will be implemented as heterogeneous multiprocessors with each processor being microprogrammed to perform specific tasks. current microprogrammed system design methodologies are examined and are shown to be inadequate. a new design methodology employing a synthetic approach for developing microprogrammed systems is proposed.  tientien li
testing an integrated circuit for what it should not do (abstract only)  integrated circuits are designed to perform some intended function. this is true not only of the circuit as a whole, but also of all of the functional parts that make up the circuit. the general philosophy of testing is to provide some sequence of inputs and test to see if the outputs reflect the intended function. little notice is given to the possibility that the circuit may have produced undesirable side effects. for example, a processor that is given a "load accumulator" instruction may indeed load data into the accumulator exactly as desired, but it may also incorrectly change the contents of some other register. the problem with testing for this condition is that the number of possibilities may be very large and the time required for exhaustive testing may become excessive. furthermore, it may become difficult to identify the meaningful possibilities to check for. this paper presents a case study for problems of this kind and shows how the problems encountered defy recognition by normal logic simulation and test generation techniques. extended methods of test generation are proposed for identifying problems of this type.  charles kapps
hardware microcontrol schemes using plas  four new schemes for microprogram control design with programmable logic arrays (plas) are proposed. the general structure of the first three schemes consists of three units namely, the microcode memory (rom), the microsequencer pla, and a register-counter. the basic idea is to store only branching information, by means of control constructs or transactions, in the pla(s). these transactions have simple jump-type or continue-type formats with only the jump being embedded in pla(s).  a more general structure, scheme 4, is also proposed with the objective to generate powerful transactions implementing complex control constructs, such as microsubroutines, nested microprogram loops, etc., in addition to multiway branch capability. these transactions contain horizontally formatted directive bits and, hence, they exhibit a measure of parrallelism. the aim is to transform the sequencing structure of a microprogram into a "program" composed of these transactions. however, a directive-driven processor is required to execute each transaction in order to produce the desired address.  christos a. papachristou
on routing two-point nets across a channel  many problems that arise in general channel routing manifest themselves in simpler situations. we consider connecting a set of n terminals on a line to another set on a parallel line across a rectangular channel. we show that in any solution to the problem that (almost) minimizes the width of the channel (i.e. the distance between the lines the terminals reside on)  a net may require as many as ?(?n) horizontal jogs  no net routed from top to bottom need ever turn upward in the middle  we also present an efficient algorithm to obtain minimal jogging in river routing, and provide necessary and sufficient conditions for conflict cycle resolution.  these and other results are presented in the context of a general survey on routing from a combinatorial complexity point of view.  ron y. pinter
footprints in the cache  this paper develops an analytical model for a cache-reload transient. when an interrupt program or system program runs periodically in a cache-based computer, a short cache-reload transient occurs each time the interrupt program is invoked. that transient depends on the size of the cache, the fraction of the cache used by the interrupt program, and the fraction of the cache used by background programs that run between interrupts. we call the portion of a cache used by a program its footprint in the cache, and we show that the reload transient is related to the area in the tail of a normal distribution whose mean is a function of the footprints of the programs that compete for the cache. we believe that the model may be useful as well for predicting paging behavior in virtual-memory systems with round-robin scheduling.  harold s. stone dominique thibaut
a reconfigurable multi-function computing cache architecture  a considerable portion of a chip is dedicated to a cache memory in a modern microprocessor chip. however, some applications may not actively need all the cache storage, especially the computing bandwidth limited applications. instead, such applications may be able to use some additional computing resources. if the unused portion of the cache could serve these computation needs, the on-chip resources would be utilized more efficiently. this presents an opportunity to explore the reconfiguration of a part of the cache memory for computing. in this paper, we present a cache architecture to convert a cache into a computing unit for either of the following two structured computations, fir and dct/idct. in order to convert a cache memory to a function unit, we include additional logic to embed multi-bit output luts into the cache structure. therefore, the cache can perform computations when it is reconfigured as a function unit. the experimental results show that the reconfigurable module improves the execution time of applications with a large number of data elements by a large factor (as high as 50 and 60). in addition, the area overhead of the reconfigurable cache module for fir and dct/idct is less than the core area of those functions. our simulations indicate that a reconfigurable cache does not take a significant delay penalty compared with a dedicated cache memory. the concept of reconfigurable cache modules can be applied at level-2 caches instead of level-1 caches to provide an active- level-2 cache similar to active memories.  hue-sung kim arun k. somani akhilesh tyagi
lroute: a delay minimal router for hierarchical cplds  this paper describes lroute, a novel router for the popular and scalable hierarchical complex programmable logic devices (cplds). cpld routing has constraints on routing topologies due to architectural limitations and performance considerations. these constraints make the problem quite different from fpga routing and render the routing problem more complicated. extensions of popular fpga routers like the maze router performs poorly on such cplds. there is also little published work on cpld routing. lroute uses a different paradigm based on the lagrangian relaxation framework in the theory of mathematical programming. it respects the topology constraints imposed and routes a circuit with minimum delay. we tested this router on a set of industry problems that commercial software failed to route. our router was able to route all of them very quickly.  k. k. lee martin d. f. wong