waashk/acm huggingface dataset:
on the syllogistic structure of object-oriented programming  _recent works by sowa and by rayside & campbell demonstrate that there is a strong connection between object-oriented programming and the logical formalism of the syllogism, first set down by aristotle in the_ prior analytics. _in this paper, we develop an understanding of polymorphic method invocations in terms of the syllogism, and apply this understanding to the design of a novel editor for object- oriented programs. this editor is able to display a polymorphic call graph, which is a substantially more difficult problem than displaying a non- polymorphic call graph. we also explore the design space of program analyses related to the syllogism, and find that this space includes unique name, class hierarchy analysis, class hierarchy slicing, class hierarchy specialization, and rapid type analysis._  derek rayside kostas kontogiannis
low-level ada tasking support for gnat-performance and portability improvements gnarl is the tasking runtime system of the gnu nyu ada95 translator (gnat). gnarl is divided into two main layers, the lower of which isolates dependences on a particular host operating system or real-time kernel. for portability, the primary implementation of this lower level accesses os services via the posix interfaces. in this paper we describe our recent redesign of the low-level interface, to improve both performance and portability. performance comparisons between the new and old runtime system on solaris2.4 show up to approximately 40 percent improvement on tasking related operations. t. p. baker dong-ik oh seung-jin moon
improving java performance using hardware translation  state of the art java virtual machines with just-in-time (jit) compilers make use of advanced compiler techniques, run-time profiling and adaptive compilation to improve performance. however, these techniques for alleviating performance bottlenecks are more effective in long running workloads, such as server applications. short running java programs, or client workloads, spend a large fraction of their execution time in compilation instead of useful execution when run using jit compilers. in short running java programs, the benefits of runtime translation do not compensate for the overhead.  we propose using hardware support to perform efficient java translation coupled with a light weight run time environment. the additional hardware performs the translation of java bytecodes to native code, thus eliminating much of the overhead of software translation. a _translate d code buffer_ is used to hold the translated code, enabling reuse at the byte code level. the proposed hardware can be used in any general purpose processor without degrading performance of native code. the proposed technique is extremely effective for short running client workloads. a performance improvement of 2.8 times to 7.7 times over a software interpreter is achieved. when compared to a jit compiler all specjvm98 benchmarks except one show a performance improvement ranging from. 2.7 times to 5.0 times. a performance degradation (0.58 times) is observed for one benchmark which is long running. allowing hardware translation to perform optimizations similar to jit compilers and java processors will execute long running programs more efficiently and provide speedups similar to that of client workloads.  ramesh radhakrishnan ravi bhargava lizy k. john
address/memory management for a gigantic lisp environment or, gc considered harmful  the possibility of incredibly cheap, fantastically large media for storage gives rise to a realistic lisp memory management scheme under which gc may be postponed for days, or even indefinitely; the idea is encapsulated in the acronym "ddi"\---"gc? don't do it!". tertiary memory is used to archive pages of the lisp environment which are perhaps reclaimable, but which have not been proven so; whereas the standard technique of "paging" is used to swap active data from the main memory to a secondary store such as magnetic disk. some scenarios are presented considering a variety of currently-available technologies, and of one speculative possibility---videodisc---by which a requisite compactifying gc would be done "overnight", or over the weekend. with enough tertiary available, one design could last for over 12 years without a gc. "write-once" memories, probably unusable for most applications, would not be at a disadvantage here.  jon l. white
plowing  the magic layout editor provides a new operation called plowing, for stretching and compacting manhattan vlsi layouts. plowing works directly on the mask-level representation of a layout, allowing portions of it to be rearranged while preserving connectivity and layout-rule correctness. the layout and connectivity rules are read from a file, so plowing is technology independent. plowing is fast enough to be used interactively. this paper presents the plowing operation and the algorithm used to implement it.  walter s. scott john k. ousterhout
practical automated design of lsi for large computers  the design of large computers using lsi techniques requires relatively large numbers of different designs in relatively small quantities. the paper describes a system of designing integrated circuits rapidly and reliably in this environment using the uncommitted logic array (master slice) approach. an integrated design, validation and production system has been developed from logical input to pattern generator tape production which takes away the need for knowledge of silicon layout techniques from the integrated circuit designer.  j philip singleton nigel r crocker
analysis of multiprocessor cache organizations with alternative main memory update policies  cache memory has played a significant role in the memory hierarchy and has been used extensively in large systems and minisystems. the effectiveness of cache memories with alternative main memory update policies in a multiprocessor system is a major concern in this paper. the performances of write-through with write-allocation or no-write allocation, buffered write- through, flag-swap, and buffered flag-swap policies have been analyzed. because of the dominating cost of the interface between processors and main memory modules in the multiprocessor system, the effect of varying the bus width or block size has also been considered. queuing models were developed to analyze these alternative organizations, and results predicted by the models were validated by a set of simulations.  w. c. yen k. s. fu
forward semantic: a compiler-assisted instruction fetch method for heavily pipelined processors  a new instruction fetch method, forward semantic, is offered to enable the deeply pipelined processors to fetch one useful instruction every cycle. forward semantic is an improved alternative to the delayed branching (with or without squashing), with five major advantages. fist, no restriction is imposed on the type of instructions filling the branch slots, which allows a large number of slots to be filled. second, no modification to the offsets and displacements is necessary when an instruction is copied to fill a branch slot, which simplifies the linker implementation. third, an interrupted program can resume execution with a single program counter, eliminating the need for reloading the instruction pipeline before resuming execution. fourth, programs compiled with n slots can execute on pipelines requiring k (k ≤ n) slots, which makes family architecture compatibility possible . lastly, the filling of branch slots is totally transparent to code compaction and software interlocking schemes. these advantages combine to provide an efficient instruction fetch mechanism and to eliminate artificial penalties on branch cost. at the cost of 11% static code expansion, forward semantic achieves an instruction fetch cost of 1.2 cycles for pipelines requiring 10 slots for each taken branch. this level of instruction fetch efficiency has never been achieved before with conventional instruction fetch methods. the branch cost is dictated by the accuracy of the compile-time branch prediction rather than artificial limitations, such as data dependencies, which prevent the slots from being filled. these results are measured from the execution of real unix and cad programs with complex control structures.  p.-h. chang w.-m. w. hwu
delaying physical register allocation through virtual-physical registers  register file access time represents one of the critical delays of current microprocessors, and it is expected to become more critical as future processors increase the instruction window size and the issue width. this paper present a novel physical register management scheme that allows for a late allocation (at the end of execution) of registers. we show that it can provide significant savings in number of registers and thus, it can significantly shorter the register file access time. the approach is based on virtual-physical registers, which we presented in a previous work, extended with a new register allocation policy. this policy consists of an on- demand allocation in order to maximize the register usage, combined with a stealing mechanism that prevents older instruction from being delayed by younger ones. this shortens the average number of cycles that each physical register is allocated, and allows for an early execution of instructions since they can obtain a physical register for its destination earlier than with the conventional scheme. early execution is especially beneficial for branches and memory operations, since the former can be resolved earlier and the latter can prefetch their data in advance.  teresa monreal antonio gonzalez mateo valero jose gonzalez victor vinals
fast integrated tools for circuit design with fpgas  to implement high-density and high-speed fpga circuits, designers need tight control over the circuit implementation process. however, current design tools are unsuited for this purpose as they lack fast turnaround times, interactiveness, and integration. we present a system for the xilinx xc6200 fpga, which addresses these issues. it consists of a suite of tightly integrated tools for the xc6200 architecture centered around an architecture- independent tool framework. the system lets the designer easily intervene at various stages of the design process and features design cycle times (from an hdl specification to a complete layout) in the order of seconds.  stephan w. gehring stefan h.-m. ludwig
truth in spec benchmarks  the system performance evaluation cooperative (spec) benchmarks are a set of integer and floating-point programs that are intended to be "effective and fair in comparing the performance of high performance computing systems". spec ratings are often quoted in company advertising and have been trusted as the de facto measure of comparison for computer systems. recently, there has been some concern regarding the fairness and the value of these benchmarks for comparing computer systems.  in this paper we investigate the following two questions regarding the spec92 benchmark suite: 1) how sensitive are the spec ratings to various tunings? 2) how reproducible are the published results? for six vendors, we compare the published specpeak and specbase ratings, and observe an 11% average improvement in the specpeak ratings due to changes in the compiler flags alone. in our own attempt to reproduce the published spec ratings, we came across various "explicit" and "hidden" tuning parameters that we consider unrealistic. we suggest a new unit called specsimple that requires using only the -o compiler optimization flag, shared libraries, and standard system configuration. specsimple is designed to better match the performance experienced by a typical user. our measured specsimples are 65-86% of the advertised specpeak performance. we conclude this paper by citing cases compiler optimizations specifically designed for spec programs, in which performance decreases drastically or the computed results are incorrect if the compiled program does not exactly match the spec benchmark program. these findings show that the fairness and value of the popular spec benchmarks are questionable.  nikki mirghafori margret jacoby david patterson
an efficient variable-cost maze router  a variable cost maze router is described. the router is substantially faster than most other maze routers and also provides a flexibility which is valuable in a variety of ways. it is particularly well suited for use on multiple layer routing surfaces in which adjacent layers have primary wire directions which are perpendicular to each other. the router has been incorporated as a final phase into both a circuit board routing system and an lsi gate array router. experience with these systems is described. potential applications of the variable cost ability are also discussed.  robert k. korn
general decomposition of sequential machines: relationships to state assignment  in this paper, we present new techniques for state assignment of finite state machines based on state machine decomposition algorithms.  a finite state machine can be decomposed into smaller interacting machines so as to optimize area and performance of the eventual logic implementation. a recently proposed form of decomposition, which has been shown to be superior to previous decomposition methods, involves identifying subroutines or factors in the original machine and extracting these factors to produce factored and factoring machines.  optimal state assignment corresponds to finding an optimal multiple general decomposition of a finite state machine. we present state assignment techniques targeting two-level and multi-level logic implementations based on factorization algorithms followed by state assignment algorithms. for the two- level case, we prove that one-hot encoding a non-trivially factored machine is guaranteed to produce a better result than one-hot encoding the original machine. experimental results indicate that this technique of factorization followed by state assignment is superior to previous state assignment techniques for large sequential machines, when targeting either two-level or multi-level implementations.  s. devadas
breakpoints and breakpoint detection in source-level emulation  we present an approach for accelerating the validation speed of behavioral system descriptions through hardware emulation. the method allows source-level debuggingof running hardware specified in behavioral vh dl in a way similar to sorce-leve debugging in software programing languages. we discuss breakpoints in source-level emulation and how the circuit generated by high-level synthesis has to be modified to work with breakpoints. breakpoint encoding and detection are shown in detail. our approach allows breakpoint detection by hardware with seriously slowing the circuit or dramitically increasing its size.  gernot h. koch w. rosenstiel u. kebschull
multi-level network optimization for low power  this paper describes a procedure for minimizing the power consumption in a boolean network under the zero delay model. power is minimized by modifying the function of each intermediate node in the network such that the power consumption of the node is decreased without increasing the power consumption of the other nodes in the network. a formal analysis of how changes in the switching activity of an intermediate node affect the switching activity of other nodes in the networks is given first. using this analysis, a procedure for calculating the set of compatible power don't cares for each node in the network is presented. finally it is shown how these don't cares are used to optimize the network for low power. these techniques have been implemented and results show an average of 10% improvement in total power consumption of the network compared to the results generated by the conventional network optimization techniques.  sasan iman massoud pedram
performance-driven constructive placement  a new approach to the performance-driven placement based on a window concept is presented. we first convert timing constraints to geometric shapes using the defined windows. a window represents a region in which all the modules along a given path can be placed without degrading the circuit performance. then a constructive placement process uses the window information to select an unplaced module, and to find an appropriate position for the module. this approach represents a unified way to consider both timing and geometric constraints during the placement process. the experimental results show that the improvement of circuit performance can be achieved by the sufficient use of the window information.  ichiang lin david h. c. du
a fully associative software-managed cache design  as dram access latencies approach a thousand instruction-execution times and on-chip caches grow to multiple megabytes, it is not clear that conventional cache structures continue to be appropriate. two key features---full associativity and software management---have been used successfully in the virtual-memory domain to cope with disk access latencies. future systems will need to employ similar techniques to deal with dram latencies. this paper presents a practical, fully associative, software-managed secondary cache system that provides performance competitive with or superior to traditional caches without os or application involvement. we see this structure as the first step toward os- and application-aware management of large on-chip caches.  this paper has two primary contributions: a practical design for a fully associative memory structure, the indirect index cache (iic), and a novel replacement algorithm, generational replacement, that is specifically designed to work with the iic. we analyze the behavior of an iic with generational replacement as a drop-in, transparent substitute for a conventional secondary cache. we achieve miss rate reductions from 8% to 85% relative to a 4-way associative lru organization, matching or beating a (practically infeasible) fully associative true lru cache. incorporating these miss rates into a rudimentary timing model indicates that the iic/generational replacement cache could be competitive with a conventional cache at today's dram latencies, and will outperform a conventional cache as these cpu-relative latencies grow.  erik g. hallnor steven k. reinhardt
technology-independent circuit layout  as physical implementation of electronic circuits has evolved from discrete component printed circuit boards to very large scale integrated circuits, there has been increasing economic pressure to automate the layout design process. early efforts to use computer- based layout focused on relatively simple pcb's, while recently developed layout tools address the demands of quite complex ic layout tasks. it has become evident that it is economically impractical to develop comprehensive layout systems that focus on a single circuit style or technology. hence, increasing attention has been given to layout tools that are relatively technology independent. that is, they may be successfully applied to a diversity of layout problem styles having different floorplans, design rules, and component attributes.  we would prefer to develop and support design tools that are "technology independent"; in the sense that for both printed circuit boards and integrated circuits having these diverse characteristics the software basis for these tools is common.  robert j. smith
logic partition orderings for multi-fpga systems  one of the critical issues for multi-fpga systems is developing software tools for automatically mapping circuits. in this paper we consider one step in this process, partitioning. we described the task of finding partition orderings, i.e., determining the way in which a circuit should be bipartitioned so as to best map it to a multi-fpga system. this allows multi-fpga partitioners to harness standard partitioning techniques. we develop an algorithm for finding partition orderings, which includes a method for increasing parallelism in the process, as well as for including multi-sectioning and multi-way partitioning algorithms. this method is very efficient, and capable of handling most of the current multi-fpga topologies.  scott hauck gaetano borriello
a redesign technique for combinational circuits based on gate reconnections  in this paper, we consider a redesign technique applicable to combinational circuits implemented with gate-array or standard-cell technology, where we rectify an existing circuit only by reconnecting gates on the circuit with all the gate types unchanged. this constraint allows us to reuse the original placement as is, thereby speeding up the total time needed for a redesign. we formulate this problem as a boolean-constraint problem and give a bdd-based algorithm to check the feasibility of redesign.  yuji kukimoto masahiro fujita robert k. brayton
on the use of registers vs. cache to minimize memory traffic  single- chip computers are becoming increasingly limited by the access constraints to off-chip memory. to achieve high performance, the structure of on-chip memory must be appropriate, and it must be allocated effectively to minimize off-chip communication. we report experiments that demonstrate that on-chip memory can be effective for local variable accesses. for best use of the limited on-chip area, we suggest organizing memory as registers and argue that an effective register spilling scheme is required. we introduce a heuristic algorithm for register spilling within basic blocks and demonstrate that trace optimization techniques can extend the use of the algorithm to global allocation. through trace simulation, we show that the use of registers can be more effective in reducing the bus traffic than cache memory of the same size.  j. r. goodman w. c. hsu
reduced offsets for two-level multi-valued logic minimization  the approaches to two-level logic minimization can be classified into two groups: those that use tautology for expansion of cubes and those that use the offset. tautology based schemes are generally slower and often give somewhat inferior results, because of a limited global picture of the way in which the cube can be expanded. if the offset is used, usually the expansion can be done quickly and in a more global way because it is easier to see effective directions of expansion. the problem with this approach is that there are many functions that have a reasonable size onset and don't care set but the offset is unreasonably large. it was recently shown that for the minimization of such boolean functions, a new approach using reduced offsets, provides the same global picture and can be computed much faster. in this paper we extend reduced offsets to logic functions with multi-valued inputs.  abdul a. malik robert k. brayton a. richard newton alberto l. sangiovanni- vincentelli
matching and searching analysis for parallel hardware implementation on fpgas  matching and searching computations play an important role in the indexing of data. these computations are typically encoded in very tight loops with a single index variable and a simple search/ matching predicate. their inherent sequential nature, either because of data dependences but more often because of very strong control dependences, makes it impossible to apply existing data dependence and parallelization analysis to exploit significant levels parallelism on traditional architectures. this paper describes a class of searching and matching computations and describes a mapping strategy to map these computations to hardware. we have developed a compiler analysis in suif using array data dependence analysis and implicit loop unrolling analysis to expose more parallelism for the parallel evaluation of these computations. our compiler generates parallel hardware specifications in vhdl. the resulting parallel hardware yields significant performance improvements when these kernel operators are repeated over shifted portions of the input data on fpga- based computing architectures.  pablo moisset pedro diniz joonseok park