Using Idle Workstations to Implement Predictive Prefetching

The benefits of Markov-busedpredictive prefetchitig have been largely overshadowed by the overhead required to pro-duce high quality predictions. While both theoretical and simulation results f o r prediction algorithms appear promis-ing, substantial limitations exist in practice. This outcome can be partially attributed to the.fact that practical iniple-metitations ultimately niake conipromises in order to reduce overhead. These conipromises limit the level of ulgorithni complexity, the variety of access patterns, arid the granular-ity of trace data the iniplemetitatioti supports. This paper describes the design and iniplenientatiori of GMS-3e ati operatitig-systeni kerriel extension that ofloads prediction overhead to idle network nodes. GMS-3P builds on the C M S global menlory system, which pages to and from remote workstation memory. 111 GMS-38 the target node sends an on-line trace of an application’s page faults to an idle node that is running a Markov-based prediction algo-rithm. The prediction node then uses CMS to prefetch pages to the target node froni tile men ion of other workstations in the network. Our preliminary results show that predictive prefetchirig cati reduce remote-memory page fault time by 60 % or more and that by ofloaditig prediction overhead to an idle node, GMS-3P can reduce this improved latency by between 24 % and 44%, depending on Markov-model ordes 1