Calculating All Condition Predicates

from FPGA Resources by GateForge Consulting Ltd.

In Hacker's Delight, Section 2-12, How the Computer Sets the Comparison Predicates, Henry S. Warren Jr. describes how to compute all the integer comparisons, based on the condition flags generated after a (2's-complement) subtraction x - y, which I reproduce below.

Given the following four condition flags after computing x - y:

We can compute all the integer comparisons like so:

ComparisonCalculationNotes
VCi ⊕ Cosigned overflow
x = y:Z
x ≠ y¬Z
x < yN ⊕ V
x ≤ y(N ⊕ V) ∨ Z
x > y(N ≡ V) ∧ ¬Z≡ means XNOR
x ≥ yN ≡ V
x < y¬Counsigned
x ≤ y¬Co ∨ Zunsigned
x > yCo ∧ ¬Zunsigned
x ≥ yCounsigned


It so happens that we can arrange the four basic conditions as two groups, A and B, where a Boolean combination of any pair with one member from from each group suffices to reconstruct all the integer comparisons:

So a pair of 2:1 multiplexers feeding into a Universal Dyadic Boolean Operator module is enough to recreate all of the comparisons, and a few more.

But in a modern FPGA, 4:1 multiplexers naturally map 1:1 onto 6-LUTs (6-input Look-Up Tables), so we can extend groups A and B to contain more kinds of conditions commonly encountered in software, which we can now check with programmable hardware: checks for sentinel values (e.g.: the string-terminating NULL), counters (e.g.: counted loops, software timers), and external inputs (e.g.: test an input pin). The external inputs also act as a generic place to add special conditions, or for chaining previous predicate calculations.

The groups now are:

where the Sentinel flags can take the place of the Z (Zero) condition. All conditions (except External ones) are set by the result of the previous instruction, denoted by the p subscript in some case (it's a convention in the diagrams, to distinguish from similar signals derived from the current instruction). The ALU provides the Co and N⊕V conditions. Another module can calculate Z and N.

Selecting from 4 inputs each requires 2 bits, plus 4 bits to select one of the 16 possible dyadic Boolean operations, resulting in 256 possible comparisons. There is some redundancy: 16 cases always output 0 or 1 so we keep 2 for use, and 32 cases always output the selected member from A or B so we keep 8 for use (one per input condition), leaving us with 202 non-redundant comparison predicates (CP).

It's interesting to think of the non-redundant fraction of the possible outputs of a logic circuit as a potential measure of its quality. (This one sits at 202/256 = 0.789.) Fewer redundant cases suggests a more "significant" computation.


To implement this condition predicate calculator, we first need to define the conditions and operations (which remain constant anywhere, and so by convention are created as macros rather than parameters).

`ifndef CONDITION_PREDICATE_OPERATIONS
`define CONDITION_PREDICATE_OPERATIONS

    // Never changes
    `define GROUP_SELECTOR_WIDTH    2

    // First, the A/B group condition flag selectors

    `define A_GROUP_NEGATIVE        2'd0
    `define A_GROUP_CARRYOUT        2'd1
    `define A_GROUP_SENTINEL        2'd2
    `define A_GROUP_EXTERNAL        2'd3

    `define B_GROUP_LESSTHAN        2'd0
    `define B_GROUP_COUNTER         2'd1
    `define B_GROUP_SENTINEL        2'd2
    `define B_GROUP_EXTERNAL        2'd3

    // Second, for the combining stage

    `include "Dyadic_Boolean_Operations.vh"

`endif

Then is it simply a matter of instantiating two Addressed Multiplexers and one Universal Dyadic Boolean Operator. The resulting circuit consumes only three 6-LUTs, making quite small and fast. You can implement multiple instances to compute multiple arbitrary comparison predicates in parallel.

// Computes a true/false value based on a Boolean combination of selected
// input conditional predicates, each selected from one of two groups.
// (See Hacker's Delight, 2-12)

`default_nettype none

module Condition_Predicate
(
    input   wire    [`GROUP_SELECTOR_WIDTH-1:0]     A_selector,
    input   wire                                    A_negative,
    input   wire                                    A_carryout,
    input   wire                                    A_sentinel,
    input   wire                                    A_external,

    input   wire    [`GROUP_SELECTOR_WIDTH-1:0]     B_selector,
    input   wire                                    B_lessthan,
    input   wire                                    B_counter,
    input   wire                                    B_sentinel,
    input   wire                                    B_external,

    input   wire    [`DYADIC_CTRL_WIDTH-1:0]        AB_operator,

    output  wire                                    predicate
);

// --------------------------------------------------------------------

    localparam WORD_WIDTH = 1; // Predicates are 1/0

// --------------------------------------------------------------------

    wire selected_A;

    Addressed_Mux
    #(
        .WORD_WIDTH     (WORD_WIDTH),
        .ADDR_WIDTH     (`GROUP_SELECTOR_WIDTH),
        .INPUT_COUNT    (2**`GROUP_SELECTOR_WIDTH)
    )
    Select_A
    (
        .addr           (A_selector),    
        .in             ({A_external,A_sentinel,A_carryout,A_negative}),
        .out            (selected_A)
    );

// --------------------------------------------------------------------

    wire selected_B;

    Addressed_Mux
    #(
        .WORD_WIDTH     (WORD_WIDTH),
        .ADDR_WIDTH     (`GROUP_SELECTOR_WIDTH),
        .INPUT_COUNT    (2**`GROUP_SELECTOR_WIDTH)
    )
    Select_B
    (
        .addr           (B_selector),    
        .in             ({B_external,B_sentinel,B_counter,B_lessthan}),
        .out            (selected_B)
    );

// --------------------------------------------------------------------

    Dyadic_Boolean_Operator
    #(
        .WORD_WIDTH     (WORD_WIDTH)
    )
    AB_Combiner
    (
        .op             (AB_operator),
        .a              (selected_A),
        .b              (selected_B),
        .o              (predicate)
    );

endmodule

fpgacpu.ca