Skip to content
ES
2015—2022 Archived

Reduct computation: from the algorithm to the FPGA

Doctoral work on an NP-hard combinatorial problem, attacked simultaneously in algorithm design and in hardware.

Block diagram of the Candidate Generator module: the super-reduct and contributes inputs feeding a selector, three blocks E1A, E2A and A whose outputs reach three multiplexers, registers holding the current candidate, the previous candidate and J, and a comparator against all-zeros that raises the done signal.
Figure 4.5 of the thesis, hardware architecture chapter: the module that generates the next candidate. The search order is wired, not interpreted — which is the whole reason the computation moves to an FPGA.
Line chart of runtime in seconds against the mean density of 1's, from 0.22 to 0.78, with a standard-deviation bar on every point. The three curves rise to a peak and fall to near zero by 0.70. fast-BR peaks highest, around 200 s near 0.26; fast-CT-EXT around 145 s near 0.34; GCreduct lowest, around 105 s near 0.34. GCreduct runs below both of the others up to about 0.36, past which fast-BR becomes the fastest of the three, and GCreduct stays below fast-CT-EXT across the whole range.
Figure 5.1 of the thesis, chapter 5, page 61: average runtime over 500 randomly generated basic matrices of 2000 rows and 30 columns, grouped into 15 density bins of about 33 matrices each; the bars are the standard deviation within each bin. Java implementations — the authors' own for fast-CT-EXT and fast-BR — timed on an Intel Core i7-5820K at 3.30 GHz with 32 GB of RAM under GNU/Linux. The result is the rule the chapter closes on: GCreduct is the fastest below a density of 0.36, fast-BR between 0.36 and 0.66, and above that the choice stops mattering. The legend spells it CGreduct, which is an error in the thesis figure itself; it is reproduced as defended rather than repainted here.

The problem. Computing all reducts of a decision system — the minimal attribute subsets that preserve its discernibility — is NP-hard. The naive approach enumerates the power set, and the cost is not something you optimise your way out of with better code.

Two fronts at once. On the algorithmic side, GCreduct prunes the search space using gap elimination and attribute contribution; MinReduct computes all the shortest reducts without enumerating the rest. On the hardware side, a co-designed FPGA platform accelerates the computation of irreducible testors.

Why it still matters here. It is the same instinct that produced everything else on this page: when a computation is expensive, the answer is rarely a bigger machine. It is a better algorithm, the right place to run it, and the willingness to design both.