40 Years of Computing at Newcastle

Department Technical Report Series No. 563

Tree Arbiter with Nearest-Neighbour Scheduling.

I. Mitrani and A. Yakovlev

University of Newcastle upon Tyne. 1997.

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.

Department Technical Report Series - 1997
Department Technical Report Series Index
Contents Page - 40 Years of Computing at Newcastle

Technical Report Abstract No. 563, 30 June 1997