MIMD machine communication using the augmented data manipulator network

ABSTRACT

There have been many multistage interconnection networks proposed in the literature for interconnecting the processors that comprise large parallel processing systems. In this paper, the use of a multistage network in the MIMD mode of operation is considered. A tag based routing scheme is proposed for the Augmented Data Manipulator network. Also included is a rerouting scheme that allows a message blocked by a busy link in its present path to dynamically make use of a non-busy link and continue, when possible. Finally, a tag based broadcasting scheme is introduced that allows one processor to send messages to a power of two other processors.

REFERENCES

• 1: K. E. Batcher, "The flip network in STARAN," 1976 Int'l Conf. Parallel Processing, Aug. 1976, pp. 746-757.
• 2: F. Briggs, K. S. Fu, K. Hwang and J. Patel, "PM4 - a reconfigurable multimicroprocessor system for pattern recognition and image processing," Nat'l. Comp. Conf., June 1979, pp. 255-265.
• 3: T. Feng, "Data manipulating functions in parallel processors and their implementations," IEEE Trans. Comp., Vol. C-23, Mar. 1974, pp. 309-318.
• 4: M. J. Flynn, "Very high-speed computing systems," Proc. IEEE, Vol. 54, Dec. 1966, pp. 1901-1909.
• 5: L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
• 6: P. M. Kogge and H. S. Stone, "A parallel algorithm for the efficient solution of a general class of recurrence equations," IEEE Trans. Comp., Aug. 1973, pp. 786-792.
• 7: T. Lang and H. S. Stone, "A shuffle-exchange network with simplified control," IEEE Trans. Comp., Vol. C-25, Jan. 1976, pp. 55-65.
• 8: D. H. Lawrie, "Access and alignment of data in an array processor," IEEE Trans. Comp., Vol. C-24, Dec. 1975, pp. 1145-1155.
• 9: G. J. Lipovski and A. Tripathi, "A reconfigurable varistructure array processor," 1977 Int'l. Conf. Parallel Processing, Aug. 1977, pp. 165-174.
• 10: R. J. McMillen and H. J. Siegel, Multistage ADM and Cube Networks for MIMD Machines, Electrical Engineering School, Purdue, Technical Report in preparation.
• 11: Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979 [doi>10.1145/800090.802906]
• 12: M. C. Pease, "The indirect binary n-Cube microprocessor array," IEEE Trans. Comp., Vol. C-26, May 1977, pp. 458-473.
• 13: H. J. Siegel, "Analysis techniques for SIMD machine interconnection networks and the effects of processor address masks," IEEE Trans. Comp., Vol. C-26, Feb. 1977, pp. 153-161.
• 14: H. J. Siegel, "Preliminary design of a versatile parallel image processing system," 3rd Biennial Conf. Computing in Indiana, Apr. 1978, pp. 11-25.
• 15: H. J. Siegel, "Interconnection networks for SIMD machines," Computer, Vo1. 12, June 1979, pp. 57-65.
• 16: H. J. Siegel, "A model of SIMD machines and a comparison of various interconnection networks," IEEE Trans. Comp., Vol. C-28, Dec. 1979, pp. 907-917.
• 17: H. J., Siegel, R. J. McMillen, and P. T. Mueller Jr., "A survey of interconnection methods for reconfigurable parallel processing systems," 1979 Nat'l. Comp. Conf., June 1979, pp. 529-542. Reprinted in Japanese in Nikkei Electronics, No. 228, Dec. 1979, pp. 49-83.
• 18: H. J. Siegel, P. T. Mueller Jr., and Smalley, H. E., Jr., "Control of a partitionable multimicroprocessor system," 1978 Int'l. Conf. Parallel Processing, Aug. 1978, pp. 9-17.
• 19: H. J. Siegel, L. J. Siegel, R. J. McMillen, P. T. Mueller Jr., and S. D. Smith, "An SIMD/MIMD multimicro-processor system for image processing and pattern recognition," 1979 IEEE Comp. Soc. Conf. Pattern Recog. and Image Processing, Aug. 1979, pp. 214-224.
• 20: Howard Jay Siegel , S. Diane Smith, Study of multistage SIMD interconnection networks, Proceedings of the 5th annual symposium on Computer architecture, p.223-229, April 03-05, 1978 [doi>10.1145/800094.803052]
• 21: H. J. Siegel and S. D. Smith, "An interconnection network for multimicroprocessor emulator systems," 1st Int'l. Conf. Distributed Computing Systems, Oct. 1979, pp. 772-782.
• 22: S. D. Smith, and H. J. Siegel, "Recirculating, pipelined, and multistage SIMD interconnection networks," 1978 Int'l. Conf. Parallel Processing, Aug. 1978,pp. 206-214.
• 23: S. Diane Smith , H. J. Siegel, An emulator network for SIMD machine interconnection networks, Proceedings of the 6th annual symposium on Computer architecture, p.232-241, April 23-25, 1979 [doi>10.1145/800090.802913]
• 24: S. D. Smith and H. J. Siegel, Design and Analysis of Interconnection Networks for Partitionable Parallel Processing Systems, School of Electrical Engineering, Purdue University, Technical Report TR-EE 79-39, Aug. 1979.
• 25: Kuo Yen Wen, Interprocessor connections--capabilities, exploitation and effectiveness., 1976
• 26: C. Wu and T. Feng, "Routing techniques for a class of multistage interconnection networks," 1978 Int'l. Conf. Parallel Processing, Aug. 1978, pp. 197-205.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: ADM

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

General Terms:
Design