Algorithms¶

algos.cp(g, return_delta=False)¶

Compute the clock period of a synchronous circuit.

Time complexity	$O(E)$
Space complexity	$O(V + E)$

Parameters

g – A NetworkX (Multi)DiGraph representing a synchronous circuit.
return_delta – Whether to return the computed $\Delta$ or not (used in other algorithms).

Returns

The clock period of the given circuit.

algos.feas(g, c)¶

Given a synchronous circuit $G$ and a desired clock period $c$ , this algorithm produces a retiming $r$ of $G$ such that $G_r$ is a synchronous circuit with clock period not greater than $c$ , if such retiming exists.

Time complexity	$O(VE)$
Space complexity	$O(V + E)$

Parameters

g – A NetworkX (Multi)DiGraph representing a synchronous circuit.
c – The desired clock period.

Returns

The retiming function or None if c is not feasible.

algos.opt1(g, show_wd=False)¶

Given a synchronous circuit $G$ , this algorithm determines a retiming $r$ such that the clock period of $G_r$ is as small as possible.

Time complexity	$O(V^3 \log V)$
Space complexity	$O(V^2)$

Parameters

g – A NetworkX (Multi)DiGraph representing a synchronous circuit.
show_wd – Print matrices W and D.

Returns

The retimed graph having the smallest possible clock period.

algos.opt2(g, show_wd=False)¶

Given a synchronous circuit $G$ , this algorithm determines a retiming $r$ such that the clock period of $G_r$ is as smallas possible.

Time complexity	$O(VE \log V)$
Space complexity	$O(V^2)$

Parameters

g – A NetworkX (Multi)DiGraph representing a synchronous circuit.
show_wd – Print matrices W and D.

Returns

The retimed graph having the smallest possible clock period.

algos.retime(g, r)¶

Compute the retimed graph.

Parameters

g – A NetworkX (Multi)DiGraph representing a synchronous circuit.
r – The retiming function $r: V \mapsto Z$ to be applied.

Returns

The retimed graph.

algos.wd(g, show=False)¶

Given a synchronous circuit $G$ , this algorithm computes $W(u, v)$ and $D(u, v)$ for all $u,v \in V$ such that $u$ is connected to $v$ in $G$ .

Time complexity	$O(V^3)$
Space complexity	$O(V^2)$

Parameters

g – A NetworkX (Multi)DiGraph representing a synchronous circuit.
show – Print the matrices.

Returns

Matrices W and D in the form dict<(u,v), int>.