Conflict-free data access of arrays and trees in parallel memory systems

摘要

Mapping the nodes of a data structure to a given set of memory modules so that different sets of nodes (called templates) can be accessed in parallel without conflicts is an important problem. We consider two useful data structures, namely trees and arrays. The most commonly used templates of a tree are the subtrees of a given height or the nodes in any given level. We present a recursive memory module assignment algorithm for complete k-ary trees, allowing conflict-free access to any complete subtree of height h. Our scheme uses k/sup h-1/-1/k-1 memory modules which is the same as the number of nodes in the subtree and hence the memory utilization is optimal. The number of conflicts in accessing nodes in different levels or subtrees of different heights for these schemes are presented. For accessing arrays, the templates of interest are rows, columns, diagonals, different subblocks, distributed blocks and so on. We propose a new scheme for conflict-free access to all of these templates with the help of quasigroups. The multiplication table of a quasigroup will be used to map the array elements to different memory modules.