Optimization of wall distance computation

[harichandiisc]

Wall distance computation is SU2 right now seems to be doing brute force search along the wall boundaries to find the nearest wall vertex. One performance optimization here would be to use k-d search tree to find the nearest neighbor.

Is it necessary to have a internal k-d tree code or can I use a third party library (like pointcloud). Since I was not sure, I have raised this as an issue and not a pull request.

[economon]

Indeed, at the moment, we are relying on brute force searches. We have discussed using tree searches internally (and potentially have some reusable code available for this), but nothing has been implemented.

It looks like pointcloud is released under a BSD license, which is very permissive. Do you have an implementation in SU2 already with this code embedded? It is also fairly straightforward for us to add hooks in the configure process to installed libraries on your system.

[juanjosealonso]

All,

I completely agree that a tree-based search (we have used quarters, octrees and alternating digital trees (ADTs) in the past with very significant cost reductions) is going to be necessary in the very near future as people begin to run much larger models. Otherwise the preprocessing time for the searches can become excessive and dominant.

If someone wanted to try using PCL for this, that would be quite interesting. Given the open source license, as Tom mentions, there should not be a problem interfacing with SU2.

Now, an issue we faced in the ASC / PSAAP programs is that for extremely large calculations, the surface mesh (to be searched for minimum distance calculations) may actually not fit in a single processor. For that purpose we built parallel ADTs in the past (unfortunately in FORTRAN90) which replicate a small portion of the upper structure of the tree in all processors (without consuming a lot of memory) and then decomposed the tree into the various processors participating in the searches. While the parallel speedups / efficiencies were not earth-shattering, we did manage to overcome the memory bottlenecks. Does anyone know if PCL can also handle trees that are decomposed in parallel? Would PCL work with its own MPI communicator and automate the communication needed for the searches?

Cheers,

Juan

On Jun 5, 2016, at 4:06 AM, Thomas D. Economon notifications@github.com<mailto:notifications@github.com> wrote:

Indeed, at the moment, we are relying on brute force searches. We have discussed using tree searches internally (and potentially have some reusable code available for this), but nothing has been implemented.

It looks like pointcloud is released under a BSD license, which is very permissive. Do you have an implementation in SU2 already with this code embedded? It is also fairly straightforward for us to add hooks in the configure process to installed libraries on your system.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/su2code/SU2/issues/282#issuecomment-223807001, or mute the threadhttps://github.com/notifications/unsubscribe/ADpSxPh8ni-GpSN-zKjD9Nyi47sf5sqZks5qIq2jgaJpZM4ItVbi.

[LaSerpe]

All,

I'll get the chance to jump into this topic which I'm interested in. As some of you know I'm currently working on sliding meshes and multi-zone problems for turbo-machinery applications. Currently also the cinterpolator class, in particular for the nearest neighbour interpolation, relies on brute force search algorithms. Moreover, a lot of possible (future) interpolation methods may rely on a nearest neighbour search in the very first place (I'm thinking for instance to the construction of a polynomial interpolation pattern which would require to find a bunch of donor points on the donor mesh) This may lead to a dramatic increase of the computational time when dealing with very large problems like for instance unsteady multi-stage turbo-machinery problems, since, for these particular applications, at every time step we will need to reconstruct the communication pattern among rotors and stators. So the implementation of a clever way to carry out the nearest neighbour search will be mandatory in the future of SU2.

I think that it would be very useful to have a reliable and reusable tree search library so that everyone can exploit the same function calls. For former works I did use the ANN library from the University of Maryland which is distributed under the GNU lesser public license, moreover I talked with Edwin and he also has some routines he wrote himself that could suits this particular problem.

Just let me know if and how we can help in solving this thorny problem.

Ciao! Giulio

[harichandiisc]

All,

Thanks for your comments. I think ANNlibrary is no longer maintained. It would be better if we can use a well maintained library in-order to prevent issues in future. Additionally ANNlibrary does not support distributed trees.

As far as I know, pointcloud library also does not support distributed trees. I guess we will have to write a wrapper routine using MPI. This will create a local tree for its own portion of the surface mesh. Now distance computation can be done by querying all the trees and using the minimum. One catch here is that we will have to compute distance queries in a group in order to prevent the communication latency eating up the advantage.

Waiting for comments

[juanjosealonso]

Harichand, Giulio, Edwin, and all,

I would definitely prefer to use either (a) an open source library that is actively maintained, or (b) our own tree-based search. I do think that this is important for the various reasons that have been outlined/discussed already.

The method Harichand describes is pretty much what we did in the ASC program. Edwin can provide more details (and we had an AIAA paper around 2005 on this topic).

My suggestion: if Edwin has a tree search in C++ already and someone is willing to spend the time to integrated it, that would be the best option. We get the performance that is needed with a lightweight tree search, without external dependencies (to libraries that may provide a lot of other functionality we do not need), and we can expand to parallel trees as needed. If there is no code already available, then PCL seems like a good alternative (since it seems one can compile only portions of the library).

Any takers?

Cheers,

Juan

On Jun 8, 2016, at 4:35 AM, Harichand M V notifications@github.com<mailto:notifications@github.com> wrote:

All,

Thanks for your comments. I think ANNlibrary is no longer maintained. It would be better if we can use a well maintained library in-order to prevent issues in future. Additionally ANNlibrary does not support distributed trees.

As far as I know, pointcloud library also does not support distributed trees. I guess we will have to write a wrapper routine using MPI. This will create a local tree for its own portion of the surface mesh. Now distance computation can be done by querying all the trees and using the minimum. One catch here is that we will have to compute distance queries in a group in order to prevent the communication latency eating up the advantage.

Waiting for comments

— You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/su2code/SU2/issues/282#issuecomment-224563432, or mute the threadhttps://github.com/notifications/unsubscribe/ADpSxBy8kuwFTxIZIeCNXcpo7NhErZYeks5qJqjqgaJpZM4ItVbi.

[economon]

I'm with Juan on this... an in-house option in C++ would be best to avoid dependencies and have control of the algorithms for further tuning and easier application throughout the codebase.

If anyone is willing to give it a shot, please let us know, and we can help with integration.

[vdweide]

If the ADT stuff I already have will be used as a base, then I am probably the most likely candidate to do this. However, I have a couple of other things to do as well, so my time is a bit limited.

[harichandiisc]

If a k-d tree based implementation with parallel support with either pointcloud or full implementation is planned, I am interested to contribute.

Otherwise Edwin can lead the work with ADT based implementation. I can give the necessary coding support.

[juanjosealonso]

All,

Edwin has WAAAYYY too much on his plate right now. The ADT code is not that complicated and I know that there is an F90 (fairly object oriented) implementation. Edwin, is there also a C++ implementation that someone could start from?

If either Harichand or Giulio want to lead the effort, that would be great. I am sure Edwin would be happy to advise here and there if needed.

So?

Cheers,

Juan

On Jun 9, 2016, at 4:42 AM, Harichand M V notifications@github.com<mailto:notifications@github.com> wrote:

If a k-d tree based implementation with parallel support with either pointcloud or full implementation is planned, I am interested to contribute.

Otherwise Edwin can lead the work with ADT based implementation. I can give the necessary coding support.

— You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/su2code/SU2/issues/282#issuecomment-224871075, or mute the threadhttps://github.com/notifications/unsubscribe/ADpSxFz0dOtTPpROEf7HF5x7B-duSVsDks5qJ_wUgaJpZM4ItVbi.

[vdweide]

There is also a C++ version of the ADT search, although it assumes that the entire tree can be stored on one rank.

Edwin

---

From: juanjosealonso notifications@github.com Sent: Thursday, June 9, 2016 9:27 PM To: su2code/SU2 Cc: Weide, E.T.A. van der (CTW); Comment Subject: Re: [su2code/SU2] Optimization of wall distance computation (#282)

All,

Edwin has WAAAYYY too much on his plate right now. The ADT code is not that complicated and I know that there is an F90 (fairly object oriented) implementation. Edwin, is there also a C++ implementation that someone could start from?

If either Harichand or Giulio want to lead the effort, that would be great. I am sure Edwin would be happy to advise here and there if needed.

So?

Cheers,

Juan

On Jun 9, 2016, at 4:42 AM, Harichand M V notifications@github.com<mailto:notifications@github.com> wrote:

If a k-d tree based implementation with parallel support with either pointcloud or full implementation is planned, I am interested to contribute.

Otherwise Edwin can lead the work with ADT based implementation. I can give the necessary coding support.

You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/su2code/SU2/issues/282#issuecomment-224871075, or mute the threadhttps://github.com/notifications/unsubscribe/ADpSxFz0dOtTPpROEf7HF5x7B-duSVsDks5qJ_wUgaJpZM4ItVbi.

You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/su2code/SU2/issues/282#issuecomment-225000652, or mute the threadhttps://github.com/notifications/unsubscribe/AOUnxLFSv5QD58IfpCw5MIgXIUo6tTBVks5qKGksgaJpZM4ItVbi.

[harichandiisc]

If you can share the ADT code, I will look in to the possibilities of distributed search and implementation in SU2.

[vdweide]

I can create a first implementation of an ADT search in which all wall points and connectivities are gathered on every rank. I already created the branch feature_WallDistance. However, I have to talk to Giulio first to make sure that the ADT can also be used for the sliding interfaces

[harichandiisc]

Awesome! Let me know if you need any help.

[vdweide]

I uploaded a first version of the ADT nearest node search to the branch feature_WallDistance. Seems to give the correct results, but I have not done any efficiency tests with a large mesh. If somebody could do that, that would be helpful.