We use a heuristic function compatibility(w_tree, p_tree) which returns an indication between 0 and 1 of the degree to which a working tree w_tree and a pattern tree p_tree resemble each other. When the function's value is above constant MATCH_THRESHOLD, we say that the two trees match, meaning that they are similar enough that they are considered to belong to the same access pattern. We shall explain the definition of compatibility function in more detail after we discuss the basic operation of the mechanism.
As mentioned earlier, a number of pattern trees are saved in virtual memory for each program; a working tree is constructed in the course of every program execution. Whenever a program references a file, a new child node is added in the working tree for the program, and some analysis is performed to find out whether any saved pattern trees can be prefetched. Our analysis follows a simple guideline: if there is no previously prefetched pattern tree or the current working tree no longer matches the prefetched pattern tree, compute the compatibility of the working tree and each of the pattern trees for the program. If any match is found, then prefetch the pattern tree with the highest compatibility. If more than one pattern tree bears the highest compatibility, then prefetch the one most recently saved.
The above analysis is carried out for each executable file inside the working tree whenever the executable initiates a file reference. At this point, a pattern tree may have already been prefetched for the executable, either as the result of prefetch analysis incurred by earlier file accesses or in the form of a subtree of the larger tree we prefetched at a higher level. The executable can always prefetch another pattern tree, based on the analysis result. This effectively allows minor prefetch corrections to be made, reducing the cost of a bad guess.
Two complications may arise when the pattern tree selected for prefetching is large: prefetched files may be evicted from the cache before they are actually referenced, and the cache is considerably destroyed when the prefetching guess is bad. To diminish the extent of these problems, we place an upper limit (PREFETCH_CAPACITY) on the number of files from a pattern tree we shall prefetch at one time. When the pattern tree selected is too large, we prefetch only those files in the initial portion of the tree so that the prefetch limit is not exceeded. We also record the immediate child node of the pattern tree we prefetch last. When later the working tree extends to this child, we will prefetch the remaining portion of the pattern tree, if the latest working tree still matches it. We measure PREFETCH_CAPACITY in number of files, rather than in number of bytes, because such a measure goes well with the access tree structure, where each tree node represents a file. Further, as illustrated later, only the initial portion of a predicted file will be prefetched, hence the cost of an incorrect prediction is proportional to the number of prefetched files.
On program exit, we compare the newly completed working tree with the saved pattern trees. If it doesn't match any of the pattern trees, the working tree is saved as new information. Otherwise, it is substituted for the pattern tree that it matches best.
We set the two algorithmic parameters to the following values: