Randomized parallel communication (Preliminary Version)

ABSTRACT

Using a simple finite degree interconnection network among n processors and a straightforward randomized algorithm for packet delivery, it is possible to deliver a set of n packets travelling to unique targets from unique sources in 0(log n) expected time. The expected delivery time is in other words the depth of the interconnection graph. The b -way shufile networks are examples of such. This represents a crude analysis of the transient response to a sudden but very uniform request load on the network. Variations in the uniformity of the load are also considered. Consider si packets with randomly chosen targets beginning at a source labelled i. The expected overall delay is then [equation] where the labelling is chosen so that s1≥s2≥. These ideas can be used to guage the asymptotic efficiency of various synchronous parallel algorithms which use such a randomized communications system. The only important assumption is that variations in the physical transmission time along any connection link are negligible in comparison to the amount of work done at a processor.

REFERENCES

• 1: Lev, G., Pippenger, N., Valiant, L.: "A fast parallel algorithm for routing in permutation networks", IEEE Trans. on Computers, Vol. 30, 1981, p.93.
• 2: 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]
• 3: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 4: Loeve, M: Probability Theory I, Graduate Text in Mathematics No. 45, Springer Verlag, New York, 1967.
• 5: Marshall, A. W., Olkin, I.: Inequalities: Theory of Majorization and Its Applications, Academic Press, New York, 1979.
• 6: A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
• 7: Frederick S. Hillier , Gerald J. Lieberman, Introduction to operations research, 4th ed., Holden-Day, Inc., San Francisco, CA, 1986
• 8: Nassimi, D. and Sahni, S.: "A Self-Routing Benes Network and Parallel Permutation Algorithms", IEEE Trans. on Computers, Vol. 30, 1981, p. 332.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
Average response time, Parallel communication, Randomization, Worst case