next up previous contents
Next: Distributed Dynamic Storage - Up: Definition and Description of Previous: Mapping to Address Spaces.   Contents

Storage and Access-Extendible hashing for distributed dynamic storage and access.

Data storage is implemented using extendible hashing techniques to provide a dynamically extendible, globally indexed storage (see the figure below). The keys for the Extendible Hash Table are contractions of the unique keys defined as described preceding.

Similarly, when data associated with a DAGH block entry is ready to ship, the associated bucket is shipped as is. The overall HDDA/DAGH distributed dynamic storage scheme is shown in figure 7.

Figure 7:
\begin{figure}\centerline{\psfig{figure=storage.eps,width=4.8in}}\end{figure}

Entries into the HDDA correspond to DAGH blocks. Expansion and contraction are local operations involving at most two buckets. Locality of data is preserved without copying. The HDDA data storage provides a means for efficient communication between DAGH blocks. To communicate data to another DAGH blocks, the data is copied to appropriate locations in the HDDA. This information is then asynchronously shipped to the appropriate processor.

Similarly, data needed from remote DAGH blocks is received on-the-fly and inserted into the appropriate location in the HDDA. Storage associated with the HDDA is maintained in ready-to-ship buckets. This alleviates overheads associated with packing and unpacking. An incoming bucket is directly inserted into its location in the HDDA.

Figure 8: Dynamic hashing by splitting and coalescing buckets
\begin{figure}\centerline{\psfig{figure=hashing.eps,width=4.8in}}\end{figure}

next up previous contents
Next: Distributed Dynamic Storage - Up: Definition and Description of Previous: Mapping to Address Spaces.   Contents
Bryan Carpenter 2002-07-12