Tag Archives: Register Sufficiency

Sequencing to Minimize Maximum Cumulative Cost

I want to give credit to our Interlibrary Loan people who tracked this reference down- it’s a Ph.D. thesis that only existed on microfilm.   So I got to use the microfilm reader for the first time since elementary school.  Those things are very different now.

The problem: Sequencing to Minimize Maximum Cumulative Cost.  This is problem SS7 in the appendix.

The description: Given a set of tasks with a partial order defined on the tasks, and a (possibly negative) integer cost c(t) for each task t, and a positive value Z.  Can we create a one-processor schedule that obeys the partial order constraints such that for each task t, the cost of each task scheduled before t is K or less?

Example: Suppose we have the following precedence graph of tasks (the number in the vertex is the cost of the task):

The schedule (d,e,a,c,b), has the last cost (task b) with a total cost of 12 (the sum of the costs of all tasks before it).  Notice that if some task costs are negative, it’s possible that the last task that is done does not have the maximum total cost.  For example, if task c’s cost was -4, then the schedule (d,e,a,c,b) has its maximum cost of 10 after task a is scheduled.

Reduction: I got this from a Ph.D. thesis by Abdel-Wahab, and in it, he reduces from Register Sufficiency.  So we’re given an instance of register sufficiency: a directed graph G=(V,E), and a K.  The precedence graph G’=(V’, E’) that we’ll build has 2 copies of every vertex in G.  The edge set of G’ will have all of the edges in E, and additionally, if (i,j) is an edge in E, then (j’, i) is an edge in E’.  (That’s an edge from the second copy of j, back to i.)  Each vertex costs 1 if it was in V, and -1 if it is a second copy.  Set K’ = K+1.

If the register sufficiency problem has a solution, then we build a sequence based on it.  Thinking in terms of Sethi’s “stone game”, each time we place a new stone on a vertex, we add that vertex to the end of the sequence.  If we pick up a stone from vertex x, add x’ (the second copy) to the end of the sequence.  If we’re moving a stone from y to x, then that’s like removing it from y and adding it to x.  You can prove by induction that the max cost of any task in this sequence is K’.

If the scheduling task has a solution, then we build a solution to the stone game.  For each task in the schedule, if it is in V (the original set of vertices), then place a stone on that vertex.   If it is not in V then it is a new vertex, so remove a stone from the copy in V.  Since K’ = K+1, it’s possible that this sequence of steps uses K+1 stones, so we need to modify it to use K.   So, find a node in the sequence whose cost is exactly K’.  We know this node is in V (it was a “place a stone” move since it took us to K’ stones).  It can’t be the last task since we have to end with one that costs -1 (since all of those vertices have no outdegree, and the ones that cost 1 all have an outdegree of at least 1).    So look at the task after it.  It can’t be a “place a stone” move, otherwise, we’ll use K’+1 stones.  So we know that the next task to be scheduled has cost -1.  Since that move will be to pick up a stone, just move the stone that’s about to be removed to our peak cost task instead of allocating a new stone, and we will solve the problem using 1 less stone at this point. If multiple places in the schedule cost K’ exactly, we can do this modification to all of them, creating a program sequence that uses just K stones at most.

Difficulty: 6.  The reduction is not hard, but the stone game takes some work to understand, and the turning a solution that costs K’ into a solution that costs K is a little tricky.  I wonder if there’s an alternate reduction that has K’=K.

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.