Cookbook

Comparing Values

Application

This automaton examines two sequential symbols and reports whether the first symbol is greater than or less than the second symbol.

The # symbol indicates the automaton should examine the next two symbols. Similarly, report output is generated on a trailing # symbol that not only triggers the output generation, but also simultaneously triggers the automaton to process another two-symbol input sequence.

ANML Construction (AP Workbench)


Comparing values

C Code

#include <micron/ap/ap_defs.h>
#include <micron/ap/ap_anml.h>

int main(int argc, char* argv[]) {
    ap_anml_t anml = NULL;
    ap_anml_network_t anml_net;
    struct ap_anml_element element = {0};
    ap_anml_element_ref_t s1, greater, less;
    ap_anml_element_ref_t L0, L1, L2, L3, L4, L5, L6, R0, R1, R2, R3, R4, R5, R6;

    // Initialize the automata network
    anml = AP_CreateAnml();
    AP_CreateAutomataNetwork(anml, &anml_net, "comparator_3_bit");

    // Build the network
    element.id = "s1";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "#";
    AP_AddAnmlElement(anml_net, &s1, &element);

    element.start = NO_START;
    element.match = 1;
    element.id = "greater";
    AP_AddAnmlElement(anml_net, &greater, &element);
    element.id = "less";
    AP_AddAnmlElement(anml_net, &less, &element);

    element.match = 0;
    element.id = "L0";
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &L0, &element);
    element.id = "L1";
    element.symbols = "b";
    AP_AddAnmlElement(anml_net, &L1, &element);
    element.id = "L2";
    element.symbols = "c";
    AP_AddAnmlElement(anml_net, &L2, &element);
    element.id = "L3";
    element.symbols = "d";
    AP_AddAnmlElement(anml_net, &L3, &element);
    element.id = "L4";
    element.symbols = "e";
    AP_AddAnmlElement(anml_net, &L4, &element);
    element.id = "L5";
    element.symbols = "f";
    AP_AddAnmlElement(anml_net, &L5, &element);
    element.id = "L6";
    element.symbols = "g";
    AP_AddAnmlElement(anml_net, &L6, &element);

    element.id = "R0";
    element.symbols = "[b-h]";
    AP_AddAnmlElement(anml_net, &R0, &element);
    element.id = "R1";
    element.symbols = "[c-h]";
    AP_AddAnmlElement(anml_net, &R1, &element);
    element.id = "R2";
    element.symbols = "[d-h]";
    AP_AddAnmlElement(anml_net, &R2, &element);
    element.id = "R3";
    element.symbols = "[e-h]";
    AP_AddAnmlElement(anml_net, &R3, &element);
    element.id = "R4";
    element.symbols = "[f-h]";
    AP_AddAnmlElement(anml_net, &R4, &element);
    element.id = "R5";
    element.symbols = "[g-h]";
    AP_AddAnmlElement(anml_net, &R5, &element);
    element.id = "R6";
    element.symbols = "h";
    AP_AddAnmlElement(anml_net, &R6, &element);

    AP_AddAnmlEdge(anml_net, s1, L0, 0);
    AP_AddAnmlEdge(anml_net, s1, L1, 0);
    AP_AddAnmlEdge(anml_net, s1, L2, 0);
    AP_AddAnmlEdge(anml_net, s1, L3, 0);
    AP_AddAnmlEdge(anml_net, s1, L4, 0);
    AP_AddAnmlEdge(anml_net, s1, L5, 0);
    AP_AddAnmlEdge(anml_net, s1, L6, 0);
    AP_AddAnmlEdge(anml_net, s1, R0, 0);
    AP_AddAnmlEdge(anml_net, s1, R1, 0);
    AP_AddAnmlEdge(anml_net, s1, R2, 0);
    AP_AddAnmlEdge(anml_net, s1, R3, 0);
    AP_AddAnmlEdge(anml_net, s1, R4, 0);
    AP_AddAnmlEdge(anml_net, s1, R5, 0);
    AP_AddAnmlEdge(anml_net, s1, R6, 0);

    AP_AddAnmlEdge(anml_net, L0, R0, 0);
    AP_AddAnmlEdge(anml_net, R0, L0, 0);
    AP_AddAnmlEdge(anml_net, L1, R1, 0);
    AP_AddAnmlEdge(anml_net, R1, L1, 0);
    AP_AddAnmlEdge(anml_net, L2, R2, 0);
    AP_AddAnmlEdge(anml_net, R2, L2, 0);
    AP_AddAnmlEdge(anml_net, L3, R3, 0);
    AP_AddAnmlEdge(anml_net, R3, L3, 0);
    AP_AddAnmlEdge(anml_net, L4, R4, 0);
    AP_AddAnmlEdge(anml_net, R4, L4, 0);
    AP_AddAnmlEdge(anml_net, L5, R5, 0);
    AP_AddAnmlEdge(anml_net, R5, L5, 0);
    AP_AddAnmlEdge(anml_net, L6, R6, 0);
    AP_AddAnmlEdge(anml_net, R6, L6, 0);

    AP_AddAnmlEdge(anml_net, L0, greater, 0);
    AP_AddAnmlEdge(anml_net, L1, greater, 0);
    AP_AddAnmlEdge(anml_net, L2, greater, 0);
    AP_AddAnmlEdge(anml_net, L3, greater, 0);
    AP_AddAnmlEdge(anml_net, L4, greater, 0);
    AP_AddAnmlEdge(anml_net, L5, greater, 0);
    AP_AddAnmlEdge(anml_net, L6, greater, 0);

    AP_AddAnmlEdge(anml_net, R0, less, 0);
    AP_AddAnmlEdge(anml_net, R1, less, 0);
    AP_AddAnmlEdge(anml_net, R2, less, 0);
    AP_AddAnmlEdge(anml_net, R3, less, 0);
    AP_AddAnmlEdge(anml_net, R4, less, 0);
    AP_AddAnmlEdge(anml_net, R5, less, 0);
    AP_AddAnmlEdge(anml_net, R6, less, 0);

    // Export the network to an ANML file
    AP_ExportAnml(anml_net, "comparator_3_bit.anml", "");

    // Clean up 
    AP_DestroyAnml(anml);
    return 0;
}

Python Code

from micronap.sdk import *

def main():
    # Initialize the automata network
    A = Anml()
    AN = A.CreateAutomataNetwork(anmlId='comparator_3_bit')

    # Build the network
    s1 = AN.AddSTE('#', startType=AnmlDefs.ALL_INPUT, anmlId='s1')
    greater = AN.AddSTE('#', match=True, anmlId='greater')
    less = AN.AddSTE('#', match=True, anmlId='less')

    L0 = AN.AddSTE('a', anmlId='L0')
    L1 = AN.AddSTE('b', anmlId='L1')
    L2 = AN.AddSTE('c', anmlId='L2')
    L3 = AN.AddSTE('d', anmlId='L3')
    L4 = AN.AddSTE('e', anmlId='L4')
    L5 = AN.AddSTE('f', anmlId='L5')
    L6 = AN.AddSTE('g', anmlId='L6')
    R0 = AN.AddSTE('[b-h]', anmlId='R0')
    R1 = AN.AddSTE('[c-h]', anmlId='R1')
    R2 = AN.AddSTE('[d-h]', anmlId='R2')
    R3 = AN.AddSTE('[e-h]', anmlId='R3')
    R4 = AN.AddSTE('[f-h]', anmlId='R4')
    R5 = AN.AddSTE('[g-h]', anmlId='R5')
    R6 = AN.AddSTE('h', anmlId='R6')

    AN.AddAnmlEdge(s1, L0, 0)
    AN.AddAnmlEdge(s1, L1, 0)
    AN.AddAnmlEdge(s1, L2, 0)
    AN.AddAnmlEdge(s1, L3, 0)
    AN.AddAnmlEdge(s1, L4, 0)
    AN.AddAnmlEdge(s1, L5, 0)
    AN.AddAnmlEdge(s1, L6, 0)
    AN.AddAnmlEdge(s1, R0, 0)
    AN.AddAnmlEdge(s1, R1, 0)
    AN.AddAnmlEdge(s1, R2, 0)
    AN.AddAnmlEdge(s1, R3, 0)
    AN.AddAnmlEdge(s1, R4, 0)
    AN.AddAnmlEdge(s1, R5, 0)
    AN.AddAnmlEdge(s1, R6, 0)

    AN.AddAnmlEdge(L0, R0, 0)
    AN.AddAnmlEdge(R0, L0, 0)
    AN.AddAnmlEdge(L1, R1, 0)
    AN.AddAnmlEdge(R1, L1, 0)
    AN.AddAnmlEdge(L2, R2, 0)
    AN.AddAnmlEdge(R2, L2, 0)
    AN.AddAnmlEdge(L3, R3, 0)
    AN.AddAnmlEdge(R3, L3, 0)
    AN.AddAnmlEdge(L4, R4, 0)
    AN.AddAnmlEdge(R4, L4, 0)
    AN.AddAnmlEdge(L5, R5, 0)
    AN.AddAnmlEdge(R5, L5, 0)
    AN.AddAnmlEdge(L6, R6, 0)
    AN.AddAnmlEdge(R6, L6, 0)

    AN.AddAnmlEdge(L0, greater, 0)
    AN.AddAnmlEdge(L1, greater, 0)
    AN.AddAnmlEdge(L2, greater, 0)
    AN.AddAnmlEdge(L3, greater, 0)
    AN.AddAnmlEdge(L4, greater, 0)
    AN.AddAnmlEdge(L5, greater, 0)
    AN.AddAnmlEdge(L6, greater, 0)

    AN.AddAnmlEdge(R0, less, 0)
    AN.AddAnmlEdge(R1, less, 0)
    AN.AddAnmlEdge(R2, less, 0)
    AN.AddAnmlEdge(R3, less, 0)
    AN.AddAnmlEdge(R4, less, 0)
    AN.AddAnmlEdge(R5, less, 0)
    AN.AddAnmlEdge(R6, less, 0)

    # Export the network to an ANML file
    AN.ExportAnml('comparator_3_bit.anml')

if __name__ == '__main__':
    main()

ANML Code

See Comparing Values.

Operation

This automaton determines whether one symbol in the input data stream is greater than or less than another symbol in the input stream.

For example, if the input #db# is provided to the automaton, the first symbol (#) would cause the top-most STE S1 to match, and this would activate both vertical chains of STEs running through the design (L0–L6 and R0–R6).

When the d symbol is seen, four STEs would match: L3, R2, R1, and R0. Each of these STEs would now activate the adjacent STE in the other vertical chain (L3 activates R3; R2, R1, and R0 activate L2, L1, and L0).

If the next symbol in the input data stream is greater than d, STE R3 will match, as it contains the set of symbols all of which are greater than d. All STEs on the right (in the AP Workbench example) are programmed this way; they all contain symbols ranges greater than the STEs directly across from them in the left vertical chain.

Similarly, if the next symbol in the input data stream is less than d, one of the three STEs L0, L1, or L2 will match. As explained in the previous paragraph, all STEs in the right vertical chain are programmed with symbol ranges greater than their corresponding STEs in the left chain. Therefore, if the automaton transitions from a right STE on the first symbol to a left STE on the second symbol, it can be determined the second symbol was less than the first symbol.

The final symbol # generates a report from either the greater or the lesser reporting STE. These STEs have been programmed to report the results of comparing the first symbol to the second symbol. If the first symbol is greater than the second symbol, the greater STE will report. If the first symbol is less than the second symbol, the lesser STE will report. If the two symbols are equal, the automaton will not report.

This automaton could be augmented further with STEs that indicate equality between the two symbols. An equal reporting STE would be needed, and a third vertical chain identical to the left chain could be inserted into the design. All left STEs would connect to the corresponding equal STEs in the new vertical column. And all of the new vertical column STEs would connect to the equal reporting STE.