**The problem: **Code Generation for Parallel Assignments. This is problem PO6 in the appendix.

**The description: **Given a set of variables V= {v_{1} ..v_{n}}, a set of assignments A= {A_{1}..A_{n}}, where each assignment sets some variable v_{i} to the result of some operation on a subset of parameters of V, and an integer K.

Can we order the elements of V in such a way that an assignment references a variable that comes later in the ordering at most K times?

**Example: **Sethi’s paper, which describes this problem, defines a parallel assignment as a statement like this:

i,x <- i+1, x+i

The idea is that both i and x get set to their values in the same assignment.

Sethi also defines a *realization* of an instruction, which is the ordering in which we do the assignments. One realization of the above instruction is to compute i before x, and the other is to do x before i.

The cost of that realization is the number of variables that cause references to future instructions in the realization. So, if we compute i before x, that realization is cost 1, because the x+i instruction has to wait for the change to i to happen (and we have to keep the “new” value of i around someplace to use in the x instruction).

Computing x first and i second has a cost of 0, because we don’t need to keep the value of x around for the second instruction. Our job is to minimize this cost (or, technically, to see if the cost is <= K).

What’s interesting to me, but not really discussed in the paper, is the fact that different realizations have different semantic meanings. If we compute the i+1 first, x gets the updated value of i, but if we compute it second, then x gets the old value of i. Maybe this kind of potential confusion is why we don’t typically see this kind of assignment operation in the present day.

**Reduction: **Sethi uses Feedback Node Set. So we start with a directed graph G. We will map all of the vertices in the graph to variables. For each vertex v_{i} in the graph, if v_{i} has edges connecting to w_{1}..w_{k}, we say that v_{i} is computed from those vertices (the w_{1}..w_{k} are the parameters to create v_{i}). We will use the same K from the Feedback Node Set problem.

Suppose our graph has a set U of feedback vertices. Sethi provides a separate proof about feedback vertex sets: A graph G has a feedback set U if and only if we can order the vertices in the graph y_{1}..y_{n} such that if we have a “backward” edge from y_{j} to y_{i}, if j > i, then y_{j} is in U.

So, we use that ordering as our realization for our assignments. These “backward” edges correspond to “backward” references in our realization (which contribute to the cost). Since each of these back edges must start with a vertex in U, and each one of these vertices costs 1 to our realization cost, this means that our realization cost is at most the size of U, which we know is K.

**Difficulty**: 6. The sequence proof is a bit challenging to follow but other than that the hard part of this is understanding the problem. One thing that tripped me up was that the cost of the realization was the number of variables that had backward references, not the number of references themselves. (So, a variable that has 2 references to 2 different future instructions counts just once)