Fiduciary Pebbling Challenge: Minimize Energy in Red-Blue Pebble Game for 100-Layer NN Gradient
Description
Look at pebbling game characterization of gradient computation in FF neural networks in https://medium.com/tensorflow/fitting-larger-networks-into-memory-583e3c758ff9 . Now extend this to be the red-blue pebble game described below. Minimize the objective in this problem:
1. Problem Overview
The Fiduciary Pebbling Challenge is a strategic resource-management game designed to simulate the "Memory Wall" in modern deep learning hardware. The task is to compute the gradient of a 100-layer neural network while minimizing total energy expenditure. Participants must manage a hierarchy of memory—fast but scarce Red Pebbles (SRAM) and slow but infinite Blue Pebbles (DRAM)—to navigate a 100-step Directed Acyclic Graph (DAG).
2. The Topology (The DAG)
The computation is represented as a linear chain of nodes N_0, N_1, ..., N_100.
- Forward Pass: To compute node N_i, the player must have a Red Pebble on node N_{i-1}. (Initial state: N_0 starts with a Red Pebble).
- Backward Pass (Target): The game is only won when the "gradient" has been computed for every node in reverse order (N_100 → N_0). Computing the gradient for N_i requires a Red Pebble on N_i and a Red Pebble on N_{i+1}.
3. Resource Constraints
- Red Pebbles (r = 11): Represents local SRAM/Registers. You may never have more than 11 Red Pebbles on the graph at any given time.
- Blue Pebbles (b = ∞): Represents external HBM/DRAM. Capacity is unlimited, but access is penalized.
4. Move Set and Energy Costs (Objective Function)
The goal is to minimize the Total Energy Cost (E_total). Each legal move and its energy cost is defined below:
| Move | Description | Energy Cost |
|---|---|---|
| Compute(i) | Place a Red Pebble on N_i. Requires a Red Pebble already on N_{i-1}. Consumes 1 Red Pebble slot. | 1 unit |
| Store(i) | Copy the Red Pebble on N_i to a Blue Pebble (write to DRAM). N_i must currently have a Red Pebble. Blue Pebble persists until deleted. | 100 units |
| Load(i) | Place a Red Pebble on N_i from its existing Blue Pebble (read from DRAM). N_i must have a Blue Pebble. Consumes 1 Red Pebble slot. | 100 units |
| Delete-Red(i) | Remove the Red Pebble from N_i. Frees 1 Red Pebble slot. | 0 units |
| Delete-Blue(i) | Remove the Blue Pebble from N_i. | 0 units |
Rationale: Compute and SRAM operations (Red) cost 1 unit. DRAM access (Store/Load) costs 100 units per operation, reflecting the real-world ~100× latency/energy gap between SRAM and DRAM/HBM. Deletions are free as they involve no data movement.
Note: Placing a Red Pebble on a node via Compute or Load consumes 1 unit of your 11-pebble capacity. Deleting a Red Pebble frees that capacity.
5. Unambiguous Rules of Play
- Initial State: N_0 is pebbled Red. E = 0.
- Sequential Computation: A node N_i can only be visited (Red pebbled via Compute) if its predecessor N_{i-1} is currently Red pebbled.
- Persistence: If a Red Pebble is removed from N_i and it does not have a Blue Pebble, that node's value is "lost" and must be recomputed from the nearest preceding Red or Blue pebble.
- Win Condition: The simulation is complete when the Backward Pass has visited every node from N_100 down to N_0 while respecting the 11-Red-pebble limit.
- Tie-Breaking: If two strategies yield the same energy cost, the strategy with the fewer total moves wins.
6. Deliverable
Submit:
- The complete move sequence (as a list of moves) for your strategy.
- The total energy cost E_total.
- A brief explanation of the strategy (e.g., checkpoint interval chosen and why).