search

qiskit-advocate / qiskit-advocate-projects

A repository of projects that Qiskit Advocates are actively working on. This project has been evolved into Qiskit Advocate Mentorship Program (QAMP) and the repo is archived. See QAMP Spring 21 for example.
https://github.com/qiskit-advocate/qamp-spring-21
13 stars 2 forks source link

Migrate Terra's CouplingMap class to use retworkx internally #4

Closed mtreinish closed 4 years ago

mtreinish commented 4 years ago

Abstract

The qiskit project retworkx is a general purpose graph library designed as a higher performance alternative to networkx. It is written in Rust to get this performance improvement. The DAGCircuit class was the first piece in qiskit-terra to use this and saw a very large performance improvement in transpile runtime because of this. However, there are still parts of qiskit-terra that is using networkx which is a potential performance bottleneck. The most obvious of these is the CouplingMap class which defines the coupling graph of backends for the transpiler; this class still using networkx mostly because not all the APIs used in the class exist in retworkx yet. This project is to add the missing features to retworkx so that we can migrate the CouplingMap class to retworkx, and then after that feature gap is closed migrate the class in terra to use retworkx instead of networkx.

Description

Members

Deliverable

PRs to retworkx to close the feature gap and then a PR to terra to migrate CouplingMap

GitHub repo

https://github.com/Qiskit/retworkx https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/coupling.py

HuangJunye commented 4 years ago

This is a really exciting project. I want to work on it. Are you looking for one or more collaborators?

aditya-giri commented 4 years ago

I'd be happy to help too...

mtreinish commented 4 years ago

This is a really exciting project. I want to work on it. Are you looking for one or more collaborators?

Ok awesome, thanks. One or more, it's really however many people are interested in this. There isn't a ton of work for this though so probably not too many people (probably not more than 3 or 4).

Looking a bit more closely at the coupling graph class the places where we need to add missing functionality to retworkx are:

Plus the obvious terra work to refactor coupling.py to use retworkx after all those are added.

The one thing that's common to a couple of things there is a way to treat a directed graph as undirected which retworkx doesn't support yet either.

HuangJunye commented 4 years ago

I am new to Rust so it will take me a while to get productive. @aditya-giri If you are also new to Rust, I recommend watching this video to get started.

I want to start with adding is_weakly_connected() function to retworkx. (https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/coupling.py#L131) If I understand it correctly, I need to rewrite all the functions in this file of networkx in Rust and add to lib.rs file in retworkx.

I still need to understand how to write a function in Rust and use PyO3 to bind to python. Looking at other functions in lib.rs, I think the header can be something like:

/// Test directed graph for weak connectivity.
#[pyfunction]
#[text_signature = "(graph, /)"]
fn is_weakly_connected(graph: &digraph::PyDiGraph) -> PyResult<bool> {

}

@mtreinish Am I going in the right direction?

mtreinish commented 4 years ago

I am new to Rust so it will take me a while to get productive. @aditya-giri If you are also new to Rust, I recommend watching this video to get started.

I want to start with adding is_weakly_connected() function to retworkx. (https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/coupling.py#L131) If I understand it correctly, I need to rewrite all the functions in this file of networkx in Rust and add to lib.rs file in retworkx.

I still need to understand how to write a function in Rust and use PyO3 to bind to python. Looking at other functions in lib.rs, I think the header can be something like:

/// Test directed graph for weak connectivity.
#[pyfunction]
#[text_signature = "(graph, /)"]
fn is_weakly_connected(graph: &digraph::PyDiGraph) -> PyResult<bool> {

}

@mtreinish Am I going in the right direction?

Yep, that looks like exactly the right direction. That one is also pretty easily to implement since the number_weakly_connected_components function shows you how to get the number of components from the PyDiGraph input and the logic for this function is straightforward once you get that.

Also, please feel free to reach out to me (here, on slack, anywhere else) if you have any issues with rust or getting started there. I don't claim to be a rust expert yet, but I will help anyway I can. The language has a steeper learning curve than many and can feel intimidating at first, but once you get over that initial hump it's very rewarding.

mtreinish commented 4 years ago

I want to start with adding is_weakly_connected() function to retworkx. (https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/coupling.py#L131) If I understand it correctly, I need to rewrite all the functions in this file of networkx in Rust and add to lib.rs file in retworkx.

Actually I missed this before, you don't need to implement all the functions there to start. For the coupling map we just need is_weakly_connected the other pieces (to get the number of weakly_connected_components) should already be in retworkx. I think the only other function in there is to actually get the components, but we don't have a use case for that in retworkx (yet?).

HuangJunye commented 4 years ago

I found number_of_weakly_connected_components: https://github.com/Qiskit/retworkx/blob/master/src/lib.rs#L152. I will try and see if I can implement is_weakly_connected this week. I'll reach out to you either here or Slack when I face difficulties. Thank you!

aditya-giri commented 4 years ago

Thanks @mtreinish and @HuangJunye. I'm new to Rust too, so let me try and get a feel of it by the end of this week too :)

mtreinish commented 4 years ago

I just pushed up https://github.com/Qiskit/retworkx/pull/143 which I think is the last piece needed before we can use that floyd warshall function there in place of everything in: https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/coupling.py#L143-L158

mtreinish commented 4 years ago

I also just pushed up https://github.com/Qiskit/retworkx/pull/144 which will handle the subgraph method in the coupling map (I just needed a change of pace at the end of today and both were fairly straightforward to implement). After those are reviewed (please feel free to review and ask question on both PRs) all that is left on the retworkx side in the coupling map class is the is_weakly_connected function and the shortest_path functions. Then we also have to update terra to use retworkx and iterate from there.

mtreinish commented 4 years ago

I was just tracing through the transpiler code and found another method we'll need to implement:

https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/passes/routing/layout_transformation.py#L60

basically a method on PyDiGraph that will return a PyGraph for it. It shouldn't be too hard to do. I'm sure once we try to use retworkx in the coupling map for the first time we'll find some places like this

HuangJunye commented 4 years ago

Sorry I have been busy for the last week. I will take sometime tomorrow and the weekend to review the two PRs. It will be a good exercise for understanding Rust. I can probably try to implement the few things left on retworkx next week.

HuangJunye commented 4 years ago

@mtreinish Sorry it seems like I will be super busy for a while. I am not sure I can commit to this project before mid Nov. Let's hope there will be other people interested in pushing the project forward. Sorry about that.

mtreinish commented 4 years ago

I'm just going to close this. I've written all the PRs necessary for this (see: https://github.com/Qiskit/retworkx/issues/154 ) and have a local branch implementing the Terra component: https://github.com/Qiskit/qiskit-terra/pull/5183 so there is nothing left to do here anymore.

HuangJunye commented 4 years ago

@mtreinish That’s super speed! Sorry again for not being available to collaborate. But I certainly want to work on projects in the future with you and learn from you!