sieve-dev mesh loading and distribution

[Matthew Knepley]

On Thu, Oct 30, 2008 at 10:39 AM, Shi Jin <jinzishuai at gmail.com> wrote:
> Hi there,
>
> I have been thinking about issue of large memory cost and slow process
> of loading and distributing mesh. I have three points and would
> appreciate your comment.
>
> 1. I realized that a major difficulty lies in the treatment of edge
> and faces, ie, the interpolation of the mesh. In fact, it is fairly
> straightforward to have an efficient code that only deals with first
> order elements, ie, in the sieve structure, there are only two layers,
> cells and vertexes. Our input files are  actually for a linear element
> mesh. The master process loads it in and spends a lot of time and
> memory doing the interpolation. This part is not parallelized. I am
> wondering if it is possible to make the interpolation run in parallel
> too. We can first distribute the uninterpolated mesh across processes,
> which can be done much more efficiently with much less resources.
> After the distribution, we do a interpolation locally on each process.
> Surely we have an issue of overlaps and renumbering for the newly
> introduced points. So this is definitely a very non-trivial task. But
> once it is implemented, we are able to run much larger meshes since
> the cost is shared by lots of processes.

That is the idea. However, it will take some time to implement this,
test it, etc. Also, there is absolutely no money to do this :) Maybe that
will make it better.

> 2. Since linear elements are fairly easy to do, I wrote my own code to
> load in the same input files (.nodes and .lcon files). From that, I
> can construct the inverse connectivity table and then produce the same
> sieve data structure. This code is able to produce the same first
> order grid as using the loadMesh() directly for linear elements.
> However, I only use about 1/3 of the memory and spent 25% less time in
> doing this. Are you interested in my implementation? My inverse
> connectivity table in allocated as a single continuous 1-D array, with
> length=NumberofVertex*MaxSupportSize, where the MaxSupportSize is a
> number I can control by command line options. For the mesh I am using,
> MaxSupportSize=24. So my code is not as general as yours in this
> sense. My cone and coneOrientation data are identical to the one
> obtained in your code (the coneOrientation are all 0s for a serial
> code, right?), which is just the connectivity table in the input .lcon
> file. My support data are the same but not ordered as yours, since I
> did not use the STL list data structure. If I am to sort it, it is
> definitely going to be more expensive. Is the order of support points
> important? I am very happy to share the code.
> Unfortunately my code has to use second order elements so I cannot
> fully test this.  The importance of this part will only be critical
> after the first issue of parallel interpolation is solved.

Actually, this already exists in the ISieve code. I do it without STL so it has
optimal space complexity, and I think the time is also optimal. Look at the
conversion routine for Sieve to ISieve. The inverse connectivity routine is
called at the end.

> 3. I also realized that the support data are very expensive to obtain.
> Basically from my experience in the linear element case in point 2, I
> found the inverse connectivity table taking a lot of memory and time.
> However, the inverse connectivity table is not also used. In some
> applications, it is not necessary to have the inverse connectivity
> table (thus the support of a point) information. For those cases, is
> it possible not to set the support information? If that is true, we
> can save the a very large portion of the computational resources.

It is used for parallelism.

I think this really misses the main point. Inverse connectivity is not a problem
at all. Interpolation is the problem. I see no way to speed this up, short of
complicated memory pooling, and I am unsure how much help that would be.
Certainly, if you dispensed with the extra STL memory, the runtime would
increase greatly because search time would go up.

  Matt

> Thank you very much.
> --
> Sincerely,
> Shi Jin, Ph.D.
> http://www.ualberta.ca/~sjin1/
-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which
their experiments lead.
-- Norbert Wiener