Tutorial: Window Optimization

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

---

Using the \p skeleton script

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).

---

Implementing the Algorithm

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>
#include <algorithms/synthesis/transformation_based_synthesis.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.

bool cheaper = ok && costs( new_part, *cf ) < costs( s, *cf );

Depending on whether the new circuit part is cheaper, either that circuit or the old sub-circuit is appended to the circuit circ.

  append_circuit( circ, cheaper ? new_part : s );

  pos = to;
}

Since no errors occurred, true is returned by the algorithm.

  return true;
}

---

Creating an Executable

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 );

print_statistics( std::cout, newcirc, statistics->get<double>( "runtime" ) );

// writes a circuit to the value of option --realname
if ( opts.is_write_realization_filename_set() )
{
  write_realization( newcirc, opts.write_realization_filename() );
}
...

---

Running the Test-case

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