Design and Analysis of Interconnection Networks for Partitionable Parallel Processing Systems

摘要

A single instruction stream - multiple data stream (SIMD) computer performs one algorithm (single instruction stream) on vectors of data of a control unit (CU), processing elements (PEs), and an interconnection network. The CU broadcasts instructions to the N Pes (where N is a power of two). The interconnection network is the mechanism that allows PEs to pass data among themselves. Four types of interconnection networks are discussed in this work: the Shuffle-Exchange network, the Cube network, the ILLIAC network, and the Plus-Minus 2 (PM2I) network. Each type has been discussed in the literature and used in an existing or proposed machine design. For each of these four network types, different hardware structures are considered. A recirculating network consists of one stage of switches that is reused until the data reach their final destinations. A combinational logic multistage network consists of several stages of switches and, usually, data is transferred in one pass through the network. In pipelined multistage networks, which are introduced, registers are inserted after each stage of a combinational logic multistage network. The data are divided into segments, and these segments are passed in a parallel-pipelined manner. Hardware implementations for recirculating, combinational logic multistage, and pipelined multistage networks are presented and analyzed.