Forschungsinstitut für Diskrete Mathematik

Minimum Mean Cycle Instances in Chip Design

2008

This page constains some large real world instances for the minimum mean cycle problem as they occur in the clock skew scheduling in chip design.

The clock skew scheduling problem in chip design is, given a directed graph G with edge delays d:E(G)-> R,
find a minimum cycle time T and arrival times (a schedule) a: V(G) -> R such that a(v) + d(v,w) <= a(w) + T for all (v,w) in E(G).
G is called latch graph. The nodes are representing latches/registers and edges longest signal paths between registers.

The problem of minimizing T is equivalent to maximizing the worst slack min{s(v,w) := a(w) + T - a(v) - d(v,w) | (v,w) in E(G)} for a fixed cycle time T.

The instances provided in the tar-file below consist of directed graphs with edge costs c(v,w) = T - d(v,w),
i.e. edge slacks w.r.t. to a zero skew schedule where a = 0.
The maximum achievable worst slack by varying the schedule 'a' equals the value of a minimum mean cycle in (G,c).
Instance sizes range from 70346 nodes and 898220 edges to 1065274 nodes and 104340248 edges.
Other instances are very dense, e.g. 5361 nodes and 4169878 edges.