drt: Investigate/tune congestion based worker sizing

[antonblanchard]

Describe the bug

drt has code to detect congestion, and increase the worker size (default 7x7). I'm looking for designs that exercise this path so that we can decide if the algorithm is working as expected.

So far I've only found sky130hd/Microwatt enables congestion adjustment, and as a result it increases the worker size to be quite large (25x25):

[INFO DRT-0195] Start 0th optimization iteration.
args.size 7
[INFO DRT-0195] Start 1st optimization iteration.
args.size 7
[INFO DRT-0195] Start 2nd optimization iteration.
args.size 7
[INFO DRT-0195] Start 3rd optimization iteration.
args.size 7
[INFO DRT-0195] Start 4th optimization iteration.
args.size 7
[INFO DRT-0195] Start 5th optimization iteration.
args.size 7
[INFO DRT-0195] Start 6th optimization iteration.
args.size 7
[INFO DRT-0195] Start 7th optimization iteration.
args.size 9
[INFO DRT-0195] Start 8th optimization iteration.
args.size 11
[INFO DRT-0195] Start 9th optimization iteration.
args.size 13
[INFO DRT-0195] Start 10th optimization iteration.
args.size 15
[INFO DRT-0195] Start 11th optimization iteration.
args.size 15
[INFO DRT-0195] Start 12th optimization iteration.
args.size 17
[INFO DRT-0195] Start 13th optimization iteration.
args.size 19
[INFO DRT-0195] Start 14th optimization iteration.
args.size 21
[INFO DRT-0195] Start 15th optimization iteration.
args.size 23
[INFO DRT-0195] Start 16th optimization iteration.
args.size 7
[INFO DRT-0195] Start 17th optimization iteration.
args.size 25
[INFO DRT-0195] Start 18th optimization iteration.
[INFO DRT-0267] cpu time = 02:15:26, elapsed time = 00:10:02, memory = 14396.67 (MB), peak = 14702.38 (MB)

If I disable the congestion detection code, it completes in less iterations and in a shorter time (9 minutes instead of 10 minutes):

[INFO DRT-0195] Start 0th optimization iteration.
args.size 7
[INFO DRT-0195] Start 1st optimization iteration.
args.size 7
[INFO DRT-0195] Start 2nd optimization iteration.
args.size 7
[INFO DRT-0195] Start 3rd optimization iteration.
args.size 7
[INFO DRT-0195] Start 4th optimization iteration.
args.size 7
[INFO DRT-0195] Start 5th optimization iteration.
args.size 7
[INFO DRT-0195] Start 6th optimization iteration.
args.size 7
[INFO DRT-0195] Start 7th optimization iteration.
args.size 7
[INFO DRT-0195] Start 8th optimization iteration.
args.size 7
[INFO DRT-0195] Start 9th optimization iteration.
args.size 7
[INFO DRT-0195] Start 10th optimization iteration.
args.size 7
[INFO DRT-0195] Start 11th optimization iteration.
args.size 7
[INFO DRT-0195] Start 12th optimization iteration.
args.size 7
[INFO DRT-0195] Start 13th optimization iteration.
[INFO DRT-0267] cpu time = 02:12:57, elapsed time = 00:09:03, memory = 14398.48 (MB), peak = 14641.39 (MB)

Expected Behavior

• Have a design example in the CI that both exercises the congestion code and shows better results with it.
• Reduce the negative impact (in terms of execution time) on the sky130hd Microwatt design

Environment

Git commit: 81706aef55de40a6f2eccadf25c20f418a554ab6
os: Fedora Linux 37 (Workstation Edition)
cmake version 3.25.1
gcc (GCC) 12.2.1 20221121 (Red Hat 12.2.1-4)
clang version 15.0.6 (Fedora 15.0.6-2.fc37)

To Reproduce

Run ORFS sky130hd/microwatt

Relevant log output

No response

Screenshots

No response

Additional Context

No response

[maliberty]

Some old notes from Stephano who implemented this: Fixes https://github.com/The-OpenROAD-Project/OpenROAD/issues/1619

[antonblanchard]

I tried the test case in #1619 and OpenROAD can now successfully route it without drcs with the congestion code disabled. It also does it with less iterations and less overall time compared to when the congestion code is enabled.

Another thing I noticed is the worker size doesn't peak as high as in Microwatt. I wonder if we should put an upper bound on it (so it doesn't get out of hand like it seems to with Microwatt):

args.size 7
args.size 7
args.size 7
args.size 7
args.size 7
args.size 7
args.size 7
args.size 7
args.size 9
args.size 9
args.size 9
args.size 8
args.size 8
args.size 8
args.size 10
args.size 10
args.size 10
args.size 7
args.size 12
args.size 11
args.size 11
args.size 11
args.size 11
args.size 11
args.size 10
args.size 5
args.size 12
args.size 12
args.size 12
args.size 12
args.size 12
args.size 11
args.size 11
args.size 3
args.size 11
args.size 11
args.size 11
args.size 10
args.size 10
args.size 10
args.size 10
args.size 3
args.size 10
args.size 9
args.size 9
args.size 9
args.size 9

I'll look at the other test cases next.

[maliberty]

If we no longer need it that would be great. Thanks for digging into it.

[antonblanchard]

ispd18_test3 still fails without congestion detection. Looking at where drt fails with it disabled, it's an area with only 3 available layers of metal above a macro and a lot of wires passing over it:

We should be able to build a test case similar to this.

[antonblanchard]

I wasn't able to recreate this with Nangate45 or sky130. It was however easy to replicate this using the ispd18 tech lef.

The test case is pretty simple. I have a blockage on all of Metal1-6 and 14 Metal7 pins on the left reverse connected to 14 pins on the right. In this case the congestion code doesn't detect congestion, and we finish drt with 3 drcs:

What stands out is how large the vias are. If I reduce the size of the vias, drt completes in the 0th iteration without issue:

Do we have an issue in drt related to vias?

Test case: ispd18_test3_cutdown.tar.gz

[maliberty]

The via selection code certain could be improved and this look like a good example. On some private pdks we had to manually override the via selection.

[QuantamHD]

@antonblanchard I've run into the same via selection issues on the private PDK (should be familiar to you) Matt's referring to.

In more advanced nodes the number of default vias in the tLEF rises substantially, and the via selection code in DRT just does a primitive sort based on a few characteristics.

In the PDK we're talking about it results in DRC errors, because it chooses a via that's only legal in the context of a power grid. A proper enhancement of the code would probably check if the via is legal in a routing context, and then try to choose the via with the least restrictions at the smallest size.

[QuantamHD]

I should also point out that the via selection code is only run once per detailed route execution so computation cost isn't really an issue.

[maliberty]

Its also not design specific so you can run any test case for a particular PDK

[antonblanchard]

The via selection code certain could be improved and this look like a good example. On some private pdks we had to manually override the via selection.

For the ispd18 test there is only one via for these levels of metal, and in many cases it isn't even the correct orientation so we have to create one by flipping the dimensions. Seems a bit odd.

In my testing above I manually reduced the size of the via to test the theory that via size is contributing to the drcs. Is it valid to create a new (smaller) via using the other design rules in the tlef?

[QuantamHD]

If it's DRC legal it's legal. Did you enable via generation for that particular run?

[QuantamHD]

@antonblanchard Do you have the ability to detail route that test case with the IBM tools?

[maliberty]

They might have been making it harder to route for the contest. Equally it could just have been an oversight.

[QuantamHD]

From https://www.ispd.cc/contests/18/index.html

[maliberty]

I don't think we should invent new vias. This just appears to be part of the challenge of this design is the weird vias provided. There is nothing for via selection to do here.

[QuantamHD]

This seems like contest foder, but perhaps an optimization around high density pins makes sense.

It feels like the router is getting stuck because the pins are so close together, and the nets are coming from so far away. Perhaps for cases like these we should insert virtual intermediate points to reduce the search space between this high area of congestion, and the far away nets.

[antonblanchard]

A few more puzzling things about the ispd18_test3:

• The track layout in the def doesn't match the tlef:

LAYER Metal7
  TYPE ROUTING ;
  DIRECTION HORIZONTAL ;
  PITCH 0.2 0.2 ;
  WIDTH 0.07 ;
  AREA 0.02 ;
  SPACINGTABLE
    PARALLELRUNLENGTH 0
    WIDTH 0     0.07 
    WIDTH 0.1   0.15
    WIDTH 0.75  0.25
    WIDTH 1.5   0.45 ;
  SPACING 0.1 ENDOFLINE 0.1 WITHIN 0.035 ;
END Metal7

PITCH is 0.2 x 0.2 which with DATABASE MICRONS = 2000 means the tracks should be spaced 400 x 400. The tracks in the preferred direction are actually spaced 570:

TRACKS X 200 DO 4943 STEP 400 LAYER Metal7 ;
TRACKS Y 760 DO 2473 STEP 570 LAYER Metal7 ;

That's only an issue for my cut down test case, since I am generating a different track layout to the original test.

• The vias on Metal7-Metal9 obstruct 3 tracks, eg:

It's even worse on Metal8 because it uses the same dimensions as Metal7 instead of swapping them (so the preferred direction track pitch is 400 units).

Having scanned through drt, I wonder if this is an issue. It seems like we assume a via will only obstruct one track. There is code for NDR vias where we mark multiple tracks as being obstructed but it isn't being used. This isn't an NDR via, but it seems to have the behaviour of an NDR via doesn't it?

[maliberty]

Do the guides in the contest reflect this via obstruction ?

[maliberty]

Where are we making the via == 1 track assumption?

[antonblanchard]

Where are we making the via == 1 track assumption?

I've spent some time looking through drt, and I was wrong. It does correctly iterate across all tracks in modMinSpacingCostVia.

Not directly related to this issue, but I notice modMinSpacingCostVia only applies min area constraints to vias that aren't fat (ie not wider than the default wire):

  if (!isFatVia) {
    auto minAreaConstraint = getTech()->getLayer(lNum)->getAreaConstraint();
    auto minArea = minAreaConstraint ? minAreaConstraint->getMinArea() : 0;
    patchLength = frCoord(ceil(1.0 * minArea / defaultWidth
                               / getTech()->getManufacturingGrid()))
                  * frCoord(getTech()->getManufacturingGrid());
    length2_mar = max(length2_mar, patchLength);
  }

Is that a reasonable assumption?

[maliberty]

It seems reasonable though I've never checked it. Usually those vias are pretty large