Browse Prior Art Database

Interconnection Networks for SIMD Machines

IP.com Disclosure Number: IPCOM000131406D
Original Publication Date: 1979-Jun-01
Included in the Prior Art Database: 2005-Nov-10
Document File: 14 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

Howard Jay Siegel: AUTHOR [+3]

Abstract

[Figure containing following caption omitted: Many SIMD interconnection networks have been proposed. To put the different approaches into perspective, this analysis compares a number of single- and multistage networks.] With the advent of microprocessors, large-scale parallel processing systems with as many as 2'4 to 2~6 processors have become feasible."; 2 One multimicroprocessor structure -- the SIMD (single instruction stream-multiple data stream) mode of parallel processing -- is especially suitable for exploiting the parallelism inherent in certain tasks. SIMD systems are currently being used for scientific operations such as matrix calculations3 and image processing.4 5 In the future, their scope may be broadened to include business calculations that require the same program to be executed on many different data sets -- e.g., computing bank-account interest. Two existing SIMD machines are the Illiac IV6 and Staran,7 and many new ones have been proposed.' In designing SIMD systems, constructing an interconnection network for communications among the processors and memories presents a major problem. In this article, we analyze different approaches to network design, limiting our discussion to SIMD machine networks (other types are explored elsewheret7~i9). Interconnecting N processors and N memory modules in an SIMD system where Nmay be 26to 2~6 is a non-trivial task. A single shared bus is not sufficient, since in an SIMD machine it is desirable to allow many processors to send data to other processors simultaneously (e.g., from processor i to processor i+ 1, 0< i<N -- 1). Ideally, one would like each processor directly to every other processor, but this is highly impractical for large N. since each processor would require N -- 1 lines. An alternate network which allows all processors to communicate simultaneously is the crossbar switch.20 The difficulty here is that network costs grow with N2; given current technology, this makes crossbar switches infeasible for large systems.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1979 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

Interconnection Networks for SIMD Machines

Howard Jay Siegel Purdue University

(Image Omitted: Many SIMD interconnection networks have been proposed. To put the different approaches into perspective, this analysis compares a number of single- and multistage networks.)

With the advent of microprocessors, large-scale parallel processing systems with as many as 2'4 to 2~6 processors have become feasible." 2 One multimicroprocessor structure -- the SIMD (single instruction stream-multiple data stream) mode of parallel processing -- is especially suitable for exploiting the parallelism inherent in certain tasks. SIMD systems are currently being used for scientific operations such as matrix calculations3 and image processing.4 5 In the future, their scope may be broadened to include business calculations that require the same program to be executed on many different data sets -- e.g., computing bank-account interest.

Two existing SIMD machines are the Illiac IV6 and Staran,7 and many new ones have been proposed.' In designing SIMD systems, constructing an interconnection network for communications among the processors and memories presents a major problem. In this article, we analyze different approaches to network design, limiting our discussion to SIMD machine networks (other types are explored elsewheret7~i9).

Interconnecting N processors and N memory modules in an SIMD system where Nmay be 26to 2~6 is a non-trivial task. A single shared bus is not sufficient, since in an SIMD machine it is desirable to allow many processors to send data to other processors simultaneously (e.g., from processor i to processor i+ 1, 0< i<N -- 1). Ideally, one would like each processor directly to every other processor, but this is highly impractical for large N. since each processor would require N -- 1 lines. An alternate network which allows all processors to communicate simultaneously is the crossbar switch.20 The difficulty here is that network costs grow with N2; given current technology, this makes crossbar switches infeasible for large systems.

To solve the problem of providing fast, efficient communiations at a reasonable cost, many different networks have been proposed in the literature, a number of which we discuss here. However, no single network is generally considered "best," since the cost effectiveness of a particular design varies with such factors as the computational tasks for which it will be used, the desired speed of interprocessor data transfers, the actual hardware implementation of the network, the number of p...