Caching in a data processing system using the pigeon hole principle
US6094706A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Mar 2, 1998 |
| Grant date | Jul 25, 2000 |
| Priority date | — |
| Expiry date | Mar 2, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99936
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods and apparatus for resolving access patterns in a data processing system using the pigeon hole principle are disclosed herein. The data processing system has a directed graph G of access patterns including a vertices set V representing cache items. Each cache item v has an access pattern defined by a path of vertices (v.sub.1 .fwdarw. , . . . , .fwdarw.v.sub.n), v.sub.1 representing the start of the path and v.sub.n representing the end of the path at cache item v. The method includes defining a prefix cache for directed graph G which contains a map between an access pattern (v.sub.1 .fwdarw. , . . . , .fwdarw.v.sub.k) and vertex v.sub.k for a kth level L in graph G, storing the prefix cache in a memory and, for a given access pattern (v.sub.1 .fwdarw. , . . . , .fwdarw.v.sub.n), searching the prefix cache for a prefix (v.sub.1 .fwdarw. , . . . , .fwdarw.v.sub.k) of the given access pattern that reaches the kth level L. If the search is successful, the method includes outputting vertex v.sub.k by reference to the stored prefix cache and calling an access pattern resolution primitive which accepts access pattern (v.sub.k+1 .fwdarw. , . . . , .fwdarw.v.sub.n) as an input and g…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.