[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Dynamic resource allocation heuristics that manage tradeoff between makespan and robustness

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Heterogeneous parallel and distributed computing systems may operate in an environment where certain system performance features degrade due to unpredictable circumstances. Robustness can be defined as the degree to which a system can function correctly in the presence of parameter values different from those assumed. This work develops a model for quantifying robustness in a dynamic heterogeneous computing environment where task execution time estimates are known to contain errors. This mathematical expression of robustness is then applied to two different problem environments. Several heuristic solutions to both problem variations are presented that utilize this expression of robustness to influence mapping decisions.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ali S, Braun TD, Siegel HJ, Maciejewski AA, Beck N, Boloni L, Maheswaran M, Reuther AI, Robertson JP, Theys MD, Yao B (2005) Characterizing resource allocation heuristics for heterogeneous computing systems. In: Hurson AR (ed), Advances in computers vol 63: parallel, distributed, and pervasive computing. Elsevier, Amsterdam, Netherlands, pp 91–128

    Google Scholar 

  2. Ali S, Kim J-K, Yu Y, Gundala SB, Gertphol S, Siegel HJ, Maciejewski AA, Prasanna V (2002) Utilization-based techniques for statically mapping heterogeneous applications onto the HiPer-D heterogeneous computing system. Parallel Distrib Comput Pract, Special issue on parallel numerical algorithms on faster computers 5(4)

  3. Ali S, Maciejewski AA, Siegel HJ, Kim J-K (2004) Measuring the robustness of a resource allocation. Trans Parallel Distrib Syst 15(7):630–641

    Article  Google Scholar 

  4. Ali S, Siegel HJ, Maheswaran M, Hensgen D, Ali S (2000) Representing task and machine heterogeneities for heterogeneous computing systems. Tamkang J Sci Eng, Special 50th anniversary issue (invited), 3(3):195–207

    Google Scholar 

  5. Barada H, Sait SM, Baig N (2001) Task matching and scheduling in heterogeneous systems using simulated evolution. In: 10th IEEE heterogeneous computing workshop (HCW 2001), 15th international parallel and distributed processing symposium (IPDPS 2001), Apr 2001

  6. Banicescu I, Velusamy V (2001) Performance of scheduling scientific applications with adaptive weighted factoring. In: 10th IEEE heterogeneous computing workshop (HCW 2001), 15th International Parallel and Distributed Processing Symposium (IPDPS 2001), Apr 2001

  7. Bean J, Birge J, Mittenthal J, Noon C (1991) Matchup scheduling with multiple resources, release dates and disruptions. J Oper Res Soc Am 39(3):470–483

    MATH  Google Scholar 

  8. Braun TD, Siegel HJ, Beck N, Boloni L, Freund RF, Hensgen D, Maheswaran M, Reuther AI, Robertson JP, Theys MD, Yao B (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61(6):810–837

    Article  Google Scholar 

  9. Castain R, Saylor WW, Siegel HJ (2004) Application of lagrangian receding horizon techniques to resource management in ad-hoc grid environments. In: 13th heterogeneous computing workshop (HCW 2004), in the proceedings of the 18th international parallel and distributed processing symposium (IPDPS 2004), Apr 2004

  10. Coffman EG, Jr (ed), (1976) Computer and job-shop scheduling theory. Wiley, New York

    MATH  Google Scholar 

  11. Daniels RL, Carrilo JE (1997) β-Robust scheduling for single-machine systems with uncertain processing times. IIE Trans 29(11):977–985

    Google Scholar 

  12. Eshaghian MM (ed) (1996) Heterogeneous computing. Artech House, Norwood

    Google Scholar 

  13. Fernandez-Baca D (1989) Allocating modules to processors in a distributed system. IEEE Trans Softw Eng SE-15(11):1427–1436

    Article  Google Scholar 

  14. Foster I, Kesselman C (eds) (1999) The grid: Blueprint for a new computing infrastructure. Morgan Kaufmann, San Fransisco

    Google Scholar 

  15. Freund RF, Siegel HJ (1993) Heterogeneous processing. IEEE Comput 26(6):13–17

    Google Scholar 

  16. Ghafoor A, Yang J (1993) A distributed heterogeneous supercomputing management system. IEEE Comput 26(6):78–86

    Google Scholar 

  17. Ibarra OH, Kim CE (1977) Heuristic algorithms for scheduling independent tasks on non-identical processors. J ACM 24(2):280–289

    Article  MATH  Google Scholar 

  18. Kafil M, Ahmad I (1998) Optimal task assignment in heterogeneous distributed computing systems. IEEE Concur 6(3):42–51

    Article  Google Scholar 

  19. Khokhar A, Prasanna VK, Shaaban ME, Wang C (1993) Heterogeneous computing: challenges and opportunities. IEEE Comput 26(6):18–27

    Google Scholar 

  20. Kim J-K, Shivle S, Siegel HJ, Maciejewski AA, Braun T, Schneider M, Tideman S, Chitta R, Dilmaghani RB, Joshi R, Kaul A, Sharma A, Sripada S, Vangari P, Yellampalli SS (2003) Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines. In: 12th Heterogeneous computing workshop (HCW 2003), in the proceedings of the 17th international parallel and distributed processing symposium (IPDPS 2003), Apr 2003

  21. Leangsuksun C, Potter J, Scott S (1995) Dynamic task mapping algorithms for a distributed heterogeneous computing environment. In: 4th IEEE heterogeneous computing workshop (HCW ’95 ), 1995, pp 30–34

  22. Leon VJ, Wu SD, Storer RH (1994) Robustness measures and robust scheduling for job shops. IIE Trans 26(5):32–43

    Article  Google Scholar 

  23. Luh P, Zhao X, Wang Y, Thakur L (2000) Lagrangian relaxation neural networks for job shop scheduling. IEEE Trans Rob Autom 16(1):78–88

    Article  Google Scholar 

  24. Maheswaran M, Ali S, Siegel HJ, Hensgen D, Freund RF (1999) Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J Parallel Distrib Comput 59(2):107–121

    Article  Google Scholar 

  25. Maheswaran M, Braun TD, Siegel HJ (1999) Heterogeneous distributed computing. In: Webster JG (ed) Encyclopedia of electrical and electronics engineering, vol 8, Wiley, New York, pp 679–690

    Google Scholar 

  26. Michalewicz Z, Fogel DB (2000) How to solve it: modern heuristics. Springer, New York

    MATH  Google Scholar 

  27. Naik VK, Sivasubramanian S, Bantz D, Krishnan S (2003) Harmony: a desktop grid for delivering enterprise computations. In: Fourth international workshop on grid computing (GRID 03), Nov 2003

  28. Policella N (2005) Scheduling with uncertainty, A proactive approach using partial order schedules. PhD thesis, Dipartimento di Informatica e Sistemistica “Antonio Ruberti” Universit‘a degli Studi di Roma “La Sapienza”, 2005

  29. Shivle S, Siegel HJ, Maciejewski AA, Sugavanam P, Banka T, Castain R, Chindam K, Dussinger S, Pichumani P, Satyasekaran P, Saylor W, Sendek D, Sousa J, Sridharan J, Velazco J (2006) Static allocation of resources to communicating subtasks in a heterogeneous ad hoc grid environment. J Parallel Distribut Comput, Special Issue on Algorithms for Wireless and Ad-hoc Networks 66(4):600–611

    Article  MATH  Google Scholar 

  30. Singh H, Youssef A (1996) Mapping and scheduling heterogeneous task graphs using genetic algorithms. In: 5th IEEE heterogeneous computing workshop (HCW ’96), pp 86–97

  31. Sugavanam P, Siegel HJ, Maciejewski AA, Oltikar M, Mehta A, Pichel R, Horiuchi A, Shestak V, Al-Otaibi M, Krishnamurthy Y, Ali S, Zhang J, Aydin M, Lee P, Guru K, Raskey M, Pippin A, Robust static allocation of resources for independent tasks under makespan and dollar cost constraints, J Parallel Distrib Comput accepted, to appear

  32. Wu M-Y, Shu W, Zhang H, (2000) Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems. In: 9th IEEE Heterogeneous Computing Workshop (HCW 2000), May 2000, pp 375–385

  33. Xu D, Nahrstedt K, Wichadakul D (2001) QoS and contention-aware multi-resource reservation. Clust Comput 4(2):95–107

    Article  Google Scholar 

  34. Yang J, Ahmad I, Ghafoor A (1993) Estimation of execution times on heterogeneous supercomputer architectures. In: International conference on parallel processing, Aug 1993, pp I-219–I-226

  35. Yarmolenko V, Duato J, Panda DK, Sadayappan P, (2000) Characterization and enhancement of dynamic mapping heuristics for heterogeneous systems. In: International conference on parallel processing workshops (ICPPW 00), Aug 2000, pp 437–444

Download references

Author information

Authors and Affiliations

  1. Electrical and Computer Engineering Department, Colorado State University, Fort Collins, CO, 80523-1373, USA

    Ashish M. Mehta, Jay Smith, H. J. Siegel, Anthony A. Maciejewski, Arun Jayaseelan & Bin Ye

  2. IBM, 6300 Diagonal Highway, Boulder, CO, 80301, USA

    Jay Smith

  3. Computer Science Department, Colorado State University, Fort Collins, CO, 80523-1373, USA

    H. J. Siegel

Authors
  1. Ashish M. Mehta
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Jay Smith
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. H. J. Siegel
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Anthony A. Maciejewski
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Arun Jayaseelan
    View author publications

    You can also search for this author inPubMed Google Scholar

  6. Bin Ye
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to H. J. Siegel.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mehta, A.M., Smith, J., Siegel, H.J. et al. Dynamic resource allocation heuristics that manage tradeoff between makespan and robustness. J Supercomput 42, 33–58 (2007). https://doi.org/10.1007/s11227-006-0035-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-006-0035-y

Keywords