qiskit
qiskit copied to clipboard
Qiskit
Expose Sabre heuristic configuration to Python
Summary
This exposes the entirety of the configuration of the Sabre heuristic to Python space, making it modifiable without recompilation. This includes some additional configuration options that were not previously easily modifiable, even with recompilation:
- the base weight of the "basic" component can be adjusted
- the weight of the "basic" and "lookahead" components can be adjusted to either use a constant weight (previously not a thing) or use a weight that scales with the size of the set (previously the only option).
- the "decay" component is now entirely separated from the "lookahead" component, so in theory you can now have a decay without a lookahead.
This introduces a tracking Vec that stores the scores of all the swaps encountered, rather than just dynamically keeping hold of the best swaps. This has a couple of benefits:
- with the new dynamic structure for heuristics, this is rather more efficient because each heuristic component can be calculated in separate loops over the swaps, and we don't have to branch within the innermost loop.
- it makes it possible in the future to try things like assigning probabilities to each swap and randomly choosing from all of them, not just the best swaps. This is something I've actively wanted to try for quite some time.
The default heuristics in the transpiler-pass creators for the basic, lookahead and decay strings are set to represent the same heuristics as before, and this commit is entirely RNG compatible with its predecessor (technically for huge problems there's a possiblity that pulling out some divisions into multiplications by reciprocals will affect the floating-point maths enough to modify the swap selection).
Details and comments
I need to run more formal benchmarks on this to verify the claims in the commit message - it's possible I didn't do it sufficiently well earlier, and at any rate I no longer have the data to hand. (edit: come to think of it, I'm not even sure I ran the tests...)
I so far have not documented the newly available API stuff from Rust-space here, because I didn't necessarily want to commit to it as public interface, but did want to make it available for research - certainly I found this very useful in investigating Sabre, even if I haven't had time to turn that research into a full set of tweaked heuristics yet or anything. Happy to discuss whether we should commit to this as public API - there's probably not too much risk.
One or more of the the following people are requested to review this:
- @Eric-Arellano
@Qiskit/terra-core@kevinhartman@mtreinish
Pull Request Test Coverage Report for Build 8728467376
Warning: This coverage report may be inaccurate.
This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.
- For more information on this, see Tracking coverage changes with pull request builds.
- To avoid this issue with future PRs, see these Recommended CI Configurations.
- For a quick fix, rebase this PR at GitHub. Your next report should be accurate.
Details
- 137 of 241 (56.85%) changed or added relevant lines in 7 files are covered.
- 10 unchanged lines in 2 files lost coverage.
- Overall coverage decreased (-0.1%) to 89.131%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| qiskit/transpiler/passes/routing/sabre_swap.py | 6 | 7 | 85.71% |
| crates/accelerate/src/sabre/route.rs | 70 | 74 | 94.59% |
| crates/accelerate/src/sabre/heuristic.rs | 45 | 144 | 31.25% |
| <!-- | Total: | 137 | 241 |
| Files with Coverage Reduction | New Missed Lines | % |
|---|---|---|
| crates/qasm2/src/lex.rs | 4 | 92.11% |
| crates/qasm2/src/parse.rs | 6 | 97.15% |
| <!-- | Total: | 10 |
| Totals | |
|---|---|
| Change from base Build 8728350061: | -0.1% |
| Covered Lines: | 60364 |
| Relevant Lines: | 67725 |
💛 - Coveralls
ASV highlighted an unexpected change in the benchmarks - the output from Sabre has changed somewhat from #11977, which wasn't intended to have affected the output in any way. I'll mark this as on hold until we've figured that out.
Ok, with #12172 cherry-picked on top of this branch, the same set of benchmarks that I ran in #12172 show RNG compatibility with main from before #11977 (and so with #12172 as well), an potentially a couple of performance benefits:
Benchmarks that have improved:
before after ratio
[4ff0fa2f] [e91b7822]
<var/qpy~3> <sabre/dynamic-heuristic>
- 3.80±0.09s 3.10±0.03s 0.82 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(1081, 10, 'decay')
- 371±8ms 326±3ms 0.88 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(409, 10, 'decay')
Benchmarks that have stayed the same:
before after ratio
[4ff0fa2f] [e91b7822]
<var/qpy~3> <sabre/dynamic-heuristic>
2.31±0.01s 2.14±0.04s 0.92 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(1081, 10, 'lookahead')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(1081, 100, 'decay')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(1081, 100, 'lookahead')
33.4±0.8ms 32.9±0.6ms 0.98 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(115, 10, 'decay')
31.5±0.6ms 31.5±0.3ms 1.00 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(115, 10, 'lookahead')
289±4ms 282±8ms 0.97 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(115, 100, 'decay')
273±5ms 266±10ms 0.98 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(115, 100, 'lookahead')
391±3ms 375±6ms 0.96 quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(409, 10, 'lookahead')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(409, 100, 'decay')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(409, 100, 'lookahead')
11498 11498 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(1081, 10, 'decay')
13134 13134 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(1081, 10, 'lookahead')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(1081, 100, 'decay')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(1081, 100, 'lookahead')
557 557 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(115, 10, 'decay')
547 547 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(115, 10, 'lookahead')
5231 5231 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(115, 100, 'decay')
5663 5663 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(115, 100, 'lookahead')
2955 2955 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(409, 10, 'decay')
3945 3945 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(409, 10, 'lookahead')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(409, 100, 'decay')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(409, 100, 'lookahead')
217448 217448 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(1081, 10, 'decay')
189590 189590 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(1081, 10, 'lookahead')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(1081, 100, 'decay')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(1081, 100, 'lookahead')
4419 4419 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(115, 10, 'decay')
4351 4351 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(115, 10, 'lookahead')
44362 44362 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(115, 100, 'decay')
44711 44711 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(115, 100, 'lookahead')
42115 42115 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(409, 10, 'decay')
47894 47894 1.00 quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(409, 10, 'lookahead')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(409, 100, 'decay')
n/a n/a n/a quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(409, 100, 'lookahead')
18.7±0.7ms 18.1±0.2ms 0.97 queko.QUEKOTranspilerBench.time_transpile_bigd(0, 'sabre')
44.3±1ms 43.2±0.3ms 0.98 queko.QUEKOTranspilerBench.time_transpile_bigd(0, None)
14.7±0.2ms 14.4±0.2ms 0.98 queko.QUEKOTranspilerBench.time_transpile_bigd(1, 'sabre')
14.3±1ms 13.5±0.2ms 0.94 queko.QUEKOTranspilerBench.time_transpile_bigd(1, None)
20.3±0.7ms 20.3±0.2ms 1.00 queko.QUEKOTranspilerBench.time_transpile_bigd(2, 'sabre')
19.1±2ms 17.1±0.4ms ~0.90 queko.QUEKOTranspilerBench.time_transpile_bigd(2, None)
53.9±1ms 55.4±1ms 1.03 queko.QUEKOTranspilerBench.time_transpile_bigd(3, 'sabre')
45.1±0.6ms 45.1±0.7ms 1.00 queko.QUEKOTranspilerBench.time_transpile_bigd(3, None)
145±1ms 148±3ms 1.03 queko.QUEKOTranspilerBench.time_transpile_bntf(0, 'sabre')
366±5ms 378±10ms 1.03 queko.QUEKOTranspilerBench.time_transpile_bntf(0, None)
157±3ms 154±5ms 0.98 queko.QUEKOTranspilerBench.time_transpile_bntf(1, 'sabre')
35.4±1ms 33.8±0.9ms 0.95 queko.QUEKOTranspilerBench.time_transpile_bntf(1, None)
332±4ms 322±6ms 0.97 queko.QUEKOTranspilerBench.time_transpile_bntf(2, 'sabre')
59.0±1ms 58.8±1ms 1.00 queko.QUEKOTranspilerBench.time_transpile_bntf(2, None)
512±8ms 505±20ms 0.99 queko.QUEKOTranspilerBench.time_transpile_bntf(3, 'sabre')
136±3ms 140±5ms 1.03 queko.QUEKOTranspilerBench.time_transpile_bntf(3, None)
151±1ms 149±3ms 0.99 queko.QUEKOTranspilerBench.time_transpile_bss(0, 'sabre')
2.04±0.01s 2.08±0.03s 1.02 queko.QUEKOTranspilerBench.time_transpile_bss(0, None)
133±2ms 129±1ms 0.97 queko.QUEKOTranspilerBench.time_transpile_bss(1, 'sabre')
82.0±1ms 77.7±1ms 0.95 queko.QUEKOTranspilerBench.time_transpile_bss(1, None)
398±2ms 399±8ms 1.00 queko.QUEKOTranspilerBench.time_transpile_bss(2, 'sabre')
222±5ms 215±5ms 0.97 queko.QUEKOTranspilerBench.time_transpile_bss(2, None)
661±10ms 644±10ms 0.97 queko.QUEKOTranspilerBench.time_transpile_bss(3, 'sabre')
341±3ms 342±10ms 1.00 queko.QUEKOTranspilerBench.time_transpile_bss(3, None)
287 287 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(0, 'sabre')
246 246 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(0, None)
54 54 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(1, 'sabre')
65 65 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(1, None)
41 41 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(2, 'sabre')
45 45 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(2, None)
86 86 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(3, 'sabre')
81 81 1.00 queko.QUEKOTranspilerBench.track_depth_bigd_optimal_depth_45(3, None)
672 672 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(0, 'sabre')
850 850 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(0, None)
394 394 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(1, 'sabre')
34 34 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(1, None)
299 299 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(2, 'sabre')
30 30 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(2, None)
200 200 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(3, 'sabre')
45 45 1.00 queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(3, None)
836 836 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(0, 'sabre')
1368 1368 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(0, None)
370 370 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(1, 'sabre')
79 79 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(1, None)
361 361 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(2, 'sabre')
67 67 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(2, None)
261 261 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(3, 'sabre')
59 59 1.00 queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(3, None)
No need for the "on hold" now.
For the two questions in your review comment:
This PR already does a bit to manage the complexity and runtime cost of unused heuristics; there's catches and guards in various places to avoid doing calculations that aren't involved in any given heuristic. Some things about the "efficiency of adding a new heuristic" are going to depend on the heuristic in question; if everything's purely additive and non-interacting, it feels fairly straightforwards to add more on top. The existing decay heuristic is defined a bit more messily, so that needed a bit more complex logic to get it to interact well, but I think it's as much a function of the heuristic itself as the code used to implement it.
For API re-use and the like: that's of course good if we can manage it, but adding new heuristics will likely usually involving doing more speculative calculations based on the current state, so I'd imagine that they usually will involve doing a fair amount of additional coding. The current interfaces are meant to be roughly usable, but if a new heuristic needed a totally different structure, that'd be ok. It's no good trying to predict that before we need it, though - we'd likely make the code harder to understand and slower to run, and there'd be no guarantee that we'd get things right.
We can in general expose more to Python space if we want for controllability, though I don't immediately see any places that aren't dynamically controlled. Did you have something in mind?
Pull Request Test Coverage Report for Build 10162000789
Details
- 135 of 240 (56.25%) changed or added relevant lines in 7 files are covered.
- 6 unchanged lines in 3 files lost coverage.
- Overall coverage decreased (-0.1%) to 89.647%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| qiskit/transpiler/passes/routing/sabre_swap.py | 6 | 7 | 85.71% |
| crates/accelerate/src/sabre/route.rs | 70 | 74 | 94.59% |
| crates/accelerate/src/sabre/heuristic.rs | 43 | 143 | 30.07% |
| <!-- | Total: | 135 | 240 |
| Files with Coverage Reduction | New Missed Lines | % |
|---|---|---|
| crates/qasm2/src/expr.rs | 1 | 94.02% |
| crates/accelerate/src/two_qubit_decompose.rs | 1 | 90.61% |
| crates/qasm2/src/lex.rs | 4 | 92.11% |
| <!-- | Total: | 6 |
| Totals | |
|---|---|
| Change from base Build 10161705193: | -0.1% |
| Covered Lines: | 67013 |
| Relevant Lines: | 74752 |
💛 - Coveralls
Thanks for your work! I appreciate the clarification on managing the complexity and runtime costs of unused heuristics. I agree that the specifics of integrating new heuristics will largely depend on the nature of the heuristic itself. Regarding the API design and usability, your points about the speculative nature of new heuristics and the potential need for additional coding make a lot of sense.
I didn't have anything specific in mind regarding exposing more to Python space. I was more curious about the overall approach and potential strategies for future enhancements.
