Abacus Legalization Failing with x out of range

[ArEsKay3]

I've been hacking on some of the global placement code (in this case, I'm running mixed size adaptec), but occasionally seeing this assertion fail during legalization. Any idea what might cause this?

[ASSERT ] dreamplace/ops/abacus_legalize/src/abacus_legalize_cpu.h:156: DreamPlace::abacusPlaceRowCPU(const T*, const T*, const T*, T*, T, T, T, int, int, int*, DreamPlace::AbacusCluster<T>*, int)::<lambda(int, T, T)> [with T = float]: Assertion `cluster->x >= range_xl && cluster->x+cluster->w <= range_xh' failed

Does the comment really imply that this assert isn't necessary? https://github.com/limbo018/DREAMPlace/blob/696c750c1f343fe06d00e3615d3d82972fbc5483/dreamplace/ops/abacus_legalize/src/abacus_legalize_cpu.h#L152-L154

[limbo018]

Hi, we need to confirm two things.

1. Is the placement legal before running abacus legalization? Current implementation of Abacus only minimizes displacement for legal input.
2. Are there fixed nodes that overlap with each other? This may cause the incorrect sorting order from left to right in a row and eventually lead to the failure of this range check.

Thanks Yibo

[ArEsKay3]

Thanks for the quick reply!

1. By legal do you mean all cells in bounds? I thought during global placement all cells are clipped to the boundary so the input should be legal. I will take a look and add some code to confirm.
2. Currently I am attempting mixed size placement. In order to achieve this I altered the data structure to treat all macros as movable cells. Other fixed cells (I/O) might be overlapping with the movable macros but they shouldn't be overlapping each other. Is there an easy way to check for this failure mode?

[limbo018]

By legal, I mean both whether cells are not out boundary and there is no overlap between cells.

If you notice, abacus is the last legalization step. Before abacus, we have macro legalization and greedy legalization. If there is no overlapping message printed on the screen, it means the placement has already been legal before abacus. Then, abacus can do incremental minimization of displacement.

If you make sure no overlapping message printed before running abacus and there are no fixed macros overlapping with each other, then this assertion should hold. The easiest way to check fixed macros is to enumerate every pair of them and check overlaps in after read the design. The number of fixed macros is relatively small, so I think this is affordable.

[ArEsKay3]

OK, so it seems like there is a problem during an earlier legalization step because the [ASSERT] always comes with [ERROR]s regarding overlap. How would you suggest detecting this failure mode so I can handle it before it triggers the assert? It looks like the check_legality() method returns True/False but it doesn't look like it was plumbed through. https://github.com/limbo018/DREAMPlace/blob/d0d2b039a4710737f35c466f44993e4f7ac68ed3/dreamplace/ops/greedy_legalize/src/greedy_legalize.cpp#L99-L116

[limbo018]

This means the greedy legalization failed to find legal solution for some cells. It is rather difficult to debug the legalization part remotely unless you can go into the algorithm.

Another way is that you share the cell locations and sizes after global placement. As no interconnection information is needed, hopefully it is not too sensitive to share. This can be done by turning off the legalization and detailed placement flags in the JSON file. I can help debug on my side.

[limbo018]

A quick way around is to forbid the legalization and detailed placement, by invoking external placers like NTUplace3, but it might be slower.

[ArEsKay3]

I'm actually OK with the greedy legalization not finding a legal solution. I just need to be able to detect it properly and stop attempting the legalization (rather than triggering the following assert during abacus stage).

[limbo018]

Hi, I understand your request now. Please check out commit 57f7886. I have created a legality check operator (https://github.com/limbo018/DREAMPlace/blob/b7f7886b89401d9f51c9998146934b0b5e9d410a/dreamplace/BasicPlace.py#L386) and moved all the legality check from C++ to python. This operator will return a boolean value true or false indicating legal or not.

Meanwhile, in legalization (https://github.com/limbo018/DREAMPlace/blob/b7f7886b89401d9f51c9998146934b0b5e9d410a/dreamplace/BasicPlace.py#L452) and detailed placement (https://github.com/limbo018/DREAMPlace/blob/b7f7886b89401d9f51c9998146934b0b5e9d410a/dreamplace/BasicPlace.py#L530), we will check if each step is legal.

As all these checking is done in python now, you may feel free to move them around and customize.

Thanks Yibo

[ArEsKay3]

Awesome, I'll be giving this a try soon and I'll report back.

[ArEsKay3]

I gave this a shot on the Adaptec and BigBlue benchmarks. It seems every single run many benchmarks are reporting errors during greedy legalization. Are you able to get this to run mixed size on Adaptec2 without legalization errors?

[limbo018]

I gave this a shot on the Adaptec and BigBlue benchmarks. It seems every single run many benchmarks are reporting errors during greedy legalization. Are you able to get this to run mixed size on Adaptec2 without legalization errors?

Hi, I am a bit confused on the description. Could you clarify the following two questions?

1. "every single run many benchmarks": do you mean running multiple benchmarks at the same time in one program?
2. "mixed size on Adaptec2": do you mean making all fixed macros movable on Adaptec2?