Upper and lower I/O bounds for pebbling r-pyramids

AbstractModern computers have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I/O traffic to slower memories in the hierarchy. In this paper, we present I/O efficient algorithms to pebble r-pyramids and derive lower bounds on the number of I/O operations to do so. The r-pyramid graph models financial applications which are of practical interest and where minimizing memory traffic can have a significant impact on cost saving