[Placement] Inconsistency in Grid Blocks Data Structure

[AlexandreSinger]

For context. I have been creating an independent placement verifier which will ensure that all placement data strcutures are valid before going through the rest of the VPR flow (i.e. routing). The idea is that, if you pass this verification, then your placement can be used for the rest of the VPR flow without issue (regardless of how you created it). This checks invariants that the placement must pass (used as assumptions later in the flow). See PR #2769

There is a method that is called after placement which synchronizes the grid to the block placement:

vtr-verilog-to-routing/vpr/src/base/vpr_api.cpp

Lines 785 to 797 in eb8c186

	if (placer_opts.doPlacement == STAGE_DO) {
	//Do the actual placement
	vpr_place(net_list, vpr_setup, arch);
	} else {
	VTR_ASSERT(placer_opts.doPlacement == STAGE_LOAD);
	//Load a previous placement
	vpr_load_placement(vpr_setup, arch);
	}
	sync_grid_to_blocks();
	post_place_sync();

vtr-verilog-to-routing/vpr/src/util/vpr_utils.cpp

Lines 91 to 165 in eb8c186

	/* Points the place_ctx.grid_blocks structure back to the blocks list */
	void sync_grid_to_blocks() {
	auto& place_ctx = g_vpr_ctx.mutable_placement();
	auto& device_ctx = g_vpr_ctx.device();
	auto& device_grid = device_ctx.grid;
	const int num_layers = device_ctx.grid.get_num_layers();
	auto& grid_blocks = place_ctx.mutable_grid_blocks();
	auto& block_locs = place_ctx.block_locs();
	/* Reset usage and allocate blocks list if needed */
	grid_blocks = GridBlock(device_grid.width(), device_grid.height(), device_ctx.grid.get_num_layers());
	for (int layer_num = 0; layer_num < num_layers; layer_num++) {
	for (int x = 0; x < (int)device_grid.width(); ++x) {
	for (int y = 0; y < (int)device_grid.height(); ++y) {
	const t_physical_tile_type_ptr type = device_ctx.grid.get_physical_type({x, y, layer_num});
	grid_blocks.initialized_grid_block_at_location({x, y, layer_num}, type->capacity);
	}
	}
	}
	/* Go through each block */
	auto& cluster_ctx = g_vpr_ctx.clustering();
	for (ClusterBlockId blk_id : cluster_ctx.clb_nlist.blocks()) {
	const auto& blk_loc = block_locs[blk_id].loc;
	int blk_x = block_locs[blk_id].loc.x;
	int blk_y = block_locs[blk_id].loc.y;
	int blk_z = block_locs[blk_id].loc.sub_tile;
	int blk_layer = block_locs[blk_id].loc.layer;
	auto type = physical_tile_type(blk_loc);
	/* Check range of block coords */
	if (blk_x < 0 || blk_y < 0
	|| (blk_x + type->width - 1) > int(device_ctx.grid.width() - 1)
	|| (blk_y + type->height - 1) > int(device_ctx.grid.height() - 1)
	|| blk_z < 0 || blk_z > (type->capacity)) {
	VPR_FATAL_ERROR(VPR_ERROR_PLACE, "Block %zu is at invalid location (%d, %d, %d).\n",
	size_t(blk_id), blk_x, blk_y, blk_z);
	}
	/* Check types match */
	if (type != device_ctx.grid.get_physical_type({blk_x, blk_y, blk_layer})) {
	VPR_FATAL_ERROR(VPR_ERROR_PLACE, "A block is in a grid location (%d x %d) layer (%d) with a conflicting types '%s' and '%s' .\n",
	blk_x, blk_y, blk_layer,
	type->name.c_str(),
	device_ctx.grid.get_physical_type({blk_x, blk_y, blk_layer})->name.c_str());
	}
	/* Check already in use */
	if (grid_blocks.block_at_location(blk_loc)) {
	VPR_FATAL_ERROR(VPR_ERROR_PLACE, "Location (%d, %d, %d, %d) is used more than once.\n",
	blk_x, blk_y, blk_z, blk_layer);
	}
	if (device_ctx.grid.get_width_offset({blk_x, blk_y, blk_layer}) != 0 || device_ctx.grid.get_height_offset({blk_x, blk_y, blk_layer}) != 0) {
	VPR_FATAL_ERROR(VPR_ERROR_PLACE, "Large block not aligned in placement for cluster_ctx.blocks %lu at (%d, %d, %d, %d).",
	size_t(blk_id), blk_x, blk_y, blk_z, blk_layer);
	}
	/* Set the block */
	for (int width = 0; width < type->width; ++width) {
	for (int height = 0; height < type->height; ++height) {
	grid_blocks.set_block_at_location({blk_x + width, blk_y + height, blk_z, blk_layer}, blk_id);
	grid_blocks.increment_usage({blk_x + width, blk_y + height, blk_layer});
	VTR_ASSERT(device_ctx.grid.get_width_offset({blk_x + width, blk_y + height, blk_layer}) == width);
	VTR_ASSERT(device_ctx.grid.get_height_offset({blk_x + width, blk_y + height, blk_layer}) == height);
	}
	}
	}
	}

All of the checks found in this method are already done in the independent verifier; however this synchronization is doing something different than what the verifier expects.

The verifier is made to match what the placer generates. The placer will only place blocks at the root tile locations (width_offset = 0; height_offset = 0). For large blocks, the other locations in the tiles are left empty. The verifier ensure that this is what happens. The issue is that the synchronization method above does not follow this. Instead it places the block at all tile locations in the large tile (not just the root). I tried to remove this functionality, but some code (specifically in the flat router) is relying on this for some reason. This causes the vtr_reg_strong/strong_flat_router regression test to fail.

I think that it is wasteful and redundant to duplicate the placed block in all tile locations in the large tile. I think that just placing the cluster block in the root tile is sufficient. The sync_grid_to_blocks method should be modified to follow this, and the code in the flat router should be fixed to reflect this change (it should always look at the root tile location for the placed block). This method is also only needed when loading the placement, the placement flow should already maintain this.

Eventually it would be a good idea to fix the grid_blocks data structure so that it is impossible to place blocks at non-root tile locations.