Overview
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.
Practical Performance
Practical Performance Practical Performance Practical Performance Practical Performance
Practical performance
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.
Details
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 models.
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.
nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves
nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves nested sequences of Z-order space-filling curves 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.
2D array of nodes is superimposed with the sequence of Z-order curves 2D array of nodes is superimposed with the sequence of Z-order curves
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.
inverse mapping
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.
Address computation
Address Computation
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 . 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.
Diagram of maintaining direct access to the data while facilitating progressive refinement
Reference
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. UCRL-JC-144754.
Contact
For more information, please contact Valerio Pascucci.