Tree Arbiter With Nearest-Neighbour Scheduling (1997)

Author(s): Mitrani I, Yakovlev A

    Abstract: A tree arbiter designed to minimize the average delay between consecutive allocations of a contentious resource is described and evaluated. The idea is to divide the competing users into nested clusters corresponding to sub-trees of varying size, and to keep the resource within the smallest cluster currently containing requests. This design reduces the number of steps in the arbitration procedure and hence increases the overall throughput of requests. The performance of the new arbiter is analysed and is compared to that of an algorithm which maintains first-in-first-out order among requests. The trade-offs between the nearest-neighbour and FIFO designs are examined numerically over wide ranges of parameter values. It is shown that when the system becomes large and/or heavily loaded, the benefits of the nearest-neighbour arbiter become greater.

      • Series Title: Department of Computing Science Technical Report Series
      • Pages: 15
      • Institution: Department of Computing Science, University of Newcastle upon Tyne
      • Publication type: Report
      • Bibliographic status: Published

      Keywords: arbitration, asynchronous systems, conflict resolution, mutual exclusion, performance analysis, resource allocation, treee arbiter


      Professor Alex Yakovlev
      Professor of Computer System Design