MINIMALIST addresses the class of asynchronous controller specifications known as burst-mode, a generalization of the traditional multiple-input change (MIC) mode [32]. Burst-mode was first formalized by Nowick [18], who also developed UCLOCK, a systematic synthesis method for hazard-free implementations. This specification style is based on more ad-hoc methods used earlier by Davis et al.. [5].
Burst-mode machines allow multiple inputs to change concurrently, but, unlike MIC machines, in any order and at any time. This relaxation considerably reduces the timing constraints placed on the environment, but nonetheless allows economical and high-performance implementations. In particular, applying Nowick's method for exact two-level hazard-free logic minimization [21] yields low-area, high-performance circuits.
Burst-mode has been successfully used by both academia and commercial interests to design and implement a number of significant circuits, for example, at Stanford, UCSD, HP, AMD and Intel.
The specifications are most easily illustrated by example. A burst-mode specification for a distributed mutual-exclusion controller with 3 inputs and 3 outputs is shown in Figure 1. The unique starting state (S0) is indicated by a 'v', and initial input and output values are either explicitly specified or (as in the figure) default to 0. Each arc is labelled with a set of input and output transitions, known as bursts, separated by a '/'. Rising transitions are denoted by a '+'; falling transitions, by a '-'.
The operation of a burst-mode machine is as follows. Starting in a given state, the machine remains stable in that state until a complete input burst arrives. Individual inputs within that burst may arrive in any order and at any time. Once the last input arrives, the burst is complete. The machine then generates the corresponding output burst, if any, and moves to the specified next state. The environment allows the machine to settle, and the next cycle begins.
Figure 1 illustrates burst-mode operation. For example, consider the transition from S2 to S0, with corresponding input and output bursts LIN-,RIN- and LOUT-, respectively. As a result, when in S2, if the pair of input changes LIN- and RIN- arrive at any order, and within any time window, the machine responds with a falling edge on LOUT and a transition to S0.
Burst-mode specifications must obey two important restrictions. First, input bursts must not be empty; in the absence of input changes, the machine remains stable in its current state. Second, the so-called maximal set property stipulates that no arc leaving a given state may possess an input burst that is a subset of any other arc leaving that state. This property guarantees that, at all times, the machine can unambiguously decide whether to follow a transition or remain stable.
It is important to understand that, in a given burst-mode specification, any unspecified input combinations are forbidden. For example, the input burst RIN+ in state S0 in the specification of Figure 1 is prohibited. In other words, the surrounding circuitry must never generate that input combination. Any such combinations can thus be treated as don't-cares, and used to optimize the machine's implementation.
It is also conventional to adhere to a simple constraint, in order to ensure that the burst-mode specification can be properly synthesized1. Each state must have a unique entry point, i.e., a unique set of input and output values upon entry. In other words, each state has a single total state that is the destination of one or more transitions. Note that this property is not necessary for proper burst-mode operation. However, it tends to produce machines which are more easily minimized, and which are more easily proven to have hazard-free implementations.
An equivalent textual burst-mode specification (as used by MINIMALIST and MEAT [4]) appears in Figure 2, and an equivalent flow table in Figure 3.
It is easy to see from Figure 3 that burst-mode specifications frequently offer significant opportunity for state minimization. This due to the unique entry point criterion, which generally results in states which bind the output and next-state functions in only a few input columns.
