[...]
> Have quadtrees of David Wise's ([WEISE] and [WEISE1])
> proved to be of any importance to scientific computing
> in Haskell? Among other things, the quadtree algorithms
> supposed to improve array updating schemes. Judging
> from the publishing dates (1992, 1995 with a paper version
> of the latter scheduled for 1998) this idea is still
> very much alive. Has anyone benefited from it yet?
[...]
Wise has been my advisor for nearly five years now. We worked in Haskell
for a while, using it to write the LU decomposition he worked out in your
second reference. We even put out a tech report of this code (TR #433 at
http://www.cs.indiana.edu/ftp/techreports/). That code was actually
written in Gofer, and I'm unsure how much would have to change to update it
for the most recent version of Haskell.
But we wanted to compete with traditional code that was written in FORTRAN,
C, and even assembly (e.g., machine specific BLAS). That code is heavily
optimized and (most importantly for scientific computation) makes very good
use of memory. The biggest memory concern being the memory hierarchy. We
needed more control over our matrix structure to compete with the legacy
code. This control included things like unboxed values, a memory
sequential array, and side-effects.
Many Haskell systems would give us some of the control we wanted, except
for the side-effects. Other functional languages (where we could get even
more control) were often not tuned to make floating point operations as
fast as possible for the particular architectures that we were interested
in.
So we ended up in C. We started with the most basic, interesting matrix
algorithm: matrix-matrix multiply. Using Morton ordering, we get the
matrix into a sequential array such that each quadrant at each level of the
quadtree is in contiguous memory. Our results are not as impressive as
BLAS, but they are promising. See our paper in PPoPP'97 or the updated
Tech Report #449 (at the same URL above). More recent work may allow us to
speed up our time.
Currently, I'm working on QR Factorization with quadtree matrices written
in C. Again, I'm looking for performance tuned to the machine I compile
the code on.
If we were compiler writers (I only pretend to play one in my free time),
we could probably put many of the basic things we needed into a Haskell
compiler (like the matrix representation, assembly code for the
multiplication of small matrices, etc.). The major algorithm could be
written in Haskell. There are certain patterns that are emerging from all
of this code, that could be used in a compiler to write high-level code
that results in machine-fast assembly code.
jdf
-----
Jeremy D. Frens "I'm not saying what I'm saying. I'm not saying
Assistant Professor what I'm thinking. For that matter I'm not
Computer Science even thinking what I'm thinking."
Northwestern College (Iowa) -Captain Sheridan, _Babylon 5_
