Organization of the two‐dimensional omega network
Takeshi Kumagai, Kazuo Ikegaya · Systems and Computers in Japan · 1986
Abstract Local parallel processing is effective for such fields as image processing where problems are essentially two‐dimensional. Here, we propose the two‐dimensional Omega network as an interconnection network suitable for SIMD multiprocessor systems used in such fields. The two‐dimensional Omega network is an interconnection network devised to apply two‐dimensional permutation to local data obtained in parallel from a two‐dimensional array. The structure of inputs and outputs is an N × N two‐dimensional array, and the number of levels is log2N. Here, we will define two‐dimensional permutation as one‐to‐one mapping on the set whose elements are pairs of indices of a two‐dimensional array. Among possible two‐dimensional permutations, are two‐dimensional shift and rotation. We will show the conditions for admissible permutations on the two‐dimensional Omega network. As for hardware, the complexity is N 2/4 m log2N and the delay time is log2N; of the same order as conventional Omega networks. Furthermore, we will discuss the case where the two‐dimensional Omega network has computing capability. We show that sum, maximum, and minimum of elements in two‐dimensional arrays, and two‐dimensional Fourier transformation can be obtained by one pass.