waashk/acm huggingface dataset:
boosting beyond static scheduling in a superscalar processor  this paper describes a superscalar processor that combines the best qualities of static and dynamic instruction scheduling to increase the performance of non- numerical applications. the architecture performs all instruction scheduling statically to take advantage of the compiler's ability to efficiently schedule operations across many basic blocks. since the conditional branches in non- numerical code are highly data dependent, the architecture introduces the concept of boosted instructions, instructions that are committed conditionally upon the result of later branch instructions. boosting effectively removes the dependencies caused by branches and makes the scheduling of side-effect instructions as simple as those that are side-effect free. for efficiency, boosting is supported in the hardware by shadow structures that temporarily hold the side effects of boosted instructions until the conditional branches that the boosted instructions depend upon are executed. when the branch condition is determined, the buffered side effects are either committed or squashed. the limited static scheduler in our evaluation system shows that a 1.6-times speedup over scalar code is achievable by boosting instructions above only a single conditional branch. this performance is similar to the performance of a pure dynamic scheduler.  michael d. smith monica s. lam mark a. horowitz
a technology independent mos multiplier generator  a layout generator for technology independent implementation of the mos multiplier is described. the modified booth's algorithm with a structured floor plan has been used. the layout has been optimized and described as a program in a high level layout language. the fabrication process related information is maintained in a separate technology database that is coupled with the layout program at the time of execution to generate the mask data. the user can choose from a variety of architectures for speed, area, and power trade-off's. the user can also specify geometric and electrical constraints tailored to his system specification.  kung-chao chu ramautar sharma
vlsi circuit testing using and adaptive optimization model  the purpose of testing is to determine the correctness of the unit under test in come optimal way. one difficulty in meeting the optimality requirement is that the stochastic properties of the unit are usually unknown a priori. for instance, one might not know exactly the yield of a vlsi production line before one tests the chips made as a result. given the probability of unit failure and the coverage of a test, the optimal test period is easy to obtain. however, the probability of failure is not usually known a priori. we there- fore develop an optimal sequential testing strategy which estimates the production yield based on ongoing test results, and then use it to determine the optimal test period.  p. s. yu c. m. krishna y.-h. lee
a practical moat router  the final step in the layout of integrated circuits involves connecting a central module to a surrounding ring of pads. hence the region to be routed is in the shape of a moat. this paper presents a practical approach to the moat routing problem. the approach is based on an efficient channel routing algorithm with additional features addressing the characteristics of the moat configuration. while signal nets are similar to those of a channel router, power nets are routed in a single layer of metal. the geometry of the moat imposes some restrictions, but often allows additional compaction of the routes. each side of the moat requires a different amount of space to complete the routing, and each side of the pad ring may be moved independently. this produces an asymmetrical moat, which minimizes chip area and guarantees 100 percent routing completion.  r. k. mcgehee
a methodology and algorithms for the design of hard real-time multitasking asics  traditional high-level synthesis concentrates on the implementation of a single task (e.g. filter, linear controller, a/d converter). however, many applications---multifunctional embedded controllers intelligent wireless end- points, and dsp and multimedia servers---are defined as sets of several computational tasks. this paper describes new techniques for the synthesis of asic implementations that realize multiple computational processes under hard real-time constraints. our synthesis methodology establishes connections between two important comengineering domains: operating systems and behavioral synthesis. our hierarchical approach starts from an incompletely-specified preliminary solution and uses, interchangeably, operating system and behavioral synthesis techniques to derive increasingly more detailed and accurate design solutions. we have experimented with both optimal and heuristic algorithms to implement this methodology. the optimal algorithm uses several heuristics to speed up the average run time of an exhaustive branch- and-bound search. force-directed optimization is the core of the heuristic synthesis method. analysis of the proposed algorithms and the experiments shows that matching the number of bits and type of operational in taskes assigned to the same application-specific processor was the most important factor in obtaining area-efficient designs.  miodrag potkonjak wayne wolf
an efficient ilp-based scheduling algorithm for control-dominated vhdl descriptions  to adopt behavioral synthesis techniques in existing design flows, the synthesis methodology must provide the designer with a mechanism to specify a component's interface timing. this will permit pre- and postsynthesis validation through cosimulation with other subsystems or even through formal verification. in control-flow dominated designs, additional timing constraints will result in a complex specification/constraint system for which the scheduling problem has been shown to be np-complete. in this article, we present a mathematical framework for solving a special instance of the scheduling problem in control-flow dominated behavioral vhdl descriptions given that the timing of i/o signals has been completely or partially specified. it is based on a code-transformation approach that fully preserves the vhdl semantics. the scheduling problem is mapped onto an integer linear program (ilp) solvable in polynomial time assuming a restricted partial order on selected statements. it captures both control-flow and timing constraints in a single model and also exploits dataflow information to optimize the statement sequence across basic block boundaries.  michael munch norbert wehn manfred glesner
manhattan or non-manhattan?: a study of alternative vlsi routing architectures  circuit interconnect has become a substantial obstacle in the design of high performance systems. in this paper we explore a new routing paradigm that strikes at the root of the interconnect problem by reducing wire lengths directly. we present a non-manhattan steiner tree heuristic, obtaining wire length reductions of much as 17% _on average_, when compared to rectilinear topologies. moreover, we present a graph-based interconnect optimization algorithm, called the grats-tree algorithm, which allows performance optimization beyond what can be obtained through wire length reduction alone. the two tree construction algorithms are integrated into a new global router that allows large scale non-manhattan design. although we consider circuit placements performed under rectilinear objectives, our global router can reduce maximum congestion levels by as much as 20%. in general we find that the non-manhattan approach requires additional steiner points and bends; realization of non-manhattan routing structures requires additional vias. we observe that the increase in via cost is much less dramatic than might be expected; the benefits of wire length reduction may outweigh the additional via cost.  cheng-kok koh patrick h. madden
detecting bridging and stuck-at faults at input and output pins of standard digital components  due to the advances in the integrated circuit technology, there is an increasing importance in testing bridging (short circuit) failures in digital networks. unfortunately, very little work has been done in this area. this paper presents the schemes for the detection of feedback bridgings between the inputs and outputs through the observation of oscillation and asynchronous behavior of sequential networks created by bridging faults. the lower and upper bounds on the number of tests for detecting all feedback bridging faults are given. conditions for the undetectability of input bridgings are given and a method for testing input bridgings is presented. the results are generalized to detect bridging and stuck-at faults in the input and output lines of a multiple-output network. finally, the complete test sets are given for detecting input, output and feedback bridgings as well as stuck-at faults at the input and output pins of the standard integrated circuit chips including shift registers, counters, decoders, multiplexers, adders/subtracters, multipliers, dividers and ram.  mark karpovsky stephen y.h. su
facet: a procedure for the automated synthesis of digital systems  in the past decade significant effort has been devoted to the development of methodologies for design at the register-transfer level. however, effective and versatile procedures are still not available. this paper presents an efficient procedure for the automated synthesis of data paths at the register- transfer level. the procedure minimizes the numbers of storage elements, data operators, and interconnection units. in addition, the procedure has the capability of exploring alternatives in the design space. in some preliminary experiments the procedure produced designs nearly identical to commercially produced designs.  chia-jeng tseng daniel p. siewiorek
new efficient algorithms for computing effective capacitance  we describe a novel iterationless approach for computing the effective capacitance of an interconnect load at a driving gate output. our new approach is considerably faster than previous methods for computing effective capacitance, with little or no loss of accuracy. thus, the approach is suitable within the analysis loop for performance-driven iterative layout optimization. after reviewing previous gate load models and effective capacitance approximations, we separately derive our method for the cases of step and ramp waveform at the gate output, and note on-going extensions for the case of complex gates (e.g., channel-connected components). experimental results using the new effective capacitance approach show that our resulting delay estimates are quite accurate --- within 15% of iispice-computed delays on data corresponding to an 0.25 m microprocessor design.  andrew b. kahng sudhakar muddu
design of fpgas with area i/o for field programmable mcm  area-io provide a way to eliminate the io bottleneck of field programmable logic devices (fplds) created the mismatch between the ability of perimeter bonds to provide io and the propensity of logic to demand it. whether the incorporation of area io into fpld architectures has undesirable side effects is a question that has not yet been answered. in this paper, we examine the architectural impact of area-io on fplds from a theoretical and experimental standpoint and show that the introduction of area io generally improves the routability and delay of a set of benchmark circuits.  vijayshri maheshwari joel darnauer john ramirez wayne wei-ming dai
tolerating operational faults in cluster-based fpgas  in recent years the application space of reconfigurable devices has grown to include many platforms with a strong need for fault tolerance. while these systems frequently contain hardware redundancy to allow for continued operation in the presence of operational faults, the need to recover faulty hardware and return it to full functionality quickly and efficiently is great. in addition to providing functional density, fpgas provide a level of fault tolerance generally not found in mask-programmable devices by including the capability to reconfigure around operational faults in the field. in this paper, incremental cad techniques are described that allow functional recovery of fpga design configurations in the presence of single or multiple operational faults. our preferred approach to fault recovery takes advantage of device routing hierarchy in architectural families such as xilinx virtex [2] and altera apex [3] to quickly swap unused logic and routing resources in place of faulty ones within logic clusters. these algorithms allow for straight-forward implementation within a local fault-tolerant system without the need to access a remote processing location. if initial recovery attempts through localized swapping fail, an incremental router based on the widely- used pathfinder maze routing algorithm [10] can be applied remotely in an attempt to form connections between newly-allocated logic and interconnect based on the history of the initial design route.  vijay lakamraju russell tessier
a "gridless" variable-width channel router for marco cell design  in this paper, we present a channel router especially designed for routing macro cells. the router routes variable-width pins with wires of any width. although the router uses a routing grid internally, it acts like it is completely gridless to the user. pins along the top and the bottom edges of the channel can be at any x-location, and the router uses a channel compactor to compact all horizontal segments vertically. the router allows pins to be on either of the two routing layers. if all the power pins are on the same layer, the router routes the whole power bus in one single layer. it handles non- rectangular channels with highly irregular heights, and it also handles cyclic vertical constraints. finally, the router has been tested with a number of industrial circuits.  c. h. ng
an mos digital network model on a modified thevenin equivalent for logic simulation  a novel analytical model of mos digital networks, which is based on a modified thevenin equivalent, is described. the model can handle all the primary circuits inherent in mos technology, such as transistor logics, wired-ors, tri-state circuits, charge-share operation, and bidirectional pass transistors etc., with precise estimation of delay time.  the model has been implemented in a logic/fault simulator, named hasl-gt. performance of 4 to 10 k events/sec has been obtained on hitac m-200h(8mips). fault simulation capability has also been implemented using the concurrent method.  tsuyoshi takahashi satoshi kojima osamu yamashiro kazuhiko eguchi hideki fukuda
symmetry detection and dynamic variable ordering of decision diagrams  knowing that some variables are symmetric in a function has numerous applications; in particular, it can help produce better variable orders for binary decision diagrams (bdds) and related data structures (e.g., algebraic decision diagrams). it has been conjectured that there always exists an optimum order for a bbd wherein symmetric variables are contiguous. we propose a new algorithm for the detection of symmetries, based on dynamic reordering, and we study its interaction with the reordering algorithm itself. we show that combining sifting with an efficient symmetry check for contiguous variables results in the fastest symmetry detection algorithm reported to date and produces better variable orders for many bdds. the overhead on the sifting algorithm is negligible.  shipra panda fabio somenzi bernard f. plessier
maximizing memory data reuse for lower power motion estimation  this paper presents a new vlsi architecture of the motion estimation in mpeg-2. previously, a number of full search block matching algorithms (bma) and architectures using systolic array have been proposed for motion estimation. however, the architectures have an inefficiently large number of external memory access. recently, to reduce the number of accesses in one search block, a block matching method within a search area to reuse the search data is provided using systolic process arrays. to further reduce the data access and computation time during the block matching, we propose a new approach through the reuse of the previously-search data in two dimensions. our new architecture in this paper is an extension from our previous work such that we reuse the previously searches area not only between two consecutive columns but also between two consecutive rows, so as to entirely remove redundant memory access. experimental results show the efficiency of our algorithm.  bo-sung kim jun-dong cho
analysis and optimization of thermal issues in high-performance vlsi  this paper provides an overview of various thermal issues in high- performance vlsi with especial attention to their implications for performance and reliability. more specifically, it examines the impact of thermal effects on both interconnect design and electromigration reliability and discusses their impact on the allowable current density limits. furthermore, it also discusses how thermal and reliability constrained current density limits may conflict with those obtained through purely performance based criterion. additionally, it is shown that chip level thermal effects can have a significant impact on large-scale circuit optimization techniques, including the clock-skew minimization scheme, and can influence other physical design problem formulations. finally, high-current interconnect design rules for esd and i/o circuits are also examined.  kaustav banerjee massoud pedram amir h. ajami
udsys a microcode development system  this paper describes a microcode development system called udsys that is currently in use at data general corporation across several radically different micro-architectures. the system was developed to overcome some of the deficiencies of meta-assemblers, namely, one-to-one meaning of symbols vs. action, lack of rigorous syntax verification, and lack of application specific error messages. the system is explained by way of a specific example about the sequencer portion of a hypothetical microword.  microcoding is slowly loosing its status as an artform. many of the tools available for increasing the productivity of software engineers are now starting to become available for the generation of microcode. there is work being done on machine independent microcoding languages, microcode generators, and microcode optimizers to name but a few such tools. however, many of these tools are still in the developmental stages. at data general, our current microcode production system took the approach of leaving the optimization in the hands of the coder, but giving him the capability of building a very friendly interface to the hardware.  the system is called udsys and this paper presents an overview of some of its major concepts and features.  robert w. beauchamp neal r. firth
classes of diagnostic tests  this paper presents the results of an investigation into the types of tests useful for automatically diagnosing combinational digital devices. the diagnosis is based on a design model that allows hierarchy in both the structure and the data of the device being represented. a more general set of assumptions than is commonly employed allows data values other than boolean values to be diagnosed, and permits faults other than stuck-at faults to be found. the design model, the assumptions, and the tests are represented in subtle, a language based on predicate calculus and specialized for digital systems.  charles paulson
the case for registered routing switches in field programmable gate arrays  fpgas are characterized by a programmable interconnect that contains highly resistive and capacitive elements. while the configurable structure of the interconnect allows for the implementation of arbitrary circuits, it has also become a significant bottleneck for high-speed circuits. even if there are only a few signal paths that run along long stretches of interconnect, it is these paths that may determine the maximum operating frequency of the circuit.  in this paper we investigate architectural features that could allow us to automatically pipeline the delay associated with long routes without an excessive area penalty. the goal is to reschedule circuit operations in such a way that a signal may use multiple clock cycles to traverse a long route, rather than requiring a single long clock period. this rescheduling would not effect the timing of the visible outputs~(~no latency is added to the overall system~).  specifically, we analyze the effects of adding a small number of registered routing switches to an fpga architecture with segmented routing resources. a parameterized fpga architecture is studied where the percentage of registered routing switches is varied and the speed improvement and area penalty is evaluated. novel algorithms are presented that allow a circuit to best utilize an architecture with a given percentage of registered switches. we believe that this is the first study that attempts to evauate the tradeoffs associated with switches required in fpga architectures.  our experiments indicate that the architectural features introduced can produce significant speedup for high speed circuits without excessive area costs. we believe that these techniques will become increasingly important in the future as deep sub-micron process technologies shrink, and wire delays become even more significant.  deshanand p. singh stephen d. brown
performance measurement and trace driven simulation of parallel cad and numeric applications on a hypercube multicomputer  this paper presents the performance evaluation, workload characterization and trace driven simulation of a hypercube multi-computer running realistic workloads. six representative parallel applications were selected as benchmarks. software monitoring techniques were then used to collect execution traces. based on the measurement results, we investigated both the computation and communication behavior of these parallel programs, including cpu utilization, computation task granularity, message interarrival distribution, the distribution of waiting times in receiving messages, and message length and destination distributions. the localities in communication were also studied. a trace driven simulation environment was developed to study the behavior of the communication hardware under real workload. simulation results on dma and link utilizations are reported.  jiun-ming hsu prithviraj banerjee
raid: high-performance, reliable secondary storage  disk arrays were proposed in the 1980s as a way to use parallelism between multiple disks to improve aggregate i/o performance. today they appear in the product lines of most major computer manufacturers. this article gives a comprehensive overview of disk arrays and provides a framework in which to organize current and future work. first, the article introduces disk technology and reviews the driving forces that have popularized disk arrays: performance and reliability. it discusses the two architectural techniques used in disk arrays: striping across multiple disks to improve performance and redundancy to improve reliability. next, the article describes seven disk array architectures, called raid (redundant arrays of inexpensive disks) levels 0--6 and compares their performance, cost, and reliability. it goes on to discuss advanced research and implementation topics such as refining the basic raid levels to improve performance and designing algorithms to maintain data consistency. last, the article describes six disk array prototypes of products and discusses future opportunities for research, with an annotated bibliography disk array-related literature.  peter m. chen edward k. lee garth a. gibson randy h. katz david a. patterson