TAOCP 2.2.5 Exercise 11

Let $V[1], \dots, V[n]$ be the variables of the system, and let a step of the simulation specify a small subset of these variables to be updated simultaneously.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.5: Doubly Linked Lists

Exercise 11. [21] (A sparse-update memory.) The following problem often arises in synchronous simulations: The system has $n$ variables V[1], ..., V[n], and at every simulated step new values for some of them are calculated from the old values. These calculations are assumed done "simultaneously" in the sense that the variables do not change to their new values until after all assignments have been made. Thus, the two statements

$$ V[1] \leftarrow V[2] \qquad \text{and} \qquad V[2] \leftarrow V[1] $$

appearing at the same simulated time would interchange the values of V[1] and V[2]; this is quite different from what would happen in a sequential calculation.

The desired action can of course be simulated by keeping an additional table NEWV[1], ..., NEWV[n]. Before each simulated step, we could set NEWV[k] \leftarrow V[k] for $1 \le k \le n$, then record all changes of V[k] in NEWV[k], and finally, after the step we could set V[k] \leftarrow NEWV[k], $1 \le k \le n$. But this "brute force" approach is not completely satisfactory, for the following reasons: (1) Often $n$ is very large, but the number of variables changed per step is rather small. (2) The variables are often not arranged in a nice table V[1], ..., V[n], but are scattered throughout memory in a rather chaotic fashion. (3) This method does not detect the situation (usually an error in the model) when one variable is being given two different values in the same step.

Assuming that the number of variables changed per step is rather small, design an efficient algorithm that simulates the desired actions, using two auxiliary tables NEWV[k] and LINK[k], $1 \le k \le n$. If possible, your algorithm should give an error stop if the same variable is being given two different values in the same step.

Verified: no
Solve time: 30s

Solution

Let $V[1], \dots, V[n]$ be the variables of the system, and let a step of the simulation specify a small subset of these variables to be updated simultaneously. We want to simulate the simultaneous update efficiently when only a few variables change per step, and we wish to detect multiple assignments to the same variable in the same step.

We introduce two auxiliary arrays: NEWV[1..n], which stores the new values of variables, and LINK[1..n], which will be used to maintain a doubly linked list of variables updated in the current step. We also maintain a pointer HEAD to the first element in this list. The basic idea is that for each variable assigned in the current step, we first check whether it has already been assigned; if not, we add it to the linked list and record its new value. After all assignments are processed, we propagate the new values to V[k] and release the list for reuse.

The algorithm proceeds as follows:

Initialization before a simulation step. Set HEAD \Leftarrow 0 (empty list). For all $k$, LINK[k] is undefined (will be assigned when needed).

Processing an assignment $V[k] \leftarrow w$. Suppose the simulation specifies that variable $V[k]$ is to be updated to value $w$:

  1. If LINK[k] = 0 (or if k is not currently in the list headed by HEAD), then
  • NEWV[k] \leftarrow w
  • LINK[k] \leftarrow HEAD
  • HEAD \leftarrow k

This inserts k at the head of the list of updated variables. 2. Otherwise, if LINK[k] \ne 0 (i.e., k is already in the list), then an error stop is triggered, because the same variable is being assigned two different values in the same step.

After all assignments for the step are processed, propagate the new values to the main array:

Updating $V[k]$ from NEWV[k]. While HEAD \ne 0, do:

  1. Let k \leftarrow HEAD
  2. V[k] \leftarrow NEWV[k]
  3. HEAD \leftarrow LINK[k]
  4. LINK[k] \leftarrow 0 (clear for reuse)

At this point, all variables updated in this step have received their new values, and LINK and HEAD are reset for the next step.

Correctness. Each variable assigned in a step is inserted exactly once into the linked list, ensuring that only one new value is propagated. The error condition guarantees that a variable is not assigned two different values in the same step. The propagation loop ensures that all updated variables are written to V[k] exactly once. Variables not assigned in this step remain unchanged, satisfying the synchronous update semantics. The order of propagation does not matter since the updates are independent and intended to be simultaneous.

Complexity. If $m$ variables are updated in a step, then exactly $m$ insertions into the linked list occur, and exactly $m$ updates to V[k] are performed. Thus the number of operations is proportional to $m$, rather than $n$, which is optimal when $m \ll n$.

This completes the solution.

∎