[IntraClusterPlacement] Code Cleanups

[AlexandreSinger]

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.

• 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).
  

  vtr-verilog-to-routing/vpr/src/pack/cluster_placement.h

  Lines 14 to 19 in 859198c

  	/**
  	* @brief Stats keeper for placement within the cluster during packing
  	*
  	* Contains data structure of placement locations based on status of primitive
  	*/
  	class t_cluster_placement_stats {

• 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.
  

  vtr-verilog-to-routing/vpr/src/pack/cluster_placement.h

  Lines 110 to 112 in 859198c

  	std::unordered_multimap<int, t_cluster_placement_primitive*> in_flight; ///<ptrs to primitives currently being considered to pack into
  	std::unordered_multimap<int, t_cluster_placement_primitive*> tried; ///<ptrs to primitives that are already tried but current logic block unable to pack to
  	std::unordered_multimap<int, t_cluster_placement_primitive*> invalid; ///<ptrs to primitives that are invalid (already occupied by another primitive in this cluster)

• 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).
  

  vtr-verilog-to-routing/vpr/src/pack/cluster_placement.h

  Lines 114 to 118 in 859198c

  	/// @brief A mapping between pb_graph_nodes and the cluster placement primitive.
  	///
  	/// TODO: This could be stored more efficiently if each t_pb_graph_node had a
  	/// unique ID per cluster.
  	std::unordered_map<const t_pb_graph_node*, t_cluster_placement_primitive*> pb_graph_node_placement_primitive;

• 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!
  

  vtr-verilog-to-routing/vpr/src/pack/cluster_placement.cpp

  Lines 151 to 164 in 859198c

  	t_cluster_placement_stats* cluster_placement_stats = new t_cluster_placement_stats;
  	*cluster_placement_stats = t_cluster_placement_stats();
  	// TODO: This initialization may be able to be made more efficient.
  	// The reset and setting the mode can be done while loading the placement
  	// stats.
  	if (!is_empty_type(cluster_type)) {
  	cluster_placement_stats->curr_molecule = nullptr;
  	load_cluster_placement_stats_for_pb_graph_node(cluster_placement_stats,
  	cluster_type->pb_graph_head);
  	}
  	reset_cluster_placement_stats(cluster_placement_stats);
  	set_mode_cluster_placement_stats(cluster_placement_stats,
  	cluster_type->pb_graph_head,
  	cluster_mode);

[ZohairZaidi]

Hi @AlexandreSinger , for the intra cluster renaming, I know we talked about keeping the name short but i believe intra_cluster_placement_stats is the best one to choose here.

[AlexandreSinger]

@ZohairZaidi Sounds good. It was not a requirement to make the name shorter; it was just a nice to have. Its more important that the name is clear.