Usage - mattrighetti/leiserson-retiming GitHub Wiki

Examples

OPT1 and OPT2

Create a simple DAG and run the algorithm on that.

import networkx as nx
from algorithms.retiming.strategies import opt1, opt2

graph = nx.DiGraph()
graph.add_nodes_from([
    (0, {'delay': 0}),
    (1, {'delay': 3}),
    (2, {'delay': 3}),
    (3, {'delay': 3}),
    (4, {'delay': 3}),
    (5, {'delay': 7}),
    (6, {'delay': 7}),
    (7, {'delay': 7})
])
graph.add_weighted_edges_from([(0, 1, 1.0),
                               (1, 2, 1.0),
                               (2, 3, 1.0),
                               (3, 4, 1.0),
                               (4, 5, 0.0),
                               (5, 6, 0.0),
                               (6, 7, 0.0),
                               (7, 0, 0.0),
                               (3, 5, 0.0),
                               (1, 7, 0.0),
                               (2, 6, 0.0)])

result_opt1 = opt1(graph)
result_opt2 = opt2(graph)

result_opt1 and result_opt2 are tuples that contain:

• At position 0 the minimum feasible clock found
• At position 1 the retiming values for each node to achieve a graph with that minimum clock

This is how they are going to look like for this example

(13.0, {0: 0.0, 1: -1.0, 2: -1.0, 3: -2.0, 4: -2.0, 5: -2.0, 6: -1.0, 7: 0.0})

If you already have W and D matrices you can pass it to the algorithms, by default they are set to None so that the algorithm will generate them as soon as it sees that they have not been passed

opt1(graph, W, D)
opt2(graph, W, D)

Algorithm CP

If we want to check which is the minimum clock period of a graph, we can do this

import networkx as nx
from algorithms.clock_period import cp

graph1 = nx.DiGraph()
graph1.add_nodes_from([
    (0, {'delay': 0}),
    (1, {'delay': 3}),
    (2, {'delay': 3}),
    (3, {'delay': 7})
])
graph1.add_weighted_edges_from([(0, 1, 2.0),
                                (1, 2, 0.0),
                                (1, 3, 0.0),
                                (2, 3, 0.0),
                                (3, 0, 0.0)])
result = cp(graph)
assert result == 13.0

FEAS Algorithm

If we want to see is there is a retiming to achieve a specific clock period we can use

import network as nx
from algorithms.binary_search.strategies import feas

graph1 = nx.DiGraph()
graph1.add_nodes_from([
    (0, {'delay': 0}),
    (1, {'delay': 3}),
    (2, {'delay': 3}),
    (3, {'delay': 7})
])
graph1.add_weighted_edges_from([(0, 1, 2.0),
                                (1, 2, 0.0),
                                (1, 3, 0.0),
                                (2, 3, 0.0),
                                (3, 0, 0.0)])

is_valid, retiming_dict, clock_period = feas(graph, 13)

WD Algorithm

W and D matrices calculation can be done by

import networkx as nx
from algorithms.wd import wd

graph1 = nx.DiGraph()
graph1.add_nodes_from([
    (0, {'delay': 0}),
    (1, {'delay': 3}),
    (2, {'delay': 3}),
    (3, {'delay': 7})
])
graph1.add_weighted_edges_from([(0, 1, 2.0),
                                (1, 2, 0.0),
                                (1, 3, 0.0),
                                (2, 3, 0.0),
                                (3, 0, 0.0)])

W, D = wd(graph)

Retiming

If we have retiming values and we want to create another graph with those values we can use this

import network as nx
from algorithms.common import apply_retiming

graph = nx.DiGraph()
graph.add_nodes_from([
    (0, {'delay': 0}),
    (1, {'delay': 3}),
    (2, {'delay': 3}),
    (3, {'delay': 3}),
    (4, {'delay': 3}),
    (5, {'delay': 7}),
    (6, {'delay': 7}),
    (7, {'delay': 7})
])
graph.add_weighted_edges_from([(0, 1, 1.0),
                               (1, 2, 1.0),
                               (2, 3, 1.0),
                               (3, 4, 1.0),
                               (4, 5, 0.0),
                               (5, 6, 0.0),
                               (6, 7, 0.0),
                               (7, 0, 0.0),
                               (3, 5, 0.0),
                               (1, 7, 0.0),
                               (2, 6, 0.0)])

graph = apply_retiming(graph, {0: 0.0, 1: -1.0, 2: -1.0, 3: -2.0, 4: -2.0, 5: -2.0, 6: -1.0, 7: 0.0})