[Numpy-discussion] Z-ordering (Morton ordering) for numpy

Gamblin, Todd gamblin2@llnl....
Sat Nov 24 14:30:54 CST 2012


So, just FYI, my usage of this is for Rubik, where it's a communication latency optimization for the code being mapped to the network.  I haven't tested it as an optimization for particular in-core algorithms.  However, there was some work on this at LLNL maybe a couple years ago -- I think it was for the solvers.  I'll ask around for an example and/or a paper, or maybe Travis has examples.

Just from an ease-of-use point of view, though, if you make it simple to do zordering, you might see more people using it :).  That's why I wanted to get this into numpy.

This brings up another point.  This is pure python, so it won't be super-fast.  What's the typical way things are integrated and optimized in numpy?  Do you contribute something like this in python first then convert to cython/C as necessary?  Or would you want it in C to begin with?

-Todd


On Nov 24, 2012, at 12:17 PM, Aron Ahmadia <aron@ahmadia.net>
 wrote:

> Todd,
> 
> I am optimistic and I think it would be a good idea to put this in.  A couple previous studies [1] haven't found any useful speedups from in-core applications for Morton-order, and if you have results for real scientific applications using numpy this would not only be great, but the resulting paper would have quite a bit of impact.  I'm sure you're already connected to the right people at LLNL, but I can think of a couple other projects which might be interested in trying this sort of thing out.
> 
> http://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/co.pdf
> 
> Cheers,
> Aron
> 
> 
> On Sat, Nov 24, 2012 at 8:10 PM, Travis Oliphant <travis@continuum.io> wrote:
> This is pretty cool.    Something like this would be interesting to play with.  There are some algorithms that are faster with z-order arrays.    The code is simple enough and small enough that I could see putting it in NumPy.   What do others think?
> 
> -Travis
> 
> 
> 
> On Nov 24, 2012, at 1:03 PM, Gamblin, Todd wrote:
> 
> > Hi all,
> >
> > In the course of developing a network mapping tool I'm working on, I also developed some python code to do arbitrary-dimensional z-order (morton order) for ndarrays.  The code is here:
> >
> >       https://github.com/tgamblin/rubik/blob/master/rubik/zorder.py
> >
> > There is a function to put the elements of an array in Z order, and another one to enumerate an array's elements in Z order.  There is also a ZEncoder class that can generate Z-codes for arbitrary dimensions and bit widths.
> >
> > I figure this is something that would be generally useful.  Any interest in having this in numpy?  If so, what should the interface look like and can you point me to a good spot in the code to add it?
> >
> > I was thinking it might make sense to have a Z-order iterator for ndarrays, kind of like ndarray.flat.  i.e.:
> >
> >       arr = np.empty([4,4], dtype=int)
> >       arr.flat = range(arr.size)
> >       for elt in arr.zorder:
> >               print elt,
> >       0 4 1 5 8 12 9 13 2 6 3 7 10 14 11 15
> >
> > Or an equivalent to ndindex:
> >
> >       arr = np.empty(4,4, dtype=int)
> >       arr.flat = range(arr.size)
> >       for ix in np.zindex(arr.shape):
> >               print ix,
> >       (0, 0) (1, 0) (0, 1) (1, 1) (2, 0) (3, 0) (2, 1) (3, 1) (0, 2) (1, 2) (0, 3) (1, 3) (2, 2) (3, 2) (2, 3) (3, 3)
> >
> > Thoughts?
> >
> > -Todd
> > ______________________________________________________________________
> > Todd Gamblin, tgamblin@llnl.gov, http://people.llnl.gov/gamblin2
> > CASC @ Lawrence Livermore National Laboratory, Livermore, CA, USA
> >
> > _______________________________________________
> > NumPy-Discussion mailing list
> > NumPy-Discussion@scipy.org
> > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> 
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
> 
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion

______________________________________________________________________
Todd Gamblin, tgamblin@llnl.gov, http://people.llnl.gov/gamblin2
CASC @ Lawrence Livermore National Laboratory, Livermore, CA, USA



More information about the NumPy-Discussion mailing list