Related Work

TPIE [35,5] was the first large software project implementing I/O-efficient algorithms and data structures. The library provides implementation of I/O efficient sorting, merging, matrix operations, many (geometric) search data structures (B$^+$-tree, persistent B$^+$-tree, R-tree, K-D-B-tree, KD-tree, Bkd-tree), and the logarithmic method. The work on the TPIE project is in progress.

LEDA-SM [11] external memory library was designed as an extension to the LEDA library [25] for handling large data sets. The library offers implementations of I/O-efficient sorting, external memory stack, queue, radix heap, array heap, buffer tree, array, B$^+$-tree, string, suffix array, matrices, static graph, and some simple graph algorithms. However, the data structures and algorithms can not handle more than $2^{31}$ bytes. The development of LEDA-SM has been stopped.

LEDA-SM and TPIE libraries currently offer only single disk external memory algorithms and data structures. They are not designed to explicitly support overlapping between I/O and computation. The overlapping relies largely on the operating system that caches and prefetches data according to a general purpose policy, which can not be as efficient as the explicit approach. Furthermore, overlapping based on system cache on most of the operating systems requires additional copies of the data, which leads to CPU and internal memory overhead.

The idea of pipelined execution of the algorithms which process large data sets not fitting into main memory is well known in relational database management systems [33]. The pipelined execution strategy allows to execute a database query with minimum number of external memory accesses, to save memory space to store intermediate results, and to obtain the first result as soon as possible.

The design framework FG [13] is a programming environment for parallel programs running on clusters. In this framework, parallel programs are split into series of asynchronous stages, which are executed in the pipelined fashion with the help of multithreading. The pipelined execution allows to mitigate disk latency of external data accesses and communication network latency of remote data accesses. I/O and communication could be automatically overlapped with computation stages by the scheduler of FG environment.