4.10.2 Data Access

On shared memory machines the access to the H-RLE data structures of other threads is not difficult. Random access is realized by first determining the H-RLE data structure which contains the information of the corresponding grid point. This requires a search within the index vector array which defines the grid segmentation. This increases the complexity of a random access to ${\mathcal{O}}(\log{{N}_\text{CPU}}+\log{{N}_\text{D}})$ in the worst case.

Similarly, sequential access does not require any major changes. The iterators described in Section 4.2 can be reused with a small modification. If an iterator reaches a run code annotating that the corresponding grid points can be found in another H-RLE data structure, a random access operation is performed on that data structure. However, on average, sequential access can still be performed in constant time. This guarantees a linear complexity of the sparse field LS method for the parallel data structure.

The lexicographical order of defined grid points within the (non-parallel) H-RLE data structure leads implicitly to a numbering. Each defined grid point can be unambiguously identified by the array index of the corresponding LS value. This number is very useful when assigning additional data to defined grid points. To obtain this identification number from the parallel H-RLE data structure, an offset must be added to the corresponding array index. For this purpose an additional array is introduced to store the index of the first defined grid point, as shown in Figure 4.20.