Asynchronous controller synthesis follows a flow similar to that of synchronous synthesis; however, it presents unique problems requiring significantly different solution methods. Like synchronous synthesis, the synthesis trajectory is divided for tractability's sake into several steps: state minimization, state encoding, two-level logic minimization, multi-level transformation, synthesis for testability, and so on. Each of these steps can be modeled roughly after its synchronous counterpart, but poses additional complications. We now review each step, outlining the basic problems unique to asynchronous synthesis.
The task of state minimization is to find a minimum-cardinality closed state cover for the original burst-mode specification. The result is a reduced machine realizing the original specification [10]. As with synchronous machines, this problem can be solved by first forming a set of compatibles and then forming a binate covering problem expressing the two basic sets of constraints (coverage and closure) [9]. Asynchronous machines, however, require different forms of compatible in order to be assured of the existence of a hazard-free logic implementation [19].
State encoding produces a set of binary codes for the symbolic states of the reduced machine. For synchronous machines, all encodings which distinguish the states are valid; however, typically this is performed judiciously, so as to minimize logic area [6], improve performance, or reduce power consumption. By contrast, asynchronous machines must be encoded so as to avoid critical races [31]. Further, if optimal logic is to be obtained, logic hazards [32][20] must be taken into account [8].
Finally, to ensure correct operation, two-level logic minimization for burst-mode asynchronous machines must also take care to avoid logic hazards. Recent developments in this area include exact multi-valued-input (i.e., mvi)/multi-output minimization [8], fast heuristic minimization [29], and exact implicit minimization [30].
An additional issue facing asynchronous synthesis is the potential for using fed-back outputs to reduce the number of state variables and the overall implementation complexity. In this machine implementation style, primary outputs are fed back as additional input variables, which help to identify the machine's present state, thereby reducing the need for distinct state variables. The loading on the outputs may be minimal (only a short path to a feedback buffer is added to its fan-out), but the savings in overall logic complexity can be dramatic. Care must be taken, however, in various synthesis steps, in order to ensure that the use of fed-back outputs does not introduce hazards or critical races.