Near-Optimal Parallel Prefetching and Caching

The authors consider algorithms for integrated prefetching and caching in a model with a fixed-size cache and any number of backing storage devices (disks). Previously, the single disk case was considered by Cao et al. (1995). They show that the natural extension of their aggressive algorithm to the parallel disk case is suboptimal by a factor near the number of disks in the worst case. The main result is a new algorithm, reverse aggressive, with near-optimal performance in the presence of multiple disks.

Authors

• Tracy Kimbrel
• Anna R. Karlin

Keywords

• Prefetching
• Computer science
• Cache storage
• Costs
• Bandwidth
• Parallel processing
• Polynomials
• Scheduling algorithm
• Caching
• Single Disk
• Number Of Disks
• Unit Time
• Less Than Or Equal
• End Of Phase
• Forward Direction
• Forward Sequences
• Beginning Of Phase
• Start Of Phase
• Wrong Direction
• Time Ti
• Set Of Blocks
• Optimal Rule
• Strong Dominance
• Cursor Position
• Color Block