Fix virtual/physical-qubit distinction in Sabre #10712
Conversation
|
One or more of the the following people are requested to review this:
|
5250ae6 to
d473402
Compare
Pull Request Test Coverage Report for Build 5984811233
💛 - Coveralls |
`SabreLayout` in particular previously had a very confused notion of virtual and physical qubits in Rust space; on each iteration, it rewrote the `SabreDAG` to "apply" a layout. This is not logically what `SabreDAG` represents, though; that defines the circuit purely in terms of virtual qubits, which by definition do not change as the mapping of them to physical qubits changes. This commit modifies that internal logic so that there is a clear distinction between the virtual DAG and the changing layout. This significantly simplies the logic within the Sabre layout Rust component. This commit is RNG-compatible with its parent. The Python entry points to the Rust components of both layout and routing are modified to return a final permutation, rather than a final layout, as this is what `TranspileLayout.final_layout` actually is. The application of the Sabre result to a DAG is also updated to reflect the correct virtual/physical relationship. With the roles of everything clarified, this now means that in the Sabre layout case, it automatically does the job of `ApplyLayout` _and_ the subsequent swap-mapping in one iteration, rather than rewriting the DAG once with `ApplyLayout` only to rewrite it immediately after with the swap-mapped form; the initial layout is after all only valid as far as the first inserted swap. The Sabre routing inputs are slightly tweaked, so the clone of the layout that the routing pass mutates to track its state as it progresses happens internally. _Technically_, there could have been situations where it was preferable for the caller in Rust-space to give the output object (if it didn't care about losing the initial layout), but in practice, we always cloned on entry. The cost of the layout clone is not high even in the worst case, and this makes the ownership, mutation and return-value interfaces clearer.
d473402 to
a09d212
Compare
|
The benchmark suite currently doesn't really capture any performance changes from this PR, but locally I've found that it is definitely an improvement in the reconstruction speed of the DAG, particularly after Sabre layout, just by nature of skipping some of the copy and rewrite handling when outputting the swap gates onto the DAG. For this circuit: when instrumented with A ~12% improvement in layout performance is pretty good going here, considering this PR isn't even meant to be the performance focussed one. This is just the effect of tidying up all the logic; we need to do less to unpick the confused layouts during reconstruction now, so it's all easier. |
| @@ -39,16 +51,18 @@ impl SabreDAG { | |||
| num_clbits: usize, | |||
| nodes: Vec<(usize, Vec<usize>, HashSet<usize>)>, | |||
| node_blocks: HashMap<usize, Vec<SabreDAG>>, | |||
| ) -> PyResult<Self> { | |||
| ) -> Self { | |||
There was a problem hiding this comment.
Hmm, nothing was returning an error before?
There was a problem hiding this comment.
There's no detection in here of failure, though I guess Rust would panic if fed "qubits" or "clbits" that are out of range. If we're worried about that, we could (possibly should) add proper error handling, but maybe in a separate PR?
There was a problem hiding this comment.
See #10724 for a possible change here.
There was a problem hiding this comment.
Oh, I wasn't necessarily suggesting we should be returning an error here. I was more just surprised that nothing complained about us having a result return without an error anywhere in the function. I was assuming clippy or something would see we only returned Ok(..) and would have suggested dropping the result (although maybe PyResult isn't tracked like that)
There was a problem hiding this comment.
If it's a public function, I guess clippy couldn't complain about the return value because it could be that it's a defined part of the interface that you (for example) can use the function object as having a particular type in a different crate. But also the (spelling of the) ! type to make infallible Result<_, !> types is relatively new as well, so it may well be that clippy just doesn't care about unnecessary result wrapping.
There was a problem hiding this comment.
Also about the error: I feels a shade nicer to check and error, but I don't feel strongly about it. We can either merge or close #10724 as people prefer.
| swap_qargs = [canonical_register[swap[0]], canonical_register[swap[1]]] | ||
| apply_gate( | ||
| mapped_dag, | ||
| DAGOpNode(op=SwapGate(), qargs=swap_qargs), |
There was a problem hiding this comment.
I'm glad to see this oddity disappear. There wasn't ever a real reason we should have been manually creating dag nodes.
There was a problem hiding this comment.
LGTM overall as well. I remember wondering why it was necessary to walk the SabreDAG to manually adjust the indices inside SabreLayout while adding control flow support. These changes make the separation a lot clearer.
I also like that you got rid of the oddness of us moving a layout into swap_map_trial and then out of it on return, which previously felt like it was obfuscating the semantics of what was really going on.
| let layout_dag = apply_layout(&dag_forward, &initial_layout); | ||
| let mut pass_final_layout = NLayout::generate_trivial_layout(num_physical_qubits); | ||
| build_swap_map_inner( | ||
| for dag in [&dag_no_control_forward, &dag_no_control_reverse] { |
Co-authored-by: Matthew Treinish <mtreinish@kortar.org> Co-authored-by: Kevin Hartman <kevin@hart.mn>
| @@ -97,7 +96,7 @@ pub fn sabre_layout_and_routing( | |||
| }; | |||
| ( | |||
| res.0, | |||
| res.1, | |||
| PyArray::from_vec(py, res.1).into(), | |||
There was a problem hiding this comment.
Hah I didn't even know this method or from_iter() existed. Looking at the rust-numpy source it looks like it just calls into_pyarray() internally. I wonder if this just my knowledge of the library is several years out of date and these didn't exist when I started using it. It's a little bit more ergonomic looking than the .into_pyarray() I used everywhere else to do a no copy numpy array creation.
* Fix virtual/physical-qubit distinction in Sabre `SabreLayout` in particular previously had a very confused notion of virtual and physical qubits in Rust space; on each iteration, it rewrote the `SabreDAG` to "apply" a layout. This is not logically what `SabreDAG` represents, though; that defines the circuit purely in terms of virtual qubits, which by definition do not change as the mapping of them to physical qubits changes. This commit modifies that internal logic so that there is a clear distinction between the virtual DAG and the changing layout. This significantly simplies the logic within the Sabre layout Rust component. This commit is RNG-compatible with its parent. The Python entry points to the Rust components of both layout and routing are modified to return a final permutation, rather than a final layout, as this is what `TranspileLayout.final_layout` actually is. The application of the Sabre result to a DAG is also updated to reflect the correct virtual/physical relationship. With the roles of everything clarified, this now means that in the Sabre layout case, it automatically does the job of `ApplyLayout` _and_ the subsequent swap-mapping in one iteration, rather than rewriting the DAG once with `ApplyLayout` only to rewrite it immediately after with the swap-mapped form; the initial layout is after all only valid as far as the first inserted swap. The Sabre routing inputs are slightly tweaked, so the clone of the layout that the routing pass mutates to track its state as it progresses happens internally. _Technically_, there could have been situations where it was preferable for the caller in Rust-space to give the output object (if it didn't care about losing the initial layout), but in practice, we always cloned on entry. The cost of the layout clone is not high even in the worst case, and this makes the ownership, mutation and return-value interfaces clearer. * Fix out-of-date types Co-authored-by: Matthew Treinish <mtreinish@kortar.org> Co-authored-by: Kevin Hartman <kevin@hart.mn> * Improve efficiency of interfaces --------- Co-authored-by: Matthew Treinish <mtreinish@kortar.org> Co-authored-by: Kevin Hartman <kevin@hart.mn>
This has been a bug since Qiskitgh-10712, but wasn't caught by the integration test in the test suite because that constructs a backend with all-to-all connectivity, so the layout stage was short-circuiting out after VF2.
This has been a bug since Qiskitgh-10712, but wasn't caught by the integration test in the test suite because the circuit has a perfect layout, so the layout stage was short-circuiting out after VF2.
This has been a bug since gh-10712, but wasn't caught by the integration test in the test suite because the circuit has a perfect layout, so the layout stage was short-circuiting out after VF2.
…14190) * Fix circuit-metadata propagation in `SabreLayout` (#14186) This has been a bug since gh-10712, but wasn't caught by the integration test in the test suite because the circuit has a perfect layout, so the layout stage was short-circuiting out after VF2. (cherry picked from commit 2504bde) # Conflicts: # qiskit/transpiler/passes/layout/sabre_layout.py * Fix merge conflicts * Adjust plugins used in testing for 1.4.x --------- Co-authored-by: Jake Lishman <jake.lishman@ibm.com> Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
Summary
SabreLayoutin particular previously had a very confused notion of virtual and physical qubits in Rust space; on each iteration, it rewrote theSabreDAGto "apply" a layout. This is not logically whatSabreDAGrepresents, though; that defines the circuit purely in terms of virtual qubits, which by definition do not change as the mapping ofthem to physical qubits changes.
This commit modifies that internal logic so that there is a clear distinction between the virtual DAG and the changing layout. This significantly simplies the logic within the Sabre layout Rust component. This commit is RNG-compatible with its parent.
The Python entry points to the Rust components of both layout and routing are modified to return a final permutation, rather than a final layout, as this is what
TranspileLayout.final_layoutactually is.The application of the Sabre result to a DAG is also updated to reflect the correct virtual/physical relationship. With the roles of everything clarified, this now means that in the Sabre layout case, it automatically does the job of
ApplyLayoutand the subsequent swap-mapping in one iteration, rather than rewriting the DAG once withApplyLayoutonly to rewrite it immediately after with the swap-mapped form; the initial layout is after all only valid as far as the first inserted swap.The Sabre routing inputs are slightly tweaked, so the clone of the layout that the routing pass mutates to track its state as it progresses happens internally. Technically, there could have been situations where it was preferable for the caller in Rust-space to give the output object (if it didn't care about losing the initial layout), but in practice, we always cloned on entry. The cost of the layout clone is not high even in the worst case, and this makes the ownership, mutation and return-value interfaces clearer.
Details and comments
I came across this when trying to move more of the layout application behaviour from Sabre into Rust space; at the moment, there's a lot of quite split logic that means that the Rust component of the Sabre algorithm doesn't have all the information it needs, despite appearances. This refactor now means that a call to
build_swap_map_innersupplies it with all the information needed to apply the layout to the original DAG as well, and simplifies a lot of the data.In practice, it would be far easier for reconstruction if the Rust Sabre components output its swaps in terms of physical qubits rather than virtual ones - we're applying swaps to the physical circuit not the virtual one. This would avoid a lot of faffing around that we have to do during the reconstruction at the moment to handle the ancilla allocations correctly; there's no reason in principle that
SabreSwapactually needs its input DAG to be full width other than it's difficult to apply the virtual swaps without it. This especially hurtsSabreLayouton disjoint coupling maps, since the ancilla allocation doesn't happen until after the disjoint layout has been done, so we have to run around trying to work out which ancillas were effectively mapped to each component.Performance:
ApplyLayoutfromSabreLayoutwhen doing both the layout and routing together, which may be a small performance boost for large circuits that are already close to routed (the relative impact is smaller if we insert many swaps)DAGOpNodetransforming logic in the Sabre reconstruction is now simpler and involves less copying just to throw a node away again, so there might be a little win there.I'll run some actual benchmarks a bit later, but I'm not worried if this has a neutral effect on performance; this PR is just meant to be clarifying all the logic ahead of a complete rewrite of the Sabre routing reconstruction that's actually intended to be more performant, and to reduce memory usage in the output. edit: I ran the whole suite, and it was neutral in benchmarking.