Performance and fault tolerance improvements in the Inverse Augmented Data Manipulator network

ABSTRACT

The Inverse Augmented Data Manipulator (IADM) is a multistage interconnection network based on the Augmented Data Manipulator (ADM) and Feng's data manipulator. It is designed to be used in large-scale parallel/distributed processing systems for communication among processors, memories, and other system devices. Two aspects of IADM network design are discussed: performance and fault tolerance. A single stage look-ahead scheme for predicting blockage is presented to enhance performance. Next, one method of adding some links to the network to enable it to tolerate one link failure is described. Finally, a different method of adding links is shown that both improves performance and allows the network to tolerate two switching element or two link failures. Included is a new routing tag scheme that accommodates the new links.

REFERENCES

• 1: G. B. Adams III, H. J. Siegel, "The extra stage cube: a fault tolerant interconnection network for supersystems," IEEE Trans. Comp., Vol.C-31, scheduled to appear May 1982.
• 2: D. P. Agrawal, "Testing and fault-tolerance of multistage interconnection networks," Computer, to appear Apr. 1982.
• 3: W. J. Bouknight, et al., "The Illiac IV system," Proc. IEEE, Vol. 60, pp. 369-388, Apr.1972.
• 4: F. Briggs, K. Hwang, K. S. Fu, M. Dubois, "PUMPS architecture for pattern analysis and image data-base management," Pattern Recognition and Image Proc. Conf., pp. 387-398, Aug. 1981.
• 5: D. M. Dias, J. R. Jump, "Analysis and simulation of buffered delta networks," IEEE Trans. Comp., pp. 273-282, Apr. 1981.
• 6: T. Feng, "Data manipulating functions in parallel processors and their implementations," IEEE Trans. Comp., Vol. C-23, pp. 309-318, Mar. 1974.
• 7: T. Feng, C. Wu, "Fault-diagnosis for a class of multistage interconnection networks," IEEE Trans. Comp., Vol. C-30, pp. 743-758, Oct. 1981.
• 8: M. J. Flynn, "Very high-speed computing systems," Proc. IEEE, Vol. 54, pp. 1901-1909, Dec.1966.
• 9: C. Jensen, "Taking another approach to supercomputing," Datamation, Vol. 24, pp. 159-172, Feb. 1978.
• 10: D. H. Lawrie, C. Vora, "The prime memory system for array access," 1980 Int'l. Conf. Parallel Processing, pp.81-87, Aug. 1980.
• 11: R. J. McMillen, H. J. Siegel, "The hybrid cube," Distributed Data Acquisition, Computing, and Control Symp., pp. 11-22, Dec. 1980.
• 12: Robert J. McMillen , Howard Jay Siegel, Dynamic rerouting tag schemes for the augmented data manipulator network, Proceedings of the 8th annual symposium on Computer Architecture, p.505-516, May 12-14, 1981, Minneapolis, Minnesota, United States
• 13: J. J. Narraway, K-M. So, "Fault diagnosis in inter-processor switching networks," Int'l. Conf. Circuits and Computers, pp. 750-753, Oct. 1980.
• 14: D. K. Pradhan, "Interconnection topologies for fault-tolerant parallel and distributed architectures," 1981 Int'l. Conf. parallel Processing, pp. 238-242, Aug. 1981.
• 15: D. K. Pradhan, S. M. Reddy, "A fault-tolerant communication architecture for distributed systems," 11th Fault-Tolerant Computing Symposium, pp. 214-220, June 1981.
• 16: B. D. Rathi, M. Malek, "Fault diagnosis of interconnection networks," Distributed Data Acquisition, Computing, and Control Symp., pp. 110-119, Dec. 1980.
• 17: M. C. Sejnowski, E. T. Upchurch, R. N. Kapur, D. P. S. Charlu, G. J. Lipovski, "An overview of the Texas Reconfigurable Array Comp.," AFIPS 1980 Nat'l. Comp. Conf., pp. 631-641, June 1980.
• 18: John P. Shen , John P. Hayes, Fault tolerance of a class of connecting networks, Proceedings of the 7th annual symposium on Computer Architecture, p.61-71, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801910]
• 19: H. J. Siegel, "The theory underlying the partitioning of permutation networks," IEEE Trans. Comp., Vol. C-29, pp. 791-801, Sept. 1980.
• 20: H. J. Siegel, R. J. McMillen, "Using the Augmented Data Manipulator Network in PASM," Computer, Vol. 14, pp. 25-33, Feb. 1981.
• 21: H. J. Siegel, R. J. McMillen, "The multistage cube: a versatile interconnection network," Computer, Vol. 14, pp. 65-76, Dec. 1981.
• 22: H. J. Siegel, L. J. Siegel, F. C. Kemmerer, P. T. Mueller, Jr., H. E. Smalley, Jr., and S. D. Smith, "PASM: a partitionable SIMD/MIMD system for image processing and pattern recognition," IEEE Trans. Comp., Vol. C-30, pp. 934-947, Dec. 1981.
• 23: 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]
• 24: R. J. Swan, S. H. Fuller, D. P. Siewiorek, "Cm*: a modular, multi-microprocessor," AFIPS 1977 Nat'l. Comp. Conf., pp. 637-644, June 1977.
• 25: Suchai Thanawastien, The shuffle/exchange-plus networks, Proceedings of the 20th annual Southeast regional conference, p.89-96, April 01-03, 1982, Knoxville, Tennessee [doi>10.1145/503896.503912]
• 26: Anand R. Tripathi , G. Jack Lipovski, Packet switching in banyan networks, Proceedings of the 6th annual symposium on Computer architecture, p.160-167, April 23-25, 1979 [doi>10.1145/800090.802905]
• 27: W. A. Wulf, C. G. Bell, "C.mmp—a multi-miniprocessor," AFIPS 1972 Fall Joint Comp. Conf., pp. 765-777, Dec. 1972.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

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

General Terms:
Design, Performance