Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Four SIMD multistage networks - Feng's data manipulator, STARAN flip network, omega network, and indirect binary n-cube—are analyzed. Three parameters - topology, interchange box, and control structure—are defined. It is shown that the latter three networks use equivalent topologies and differences in their capabilities result from the other parameters. An augmented data manipulator network using a modified control structure to perform more single pass interconnections than the other networks is presented. Some problems may be solved more efficiently if the 2n processing elements of an SIMD machine can be partitioned into submachines of size 2r. Single and multiple control partitioning are defined. The capabilities of these multistage networks to perform in these partioned environments are discussed.

REFERENCES

• 1: K. E. Batcher, "The multidimensional access memory in STARAN," IEEE Trans. Comput., Vol. C-26 (Feb., 1977), pp. 174-177.
• 2: K. E. Batcher, "The flip network in STARAN," 1976 Int. Conf. on Parallel Processing, (Aug. 1976), pp. 65-71.
• 3: Lyal H. Bauer, Implementation of Data Manipulating Functions on the STARAN Associative Processor, Proceedings of the Sagamore Computer Conference on Parallel Processing, p.209-227, August 20-23, 1974
• 4: T. Feng, Parallel Processing Characteristics and Implementation of Data Manipulating Functions, Dept. of Electrical and Computer Engineering, Syracuse University, RADC-TR-73-189 (Jul., 1973).
• 5: T. Feng, "Data manipulating functions in parallel processors and their implementations," IEEE Trans. Comput., Vol. C-23 (Mar., 1974), pp. 309-318.
• 6: M. J. Flynn, "Very high-speed computing systems," Proceedings of the IEEE, Vol. 54 (Dec., 1966), pp. 1901-1909.
• 7: T. Lang and H. S. Stone, "A shuffle-exchange network with simplified control," IEEE Trans. Comput., Vol. C-25 (Jan., 1976), pp. 55-65.
• 8: D. Lawrie, "Access and alignment of data in an array processor," IEEE Trans. Comput., Vol. C-24 (Dec., 1975), pp. 1145-1155.
• 9: G. J. Lipovski and A. Tripathi, "A reconfigurable varistructure array processor," 1977 Int. Conf. On Parallel Processing (Aug., 1977), pp. 165-174.
• 10: M. C. Pease, "The indirect binary n-cube microprocessor array," IEEE Trans. Comput., Vol. C-26 (May, 1977), pp. 458-473.
• 11: H. J. Siegel, "Analysis techniques for SIMD machine interconnection networks and the effects of processor address masks," IEEE Trans. Comput., Vol. C-26 (Feb., 1977), pp. 153-161.
• 12: H. J. Siegel, "Single instruction stream - multiple data stream machine interconnection network design," 1976 Int. Conf. on Parallel Processing (Aug., 1976), pp. 272-282.
• 13: Howard Jay Siegel, The universality of various types of SIMD machine interconnection networks, Proceedings of the 4th annual symposium on Computer architecture, p.70-79, March 23-25, 1977
• 14: Herbert Sullivan , Theodore R. Bashkow , David Klappholz, A Large Scale, Homogenous, Fully Distributed Parallel Machine, II, Proceedings of the 4th annual symposium on Computer architecture, p.118-124, March 23-25, 1977

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Performance