US5794243A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for executing a binary search in a data cache
Assignee: International Business Machines Corp
•
Filing: 1995-12-11
•
Granted: 1998-08-11
•
Expires: 2015-12-11
Abstract
Abstract Minimizing data cache misses when performing binary searches. Values in an array to be searched are stored as subsets, clustered to minimize the number of cache misses. A first set of auxiliary values is created consisting of a subset of the first-searched values that fit on one cache line. Subsequent sets of values are then created consisting of one cache line full of values for each value in the first set within one cache line. A binary search is conducted by first searching SET ONE, for the largest array value that is less-than or equal to the search key, or alternatively the smallest array value greater than or equal to the search key. The search of SET ONE, is followed by a search of any subsequent sets of values, with the binary search concluding by testing values within one cache line in the subsequent sets of values until the desired value is found.
Inventors
- 👤 William Preston Alexander, III
- 👤 Geoffrey Owen Blandy
- 👤 Robert J. Urquhart
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:34
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
128 words
A method, implemented in a computer system, for executing a binary search in a data cache for a value in a random ordered array in main memory of said computer, wherein said main memory is connected to a data cache, comprising the steps of: creating a first set of values for said random ordered array as a subset of first-search values on one cache line of said data cache; calculating a total cluster size for said random ordered array based on said array size and said data cache line size; creating subsequent sets of values of said random ordered array of one cache line full of values for each value of said first set of values; performing a binary search for a search key in said data cache.
Claim 2
Independent Claim
128 words
A method, implemented in a computer system, for executing a binary search in a data cache for a value in a random ordered array in main memory of said computer, wherein said main memory is connected to a data cache, comprising the steps of: creating a first set of values for said random ordered array as a subset of first-search values on one cache line of said data cache; calculating a total cluster size for said random ordered array based on said array size and said data cache line size; creating subsequent sets of values of said random ordered array of one cache line full of values for each value of said first set of values; performing a binary search for a search key in said data cache.
Claim 3
Dependent Claim
46 words
The method of claim 1, wherein the step of performing a binary search further comprises: searching said first set for said search key; and searching for said search key in said subsequent sets of values when said search key is not found in said first set.
Claim 4
Dependent Claim
47 words
The method of claim 2, further comprising: searching said first set for the largest array value less than or equal to said search key; and searching for said search key in said subsequent sets of values based on the largest array value found in said first set.
Claim 5
Dependent Claim
47 words
The method of claim 2, further comprising: searching said first set for the smallest array value greater than or equal to said search key; and searching for said search key in said subsequent sets of values based on the smallest array value found in said first set.
Claim 6
Independent Claim
129 words
An apparatus for executing a binary search in a data cache for a value in a random ordered array in main memory of said computer, where said main memory is connected to a data cache, comprising: means for creating a first set of values for said random ordered array as a subset of first-search values on one cache line of said data cache; means for calculating a total cluster size for said random ordered array based on said array size and said data cache line size; means for creating subsequent sets of values of said random ordered array of one cache line full of values for each value of said first set of values; and means for performing a binary search for a search key in said data cache.
Claim 7
Independent Claim
129 words
An apparatus for executing a binary search in a data cache for a value in a random ordered array in main memory of said computer, where said main memory is connected to a data cache, comprising: means for creating a first set of values for said random ordered array as a subset of first-search values on one cache line of said data cache; means for calculating a total cluster size for said random ordered array based on said array size and said data cache line size; means for creating subsequent sets of values of said random ordered array of one cache line full of values for each value of said first set of values; and means for performing a binary search for a search key in said data cache.
Claim 8
Dependent Claim
50 words
The apparatus of claim 5, wherein the means for performing a binary search further comprises: means for searching said first set for said search key; and means for searching for said search key in said subsequent sets of values when said search key is not found in said first set.
Claim 9
Dependent Claim
51 words
The apparatus of claim 6, further comprising: means for searching said first set for the largest array value less than or equal to said search key; and means for searching for said search key in said subsequent sets of values based on the largest array value found in said first set.
Claim 10
Dependent Claim
51 words
The apparatus of claim 6, further comprising: means for searching said first set for the smallest array value greater than or equal to said search key; and means for searching for said search key in said subsequent sets of values based on the smallest array value found in said first set.
Claim 11
Dependent Claim
149 words
A computer program product having a computer readable medium having computer program logic recorded thereon for executing a binary search in a data cache for a value in a random ordered array in main memory of said computer, wherein said main memory is connected to a data cache, comprising: computer readable means for creating a first set of values for said random ordered array as a subset of first-search values on one cache line of said data cache; computer readable means for calculating a total cluster size for said random ordered array based on said array size and said data cache line size; computer readable means for creating subsequent sets of values of said random ordered array of one cache line full of values for each value of said first set of values; computer readable means for performing a binary search for a search key in said data cache.
Claim 12
Dependent Claim
149 words
A computer program product having a computer readable medium having computer program logic recorded thereon for executing a binary search in a data cache for a value in a random ordered array in main memory of said computer, wherein said main memory is connected to a data cache, comprising: computer readable means for creating a first set of values for said random ordered array as a subset of first-search values on one cache line of said data cache; computer readable means for calculating a total cluster size for said random ordered array based on said array size and said data cache line size; computer readable means for creating subsequent sets of values of said random ordered array of one cache line full of values for each value of said first set of values; computer readable means for performing a binary search for a search key in said data cache.
Claim 13
Dependent Claim
51 words
The computer program of claim 9, comprising: computer readable means for searching said first set for an array value equal to said search key; and computer readable means for searching for said search key in said subsequent sets of values when said array value is not found in said first set.
References Cited (Backward Citations)
US5241638A
Cited
US4860201A
Cited
US5155832A
Cited
US5280613A
Cited
US5263160A
Cited
US5396604A
Cited
US5305389A
Cited
US5359723A
Cited
US5404510A
Cited
US5590307A
Cited
US5537573A
Cited
US5513344A
Cited
US5586297A
Cited
US5577227A
Cited
US5548742A
Cited
US5563987A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-10 | 2002-02-09 | 2002-08-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-10 | 2006-02-09 | 2006-08-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-10 | 2010-02-09 | 2010-08-11 | $7700.00 | Window Closed / Lapsed |