|
Description
|
This data set contains some large real-world instances of the minimum mean cycle problem. They are reported as the bonn01 to bonn09 instances in the paper:
Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. "An experimental study of minimum mean cycle algorithms", in 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 1–13, SIAM.
The instances arise in clock skew scheduling in chip design, e.g. see
Held, S., Korte, B., Rautenbach, D. and Vygen, J. "Combinatorial optimization in VLSI design. Combinatorial Optimization", in Combinatorial Optimization, NATO Science for Peace and Security Series - D: Information and Communication Security, pp. 33–96, 2011.
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 a latch graph. The nodes represent latches and registers, and the edges represent the 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. 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.
Note that the instances may not be strongly connected or 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) (2024-02-27)
|
|
Related Publication
| Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. "An experimental study of minimum mean cycle algorithms", in 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 1-13, SIAM.isbn: 978-0-89871-930-7 |
