Skip to content

greedy_topological_sort in musical score #1640

Open
@mpharrigan

Description

@mpharrigan

Similar to #1636, the get_musical_score_data function for displaying traditional, "musical score"-style circuit diagrams uses a topological sort to order the bloq instances within a decomposition.

  • This should be changed to use greedy_topological_sort to match our expected heuristic of delaying allocations and hurrying frees
  • It's not a straightforward replacement, since we're using topological_generations and using the generation index as part of our musical score data. The networkx function we're using in greedy_topological_sort doesn't return the generations -- just a sort order
  • We're theoretically using the generation index, but we're not using it in practice. It's part of the MusicalScoreData and could be used by a better drawing routine to group subbloqs that can be executed in parallel, but our simple drawing routine doesn't do that right now, so you can use greedy_topological_sort and put garbage data in the topo_gen field and not observe any ill effects. This is how I made the diagram in the linked issue.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions