A general class of processor interconnection strategies

ABSTRACT

A new class of general topologies is proposed in this paper for interconnecting a large network of computers in parallel and distributed environment. These structures have been shown to possess small internode distances, fairly low number of links per node, easy message routing and large number of alternate paths that can be used in case of faults in the system. The interconnection is based on a mixed radix number system, presented in this paper. The technique results in a variety of structures for a given number of processors N, depending on the required diameter in the network. A bus oriented structure is also introduced here, based on the same mathematical framework. These structures possess only two I/O ports per processor and are also shown to have small internode distances.

REFERENCES

• 1: M.T. Liu, "Distributed loop computer networks," in Advances in Computers, Vol. 17, New York, Academic Press, 1978.
• 2: S.I. Saffer et al., "NODAS - The net oriented data acquisition system for the medical environment," AFIPS Conf. Proc. Vol. 46, pp. 188-195, NCC, 1977.
• 3: E.M. Aupperle, "MERIT Computer network: Hardware considerations," in Computer Networks, pp. 49-63, Prentice Hall, 1972.
• 4: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 5: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
• 6: L.D. Wittie, "Communication structures for large networks of micro computers," IEEE Trans. on Computers, C-30, No. 4, pp. 264-273, April 1981.
• 7: Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
• 8: D.K. Pradhan, "Interconnection topologies for fault tolerant parallel and distributed architectures," Proc. 10th Int. Conf. on Parallel Processing, pp. 238-242, Aug. 1981.
• 9: D.K. Pradhan and S.M. Reddy, "A fault tolerant communication architecture for distributed systems," Proc. 11th Fault Tolerant Comp. Symp., pp. 214-220, May 1981.
• 10: L. Kleinrock, "Queueing systems: Vol. II, computer applications,"# John Wiley and Sons, 1976.
• 11: R. Finkel and M.H. Solomon, "Processor Interconnection Strategies," IEEE Trans. on Computers, C-29, pp. 360-371, May 1980.
• 12: George A. Anderson , E. Douglas Jensen, Computer Interconnection Structures: Taxonomy, Characteristics, and Examples, ACM Computing Surveys (CSUR), v.7 n.4, p.197-213, Dec. 1975 [doi>10.1145/356654.356658]
• 13: D.P. Agrawal, T.Y. Feng and C.L. Wu, "A survey of communication processor systems," Proc. Computer Software and Applications (COMPSAC) Conference, Chicago, pp. 668-673, Nov. 1978.
• 14: D.P. Agrawal and T.Y. Feng, "A study of communication processor systems," Tech. Report submitted to Rome Air Development Centre, RADC-TR-79-310, Dec. 1979.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Design