Hierarchical Index Spaces.

The hierarchical, extendible index space component of the HDDA is derived directly from the application domain using space-filling mappings which are computationally efficient, recursive mappings from N-dimensional space to 1- dimensional space. Figure 6 illustrates a 2-dimensional Peano-Hilbert curve. The solution space is first partitioned into segments.

Figure 6:

The space filling curve then passes through the midpoints of these segments. Space filling mappings encode application domain locality and maintain this locality though expansion and contraction. The self-similar or recursive nature of these mappings can be exploited to represent a hierarchical structure and to maintain locality across different levels of the hierarchy.

Space-filling mappings allow information about the original multi-dimensional space to be encoded into each space-filling index. Given an index, it is possible to obtain its position in the original multi-dimensional space, the shape of the region in the multi- dimensional space associated with the index, and the space-filling indices that are adjacent to it. The index-space is used as the basis for application domain partitioning, as a global name-space for name resolution, and for communication scheduling.