| 摘要 |
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 (v1-> , . . . , ->vn), v1 representing the start of the path and vn 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 (v1-> , . . . , ->vk) and vertex vk for a kth level L in graph G, storing the prefix cache in a memory and, for a given access pattern (v1-> , . . . , ->vn), searching the prefix cache for a prefix (v1-> , . . . , ->vk) of the given access pattern that reaches the kth level L. If the search is successful, the method includes outputting vertex vk by reference to the stored prefix cache and calling an access pattern resolution primitive which accepts access pattern (vk+1-> , . . . , ->vn) as an input and generates vertex vn as an output. If the search is unsuccessful, the method includes setting the input to the resolution primitive to the given access pattern (v1-> , . . . , ->vn) to generate vertex vn as the output. In either case, the given access pattern (v1-> , . . . , ->vn) 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.
|
