Class Project for Fall 2011
last updated: Nov 17, 2011
Key Dates and Presentation
Each student has 10 minutes for the presentation. Focus on results, lessons learned, enhancements (if any), etc. You are welcome to do a demo (within the time limit). Go/no-go on final exam will be determined by 4pm, 12/8.
- 12/6: in-class presentation (KL partitioning, Stockmeyer floorplanning, 1-Steiner routing)
- 12/8: in-class presentation (the rest)
- 12/8 (4pm): take-home final exam
- 12/11 (5pm): project due on T-square (attach your PDF report and zip files)
Project List
- B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning of Electrical Circuits" (1 person)
- L. Stockmeyer, "Optimal Orientation of Cells in Slicing Floorplan Designs" (1 person)
- A. B. Kahng and G. Robins, "A new class of iterative Steiner tree heuristics with good performance" (1 person)
- W. J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits" (1 person): if clustering is not used.
- D. F. Wong and C. L. Liu, "Floorplan design of VLSI circuits" (2 persons)
- W. J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits" (2 persons): if clustering is used.
- A. Dunlop and B. Kernighan, "A Procedure For Placement Of Standard-cell VLSI Circuits (2 persons): use KL as the partitioner.
Participating Teams
-
Chang-Chih Chen: KL partitioning
- Ankit Mashruwala: KL partitioning
- Amanda Cummings: Stockmeyer floorplanning
- Allan Feldman: Stockmeyer floorplanning
- Hirenkumar Kalathiya: Stockmeyer floorplanning
- Xiaomeng Wu: 1-Steiner routing
- Wink Barnes: 1-Steiner routing
-
Purav Gada: 1-Steiner routing
- William Freelove: Rajaraman and Wong clustering
- Kevin Morgan: A* routing
- Jigar Doshi: Timberwolf placement
-
Sung Joo Park: EIG partitioner
-
Chandan Gouri & Nathan Murdaugh: Polish expression
- Pranav Lalan & Adnan Pratama: Polish expression
- Gaurav Rajasekar & Muneeb Zia: Polish expression
-
Rohit Bothra & Phillip Bonhomme: Polish expression
Benchmark Circuits
- Partitioning & placement:
fract.hgr,
industry2.hgr,
ibm01.hgr,
ibm10.hgr,
ibm18.hgr.
- Clustering:
s9234.blif,
s13207.blif,
b20_opt.blif,
b22_opt.blif,
b17_opt.blif.
- Stockmeyer & polish expression:
5_block.ple,
10_block.ple,
30_block.ple,
100_block.ple,
150_block.ple.
- 1-steiner routing:
points_10_5.pts,
points_10_10.pts,
points_10_20.pts,
points_30_50.pts,
points_30_100.pts.
- A* routing: on your own (same as 1-steiner routing + randomly added obstacles)
Special Requirements
These rules apply to all: (1) seek the most effective way to "visualize" your results. (2) report both quality metric AND runtime. Project-specific requirements are as follows:
- KL partitioning: perform 2-way, 3-way, and 4-way partitioning.
- Stockmeyer floorplanning: show floorplans before and after the optimization.
- 1-Steiner routing: show the best tree after each 1-Steiner point insertion.
- RW clustering: show max cluster size vs delay tradeoff. Explain the algorithm.
- A* routing: handle multi-pin nets. Show routing results. Explain the algorithm.
- Timberwolf placement: show the annealing progress using placement snapshots.
- EIG partitioner: only 2-way balanced partitioning is required. Use 1% area skew and show split point vs cutsize and ratio cut plots.
- Polish expression: show the annealing progress using floorplan snapshots.
You are encouraged to be creative on how you present your results, how you improve the quality of results, how you make your program run faster, etc.
Submission & Grading
Students are to submit (i) source codes with makefile, (ii) executable
(preferably on Solaris or Linux), and (iii) 5-10 page final report.
Your report needs to contain the following sections: Introduction,
Problem Formulation, Algorithm Discussion, Implementation Issues,
Experimental Results, Conclusion and Extension. In addition, each
student needs to do a 15-min powerpoint presentation.
Your final grade will be based on the following criteria:
- completeness & correctness (60%)
- programming style and documentation (20%)
- presentation (20%)
Sample Project Slides and Reports
Depending on the
quality of the work, we can submit to a CAD conference/journal. Here
are some sample projects that are published:
- Peter Sassone and Sung Kyu Lim, "Traffic: A Novel Geometric
Algorithm For Fast Wire-Optimized Floorplanning," IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, Vol. 25,
No. 6, pp. 1075-1086, 2006. (pdf)
- Mongkol Ekpanyapong, Jacob Minz, Thaisiri Watewai, Hsien-Hsin S.
Lee, and Sung Kyu Lim, "Profile-Guided Microarchitectural
Floorplanning for Deep Submicron Processor Design," IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25,
No. 7, pp. 1289-1300, 2006. (pdf)