Benchmark applications

We use eight benchmark applications in our evaluation. Four of the benchmark applications are explicit-I/O applications, three are swapping applications, and one performs a substantial amount of both types of I/O. To assist comparison with prior work, these benchmarks are similar, and in many cases identical, to those used in prior evaluations of the TIP prefetching and caching manager [5], user-level speculative execution [3] and compiler-based prefetching [4,2]. The benchmarks are summarized in Table 1 and described in greater detail below.

Table 1: Benchmark characteristics. Run time is on an unmodified kernel, with no speculative execution.

Benchmark	Description	Run time	Read calls	Data set size
Agrep	text search	42 s	9385	105 MB
Gnuld	object code linker	30 s	16261	70 MB
PostgreSQL	AS3AP benchmark (database queries)	9915 s	4845047	535 MB
XDataSlice	visualization of 3-D data sets	171 s	46421	512 MB
FFTPDE	FFT solver for 3-D PDEs	5537 s	-	224 MB
MGRID	multigrid solver for 3-D potential	913 s	-	431 MB
MATVEC	Matrix-vector multiplication	1006 s	-	385 MB
Sphinx	Off-line speech recognition	72 s	66358	181 MB

Agrep (version 2.0.4) is a fast pattern matching utility. Agrep opens each file on its command line in turn, and reads each one sequentially from start to finish. In the benchmark, Agrep searches 8971 files in the Linux 2.4.5 source tree for exact matches of a simple string that does not occur in any of the files.

Gnuld (version 2.11.2) is the Free Software Foundation's object code linker. Gnuld first reads each object file's file header and uses it to find the symbol header, which in turn provides offsets to the symbol and string tables. Gnuld then makes a small number of small, non-sequential reads to gather debugging information; the required file offsets are determined from the symbol tables. Finally, Gnuld sequentially reads the non-debugging sections in each object file. In the benchmark, an Alpha cross-linker is used to link 562 object files to produce a Digital UNIX kernel.

PostgreSQL (version 7.0.3) is an enhanced version of the original POSTGRES database management system. Our tests use a subset of the open-source database benchmark (OSDB), which implements the industry-standard AS3AP benchmark suite [6]. Our data set consists of four relations conforming to the AS3AP specification, which reside in 500MB of disk space. Our benchmark generates a set of indexes for each relation.

XDataSlice (version 2.2) is a data visualization package that allows users to view a false-color representation of arbitrary slices through a three-dimensional data set. The original application limited itself to data sets that fit into memory, but our version was modified for the TIP benchmark suite [5] to load data dynamically from large data sets. In the benchmark, XDataSlice retrieves 25 random slices through a set of 512x512x512 32-bit values which resides in 512MB of disk space.

FFTPDE and MGRID are two applications from the NAS Parallel benchmark suite [7], which have been modified by Demke and Mowry [2] so that their data sets do not fit in main memory. These applications make looping array accesses whose stride length and bounds vary dynamically during execution. This lack of predictability makes it hard for a conventional prefetcher to prevent I/O stalls.

MATVEC is a matrix-vector multiplication kernel that we obtained directly from Demke and Mowry's recent paper on compiler-based prefetching and memory management [2].

Finally, Sphinx is a speech recognition application. As with XDataSlice, the original application was modified to load its data dynamically from disk for the TIP benchmark suite [5]. The benchmark is to recognize an 18-second recording that was commonly used in Sphinx regression testing. The benchmark contains two phases: a first phase in which it reads about 15MB in a mostly sequential fashion from four data files, and a second phase of seemingly random accesses to a 176MB file.