Caching in a data processing system using the pigeon hole princi

Details Caching in a data processing system using the pigeon hole princi Caching in a data processing system using the pigeon hole princi

1998-03-02

2000-07-25

Peikari, Behzad James

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

711203, 711118, 707 6, G06F 1200

Patent

active

060947063

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 generates vertex v.sub.n as an output. If the search is unsuccessful, the method includes setting the input to the resolution primitive to the given access pattern (v.sub.1 .fwdarw. , . . . , .fwdarw.v.sub.n) to generate vertex v.sub.n as the output. In either case, the given access pattern (v.sub.1 .fwdarw. , . . . , .fwdarw.v.sub.n) is fully resolved. Apparatus for performing this method is also disclosed. A particular use of the pigeon hole principle for caching in a data processing system involves the resolution of hierarchical file pathnames into in-core representations of the files named by the paths (i.e., namespace resolution) using prefix caching.

REFERENCES:
patent: 5008820 (1991-04-01), Chistopher, Jr. et al.
patent: 5390318 (1995-02-01), Ramakrishnan et al.
patent: 5682499 (1997-10-01), Bakke et al.
patent: 5684976 (1997-11-01), Soheili-Arasi et al.
R.A. Floyd et al., "Directory Reference Patterns In Hierarchical File Systems", IEEE Transactions on Knowledge and Data Engineering, vol. 1, pp. 238-247, Jun. 1989.

Affiliated with

Also associated with

Rating

Caching in a data processing system using the pigeon hole princi does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Caching in a data processing system using the pigeon hole princi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Caching in a data processing system using the pigeon hole princi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1343806