Tutorial: Window Optimization

On this page a tutorial about how to add a new algorithm to the library is given. As example, a simple version of the window optimization algorithm is used. Therefore, a sub-circuit of the given circuit with a predefined size (a so called window) is extracted. Afterwards, this window is re-synthesized. If the resulting circuit is smaller, then the original sub-circuit is replaced with it. Therefore, different cost functions are applied.

This tutorial examines the following topics:

- Adding a new algorithm using the
`skeleton`

script - Functors to support different synthesis algorithms for the re-synthesis step
- Cost functions
- How to measure the execution time of the algorithm
- Sub-circuits to extract the windows

The `helpers`

directory provide a script called `skeleton`

, which can be used to create a basic skeleton for a new algorithm. The corresponding files are automatically generated in the `unstable`

directory of the toolkit. In order to generate a skeleton for the desired window optimization approach, the following values should be entered after invoking the script.

$ helpers/skeleton window_optimization

Please specify a type of the algorithm:

1: Truth Table Based Synthesis

2: PLA/BLIF Based Synthesis

3: Embedding

4: Decomposition

5: Simulation

6: Optimization

0: Custom

Your choice [0-6]: 6

Author for documentation [username]: John Example

Brief documentation for algorithm: Simple Window Optimization

Long documentation for algorithm: Algorithm implements a window optimization approach

Settings variable (empty string to stop): unsigned window_length=5u

Settings variable (empty string to stop): truth_table_synthesis_func synthesis=transformation_based_synthesis_func()

Settings variable (empty string to stop): cost_function::ptr cf=cost_function::ptr( new gate_costs() )

Settings variable (empty string to stop):

This creates a skeleton for the algorithm, i.e. two files unstable/optimization/window_optimization.hpp and unstable/optimization/window_optimization.cpp. The directory `optimization`

is automatically determined from the choice 6 at type of algorithm. Three options were added to the settings:

**window_length:**The length of the windows to be extracted (default value 5u; note the`u`

suffix, since it is an`unsigned`

variable)**synthesis:**The synthesis algorithm to be used for re-synthesizing the windows (The default value is the transformation_based_synthesis functor)**cf:**The cost-function to be useed for deciding whether the newly generated sub-circuit is cheaper or not (the default value is the gate_costs cost function)

The information what data type to create and what are the necessary parameters is also determined from the algorithm type (here 6).

At first, we add the includes needed for the implementation of the algorithm. It becomes more clear when describing the algorithm implementation, where the corresponding functions are needed. Some are needed because we have corresponding setting parameters.

// unstable/optimization/window_optimization.cpp

#include "window_optimization.hpp"

#include <core/functor.hpp>

#include <core/functions/add_circuit.hpp>

#include <core/functions/circuit_to_truth_table.hpp>

#include <core/functions/copy_metadata.hpp>

#include <core/utils/costs.hpp>

#include <core/utils/timer.hpp>

#include <algorithms/simulation/simple_simulation.hpp>

namespace revkit

{

...

Note that it is not optimal to include the simple_simulation in the algorithm. It is needed for the re-synthesize step, but forces a strong dependency to the algorithms. The better solution would be to offer a simulation functor to the settings struct.

Now, we can focus on the actual implementation. The parsing of the properties into local variables and time measurement code has already been generated by the skeleton script together with an entry point to start with the implementation.

// unstable/optimization/window_optimization.cpp

...

bool window_optimization( circuit& circ, const circuit& base, properties::ptr settings, properties::ptr statistics )

{

// Settings parsing

unsigned window_length = get<unsigned>( settings, "window_length", 12u );

truth_table_synthesis_func synthesis = get<truth_table_synthesis_func>( settings, "synthesis", transformation_based_synthesis_func() );

cost_function::ptr cf = get<cost_function::ptr>( settings, "cf", cost_function::ptr( new gate_costs() ) );

// Run-time measuring

timer<properties_timer> t;

if ( statistics )

{

properties_timer rt( statistics );

t.start( rt );

}

// TODO insert your code here...

First, the meta-data of the `base`

circuit is copied to the circuit `circ`

, which should be created by this algorithm.

copy_metadata( base, circ );

The variable `pos`

keeps track of the position in the `base`

circuit, from where the window should be extracted.

unsigned pos = 0u;

As long as the end of the `base`

circuit is not reached...

while ( pos < base.num_gates() )

{

... sub-circuits are extracted. Therefore, the `length`

of the window is determined. If there are enough gates left, `window_length`

is used for this purpose. Otherwise, only the remaining gates are considered. Having the length, the variable `to`

stores the right-hand side position of the considered sub-circuit.

unsigned length = std::min( window_length, base.num_gates() - pos );

unsigned to = pos + length;

With that information a sub-circuit can be extracted.

subcircuit s( base, pos, to );

From that sub-circuit its corresponding truth table is extracted. Therefore, a simulation engine and the function circuit_to_truth_table is applied.

binary_truth_table spec;

circuit_to_truth_table( s, spec, simple_simulation_func() );

Using this truth table, the sub-circuit is re-synthesized. Therefore, the synthesis approach given by the functor (parsed from the settings above) is applied. The success value of the synthesis algorithm is stored in the variable `ok`

.

circuit new_part;

bool ok = synthesis( new_part, spec );

Afterwards it is checked, if the newly synthesized circuit is cheaper. This is the case if the synthesis was successful and if the resulting circuit is cheaper than the original with respect to the given cost function.

Depending on whether the new circuit `part`

is cheaper, either that circuit or the old sub-circuit is appended to the circuit `circ`

.

Since no errors occurred, `true`

is returned by the algorithm.

return true;

}

The `helpers`

directory also provides a script in order to generate an executable of an implemented approach (called `testcase`

). Such an executable can be used e.g. to test a newly implemented approach without binding it to the Python library. As the `skeleton`

script above, the `testcase`

script is interactive and basically generates a skeleton for a `main`

function as well as for program options. If desired, it also integrates the resulting approach (as test case) into the build environment.

After invoking the script, first the parameters to be used have to be chosen. In the example, parameters denoting the original circuit realization (to be optimized), the final circuit (where the result is stored), and the cost function, respectively, is selected. Afterwards, a default value for the window length is added.

$ helpers/testcase test_wo

Use program options for parsing arguments? [y]: y

What parameter should be added? (Option [1] and [2] cannot be used together)

[u] User defined parameter

[1] RevLib *.real (circuit realization) file-name to parse from

[2] RevLib *.spec (specification) file-name to parse from

[3] RevLib *.real (circuit realization) file-name to write to

[4] Cost-function

[e] No more paremeter

Your choice [e]: 1

What parameter should be added? (Option [1] and [2] cannot be used together)

[u] User defined parameter

[1] RevLib *.real (circuit realization) file-name to parse from

[2] RevLib *.spec (specification) file-name to parse from

[3] RevLib *.real (circuit realization) file-name to write to

[4] Cost-function

[e] No more paremeter

Your choice [e]: 3

What parameter should be added? (Option [1] and [2] cannot be used together)

[u] User defined parameter

[1] RevLib *.real (circuit realization) file-name to parse from

[2] RevLib *.spec (specification) file-name to parse from

[3] RevLib *.real (circuit realization) file-name to write to

[4] Cost-function

[e] No more paremeter

Your choice [e]: 4

What parameter should be added? (Option [1] and [2] cannot be used together)

[u] User defined parameter

[1] RevLib *.real (circuit realization) file-name to parse from

[2] RevLib *.spec (specification) file-name to parse from

[3] RevLib *.real (circuit realization) file-name to write to

[4] Cost-function

[e] No more paremeter

Your choice [e]: u

User defined parameter:

Parameter/Variable Name: window_length

Type [std::string]: unsigned

Default Value (empty if no default value): 10u

Description: Window length of the sub-circuits to consider

What parameter should be added? (Option [1] and [2] cannot be used together)

[u] User defined parameter

[1] RevLib *.real (circuit realization) file-name to parse from

[2] RevLib *.spec (specification) file-name to parse from

[3] RevLib *.real (circuit realization) file-name to write to

[4] Cost-function

[e] No more paremeter

Your choice [e]: e

Source file examples/test_wo.cpp created.

Added compile command to examples/CMakeLists.txt.

Doing that, a file `examples/test_wo.cpp`

is created. Into this file, some includes statements needed to implement the test case are added (highlighted by an additional comment below).

// examples/test_wo.cpp

#include <iostream>

#include <core/circuit.hpp>

#include <core/io/print_statistics.hpp> // added

#include <core/io/read_realization.hpp>

#include <core/io/write_realization.hpp>

#include <core/utils/costs.hpp>

#include <core/utils/program_options.hpp>

#include <algorithms/synthesis/transformation_based_synthesis.hpp> // added

#include <unstable/optimization/window_optimization.hpp> // added

using namespace revkit;

int main( int argc, char ** argv )

...

Now, we can focus on the implementation of the test case. We create a new empty circuit `newcirc`

, which should be generated by the window optimization algorithm. Therefore, the settings given by the parameters are set. After invoking the optimization approach, statistics about the newly created circuit as well as the run-time are printed out. Finally, the code generated by the script for writing the circuit realization is modified.. Instead of circuit `todo`

the circuit `newcirc`

should be written.

// examples/test_wo.cpp

// TODO insert your code here...

circuit newcirc;

properties::ptr settings( new properties() );

settings->set( "window_length", window_length );

settings->set( "synthesis", transformation_based_synthesis_func() );

settings->set( "cf", opts.costs() );

properties::ptr statistics( new properties() );

unstable::window_optimization( newcirc, circ, settings, statistics );

// writes a circuit to the value of option --realname

if ( opts.is_write_realization_filename_set() )

{

write_realization( newcirc, opts.write_realization_filename() );

}

...

After re-building RevKit (make sure to build it with *-DBUILD_UNSTABLE=ON* and *-DBUILD_EXAMPLES=ON*) you can find the executable in `./build/examples/test_wo `

Generated on Tue Apr 16 2013 08:12:02 for RevKit by 1.8.3.1