[Prepacker] Pack Molecule Data Structure Clarity

[AlexandreSinger]

The molecule data structure is defined here:

vtr-verilog-to-routing/vpr/src/base/vpr_types.h

Lines 369 to 410 in f520c17

	/**
	* @brief Represents a grouping of atom blocks that match a pack_pattern,
	* these groups are intended to be placed as a single unit during packing
	*
	* Store in linked list
	*
	* A chain is a special type of pack pattern. A chain can extend across multiple logic blocks.
	* Must segment the chain to fit in a logic block by identifying the actual atom that forms the root of the new chain.
	* Assumes that the root of a chain is the primitive that starts the chain or is driven from outside the logic block
	*
	* Data members:
	*
	* type : either a single atom or more atoms representing a packing pattern
	* pack_pattern : if not a single atom, this is the pack pattern representing this molecule
	* atom_block_ids : [0..num_blocks-1] IDs of atom blocks that implements this molecule, indexed by
	* t_pack_pattern_block->block_id
	* chain_info : if this is a molecule representing a chained pack pattern, this data structure will
	* hold the data shared between all molecules forming a chain together.
	* valid : whether the molecule is still valid for packing or not.
	* num_blocks : maximum number of atom blocks that can fit in this molecule
	* root : index of the pack_pattern->root_block in the atom_blocks_ids. root_block_id = atom_block_ids[root]
	* base_gain : intrinsic "goodness" score for molecule independent of rest of netlist
	* next : next molecule in the linked list
	*/
	class t_pack_molecule {
	public:
	/* general molecule info */
	bool valid;
	float base_gain;
	enum e_pack_pattern_molecule_type type;
	/* large molecules info */
	t_pack_patterns* pack_pattern;
	int root;
	int num_blocks;
	std::vector<AtomBlockId> atom_block_ids;
	std::shared_ptr<t_chain_info> chain_info;
	t_pack_molecule* next;
	// a molecule is chain is it is a forced pack and its pack pattern is chain
	bool is_chain() const { return type == MOLECULE_FORCED_PACK && pack_pattern->is_chain; }
	};

I have noticed that there are some parts of the data structure that are not clear and a bit wasteful. I think this struct should be reworked in the context of the Prepacker to make it easier to work with.

• The atom_blk_ids member is confusing. This is what caused me to look into this. Some of the elements of this vector may be invalid. The reason is that this is not a list of atoms in the molecule; it is a mapping between the IDs in the pack pattern and the molecule atoms. The invalid entries are where the pack pattern is not completely full. This is very confusing but also not very good for performance. Instead we should have an ordered list of all atom blocks in the molecule, and then another list which stores the pattern ID for each of those atoms. That or the documentation should be made more clear.
• The valid member is hardly used anymore and should be removed. This variable just says if this molecule has been packed already or not, which is now being stored in the Cluster Legalizer class. This should be removed / phased out.
• The num_blocks member is poorly named. It is not the number of blocks currently in the molecule, it is the maximum number of blocks that can be stored in the molecule. I bet you this was used to allocate a C-style array, but in recent years we moved to a vector. This variable can probably be removed.
• The root member is very strange. Why store the ID in the array instead of the AtomBlockId itself (they are both basically integers). This should be investigated and maybe cleaned up.
• The base_gain member is specific to the clustering algorithm being used. This should not be in the molecule struct in my opinion.
• The pack pattern part of this struct is a bit confusing. It may be a good idea to encapsulate that into another struct to make it clear.
• The molecules should not be a linked list. Instead we should have MoleculeIDs which the Prepacker manages. Having unique IDs for each molecule is a good idea and can make traversing the molecules much more efficient. Since we do not care about the order of the molecules list (and we do not expect to be adding or removing molecules often within the list), storing in a standard vector would actually be more performant!
• The declaration of this type should be moved to the Prepacker. It only makes sense in the context of the Prepacker.
• We should add an independent verifier class which verifies that the Prepacker created all the molecules correctly and everything works as expected. This also creates a clear interface for what user of the Prepacker should expect to see.