Issue with Molecule Clustering Causing Suboptimal Placement

[WindFrank]

Hi VTR team,

I've noticed a recurring issue with the clustering algorithm that affects the placement of molecules in CLBs during the packing process. (#2763). This happens even when the --allow_unrelated_clustering option is set to off. Ideally, VTR should manage to utilize the same number of CLBs and area without merging unrelated subnets.

Proposed Behaviour

When processing a netlist containing two unrelated subnetlists, I expect:
Each CLB, e.g., for modules 2713 and 5685, should be placed close to their respective I/Os to minimize routing complexity and associated delays.

Current Behaviour

Instead, I observed that:
CLB 5685 is located at (75, 111), and CLB 2713 at (80, 55), both centrally within the architecture. This configuration leads to increased critical path delay, wire length, and WNS due to unrelated molecules from 2713 being added to CLB 5685 despite available space in CLB 2713.

Possible Solution

I propose the following adjustments to the gain calculation process to better handle this issue (also in #2763):

1. Modify the Gain Calculation:
   In vpr/src/pack/cluster_util.cpp function get_molecule_gain, refine how the tie-breaker contributes to gain:

gain += blk_gain[blk_id]: condition_program_first2713^MIN52_0[0]; //current gain=0.000000
gain += blk_gain[blk_id]: condition_program_first2713^MIN52_1[0]; // current gain=0.000000
gain += molecule->base_gain * 0.0001; //gain=0.003840, gain after tie breaker

gain -= num_introduced_inputs_of_indirectly_related_block * (0.001); //final gain=0.003840
2. Implement Negative Gain for Unrelated Blocks:
Introduce a negative gain adjustment in blk_gain[blk_id]. If the gain is negative, treat the block as an unrelated molecule that should not be considered for clustering.
3. Verification of Block Relations:
Implement a step to verify the relationships of blocks within a CLB, ensuring that unrelated blocks are not clustered together erroneously.

Context

This issue was identified while processing a netlist with two distinct modules that are unrelated. The final FPGA solution’s performance was inferior compared to processing each module separately, which had no common routing resources.

I believe addressing these issues will enhance the accuracy of molecule placement in CLBs and significantly improve the quality of routing and overall FPGA performance. Thank you for considering these suggestions, and I look forward to your feedback.