Parallel and Distributed Access of Dense Multidimensional Extendible Array Files (Extended Abstract)

Datasets in large scale scientific data management, are often modeled as k-dimensional arrays. Elements of these arrays, when kept in files on secondary storage (or disk), are allocated in a sequence of consecutive locations according to either a row-major or column-major ordering of an array mapping function. The allocation of an array in a file can be perceived as an out-of-core image of the in-core linear storage allocation. Such storage allocations limit the degree of extendibility of the arrays, both in core and out-of-core, to one dimension only. We address the problem of allocating storage for the elements of dense multidimensional extendible arrays so that the index range of any dimension can be arbitrarily extended without reorganizing previously allocated elements. The array can be partitioned, distributed and maintained as sub-arrays in the memories of the respective computational nodes of a parallel or distributed program. We present a mapping function F∗() and its inverse F −1 ∗ (), for computing the linear address of an array element when given its k-dimensional index. Such a function is realized with the help of a Leaf-Linked Red-Black Tree (LLRB-Tree) data structure that stores, in a compact manner, the history of the expansions of the dimensions. Access to the LLRB-Tree forms part of the address computation and is maintained as part of the metadata of the corresponding array file. Parallel and distributed accesses of the multidimensional array elements are achieved by maintaining consistent copies of the LLRB-Tree on each processor. The technique introduced applies to extendible arrays in main memory just as much as for extendible array files that are resident on disk