Bemærk!! Forelæsningsplanen er opdateret 20. oktober 2004.
| Dato | Time | Emne | Forelæser | Litteratur | Opgaver |
| Uge 36 | 1. 2. |
Introduction to VLSI design | MZ | [1] (ICCAD2000 Tutorial (Part II)) | - |
| Uge 37 | 1. 2. |
Heuristics and approximation algorithms Linear programming and column generation |
MZ JE |
[2a], [2b] [2c] |
Exercises |
| Uge 38 | 1. 2. |
Floorplanning and packing | DP | [3a], [3b] (slides) | Exercises |
| Uge 39 | 1. 2. |
Global placement | JE | [4a], [4b] (slides) | Exercises |
| Uge 40 | 1. 2. |
Final placement Advanced Sequence Pair |
JE | [5a], [5b] (slides) | Exercises |
| Uge 41 | 1. 2. |
Parametric shortest paths Cycle time and slack optimization |
JE | [6a] [6b] (slides) | Exercises The edge with no cost in the graph from exercise 2 of this week should have cost value 1 (See the updated exercises) |
| Uge 42 | - | (efterårsferie) | - | - | - |
| Uge 43 | 1. 2. |
Rectilinear Steiner trees and delay-optimal trees | MZ | [7] (slides) | Opg. 3 (30 min, obligatorisk), 5 (30 min) og 9 (30 min) fra [7] |
| Uge 44 | 1. 2. |
Uniformly oriented Steiner trees Steiner trees in graphs |
MZ | [8] | - |
| Uge 45 | - | (ingen undervisning) | - | - | - |
| Uge 46 | 1. 2. |
Global routing Detailed routing |
MZ | [9a] [9b] |
- |
| Uge 47 | 1. 2. |
Algorithms for Large-Scale Flat Placement | Gruppe I: Emil S. Frisendal Bjørn Petersen Kenneth Hvam |
[10a] [10b] |
Report |
| Uge 48 | 1. 2. |
Sequence-pair packing O-tree floorplanning | Gruppe II: Thomas Antonsen Sathi Subbarayan Laurent F. Muller |
[11a] [11b] |
Report |
| Uge 49 | 1. 2. |
Balancing MSTs and SP trees Performance driven global routing
| Gruppe III: Simon Spoorendonk Mads K. Jepsen Niels Peter M. Milthers |
[12a] [12b] |
Report |
| Uge 50 | 1. 2. |
Opsumering/afrunding/evaluering | JE/DP/MZ | - | - |
| Uge 51 | - | (ingen undervisning) | - | - | - |
Alle torsdage kl. 10.15-12.00 i N034
DP: David Pisinger, pisinger@diku.dk
MZ: Martin Zachariasen, martinz@diku.dk (kursusansvarlig)
[1] T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout, kap. I.1, 3-29, 1990.
[2a] L. A. Wolsey. Heuristic Algorithms, kap. 12 from Integer Programming, Wiley, 1998.
[2b] V. V. Vazirani, Steiner Tree and TSP , kap. 3 from Approximation Algorithms, Springer, 2001.
[2c] J. Derosiers, M. E. Lubbecke, A Primer in Column Generation, Manuscript, 2004.
[3a] 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.
[3b] P.N.Guo, C.K.Cheng, T.Yoshimura, An O-tree representation of non-slicing floorplans and its applications, DAC-99, 268--273, 1999.
[4a] M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, GORDIAN: VLSI placement by quadratic programming and slicing optimization, IEEE Trans. CAD, vol. 10, 356-365, 1991.
[4b] H. Eisenmann, F. M. Johannes, Generic Global Placement and Floorplanning, Proceedings of the 35th Annual Conference on Design Automation, 269-274, 1998.
[5a] S.-W. Hur, J. Lillis, MONGREL: Hybrid Techniques for Standard Cell Placement, ICCAD, 165-170, 2000.
[5b] K. Doll, F. M. Johannes, G. Sigl, DOMINO: Deterministic Placement Improvement with Hill-Climbing Capabilities, International Conference on VLSI, 91-100, 1991.
[6a] N. E. Young, R. E. Tarjan, J. B. Orlin. Faster Parametric Shortest Paths and Minimum-Balance Algorithms, Networks, vol. 21, 205-221, 1991.
[6b] 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.
[7] M. Zachariasen. The Rectilinear Steiner Tree Problem: A Tutorial, In D.-Z. Du and X. Cheng (Eds.), Steiner Trees in Industries, pages 467-507, Kluwer Academic Publishers, 2001.
(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.)
[8] M. Brazil, D.A. Thomas and J.F. Weng. Minimum Networks in Uniform Oientation Metrics, SIAM J. Computing, vol. 30, no. 5, pp. 1579--1593, 2000.
[9a] C. Albrecht. Global Routing by New Approximation Algorithms for Multicommodity Flow, IEEE Transactions on CAD, vol. 20, no. 5, 622-632, 2001.
[9b] A. Hetzel. A Sequential Detailed Router for Huge Grid Graphs, Design, Automation and Test in Europe Conference, 332-338, 1998.
[10b] J. Vygen, Algorithms for Detailed Placement of Standard Cells, Design, Automation, and Test in Europe, 321-324, 1998.
[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.