|
OptiMist (Optimise and Map) is a package of tools that optimise Signal
Transition Graph specifications and map them into asynchronous circuits.
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
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.
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 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
The OptiMist package optimises STG specifications and map them into
asynchronous circuits in 4 stages:
-
output exposure
-
detection of redundant places
-
elimination of redundant places
-
mapping of into circuit
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.
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.
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.
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
|
|
