Randomized parallel communications on an extension of the omega network

ABSTRACT

Parallel communication algorithms and networks are central to large-scale parallel computing and, also, data communications. This paper identifies adverse source-destination traffic patterns and proposes a scheme for obtaining relief by means of randomized routing of packets on simple extensions of the well-known omega networks. Valiant and Aleliunas have demonstrated randomized algorithms, for a certain context which we call nonrenewal, that complete the communication task in time O(log N) with overwhelming probability, where N is the number of sources and destinations. Our scheme has advantages because it uses switches of fixed degree, requires no scheduling, and, for the nonrenewal context, is as good in proven performance. The main advantage of our scheme comes when we consider the renewal context in which packets are generated at the sources continually and asynchronously. Our algorithm extends naturally from the nonrenewal context. In the analysis in the renewal context we, first, explicitly identify the maximum traffic intensities in the internal links of the extended omega networks over all source-destination traffic specifications that satisfy loose bounds. Second, the benefits of randomization on the stability of the network are identified. Third, exact results, for certain restricted models for sources and transmission, and approximate analytic results, for quite general models, are derived for the mean delays. These results show that, in the stable regime, the maximum mean time from source to destination is asymptotically proportional to log N. Numerical results are presented.

REFERENCES

• 1: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• 2: François Baccelli , Erol Gelenbe , Brigitte Plateau, An End-to-End Approach to the Resequencing Problem, Journal of the ACM (JACM), v.31 n.3, p.474-485, July 1984 [doi>10.1145/828.1883]
• 3: BATCHER, K. E. Sorting networks and their applications. In AFIPS Spring Joint Computer Conference, vol. 32. AFIPS Press, Reston, Va., 1968, pp. 307-314.
• 4: BHUYAN, L. N., AND LEE, C. W. An interference analysis of interconnection networks. In Proceedings of the 1983 International Conference on Parallel Processing. IEEE, New York, 1983, pp. 2-9.
• 5: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• 6: BOROVKOV, A.A. Talk at Oberwolfach Conference on Applied Stochastic Processes, Apr. 1985.
• 7: CHERNOFF, H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics 23 (1952), 493-507.
• 8: Leonard Allen Cohn, A conceptual approach to general purpose parallel computer architecture, 1983
• 9: DADUNA, H. Passage times for overtake-free paths in Gordon-Newell networks. Adv. Appl. Prob. 14 (1981), 672-686.
• 10: 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
• 11: GOTTLIEB, A., GRISHMAN, R., K_RUSKAL, C. P., MCAULIFFE, K. P., RUDOLPH, L., AND SNm, M. The NYU ultracomputer-designing an MIMD shared memory parallel computer. IEEE Trans. Comput. C-32, 2 (Feb. 1983), 175-189.
• 12: A G Greenberg , J Goodman, Sharp approximation models of adaptive routing in mesh networks (preliminary report), Proc. of the international seminar on Teletraffic analysis and computer performance evaluation, p.255-270, December 1986, Amsterdam, The Netherlands
• 13: HOEFFDING, W. On the distribution of the number of successes in independent trials. Ann. Math. Statistics 27 (1956), 713-721.
• 14: Frank P. Kelly, The Dependence of Sojourn Times in Closed Queueing Networks, Proceedings of the International Workshop on Computer Performance and Reliability, p.111-121, September 26-30, 1983
• 15: KELLY, F.P. Blocking probabilities in large circuit-switched networks. Adv. Appl. Prob. 18 (1986), 473-505.
• 16: KINGMAN, J. F.C. The heavy traffic approximation in the theory of queues. In Proceedings of the Symposium on Congestion Theory, W. Smith and W. Wilkinson, Eds. The University of North Carolina Press, Chapel Hill, N.C., pp. 137-159.
• 17: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 18: KRAEMER, W., AND LANGENBACH-BELZ, M. Approximate formulae for the delay in the queueing system GI/G/l. in Congressbook of the 8th International Teletraffic Congress (Melbourne, Australia). 1976, pp. 235-1/8.
• 19: C. P. Kruskal , M. Snir , A. Weiss, The Distribution of Waiting Times in Clocked Multistage Interconnection Networks, IEEE Transactions on Computers, v.37 n.11, p.1337-1352, November 1988 [doi>10.1109/12.8700]
• 20: KUEHN, P.J. Approximate analysis of general queueing networks by decomposition. IEEE Trans. Commun. COM-27, l (Jan. 1979), 113-126.
• 21: KULZER, J. J. AND MONTGOMERY, W.A. Statistical switching architectures for future services. In Proceedings of the International Switching Symposium (Florence, Italy). ALl, Milano, Italy, Session 43A, May 1984.
• 22: LAWRIE, O.H. Access and alignment of data in an array processor. IEEE Trans. Comput. C-24 (1975), 1145-1155.
• 23: MARSHALL, K.T. Some inequalities in queueing. Oper. Res. 16 (1968), 651-665.
• 24: MAXEMCHUK, N. Regular mesh topologies in local and metropolitan area networks. A T&T Tech. J. 65, 7 (Sept. 1985), 1659-1685.
• 25: MITRA, O. Asymptotic analysis and computational methods for a class of simple, circuit-switched networks with blocking. Adv. Appl. Prob. 19 (1987), 219-239.
• 26: PARKER, D. S., JR. Notes on shuffle/exchange-type switching networks. IEEE Trans. Comput. C-29 (1980), 213-222.
• 27: PFISTER, G. F., BRANTLEY, W. C., GEORGE, D. A., HARVEY, S. L., KLEINFELDER, W. J., MCAULIFFE, K. P., MELTON, E. A., NORTON, V. A., AND WEISS, J. The IBM research parallel processor prototype (RP3): Introduction and architecture. In Proceedings of the 1985 International Conference on Parallel Processing. IEEE, New York, 1985, pp. 764-771.
• 28: PIPPENGER, N. Parallel communication with limited buffers. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2). ACM, New York, 1984, pp. 127-136.
• 29: RAMAKRISHNAN, K. G., AND MITRA, D. An overview of PANACEA, a software package for analyzing Markovian queueing networks. Bell Syst. Tech. J. 61, 10 (Dec. 1982), 2849-2872.
• 30: RAMAKRISHNAN, K. G., AND MITRA, D. A Short User's Manual for PANACEA 4.1 (Analytic Approximations). AT&T Bell Laboratories memorandum, Jan. 1985.
• 31: STOYAN, D. Comparison Methods for Queues and Other Stochastic Models. Wiley, New York, 1983.
• 32: Eli Upfal, Efficient schemes for parallel communication, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.55-59, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806682]
• 33: VALIANT, L.G. A scheme for fast parallel communication. SIAM J. Comput. 11 (1982) 350-361.
• 34: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 35: WALRAND, J., AND VARAIYA, P. Sojourn times and the overtaking condition in Jacksonian networks. Adv. Appl. Prob. 12 (I980), 1000-1018.
• 36: WHITT, W. The queueing network analyzer. Bell Syst. Tech. J. 62, 9, part 1 (Nov. 1983), 2779-2816.
• 37: WHITT, W. Performance of the queueing network analyzer. Bell Syst. Tech. J. 62, 9, Part l (Nov. 1983), 2817-2847.
• 38: WHITT, W. Blocking when service is required from several facilities simultaneously. A T& T Tech. J. 64, 8 (Oct. 1985), 1807-1856.

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)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Measurement, Performance, Reliability, Theory, Verification