Memory-Hierarchy Tradeoffs - Models of Computation: Exploring the Power of Computing - page 533

ance is achieved when

C comp
C I / O ≈

log 2 S

Consequently, if C comp /C I / O increases by a factor β , S must increase to S β .Underthe
conditions given above, namely, β

≈

7, a balanced two-level memory-hierarchy system for
these problems must have a storage capacity that grows from S to about S 7 every year.

11.2 The Memory-Hierarchy Pebble Game
The standard memory-hierarchy game (MHG) defined below generalizes the two-level red-
blue game to multiple levels. The L -level MHG is played on directed acyclic graphs with p l
pebbles at level l ,1 1, and an unlimited number of pebbles at level L .When

L = 2, the lower level is the red level and the higher is the blue level. The number of pebbles
used at the L

≤ l ≤ L −

− 1 lowest levels is recorded in the resource vector p =( p 1 , p 2 , ... , p L− 1 ) ,

where p j ≥ 1for1 ≤ j ≤ L − 1. The rules of the game are given below.

STANDARD MEMORY-HIERARCHY GAME

R1. (Initialization) A level- L pebble can be placed on an input vertex at any time.

R2. (Computation Step) A first-level pebble can be placed on (or moved to) a vertex if all its
immediate predecessors carry first-level pebbles.

R3. (Pebble Deletion) A pebble of any level can be deleted from any vertex.

R4. (Goal) A level- L pebble must reside on each output vertex at the end of the game.

R5. (Input from Level l )For2 ≤ l ≤ L , a level- ( l − 1 ) pebble can be placed on any vertex

carrying a level- l pebble.

R6. (Output to Level l )For2 ≤ l ≤ L , a level- l pebble can be placed on any vertex carrying a

level- ( l − 1 ) pebble.

The first four rules are exactly as in the red-blue pebble game. The fifth and sixth rules general-
ize the fifth and sixth rules of the red-blue pebble game by identifying inputs from and outputs
to level- l memory. These last two rules allow a level- l memory to serve as temporary storage
for lower-level memories.
In the standard MHG, the highest-level memory can be used for storing intermediate
results. An important variant of the MHG is the I/O-limited memory-hierarchy game ,in
which the highest level memory cannot be used for intermediate storage. The rules of this
game are the same as in the MHG except that rule R6 is replaced by the following two rules:

I/O-LIMITED MEMORY-HIERARCHY GAME

R6. (Output to Level l )For2

≤ l ≤ L −

1, a level- l pebble can be placed on any vertex

carrying a level- ( l

−

1 ) pebble.

R7. (I/O Limitation) Level- L pebbles can only be placed on output vertices carrying level-
( L − 1 ) pebbles.