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 givenconflicttolerancec,the smallestensemblethatallowsone tostoreanyn-nodedatastructure“oftypeX” insucha waythatnomore than c nodes of a structure are stored on the same module. This goal is achieved by determining the smallest c-perfect universal graphs for data structures “of type X.” Such a graph is the smallest graph that contains a homomorphic image of each n-node structure “of type X,” with each node of the image holding ? 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.