| Dato | Time | Emne | Forelæser | Litteratur |
| 6. sept. | 1. 2. |
Introduction to VLSI design | MZ | [1] (ICCAD2000 Tutorial) |
| 13. sept. | 1. 2. |
Linear programming, duality and column generation |
DP | [2] (slides, exercises) |
| 20. sept. | 1. 2. |
Combinatorial optimization/heuristics Quadratic optimization |
MZ | [3] (CG-intro, slides, slides, exercises) |
| 27. sept. | 1. 2. |
Floorplanning and packing | DP | [4a] [4b] (slides, exercises) (GSRC, Literature) |
| 4. okt. | 1. 2. |
Global placement Detailed placement |
DP MZ |
[5a] |
| 11. okt. | 1. 2. |
Geometric Steiner trees and delay-optimal trees | MZ | [6] (slides, exercises) |
| 18. okt. | - | (efterårsferie) | - | - |
| 25. okt. | 1. 2. |
Steiner trees in graphs Variants of the Steiner tree problem |
DGJ | [7] (slides, exercises) |
| 1. nov. | 1. 2. |
Global routing Detailed routing |
DGJ | [8a] [8b] |
| 8. nov. | 1. 2. |
Parametric shortest paths Cycle time and slack optimization |
MS | [9a] [9b] |
| 15. nov. | - | (ingen forelæsninger) | - | - |
| 22. nov. | 1. 2. |
Kernighan-Lin/Fiduccia-Mattheyses Hypergraph partitioning | Per Jacobsen, Stig Jørgensen (gruppe I) |
[10a] |
| 29. nov. | 1. 2. |
Sequence-pair packing O-tree floorplanning | Jesper Munch Jørgensen, Morten Frederiksen (gruppe II) |
[11a] [11b] |
| 6. dec. | 1. 2. |
Balancing MSTs and SP trees Performance driven global routing
| Adam Rosenberg, Eigil Hauge Larsen (gruppe III) |
[12a] [12b] |
| 13. dec. | 1. 2. |
Gate and wire sizing | Jes Rahbek Klinke, Niels Peter Waagstein (gruppe IV) |
[13] |
| 20. dec. | 1. 2. |
Opsumering/afrunding/evaluering | DJG/DP/MS/MZ | - |
Alle (tors)dage kl. 10.15-12.00 i N037
DP: David Pisinger, pisinger@diku.dk
MS: Mikkel Sigurd, sigurd@diku.dk
MZ: Martin Zachariasen, martinz@diku.dk
[1] T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout, kap. I.1, 3-29, 1990.
[2] R. K. Ahuja, T. L. Magnanti, J. B. Orlin: Linear Programming, Appendix C from Network Flows, Prentice Hall, 1993.
[3] L. A. Wolsey. Heuristic Algorithms, kap. 12 from Integer Programming, Wiley, 1998.
(desuden uddrag fra J. R. Shewchuk. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain)
[4a] X. Hong, G. Huang, Y. Cai, S. Dong, C-K. Cheng, J. Gu: Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan (paper)
[4b] H. Murata, K. Fujiyoshi, S. Nakatate, Y. Kajitani: VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair IEEE Transactions on CAD, vol. 15, no. 12, 1518-1524, 1996 (paper)
[5a] O. Faroe. Placement in VLSI Layout, DIKU, 2000.
[5b] O. Faroe, D. Pisinger, M. Zachariasen: Local Search for Final Placement in VLSI Design, ICCAD 2001.
[6] M. Zachariasen. The Rectilinear Steiner Tree Problem: A Tutorial, In D.-Z. Du and X. Cheng (Eds.), Steiner Trees in Industries, Kluwer Academic Publishers, to appear.
(desuden uddrag fra D. M. Warme, P. Winter, M. Zachariasen. Exact Algorithms for Plane Steiner Tree Problems: A Computational Study. In D.Z. Du, J.M. Smith and J.H. Rubinstein (Eds.) Advances in Steiner Trees, pages 81-116, Kluwer Academic Publishers, 2000.)
[7] D. G. Jørgensen. Tree Problems in Graphs, DIKU, 2001.
[8a] C. Albrecht. Global Routing by New Approximation Algorithms for Multicommodity Flow, IEEE Transactions on CAD, vol. 20, no. 5, 622-632, 2001.
[8b] A. Hetzel. A Sequential Detailed Router for Huge Grid Graphs, Design, Automation and Test in Europe Conference, 332-338, 1998.
[9a] N. E. Young, R. E. Tarjan, J. B. Orlin. Faster Parametric Shortest Paths and Minimum-Balance Algorithms, Networks, vol. 21, 205-221, 1991.
[9b] C. Albrecht, B. Korte, J. Schietke, J. Vygen. Cycle Time and Slack Optimization for VLSI-Chips, Proceedings of the IEEE International Conference on Computer-Aided Design, 232-238, 1999.
[10a] T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout, kap. 6.1-6.2, 251-275, 1990.
[10b] A. E. Caldwell, A. B. Kahng, I. L. Markov. Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning, ACM Journal of Experimental Algorithms, vol. 5, 2000.
[11a] X. Tang, R. Tian, D.F. Wong Fast evaluation of Sequence Pair in Block Placement by Longest Common Subsequence Computation, DATE 2000.
[11b] P.-N. Guo, T. Takahasi, C.-K. Cheng, T. Yoshimura. Floorplanning Using a Tree Representation, IEEE Transactions on CAD, vol. 20, no. 2, 281-289, 2001.
[12a] S. Khuller, B. Raghavachari, N. Young. Balancing Minimum Spanning Trees and Shortest-Path Trees, Algorithmica, 14, 305-321, 1995.
[12b] C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, D. Karger. Prim-Dijkstra Tradeoffs for Improved Performance-Driven Global Routing, IEEE Transactions on CAD, vol. 14 no. 7, 890-896, 1995.
[13] C.-P. Chen, C. C. N. Chu, D. F. Wong. Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation, IEEE Transactions on CAD, vol. 18, no. 7, 1014-1025, 1999.