OpenROAD icon indicating copy to clipboard operation
OpenROAD copied to clipboard

drt: Better Dynamic Programming (DP) Nodes and Elimination of getNestedIdx

Open bnmfw opened this issue 1 year ago • 3 comments

This PR is branched from #5872 and is waiting for it to merge.

std::vector<FlexDPNode>& nodes is a convoluted data structure, it has a non intuitive way of indexing nodes and holds a lot of empty data. This is the first PR in a sequences that will refactor this structure to be std::vector<std::vector<FlexDPNode>>& nodes, which is a more intuitive data structure for it and will make the code more readable.

Here are the changes and how they contribute to this objective:

FlexDPNode Decoupling from old nodes structure

The FlexDPNode object holds a the private prev_node_idx_ which is the index of the previous node in the nodes structure. This was changed so now it holds a pointer to the node itself, if one exists.

Other changes were made to the object adding auxiliary methods to make the code more readable, here are some examples:

  • (curr_node->hasPrevNode()) reads better than (curr_node->getPrevNodeIdx() != -1)
  • (prev_node->isSource() || curr_node->isDrain()) reads better than if (prev_idx_1 == -1 || curr_idx_1 == (int) insts.size())

The use of idx_ as a std::pair<int,int> allows for getting both values without the use of getNestedIdx() which leads to the second change

Elimination of getNestedIdx()

As code was refactored, getting the composed idx directly from node was more convenient and direct than using getNestedIdx(), so it was completely eliminated to only get idx from nodes.

This required both getEdgeCost() functions to get FlexDPNode* as inputs, instead of node indexes.

bnmfw avatar Oct 08 '24 17:10 bnmfw