Book: The art of multiprocessor programming Exercise 147. Consider the following

Question

Book: The art of multiprocessor programming

Exercise 147. 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 lesser 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 n] until that value is set to (v 1). The thread responds by setting filter[v mod w] to (v), and then returns v.

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

Explanation / Answer

1) In the given context, the counter implementation is linearizable as in the order the threads stop spinning. If T1 returns x and T2 returns z, where x<z, then T1 stopped spinning before T2. so T1 could not have started its operation after T2 returned.

2) The proof assumed that only one token could pass completely through the network while other tokens were stalled in the middle.

3) On a bus-based multiprocessor, this filter[] construction have better throughput than a single variable protected by a spin lock as the threads spin on the locally cahed copies. This filter actually works as a queue in background. It is easier to manage the state of filter values module 2 because the predecessor is either executing same phase with the value v-1 or in the previous one with value v-n-1.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.