Red-Black Prefetching: An Approximation Algorithm for Parallel Disk Scheduling

We address the problem of I/O scheduling of read-once reference strings in a multiple-disk parallel I/O system. We present a novel on-line algorithm, Red-Black Prefetching (RBP), for parallel I/O scheduling. In order to perform accurate prefetching RBP uses L-block lookahead. The performance of RBP is analyzed in the standard parallel disk model with D independent disks and a shared I/O buffer of size M. We show that the number of parallel I/Os performed by RBP is within a factot $\Theta(\max \{\sqrt{MD/L}, D^{1/3}\})$ of the number of I/Os done by the optimal off-line algorithm. This ratio is within a canstant factor of the best possible when L is L=O(MD1/3).