Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

ABSTRACT

Red-blue pebbling is a model of computation that captures the complexity of I/O operations in systems with external memory access. We focus on one-shot pebbling strategies, that is without re-computation. Prior work on this model has focused on finding upper and lower bounds on the I/O complexity of certain families of graphs. We give a polynomial-time bi-criteria approximation algorithm for this problem for graphs with bounded out-degree. More precisely, given a n-vertex DAG that admits a pebbling strategy with R red pebbles and I/O complexity opt, our algorithm outputs a strategy using O(R ⋅ log^3/2 n) red pebbles, and I/O complexity O(opt ⋅ log^3/2 n). We further extend our result to the generalization of red-blue pebble games that correspond to multi-level memory hierarchies. Finally, we complement our theoretical analysis with an experimental evaluation of our algorithm for red-blue pebbling.

References

1. A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. O(sqrt log n) approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems. In Proc. of the 37th Annual ACM Symposium on Theory of Computing, STOC '05, 2005.
2. P. Austrin, T. Pitassi, and Y. Wu. Inapproximability of treewidth, one-shot pebbling, and related layout problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 13--24. Springer, 2012.
3. D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner. Graph partitioning and graph clustering - 10th DIMACS implementation challenge workshop.
4. S. M. Chan, M. Lauria, J. Nordstrom, and M. Vinyals. Hardness of approximation in PSPACE and separation results for pebble games. In Proc. of IEEE 56th Ann. Symp. on Found. of Comp. Science, 2015.
5. V. Elango, F. Rastello, L.-N. Pouchet, J. Ramanujam, and P. Sadayappan. Data access complexity: The red/blue pebble game revisited. Technical report, OSU-CISRC-7/13-TR16, Ohio State University, 2013.
6. U. Feige, M. Hajiaghayi, and J. R. Lee. Improved approximation algorithms for minimum-weight vertex separators. In Proc. of the 37th Annual ACM Symp. on Theory of Comp., STOC '05, 2005.
7. J.-W. Hong and H. T. Kung. I/O complexity: The red-blue pebble game. In Proc. of the 13th Annual ACM Symposium on Theory of Computing, 1981.
8. G. Karypis and V. Kumar. Metis--unstructured graph partitioning and sparse matrix ordering system, version 2.0. 1995.
9. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359--392, December 1998.
10. P. Klein, A. Agrawal, R. Ravi, and S. Rao. Approximation through multicommodity flow. In Proc. of the 30th Ann. Symp. on Found. of Comp. Science, 1989.
11. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999.
12. J. Nordström. New wine into old wineskins: A survey of some pebbling classics with supplemental results. Foundations and Trends in Theoretical Computer Science. http://people.csail.mit.edu/jakobn, 2010.
13. N. Pippenger. Advances in pebbling. Springer, 1982.
14. D. Ranjan, J. Savage, and M. Zubair. Upper and lower I/O bounds for pebbling r-pyramids. Journal of Discrete Algorithms, 14:2--12, 2012.
15. J. E. Savage. Extending the hong-kung model to memory hierarchies. In Computing and Combinatorics, pages 270--281. Springer, 1995.
16. F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Journal of the ACM (JACM), 37(2):318--334, 1990.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

    • Processors and memory architectures

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms