vtr-verilog-to-routing icon indicating copy to clipboard operation
vtr-verilog-to-routing copied to clipboard

[IntraClusterPlacement] Code Cleanups

Open AlexandreSinger opened this issue 5 months ago • 2 comments

The intra cluster placement code used by the ClusterLegalizer is a bit dis-organized and uses C-style semantics which make it hard to read, use more memory, and may even make it slower. The following are some tasks which will make this interface better.

  • [x] The cluster_placement_stats is actually not named very precisely. It is very confusing since cluster_placement implies how the clusters will be placed in the FPGA grid, not how the primitives will be placed within a tile. This data structure should be renamed and the file name should follow-suite. It should be named to something that captures that this is intra-cluster placement of primitives into clusters (as opposed to inter-cluster placement of clusters into tiles). https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/859198ca6290cf22858326481b107d155e5e899a/vpr/src/pack/cluster_placement.h#L14-L19
  • [ ] The cluster placement stats maintains queues of primitives which are in flight, tried, or used in a given cluster. This is currently implemented as unordered multimaps. Beyond just being confusing, this is not a very time nor space efficient way to implement queues. The way these queues are implemented can probably be made better. https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/859198ca6290cf22858326481b107d155e5e899a/vpr/src/pack/cluster_placement.h#L110-L112
  • [ ] The cluster placement stats needs to maintain a lookup between the pb_graph_node primitive (the location of the primitive in the pb_graph) and the information it maintains about that primitive (what atom is actually placed there). This can be done much much better if the primitives within the pb_graph of a cluster had unique IDs. This can make lookup into this container much faster and may be able to make other parts of the overall code better (since we would not need to use recursive functions every time we wanted to find a primitive in the pb_graph). https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/859198ca6290cf22858326481b107d155e5e899a/vpr/src/pack/cluster_placement.h#L114-L118
  • [ ] How the cluster placement stats are initialized can be cleaned up slightly (which can save some runtime). Due to legacy reasons, the object is allocated, re-constructed, loaded, reset, and the set. Since each of these represent a recursive call, this can get quite expensive. This can probably all be done at once. NOTE: If each primitive had a unique ID in the pb_graph, this code can probably be made MUCH more efficient! https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/859198ca6290cf22858326481b107d155e5e899a/vpr/src/pack/cluster_placement.cpp#L151-L164

AlexandreSinger avatar Sep 20 '24 15:09 AlexandreSinger