print · source · login   

Circuits

Description

The logic synthesis workshops (LGSynth89, LGSynth91 and LGSynth93) provide 59 behavioural models for circuit synthesis, see [CDDB]. More background information can be found on [BACBL]. These models can be seen as Mealy machines, (in several ways). The models are given as kiss2 files which consist of a list of transitions. As an example we consider a transition "01-- s1 s2 0-". Here "01--" is the input bit vector, "s1", "s2" are the source, target states resp. and "0-" is the output bit vector. A dash "-" means "don't care". In this example all the bit vectors "0100", "0101", "0110" and "0111" will trigger the transition. For the output we can interpret the meaning of don't care bits in (at least) two ways:

  • Don't cares are observable. This means that "0-", "00" and "01" are three distinct values. This does not correspond to the physical behaviour of circuits.
  • Don't cares keep the output bit unchanged. In this semantics an initial output bit vector is assumed (all zeroes) and "0-" will either output "00" or "01" depending on the state of the output bit vector.

In both cases, the models are deterministic, possibly partial Mealy machines. We consider two ways of completing the models:

  • Self-loops. Whenever a transition is missing, remain in the same state and output "--" of correct length.
  • Sink-state. Whenever a transition is missing, go to a sink (or crash) state with output "--" of correct length.

In both cases we will obtain a deterministic, complete Mealy machine. We provide all 4 semantics (2*2 combinations of above). If two or more semantics give bisimilar results, we only use one of them in the benchmark suite.

These models are used as benchmarks in papers by Hierons and Turker (TODO: provide references). They choose a semantics with observable don't cares and self-loops (with a distinct null output instead of a don't care output).

TODO: create a table with the list.