Article

ECO: Efficient Collective Operations for Communication on Heterogeneous Networks

Authors:

Bruce Lowekamp,

Adam BeguelinAuthors Info & Claims

IPPS '96: Proceedings of the 10th International Parallel Processing Symposium

Pages 399 - 405

Published: 15 April 1996 Publication History

Abstract

PVM and other distributed computing systems have enabled the use of networks of workstations for parallel computation, but their approach of treating all networks as collections of point-to-point connections does not promote efficient communication---particularly collective communication. The Efficient Collective Operations package (ECO) contains programs which solve this problem by analyzing the network and establishing efficient communication patterns. This paper describes ECO and gives performance results of using ECO to implement the collective communication in CHARMM, a widely used macromolecular dynamics package. ECO substantially improves the performance of CHARMM on a heterogeneous network. ECO's approach gives a programmer the ability to use the available networks to their full potential without acquiring any knowledge of the network structure.

References

[1]

J. N. C. Árabe, A. Beguelin, B. Lowekamp, E. Seligman, M. Starkey, and P. Stephan. Dome: Parallel programming in a heterogeneous multi-user environment. Technical Report CMU-CS-95-137, Carnegie Mellon University, April 1995.

Digital Library

[2]

V. Bala, J. Bruck, R. Cypher, P. Elustondo, A. Ho, C.-T. Ho, S. Kipnis, and M. Snir. CCL: A portable and tunable collective communication library for scalable parallel computers. In Proceedings of 8th International Parallel Processing Symposium, pages 835-844. IEEE Comput. Soc. Press, 1994.

Digital Library

[3]

A. Bar-Noy and S. Kipnis. Designing broadcasting algorithms in the postal model for message-passing systems. In Proceedings of the 1992 Symposium on Parallel Algorithms and Architectures, pages 13-22. ACM, June 1992.

Digital Library

[4]

M. Barnett, S. Gupta, D. G. Payne, L. Shuler, R. van de Geijn, and J. Watts. Building a high-performance collective communication library. In Proceedings of IEEE Scalable High Performance Computing, pages 835-834. IEEE Comput. Soc. Press, 1994.

Digital Library

[5]

B. R. Brooks, R. E. Bruccoleri, B. D. Olafson, D. J. States, and S. S. M. Karplus. CHARMM: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry, 4:187-217, 1983.

[6]

D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken. LogP: Towards a realistic model of parallel computation. In Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 1-12. ACM, May 1993.

Digital Library

[7]

K. Efe. Heuristic models of task assignment scheduling in distributed systems. IEEE Computer, 19(8):897-916, 1982.

Digital Library

[8]

D. Evans and W. Butt. Load balancing with network partitioning using host groups. Parallel Computing, 20:325-345, 1994.

Digital Library

[9]

M. P. I. Forum. MPI: A message-passing interface standard. International Journal of Supercomputer Applications, 8(3/4), 1994. http://www.mcs.anl.gov/mpi/index.html.

[10]

A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam. PVM: Parallel Virtual Machine - A Users' Guide and Tutorial for Networked Parallel Computing. MIT Press, 1994.

Digital Library

[11]

W. Gropp, E. Lusk, and A. Skjellum. Using MPI. MIT Press, 1994.

[12]

C. Huang and P. K. McKinley. Design and implementation of global reduction operations across ATM networks. In Proceedings of 3rd IEEE International Symposium on High Performance Distributed Computing, pages 43-50. IEEE Comput. Soc. Press, 1994.

[13]

P. K. McKinley and J. W. S. Liu. Multicast tree construction in bus-based networks. Communications of the ACM, 33(1):29-41, January 1990.

Digital Library

[14]

P. K. McKinley, Y. Tsai, and D. F. Robinson. A survey of collective communication in wormhole-routed massively parallel computers. Technical Report MSU-CPS-94-35, Michigan State University, June 1994.

[15]

P. Mitra, D. G. Payne, L. Shuler, R. van de Geijn, and J. Watts. Fast collective communication libraries, please. Technical Report TR-95-22, The University of Texas, June 1995.

Digital Library

[16]

A. Stathopoulos, A. Ynnerman, and C. F. Fischer. A PVM implementation of the MCHF atomic structure package. International Journal of Supercomputer Applications and High Performance Computing, to appear, 1995. http://www.vuse.vanderbilt.edu/~andreas/publications/jsa.ps.

Cited By

Eyraud-Dubois LLegrand AQuinson MVivien F(2007)A first step towards automatically building network representationsProceedings of the 13th international Euro-Par conference on Parallel Processing10.5555/2391541.2391561(160-169)Online publication date: 28-Aug-2007
https://dl.acm.org/doi/10.5555/2391541.2391561
Gupta RVadhiyar S(2006)Application-oriented adaptive MPI_Bcast for gridsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899059(128-128)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899059
Barchet-Steffenel LMounié G(2006)Scheduling heuristics for efficient broadcast operations on grid environmentsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898860(324-324)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898860
Show More Cited By

ECO: Efficient Collective Operations for Communication on Heterogeneous Networks
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Redundant-wires-aware ECO timing and mask cost optimization
ICCAD '10: Proceedings of the International Conference on Computer-Aided Design

Spare cells are often used in engineering change order (ECO) timing optimization. By applying spare-cell rewiring techniques, timing-violated paths in a design can be fixed. In addition, mask re-spin cost economization has become a critical challenge ...
A search-based bump-and-refit approach to incremental routing for ECO applications in FPGAs

Incremental physical CAD is encountered frequently in the so-called engineering change order (ECO) process in which design changes are made typically late in the design process in order to correct logical and/or technological problems in the circuit. ...
ECO timing optimization using spare cells
ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

We introduce in this paper a new problem of ECO timing optimization using spare-cell rewiring and present the first work for this problem. Spare-cell rewiring is a popular technique for incremental timing optimization and/or functional change after the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IPPS '96: Proceedings of the 10th International Parallel Processing Symposium

April 1996

851 pages

ISBN:0818672552

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 15 April 1996

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Eyraud-Dubois LLegrand AQuinson MVivien F(2007)A first step towards automatically building network representationsProceedings of the 13th international Euro-Par conference on Parallel Processing10.5555/2391541.2391561(160-169)Online publication date: 28-Aug-2007
https://dl.acm.org/doi/10.5555/2391541.2391561
Gupta RVadhiyar S(2006)Application-oriented adaptive MPI_Bcast for gridsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899059(128-128)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899059
Barchet-Steffenel LMounié G(2006)Scheduling heuristics for efficient broadcast operations on grid environmentsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898860(324-324)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898860
Khuller SKim YWan YGibbons PSpirakis P(2005)Broadcasting on networks of workstationsProceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1073970.1074017(279-288)Online publication date: 18-Jul-2005
https://dl.acm.org/doi/10.1145/1073970.1074017
Legrand AMarchal LRobert Y(2005)Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platformsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2005.05.02165:12(1497-1514)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2005.05.021
Figueira SReddi V(2005)Topology-Based hypercube structures for global communication in heterogeneous networksProceedings of the 11th international Euro-Par conference on Parallel Processing10.1007/11549468_109(994-1004)Online publication date: 30-Aug-2005
https://dl.acm.org/doi/10.1007/11549468_109
Jakimovski BGusev M(2005)Improving multilevel approach for optimizing collective communications in computational gridsProceedings of the 2005 European conference on Advances in Grid Computing10.1007/11508380_56(548-556)Online publication date: 14-Feb-2005
https://dl.acm.org/doi/10.1007/11508380_56
Sundararaj AGupta ADinda PCox ASubhlok J(2004)Dynamic topology adaptation of virtual networks of virtual machinesProceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems10.1145/1066650.1066665(1-8)Online publication date: 22-Oct-2004
https://dl.acm.org/doi/10.1145/1066650.1066665
Wu JYeh SLiu P(2004)Efficient Multiple Multicast on Heterogeneous Network of WorkstationsThe Journal of Supercomputing10.1023/B:SUPE.0000022573.11074.0029:1(59-88)Online publication date: 1-Jul-2004
https://dl.acm.org/doi/10.1023/B%3ASUPE.0000022573.11074.00
Gupta ADinda P(2004)Inferring the topology and traffic load of parallel programs running in a virtual machine environmentProceedings of the 10th international conference on Job Scheduling Strategies for Parallel Processing10.1007/11407522_7(125-143)Online publication date: 13-Jun-2004
https://dl.acm.org/doi/10.1007/11407522_7
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten