Skip to content

Optimize run time and memory footprint to build the choke point data structures in routing #2782

Open
@vaughnbetz

Description

@vaughnbetz

We turned router_opt_choke_points on by default so flat routing will converge reliably on various architectures. That makes it important to optimize the data structure memory overhead and runtime for the relevant data structures, which are built from the rr-graph once the design placement is known (hence they are large -- there are some for every used cluster).

Possibly you could flyweight this, but it would be complex (need to check if you have exactly the same cluster & net combination) and my suspicion is there won't be that many identical copies.

Probably a better approach would be to separate the cross product of nets x clusters data structure into one per net and one per cluster, if at all possible. It would be good to check the scaling behaviour with design size of the current code -- is it linear in runtime and memory footprint? If anything is O(n^2) that would be high priority to fix. Please post the per-circuit runtime increase and memory increase with this option on for the Titan designs; that should help us see the scaling.

Relevant PR is #2777

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions