Boots – shoes – and leggings
Patent
1994-07-29
1997-05-06
Swann, Tod R.
Boots, shoes, and leggings
395446, 364DIG1, G06F 1202
Patent
active
056279949
ABSTRACT:
A method is provided for providing a cache architecture for a database system having a given number of request streams and a given number of pages of random access memory available for use in one or more caches. The cache architecture includes (i) an allocation of memory pages over a number of caches, and (ii) an assignment of the request streams to the caches. Given that the number of caches is less than the number of streams, the method according to the invention allocates memory pages to the caches and assigns streams to the caches so as to optimize the memory access hit ratio for a given trace of memory requests from the streams. The method includes obtaining characterization information for the request streams (mean burst sizes and cache depth distributions based on the sequence of requests in the trace), and using the characterization information to predict the hit ratios for proposed superpositions of the request streams. An efficient algorithm allows request streams to be superposed, a pair at a time, optimizing the hit ratio for each superposition based on the characterization information.
REFERENCES:
patent: 4468730 (1984-08-01), Dodd et al.
patent: 4536836 (1985-08-01), Dodd et al.
patent: 4835678 (1989-05-01), Kofuji
patent: 4888681 (1989-12-01), Barnes et al.
patent: 4928225 (1990-05-01), McCarthy et al.
patent: 4972314 (1990-11-01), Getzinger et al.
patent: 5029070 (1991-07-01), McCarthy et al.
patent: 5185871 (1993-02-01), Frey et al.
patent: 5228134 (1993-07-01), MacWilliams et al.
J. M. Rosenberg, Dictionary of Computers, Information Processing and Telecommunications 2nd ed., 1987, pp. 67 & 655. John Wiley & Sons.
S. Krakowiak [trans. D. Beeson] Principles of Operating Systems, MIT Press, 1987, pp. 211-214.
E. G. Coffman, Jr. and P. J. Denning, Operating Systems Theory, Prentice-Hall, Inc., 1973, pp. 275-278.
E. Gelenbe and I. Mitrani, Analysis and Synthesis of Computer Systems, Academic Press, 1980, pp. 9-13.
B. V. Gnedenko and I. N. Kovalenko, [trans. E. R. Kondor and D. Louvish] Introduction To Queueing Theory, Israel Program for Scientific Translations, Jerusalem, 1968, pp. 1-18.
P. G. Emma et al., Cache Miss Leading Edge Processing, IBM Tech. Disclosure Bulletin, vol. 32, No. 7, Dec. 1989.
R. D. Hoover et al., Processor Performance Enhancement Using a Memory Cache Scheme, IBM Tech. Disclosure Bulletin vol. 32, No. 6A Nov. 1989.
E. G. Coffman, Jr. et al., Operating System Theory, pp. 241-284, 1973, (book).
A. J. Smith, Cache Memories, Computing Surveys, vol. 14, No. 3, pp. 473-530.
J. Gecsei et al., Evaluation Techniques for Storage Hierarchies, Storage Hierarchy Evaluation, IBM Systems Journal, vol. 9, No. 2, pp. 78-117, 1970.
A. J. Smith, Bibliography and Readings on CPU Cache Memories and Related Topics, Computer Science Div., EECS Dept., Univ. of California Berkeley, CA, pp. 22-41.
I. J. Haikala, Cache Hit Ratios with Geometric Task Switch Intervals, IEEE, 0194-7111/84, pp. 364-371.
J. Z. Teng et al., Managing IBM Database 2 Buffers to Maximize Performance, IBM Sys. Journal, vol. 23, No. 2, 1984, pp. 211-219.
H. S. Stone, Optimal Partitioning of Cache Memory, IEEE Transactions on Computers, vol. 41, No. 9, Sep. 92, pp. 1054-1068.
Levy Hanoch
Morris Robert J. T.
International Business Machines - Corporation
Peikari J.
Pintner James C.
Swann Tod R.
LandOfFree
Method for the assignment of request streams to cache memories 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 for the assignment of request streams to cache memories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the assignment of request streams to cache memories will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2140007