[Numpy-discussion] Z-ordering (Morton ordering) for numpy
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, tgamb...@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
Re: [Numpy-discussion] Z-ordering (Morton ordering) for numpy
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, tgamb...@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
Re: [Numpy-discussion] Z-ordering (Morton ordering) for numpy
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 tra...@continuum.iowrote: 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, tgamb...@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
Re: [Numpy-discussion] Z-ordering (Morton ordering) for numpy
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 a...@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 tra...@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, tgamb...@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, tgamb...@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
Re: [Numpy-discussion] Z-ordering (Morton ordering) for numpy
On Sat, Nov 24, 2012 at 1:30 PM, Gamblin, Todd gambl...@llnl.gov wrote: 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? I think Python is a good start as it allows easy modification and can be converted to Cython later on. OTOH, if the new function looks settled from the get go, Cython is an option. snip Chuck ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
