Class Project Choices (Spring 2025)
EIG vs. KL Partitioning (Paper 2-3 and 2-1)
Algorithm tutorial: EIG algorithm,
KL algorithm
1. Coding Requirements
- Implement the EIG algorithm and obtain the best ratio cut solution under the area constraint of [49%, 51%].
- You are to use sparse matrix method to handle large benchmark.
- You can use off-the-shelf eigenvector calculator.
- Compare cutsize with KL. The runtime of KL needs to be improved significantly to handle large circuits, including IBM18. Develop heuristics that overcome the O (n^3) time complexity limitation by permitting "minor" cutsize degradation.
- Build a EIG+KL hybrid, where EIG is used to obtain the initial solution and the subsequent KL for improvement. How does this compare with EIG and KL?
- Your solutions will be judged based on the correctness, cutsize, ratio cut, and runtime.
- Provide a table that shows the metrics aforementioned for all benchmarks.
2. GUI Requirements
These snapshots should be added to your PPT.
- For EACH benchmark, show the sparsity plot and calculate fill rate.
- For EACH benchmark, show the 1-D placement.
- For EACH benchmark, show the partitioning solution (x-axis) vs. ratio cut (y-axis left) vs. cutsize (y-axis right) plot. You are to show the entire solution space, not just [49%, 51%] range.
3. Animation Requirements
4. Benchmark
You are to provide tables to report the metrics aforementioned for all these benchmark in your PPT.
5. Possible Extensions
- Compare solution quality with the third, fourth, etc, smallest eigenvalues/vectors.
- Develop non-trivial ways to improve EIG runtime.
ILP Floorplanning (Paper 4-3)
Algorithm tutorial: ILP floorplanning algorithm
1. Coding Requirements
- Implement the basic algorithm and produce floorplan results for all of the benchmark circuits. You are to size all soft modules.
- For each benchmark, compute the best possible chip dimension and the corresponding runtime. The chip aspect ratio should be close to 1.
- You can use a readily available ILP solver. You do not have to implement an ILP solver.
- For large designs, you are to implement the "Partial Floorplanning" method described in the paper to cope with the complexity..
2. GUI Requirements
- For the 30 block benchmark, show the floorplan comparison among the following options: under-estimation vs. over-estimation vs. overlap removed.
3. Animation Requirements
4. Benchmark
5. Possible Extensions
- Implement an automatic (not manual) overlap removal scheme.
- Compare with Polish Expression and/or Sequence Pair. For soft module sizing, you can create multiple sizing options and use an annealing move to pick the best.
Gordian placement (Paper 5-3)
Algorithm tutorial: Gordian algorithm
1. Coding Requirements
- Implement the basic algorithm and produce placement results on all of the benchmark circuits.
- Convert the global placement into a standard cell row structure.
- For each benchmark, compute the best possible chip dimension (aspect ration close to 1) and the number of rows.
- Use a sparse matrix handling tool to handle large circuits. You do not have to implement a QP solver.
2. GUI Requirements
- Show the placement shot at each level along with connectivity information. You may choose to show a subset of connections for dense designs.
- At the end of QP placement iterations, you are to show the final placement using the chip and row information.
3. Animation Requirements
- Using benchmark structP, create a short video that shows the placement progress after each level and its final row placement. Make sure to use the identical background during the successive frames in your video.
4. Benchmark
- README-hgr.txt
- Explanation of the chip info
- fract.hgr, fract.dim, fract.io.
- industry2.hgr, industry2.dim, industry2.io.
- industry3.hgr, industry3.dim, industry3.io.
- biomedP.hgr, biomedP.dim, biomedP.io.
- p1.hgr, p1.dim, p1.io.
- p2.hgr, p2.dim, p2.io.
- structP.hgr, structP.dim, structP.io.
5. Possible Extensions
- Upgrade the partitioning engine to KL.
- Perform clustering as a pre-process.
- Compare among multiple QP solvers available.
L-Shaped vs. Borah Steiner Routing (Paper 6-1 and 6-3)
Algorithm tutorial: L-RST algorithm,
Borah algorithm
1. Coding Requirements
- Implement the L-RST algorithm. Use Prim algorithm to build separable MSTs. Use the first node as the source.
- Implement the Borah algorithm and compare with L-RST in terms of wirelength and runtime. Both routers should use the same initial separable MST.
- You are to recti-linearize all edges in the final solution.
- Your solutions will be judged based on the correctness, final wirelength, and runtime.
- Provide tables that shows the metrics aforementioned for all benchmarks.
2. GUI Requirements
These snapshots should be added to your PPT.
- For EACH benchmark, show the initial MST vs. final L-RST vs. final Borah results side-by-side and compare wirelength and runtime.
- The routing snapshots must include terminal points, Steiner points, and their connections.
3. Animation Requirements
- Using benchmark points_30_50, create a short video that shows the L-RST routing progress after each step. Do the same for Borah. Make sure to use the identical background during the successive frames in your video.
4. Benchmark
You are to provide tables to report the metrics aforementioned for all these benchmark in your PPT.
5. Possible Extensions
- Create a big benchmark (3000 random points in 100x100 grid) and run the routers. Report the results and provide GUI outputs.
- Develop non-trivials way to improve runtime, possibly at the cost of wirelength degradation.
- Extend the algorithms to minimize wirelength under radius bound.
Multi-Commodity Flow Routing (Paper 7-2)
Algorithm tutorial: MCF algorithm
1. Coding Requirements
- Implement both the ILP algorithm and the MM heuristic.
- Given a benchmark, your ILP router needs to auto-generate the input file for ILP solver.
- You can use off-the-shelf ILP solver.
- Produce and compare the routing results between ILP and MM in terms of (1) routing resource usage, (2) total wirelength, (3) individual net wirelength, and (4) total runtime. You are to present these results using tables.
- The routing resource usage should report the following: (1) if all nets are routed while not violating the capacity constraints (successful or fail), (2) histogram of all routing channels in terms of their usage.
- Reporting requirement for big benchmark: You do not have to report individual net wirelength nor the histogram for the 80, 200, and 350 net benchmark.
2. GUI Requirements
These snapshots should be added to your PPT.
-
For the 10 net benchmark, show the routing trees for individual nets as well as the final one that contains all nets.
-
For all benchmark, compare the final routing results between ILP and MM side-by-side and report the routing resource usage, total wirelength, and runtime.
3. Animation Requirements
- Using the 15 net benchmark, create a short video that shows the routing progress after each step in the MM algorithm. Make sure to use the identical background during the successive frames in your video.
4. Benchmark
You are to provide tables to report the metrics aforementioned for all these benchmark in your PPT.
5. Possible Extensions
- Drop one capacity from each benchmark and report the results.
- Develop non-trivial ways to improve the ILP algorithm runtime, possibly at the cost of wirelength degradation.
- Develop non-trivial ways to improve the MM algorithm runtime.
--- EOF ---