Recursive Formulations for N Input Asynchronous First Come First Served Arbiters

A First Come First Served (FCFS) arbiter services requests in order of their arrival, thereby achieving fairness defined by a minimum variance of waiting times. For example, the performance of multiprocessor architectures depends on fair access to shared memory. This paper proposes a new asynchronous FCFS arbiter hardware design based on recursive formulations that result in efficient and fast implementations. Each pair of requests is ordered by a metastable robust mutual exclusion element (ME). When a request arrives before all others, the corresponding acknowledge is asserted. However, close arrivals can cause cycles such as when request 0 is deemed to arrive before 1 and 1 before 2 and 2 before 0. Dike and Ostler in 1992 resolve cycles using groups of 4 requests, known as an M4. One contribution of the current paper is the recursive formulations that lead to more efficient simpler logic than the M4 approach. For example, with N=4 requests, fewer than half the CMOS transistors are required. This recursive approach can still be expressed in logic with delay proportional to log(N). The allocation of cycles to each acknowledge can be configured and this is analysed for the new recursive approach. The paper also discusses the occurrence of hazards in FCFS resolution logic, due to multiple paths to each output. Monotonic resolution logic and a simple gated ME override structure allow removal of glitches and cycles with minimal performance impact.