US5627994A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for the assignment of request streams to cache memories
Assignee: PINTNER JAMES C
•
Filing: 1994-07-29
•
Granted: 1997-05-06
•
Expires: 2014-07-29
Abstract
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.
Inventors
- 👤 Hanoch Levy
- 👤 Robert J. T. Morris
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 17:26
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/123; G06F12/0802; G06F12/0875; G06F12/0806
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
76 words
A computer-implemented method for assigning data request streams to various ones of a plurality of data caches, the method comprising the steps of: obtaining characterization information for the request streams; and determining an assignment of the request streams to the caches using the characterization information, such that a likelihood is optimized that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 2
Dependent Claim
76 words
A computer-implemented method for assigning data request streams to various ones of a plurality of data caches, the method comprising the steps of: obtaining characterization information for the request streams; and determining an assignment of the request streams to the caches using the characterization information, such that a likelihood is optimized that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 3
Dependent Claim
24 words
A method as recited in claim 1, wherein the step of obtaining characterization information includes processing a trace of requests from the request streams.
Claim 4
Dependent Claim
67 words
A method as recited in claim 2, wherein the step of processing includes: processing the requests of the trace successively; simulating trajectories of data pages requested by the requests in the trace, the trajectories including sequences of cache positions related to the successive processing of the requests of the trace; and calculating depth distributions from the requests for the respective request streams, based on the simulated trajectories.
Claim 5
Dependent Claim
41 words
A method as recited in claim 3, wherein the step of processing a trace includes obtaining burst information related to bursts of consecutive requests, within the trace, the consecutive requests within each given burst all coming from the same request stream.
Claim 6
Dependent Claim
202 words
A method as recited in claim 4, wherein the step of obtaining burst information includes: maintaining flags F a ,b, each flag having a value of TRUE if a page requested from a stream a (designated a type a request) was encountered more recently in the trace than any page requested from a stream b (designated a type b request), and FALSE otherwise; maintaining variables n a , each variable counting the number of type a requests encountered among the requests of the trace thus far processed; maintaining variables B a ,b each variable counting the number of bursts of consecutive type a requests of the trace, assuming that all requests other than type a or type b requests in the trace are deleted; and for each successive type t request of the trace, updating the flags F a ,b, the variables n a , and the variables B a ,b by (a) incrementing the variable n t , (b) for all types s other than t, testing the state of the flag F s ,t, and (c) if the state is FALSE, then (i) setting F s ,t =TRUE, (ii) setting F t ,s =FALSE, and (iii) incrementing B t ,s.
Claim 7
Dependent Claim
57 words
A method as recited in claim 5, wherein the step of obtaining burst information further includes, following execution of the steps of maintaining flags F a ,b, maintaining a vector of variables n a , maintaining variables B a ,b, and updating, the step of: computing mean burst lengths M a ,b according to the formula ##EQU24##
Claim 8
Dependent Claim
61 words
A method as recited in claim 4, wherein the step of determining an assignment includes: making an initial fully split assignment of a predetermined number of data pages to a number of caches equal to the number of request streams; and superposing pairs of request streams, thereby making an assignment in which superposed request streams are assigned to a single cache.
Claim 9
Dependent Claim
107 words
A method as recited in claim 7 wherein the step of making an initial fully split assignment includes: (a) calculating an optimal allocation of a subset k of the buffers to a number 1 of caches less than the number of streams; (b) calculating an optimal allocation, where the number of caches is increased by one, as the allocation having the lowest miss ratio of any allocation in which the k buffers remain allocated to the I caches and all of the remaining buffers are allocated to the one additional cache; and (c) repeating step (b) until the number of caches equals the number of request streams.
Claim 10
Dependent Claim
68 words
A method as recited in claim 7, wherein the step of superposing includes: computing respective superposition reference depth distributions for respective superpositions of the request streams, based on reference depth distributions for the request streams in isolation and on burst rates of the request streams; and comparing the respective superposition reference depth distributions to identify a superposition of request streams which produces an optimum improvement in hit ratio.
Claim 11
Dependent Claim
58 words
A method as recited in claim 9, wherein the step of comparing includes comparing the respective superposition reference depth distributions to identify assignments of request streams to the caches which optimize the likelihood that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 12
Dependent Claim
78 words
A processing system for assigning data request streams to various ones of a plurality of data caches, the processing system comprising: means for obtaining characterization information for the request streams; and means for determining an assignment of the request streams to the caches using the characterization information, such that a likelihood is optimized that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 13
Dependent Claim
78 words
A processing system for assigning data request streams to various ones of a plurality of data caches, the processing system comprising: means for obtaining characterization information for the request streams; and means for determining an assignment of the request streams to the caches using the characterization information, such that a likelihood is optimized that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 14
Dependent Claim
27 words
A processing system as recited in claim 11, wherein the means for obtaining characterization information includes means for processing a trace of requests from the request streams.
Claim 15
Dependent Claim
74 words
A processing system as recited in claim 12, wherein the means for processing includes: means for processing the requests of the trace successively; means for simulating trajectories of data pages requested by the requests in the trace, the trajectories including sequences of cache positions related to the successive processing of the requests of the trace; and means for calculating depth distributions from the requests for the respective request streams, based on the simulated trajectories.
Claim 16
Dependent Claim
44 words
A processing system as recited in claim 13, wherein the means for processing a trace includes means for obtaining burst information related to bursts of consecutive requests, within the trace, the consecutive requests within each given burst all coming from the same request stream.
Claim 17
Dependent Claim
213 words
A processing system as recited in claim 14, wherein the means for obtaining burst information includes: means for maintaining flags F a ,b, each flag having a value of TRUE if a page requested from a stream a (designated a type a request) was encountered more recently in the trace than any page requested from a stream b (designated a type b request), and FALSE otherwise; means for maintaining of variables n a , each variable counting the number of type a requests encountered among the requests of the trace thus far processed; means for maintaining variables B a ,b each variable counting the number of bursts of consecutive type a requests of the trace, assuming that all requests other than type a or type b requests in the trace are deleted; and means, operable for each successive type t request of the trace, for updating the flags F a ,b, the variables n a , and the variables B a ,b by (a) incrementing the variable n t , (b) for all types s other than t, testing the state of the flag F s ,t, and (c) if the state is FALSE, then (i) setting F s ,t =TRUE, (ii) setting F t ,s =FALSE, and (iii) incrementing B t ,s.
Claim 18
Dependent Claim
67 words
A processing system as recited in claim 15, wherein the means for obtaining burst information further includes: means; operable following operation of the means for maintaining flags F a ,b, the means for maintaining a vector of variables n a , the means for maintaining variables B a ,b, and the means for updating; for computing mean burst lengths M a ,b according to the formula ##EQU25##
Claim 19
Dependent Claim
66 words
A processing system as recited in claim 14, wherein the means for determining an assignment includes: means for making an initial fully split assignment of a predetermined number of data pages to a number of caches equal to the number of request streams; and means for superposing pairs of request streams, thereby making an assignment in which superposed request streams are assigned to a single cache.
Claim 20
Dependent Claim
122 words
A processing system as recited in claim 17 wherein the means for making an initial fully split assignment includes: (a) means for calculating an optimal allocation of a subset k of the buffers to a number 1 of caches less than the number of streams; (b) means for calculating an optimal allocation, where the number of caches is increased by one, as the allocation having the lowest miss ratio of any allocation in which the k buffers remain allocated to the 1 caches and all of the remaining buffers are allocated to the one additional cache; and (c) means for repeating operation of the (b) means for calculating an optimal allocation, until the number of caches equals the number of request streams.
Claim 21
Dependent Claim
74 words
A processing system method as recited in claim 17, wherein the means for superposing includes: means for computing respective superposition reference depth distributions for respective superpositions of the request streams, based on reference depth distributions for the request streams in isolation and on burst rates of the request streams; and means for comparing the respective superposition reference depth distributions to identify a superposition of request streams which produces an optimum improvement in hit ratio.
Claim 22
Dependent Claim
61 words
A processing system method as recited in claim 19, wherein the means for comparing includes means for comparing the respective superposition depth distributions to identify assignments of request streams to the caches which optimize the likelihood that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 23
Dependent Claim
114 words
A computer program product, for use with a processing system, for directing the processing system to assign data request streams to various ones of a plurality of data caches, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the processing system to obtain characterization information for the request streams; and means, recorded on the recording medium, for directing the processing system to determine an assignment of the request streams to the caches using the characterization information, such that a likelihood is optimized that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 24
Dependent Claim
114 words
A computer program product, for use with a processing system, for directing the processing system to assign data request streams to various ones of a plurality of data caches, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the processing system to obtain characterization information for the request streams; and means, recorded on the recording medium, for directing the processing system to determine an assignment of the request streams to the caches using the characterization information, such that a likelihood is optimized that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
Claim 25
Dependent Claim
40 words
A computer program product as recited in claim 21, wherein the means for directing to obtain characterization information includes means, recorded on the recording medium, for directing the processing system to process a trace of requests from the request streams.
Claim 26
Dependent Claim
107 words
A computer program product as recited in claim 22, wherein the means for directing to process includes: means, recorded on the recording medium, for directing the processing system to process the requests of the trace successively; means, recorded on the recording medium, for directing the processing system to simulate trajectories of data pages requested by the requests in the trace, the trajectories including sequences of cache positions related to the successive processing of the requests of the trace; and means, recorded on the recording medium, for directing the processing system to calculate depth distributions from the requests for the respective request streams, based on the simulated trajectories.
Claim 27
Dependent Claim
57 words
A computer program product as recited in claim 23, wherein the means for directing to process a trace includes means, recorded on the recording medium, for directing the processing system to obtain burst information related to bursts of consecutive requests, within the trace, the consecutive requests within each given burst all coming from the same request stream.
Claim 28
Dependent Claim
253 words
A computer program product as recited in claim 24, wherein the means for directing to obtain burst information includes: means, recorded on the recording medium, for directing the processing system to maintain flags F a ,b, each flag having a value of TRUE if a page requested from a stream a (designated a type a request) was encountered more recently in the trace than any page requested from a stream b (designated a type b request), and FALSE otherwise; means, recorded on the recording medium, for directing the processing system to maintain variables n a , each variable counting the number of type a requests encountered among the requests of the trace thus far processed; means, recorded on the recording medium, for directing the processing system to maintain variables B a ,b each variable counting the number of bursts of consecutive type a requests of the trace, assuming that all requests other than type a or type b requests in the trace are deleted; and means, recorded on the recording medium, for directing the processing system, for each successive type t request of the trace, to update the flags F a ,b, the variables n a , and the variables B a ,b by (a) incrementing the variable n t , (b) for all types s other than t, testing the state of the flag F s ,t, and (c) if the state is FALSE, then (i) setting F s ,t =TRUE, (ii) setting F ts =FALSE, and (iii) incrementing B t ,s.
Claim 29
Dependent Claim
83 words
A computer program product as recited in claim 25, wherein the means for directing to obtain burst information further includes means; operable following operation of the means for directing to maintain flags F a ,b, the means for directing to maintain a vector of variables n a , the means for directing to maintain variables B a ,b, and the means for directing to update; for directing the processing system to compute mean burst lengths M a ,b according to the formula ##EQU26##
Claim 30
Dependent Claim
89 words
A computer program product as recited in claim 24, wherein the means for directing to determine an assignment includes: means, recorded on the recording medium, for directing the processing system to make an initial fully split assignment of a predetermined number of data pages to a number of caches equal to the number of request streams; and means, recorded on the recording medium for directing the processing system to superpose pairs of request streams, thereby making an assignment in which superposed request streams are assigned to a single cache.
Claim 31
Dependent Claim
153 words
A computer program product as recited in claim 27 wherein the means for directing to make an initial fully split assignment includes: (a) means, recorded on the recording medium, for directing the processing system to calculate an optimal allocation of a subset k of the buffers to a number 1 of caches less than the number of streams; (b) means, recorded on the recording medium, for directing the processing system to calculate an optimal allocation, where the number of caches is increased by one, as the allocation having the lowest miss ratio of any allocation in which the k buffers remain allocated to the 1 caches and all of the remaining buffers are allocated to the one additional cache; and (c) means, recorded on the recording medium, for directing the processing system to operate the (b) means for directing to calculate, repetitively, until the number of caches equals the number of request streams.
Claim 32
Dependent Claim
96 words
A computer program product as recited in claim 27, wherein the means for directing to superpose includes: means, recorded on the recording medium, for directing the processing system to compute respective superposition reference depth distributions for respective superpositions of the request streams, based on reference depth distributions for the request streams in isolation and on burst rates of the request streams; and means, recorded on the recording medium, for directing the processing system to compare the respective superposition reference depth distributions to identify a superposition of request streams which produces an optimum improvement in hit ratio.
Claim 33
Dependent Claim
74 words
A computer program product as recited in claim 29, wherein the means for directing to compare includes means, recorded on the recording medium, for directing the processing system to compare the respective superposition reference depth distributions to identify assignments of request streams to the caches which optimize the likelihood that a request from a given request stream is directed to a data page within a cache to which the given request stream is assigned.
References Cited (Backward Citations)
US4468730A
Cited
US4536836A
Cited
US4835678A
Cited
US4972314A
Cited
US4888681A
Cited
US4928225A
Cited
US5029070A
Cited
US5185871A
Cited
US5228134A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-05 | 2000-11-04 | 2001-05-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-05 | 2004-11-04 | 2005-05-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-05 | 2008-11-04 | 2009-05-06 | $7700.00 | Window Closed / Lapsed |