Due to the rapid growth of processor speeds and the expansion of the application base, multi-level cache hierarchies are becoming more important for microprocessor systems. One classical technique in designing multi-level caches is the subset-rule, with which the cache contents at one level of a hierarchy are maintained as a subset of the next level of the hierarchy. A major benefit of the subset-rule is its conceptual simplicity for cache coherence control. However, in certain systems, conventional subset management may result in higher hardware costs or in unexpected performance losses. In this paper, we investigate these aspects through simulations for a multiprocessor environment. Several alternatives to the conventional subset approach are proposed and evaluated. We also examine some new techniques for managing coherence information at lower costs when very large caches are involved.>

One critical aspect in designing set-associative cache at high clock rate is deriving timely results from directory lookup. In this paper we investigate the possibility of accurately approximating the results of conventional directory search with faster matches of few partial address bits. Such fast and accurate approximations may be utilized to optimize cache access timing, particularly in a customized design environment. Through analytic and simulation studies we examine the trade-offs of various design choices. We also discuss few other applications of partial address matching to computer designs.

In most high performance computers the speeds of cache accessing are critical in determining the cycle times. A classical method for designing set-associative caches is to late-select array data based on the results of cache directory lookups. The impact on the critical path timing due to late-select will become more significant in future microprocessors with very high clock frequencies. In this paper we propose a new approach to the optimization of array access timing for set-associative caches. The basic idea is to utilize a relatively small partial address directory (PAD) for fast and accurate approximations of cache access coordinates. The PAD can speed up most cache array access by accurately predicting cache locations without having to wait for results from conventional cache directory lookups. Occasionally when the PAD guesses wrong, a memory access can be re-issued with only 1-cycle delays. The PAD may be closely integrated with the array design. The effectiveness of the PAD method is analyzed through combinatorial and simulation studies.>

Traditional approaches for increasing TLB hit ratios include using more TLB entries and/or bigger page sizes. These techniques are often subject to significant costs in implementations. We illustrate techniques for improving TLB efficiency with less expensive hardware. The basic idea is to allow multiple pages translated upon each invocation of translation through page table. The proposal can improve TLB hit ratios with reasonable amount of hardware while transparent to the software. Trade-offs in using multiple page translations are illustrated through simulation results.>

The authors propose design techniques that may significantly simplify the cache access path, and hence offer the opportunity of shorter cycle time or fewer pipeline stages. Their proposals are based on highly accurate prediction methods that allow them to efficiently resolve address translation information early in the pipe.>

An approach to workload sampling in which, instead of selection of memory references based on the time parameter, sample decisions are based on where the cache is accessed. More specifically, the sampling heuristics are focused on analysis for set-associative caches. The validity of the heuristics is supported with empirical data. Four sampling policies are discussed, and simulation results based on a commercial database transaction workload are presented. Observations from simulation studies with SPEC 1.0 uniprogram benchmarks are also described. An environment in which congruence class sampling may be useful is illustrated.>

Techniques for sampling of cache congruence classes are considered. A sampling policy that selects on the basis of where a reference hits the cache (physically) instead of when a reference arrives is examined. The notion of weighted misses is used to provide some meaningful interpretations of the miss ratios associated with workload partitioning.>

A formal model of multilevel security systems is presented. We examine weaknesses of current security flow analysis mechanisms. A concept of expression flows is introduced, which allows us to use various techniques to certify systems that cannot be certified using current flow analysis techniques. We provide a method for generating static authorization requirements for systems in which authorization functions are only partially specified. We also attack the problem of using dynamic authorization functions for system certification.

Traditional implementations of conditional critical regions and monitors can lead to unproductive "busy waiting" if processes are allowed to wait on arbitrary boolean expressions. Techniques from global flow analysis may be employed at compile time to obtain information about which critical regions (monitor calls) are enabled by the execution of a given critical region (monitor call). We investigate the complexity of computing this information and show how it can be used to obtain efficient scheduling algorithms with less busy waiting.