Optimize shortestpath in SABRE

csookim commented 3 months ago

This PR is an addition to #1398.

Since deepcopy() makes the compiler slower, it needs to be changed.

code

Line 901 takes over 30% of the routing time.

Checklist:

[x] Reviewers confirm new code works as expected.
[x] Tests are passing.
[x] Coverage does not decrease.
[x] Documentation is updated.

csookim commented 3 months ago

Previous approach

Save the circuit after the gate is routed.

self._temporary_added_swaps: int
self._saved_circuit: CircuitMap

https://github.com/qiboteam/qibo/blob/9db9b666f67563122a5ab716ae689bfe579d333f/src/qibo/transpiler/router.py#L900-L901

Revert to the saved circuit when the number of SWAPs exceeds the threshold.

https://github.com/qiboteam/qibo/blob/9db9b666f67563122a5ab716ae689bfe579d333f/src/qibo/transpiler/router.py#L689-L693

Updated approach

Save the sequence of SWAPs.

self._temp_added_swaps: list

https://github.com/qiboteam/qibo/blob/a7a1c62850bd4e720a3cc0f90cc39df0cdc44519/src/qibo/transpiler/router.py#L817-L818

Undo all of the temporary SWAPs when the number of SWAPs exceeds the threshold.

https://github.com/qiboteam/qibo/blob/a7a1c62850bd4e720a3cc0f90cc39df0cdc44519/src/qibo/transpiler/router.py#L701-L708

Results

Average runtime of routing 100 random CZ circuits (20 qubits, 50 gates)
Trivial Placer, SABRE router, Line connectivity

Before update: 0.558s After update: 0.253s

Discussion

The undo functionality is currently implemented in CircuitMap.update(). Would it be better to create a new function undo() for this purpose?
TranspilerPipelineError is raised when the gate to be undone doesn't match the last added SWAP gate. Is there a more suitable error type for this situation?

Simone-Bordoni commented 3 months ago

Thank you for this work, the code looks nice. Regarding the two points you asked in the discussion:

For the undo I think it would be better to have a separate function.
Regarding the error type I think it would be better to raise ConnectivityError. In my Idea Connectivity error is raised every time there is some problem during routing while TranspilerPipelineError regards an error occurring in defining the pipeline for example if you forget to define the Placer.

codecov[bot] commented 3 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 99.94%. Comparing base (3d87ba7) to head (96a0bd8).

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #1408 +/- ## ======================================= Coverage 99.94% 99.94% ======================================= Files 78 78 Lines 11225 11237 +12 ======================================= + Hits 11219 11231 +12 Misses 6 6 ``` | [Flag](https://app.codecov.io/gh/qiboteam/qibo/pull/1408/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=qiboteam) | Coverage Δ | | |---|---|---| | [unittests](https://app.codecov.io/gh/qiboteam/qibo/pull/1408/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=qiboteam) | `99.94% <100.00%> (+<0.01%)` | :arrow_up: | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=qiboteam#carryforward-flags-in-the-pull-request-comment) to find out more.

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

csookim commented 3 months ago

@Simone-Bordoni , I have a question about the def test_circuit_map() function.

https://github.com/qiboteam/qibo/blob/a2f74249c40e1d76eada8b8b795b5155e1ad6374/tests/test_transpiler_router.py#L264

The function includes the following code:

...
initial_layout = {"q0": 2, "q1": 0, "q2": 1, "q3": 3}
...
circuit_map.update((0, 2)) # first swap
...
circuit_map.update((1, 2)) # second swap
assert routed_circuit.queue[5].qubits == (2, 0)    # routed_circuit.queue[5] is the second swap

After the first swap, the layout should be converted to:

{"q0": 0, "q1": 2, "q2": 1, "q3": 3}

since update() operates on logical qubits. This would be equivalent to swapping physical qubits q0 and q1.

After the second swap, the swap should be on logical qubits (1, 2). So, the layout will be changed to:

{"q0": 0, "q1": 1, "q2": 2, "q3": 3}

Does this mean that the qubits affected by the swap are q2 and q1?

assert routed_circuit.queue[5].qubits == (2, 1)

Since routed_circuit.queue[i].qubits contains physical qubits, I think the qubits should be (2, 1). Could you help me understand if there's something I’m misunderstanding here?

Thank you for your time.

qiboteam / qibo