PARALLEL MEMORY ALLOCATION AND DATA ALIGNMENT IN SIMD MACHINES
Cengiz Erbaş, Murat M. Tanik, Vivek Nair · International Journal of Parallel Emergent and Distributed Systems · 1994
In this paper, we introduce a memory storage scheme allowing conflict-free parallel access to rows, columns, square blocks, distributed blocks, and positive and negative diagonals of two dimensional arrays. Unlike the existing schemes, the proposed scheme can be used for an arbitrary number of memory modules and an arbitrary size of matrices. We develop a systematic procedure for the memory allocation based on a placement matrix constructed using circulant matrices. We, also, analyze the data alignment requirements of the proposed scheme, and demonstrate that the data vectors read from memory modules can be aligned for the processors using a set of shift, flip, and shuffle operations, which can be implemented by a data manipulation network.