Load balanced mapping of data structures in parallel memory modules for fast and conflict-free templates access

Conflict-free, memory access is one of the important factors for the overall performance of a multiprocessor System in which the available memory is partitioned into several modules. Even if there is no contention in the processor-memory interconnection path, conflicts may still occur when two or more processors attempt to gain access to a single memory module or a memory location within a module. With a goal to achieve higher memory bandwidth, in this paper we resolve access conflicts at the level of memory modules. In particular, we deal with the problem of evenly mapping a data structure, called host, into as few distinct memory modules as possible to guarantee that subsets of distinct host nodes, called templates, can be accessed simultaneously in a conflict-free manner.Since trees are among the most frequently used data structures in numerous applications, we propose a simple algebraic function based on the node indices for assigning the nodes of a k-ary tree to the memory modules in such a way that each subtree of a given height and arity can be accessed without conflicts. The assignment is direct, load balanced and also optimal in terms of the number of modules required. We also investigate conflict-free access to d-dimensional subcubes (Qd) of n-dimensional hypercubes (Qn), where Qn represcnts a set of items indexed with n-digit addresses and accesses will be made to subsets of items differing in any arbitrary d-digit positions. With the help of the coding theory, we propose a novel approach to solve the subcube access problem. Codes with minimum distance d > 2 play a crucial role in our applications. We prove that any occurrence of a subcube Q, C Qn, for O < a < d - 1, can be accessed without conflicts using [2n] memory modules, by associating Qn with a linear [M]code C of length n, size M and minimum distance d. Associating the hypercube nodes with perfect or maximum distance separable (MDS) codes, our problem is solved optimally both in terms of the number of memory modules required and load balancing per module. These codes can be easily modified (without node relocation) according to the change in the sìze of the host or the number of available memory modules.