Recursive formulations for n input asynchronous First Come First Served arbiters

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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.
Original languageEnglish
Title of host publication2020 26th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC)
EditorsAndreas Steininger, Matheus Moreira
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages8
ISBN (Electronic)9781728154954
ISBN (Print)9781728154961
Publication statusPublished - 2020
EventIEEE International Symposium on Asynchronous Circuits and Systems (ASYNC) 2020 - Snowbird, United States of America
Duration: 17 May 202020 May 2020
Conference number: 26th


ConferenceIEEE International Symposium on Asynchronous Circuits and Systems (ASYNC) 2020
Abbreviated titleASYNC 2020
Country/TerritoryUnited States of America
Internet address

Cite this