Qiskit / qiskit / 16950907807

88%

Build Type

push

github

Committed by web-flow

Commit Message

Collapse Sabre nodes with no routing implications (#14607)

* Collapse Sabre nodes with no routing implications

Not all nodes in the `SabreDAG` actually imply additional routing
constraints.  For example, a 2q gate immediately following a prior 2q
gate on the same qubits doesn't need to be routed; it's automatically
valid as soon as its predecessor is.  Similarly, 1q gates (without
additional classical wires) never impact routing and can be folded into
previous instructions.

More formally, a `Synchronize` node whose incoming edges are all from
the same predecessor (or are at the start of the circuit) does not
actually synchronise anything, and can be folded into any preceding
node.  A `TwoQ` node whose incoming edges are all from the same
predecessor can be folded into that predecessor if it is another `TwoQ`
node (even if there were already intermediate `Synchronize` nodes folded
into that `TwoQ` node).  `ControlFlow` nodes always have to be
considered by the router, because they need to be recursed into.

Collapsing these nodes as part of the `SabreDAG` construction has a few
benefits:

- In layout, when we keep multiple versions of a `SabreDAG`
  around, we have to store less memory, especially because we can
  entirely throw away all tracking of the collapsed DAG nodes, since we
  never need to rebuild afterwards.

- In routing, when we look ahead to populate the extended set, we no
  longer need to have the separate `visit_now` queue because all the
  nodes (and more!) that we would "look through" to make a DFS over the
  2q gates are now automatically folded into the preceding 2q gate
  already.  The behaviour is not entirely identical (the handling of
  wide `Synchronize` items can be slightly different), but the spirit is
  still there, and the handling is much easier.

- When populating the extended set, runs of 2q gates can no longer be
  multiply counted.  Previously, a run _could_ saturate the extended
  set, biasing the algorithm toward... (continued)

Run Details

65 of 68 new or added lines in 2 files covered. (95.59%)

16 existing lines in 5 files now uncovered.

87243 of 98853 relevant lines covered (88.26%)

508901.63 hits per line