Boots – shoes – and leggings
Patent
1993-07-16
1995-09-19
Beausoliel, Jr., Robert W.
Boots, shoes, and leggings
39518401, 395460, 395500, 364285, 3642241, G06F 1134
Patent
active
054524407
ABSTRACT:
Method and structure for collecting statistics for quantifying locality of data and thus selecting elements to be cached, and then calculating the overall cache hit rate as a function of cached elements. LRU stack distance has a straight-forward probabilistic interpretation and is part of statistics to quantify locality of data for each element considered for caching. Request rates for additional slots in the LRU are a function of file request rate and LRU size. Cache hit rate is a function of locality of data and the relative request rates for data sets. Specific locality parameters for each data set and arrival rate of requests for data-sets are used to produce an analytical model for calculating cache hit rate for combinations of data sets and LRU sizes. This invention provides algorithms that can be directly implemented in software for constructing a precise model that can be used to predict cache hit rates for a cache, using statistics accumulated for each element independently. The model can rank the elements to find the best candidates for caching. Instead of considering the cache as a whole, the average arrival rates and re-reference statistics for each element are estimated, and then used to consider various combinations of elements and cache sizes in predicting the cache hit rate. Cache hit rate is directly calculated using the to-be-cached files' arrival rates and re-reference statistics and used to rank the elements to find the set that produces the optimal cache hit rate.
REFERENCES:
patent: 4490782 (1984-12-01), Dixon et al.
patent: 4669043 (1987-05-01), Kaplinsky
patent: 4835686 (1989-05-01), Furuya et al.
patent: 4920478 (1990-04-01), Furuya et al.
patent: 5043885 (1991-08-01), Robinson
patent: 5133060 (1992-07-01), Weber et al.
patent: 5241640 (1993-08-01), Hisano et al.
patent: 5325504 (1994-06-01), Tipley et al.
patent: 5325509 (1994-06-01), Lautzenheiser
patent: 5335317 (1994-08-01), Hisano et al.
patent: 5353430 (1994-10-01), Lautzenheiser
patent: 5359713 (1994-10-01), Moran et al.
Performance Analysis of Buffer Coherency Policies in a Multisystem Data Sharing Environment, Asit Dan, pp. 289-305, IEEE Mar. 1993.
Improving Disk Cache Hit-Ratios Through Cache Partitioning, Dominique Thiebaut, pp. 665-676, IEEE vol. 41, No. 6 Jun. 1992.
"An Analytical Cache Model," ACM Transactions on Computer Systems, vol. 7, No. 2, May 1989, pp. 184-215, Agarwal et al.
"A File-Based Adaptive Prefetch Caching Design," Shih et al., IBM T. J. Watson Research Center, 1990 IEEE.
"Method for Predicting the Performance of Set-Associative Cache Memories," 700 IBM Technical Disclosure Bulleting 31 (1989) Jan., No. 8, Armont, N.Y., U.S.
"Optimal Partioning of Cache Memory," Harold S. Stone, IEEE Transactions of Computers., vol. 41, No. 9, Sep. 1992.
"A Multiple Workload Approach to Cache Planning,", McNutt et al., pp. 9-15.
An Analytical Cache Model, Aragwal et al., Abstract, Apr. 25, 1988 Computer Systems Lab., Stanford University, Stanford, Calif. 94305.
A Measure of Program Locality and Its Application, Bunt et al., Abstract, Dept. of Computational Science, University of Saskatchewan 1984.
An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes, Dan et al., Abstract, University of Massachusetts, Amherst, Mass.
MVS Memory Management, Friedman, Abstract, Landmark Systems Corp. Vienna, Va.
Locality-Based Approach to Characterize Data Set Referencing Patterns.
Measurement and Analysis of Locality Phases in File Referencing Behaviour Majumdar et al, Abstract, Dept. of Computational Science, Saskatchewan University.
A Multiple Workload Approach to Ache Planning, McNutt et al., Abstract, International Business Machines, Corporation, San Jose, Calif.
A Simple Statistical Model of Cache Reference Locality and Its Application to Cache Planning, Measurement and . . . , McNutt, IBM, San Jose, Calif., pp. 203, 1991.
Workload Characterization for Storage Modeling, Olcott, Abstract, Schering-Plough Corporation, Memphis, Tenn. pp. 705-716, 1991.
Disk Cache-Miss Ratio Analysis and Design Considerations, A. J. Smith, University of California, Berkeley, ACM Trans. on Com. Sys., vol. 3, No. 3, Aug.
Empirical Results on Locality in Database Referencing, Verkamo, Dept. of Computer Science, University of Helsinki, 1985, ACM.
Beausoliel, Jr. Robert W.
Caserza S.
Le Dieu-Minh
Zitel Corporation
LandOfFree
Method and structure for evaluating and enhancing the performanc does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and structure for evaluating and enhancing the performanc, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and structure for evaluating and enhancing the performanc will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1835629