Name
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 ⋅ log3/2 n) red pebbles, and I/O complexity O(opt ⋅ log3/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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2935764.2935807 | SPAA |
Field | DocType | Citations |
Discrete mathematics,Approximation algorithm,Graph,Combinatorics,Memory hierarchy,Upper and lower bounds,Input/output,Model of computation,Mathematics,Bounded function,Auxiliary memory,Distributed computing | Conference | 2 |
PageRank | References | Authors |
0.37 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Timothy Carpenter | 1 | 2 | 0.37 |
| Fabrice Rastello | 2 | 482 | 38.30 |
| P. Sadayappan | 3 | 4821 | 344.32 |
| Anastasios Sidiropoulos | 4 | 330 | 31.78 |