A Better Priority Arbiter

by GateForge Consulting Ltd.

A priority arbiter is a useful building block, but the usual manual implementations using case statements or chains of assign statements are hard to follow, and must be manually adjusted each time the number of requestors changes. For reference, see Section 3 of Matt Weber's Arbiters: Design Ideas and Coding Styles, which is dated and very ASIC-centric, but contains useful diagrams and discussion.

A better description of a priority arbiter comes from Henry S. Warren Jr.'s Hacker's Delight, which describes many, many techniques using integer arithmetic extended with Boolean operations (and vice-versa) to create branch-free implementations of common and not-so-common operations. By being branch-free, these implementations map well to hardware, and by using integer arithmetic, provide a compact, clear way to express calculations across the bits of a word via the arithmetic carry bits.

In Chapter 2 ("Basics", available on his website), he shows how a subtraction followed by a bitwise AND isolates the right-most (Least Significant) bit set, or returns zero if none set. For example:

00000 --> 00000
01101 --> 00001
01100 --> 00100

If we take the bits, right-to-left, as requests of higest-to-lowest priority, we can use this simple operation to describe a priority arbiter. And since we express it as integer arithmetic and Booleans, it will map quite naturally to the adder carry-chain and LUT logic of an FPGA. The carry-chain provides a high-speed right-to-left connection between each bit in the word. Wrapping that one line of code into a module indicates its meaning, and allows trivial parameterization to any number of requestors.

// Simple priority arbiter.
// Returns the LSB set, where bit 0 has highest priority

module Priority_Arbiter
#(
    parameter       WORD_WIDTH          = 0
)
(
    input   wire    [WORD_WIDTH-1:0]    requests,
    output  reg     [WORD_WIDTH-1:0]    grant
);

    initial begin
        grant = 0;
    end

    always @(*) begin
        grant = requests & -requests;
    end

endmodule

fpgacpu.ca