Parallelization of FastRouteCore::mazeRouteMSMD

[eszpotanski]

Description

A major part of global routing is spent on fixing overflows in FastRouteCore::mazeRouteMSMD. It iterates over Steiner trees representing parts of the routing, which are mostly disjoint. It should be possible to parallelize this method.

Suggested Solution

We're currently trying to parallelize the FastRouteCore::mazeRouteMSMD.

Additional Context

No response

[stefanottili]

Is this effort inspired by some of the ispd24 contest approaches or do you have something else in mind ?
https://liangrj2014.github.io/ISPD24_contest/
The largest of the ispd24 test cases OpenRoad is currently able to grt/drt in 64GB is the 715k stdcell bsg_chip.def.gz

[eszpotanski]

No, I though about adjusting existing method to make it work in parallel on CPU.

I checked out the contest and it was mainly focused on GPU acceleration and ML solutions - top submissions are vaguely described in final presentation, but I found a few papers created by the top teams; I'll check whether there is something that can be used.

[stefanottili]

One of the top three didn’t use the gpu at all, so threading can help a lot with regard to runtime.
Could you point me to the papers you found ?
It would be good to run the ispd24 testcases with OpenRoad. For bsg_chip I had to set the global route resource adjustment to 0.5 get it to detail route without too many starting violations.

[maliberty]

It would be good to describe your approach once you clarify it. InstantGR does work with the gpu.

[eszpotanski]

It seems that papers don't describe work from the contest, as they usually compare results with top three teams. But they are created by the same people, so I guess papers describe improved solutions:

• 1st place team - paper
• 2nd place team (already mentioned InstantGR) - paper, code

Both approaches use GPU.

Other papers based on ISPD24:

• paper, code