Our MAG implementation was extended beyond the 12-bit
range (imposed by Dempster and Macleod for physical
RAM constraints) using the generic graph extension cases
illustrated in [11]. Also, we noted the potential for greater
differentiation between the multiple graphs found by MAG
for each integer value in range. Instead of using one level
of differentiation with the single-bit full adder count metric
described in [11], we implemented two metric levels
(primary and secondary) to allow one ‘best graph’ to be
selected. For each integer, the primary metric selects the
subset of graphs with minimum logic depth and from that
subset, the secondary metric selects the graph with lowest
vertice sum to minimise bit-widths. These new metrics
reflect the low FPGA area observations described previously
and, in general, leave only one best graph per integer,
whereas the sole ‘single-bit full adder’ metric selects
multiple graphs from which an arbitrary choice must be
made. Note that up to and including adder cost 3, for each
integer in range, the modified MAG implementation stores
and allows extension/branching from every graph found.
This allows full searching of the graph space up to and
including cost 4. From cost 4 graphs upwards (i.e. beyond
12-bits), only one ‘best graph’ (as selected by the new
primary/secondary metric system described previously) is
stored and used per integer for extending to higher cost
graphs. This restriction is for practical implementation
concerns of available physicalRAMand algorithm run-time.