Andrew Tomkins

Practical and Theoretical Issues in Prefetching and Caching Degree Type: Ph.D. in Computer Science
Advisor(s): Merrick Furst
Graduated: December 1997

Abstract:

This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed preteching and caching in which an application provides information about its upcoming I/A accesses to the operating system, allowing the system to prefetch data and to make informed cache replacement decisions. I compare existing algorithms for this problem using trace-driven simulation, and use the results to develop a new algorithm that performs better than previous approaches, again under trace-driven simulation.

The second part considers weights caching, a theoretical problem from the domain of on-line algorithms. I present an algorithm with competitive ratio O(log²k) on (k + 1)-point spaces, the first poly-logarithmic ratio for this problem. I also give an almost-tight lower bound of Omega(log k) for any weighted caching problem on at least k + 1 points. I then show a connection between this problem and a new on-line k-server model in which the servers may rearrange themselves without cost during "free-time" between requests, and describe a series of results in the free-time model.

Thesis Committee:
Merrick Furst (Chair)
Avrim Blum
Garth Gibson
Daniel D. Sleator
Richard J. Lipton (Princeton University)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Operating systems, storage management, secondary storage, caching, prefeching, trace-driven simulation, TIP, algorithms, probabalistic algorithms, online algorithms, competitive ratio, weighted caching, metrical task systems, free time, k-server problems