There are two concurrent paths in a typical cache access --- one through the data array and the other through the tag array. The path through the data array drives the selected set out of the array. The path through the tag array determines cache hit/miss and, for set-associative caches, selects the appropriate line from within the selected set. In both directmapped and set-associative caches, the path through the tag array is significantly longer than that through the data array. In this paper, we propose a path balancing technique to help match the delays of the tag and data paths. The basic idea behind this technique is to employ a separate subset of the tag array to decouple the one-to-one relationship between address tags and cache lines so as to achieve a design that provides higher performance. Performance evaluation using both TPC-C and SPEC92 benchmarks shows that this path balancing technique offers impressive improvements in overall system performance over conventional cache...

Prefetching techniques in disk caching are addressed. An adaptive prefetch design based on a run-time caching statistics of files is presented. Cache hit histories produced by prefetching are used as a measure of the file access sequentialities. Detailed cache design analysis is discussed using simulation results of a trace-driven model with traces collected from a personal system. The curves obtained from the adaptive design, although not the best at every point, track very well with the best curve in each operation. This shows the dynamic intelligence and efficiency of the file-based adaptive prefetching. The file-based design is compared with one that uses the same transition diagram on disk access but without file identification. The file-based adaptive design outperforms the non-file-based one consistently under all cache sizes.>

The development and comparison of two trace-driven simulation models for microsystems with tightly coupled, shared-bus multiprocessors is presented. One model monitors the complete activities of processors, private caches, global bus, and main memory, while the other first abstracts local bus activities of processors, and then takes care of the multiprocessing interaction. The second model provides a means to move more quickly within the design space, while the first model can be used to select a final optimized design. Examples are presented to illustrate how these simulation models can help a complex choice among architectures, system configurations, and chip parameters for the design of an optimized microsystem.>

Although many of the basic techniques of computer arithmetic have been known since the earliest days of electronic computing, there is a continuing need to re-evaluate them in the context of developments in VLSI circuit technology. Furthermore, recent work in complexity of algorithms, particularly the solution of recurrence relations, suggests new candidate structures for generating the carry vector and raises the questions as to their practicality in modern logic design practice.

This paper describes aspects of an arithmetic design system (ADS) to support the quantitative evaluation of alternate number systems with respect to a given application and realization technology. In computer arithmetic we are concerned with establishing a correspondence between abstract quantities (numbers) and some physical representation (symbols), and with simulating the operations on these symbols. The ADS is intended to help study the cost and performance of alternate simulations. A finite number system is a triple consisting of a symbol set (elements are called "digit-vectors"), an interpretation set, a mapping between these two sets, and a set of operators (digit-vector algorithms) defined on its symbol set. A set of these digit vector algorithms are proposed for conducting arithmetic design. A number system matrix defines the digit vector algorithm for numerous number systems and a method for computing time and space complexity of compositions of these algorithms is proposed. An example of how the system could be used to compare addition, with and without out-of-range detection, for three number systems is given.

This paper describes an evolving Arithmetic Design System (ADS) to support the quantitative evaluation of alternate number systems with respect to a given application and realization technology. In computer arithmetic we are concerned with establishing a correspondence between abstract quantities (numbers) and some physical representation (symbols), and with simulating the operations on these symbols. The ADS is intended to help study the cost and performance of alternate simulations. A finite number system is a triple consisting of a symbol set (elements are called "digit-vectors"), an interpretation set, a mapping between these two sets, and a set of operators (digit-vector algorithms) defined on its symbol set. A set of these digit vector algorithms are proposed for conducting arithmetic design. A number system matrix defines the digit vector algorithm for numerous number systems and a method for computing time and space complexity of compositions of these algorithms is proposed. An example of how the system could be used to compare addition, with and without overflow detection, for three number systems is given.

Component and time complexity measures in terms of number of gates and gate delays, respectively, are derived for two multioperand adder structures: a tree of carry-save adders and a tree of carry-lookahead adders. The parameters of the complexity measures are operand length, number of operands, and maximum fanin to the gates. The analysis involves a constructive derivation of the complexity of carry-lookahead networks including optimization by removal of redundant paths. An alternate measure of component complexity, number of packages with a given number of pinouts, rather than number of gates, is also presented.

This paper presents the results of one phase of a study concerning methods for addition of P>2 numbers, each encoded as a vector of digits (digit vector) of length N. Such multi-operand addition has been studied most often in the context of reducing a set of partial products to a single result in the implementation of multiplication. More generalized multi-operand addition, most notably in the form of inner product calculations is, however, central to numerous scientific applications of digital computers. Although multi-operand addition is trivially accomplished by accumulation (iteration in time) in any general purpose machine, demands for very high-speed computation, typified by 2- and 3-D signal processing prompt implementation of dedicated, hardware-intensive structures for multi-operand addition. This study, for example, is motivated in part by requirements for rapid simultaneous addition of up to 100, 16-bit operands in the design of a dedicated processor for real-time reconstruction of 3-D images of the beating heart and breathing lungs [1].