Analysing Object Relationships to Predict Page Access for Prefetching

Authors:	Nils Knafla
Date:	30th August - 1st September 1998
Type:	Paper for the Eighth International Workshop on Persistent Object Systems: Design, Implmentation and Use POS-8 Tiburon, California, 30th August - 1st September 1998
Institution:	Department of Computer Science, Edinburgh University

Abstract

We present a new approach to predicting page accesses to facilitate prefetching persistent objects in a client/server computing environment. The relationships between persistent objects are modelled by a discrete-time Markov Chain, which allowed us to use a method called hitting times to compute the page access probability and the mean time to access a page. If the probability of a page is higher than a threshold defined by cost/benefit parameters then the page is a candidate for prefetching. To determine the prefetching threshold we consider various cost parameters to compare the benefit of a correct prefetch with the cost of an incorrect prefetch. In addition, we compute the best possible time to start the prefetch operation. We incorporated this prefetching algorithm into the EXODUS storage manager, and used the timing results in a simulation.

Nils Knafla, <nk@dcs.ed.ac.uk>