Forschungsinstitut für Diskrete Mathematik

Minimum Mean Cycle Instances in Chip Design


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.

Minimum Mean Cycle Instances (tar-file containing gzipped instances)
Note that the instances may not be strongly connected and not even connected.
Format: Ignore empty lines and lines starting with '#', then:
1st line: number_of_nodes number_of_edges
next lines: from_node to_node edge_cost (i.e. zero_skew_slack)
S. Held

Last modified: Fri Sep 19 18:42:38 MSZ 2008