ODD MEMORY-SYSTEMS - A NEW APPROACH

To reject the use of a prime (or odd) number N of memory banks in a ve ctor processor, it is generally advanced that address computation for such a memory system would require systematic Euclidean division by th e number N. We first show that the Chinese Remainder Theorem allows on e to define a very simple mapping of data onto the memory banks for wh ich address computation does not require any Euclidean division. Massi vely parallel SIMD computers may have thousands of processors. When th e memory on such a machine is globally shared, routing vectors from me mory to the processors is a major difficulty; the control for the inte rconnection network cannot be generally computed at execution time. Wh en the number of memory banks and processors is a product of prime num bers, the family of permutations needed for routing vectors from memor y to the processors through the interconnection network has very speci fic properties. The Chinese Remainder Network presented in the paper i s able to execute all these permutations in a single path and may be e asily controlled. (c) 1995 Academic Press, Inc.