MULTISKEWING - A NOVEL TECHNIQUE FOR OPTIMAL PARALLEL MEMORY ACCESS

The disparity between the processing speed and the data access rates p resents a serious bottleneck in pipelined/vector processors. The memor y bank conflict in interleaved system can be alleviated by skewing, fo r scientific computations performing functions on varieties of submatr ices. So far uniskewing involving periodic and linear functions have b een studied. Several difficulties encountered in such schemes are that they require a prime number of memory modules, may create wasted memo ry space, or addressing functions and the alignment network become com plex. We present a new technique, termed multiskewing, which applies m ultiple functions on different sections of the array. Each of these fu nctions may be as simple as a linear shift. We show that some of the a dvantages are that it does not require a prime number of memory, memor y utilization factor is 100%, maintains the logical structure of the a rray, and allows optimal memory access of a large class of submatrices .