Synchronized access to streams in multiprocessors

The synchronized and simultaneous access to several vectors that form a single stream occurs in SIMD vector multiprocessors as well as in MIMD superscalar multiprocessors with decoupled access. In this paper we propose a block-interleaved storage scheme and an out-oforder access mechanism that allows conflict-free access to streams with an arbitrary initial address and constant stride between elements. A maximal number of conflict-free families including the most commonly used strides can be obtained. We consider the use of a crossbar interconnection network, although the method applies also for the case of a multistage interconnection network.Peer ReviewedPostprint (published version