Scaling the detailed router to handle circuits with 50 million cells

[liangrj2014]

Any ideas in scaling the detailed router to handle circuits with 50 million cells? The memory footprint and runtime will be serious concerns. Blows are suggestions from ChatGPT :)

1. Parallelization: Leverage parallel processing techniques to distribute the routing tasks across multiple CPU cores or GPUs. Multithreading and GPU acceleration can significantly speed up the routing process.
2. Hierarchical Routing: Implement hierarchical routing techniques that break down the routing problem into smaller, more manageable subproblems. This reduces the complexity of routing large circuits.
3. Incremental Routing: Instead of routing the entire circuit in one go, use incremental routing where you route smaller sections of the circuit at a time. This can improve efficiency and reduce memory requirements.
4. Advanced Algorithms: Explore advanced routing algorithms that are optimized for large-scale circuits. Some algorithms are specifically designed to handle massive designs efficiently.
5. Memory Management: Optimize memory usage by employing data structures and algorithms that reduce memory overhead. Use memory-efficient representations of the circuit.
6. Distributed Computing: Consider distributed computing approaches where the routing task is distributed across multiple machines or nodes in a cluster. This can further speed up routing for large circuits.
7. Machine Learning: Investigate the use of machine learning techniques to predict and guide the routing process. Machine learning can help in making routing decisions more efficiently.
8. Resource-Aware Routing: Develop routing algorithms that are aware of available resources (e.g., routing tracks, vias) and can make intelligent decisions to optimize routing.
9. Algorithmic Improvements: Continuously research and implement algorithmic improvements and optimizations specific to global and detailed routing for large-scale circuits.
10. Hardware Acceleration: Explore the use of specialized hardware accelerators, such as FPGA-based routers, to handle the routing tasks efficiently.
11. Circuit Abstraction: Utilize abstraction techniques to reduce the complexity of the circuit during routing without sacrificing the quality of the final solution.
12. Memory Hierarchy: Optimize the use of cache and memory hierarchies to minimize data access latencies during the routing process.
13. Benchmarking and Profiling: Regularly benchmark and profile the routing tool to identify performance bottlenecks and areas for improvement.
14. User Guidance: Provide options for users to guide the router's behavior, allowing them to make trade-offs between runtime and routing quality.
15. Incremental Updates: Implement mechanisms for incremental updates, allowing users to modify parts of the design without rerouting the entire circuit.

[maliberty]

If the goal is detailed routing then you could look at the work we have done for distributed detailed routing. It doesn't solve the memory concern but it does allow you to apply a lot more CPU to the runtime.

[maliberty]

@osamahammad21 would you run (or have Ahmed run) bsg_chip and mempool_group from ISPD2024_benchmarks on a 96-core machine on GCP to get a runtime & memory baseline. Also run with the distributed router to see how much it helps with runtime as you have before.

[osamahammad21]

there are no global routing guides in the benchmarks. Should I just run our global router?

[maliberty]

Yes.

[osamahammad21]

I am getting this error in GRT:
[ERROR GRT-0039] Found pin VDD outside die area in instance next/downlink/ch_0__iddr_data/data_p_r_8_sv2v_reg_reg.
It seems a valid error from the gui:

Also I don's see the power grid, is this ready for routing or do we need to do the full flow?

[maliberty]

Since we don't route to power pins in grt/drt we can skip such for this warning (@eder-matheus ).

I'll leave it to @liangrj2014 to discuss the lack of a power grid. We can route without it though it makes the design less realistic.

[osamahammad21]

bsg_chip:

• Machine: 96-CPU 360GB RAM
• Total RUNTIME: 04:14:16
• Peak Memory: 24.5GB
• Pin Access:
  • [INFO DRT-0267] cpu time = 18:12:07, elapsed time = 00:33:37, memory = 8956.00 (MB), peak = 9547.98 (MB)
• Detailed Routing:
  • [INFO DRT-0267] cpu time = 80:21:46, elapsed time = 03:26:59, memory = 19989.62 (MB), peak = 24497.96 (MB)
• Converged After 57 Iterations
• Did not set a min/max routing layer

[maliberty]

How many nets and instances?

[osamahammad21]

714938 insts
768239 Nets
After setting the min and max routing layers correctly the results are:

• Total runtime(GR and DR): 02:57:34
• Pin Access:
  • [INFO DRT-0267] cpu time = 18:13:00, elapsed time = 00:31:58, memory = 8957.35 (MB), peak = 9547.68 (MB)
• Detailed Routing:
  • [INFO DRT-0267] cpu time = 79:43:19, elapsed time = 02:16:30, memory = 19615.47 (MB), peak = 24473.79 (MB)
• Converged after 22 iterations