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.
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.
YK Channel Routing (Paper 7-4)
Algorithm tutorial: constrained left-edge (CLE) algorithm, YK algorithm
1. Coding Requirements
- Implement the constrained left-edge (CLE) algorithm.
- Implement the net merging algorithm using the "Simple" method described in Section IV of the paper.
- Compare CLE and YK in terms of channel density, track usage, and runtime.
- For those benchmarks that have cycles in VCG, you are to break them using doglegs at every terminal location (restricted doglegging).
2. GUI Requirements
These snapshots should be added to your PPT.
- For EACH benchmark, you are to show the routing results. Report the # of nets, channel density, track usage, and runtime.
3. Animation Requirements
- Using dr2 benchmark, create a short video that shows the routing progress for each track from the top to the bottom. 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.
Note that some circuits contain cycles in the VCGs, but they can be broken by adding doglegs at each terminal column.
5. Possible Extensions
- Improve the dogleg insertion algorithm to further reduce the number of doglegs inserted and/or the track usage.
- Implement the net merging algorithm using the "Matching" method described in Section V.
--- EOF ---