research-article

Randomizing task placement does not randomize traffic (enough)

Authors:

Ana Jokanovic,

Bogdan Prisacari,

German Rodriguez,

Cyriel MinkenbergAuthors Info & Claims

IMA-OCMC '13: Proceedings of the 2013 Interconnection Network Architecture: On-Chip, Multi-Chip

Pages 9 - 12

https://doi.org/10.1145/2482759.2482762

Published: 23 January 2013 Publication History

Get Access

Abstract

Dragonflies are one of the most promising topologies for the Exascale effort for their scalability and cost. Dragonflies achieve very high throughput under uniform traffic, but have a pathological behavior under other regular traffic patterns, some of them very common in HPC applications. A recent study showed that randomization of task placement can make pathological, regular (multi-dimensional stencil) traffic patterns behave similar to uniform traffic.

In this work we provide a theoretical model that is able to predict the expected performance of a generic dragonfly network under uniform traffic and characterize performance-optimal dragonflies. We then analyze whether this model can be extended to other patterns by means of benchmarking the performance of multiple such patterns under both contiguous and randomized task placement. We conclude that, although in comparison with contiguous task placement, randomization does lead to a significant improvement in performance for pathological communication patterns, this performance is not on par with that of uniform traffic, but rather half of it.

References

[1]

A. Bhatele, N. Jain, W. D. Gropp, and L. V. Kale. Avoiding hot-spots on two-level direct networks. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC '11, pages 76:1--76:11, New York, NY, USA, 2011. ACM.

Digital Library

Google Scholar

[2]

W. Dally and B. Towles. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.

Digital Library

Google Scholar

[3]

M. García, E. Vallejo, R. Beivide, M. Odriozola, C. Camarero, M. Valero, G. Rodríguez, J. Labarta, and C. Minkenberg. On-the-fly adaptive routing in high-radix hierarchical networks. In The 41st International Conference on Parallel Processing (ICPP), 09 2012.

Digital Library

Google Scholar

[4]

J. Kim, W. J. Dally, S. Scott, and D. Abts. Technology-driven, highly-scalable dragonfly topology. In Proceedings of the 35th Annual International Symposium on Computer Architecture, ISCA '08, pages 77--88, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

Google Scholar

[5]

L. G. Valiant. A scheme for fast parallel communication. SIAM J. Comput., 11(2):350--361, 1982.

Digital Library

Google Scholar

Cited By

View all

Chinavinijkul INewcomb JXi LBunde DScheideler CFineman J(2018)Brief AnnouncementProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210665(91-93)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210665
Chen DHeidelberger PStunkel CSugawara YMinkenberg CPrisacari BRodriguez G(2016)An evaluation of network architectures for next generation supercomputersProceedings of the 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computing Systems10.5555/3019057.3019059(11-21)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3019057.3019059
Chen DHeidelberger PStunkel CSugawara YMinkenberg CPrisacari BRodriguez G(2016)An Evaluation of Network Architectures for Next Generation Supercomputers2016 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS)10.1109/PMBS.2016.007(11-21)Online publication date: Nov-2016
https://doi.org/10.1109/PMBS.2016.007
Show More Cited By

Index Terms

Randomizing task placement does not randomize traffic (enough)

Recommendations

Performance implications of remote-only load balancing under adversarial traffic in Dragonflies
INA-OCMC '14: Proceedings of the 8th International Workshop on Interconnection Network Architecture: On-Chip, Multi-Chip

Dragonfly topologies are recent network designs that are considered one of the most promising interconnect options for Exascale systems. They offer a low diameter and low network cost, but do so at the expense of path diversity, which makes them ...
Randomizing task placement and route selection do not randomize traffic (enough)

Dragonflies are one of the most promising topologies for the Exascale effort for their scalability and cost. Dragonflies achieve very high throughput under uniform traffic, but have a pathological behavior under other regular traffic patterns, some of ...
Quality of service using traffic engineering over MPLS: an analysis
LCN '00: Proceedings of the 25th Annual IEEE Conference on Local Computer Networks

We compare the service received by TCP and UDP flows when they share either a link or a Multiprotocol Label Switching (MPLS) traffic trunk. Since MPLS traffic trunks allow non-shortest path links also to be used, the total network throughput goes up ...

Comments

Information & Contributors

Information

Published In

IMA-OCMC '13: Proceedings of the 2013 Interconnection Network Architecture: On-Chip, Multi-Chip

January 2013

29 pages

ISBN:9781450317849

DOI:10.1145/2482759

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

INA-OCMC '13

INA-OCMC '13: On-Chip, Multi-Chip

January 23, 2013

Berlin, Germany

Acceptance Rates

IMA-OCMC '13 Paper Acceptance Rate 7 of 17 submissions, 41%;

Overall Acceptance Rate 12 of 27 submissions, 44%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
132
Total Downloads

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

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chinavinijkul INewcomb JXi LBunde DScheideler CFineman J(2018)Brief AnnouncementProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210665(91-93)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210665
Chen DHeidelberger PStunkel CSugawara YMinkenberg CPrisacari BRodriguez G(2016)An evaluation of network architectures for next generation supercomputersProceedings of the 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computing Systems10.5555/3019057.3019059(11-21)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3019057.3019059
Chen DHeidelberger PStunkel CSugawara YMinkenberg CPrisacari BRodriguez G(2016)An Evaluation of Network Architectures for Next Generation Supercomputers2016 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS)10.1109/PMBS.2016.007(11-21)Online publication date: Nov-2016
https://doi.org/10.1109/PMBS.2016.007
Won JKim GKim JJiang TParker MScott S(2015)Overcoming far-end congestion in large-scale networks2015 IEEE 21st International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2015.7056051(415-427)Online publication date: Feb-2015
https://doi.org/10.1109/HPCA.2015.7056051
Hastings ERincon-Cruz DSpehlmann MMeyers SXu ABunde DLeung V(2015)Comparing Global Link Arrangements for Dragonfly NetworksProceedings of the 2015 IEEE International Conference on Cluster Computing10.1109/CLUSTER.2015.57(361-370)Online publication date: 8-Sep-2015
https://dl.acm.org/doi/10.1109/CLUSTER.2015.57
Prisacari BRodriguez GHeidelberger PChen DMinkenberg CHoefler TPlale BRipeanu MCappello FXu D(2014)Efficient task placement and routing of nearest neighbor exchanges in dragonfly networksProceedings of the 23rd international symposium on High-performance parallel and distributed computing10.1145/2600212.2600225(129-140)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1145/2600212.2600225
Prisacari BRodriguez GGarcia MVallejo EBeivide RMinkenberg CDimitrakopoulos GSonntag SFlich JVivet P(2014)Performance implications of remote-only load balancing under adversarial traffic in DragonfliesProceedings of the 8th International Workshop on Interconnection Network Architecture: On-Chip, Multi-Chip10.1145/2556857.2556860(1-4)Online publication date: 22-Jan-2014
https://dl.acm.org/doi/10.1145/2556857.2556860

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Performance implications of remote-only load balancing under adversarial traffic in Dragonflies

Randomizing task placement and route selection do not randomize traffic (enough)

Quality of service using traffic engineering over MPLS: an analysis

Comments

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Performance implications of remote-only load balancing under adversarial traffic in Dragonflies

Randomizing task placement and route selection do not randomize traffic (enough)

Quality of service using traffic engineering over MPLS: an analysis

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations