Module cycle_ratio 

The maximum cycle ratio of a weighted digraph, exact and certified: the bound a loop puts on a clock period.

In a circuit’s retiming graph (Leiserson & Saxe, Retiming synchronous circuitry, 1991) an edge carries the combinational delay of its source and the registers on it. A cycle of total delay D through R registers cannot run faster than D / R a clock, however the registers are moved, because retiming keeps every cycle’s register count; so the largest D / R over every cycle is the period floor no retiming or pipelining of the loop’s own logic can beat, and the cycle reaching it names the loop to re-architect. A cycle of no register is a combinational loop and has no period at all.

max_cycle_ratio splits the graph into strongly connected components, since every cycle lies in one, and runs Howard’s policy iteration on each (Cochet-Terrasson, Cohen, Gaubert, Mc Gettrick & Quadrat, Numerical computation of spectral elements in max-plus algebra, 1998), the fastest method in practice (Dasdan, Experimental analysis of the fastest optimum cycle ratio and mean algorithms, 2004). A policy picks one edge out of every node; its cycles have exact ratios p/q in lowest terms, and each node takes the ratio of the cycle its policy path reaches and a bias x with x(u) = q·delay − p·registers + x(v) along its edge. A node switches to an edge reaching a larger ratio, or, when none does, to an edge of the same ratio and a larger q·delay − p·registers + x(v); when no node can switch, every node of the component has the component’s largest ratio. All of it is integer arithmetic.

The largest ratio D/R over the components is the bound, and a longest-path pass over the integer weights R·delay − D·registers, which no cycle makes positive, gives a potential π with π(to) ≥ π(from) + R·delay − D·registers on every edge. Summed around any cycle that says no cycle’s ratio exceeds D/R, and the cycle found reaches it: the Bound::Ratio is that cycle and that potential, and check replays both in exact integer arithmetic, trusting nothing the search did.

Every delay and register count is below LIMIT and a graph has at most NODES nodes, so every sum and product the search and the checker form fits i128 exactly.

Structs

Edge

An edge of the graph: delay of combinational logic and registers on it, both counts.

Enums

Bound

What bounds the period.

GraphError

Why a graph has no bound computed.

Constants

LIMIT

The bound on an edge’s delay and register count.

NODES

The bound on the node count.

Functions

check

Whether bound is the graph’s: a combinational loop is a simple cycle of no register; a ratio’s cycle is a simple cycle with those sums and some register, and its potential satisfies every edge; acyclic means the graph has no cycle. The graph itself must be well formed.

max_cycle_ratio

The bound on the period the graph’s cycles put.