About carries and tokens: re-using adder circuits for arbitration

Abstract

This paper explores the analogies among the carry propagation within binary adders and the token passing within arbiter implementations. This analysis identifies a common design space, thus decreasing the design costs and time by efficient re-use beyond individual application domains. The immediate utilization of available carry-propagation networks is outlined and justified. This, for instance, enables designers to choose directly from a large pool of well-studied parallel prefix networks. While these solutions are, due to their regularity, favorable for VLSI ASIC designs, they do usually not synthesize well on FPGAs. Extending the analogy between carry propagation and token passing to this domain, the appropriate utilization of carry chains commonly available on FPGAs is demonstrated to yield small and fast arbiters.