CHASM

For state encoding, MINIMALIST uses CHASM (Coding for Hazard-free Asynchronous State Machines), the first exact method for input encoding of multiple-input change asynchronous machines. CHASM has many operating modes. One highlight is that its ``exact mode'' can be used to produce exactly optimum two-level output logic, over all critical race-free encodings, thus optimizing the key performance parameter for asynchronous networks (output latency). Its approximate mode also gives significant reductions in overall implementation cost.

CHASM, as reported in [8], loosely follows the flow of the KISS [#KISS##1###] method for input encoding of synchronous machines. Several significant modifications are required to handle asynchronous machines. There are three steps. First, symbolic hazard-free logic minimization is performed. Second, a set of encoding constraints is generated, which properly subsumes both the classic synchronous KISS (``face embedding'') optimality constraints as well as asynchronous critical race-free [31] constraints. The constraints are in the form of generalized dichotomies [31] (not face embedding constraints). Finally, the constraints are solved. For constraint solution, CHASM has two modes: (i) an exact mode, which uses DICHOT [26], and (ii) an approximate mode, using NOVA's [33] simulated annealing engine. The approximate mode, as in NOVA, attempts to solve as many constraints as possible, under the restriction of a fixed code length; it has the advantage that it may reduce next-state logic complexity.

For MINIMALIST, CHASM has been extended in several new ways.

First, CHASM is now being applied to implementations with fed-back outputs. Specifically, we have proven that CHASM requires no modification to properly encode implementations with fed-back outputs. A modified functional specification is provided as input, which simply identifies the primary outputs as fed-back inputs. The symbolic two-level logic minimizer then forms a symbolic cover on this new function.

Second, CHASM can now target three logic implementation styles: (i) multi-output (where outputs and next-state may share products), (ii) output-disjoint (where products are shared among outputs, but not between outputs and next-state), and (iii) single-output (where no product terms are shared between any output functions). The motivation is that the ``single-output style'' is most suitable for performance-optimal designs: each output is individually optimized. Note that, in asynchronous machines (unlike synchronous), output latency is often the key parameter to overall system performance in a network of interacting machines. The ``multi-output style'' is most suitable for area-optimal designs, since it uses maximal sharing of logic. Finally, the ``output-disjoint style'' is a balanced compromise.

For modes (ii) and (iii), a novel feature of CHASM is that it produces exactly optimum two-level output logic, over all critical race-free encodings. This result holds, because the optimal output-only state encoding problem is a true ``input encoding problem'', unlike the general optimal state encoding problem (which is an approximation).

Finally, CHASM targets two distinct cost functions: (i) product cardinality, and (ii) literal count, at the symbolic level. It does the latter by performing weighted unate covering during symbolic logic minimization. This technique is only a heuristic, however, because the literal count of the final binary cover can only be estimated. In practice, the heuristic nonetheless yields significant reduction in literal count.