Currently, the most popular file-sharing applications have used either centralized or flood-based search algorithms. Napster has been successful in providing a centralized index with presumably perfect query recall. Succeeding, more distributed protocols like Gnutella and Kazaa have used flood-based search procedures in which a query is propagated through an unstructured network. Query result quality in such networks suffers as queries for items that are rare have high probabilities of not being found as the entire corpus is not covered during a search. In this paper, we present a new and improved implementation of a distributed file-sharing system yielding (1) query result quality better than flooding and close to a centralized index, and (2) low-maintenance network overhead. These improvements result from our optimized approaches to (a) high churn rates (clients and servers frequently entering and leaving the system) and (b) skewed workloads (high variation in access frequencies vs. key). High churn rates are addressed by keeping all data in soft state, which is periodically refreshed, such that the loss of a server or client is quickly reflected in the indexes; higher refresh rates imply fewer false positives. Skewed workloads are load balanced with the use of a layer of indirection for placing and locating data, such that data is partitioned and distributed based on the frequency of use. A trace-driven prototype evaluation based on Gnutella system traces shows that our prototype implementation achieves a low network bandwidth, attains max-average load ratios within a factor of three across all servers, and has positive recall values for over 90% of all queries, despite a high churn rate; the recall would be 100% absent churn.

Disk I/O is increasingly the performance bottleneck in computer systems despite rapidly increasing disk data transfer rates. In this article, we propose Automatic Locality-Improving Storage (ALIS), an introspective storage system that automatically reorganizes selected disk blocks based on the dynamic reference stream to increase effective storage performance. ALIS is based on the observations that sequential data fetch is far more efficient than random access, that improving seek distances produces only marginal performance improvements, and that the increasingly powerful processors and large memories in storage systems have ample capacity to reorganize the data layout and redirect the accesses so as to take advantage of rapid sequential data transfer. Using trace-driven simulation with a large set of real workloads, we demonstrate that ALIS considerably outperforms prior techniques, improving the average read performance by up to 50% for server workloads and by about 15% for personal computer workloads. We also show that the performance improvement persists as disk technology evolves. Since disk performance in practice is increasing by only about 8% per year, the benefit of ALIS may correspond to as much as several years of technological progress.

By dynamically varying CPU speed and voltage, it is possible to save significant amounts of energy while still meeting prespecified soft or hard deadlines for tasks; numerous algorithms have been published with this goal. We show that it is possible to modify any voltage scaling algorithm to minimize energy use without affecting perceived performance and present a formula to do so optimally. Because this formula specifies increased speed as the task progresses, we call this approach PACE (Processor Acceleration to Conserve Energy). This optimal formula depends on the probability distribution of the task's work requirement and requires that the speed be varied continuously. We therefore present methods for estimating the task work distribution and evaluate how effective they are on a variety of real workloads. We also show how to approximate the optimal continuous schedule with one that changes speed a limited number of times. Using these methods, we find we can apply PACE practically and efficiently. Furthermore, PACE is extremely effective. Simulations using real workloads and the standard model for energy consumption as a function of voltage show that PACE can reduce the CPU energy consumption of existing algorithms by up to 49.5 percent, with an average of 20.6 percent, without any effect on perceived performance. The consequent PACE-modified algorithms reduce CPU energy consumption by an average of 65.4 percent relative to no dynamic voltage scaling, as opposed to only 54.3 percent without PACE.

Article Share on Operating System Modifications for Task-Based Speed and Voltage Authors: Jacob R. Lorch View Profile , Alan Jay Smith View Profile Authors Info & Claims MobiSys '03: Proceedings of the 1st international conference on Mobile systems, applications and servicesMay 2003 Pages 215–229https://doi.org/10.1145/1066116.1189044Published:05 May 2003Publication History 32citation233DownloadsMetricsTotal Citations32Total Downloads233Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Many microprocessor instruction sets include instructions for accelerating multimedia applications such as DVD playback, speech recognition, and 3D graphics. Despite general agreement on the need to support this emerging workload, there are considerable differences between the instruction sets that have been designed to do so. In this paper, we study the performance of five instruction sets on kernels extracted from a broad multimedia workload. We compare the performance of contemporary implementations of each extension against each other as well as to the original compiled C performance. From our analysis, we determine how well multimedia workloads map to current instruction sets, noting what was useful and what was not. We also propose two enhancements: fat subwords and strided memory operations.

The caching behavior of multimedia applications has been described as having high instruction reference locality within small loops, very large working sets, and poor data cache performance due to non-locality of data references. Despite this, there is no published research deriving or measuring these qualities. Utilizing the previously developed Berkeley Multimedia Workload, we present the results of execution driven cache simulations with the goal of aiding future media processing architecture design. Our analysis examines the differences between multimedia and traditional applications in cache behavior. We find that multimedia applications actually exhibit lower instruction miss ratios and comparable data miss ratios when contrasted with other widely studied workloads. In addition, we find that longer data cache line sizes than are currently used would benefit multimedia processing.

As improvements in processor performance continue to far outpace improvements in storage performance, I/O is increasingly the bottleneck in computer systems, especially in large database systems that manage huge amoungs of data. The key to achieving good I/O performance is to thoroughly understand its characteristics. In this article we present a comprehensive analysis of the logical I/O reference behavior of the peak productiondatabase workloads from ten of the world's largest corporations. In particular, we focus on how these workloads respond to different techniques for caching, prefetching, and write buffering. Our findings include several broadly applicable rules of thumb that describe how effective the various I/O optimization techniques are for the production workloads. For instance, our results indicate that the buffer pool miss ratio tends to be related to the ratio of buffer pool size to data size by an inverse square root rule. A similar fourth root rule relates the write miss ratio and the ration of buffer pool size to data size. In addition, we characterize the reference characteristics of workloads similar to the Transaction Processing Performance Council (TPC) benchmarks C (TPC-C) and D(TPC-D), which are de facto standard performance measures for online transaction processing (OLTP) systems and decision support systems (DSS), respectively. Since benchmarks such as TPC-C and TPC-D can only be used effectively if their strengths and limitations are understood, a major focus of our analysis is to identify aspects of the benchmarks that stress the system differently than the production workloads. We discover that for the most part, the reference behavior of TPC-C and TPC-D fall within the range of behavior exhibited by the production workloads. However, there are some noteworthy exceptions that affect well-known I/O optimization techniques such as caching (LRU is further from the optimal for TPC-C, while there is little sharing of pages between transactions for TPC-D), prefetching (TPC-C exhibits no significant sequentiality), and write buffering (write buffering is lees effective for the TPC benchmarks). While the two TPC benchmarks generally complement one another in reflecting the characteristics of the production workloads, there remain aspects of the real workloads that are not represented by either of the benchmarks.

Shared bus computer systems permit the relatively simple and efficient implementation of cache consistency algorithms, but the shared bus is a bottleneck which limits performance. False sharing can be an important source of unnecessary traffic for invalidation-based protocols, elimination of which can provide significant performance improvements. For many multiprocessor workloads, however, most misses are true sharing plus cold start misses. Regardless of the cause of cache misses, the largest fraction of bus traffic are words transferred between caches without being accessed, which we refer to as dead sharing. We establish here new methods for characterizing cache block reference patterns, and we measure how these patterns change with variation in workload and block size. Our results show that 42 percent of 64-byte cache blocks are invalidated before more than one word has been read from the block and that 58 percent of blocks that have been modified only have a single word modified before an invalidation to the block occurs. Approximately 50 percent of blocks written and subsequently read by other caches show no use of the newly written information before the block is again invalidated. In addition to our general analysis of reference patterns, we also present a detailed analysis of dead sharing for each shared memory multiprocessor program studied. We find that the worst 10 blocks (based on most total misses) from each of our traces contribute almost 50 percent of the false shearing misses and almost 20 percent of the true sharing misses (on average). A relatively simple restructuring of four of our workloads based on analysis of these 10 worst blocks leads to a 21 percent reduction in overall misses and a 15 percent reduction in execution time. Permitting the block size to vary (as could be accomplished with a sector cache) shows that bus traffic can be reduced by 88 percent (for 64-byte blocks) while also decreasing the miss ratio by 35 percent.

Recent developments in both hardware and software have made it worthwhile to consider embedding intelligence in storage to handle general-purpose processing that can be off-loaded from the hosts. In particular, low-cost processing power is now widely available and software can be made robust, secure and mobile. In this paper, we propose a general smart storage (SmartSTOR) architecture in which a processing unit that is coupled to one or more disks can be used to perform such off-loaded processing. A major part of the paper is devoted to understanding the performance potential of the SmartSTOR architecture for decision support workloads. Our analysis suggests that there is a definite performance advantage in using fewer but more powerful processors, a result that bolsters the case for sharing a powerful processor among multiple disks. As for software architecture, we find that the off-loading of database operations that involve only a single relation is not very promising. In order to achieve significant speed-up, we have to consider the off-loading of multiple-relation operations. In general, if embedding intelligence in storage is an inevitable architectural trend, we have to focus on developing parallel software systems that can effectively take advantage of the large number of processing units that will be in the system.

The first commercially available CPU cache memory used a sector design, by which the cache consisted of sectors (address tags) and subsectors (or blocks, with valid bits). It rapidly became clear that superior performance could be obtained with the now familiar set-associative cache design. Because of changes in technology, the time has come to revisit the design of sector caches. Sector caches have the feature that large numbers of bytes can be controlled using relatively small numbers of tag bits, while not having to transfer very large blocks. This suggests the use of sector caches for multi-level cache designs. In such a design, the cache tags can be placed at a high level (e.g., on the processor chip) and the cache data array can be placed at a lower level (e.g., off-chip). We present a thorough analysis of the design and use of uniprocessor sector caches. We start by creating a standard workload and then through simulation derive miss ratios for a wide range of sector cache designs. Those miss ratios are transformed into design target miss ratios, which are intended to be representative of a wide range of workloads. The miss ratios are then used to estimate performance, using typical timings, for a variety of one-level and true-level cache designs.

Sector caches use an address tag to identify a sector, and valid bits to indicate whether each subsector is present in the cache.This design permits a small number of tag bits to control a large number of data bytes in the cache.Such a design is useful for single level caches when cache sizes are small and/or when the optimal line sizes are small.Sector caches are most useful when small firstlevel tag arrays are used to control large second level cache data arrays.The problem with sector caches is that because of the constrained mapping between address tags and data array space, frequently many of the subsectors are not filled before the sector is replaced.In this paper, we propose a new design, called the sector pool cache, in which subsectors may be shared between sectors, so that the cache data arrays are used much more efficiently.We evaluate this design using a large multiprogrammed workload to provide a more realistic test of the various cache designs.Our results show that the sector pool cache can be an attractive solution for a first level on-chip cache when used in conjunction with a regular second level off-chip sector cache.Such a design provides improved performance by more efficiently utilizing the first-level cache bits.

Presents Cerberus, an efficient system for simulating the execution of shared-memory, multiprocessor programs on a uniprocessor workstation. Using EDS (execution-driven simulation), it generates address traces which can be used to drive cache simulations on-the-fly, eliminating the large disk space requirements needed by trace files. It is fast because it links the program to be traced together with the cache or statistics gathering tool into a single executable, which eliminates the context switching needed by communicating processes. It is flexible because it has a simple interface which allows users to easily add any kind of module to use the generated trace information. It compares favorably to other existing tracers; it runs on a commonly available workstation and it is accurate, allowing cycle-by-cycle interactions between the simulated processors. The resulting slowdown from Cerberus is approximately 31 in uniprocessor mode and 45-50 in multiprocessor mode, relative to the workloads run natively on the same machines. We demonstrate that EDS uses only 5% of the total execution cycles when combined with a cache simulator, and we show that EDS is just as efficient as using trace-driven simulation.

Most published research on system behavior and workload characterization has been based on either Unix systems or large (usually IBM) mainframe systems. It is reasonable to believe that user behaviors and workloads are different for PC systems. Further, the aspects of system design and most-needed study have changed from the mainframes that were dominant in the 1960s and 1970s, and the Unix systems that became so popular in the 1980s, to the PCs that seem to be rapidly taking over many or most aspects of computing. Our analysis focuses instead on Microsoft Windows 95, which is currently the most widely used computer operating system; the newly released Windows 98 is very similar. In this paper, we describe a workload analysis based on 36 sets of traces collected from Intel Pentium-based PCs running the Windows 95 operating system. Following the discussion of our Windows 95 trace data, we present some descriptive and statistical characterizations of this data, directed principally at user behavior and file system behavior.

As the performance gap between processors and main memory continues to widen, increasingly aggressive implementations of cache memories are needed to bridge the gap. In this paper, we consider some of the issues that are involved in the implementation of highly optimized cache memories and survey the techniques that can be used to help achieve the increasingly stringent design targets and constraints of modern processors. In particular, we consider techniques that enable the cache to be accessed quickly and still achieve a good hit ratio. We also consider issues such as area cost and bandwidth requirements. Trace-driven simulations of a TPC-C-like workload and selected applications from the SPEC95 benchmark suite are used in the paper to compare the performance of some of the techniques.

Prefetching into CPU caches has long been known to be effective in reducing the cache miss ratio, but known implementations of prefetching have been unsuccessful in improving CPU performance. The reasons for this are that prefetches interfere with normal cache operations by making cache address and data ports busy, the memory bus busy, the memory banks busy, and by not necessarily being complete by the time that the prefetched data is actually referenced. In this paper, we present extensive quantitative results of a detailed cycle-by-cycle trace-driven simulation of a uniprocessor memory system in which we vary most of the relevant parameters in order to determine when and if hardware prefetching is useful. We find that, in order for prefetching to actually improve performance, the address array needs to be double ported and the data array needs to either be double ported or fully buffered. It is also very helpful for the bus to be very wide (e.g., 16 bytes) for bus transactions to be split and for main memory to be interleaved. Under the best circumstances, i.e., with a significant investment in extra hardware, prefetching can significantly improve performance. For implementations without adequate hardware, prefetching often decreases performance.

We present the results of a variety of trace-driven simulations of disk cache designs using traces from a variety of mainframe timesharing and database systems in production use. We compute miss ratios, run lengths, traffic ratios, cache residency times, degree of memory pollution and other statistics for a variety of designs, varying lock size, prefetching algorithm and write algorithm. We find that for this workload, sequential prefetching produces a significant (about 20%) but still limited improvement in the miss ratio, even using a powerful technique for detecting sequentiality. Copy-back writing decreased write traffic relative to write-through by more than 50%; periodic flushing of the dirty blocks increased write traffic only slightly compared to pure write-back, and then only for large cache sizes. Write-allocate had little effect compared to no-write-allocate. Block sizes of over a track don't appear to be useful. Limiting cache occupancy by a single process or transaction appears to have little effect. This study is unique in the variety and quality of the data used in the studies.

The CPU is one of the major power consumers in a portable computer, and considerable power can be saved by turning off the CPU when it is not doing useful work.In Apple's MacOS, however, idle time is often converted to busy waiting, and generally it is very hard to tell when no useful computation is occurring.In this paper, we suggest several heuristic techniques for identifying this condition, and for temporarily putting the CPU in a low-power state.These techniques include turning off the processor when all processes are blocked, turning off the processor when processes appear to be busy waiting, and extending real time process sleep periods.We use trace-driven simulation, using processor run interval traces, to evaluate the potential energy savings and performance impact.We find that these techniques save considerable amounts of processor energy (as much as 66% ), while having very little performance impact (less than 2% increase in run time).Implementing the proposed strategies should increase battery lifetime by approximately 20% relative to Apple's current CPU power management strategy, since the CPU and associated logic are responsible for about 32% of power use; similar techniques should be applicable to operating systems with similar behavior.

Standard benchmarking provides to run-times for given programs on given machines, but fails to provide insight as to why those results were obtained (either in terms of machine or program characteristics) and fails to provide run-times for that program on some other machine, or some other programs on that machine. We have developed a machine-imdependent model of program execution to characterize both machine performance and program execution. By merging these machine and program characterizations, we can estimate execution time for arbitrary machine/program combinations. Our technique allows us to identify those operations, either on the machine or in the programs, which dominate the benchmark results. This information helps designers in improving the performance of future machines and users in tuning their applications to better utilize the performance of existing machines. Here we apply our methodology to characterize benchmarks and predict their execution times. We present extensive run-time statistics for a large set of benchmarks including the SPEC and Perfect Club suites. We show how these statistics can be used to identify important shortcoming in the programs. In addition, we give execution time estimates for a large sample of programs and machines and compare these against benchmark results. Finally, we develop a metric for program similarity that makes it possible to classify benchmarks with respect to a large set of characteristics.

In previous research, we have developed and presented a model for measuring machines and analyzing programs, and for accurately predicting the running time of any analyzed program on any measured machine. That work is extended here by: (1) developing a high level program to measure the design and performance of the cache and TLB units; (2) using those measurements, along with published miss ratio data, to improve the accuracy of our runtime predictions; (3) using our analysis tools and measurements to study and compare the design of several machines, with particular reference to their cache and TLB performance. As part of this work, we describe the design and performance of the cache and TLB for ten machines. The work presented, in this paper extends a powerful technique for the evaluation and analysis of both computer systems and their workloads; this methodology is valuable both to computer users and computer system designers.>

Optimizing compilers have become an essential component in achieving high levels of performance. Various simple and sophisticated optimizations are implemented at different stages of compilation to yield significant improvements, but little work has been done in characterizing the effectiveness of optimizers, or in understanding where most of this improvement comes from. We study the performance impact of optimization in the context of our methodology for CPU performance characterization based on the abstract machine model. The model considers all machines to be different implementations of the same high level language abstract machine; in previous research, the model has been used as a basis to analyze machine and benchmark performance. We show that our model can be extended to characterize the performance improvement provided by optimizers and to predict the run time of optimized programs, and measure the effectiveness of several compilers in implementing different optimization techniques.>

There are three general techniques for studying the design, operation and optimization of any type of system: implementation, modeling, and simulation. Implementation can be used when the time is available and the effort is justified. Mathematical modeling can be used if the system is simple enough or if gross approximations are acceptable. Simulation is needed for the remaining cases. In all three cases, a crucial element is the need for accurate estimates of the "workload." For example, for a computer main or cache memory system, the workload may at one level of detail be the timing and sequence of memory addresses referenced; at another level of detail, it could be just the ratio of loads to stores. No matter how accurate the model of a system may be, any results from it are useless if the workload is not accurately represented. We discuss various types of models and when and what type of accurate workload data is needed. We pay particular attention to performance analysis of memory hierarchies and the use of trace driven simulation.>

The performance of shared-memory, cache-coherent multiprocessors is a strong function of the reference behavior within multiprocessor applications. This research characterizes the memory reference behavior in a wide variety of scalar and vector multiprocessor traces, to estimate and improve the performance of cache-consistency protocols. We find wide differences between the sharing behavior observed in vector and scalar applications. Compared to scalar programs, vector programs reference shared data more frequently and contain larger amounts of processor locality. Write sharing by different processors over short time intervals are infrequent in one workload but frequent in another. The latter result implies that sequentially-consistent programming models will remain necessary unless applications are recoded to avoid such reference patterns.>

Vector processors have typically used vector registers, interleaved memory, and pipelined access to data to provide sufficient memory system performance. Caches have been used mainly for instructions and scalar data, while vectors are usually uncached, presumably partially because of the belief that there is insufficient vector locality in these workloads. In this study we use memory address traces from an Ardent Titan to examine both reference locality and cache performance in a vector processing environment. Many of the Titan traces are from real vectorized applications which reference large amounts of data. We have found that vector references contain somewhat less temporal locality, but large amounts of spatial locality compared to instruction and scalar references. Cache miss ratios are found to be comparable to those measured and published previously for various non-vectorized workloads. We provide analyses of trace behavior with regard to parameters of interest to cache designers. Calculations based on our measured miss ratios indicate that caches will improve average access times, which in turn can be expected to translate into significant improvements in machine performance. Arguments suggesting otherwise are discussed and considered.

A branch target buffer (BTB) can reduce the performance penalty of branches in pipelined processors by predicting the path of the branch and caching information used by the branch. Two major issues in the design of BTBs that achieves maximum performance with a limited number of bits allocated to the BTB implementation are discussed. The first is BTB management. A method for discarding branches from the BTB is examined. This method discards the branch with the smallest expected value for improving performance; it outperforms the least recently used (LRU) strategy by a small margin, at the cost of additional complexity. The second issue is the question of what information to store in the BTB. A BTB entry can consist of one or more of the following: branch tag, prediction information, the branch target address, and instructions at the branch target. Various BTB designs, with one or more of these fields, are evaluated and compared.>

Abstract In performance analysis of computer systems, trace‐driven simulation techniques have the important advantage of credibility and accuracy. Unfortunately, traces are usually difficult to obtain, and little work has been done to provide efficient tools to help in the process of reducing and manipulating them. This paper presents TRAMP, a tool for the data reduction and data analysis phases of trace‐driven simulation studies. TRAMP has three main advantages: it accepts a variety of common trace formats; it provides a programmable user interface in which many actions can be directly specified; and it is easy to extend. TRAMP is particularly helpful for reducing and analysing complex trace data, such as traces of file system or database activity. This paper presents the design principles and implementation techniques of TRAMP and provides a few concrete examples of the use of this tool.

The authors present new and efficient algorithms for simulating alternative direct-mapped and set-associative caches and use them to quantify the effect of limited associativity on the cache miss ratio. They introduce an algorithm, forest simulation, for simulating alternative direct-mapped caches and generalize one, which they call all-associativity simulation, for simulating alternative direct-mapped, set-associative, and fully-associative caches. The authors find that although all-associativity simulation is theoretically less efficient than forest simulation or stack simulation (a commonly used simulation algorithm), in practice it is not much slower and allows the simulation of many more caches with a single pass through an address trace. The authors also provide data and insight into how varying associatively affects the miss ratio.>

Measurements are presented for a large number of machines ranging from small workstations to supercomputers. The authors combine these measurements into groups of parameters which relate to specific aspects of the machine implementation, and use these groups to provide overall machine characterizations. The authors also define the concept of pershapes, which represent the level of performance of a machine for different types of computation. A metric based on pershapes is introduced that provides a quantitative way of measuring how similar two machines are in terms of their performance distributions. The metric is related to the extent to which pairs of machines have varying relative performance levels depending on which benchmark is used.>

For the class of replacement algorithms known as stack algorithms, existing analysis techniques permit the computation of memory miss ratios for all memory sizes simultaneously in one pass over a memory reference string. We extend the class of computations possible by this methodology in two ways. First, we show how to compute the effects of copy-backs in write-back caches. The key observation here is that a given block is clean for all memory sizes less than or equal to C blocks and is dirty for all larger memory sizes. Our technique permits efficient computations for algorithms or systems using periodic write-back and/or block deletion. The second extension permits stack analysis simulation for sector (or subblock) caches in which a sector (associated with an address tag) consists of subsectors (or subblocks) that can be loaded independently. The key observation here is that a subsector is present only in caches of size C or greater. Load forward prefetching in a sector cache is shown to be a stack algorithm and is easily simulated using our technique. Running times for our methods are only slightly higher than for a simulation of a single memory size using nonstack techniques.

The line (block) size of a cache memory is one of the parameters that most strongly affects cache performance. In this paper, we study the factors that relate to the selection of a cache line size. Our primary focus is on the cache miss ratio, but we also consider influences such as logic complexity, address tags, line crossers, I/O overruns, etc. The behavior of the cache miss ratio as a function of line size is examined carefully through the use of trace driven simulation, using 27 traces from five different machine architectures. The change in cache miss ratio as the line size varies is found to be relatively stable across workloads, and tables of this function are presented for instruction caches, data caches, and unified caches. An empirical mathematical fit is obtained. This function is used to extend previously published design target miss ratios to cover line sizes from 4 to 128 bytes and cache sizes from 32 bytes to 32K bytes; design target miss ratios are to be used to guide new machine designs. Mean delays per memory reference and memory (bus) traffic rates are computed as a function of line and cache size, and memory access time parameters. We find that for high performance microprocessor designs, line sizes in the range 16-64 bytes seem best; shorter line sizes yield high delays due to memory latency, although they reduce memory traffic somewhat. Longer line sizes are suitable for mainframes because of the higher bandwidth to main memory.

Standardization of a high performance blackplane bus, so that it can accommodate boards developed by different vendors, implies the need for a standardized cache consistency protocol. In this paper we define a class of compatible consistency protocols supported by the current IEEE Futurebus design. We refer to this class as the MOESI class of protocols; the term “MOESI” is derived from the names of the states. This class of protocols has the property that any system component can select (dynamically) any action permitted by any protocol in the class, and be assured that consistency is maintained throughout the system. Included in this class are actions suitable for copyback caches, write through caches and non-caching processors. We show that the Berkeley protocol and the Dragon protocol fall within this class, and can be extended to be compatible with other members of the class. The Illinois, Firefly and Write-Once protocols can be adapted to be compatible with this class; the facilities of he Futurebus currently do not support those protocols without adaptation. We discuss very briefly performance choices among protocols, and also other issues relating to a standard bus consistency protocol.

The selection of the "best" parameters for a cache design, such as size, mapping algorithm, fetch algorithm, line size, etc., is dependent on the expected workload.Similarly, the machine performance is sensitive to the cache performance which itself depends on the workload.Most cache designers have been greatly handicapped in their designs by the lack of realistic cache performance estimates.Published research generally presents data which is unrealistic in some respects, and available traces are often not representative.In this paper, we present measurements from a very wide variety of traces: there are 49 traces, taken from G machine architectures, (370, 360, VAX, MG8000, Z8000, CDC 6400), coded in 7 source languages.Statistics are shown for miss ratios, the effectiveness of prefetching in terms of both miss ratio and its effect on bus traffic, the frequency of writes, reads and instruction fetches, and the frequency of branches.Some general observations are made and a "design estimate" set of miss ratios are proposed.Some "fudge" factors are proposed by which statistics for workloads for one machine architecture can be used to estimate corresponding parameters for another (as yet unrealized) architecture.

The current trend of computer system technology is toward CPUs with rapidly increasing processing power and toward disk drives of rapidly increasing density, but with disk performance increasing very slowly if at all. The implication of these trends is that at some point the processing power of computer systems will be limited by the throughput of the input/output (I/O) system. A solution to this problem, which is described and evaluated in this paper, is disk cache . The idea is to buffer recently used portions of the disk address space in electronic storage. Empirically, it is shown that a large (e.g., 80-90 percent) fraction of all I/O requests are captured by a cache of an 8-Mbyte order-of-magnitude size for our workload sample. This paper considers a number of design parameters for such a cache (called cache disk or disk cache), including those that can be examined experimentally (cache location, cache size, migration algorithms, block sizes, etc.) and others (access time, bandwidth, multipathing, technology, consistency, error recovery, etc.) for which we have no relevant data or experiments. Consideration is given to both caches located in the I/O system, as with the storage controller, and those located in the CPU main memory. Experimental results are based on extensive trace-driven simulations using traces taken from three large IBM or IBM-compatible mainframe data processing installations. We find that disk cache is a powerful means of extending the performance limits of high-end computer systems.

It has been suggested that the algorithm used to schedule those processes active and in main memory can have an effect on memory contention. We create models for memory contention in a system that uses global LRU replacement and either round robin or priority internal scheduling. Parameters to our model include the ratio of secondary storage to primary storage access times, thus allowing consideration of a variety of storage technologies. The round robin quantum size is included and is shown to have some effect. Our model uses LRU miss ratio curves and thus reflects actual program characteristics. Trace driven simulations are used to verify the accuracy of the models. We find that in most cases internal scheduling has only a small effect on page fault rates and CPU utilization. In certain cases, however priority scheduling is found to besignificant in relieving thrashing.

In most large computer installations files are moved between on-line disk and mass storage (tape, integrated mass storage device) either automatically by the system and/or at the direction of the user. In this paper we present and analyze long term file reference data in order to develop a basis for the construction of algorithms for file migration. Specifically, we examine the use of the on-line user (primarily text editor) data sets at the Stanford Linear Accelerator Center (SLAC) computer installation through the analysis of 13 months of file reference data. We find that most files are used very few times. Of those that are used sufficiently frequently that their reference patterns may be examined, we find that: 1) about a third show declining rates of reference during their lifetime, 2) of the remainder, very few (about 5 percent) show correlated interreference intervals, and 3) interreference intervals (in days) appear to be more skewed than would occur with the Bernoulli process. Thus, about two-thirds of all suffi1ciently active files appear to be referenced as a renewal process with a skewed interreference distribution. A large number of other file reference statistics (file lifetimes, interference distributions, moments, means, number of uses/ file, file sizes, file rates of reference, etc.) are computed and presented. Throughout, statistical tests are described and explained. The results of our analysis of file reference patterns are applied in a companion paper to the development and comparative evaluation of file migration algorithms.

Abstract We study memory contention during multiprogramming when programs are free to compete for page frames. A random walk between the possible partitions of memory over the set of active programs is used to model memory contention and calculate throughput. Our model of contention takes into account program characteristics by using miss ratio curves, and also considers memory size and page fetch latency. With the aid of numerous trace‐driven simulations, we are able to verify our model, finding good agreement both in the observed distribution of memory among competing programs and in CPU utilization. We find that for high ratios of secondary to primary memory access time and under conditions of high memory contention, small programs with compact working sets are able to run with far less than expected interference from larger, more diffuse programs. In the case of multiprogramming the same program several times, we find that observed partition distributions are not necessarily even and that higher than expected levels of CPU use are observed. Lower ratios of access time are found to yield different results; programs compete on a more even basis and partition memory relatively more evenly than with higher ratios.

The problem of multiple, nonidentical copies of the same data in computer systems with both local cache and shared main memory has led some manufacturers to use "write-through" updating for main memory despite some known efficiency advantages favoring "swap" updating We propose that write throughs to main memory be buffered, thus reducing the probability that the CPU will have to walt for a mare memory write operation to take place Statistics on the nonstatmnary point process of stores to memory lead to a model in which the sequence of stores is considered to be described by a Poisson process which proceeds at rate ~, for a fraction of the Ume 13, This type of process has been described as a regime process Values for X, and /3, are obtained by (least squares) fitting the distrnbutlon function for the number of stores per 100 memory cycles This model is a model for the effect of the storage process on write-through updating, but is not a model of the storage process itself The model is then used to estimate the frequency of blocking in a computer system using a finite queue to buffer write-through operations The predicted frequency of blocking is found to agree well with the actual frequency of blocking as determined by trace driven simulation Comparisons are made with swap updating.

A multiple channel controller (MCC) is a controller which switches a given number of channels among a larger number of input/output devices and permits simultaneous access to as many devices as there are channels available. A simple queuing model for multiple channel controllers is created, and an approximate solution for this model is generated. The approximate solution is found, using simulation, to be very close for those cases examined to the actual behavior of the model. Further simulations indicate that the approximate solution of the model appears to be robust with respect to changes in some of the assumptions used in making the approximation. Trace data taken from a real system are analyzed and they confirm the predicted utility of MCC's. The problem of optimal scheduling of MCC's is briefly discussed. Alternative system configurations are compared with the objective of minimizing queuing delays.

The memory hierarchy is usually the largest identifiable part of a computer system and making effective use of it is critical to the operation and use of the system. We consider the levels of such a memory hierarchy and describe the state of the art and likely directions for both research and development. Algorithmic and logical features of the hierarchy not directly associated with specific components are also discussed. Among the problems we believe to be the most significant are the following: (a) evaluate the effectiveness of gap filler technology as a level of storage between main memory and disk, and if it proves to be effective, determine how/where it should be used, (b) develop algorithms for the use of mass storage in a large comguter system and (c) determine how cache memories should be implemented in very large, fast multiprocessor systems.

Access patterns to input/output files are usually sequential and local; a small number of files are open for each job and the file is generally read or written sequentially. This implies that if files are allocated in contiguous disk storage, the disk arms will rarely be required to move. Disk seeks can be almost entirely eliminated by using multiple arms, whereby if there are several open files on a given spindle, there will be an arm for each. Even better results can be obtained by using electronic storage such as magnetic bubbles, CCD's or electron beam memories to buffer portions of the disk. Such buffers not only eliminate seek time but reduce rotational latency to negligible amounts and decrease transfer time. We study, using trace driven simulation, the effectiveness of both buffers and multiple arms. For the data used, our experiments show that a minimum total buffer capacity of 20 tracks is required in a buffered disk. Best hit ratio results are obtained with individual buffer sizes upwards of one quarter cylinder. Three cylinder size buffers give very high hit ratios, on the order of 96%, and this appears to be a good choice for buffer size and number. LRU buffer scheduling is found to work well; comparisons with optimal, look-ahead buffer scheduling are made. Some possible models for the frequency of seeks are briefly considered.

Sequentiality of access is an inherent characteristic of many database systems. We use this observation to develop an algorithm which selectively prefetches data blocks ahead of the point of reference. The number of blocks prefetched is chosen by using the empirical run length distribution and conditioning on the observed number of sequential block references immediately preceding reference to the current block. The optimal number of blocks to prefetch is estimated as a function of a number of “costs,” including the cost of accessing a block not resident in the buffer (a miss), the cost of fetching additional data blocks at fault times, and the cost of fetching blocks that are never referenced. We estimate this latter cost, described as memory pollution, in two ways. We consider the treatment (in the replacement algorithm) of prefetched blocks, whether they are treated as referenced or not, and find that it makes very little difference. Trace data taken from an operational IMS database system is analyzed and the results are presented. We show how to determine optimal block sizes. We find that anticipatory fetching of data can lead to significant improvements in system operation.

Set associative page mapping algorithms have become widespread for the operation of cache memories for reasons of cost and efficiency. We show how to calculate analytically the effectiveness of standard bit-selection set associative page mapping or random mapping relative to fully associative (unconstrained mapping) paging. For two miss ratio models, Saltzer's linear model and a mixed geometric model, we are able to obtain simple, closed-form expressions for the relative LRU fault rates. We also experiment with two (infeasible to implement) dynamic mapping algorithms, in which pages are assigned to sets either in an LRU or FIFO manner at fault times, and find that they often yield significantly lower miss ratios than static algorithms such as bit selection. Trace driven simulations are used to generate experimental results and to verify the accuracy of our calculations. We suggest that as electronically accessed third-level memories composed of electron-beam tubes, magnetic bubbles, or charge-coupled devices become available, algorithms currently used only for cache paging will be applied to main memory, for the same reasons of efficiency, implementation ease, and cost.

The high cost of analyzing long memory address traces has limited most researchers to short traces and analysis algorithms that are linear in the length of the trace. We suggest two methods that permit a trace to be shortened in length by one to two orders of magnitude (or more) for later further analysis. The Stack Deletion Method eliminates all references in the trace to the top k levels of the LRU stack. The Snapshot Method records the reference bits of the pages in the original tape at discrete intervals and uses these bits to generate a new trace. Extensive measurements are presented, from which we conclude that there is little or no loss in accuracy using reduced traces for many purposes for a wide range of memory sizes and degrees of reduction.

We express the future behavior of programs that may be described by two common program behavior models, the independent reference model and the LRU stack model, by a discrete time Markov chain. Using this Markov chain model, we are able to calculate the theoretical minimum number of page faults for a program representable by either of these models in either a fixed or variable size memory. The behavior of optimal look-ahead and optimal realizable demand paging algorithms are compared, and it is seen that look-ahead paging demonstrates an inherent advantage sufficient to account for the differences observed between currently implemented demand paging algorithms and theoretically optimal algorithms.

The working set paging algorithm is known to be highly efficient, yet has the disadvantage that during changes of locality large numbers of pages are accumulated in memory Unnecessarily. The author proposes a modification of the working set algorithm called the damped working set(DWS)algorithm which resists sudden expansion of working set size and exhibits far greater stability in the number of page frames-allocated to an active process. Program address traces are analyzed to determine the effectiveness of the DWS algorithm.