Fix high rejection rate for constrained blocks during annealing

soheilshahrouz commented 2 weeks ago

Most proposed moves for blocks with tight floorplan constraints are rejected because the proposed location for a constrained block is not withing the floorplan region. This PR tries to fix this problem.

How Has This Been Tested?

Running vtr_reg_nightly_test5/vpr_tight_floorplan regression test

Types of changes

[x] Bug fix (change which fixes an issue)
[ ] New feature (change which adds functionality)
[ ] Breaking change (fix or feature that would cause existing functionality to change)

Checklist:

[ ] My change requires a change to the documentation
[ ] I have updated the documentation accordingly
[ ] I have added tests to cover my changes
[ ] All new and existing tests passed

soheilshahrouz commented 2 weeks ago

Results for vtr_reg_nightly_test5/vpr_tight_floorplan test Circuit: neuron_stratixiv_arch_timing.blif Architectur: stratixiv_arch_neuron.timing.xml

Constraint file	Total swaps	Aborted swaps	Placed WL	Placed CPD	Place time
sixteenth.xml	1.06	0.44	0.98	1.01	1.44
half_blocks_half.xml	0.98	0.54	0.90	0.89	1.31
one_big_partition.xml	1.01	0.99	0.99	1.02	1.29

soheilshahrouz commented 2 weeks ago

one_big_partition.xml defines a single partition covering the entire grid. Other constraint files divide the grid into two and sixteen equally-sized regions. For these two constraint files, the number of aborted swaps is halved. This is because intersect_range_limit_with_floorplan_constraints() updates the search range of the target location, making sure tha the selected location is within the floorplan region. Without this change, the move generator might propose a target location outside the floorplanning region, causing the proposed move be aborted before cost difference evaluation starts.

The placement runtime increases because proposed swaps are not aborted prematurely, and more swaps result in cost difference evalution.

vaughnbetz commented 2 weeks ago

@soheilshahrouz is investigating why one_big_partition slows things down -- there doesn't seem to be a good reason.

soheilshahrouz commented 2 weeks ago

Results for vtr_reg_nightly_test5/vpr_tight_floorplan after fixing grid_loc_to_compressed_loc_approx_round_up() Circuit: neuron_stratixiv_arch_timing.blif Architectur: stratixiv_arch_neuron.timing.xml

Constraint file	Total swaps	Aborted swaps	Placed WL	Placed CPD	Place time
sixteenth.xml	1.06	0.46	0.99	1.006	1.09
half_blocks_half.xml	0.97	0.48	0.92	0.907	0.93
one_big_partition.xml	1.01	0.99	0.99	1.023	0.95

vaughnbetz commented 2 weeks ago

Excellent! Glad it looks like it is working now.

vaughnbetz commented 2 weeks ago

@soheilshahrouz : we can merge if you remove the WIP from the title. Also, did you validate the grid->compressed grid mapping code with some automated test (or extensive manual tests)? The results look good, but the new functions should still be independently tested I think, since it would be easy for a bug to sneak through and just subtly degrade optimization.

soheilshahrouz commented 2 weeks ago

We discussed about parital overlaps with blocks larger than 1x1 and regions. It's unclear to me what the expected behavior is when there is a partial overlap between a region and a block larger than 1x1. I'll explain my understanding of the code. Please correct me if I'm wrong.

cluster_floorplanning_legal() checks if a block is within its partition region. This function calls ParitionRegion::is_loc_in_part_reg(), which then calls Region::is_loc_in_reg() for all regions in the PartitionRegion.

https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/9438f73722a7e5b8baf943ffb85afc46e845f76d/vpr/src/place/place_constraints.cpp#L213-L240

Based on Region::is_loc_in_reg(), a block location is legal if its bottom-left corner is within the floorplanning constraint. Therefore, if only the upper or right part of a block larger than 1x1 overlaps with a region, it doesn't belong to that region.

https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/9438f73722a7e5b8baf943ffb85afc46e845f76d/vpr/src/base/region.cpp#L45-L69

The newly added function for converting floorplanning regions from the device grid coordinate system to compressed grid are compatible with this understanding. I can add unit tests to check if these function are behaving as expected.

vaughnbetz commented 2 weeks ago

Hmmm ... looks like I was wrong on this one. In Quartus I made floorplan regions include a block if any part was touched, but in VTR it looks like we didn't. I am now dimly recalling that this was due to Sarah finding the code more complex to handle that case, so we just decided to document it. I think we should just add this detail to the documentation.

vaughnbetz commented 1 week ago

Update: this looks good, but @soheilshahrouz wants to add a unit test to it before merging.

verilog-to-routing / vtr-verilog-to-routing