Bounded-Collision Memory-Mapping Schemes for Data Structures with Applications to Parallel Memories

摘要

Techniques are developed for mapping structured data to an ensemble of parallel memory modules in a way that limits the number of conflicts, i.e., simultaneous accesses by distinct processors to the same memory module. The techniques determine, for any given conflict tolerancec, the smallest ensemble that allows one to store anyn{hbox{-}}rm node data structure "of type X驴 in such a way that no more than c nodes of a structure are stored on the same module. This goal is achieved by determining the smallest c{hbox{-}}{it perfect universal graphs} for data structures "of type X.驴 Such a graph is the smallest graph that contains a homomorphic image of each n{hbox{-}}rm node structure "of type X,驴 with each node of the image holding leq c nodes of the structure. In the current paper, "type X驴 refers to rooted binary trees and three array-like structures: chaotic arrays, ragged arrays, and rectangular arrays. For each of these families of data structures, the number of memory modules needed to achieve conflict tolerance c is determined to within constant factors.