Add star to linear pre-routing pass #11387
Conversation
This commit adds a new transpiler pass StarPreRouting that adds a dedicated transformation that finds a star graph connectivity subcircuit and replaces it with a linear routing equivalent. This makes the circuit easier for a routing pass to work with.
Pull Request Test Coverage Report for Build 8926693870Warning: 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.
Details
💛 - Coveralls |
This commit adds functionality to the built-in routing passes for composing an existing final layout with the routing permutation. In PRs Qiskit#9523 and Qiskit#11387 we're adding new passes that introduce a permutation prior to routing that needs to be tracked for the final output layout to be valid. To faciliate this a new method compose() is added to the Layout class which will combine the two layouts. Then the built-in routing passes are updated to call compose when a layout has already been set.
There was a problem hiding this comment.
I was playing a bit with this code, so decided to write a few high-level comments.
This is a very cool pass that will greatly improve the quality of compiled circuits for various sparsely connected architectures.
The main question that I have (and this is more general than this PR) is that (if I understand correctly) this star-to-line pass will run before routing, with the intuition that for sparsely connected architectures we will find better layout + routing when the circuit consists of linear pieces rather than star pieces. If the circuit consists of a single star and the coupling graph contains a line of the right size, then VF2 will even find a perfect layout and no routing would be needed. However if there are two or more stars (or there are more 2-qubit gates), then even if the first star is mapped perfectly, Sabre might need to do many swaps before the second star, and it's not clear that the line connectivity of the second star will help. What do you think?
| for node in dag.topological_op_nodes(): | ||
| if ( | ||
| len(node.qargs) == 2 | ||
| and len(node.cargs) == 0 | ||
| and getattr(node.op, "condition", None) is None | ||
| ): | ||
| if center_node is None: | ||
| center_node = set(node.qargs) | ||
| star_sequence.append(node) | ||
| elif isinstance(center_node, set): | ||
| if node.qargs[0] in center_node: | ||
| center_node = node.qargs[0] | ||
| star_sequence.append(node) | ||
| elif node.qargs[1] in center_node: | ||
| center_node = node.qargs[1] | ||
| star_sequence.append(node) | ||
| else: | ||
| center_node = None | ||
| star_sequence = [] | ||
| else: | ||
| if center_node in node.qargs: | ||
| star_sequence.append(node) | ||
| else: | ||
| saved_center = center_node | ||
| center_node = None | ||
| elif len(node.qargs) > 2: | ||
| saved_center = center_node | ||
| center_node = None | ||
|
|
||
| # If center_node is None after we've processed the node that | ||
| # means we've broken star connectivity | ||
| if center_node is None and len(star_sequence) > 1: | ||
| star_sequences.append((star_sequence, saved_center)) | ||
| star_sequence = [] | ||
| if len(node.qargs) == 2: | ||
| center_node = set(node.qargs) | ||
| star_sequence.append(node) | ||
| if len(star_sequence) > 1 and center_node: | ||
| star_sequences.append((star_sequence, center_node)) |
There was a problem hiding this comment.
I was thinking that we have multiple passes that collect blocks of nodes according to the following general strategy:
- if the current node matches a certain condition C1 and the current node can be added to the current block while satisfying a certain other condition C2, add the current node to the current block (and continue to the next node)
- else if the current block is empty, skip the current node (and continue to the next node)
- otherwise, add the current block to the list of collected blocks, set the current block to be empty, and repeat the first step with the empty current block
This is more general than what BlockCollector can currently do since it only collects nodes matches a given filter function (corresponding to C1), while now we want to say something like this: a node can be added to a partially constructed block either when the block is empty or one of the node's qubits is equal to the center_qubit (i.e. this is what the condition C2 would look like).
If you think that having this more general set of block collection strategies would be useful, I will write a PR (I actually have code somewhere that does something similar already)
There was a problem hiding this comment.
There might be similar applications for block collection strategies like this, I'm not entirely sure though. But I can't imagine it would hurt to have the BlockCollector support this use case. I wouldn't mind having the block collection done in this pass be a bit more robust, it only works because of our default lexicographical topological sorting based on the qubit indices.
| if swap_source is None: | ||
| swap_source = center_node | ||
| new_dag.apply_operation_back( | ||
| inner_node.op, | ||
| _apply_mapping(inner_node.qargs, qubit_mapping, dag.qubits), | ||
| inner_node.cargs, | ||
| ) | ||
| prev = inner_node.qargs | ||
| processed_nodes.add(inner_node) | ||
| continue |
There was a problem hiding this comment.
Oh, I see, not including the swap gate after the very first gate is ok because it's the previous optimization all over again. At first I was surprised that applying the pass to the circuit
q_0: ──■────■────■────■──
┌─┴─┐ │ │ │
q_1: ┤ X ├──┼────┼────┼──
└───┘┌─┴─┐ │ │
q_2: ─────┤ X ├──┼────┼──
└───┘┌─┴─┐ │
q_3: ──────────┤ X ├──┼──
└───┘┌─┴─┐
q_4: ───────────────┤ X ├
└───┘
we get
q_0: ──■────■───X─────────────────
┌─┴─┐ │ │
q_1: ┤ X ├──┼───┼─────────────────
└───┘┌─┴─┐ │
q_2: ─────┤ X ├─X───■───X─────────
└───┘ ┌─┴─┐ │
q_3: ─────────────┤ X ├─X───■───X─
└───┘ ┌─┴─┐ │
q_4: ─────────────────────┤ X ├─X─
└───┘
but I see now that the line consists of qubits 1 -- 0 -- 2 -- 3 -- 4.
And you can drop the very last swap gate, since this already synthesizes the star up to a permutation gate, so the last swap can be absorbed into it.
| continue | ||
| else: | ||
| new_dag.apply_operation_back(node.op, node.qargs, node.cargs) | ||
| return new_dag |
There was a problem hiding this comment.
To account for the induced permutation of qubits, would it make sense to add a PermutationGate at the end of the star rather than modifying the layout directly? And we already have the ElidePermutations pass that would be able to process these permutations.
There was a problem hiding this comment.
Well ElidePermutations hasn't merged yet, I'm still trying to figure out the layout issues there. But yeah we could in theory combine them, but yeah I like the idea of pairing them. I do wonder if there is a use case for this without adding the permutation, but doing this would work well. Maybe have it as a flag, like reverse_permutation=True, in the constructor to control whether we insert the PermutationGate or not?
I was thinking we would run this before the |
|
There might be some problems with treating single-qubit gates. For example, the following circuit gets transformed into Intuitively, this is because the pass only collects sequences of 2-qubit gates while ignoring 1-qubit gates (which is probably fine, since 1-qubit gates pose no problems for routing), but then forgets to take these 1-qubit gates into account (see how all of the Hadamard gates got pushed out to the end of the circuit). |
|
Another random thought is that star-to-line translation may create gate cancellation opportunities, i.e. we may want to rerun passes like inverse cancellation after star-to-line but before layout or routing. |
Yeah, that's a good point. I think when we're adding the pass to the preset pass managers we can determine the best place to add this. I'm wondering if we'll want to have a do while loop for initial optimization like we do for final optimization |
This commit fixes two related issues. The first is that it fixed the handling of 1q gates in the middle of a star sequence. The sequence collection was correctly skipping the 1q gates, but when we reassembled the circuit and applied the linear routing it would incorrectly build the routing without the 1q gates. This would result in the 1q gates being pushed after the star. At the same time the other related issue was that the permutations caused by the swap insertions were not taken into account for subsequent gates. This would result in gates being placed on the wrong bits and incorrect results being returned.
This was a good catch, I've pushed up a fix for this here: 8cc0587 |
* Compose multiple final_layout attributes in routing This commit adds functionality to the built-in routing passes for composing an existing final layout with the routing permutation. In PRs #9523 and #11387 we're adding new passes that introduce a permutation prior to routing that needs to be tracked for the final output layout to be valid. To faciliate this a new method compose() is added to the Layout class which will combine the two layouts. Then the built-in routing passes are updated to call compose when a layout has already been set. * adding inverse and to_permutation methods, tests, updating release notes --------- Co-authored-by: AlexanderIvrii <alexi@il.ibm.com>
|
|
|
Executed on a 6-qubit QFT quantum circuit, whereas A comparison on a 100-qubit QFT was done by running: This yielded the following data when barriers are included between the different 'stars' of a QFT instance: - quite a larger decrease in which yields a 16% decrease in |
|
One or more of the the following people are requested to review this:
|
|
I've moved this out of draft since @sbrandhsn finished this up! But it still has dependencies on open PRs and will need to be rebased so I've marked this as on hold to indicate this. |
There was a problem hiding this comment.
Overall this looks great to me, thanks @sbrandhsn for taking this over and getting it across the finish line! I left a few inline comments, most of them are just questions or pretty minor.
| if not isinstance(self.dag, DAGDependency): | ||
| return [pred for pred in self.dag.predecessors(node) if isinstance(pred, DAGOpNode)] | ||
| else: | ||
| return [ | ||
| self.dag.get_node(pred_id) for pred_id in self.dag.direct_predecessors(node.node_id) | ||
| ] |
There was a problem hiding this comment.
I realize this was likely ported from #11614 but were you thinking we'd want to run this with a DAGDependency? I guess there is the potential to find a bigger star if we factor in potential commutations.
There was a problem hiding this comment.
Yup, @alexanderivrii realized we could run this pass while considering commutations in #11614 so I just left it in. Should I remove the paths corresponding to DAGDependency?
There was a problem hiding this comment.
I would suggest to remove the DAGDependency path for now, and this will get optimized automatically when we finalize #11614. Thanks!
There was a problem hiding this comment.
I don't think the paths on DAGDependency are fully functional as of now - at least I have not verified it...
There was a problem hiding this comment.
No it's fine, we don't have a great story about how to use DAGDependency via the pass managers yet. But I guess it's an option for someone running things manually and doesn't hurt at all.
|
Thanks @mtreinish and @sbrandhsn for getting this completed, this is definitely going to be a super-useful pass. And thanks @jakelishman for doing this review (somehow I forgot that I was assigned to review this PR). I also looked at the code, and it looks great. In the future, we should probably refactor the star collection part of the pass into the more general block collection (i.e. finalize #11614) and replace the |
Makes sense, thanks Jake, Matthew and Sasha for reviewing this! :-) |
* Add Star to linear pre-routing pass This commit adds a new transpiler pass StarPreRouting that adds a dedicated transformation that finds a star graph connectivity subcircuit and replaces it with a linear routing equivalent. This makes the circuit easier for a routing pass to work with. * Add missing doc imports * Fix handling of 1q gates and swap tracking This commit fixes two related issues. The first is that it fixed the handling of 1q gates in the middle of a star sequence. The sequence collection was correctly skipping the 1q gates, but when we reassembled the circuit and applied the linear routing it would incorrectly build the routing without the 1q gates. This would result in the 1q gates being pushed after the star. At the same time the other related issue was that the permutations caused by the swap insertions were not taken into account for subsequent gates. This would result in gates being placed on the wrong bits and incorrect results being returned. * fixed/tested star-prerouting * Apply suggestions from code review * changed moved self.dag to a function parameter * Removing the usage of FinalizeLayout in star prerouting tests * format --------- Co-authored-by: Sebastian Brandhofer <148463728+sbrandhsn@users.noreply.github.com>
Summary
This commit adds a new transpiler pass
StarPreRoutingthat adds a dedicated transformation that finds a star graph connectivity subcircuit and replaces it with a linear routing equivalent. This makes the circuit easier for a routing pass to work with.Details and comments
TODO:
Co-Authored-By: Sebastian Brandhofer 148463728+sbrandhsn@users.noreply.github.com