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.
Last modified: Fri Sep 19 18:42:38 MSZ 2008 |