INVERSE SPACEFILLING CURVE PARTITIONER
    RANDY PILKINGTON (JPILKING@CS.UCSD.EDU)
    SCOTT B. BADEN (BADEN@CS.UCSD.EDU)
    DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
    UNIVERSITY OF CALIFORNIA, SAN DIEGO

    VERSION DATED 12/31/93


This directory contains the code for an inverse spacefilling
curve partitioner (ISP), in shar form.  The isp algorithm is
contained in isp.c.  ISP is implemented with three functions,
that are described in isp.h.  You must include isp.h in any module
that calls the spacefilling curve partitioner.

An example driver program is found in test.c
which creates a 3d mesh with random workloads, partitions, 
tests and evaluates the partitions.

ISP is described in
"Dynamic Non-Uniform Mesh Partitioning with Spacefilling Curves,"
by Randy Pilkington and Scott B. Baden, a CSE technical report
to soon appear (please let us know if you would like a copy
of this report.)

Limitations:

1) The lengths of each dimension of the mesh must be equal and
   a power of 2, though the extents do not all have to be the same.
   For arbitrary lengths, you will have to pad the array,
   ignore the mappings in the padded region.

2) The value of the variable MAXLEVEL (defined in isp.h)
   sets the maximum side lengths of the mesh dimensions.
   (maximum side length == 2^MAXLEVEL)
   The  value of MAXLEVEL is set to 12, hence the maximum
   length is 4096.  The limit can be increased by changing
   MAXLEVEL in isp.h.
   
3) The number of array dimensions is limited to 10.

4) The mapping (preprocessing step) function could be optimized
   to run faster, however, the mapping time  should be small
   enough that the optimizations would not significantly
   reduce the running time.  Potentially the two
   and three dimensional cases could run perhaps 2-3 times faster.