THE REFINE MULTIPROCESSOR - THEORETICAL PROPERTIES AND ALGORITHMS

A reconfigurable interconnection network based on a multi-ring archite cture called REFINE is described. REFINE embeds a single 1-factor of t he Boolean hypercube in any given configuration. The mathematical prop erties of the REFINE topology and the hardware for the reconfiguration switch are described. The REFINE topology is scalable in the sense th at the number of interprocessor communication links scales linearly wi th network size whereas the network diameter scales logarithmically wi th network size. Primitive parallel operations on the REFINE topology are described and analyzed. These primitive operations could be used a s building blocks for more complex parallel algorithms. A large class of algorithms for the Boolean n-cube which includes the FFT and the Ba tcher's bitonic sort is shown to map efficiently on the REFINE topolog y. The REFINE multiprocessor is shown to offer a cost-effective altern ative to the Boolean n-cube multiprocessor architecture without substa ntial loss in performance.