Skip to main content
SpringerLink
Log in

Understanding the Effect of Task Granularity on Execution Time in Asynchronous Many-Task Runtime Systems

  • Conference paper
  • First Online:
Euro-Par 2021: Parallel Processing Workshops (Euro-Par 2021)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13098))

Included in the following conference series:

  • 679 Accesses

Abstract

Task granularity is a key factor in determining the performance of asynchronous many-task (AMT) runtime systems. The overhead of scheduling an excessive number of tasks with smaller granularities causes performance degradation, while creating a few larger tasks leads to starvation and therefore under-utilization of resources. In this paper, we developed an analytical model of the execution time of an application with balanced parallel for-loops in terms of grain size, and number of cores. The parameters of this model mostly depend on the runtime and the architecture. We introduce an approach to suggest a range of possible grain sizes to achieve the best performance based on the proposed model. To the best of our knowledge, our analytical model is the first to explain the relationship between the execution time in terms of grain size, runtime, and physical characteristics of the machine in an asynchronous runtime system.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    https://gist.github.com/shahrzad/b81e1eb252880aca48528d2de0bd1d10.

References

  1. Akhmetova, D., Kestor, G., Gioiosa, R., Markidis, S., Laure, E.: On the application task granularity and the interplay with the scheduling overhead in many-core shared memory systems. In: 2015 IEEE International Conference on Cluster Computing, pp. 428–437. IEEE (2015)

    Google Scholar 

  2. Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the Spring Joint Computer Conference, 18–20 April 1967, pp. 483–485. ACM (1967)

    Google Scholar 

  3. Bennett, J., et al.: Asynchronous many-task runtime system analysis and assessment for next generation platforms. US Department of Energy, Sandia National Laboratories Report, Rep. no. SAND2015-8312 (2015)

    Google Scholar 

  4. Gao, G.R., Sterling, T., Stevens, R., Hereld, M., Zhu, W.: Parallex: a study of a new parallel computation model. In: 2007 IEEE International Parallel and Distributed Processing Symposium, pp. 1–6. IEEE (2007)

    Google Scholar 

  5. Grama, A., Kumar, V., Gupta, A., Karypis, G.: Introduction to Parallel Computing. Pearson Education, Boston (2003)

    MATH  Google Scholar 

  6. Grubel, P., Kaiser, H., Cook, J., Serio, A.: The performance implication of task size for applications on the HPX runtime system. In: 2015 IEEE International Conference on Cluster Computing, pp. 682–689. IEEE (2015)

    Google Scholar 

  7. Grubel, P., Kaiser, H., Huck, K., Cook, J.: Using intrinsic performance counters to assess efficiency in task-based parallel applications. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 1692–1701. IEEE (2016)

    Google Scholar 

  8. Gunther, N.J.: The practical performance analyst. iuniverse. com inc. Lincoln, Nebraska (2000)

    Google Scholar 

  9. Gunther, N.J.: What is Guerrilla Capacity Planning? Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-31010-5_1

    Book  Google Scholar 

  10. Kaiser, H., Brodowicz, M., Sterling, T.: Parallex an advanced parallel execution model for scaling-impaired applications. In: 2009 International Conference on Parallel Processing Workshops, pp. 394–401. IEEE (2009)

    Google Scholar 

  11. Kaiser, H., Heller, T., Adelstein-Lelbach, B., Serio, A., Fey, D.: HPX: a task based programming model in a global address space. In: Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models, p. 6. ACM (2014)

    Google Scholar 

  12. Kulkarni, A., Lumsdaine, A.: A comparative study of asynchronous many-tasking runtimes: Cilk, charm++, parallex and am++. arXiv preprint arXiv:1904.00518 (2019)

  13. Wagle, B., Monil, M.A.H., Huck, K., Malony, A.D., Serio, A., Kaiser, H.: Runtime adaptive task inlining on asynchronous multitasking runtime systems. In: Proceedings of the 48th International Conference on Parallel Processing, pp. 1–10 (2019)

    Google Scholar 

Download references

Acknowledgment

The authors are grateful for the support of this work by the LSU Center for Computation & Technology and by the DTIC project: Phylanx Engine Enhancement and Visualizations Development (Contract Number: FA8075-14-D-0002/0007).

Author information

Authors and Affiliations

  1. Louisiana State University, Baton Rouge, LA, USA

    Shahrzad Shirzad, R. Tohid, Alireza Kheirkhahan & Hartmut Kaiser

  2. The STE||AR Group, Baton Rouge, USA

    Bibek Wagle

Authors
  1. Shahrzad Shirzad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Tohid
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alireza Kheirkhahan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bibek Wagle
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Hartmut Kaiser
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shahrzad Shirzad .

Editor information

Editors and Affiliations

  1. University of Lisbon, Lisbon, Portugal

    Ricardo Chaves

  2. Department of Computer Engineering, CiTIUS, University of Santiago de Compostela, Santiago de Compostela, La Coruña, Spain

    Dora B. Heras

  3. University of Lisbon, Lisbon, Portugal

    Aleksandar Ilic

  4. Koç University, Istanbul, Turkey

    Didem Unat

  5. Barcelona Supercomputing Center, Barcelona, Spain

    Rosa M. Badia

  6. University of Stirling, Stirling, UK

    Andrea Bracciali

  7. Louisiana State University, Baton Rouge, USA

    Patrick Diehl

  8. Mathematics and Computer Science, Argonne National Laboratory, Lemont, IL, USA

    Anshu Dubey

  9. Ajou University, Suwon, Korea (Republic of)

    Oh Sangyoon

  10. Tennessee Technological University, Cookeville, TN, USA

    Stephen L. Scott

  11. University of Pisa, Pisa, Italy

    Laura Ricci

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Shirzad, S., Tohid, R., Kheirkhahan, A., Wagle, B., Kaiser, H. (2022). Understanding the Effect of Task Granularity on Execution Time in Asynchronous Many-Task Runtime Systems. In: Chaves, R., et al. Euro-Par 2021: Parallel Processing Workshops. Euro-Par 2021. Lecture Notes in Computer Science, vol 13098. Springer, Cham. https://doi.org/10.1007/978-3-031-06156-1_36

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-06156-1_36

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-06155-4

  • Online ISBN: 978-3-031-06156-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation