No Access

COMMUNICATION SCHEDULING WITH RE-ROUTING BASED ON STATIC AND HYBRID TECHNIQUES

DAVID R. SURMA

Department of Computer and Information Sciences, Indiana University South Bend, South Bend, IN 46634, USA

Search for more papers by this author

EDWIN H.-M. SHA

Department of Computer Science, University of Texas at Dallas, Dallas, TX 75083, USA

Search for more papers by this author

, and

NELSON PASSOS

Department of Computer Science, Midwestern State University, Wichita Falls, TX 76308, USA

Search for more papers by this author

https://doi.org/10.1142/S0218126604001829Cited by:0 (Source: Crossref)

Abstract

In massively parallel systems, the performance gains are often significantly diminished by the inherent communication overhead. This overhead is caused by the required message passing resulting from the task allocation scheme. In this paper, techniques to reduce this communication overhead by both scheduling the communication and determining the routing that the messages should take within a tightly-coupled processor network are presented. Using the recently developed Collision Graph model, static scheduling algorithms are derived which work at compile-time to determine the ordering and routing of the individual message transmissions. Since a priori knowledge about the network traffic required by static scheduling may not be available or accurate, this work also considers dynamic scheduling. A novel hybrid technique is presented which operates in a dynamic environment yet uses known information obtained by analyzing the communication patterns. Experiments performed show significant improvement over baseline techniques.

Keywords:

References

H. Kasahara and S. Narita, IEEE Trans. Comput. C-33, 1023 (1984). Crossref, Web of Science, Google Scholar
A. A. Munshi and B. Simons, SIAM J. Comput. 19, 728 (1990). Crossref, Web of Science, Google Scholar
H. El-Rewini , T. G. Lewis and H. H. Ali , Task Scheduling in Parallel and Distributed Systems ( Prentice-Hall , Englewood Cliffs, NJ , 1994 ) . Google Scholar
S. Shukla, B. Little and A. Zaky, A compile-time technique for controlling real-time execution of task-level data-flow graphs, 1992 Int. Conf. Parallel Processing, Vol. II (1992), pp. 49–56 . Google Scholar
D. I. Moldovan and J. A. B. Fortes, IEEE Trans. Comput. C-35, 1 (1986). Crossref, Web of Science, Google Scholar
K. R. Baker , Introduction to Sequencing and Scheduling ( Wiley , New York , 1974 ) . Google Scholar
R. W. Conway , W. L. Maxwell and L. W. Miller , Theory of Scheduling ( Addison-Wesley , Reading MA , 1967 ) . Google Scholar
P. K. McKinley, Y. Tsai and D. F. Robinson, IEEE Comput. 28, 39 (1995). Crossref, Web of Science, Google Scholar
W. J. Dally and C. L. Seitz, J. Distributed Comput. 1, 187 (1986). Crossref, Web of Science, Google Scholar
L. M. Ni and P. McKinley, IEEE Comput. 26, 62 (1993). Crossref, Web of Science, Google Scholar
S. Lee and J. Kim, Path selection for communicating tasks in a wormhole-routed multicomputer, 1994 Int. Conf. Parallel Processing, Vol. 3 (1994), pp. 172–175 . Google Scholar
W. J. Dally and C. L. Seitz, IEEE Trans. Comput. C-36, 547 (1987). Crossref, Web of Science, Google Scholar
A. S. Tanenbaum , Computer Networks ( Prentice-Hall , New Jersey , 1996 ) . Google Scholar
R. P. Bianchini and J. P. Shen, IEEE Trans. Comput. C-36, 396 (1987). Crossref, Web of Science, Google Scholar
D. D. Kandlur and K. G. Shin, IEEE Trans. Comput. C-41, 1257 (1992). Web of Science, Google Scholar
A. Eberhart and J. Li, Contention-free communication scheduling on 2d meshes, 1996 Int. Conf. Parallel Processing (1996), pp. 44–51 . Google Scholar
D. R. Surma and E. Sha, Application specific communication scheduling on parallel systems, Eighth Int. Conf. Parallel and Distributed Computing Systems (1995), pp. 137–139 . Google Scholar
D. R. Surma, S. Tongsima and E. Sha, Optimal communication scheduling based on collision graph model, 1996 Int. Conf. Acoustics, Speech and Signal Processing, Vol. VI (1996), pp. 3319–3322 . Google Scholar
D. R. Surma and E. Sha, Static communication scheduling for minimizing collisions in application-specific parallel systems, Int. Conf. Application-Specific Systems, Architectures, and Processors (1996), pp. 210–219 . Google Scholar
D. R. Surma, Collision graph based communication reduction techniques for mesh networks, 14th Int. Conf. Computer Applications in Industry and Engineering (2001), pp. 9–12 . Google Scholar
D. R. Surma and E. Sha, Hybrid static-dynamic communication scheduling for parallel systems, ACM Symp. Applied Computing (1997), pp. 374–379 . Google Scholar
D. R. Surma and E. Sha, Int. J. Comput. Appl. 5, 11 (1998). Web of Science, Google Scholar
D. R. Surma and E. Sha, Efficient communication scheduling with re-routing based on collision graphs, Int. Symp. High Performance Computing Systems (1997), pp. 483–492 . Google Scholar
D. R. Surma and E. Sha, SCORE: An efficient technique to reduce congestion in parallel systems, Tenth Int. Conf. Parallel and Distributed Computing Systems (1997), pp. 198–203 . Google Scholar
D. R. Surma, Communication reduction techniques for torus networks based on collision graphs, 13th Int. Conf. Parallel and Distributed Computing Systems (2000), pp. 262–267 . Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability, A Guide to the Theory of NP-Completeness ( W. H. Freeman and Company , New York , 1979 ) . Google Scholar
K. Hwang , Advanced Computer Architecture, Parallelism, Scalability, Programmability ( McGraw-Hill , New York , 1993 ) . Google Scholar
I. Corporation, Paragon XP/S Product Overview (1991) . Google Scholar
D. Lenoskiet al., IEEE Comput. 25, 63 (1992). Crossref, Web of Science, Google Scholar
C. Lutz et al., Design of the mosaic element, Proc. MIT Conf. Advanced Research in VLSI (1984), pp. 1–10 . Google Scholar
J. Li and M. W. Mutka, Priority based real-time communication for large scale wormhole networks, Int. Conf. Parallel Processing Symp. (1994), pp. 433–438 . Google Scholar
T. H. Cormen , C. E. Leiserson and R. L. Rivest , Introduction to Algorithms ( McGraw-Hill , New York , 1990 ) . Google Scholar