Multidimensional access shared memory parallel processing systems

Orthogonal graphs are a simple but powerful tool for the analysis and description of a class of interconnection networks. Omega graphs and multidimensional orthogonal graphs are considered for the generation of a class of shared memory systems which, in turn, include the OMP and STARAN´s multidimensional access (MDA) memory. Given 2ⁿ processors and 2^m memory modules, it is shown that an integer set Q⊆{0,1,. . .,m-1} defines a number of conflict free memory access modes if (Q,+mod m) is a group. Such a result is derived from the definition of a relation of equivalence responsible for the partition of the set of memory modules. These facts are used for the derivation of a design methodology for the interconnection network needed to implement multidimensional access