D. Mitra
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.
- 1 ALEL{UNAS, R. Randomized parallel communication. In Proceedings of the ACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Ont., Canada, Aug. 18-20). ACM, New York, 1982, pp. 60-72. Google Scholar
- 2 BACCELU, F., GELENBE, E., AND PLATEAU, B. An end-to-end approach to the resequencing problem. J. ACM 31, 3 (July 1984), 474-485. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 5 BORODIN, A., AND HOPCROFT, J.E. Routing, merging and sorting on parallel models of computation. J. Comput. Sci. Syst. Sci. 30 (1985), 130-145. Google Scholar
- 6 BOROVKOV, A.A. Talk at Oberwolfach Conference on Applied Stochastic Processes, Apr. 1985.Google Scholar
- 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.Google Scholar
- 8 COHN, L. A. A conceptual approach to general purpose parallel computer architecture. Ph.D. dissertation, Columbia Univ., New York, N.Y., 1983. Google Scholar
- 9 DADUNA, H. Passage times for overtake-free paths in Gordon-Newell networks. Adv. Appl. Prob. 14 (1981), 672-686.Google Scholar
- 10 GOKE, G. R., AND DPOVSKI, G.J. Banyan networks for partitioning multiprocessor system. In Proceedings of the 1st Annual Symposium on Computer Architecture. IEEE, New York, 1973, pp. 21-28. Google Scholar
- 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.Google Scholar
- 12 GREENBERG, A. G., AND GOODMAN, J. Sharp approximate analysis of adaptive routing in mesh networks. In Teletraffic Analysis and Computer Performance Evaluation, O. J. Boxma, J. W. Cohen, and H. C. Tijms, Eds. Elsevier (North-Holland), New York, 1986, pp. 225-270. Google Scholar
- 13 HOEFFDING, W. On the distribution of the number of successes in independent trials. Ann. Math. Statistics 27 (1956), 713-721.Google Scholar
- 14 KELLY, F.P. The dependence of sojourn times in closed queueing networks. In Mathematical Computer Performance and Reliability, G. Iazeolla, P. J. Courtois, and A. Hordijk, Eds. Elsevier Science Publishers B. V. (North-Holland), New York, 1984, pp. 111-121. Google Scholar
- 15 KELLY, F.P. Blocking probabilities in large circuit-switched networks. Adv. Appl. Prob. 18 (1986), 473-505.Google Scholar
- 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.Google Scholar
- 17 KLEINROCK, L. Queueing Systems, vol. I and II. Wiley, New York, 1975. Google Scholar
- 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.Google Scholar
- 19 KRUSKAL, C. P., SNIR, M., AND WEISS, A. The distribution of waiting times in clocked multistage interconnection networks. IEEE Trans. Comput. To appear. Google Scholar
- 20 KUEHN, P.J. Approximate analysis of general queueing networks by decomposition. IEEE Trans. Commun. COM-27, l (Jan. 1979), 113-126.Google Scholar
- 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.Google Scholar
- 22 LAWRIE, O.H. Access and alignment of data in an array processor. IEEE Trans. Comput. C-24 (1975), 1145-1155.Google Scholar
- 23 MARSHALL, K.T. Some inequalities in queueing. Oper. Res. 16 (1968), 651-665.Google Scholar
- 24 MAXEMCHUK, N. Regular mesh topologies in local and metropolitan area networks. A T&T Tech. J. 65, 7 (Sept. 1985), 1659-1685.Google Scholar
- 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.Google Scholar
- 26 PARKER, D. S., JR. Notes on shuffle/exchange-type switching networks. IEEE Trans. Comput. C-29 (1980), 213-222.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 31 STOYAN, D. Comparison Methods for Queues and Other Stochastic Models. Wiley, New York, 1983.Google Scholar
- 32 UPFAL, E. Efficient schemes for parallel communication. In Proceedings of the ACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Ont., Canada, Aug. 18-20). ACM, New York, 1982, pp. 55-59. Google Scholar
- 33 VALIANT, L.G. A scheme for fast parallel communication. SIAM J. Comput. 11 (1982) 350-361.Google Scholar
- 34 VALIANT, L. G., AND BREaNER, G. J. Universal schemes for parallel communication. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing (Milwaukee, Wis., May 11-13). ACM, New York, 1981, pp. 263-277. Google Scholar
- 35 WALRAND, J., AND VARAIYA, P. Sojourn times and the overtaking condition in Jacksonian networks. Adv. Appl. Prob. 12 (I980), 1000-1018.Google Scholar
- 36 WHITT, W. The queueing network analyzer. Bell Syst. Tech. J. 62, 9, part 1 (Nov. 1983), 2779-2816.Google Scholar
- 37 WHITT, W. Performance of the queueing network analyzer. Bell Syst. Tech. J. 62, 9, Part l (Nov. 1983), 2817-2847.Google Scholar
- 38 WHITT, W. Blocking when service is required from several facilities simultaneously. A T& T Tech. J. 64, 8 (Oct. 1985), 1807-1856.Google Scholar
Index Terms
- Randomized parallel communications on an extension of the omega network
Recommendations
Constant-Time Randomized Parallel String Matching
Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern ...
Randomized Priority Queues for Fast Parallel Access
Parallel and distributed data structuresWe present simple randomized algorithms for parallel priority queues on distributed memory machines. Inserting O(n) elements or deleting the O(n) out ofmsmallest elements usingnprocessors requires O(Tcoll+ log(m/n)) amortized time with high probability ...
Tight Analysis of Parallel Randomized Greedy MIS
Special Issue on Soda'18 and Regular PapersWe provide a tight analysis that settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA’12].
The parallel/distributed randomized greedy ...
Comments