15

Conclusions Part III

In this Part we have considered a wide range of arbiters, from very simple two-way ones to multi-way ordinary, and then finally multi-way priority arbiters. We illustrated their behaviour by means of signal transition graphs, which are interpreted Petri nets.

Priority arbitration is a powerful method for resource allocation in the context of multiprocessor systems on chips. Here client processes gain access to a shared resource on a priority based discipline. A priority discipline is defined as an arbitrary combinational function, which is an extension to the traditional linear priority scheme. Typical applications for such arbitration schemes are (on-chip) busses and switches.

Conventional techniques for priority arbitration use disciplines which are fixed according to some topological order, such as, a daisy-chain. In the designs described above we allow the discipline of resource allocation to be a function of parameters of the active requests, which are assigned to the requests either statically or dynamically. We can thus consider systems which are clustered in terms of access to shared resources, and the resource allocation discipline is determined on the basis of a combinatorial function of a vector of active requests and their distribution among clusters. We illustrate this solution in our static priority arbiter. The static priority arbiter also provides a generic speed-independent circuitry to lock active requests and issue grants based on a priority module that can be ‘plugged-in’ or re-programmed with varying delays, without affecting the correctness of the overall logic. The dynamic case allows priorities to arrive together with their requests, and be involved in the process of computing the grant. In this dynamic case, we design a priority module which is built as a tree with speed independent priority data path encoding (dual-rail or one-hot). The special feature of this data path logic is that it uses a three-signal control (‘valid’–‘invalid’–‘done’), which maximally decouples control flow from the data path by means of an early propagation of the ‘valid’–‘invalid’ signals, concurrently with processing the priority data, separately acknowledged by ‘done’. The data path computation can sometimes be ‘disregarded’ (depending on the ‘valid’–‘invalid’ inputs) and grant issued with a very low latency. This acceleration significantly reduces the overall arbitration delay when the number of active requests is low. The design clearly illustrates the power of self-timed design principle in systems where delays are data dependent. We believe that the method with explicit ‘valid’–‘invalid’ control can be extended to other applications involving data processing with asynchronously arriving data from multiple sources. One such application could be embedded microcontrollers.