A pebble game is a game played on Directed Acyclic Graphs (DAGs) in which on each turn the player can put a pebble on a node if all parents (nodes from incoming edges) have pebbles on them. Any number of pebbles can be removed at the end of the turn and reused in future turns. The goal of the game is to place a pebble on a particular result node while trying to minimize the number of turns and/or the number of pebbles used. Such pebble games were used in the 70s and 80s to prove several result in complexity theory involving time/space tradeoffs.
In this talk I'll discuss how an extension of pebble games can be used to give a very clean and relatively precise model of both time and space costs in a wide class of parallel languages, including languages with nested parallelism, with futures, and with fork-join constructs. I'll describe how these ideas have been used to implement an efficient thread scheduler for parallel languages on Symmetric Multiprocessors (SMPs), to generate provable implementation bounds for various languages, and to effectively use futures to generate highly parallel algorithms.
Back to LESS
Last modified: March 28, 1997