State Minimization

MINIMALIST includes two new and very efficient algorithms for exact state minimization. In contrast, the 3D method uses a heuristic greedy minimization algorithm. Therefore, in this section, we will focus on a more direct comparison: the MINIMALIST exact algorithms and an earlier exact state minimization algorithm found in UCLOCK.

MINIMALIST improves significantly on UCLOCK's state minimization approach in two ways -- (i) by allowing outputs to be fed back as inputs, and (ii) by dramatically reducing run-time complexity.

MINIMALIST offers two new exact state minimization algorithms: 1) for implementations without fed-back outputs (loosely based on UCLOCK's method), and 2) for implementations with fed-back outputs. The latter is the first exact algorithm for state minimization that handles fed-back outputs. Thus, it supports two machine implementation styles. As mentioned earlier, fed-back outputs can dramatically reduce the implementation's logic complexity.³ In particular, their use allows merging certain states which would otherwise be incompatible. MINIMALIST makes use of this fact by relaxing UCLOCK's compatibility relation. In fact, several benchmark specifications collapse into a single state using the new relation, whereas UCLOCK's relation results in 2 or more states.

Second, MINIMALIST improves run-time by several orders of magnitude over the UCLOCK method. UCLOCK uses an expensive algorithm to generate maximal compatibles. In contrast, MINIMALIST uses a simple transformation which allows it to generate maximal compatibles using a fast unate prime generation algorithm instead. In addition, both UCLOCK and MINIMALIST (currently) approximate the binate covering step by a unate one followed by a closure check⁴. UCLOCK, however, employs Petrick's method to solve the unate problem, while MINIMALIST employs a state-of-the-art tool, MINCOV [#RUDELL-PHDTHESIS##1###]. The combination of these two algorithmic enhancements reduce the run-time of state minimization by two or more orders of magnitude. To date we have encountered only one specification for which state minimization requires more than a few seconds, whereas run-times of many minutes were common for UCLOCK. For such large specifications, both of MINIMALIST's algorithms also feature an approximate mode which further reduces run-time.