WD - mattrighetti/leiserson-retiming GitHub Wiki
Given a synchronous circuit ,this algorithm computes
and
for all
such that u is connected to v in G.
- Weight each edge
in E with the ordered pair
- Using the weighting from step 1, compute the weight of the shortest path joining each connected pair of vertices by solving an all-pairs shortest-paths algorithm (Floyd-Warshall performs best in dense graphs)
- For each shortest-path weight
between two vertices u and v, set
and