Async.org.uk Logo

OptiMist


OptiMist (Optimise and Map) is a package of tools that optimise Signal Transition Graph specifications and map them into asynchronous circuits.

0. Table of content

1. Download

The latest release of the tools can be found on OptiMist homepage:

The author of the OptiMist package can be contacted by e-mail: danil (dot) sokolov (at) ncl (dot) ac (dot) uk

2. Installation

If you compile OptiMist from source, then in order to obtain binary executables as a non-root user do:


  $ make

This will compile six tools which form the OptiMist package: om_detect, om_expose, om_transform, om_verilog, om_library and om_graph.

These tools can ether be used individually or by means of optimist script. This script is already present in the source files directory. It connects all OptiMist tools in one command-line interface.

In order to start using the OptiMist tools copy them into a directory which is referenced from your PATH environment variable (e.g. /usr/local/bin/). This can be done by running the following command as root:


  $ make install

If you already have all executables then just put them into you a directory which is referenced from your PATH environment variable.

3. Usage of the tools

This section explains how to use the OptiMist toolkit for direst mapping of asynchronous circuits from STGs. The toolkit contains the following tools (see the design flow figure):
  • optimist - a wrapper script which is a front-end to the OptiMist tools;
  • om_detect - a tool for detection of redundant places;
  • om_expose - a tool for exposure of the outputs;
  • om_transform - a tool for elimination of redundant places;
  • om_verilog - a tool for mapping of the optimised specification into a circuit;
  • om_lib -generation of a library of required DCs and FFs either at transistor- or gate-level;
  • om_graph - a tool for visualisation of an STG with read-arcs extension and tracker-bouncer structure.
The usage of the tools is described in the following sections.
OptiMist design flow

OptiMist wrapper script

The easiest way to process an STG file is to give it as a parameter to the optimist script:


  $ optimist file.g

This script calles OptiMist tools with necessary command-line prameters and creates the following files:

file_3.g
STG where redundant places are detected using heuristics A, B and C
file_3e.g
STG where the detected redundant places are tagged and outputs are exposed
file_3et.g
STG from which redundant places are removed

By default the input STG is optimised using all heuristics. The minimum number of DC in a loop is set to 3. The maximum join transition fanin is limited by 2. This options can be overridden by using command-line parameters whose full list of is shown below:


  Usage: optimist [OPTIONS] INPUT_FILE_NAME
  OPTIONS:
  -l, --level[N]                  level of redundant places detection (N=0,1,2,[3])
        0 = all places are tagged as non-redundant
        1 = 0 + heuristic A is used to detect redundant places
        2 = 1 + heuristics B is applied to detect redundant places
        3 = 2 + heuristic C is applied to detect redundant places
        Heuristic A (latency reduction): Places after input transitions but
                before output transitions are tagged as redundant.
        Heuristic B (size reduction): The chains of places between redundant
                places which are detected by heuristic A are considered. The
                places of each chain are tagged starting from the beginning of
                the chain and going in the direction of consuming-producing
                arcs. The last place in each chain is skipped.
        Heuristic C (size reduction): All non-tagged places (which are the
                last places in the chains) are tagged individually.
  -r, --redundant PLACE_LIST      list of predefined redundant places []
  -s, --separator PLACE_LIST      list of predefined mandatory places []
  -n, --num-loop[N]               minimum number of DC in a loop (N=1,2,[3])
  -j, --join-fanin[N]             max join transitions fanin (N=[0],1,2,3)
        0 = no control on the join transitions fanin
        1-3 = restrict join transitions fanin to the given number,
        higher value for this parameter is not practical
  -v, --verilog                   map STG into Verilog netlist
  -i, --info                      include circuit statitstics into netlist
  -t, --test                      generate circuit ready for off-line testing
  -g, --graph                     draw STG in PostScript format
  -d, --debug                     print debug information
  -h, --help                      print this help

For example, the same file can be processed with the following command-line parameters:


  $ optimist -l2 -v -g file.g

or


  $ optimist --level2 --verilog --graph file.g

This command will produce the following set of files:

file_2.g
STG where redundant places are detected using heuristics A and B
file_2e.g
STG where the detected redundant places are tagged and outputs are exposed
file_2et.g
STG from which redundant places are removed
file_2et.v
Verilog netlist obtained by mapping the STG into DCs and FFs
file_2.ps
PostScript file for the STG where redundant places are detected using heuristics A and B
file_2e.ps
PostScript file for the STG where the detected redundant places are tagged and outputs are exposed
file_2et.ps
PostScript file for the STG from which redundant places are removed

The OptiMist tools can also be executed individually. It might be neccessary in order to get access to their really used command line parameters which are described in the followiin sections.

OptiMist tool for detection of redundant places


  Usage: om_detect [FLAGS] [IN_FILE_NAME]
  FILE OPTIONS:
  -o, --output OUT_FILE_NAME  output file [STDOUT]
  GENERAL OPTIONS:
  -l, --level[N]              level of redundant places detection (N=0,1,2,[3])
      0 = all places are tagged as non-redundant
      1 = 0 + heuristic A is used to detect redundant places
      2 = 1 + heuristics B is applied to detect redundant places
      3 = 2 + heuristic C is applied to detect redundant places
      Heuristic A (latency reduction): Places after input transitions but
          before output transitions are tagged as redundant.
      Heuristic B (size reduction): The chains of places between redundant
          places which are detected by heuristic A are considered. The places
          of each chain are tagged starting from the beginning of the chain
          and going in the direction of consuming-producing arcs. The last
          place in each chain is skipped.
      Heuristic C (size reduction): All non-tagged places (which are the last
          places in the chains) are tagged individually.
  -n, --num-loop[N]           minimum number of DC in a loop (N=1,2,[3])
  -f, --fork                  consider places after fork as mandatory
  -j, --join                  consider places after join as mandatory
  -c, --choice                consider choice places as mandatory
  -m, --merge                 consider merge places as mandatory
  -t, --token                 consider places marked with a token as mandatory
  -r, --redundant PLACE_LIST  list of predefined redundant places []
  -s, --separator PLACE_LIST  list of predefined mandatory places []
  INFORMATION OPTIONS:
  -d, --debug[N]              level of debug information (N=[0],1,2,3,4)
  -v, --version               print version and copyright
  -h, --help                  print this help

OptiMist tool for exposure of outputs


  Usage: om_expose [FLAGS] [IN_FILE_NAME]
  FILE OPTIONS:
  -o, --output OUT_FILE_NAME  output file [STDOUT]
  INFORMATION OPTIONS:
  -d, --debug[N]              level of debug information (N=[0],1,2,3,4)
  -v, --version               print version and copyright
  -h, --help                  print this help

OptiMist tool for elimination of redundant places


  Usage: om_transform [FLAGS] [IN_FILE_NAME]
  FILE OPTIONS:
  -o, --output OUT_FILE_NAME  output file [STDOUT]
  GENERAL OPTIONS:
  -l, --level[N]              level of transformation (N=0,1,2,3,4,[5])
      0 = remove transient arcs only
      1 = 0 + move initial marking to mandatory places
      2 = 1 + recalculate contect signals
      3 = 2 + eliminate redundant places
      4 = 3 + remove transient arcs, not connected places and transitions
      5 = 4 + simplify join transitions
  -j, --join-fanin[N]         max join transitions fanin (N=[0],1,2,3)
      0 = no control on the join transitions fanin
    1-3 = restrict join transitions fanin to the given number,
          higher value for this parameter is not practical
  INFORMATION OPTIONS:
  -d, --debug[N]              level of debug information (N=[0],1,2,3,4)
  -v, --version               print version and copyright
  -h, --help                  print this help

Optimist tool for mapping STG into Verilog netlist


  Usage: om_verilog [FLAGS] [IN_FILE_NAME]
  FILE OPTIONS:
  -o, --output OUT_FILE_NAME  output file [STDOUT]
  GENERAL OPTIONS:
  -t, --test                  generate circuit ready for online testing
  -s, --statistics            include statistic comments into Verilog netlist
  -dc,--david_cell            provide detail DC statistics
  -ff,--flip_flop             provide detail FF statistics
  -i, --input                 provide input signals statistics
  INFORMATION OPTIONS:
  -d, --debug[N]              level of debug information (N=[0],1,2,3,4)
  -v, --version               print version and copyright
  -h, --help                  print this help

OptiMist tool for generation of Verilog netlist for DCs and FFs


  Usage: om_lib [FLAGS] [ELEMENT_NAME]
  FILE OPTIONS:
  -o, --output OUT_FILE_NAME  output file [STDOUT]
  GENERAL OPTIONS:
  -f, --format[N]             format of the output data (N=0,1,2,[3])
      0 = check the validity of the element name
      1 = pins description
      2 = gate-level Verilog netlist
      3 = transistor-level Verilog netlist
  INFORMATION OPTIONS:
  -d, --debug[N]              level of debug information (N=[0],1,2,3,4)
  -v, --version               print version and copyright
  -h, --help                  print this help

OptiMist tool for drawing STG using GraphVis DOT format


  Usage: om_graph [FLAGS] [IN_FILE_NAME]
  FILE OPTIONS:
  -o, --output OUT_FILE_NAME  output file [STDOUT]
  GENERAL OPTIONS:
  -l, --legend                show legend
  -c, --connect               connect read-arcs to places
  -i, --inputs                show elementary cycles for inputs
  INFORMATION OPTIONS:
  -d, --debug[N]              level of debug information (N=[0],1,2,3,4)
  -v, --version               print version and copyright
  -h, --help                  print this help

4. Summary of the Method

The OptiMist package optimises STG specifications and map them into asynchronous circuits in 4 stages:

  1. output exposure
  2. detection of redundant places
  3. elimination of redundant places
  4. mapping of into circuit

4.1. Output exposure

At this stage the initially closed (with both input and output transitions) system specification is transferred into an open system specification using the concept of environment tracking and output exposure [1]. The resultant specification consists of two blocks: a tracker and a bouncer. The tracker follows the behaviour of the environment and generates context signals for the bouncer. The bouncer is a set of elementary cycles, each of which represents an output signal. An elementary cycle consists of two places, corresponding to low and high levels of the signal, and positive and negative transitions of the signal. The elementary cycle switches between low and high states using a signal from the tracker.

4.2. Detection of redundant places

When outputs are exposed some places in the tracker become redundant, because an output can be switched by directly preceding input signal without using intermediate state of the tracker. Many tracker places can thus be removed, provided that the system behaviour is preserved w.r.t. input-output interface (weak bisimulation). Their elimination is however restricted by potential coding conflicts (which may cause tracker errors) and implementation constraints (at least three DCs in every loop). Redundant places are detected using a set of optimisation heuristics [2,3,4]. Initially all places are not tagged. Then every place is given a tag: redundant (if the place can be removed) or mandatory (if the place is necessary). The heuristics define the order in which the places should be checked.

Heuristic A (latency reduction):
Places after input but before output transitions are tagged as redundant.

Heuristic B (size reduction):
The chains of places between redundant places detected in the previous heuristic are considered. The places of each chain are tagged starting from the beginning of the chain and going in the direction of consuming arcs. The last place in each chain is not tagged.
Heuristic C (size reduction):
All non-tagged places (the last places in the chains) are tagged individually.

4.3. Elimination of redundant places

At this stage redundant places are removed from the tracker one by one. After a removal of each place the specification is modified preserving the behaviour of the system. If a place has only one preceding transition and one succeeding transition then the modification is trivial (the place is deleted and the conjugate transitions are replaced by one). In case of more then one preceding or succeeding transitions, more sophisticated transformation is required for place removal.

Sometimes the number of context signals (signals from tracker) for an elementary cycle is increasing after removal of a redundant place. This can be explained by the splitting of a mandatory place before the deep hierarchy of forks and the recalculation of context signals from redundant places to the split places. The solution to this problem is to evaluate the complexity of elements by calculating the maximum number of incoming arcs into a transition before and after removal of every place. If this number is increasing (or at least is increasing beyond the maximum implementable value), then the place should be kept in the specification. This is the element complexity optimisation technique which reduces the size of the circuit by preventing complication of logic rather than reducing the number of state holding elements.

4.4. Mapping into circuit

Finally, the places of the tracker are mapped into David Cells (DCs) and the elementary cycles are mapped into set-reset flip-flops (FFs). The netlist of DCs and FFs is generated in Verilog format.

5. Advantages

  • Generated circuits have low output latency.
  • All optimisation is performed at the specification level as opposed to optimisation of logic circuits after the stage of synthesis.
  • Tool can process large specifications (which are not computable by logic synthesis tools in acceptable time), because optimisation is performed locally and the computation time grows almost linear with the size of specification.
  • The tools are extremely fast, which allows the designer to try different combinations of heuristics and different start points of optimisation.
  • The element complexity optimisation facilitates technology mapping by restricting the growth of logic element fanin.
  • The tools are fully automated. At the same time a designer can significantly influence on the result at the stage of redundant place detection by choosing one or more of the proposed heuristics.
  • OptiMist package can be employed in combination with Cadence to allow simulation and technology mapping of circuits. A basic library of DCs and FFs has been created for Cadence. It can be expanded, if necessary, using a tool from the package which generates a Verilog implementing DCs and FFs at transistor level.

6. ToDo list

  • To improve the algorithm of redundant place detection to avoid growth of DCs/FFs fanins.
  • To try several start points in redundant place detection procedure and automatically select the best result.

7. References

  1. A.Bystrov and A.Yakovlev, "Asynchronous circuit synthesis by direct mapping: Interfacing to environment", In Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, pages 127-136, Manchester, UK, April 2002.
  2. D.Sokolov, A.Bystrov and A.Yakovlev, "Automated design of low-latency asynchronous circuits by direct mapping", Postgraduate Research Conference in Electronics, Photonics, Communications and Software, Notingham, UK, April 2002.
  3. D.Sokolov, A.Bystrov and A.Yakovlev, "Tools for STG optimisation in the direct mapping of asynchronous circuits", 12th UK Asynchronous Forum, London, UK, June 2002.
  4. D.Sokolov, A.Bystrov and A.Yakovlev, "STG optimisation in the direct mapping of asynchronous circuits", In Proc. of Design Automation and Test in Europe, pages 932-937, Munich, Mart 2003.

Last modified 30/8/2005 by IGC