Synchronization and Arbitration in Digital Systems

13

Multi-way Arbiters

The problem of multi-way arbitration has already been briefly discussed in Chapter 11. It is relatively easy to resolve arbitration in a two-way context by using a MUTEX element, built of a simple RS flip-flop and a metastability resolver. The latter is an analog, transistor-based, circuit which prevents the metastable state from its propagation from the outputs of the flip-flop to the outputs of the MUTEX. While the two-way MUTEX, built of CMOS transistors, is known to be free from oscillations, its generalization to the case of a three-way or n-way MUTEX, built on the basis of a multi-state flop, may actually exhibit oscillatory behavior due to the presence of the high-order solutions in its linear approximation [95,96]. As a result, it is recommended to build a multi-way MUTEX, and hence a multi-way arbiter with many clients, by means of composing two-way MUTEXes. Such compositions typically follow one of the standard topologies, such as a mesh, cascaded tree or ring. Other topologies, such as multi-ring and hybrid topologies, which are combination of the above-mentioned ones, are also possible. The detailed comparison of the arbiters within each particular topology and between topologies is beyond the scope of this chapter. Our goal here is to illustrate a number of designs, based on meshes, trees and rings, which all are built using the basic building block, a two-way MUTEX. We will also provide behavioural models for these solutions in the form of Petri ...