ON METHODS TO ALIGN AND ACCESS DATA ARRAYS IN PARALLEL COMPUTERS

We present methods to store and access templates of data arrays in par allel processors with shuffle-exchange-type interconnection networks. For this purpose, we define the class of composite linear permutations . In our method, each element of the data array is stored in the memor y module determined by applying a suitable composite linear permutatio n on its indices. Simple necessary and sufficient criteria to avoid me mory conflicts in the access of important templates such as row, colum n, main diagonal, and square block are given based on the composite li near permutation involved. The criteria so derived also specify the se t of permutations to be realized by an interconnection network to avoi d network conflicts. In particular, we give the criteria to be satisfi ed by a scheme of the proposed class to avoid network conflicts during the access of templates, when shuffle-exchange-type networks are used . Almost all the previously known scrambled storage methods are specia l cases in the class of storage methods presented in this paper. (c) 1 995 Academic Press, Inc.