[P1] Investigate/refactor the cost/award estimation for mapping

[tancheng]

#58 enables the simple cost/award estimation for MRRG mapping.

However, it is now super rough and when I try to include the utilization (e.g., lower utilized tile should be prioritized for placement of an operation), the compiled II unfortunately becomes worse.

For now, the simple for loop's RecMII = 4, ResMII = 1, but CompiledII = 6: https://github.com/coredac/dataflow/blob/3a3c5546a7b6c0cf2bbef7692474a8570a2b6922/test/neura/ctrl/branch_for.mlir#L141
Our goal is to decrease CompiledII from 6 to 4. Note that the pattern matching is orthogonal, which can make RecMII = 1 hopefully.

TODO:

• Figure out why more consideration leads to worse compiled II.
• Include the utilization of HW resources into the heuristic mapping.
• Enable backtrack for operation placement, i.e., if mapping is not valid when an operation is being placed or when a move operation is being routed, we need to backtrack to the previous/producer operation's placement.

[ShangkunLi]

Hi~ Cheng,

I have some questions after reading the detailed mapping implementation:

1. Why the award is set as: int award = mapping_state.getII() + tile->getDstTiles().size();? I can understand a greater tile->getDstTiles().size() can bring more flexibility in mapping. But why a greater II is preferred?
2. Why should neura.constatnt occupy one tile in the mapping result? (i.e., Should we treat neura.constant as a "real" operation?)

[tancheng]

int award = mapping_state.getII() + tile->getDstTiles().size();

• This is the initialization, you can also replace mapping_state.getII() with 0, it is the target II at current stage/trial. When current II failed, the mapping_state.II will + 1 and retry entire procedure
• The award will be decreased depending on whether at time t the outLink is idle/ready to be occupied.
  • You can also consider other factor to decrease it or increase it, the point is to make the choices sortable, so we can pick one or multiple of them to try place&route
• In summary, greater II in this scenario is for current target II, int award = mapping_state.getII() + tile->getDstTiles().size() is applied to all the locations in this round of heuristic mapping, it won't be compared with last round smaller II or next round even greater II

Why should neura.constatnt occupy one tile in the mapping result? (i.e., Should we treat neura.constant as a "real" operation?)

• I have to start from this at this stage, as we have not yet fuse constant into the consumer op.
• And I think it is supported in our or most hardware. A constant op could be a very basic (though not that necessary) op in the PE/tile. And I prefer to have that support in our mapper.