Suggest ways to modify the Bitonic Sort class so that it will sort an input array of width w, where w is not a power of 2. Consider the following gw-thread counting algorithm. Each thread first uses a...

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

Consider the following gw-thread counting algorithm. Each thread first uses a bitonic counting network of width w to take a counter value v. It then goes through awaiting 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

A thread that exits with value v spins on filter[(v−1)modn] until that value is set to φ (v−1). The thread responds by setting filter [vmdow] to φ(v), and then return s v.

1. Explain why this counter implementation is linearizable.

2.An exercise here shows that any linear Iz able 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.