The goal of this project is to focus on research related to coupled
data structure and algorithm design that exploit the characteristics of
the modern CPU and distributed systems. The initial work in this area has
been on new data layouts for external-memory progressive visualization.
Indexing Scheme for Out-of-Core
Progressive Visualization of Large Regular Grids
We have introduced a new indexing scheme for out-of-core progressive
visualization of large regular grids. We demonstrated the effectiveness
of our approach by implementing a tool that displays at interactive
rates planar slices of scalar field data with extremely modest
computing resources. We obtained unprecedented results both in terms of
absolute performance and, more importantly, in terms of scalability. On
a laptop computer, we provide real time interaction with a 20483 grid
(8 Giga-nodes) using only 20MB of memory. On an SGI Onyx, we slice
interactively an 81923 grid (_ tera-nodes) using only 60MB of memory.
The scheme relies simply on the determination of an appropriate
reordering of the rectilinear grid data and a progressive construction
of the output slice. The reordering minimizes the amount of I/O
performed during the out-of-core computation. The progressive and
asynchronous computation of the output provides flexible quality/speed
tradeoffs and a time-critical and interruptible user interface.
We have compared two variations of our scheme, 1-bit and 3-bits
hierarchical z-order, with traditional external-memory data layouts:
brick-blocking and row major array storage.
The average slicing time based on our data layout schemes can be two
orders of magnitude faster than the same slicing combined with data
traditional data layouts.
Our main focus at this stage is the determination of efficient data
layouts and not on the absolute quality of the multi-resolution
representation. Therefore we limit our attention to the case of pure
sub-sampling of the input data as a means for creating approximated
We take advantage of the nested nature of space-filling curves to
create a sub-sampling hierarchy where the nodes touched by a curve at
level i are used as a coarse model of the nodes touched by the
refined curve of level i+1.
The figure below shows the nested sequences of Z-order space-filling
curves in the 2D and 3D cases.
For sake of simplicity we focus on the 2D case. A 2D array of nodes is
superimposed with the sequence of Z-order curves as shown below.
We store the points in memory (a 1D array) following each Z-curve from
coarse to fine resolution, where at each resolution we pick the new
(red) nodes and skip the coarse (green) nodes. Because all the nodes
are red exactly once, this procedure generates a simple permutation of
the nodes. The figure below shows the inverse mapping, relating the 1D
storage order in memory and the location of the nodes in the 2D array.
Intuitively one can observe that the data at the beginning of the
memory is the coarse representation of the 2D grid. Data blocks further
in the memory order contain finer and more localized data nodes.
Interestingly, while the geometric sub-sampling is aligned with a
quad-tree subdivision (oct-tree in 3D), the actual hierarchy is the
tree shown below. The property of this hierarchy is that each node of a
given level has three children at all the following levels.
One fundamental property of our technique is the ability to maintain
direct access to the data while facilitating progressive refinement.
Given a node of indices (i,j) in the 2D array, one can compute the
final 1D index I of the memory location where the node is stored
in hierarchical Z-order. To this end the bits of the binary
representation of i and j are interleaved to build a
temporary index Ií. The final index I is then obtained by
shifting the bits of Ií to the right until the first bit set to 1 is
removed. Note that at the first right shift the bit ingoing from the
left is at 1, while at all the following shifts the ingoing bit is set
to 0. This is summarized in the diagram below.
Valerio Pascucci, Randall J. Frank, Global Static Indexing for Real-time
Exploration of Very Large Regular Grids
, proceedings of
Supercomputing 2001 Conference, Denver, CO, Nov 10-16, 2001.