Counting, sorting, and distributed coordination

Prev: Stacks and elimination Next: Concurrent hashing and natural parallelism

Exercises

Exercise 12.1. Prove Lemma 12.5.1.

Exercise 12.2. Implement a trinary CombiningTree, that is, one that allows up to three threads coming from three subtrees to combine at a given node. Can you estimate the advantages and disadvantages of such a tree when compared with a binary combining tree?

Exercise 12.3. Implement a CombiningTree using Exchanger objects to perform the coordination among threads ascending and descending the tree. What are the possible disadvantages of your construction when compared to the CombiningTree class presented in Section 12.3?

Exercise 12.4. Implement the cyclic array-based shared pool described in Section 12.2 using two simple counters and a ReentrantLock per array entry.

Exercise 12.5. Provide an efficient lock-free implementation of a Balancer.

Exercise 12.6. (Hard) Provide an efficient wait-free implementation of a Balancer (i.e., not by using the universal construction).

Exercise 12.7. Prove that the TREE[2^k] balancing network constructed in Section 12.6 is a counting network, that is, that in any quiescent state, the sequences of tokens on its output wires have the step property.

Exercise 12.8. Let $B$ be a width- $w$ balancing network of depth $d$ in a quiescent state $s$ . Let $n = 2^{d}$ . Prove that if $n$ tokens enter the network on the same wire, pass through the network, and exit, then $B$ will have the same state after the tokens exit as it did before they entered.

Exercise 12.9. Let $X$ and $Y$ be $k$ -smooth sequences of length $w$ . A matching layer of balancers for $X$ and $Y$ is one where each element of $X$ is joined by a balancer to an element of $Y$ in a one-to-one correspondence.

Prove that if $X$ and $Y$ are each $k$ -smooth and $Z$ is the result of matching $X$ and $Y$ , then $Z$ is $(k + 1)$ -smooth.

Exercise 12.10. Consider a BLOCK[k] network in which each balancer has been initialized to an arbitrary state (either up or down). Show that no matter what the input distribution is, the output distribution is $(lo g k)$ -smooth.

Hint: You may use the claim in Exercise 12.9.

Exercise 12.11. A smoothing network is a balancing network that ensures that in any quiescent state, the output sequence is $1$ -smooth. Counting networks are smoothing networks, but not vice versa.

A Boolean sorting network is one in which all inputs are guaranteed to be Boolean. Define a pseudosorting balancing network to be a balancing network with a layout isomorphic to a Boolean sorting network.

Let $N$ be the balancing network constructed by taking a smoothing network $S$ of width $w$ , taking a pseudosorting balancing network $P$ also of width $w$ , and joining the $i$ th output wire of $S$ to the $i$ th input wire of $P$ .

Show that $N$ is a counting network.

Exercise 12.12. A 3-balancer is a balancer with three input lines and three output lines. Like its 2-line relative, its output sequences have the step property in any quiescent state. Construct a depth- $3$ counting network with six input and output lines from 2-balancers and 3-balancers. Explain why it works.

Exercise 12.13. Suggest ways to modify the BitonicSort class so that it will sort an input array of width $w$ , where $w$ is not a power of $2$ .

Exercise 12.14. Consider the following $w$ -thread counting algorithm. Each thread first uses a bitonic counting network of width $w$ to take a counter value $v$ . It then goes through a waiting filter, in which each thread waits for threads with lower values to catch up.

The waiting filter is an array filter[] of $w$ Boolean values. Define the phase function

$ϕ (v) = ⌊ v / w ⌋ mod 2$ .

A thread that exits with value $v$ spins on filter[(v - 1) mod w] until that value is set to $ϕ (v - 1)$ . The thread responds by setting filter[v mod w] to $ϕ (v)$ , and then returns $v$ .

Explain why this counter implementation is linearizable.
An exercise here shows that any linearizable counting network has depth at least $w$ . Explain why the filter[] construction does not contradict this claim.
On a bus-based multiprocessor, would this filter[] construction have better throughput than a single variable protected by a spin lock? Explain.

Exercise 12.15. If a sequence $X = x_{0}, \dots, x_{w - 1}$ is $k$ -smooth, then the result of passing $X$ through a balancing network is $k$ -smooth.

Exercise 12.16. Prove that the BITONIC[w] network has depth $(lo g w) (1 + lo g w) /2$ and uses $(w lo g w) (1 + lo g w) /4$ balancers.

Exercise 12.17. Show that the OddEven network in Fig. 12.28 is a sorting network but not a counting network.

Exercise 12.18. Can counting networks do anything besides increments? Consider a new kind of token, called an antitoken, which we use for decrements. Recall that when a token visits a balancer, it executes getAndComplement(): It atomically reads the toggle value and complements it, and then departs on the output wire indicated by the old toggle value. Instead, an antitoken complements the toggle value, and then departs on the output wire indicated by the new toggle value. Informally, an antitoken “cancels” the effect of the most recent token on the balancer’s toggle state, and vice versa.

public synchronized int antiTraverse() {
  try {
    if (toggle) {
      return 1;
    } else {
      return 0;
    }
  } finally {
    toggle = !toggle;
  }
}

Instead of simply balancing the number of tokens that emerge on each wire, we assign a weight of +1 to each token and -1 to each antitoken. We generalize the step property to require that the sums of the weights of the tokens and antitokens that emerge on each wire have the step property. We call this property the weighted step property.

Figure 12.30 shows an antiTraverse() method that moves an antitoken through a balancer. Other networks would need different antiTraverse() methods.

Let $B$ be a width- $w$ balancing network of depth $d$ in a quiescent state $s$ . Let $n = 2^{d}$ . Show that if $n$ tokens enter the network on the same wire, pass through the network, and exit, then $B$ will have the same state after the tokens exit as it did before they entered.

Exercise 12.19. Let $B$ be a balancing network in a quiescent state $s$ , and suppose a token enters on wire $i$ and passes through the network, leaving the network in state $s^{'}$ . Show that if an antitoken now enters on wire $i$ and passes through the network, then the network goes back to state $s$ .

Exercise 12.20. Show that if balancing network $B$ is a counting network for tokens alone, then it is also a balancing network for tokens and antitokens.

Exercise 12.21. A switching network is a directed graph, where edges are called wires and nodes are called switches. Each thread shepherds a token through the network. Switches and tokens are allowed to have internal states. A token arrives at a switch via an input wire. In one atomic step, the switch absorbs the token, changes its state and possibly the token’s state, and emits the token on an output wire. For simplicity, switches have two input and output wires. Note that switching networks are more powerful than balancing networks, since switches can have arbitrary state instead of a single bit, and tokens also have state.

An adding network is a switching network that allows threads to add or subtract arbitrary values.

We say that a token is in front of a switch if it is on one of the switch’s input wires. Start with the network in a quiescent state $q_{0}$ , where the next token to run will take value $0$ . Imagine we have one token $t$ of weight $a$ and $n - 1$ tokens $t_{1}, \dots, t_{n - 1}$ all of weight $b$ , where $b > a$ , each on a distinct input wire. Denote by $S$ the set of switches that $t$ traverses if it traverses the network by starting in $q_{0}$ .

Prove that if we run the $t_{1}, \dots, t_{n - 1}$ one at a time through the network, we can halt each $t_{i}$ in front of a switch of $S$ .

At the end of this construction, $n - 1$ tokens are in front of switches of $S$ . Since switches have two input wires, it follows that $t$ ‘s path through the network encompasses at least $n - 1$ switches, so any adding network must have depth at least $n - 1$ , where $n$ is the maximum number of concurrent tokens. This bound is discouraging because it implies that the size of the network depends on the number of threads, also true for CombiningTrees but not counting networks, and that the network has inherently high latency.

Exercise 12.22. Extend the proof of Exercise 12.21 to show that a linearizable counting network has depth at least $n$ .

Prev: Stacks and elimination Next: Concurrent hashing and natural parallelism

Takashi's Notes

Explorer

Counting, sorting, and distributed coordination

Counting, sorting, and distributed coordination

Exercises

Graph View

Table of Contents

Backlinks