Cited By
View all- Estebanez ALlanos DGonzalez-Escribano A(2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
Brief announcement: locality-aware load balancing for speculatively-parallelized irregular applications
Pages 183 - 185
Abstract
Load balancing is an important consideration when running data-parallel programs. While traditional techniques trade off the cost of load imbalance with the overhead of mitigating that imbalance, when speculatively parallelizing amorphous data-parallel applications, we must also consider the effects of load balancing decisions on locality and speculation accuracy. We present two data centric load balancing strategies which account for the intricacies of amorphous data-parallel execution. We implement these strategies as schedulers in the Galois system and demonstrate that they outperform traditional load balancing schedulers, as well as a data-centric, non-load-balancing scheduler.
References
[1]
Intel Threading Building Blocks Reference Manual, Rev 1.9. 2008.
[2]
Robert D. Blumofe and Charles E. Leiserson. Scheduling multithreaded computations by work stealing. J. ACM, 46(5):720--748, 1999.
[3]
Yi Guo, Jisheng Zhao, Vincent Cave, and Vivek Sarkar. SLAW: A scalable locality-aware adaptive work-stealing scheduler for multi-core systems. In PPoPP'10: Proceedings of the 15th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 341--342, 2010.
[4]
S. Krishnamoorthy, U. Catalyurek, J. Nieplocha, and P Sadayappan. An approach to locality-conscious load balancing and transparent memory hierarchy management with a global-address-space parallel programming model. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.
[5]
Milind Kulkarni, Martin Burtscher, Rajasekhar Inkulu, Keshav Pingali, and Calin Cascaval. How much parallelism is there in irregular applications? In PPoPP'09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 3--14, New York, NY, USA, 2009. ACM.
[6]
Milind Kulkarni, Martin Burtscher, Keshav Pingali, and Calin Cascaval. Lonestar: A suite of parallel irregular programs. In 2009 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 65--76, April 2009.
[7]
Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala, and L. Paul Chew. Optimistic parallelism benefits from data partitioning. In ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, pages 233--243, New York, NY, USA, 2008. ACM.
[8]
Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and L. Paul Chew. Optimistic parallelism requires abstractions. In PLDI'07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 211--222, New York, NY, USA, 2007. ACM.
[9]
E. P. Markatos and T. J. LeBlanc. Load balancing vs. locality management in shared-memory multiprocessors. Technical report, Rochester, NY, USA, 1991.
[10]
Constantine D. Polychronopoulos and David J. Kuck. Guided self-scheduling: A practical scheduling scheme for parallel supercomputers. IEEE Transactions on Computers, C-36(12), 1987.
Index Terms
- Brief announcement: locality-aware load balancing for speculatively-parallelized irregular applications
Recommendations
Brief announcement: threshold load balancing in networks
PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computingWe study probabilistic protocols for concurrent threshold-based load balancing in networks. There are n resources or machines represented by nodes in an undirected graph and m >> n users that try to find an acceptable resource by moving along the edges ...
Brief Announcement: Approximation Algorithms for Preemptive Resource Allocation
SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and ArchitecturesCloud services require the allocation of scarce resources to multiple user requests (jobs) in a setting that facilitates preemption and migration while respecting resource and timing constraints. This gives rise to the following variants of the ...
Brief announcement: a lower bound for depth-restricted work stealing
SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architecturesWork stealing is a common technique used in the runtime schedulers of parallel languages such as Cilk and parallel libraries such as Intel Threading Building Blocks (TBB). Depth-restricted work stealing is a restriction of Cilk-like work stealing in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2010
378 pages
Copyright © 2010 Copyright is held by the author/owner(s).
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 June 2010
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
SPAA 10: 22nd ACM Symposium on Parallelism in Algorithms and Architectures
June 13 - 15, 2010
Santorini, Thira, Greece
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 207Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
Cited By
View all- Estebanez ALlanos DGonzalez-Escribano A(2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in