rtlmp fails to find solution

[gadfort]

Describe the bug

#6391 seems to triggering on designs that used to pass without any issues.
With this PR I'm getting:

[ERROR MPL-0037] Couldn't break flat cluster (root)_glue_logic_0_0 with PAR. The solution is fully unbalanced.
Error: sc_macro_placement.tcl, 115 MPL-0037

Expected Behavior

Macros placed without errors

Environment

OpenROAD v2.0-17721-g5f20e5980 
Features included (+) or not (-): +GPU +GUI +Python
This program is licensed under the BSD-3 license. See the LICENSE file for details.
Components of this program may be licensed under more restrictive licenses which must be honored.

To Reproduce

sc_issue_ethmac_job0_skywater130_sky130hd_floorplan.macro_placement0_20241220-034710.tar.gz

tar xvf sc_issue_ethmac_job0_skywater130_sky130hd_floorplan.macro_placement0_20241220-034710.tar.gz
cd sc_issue_ethmac_job0_skywater130_sky130hd_floorplan.macro_placement0_20241220-034710
./run.sh

Relevant log output

Floorplan Outline: (0, 0) (1142.89, 1142.89),  Core Outline: (1.38, 2.72) (1141.72, 1139.68)
	Number of std cell instances: 8017
	Area of std cell instances: 99596.03
	Number of macros: 1
	Area of macros: 419462.72
	Halo width: 40.00
	Halo height: 40.00
	Area of macros with halos: 541366.31
	Area of std cell instances + Area of macros: 519058.75
	Core area: 1296521.00
	Design Utilization: 0.40
	Core Utilization: 0.11
	Manufacturing Grid: 5

[ERROR MPL-0037] Couldn't break flat cluster (root)_glue_logic_0_0 with PAR. The solution is fully unbalanced.
Error: sc_macro_placement.tcl, 115 MPL-0037

Screenshots

No response

Additional Context

No response

[AcKoucher]

@gadfort This is surprising.

The changes in #6391 add an error to prevent MPL2 to move on when PAR does a terrible job partitioning a cluster.

We only throw this error when we give a certain hypergraph input to the partitioner (that represents a certain cluster A made of X macros and Y std cells) and the partitioner outputs an empty partition along with another partition identical to A.

This may trigger an infinite recursion like #6083 or we may get lucky and in the subsequent split for one of the output partitions (we'll give the same problem to the partitioner again) some random seed variation may generate a slightly different output and it will go on. The latter is what seems to be happening here. Here are some debugPrint messages without the new changes to show where the problem is.

[DEBUG MPL-multilevel_autoclustering] Breaking Cluster: root
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic: Num Macros: 1 Num Std Cells: 8017
[DEBUG MPL-multilevel_autoclustering] Breaking flat cluster (root)_glue_logic with TritonPart
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0: Num Macros: 1 Num Std Cells: 6414
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_1: Num Macros: 0 Num Std Cells: 1603
[DEBUG MPL-multilevel_autoclustering] Breaking flat cluster (root)_glue_logic_0 with TritonPart
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0: Num Macros: 1 Num Std Cells: 6240
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_1: Num Macros: 0 Num Std Cells: 174
[DEBUG MPL-multilevel_autoclustering] Breaking flat cluster (root)_glue_logic_0_0 with TritonPart
/* Here's the problem */
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0_0: Num Macros: 1 Num Std Cells: 6240
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0_1: Num Macros: 0 Num Std Cells: 0
[DEBUG MPL-multilevel_autoclustering] Breaking flat cluster (root)_glue_logic_0_0_0 with TritonPart
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0_0_0: Num Macros: 1 Num Std Cells: 6010
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0_0_1: Num Macros: 0 Num Std Cells: 230
[DEBUG MPL-multilevel_autoclustering] Breaking flat cluster (root)_glue_logic_0_0_0_0 with TritonPart
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0_0_0_0: Num Macros: 1 Num Std Cells: 5022
[DEBUG MPL-multilevel_autoclustering] Setting Cluster Metrics for (root)_glue_logic_0_0_0_0_1: Num Macros: 0 Num Std Cells: 988

I'm working on a change to apply a relaxation to the constraints we give to PAR if it outputs such a bad result.