A multiprocessor network suitable for single-chip VLSI implementation

Abstract

This paper presents a multiprocessor network architecture suitable for VLSI implementation. The proposed class of architectures is based on De Bruijn graphs which are distinct from the well-studied shuffle-exchange graphs. Compared to these latter De Bruijn graphs possess a smaller diameter and a greater fault-tolerance. The proposed architectures are shown to be suitable for efficient execution of parallel algorithms such as the N-point fast Fourier transform (FFT). It is shown that any VLSI layout of the proposed networks requires an area of atleast Ω(N ² /logN), thus, providing a lower bound which is greater than that for shuffle-exchange graphs. Two procedures for laying out these networks on a VLSI chip are presented. The first procedure produces an O(N ² /logN)-area layout and has a time complexity of O(N). The second procedure also produces an O(N ² /logN)-area layout with good aspect ratio close to unity (for small N).