Register Sufficiency

We’re jumping ahead again since this problem is used in the next reduction.

The problem: Register Sufficiency.  This is problem PO1 (“Program Optimization”) in the appendix.

The description: Given a directed acyclic graph G=(V,A), and a positive integer K,  can we find a “computation” for G that uses K or fewer registers?  The idea behind a “computation” is that vertices represent values that need to be kept in registers, and edges show dependencies between these values.  So can we represent the computation keeping K or fewer values in memory at all times?

Example: Here is the example graph from the paper by Sethi with the reduction (p.227):

So, for example, the “x” at the bottom is used twice: Once in t1 for the c*x calculation, and one at t3 for the (b+c*x)*x calculation.  We’d like to keep the x in the same register for both calculations.  The numbers of the vertices show the registers holding the values and lead to the following assembly-like computation:

  1. Load c into register 2
  2. Load x into register 3
  3. Multiply registers 2 and 3, putting the result in register 2.
  4. Load b into register 1.
  5. Add registers  1 and 2, putting the result in register 2.
  6. Multiply registers 2 and 3, putting the result in register 2.
  7. Load a into register 3.
  8. Add registers 2 and 3, putting the result into register 1.

A related problem: It’s worth mentioning that Sethi represents this computation problem as a “game” problem of placing stones on a graph.  The stones are like registers.  The possible moves are:

  1. Place a stone on a leaf (allocating that leaf’s value to a register)
  2. Pick up a stone from a node (reclaiming that register for another use)
  3. Place  a stone on a non-leaf node if there is a stone on all of its children (generating a value and putting the result in a new register)
  4. Move a stone from a node to a parent node if all children of the parent have a stone (generating a value and putting the result in a register held by one of the children).

The problem then becomes: Can we get stones on all “root” nodes of G (nodes without parents) using K or fewer stones at all times?

Reduction: Sethi’s reduction is from 3SAT.  The SAT instance has m clauses and n variables.  K will be 5n+3m+1.  The DAG that gets built has n+m “stages”.  The first n stages “assign” truth values to variables, and the rest check that each clause is satisfied.

The variable states are a pretty crazy structure based on a vertex zi, which can only be computed after all of its ancestors are computed, and when computed, there will be n-i+1 stones in hand.  This is the number of stones needed to compute the node to xi and ~xi.  So the last stone in that computation is placed on either xi or ~xi, “setting” its truth value (and not leaving any stones to compute the opposite value).  The clause stages are set up so that we only have enough stones to compute the clause if the clause is satisfiable (using the computed stone sitting on the xi or ~xi vertex).

The actual reduction goes on for pages and pages and has a lot of details to worry about.

Difficulty: 9.  It’s a shame that the cool idea of the stones game still led to such a hard reduction.

Leave a Reply

Your email address will not be published. Required fields are marked *