DOI: https://doi.org/10.32515/2414-3820.2020.50.229-235

Analysis of Resource Planning Algorithms in a Distributed Computing Environment

Roman Minailenko

About the Authors

Roman Minailenko, Associate Professor, PhD in Technics (Candidate of Technics Sciences), Central Ukrainian National Technical University, Kropyvnytskyi, Ukraine, e-mail: aron70@ukr.net, ORCID ID: 0000-0002-3783-0476

Abstract

The article analyzes resource scheduling algorithms in a distributed computing environment. The main task that distributed computing technologies solve is providing access to globally distributed resources using special tools. The complexity of managing global resources is due to the fact that access to the necessary data can occur on different computers. In addition, global distributed computing networks formed from autonomous resources can change their configuration dynamically. Resource management in heterogeneous distributed computing systems requires the search for new models of computation and resource management. Analysis of recent research and publications has shown that currently the implementation of resource planning in a distributed computing environment requires the search for new approaches and new algorithms. Most of the work on resource planning methods in a distributed computing environment is used to solve specific tasks related to specific applications and therefore cannot be universal. The aim of the work is to analyze resource planning algorithms in a distributed computing environment in order to find methods and algorithms for resource management in a problem-oriented distributed environment, taking into account the specifics of individual tasks and use the possibility of parallel execution of different tasks. The analysis of resource planning algorithms in a distributed computing environment shows that to date, a large number of planning algorithms focused on use in a distributed computing environment. But often such algorithms do not take into account the problem-oriented specifics of the environment, and this affects the efficiency of planning. In this regard, a promising area is related to the development of resource planning algorithms in a distributed computing environment, which would create an efficient and effective resource planning system.

Keywords

computing resources, computer, scheduling algorithms, distributed computing

Full Text:

PDF

References

1. Braun, R. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems / R. Braun, H. Siegel et al. // Parallel and Distributed Computing. 2001. Vol. 61, No. 6, P. 810–837. [in English].

2. Casanova, H. Heuristics for Scheduling Parameter Sweep Applications in Grid Environ-ments / H. Casanova, A. Legrand et al. // Heterogeneous Computing Workshop (HCW'00): Proceedings of the 9th Workshop (Cancun, Mexico, May 1, 2000). IEEE Computer Society, 2000. P. 349–363. [in English].

3. You, S.Y. Task Scheduling Algorithm in GRID Considering Heterogeneous Environment / S.Y. You, H.Y. Kim et al. // Parallel and Distributed Processing Techniques and Ap-plications (PDPTA '04): Proceedings of the International Conference (Nevada, USA, June 21–24, 2004). CSREA Press, 2004. Vol. 1. P. 240–245. [in English].

4. Cooper, K. New Grid Scheduling and Rescheduling Methods in the GrADS Project /Cooper, A. Dasgupta et al. // International Parallel and Distributed Processing Sym-posium (IPDPS'04): Proceedings of the 18th International Symposium (Santa Fe, New Mexico USA, April 26–30, 2004). IEEE Computer Society, 2004. P. 199–206. [in English].

5. Kurowski, K. Improving Grid Level Throughput Using Job Migration And Rescheduling / K. Kurowski, B. Ludwiczak et al. // Scientific Programming. 2004. Vol. 12, No. 4. P. 263–273. [in English].

6. Takefusa, A. A Study of Deadline Scheduling for Client-Server Systems on the Computa-tional Grid / A. Takefusa, S. Matsuoka et al. // High Performance Distributed Computing (HPDC-10): Proceedings of the 10th IEEE International Symposium (San Francisco, Cal-ifornia, USA, August 7–9, 2001). IEEE Computer Society, 2001. P. 406–415. [in English].

7. Chen, H. Distributed Dynamic Scheduling of Composite Tasks on Grid Computing Sys-tems / H. Chen, M. Maheswaran // International Parallel and Distributed Processing Symposium (IPDPS 2002): Proceedings of the 16th International Symposium (Fort Lauderdale, FL, USA, April 15-19, 2002). IEEE Computer Society, 2002. P. 88–97. [in English].

8. Muthuvelu, N. A Dynamic Job Grouping-Based Scheduling for Deploying Applications with Fine-Grained Tasks on Global Grids / N. Muthuvelu, J. Liu et al. // Grid Computing and e-Research (AusGrid 2005): Proceedings of the 3rd Australasian Workshop (Newcas-tle, NSW, Australia, January 30 – February 4, 2005). Australian Computer Society, 2005. P. 41–48. [in English].

9. Shan, H. Scheduling in Heterogeneous Grid Environments: The Effects of Data Migration / H. Shan, L. Oliker et al. // Advanced Computing and Communication (ADCOM 2004): Proceedings of the 12th IEEE International Conference (Ahmedabad Gujarat, India, De-cember 15–18, 2004). IEEE Computer Society, 2004. P. 1–8. [in English].

10. Dong, F. Scheduling algorithms for grid computing: State of the art and open problems. Technical Report No. 2006-504 / F .Dong, S.G. Akl, Queen’s University, Canada, 2006. P. 55. [in English].

11. Subramani, V. Distributed Job Scheduling on Computational Grids using Multiple Simul-taneous Requests / V. Subramani, R. Kettimuthu et al. // High Performance Distributed Computing (HPDC 2002): Proceedings of 11th IEEE Symposium (Edinburgh, Scotland, July 23–26, 2002). IEEE Computer Society, 2002. P. 359–366. [in English].

12. El-Rewini, H. Task Scheduling in Parallel and Distributed Systems / H. El-Rewini, T. Lewis, H. Ali — Prentice Hall, 2010. 290 p. [in English].

13. Radulescu, A. On the Complexity of List Scheduling Algorithms for Distributed Memory Systems / A. Radulescu, A.J.C. Gemund // Supercomputing (SC’99): Proceedings of 13th International Conference (Portland, Oregon, USA, November 13–19, 1999). IEEE Com-puter Society, 1999. P. 68–75. [in English].

14. Sakellariou, R. A Low-cost Rescheduling Policy for Efficient Mapping of Workflows on Grid Systems / R. Sakellariou, H. Zhao // Scientific Programming. 2017. Vol. 12, No. 4. P. 253–262. [in English].

15. Darbha, S. Optimal Scheduling Algorithm for Distributed Memory Machines / S. Darbha, D.P. Agrawal // IEEE Transactions on Parallel and Distributed Systems. 1998. Vol. 9, No. 1. P. 87–95. [in English].

16. Ranaweera, S. A Task Duplication Based Scheduling Algorithm for Heterogeneous Systems/ S. Ranaweera, D.P. Agrawal // International Parallel and Distributed Processing Sym-posium (IPDPS'00): Proceedings of 14TH International Symposium (Cancun, Mexico, May 1–5, 2018). IEEE Computer Society, 2005. P. 445–450. [in English].

17. Bajaj, R. Improving Scheduling of Tasks in A Heterogeneous Environment / R. Bajaj, D.P. Agrawal // IEEE Transactions on Parallel and Distributed Systems. 2004. Vol. 15, No. 2. P. 107–118. [in English].

18. Yang, T. DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors /Yang, A. Gerasoulis // EEE Transactions on Parallel and Distributed Systems. 1994. Vol. 5, No. 9. P. 951–967. [in English].

19. Liou, J. A Comparison of General Approaches to Multiprocessor Scheduling / J. Liou, M.A. Palis // International Parallel Processing Symposium (IPPS '97): Proceedings the 11th International Symposium (Geneva, Switzerland, April 1–5, 1997). IEEE Computer Society, 1996. P. 152–156. [in English].

Citations

  1. Braun, R. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems / R. Braun, H. Siegel et al. // Parallel and Distributed Computing. 2001. Vol. 61, No. 6, P. 810–837.
  2. Casanova, H. Heuristics for Scheduling Parameter Sweep Applications in Grid Environ-ments / H. Casanova, A. Legrand et al. // Heterogeneous Computing Workshop (HCW'00): Proceedings of the 9th Workshop (Cancun, Mexico, May 1, 2000). IEEE Computer Society, 2000. P. 349–363.
  3. You, S.Y. Task Scheduling Algorithm in GRID Considering Heterogeneous Environment / S.Y. You, H.Y. Kim et al. // Parallel and Distributed Processing Techniques and Ap-plications (PDPTA '04): Proceedings of the International Conference (Nevada, USA, June 21–24, 2004). CSREA Press, 2004. Vol. 1. P. 240–245.
  4. Cooper, K. New Grid Scheduling and Rescheduling Methods in the GrADS Project /Cooper, A. Dasgupta et al. // International Parallel and Distributed Processing Sym-posium (IPDPS'04): Proceedings of the 18th International Symposium (Santa Fe, New Mexico USA, April 26–30, 2004). IEEE Computer Society, 2004. P. 199–206.
  5. Kurowski, K. Improving Grid Level Throughput Using Job Migration And Rescheduling / K. Kurowski, B. Ludwiczak et al. // Scientific Programming. 2004. Vol. 12, No. 4. P. 263–273.
  6. Takefusa, A. A Study of Deadline Scheduling for Client-Server Systems on the Computa-tional Grid / A. Takefusa, S. Matsuoka et al. // High Performance Distributed Computing (HPDC-10): Proceedings of the 10th IEEE International Symposium (San Francisco, Cal-ifornia, USA, August 7–9, 2001). IEEE Computer Society, 2001. P. 406–415.
  7. Chen, H. Distributed Dynamic Scheduling of Composite Tasks on Grid Computing Sys-tems / H. Chen, M. Maheswaran // International Parallel and Distributed Processing Symposium (IPDPS 2002): Proceedings of the 16th International Symposium (Fort Lauderdale, FL, USA, April 15-19, 2002). IEEE Computer Society, 2002. P. 88–97.
  8. Muthuvelu, N. A Dynamic Job Grouping-Based Scheduling for Deploying Applications with Fine-Grained Tasks on Global Grids / N. Muthuvelu, J. Liu et al. // Grid Computing and e-Research (AusGrid 2005): Proceedings of the 3rd Australasian Workshop (Newcas-tle, NSW, Australia, January 30 – February 4, 2005). Australian Computer Society, 2005. P. 41–48.
  9. Shan, H. Scheduling in Heterogeneous Grid Environments: The Effects of Data Migration / H. Shan, L. Oliker et al. // Advanced Computing and Communication (ADCOM 2004): Proceedings of the 12th IEEE International Conference (Ahmedabad Gujarat, India, De-cember 15–18, 2004). IEEE Computer Society, 2004. P. 1–8.
  10. Dong, F. Scheduling algorithms for grid computing: State of the art and open problems. Technical Report No. 2006-504 / F .Dong, S.G. Akl, — Queen’s University, Canada, 2006.–P. 55.
  11. Subramani, V. Distributed Job Scheduling on Computational Grids using Multiple Simul-taneous Requests / V. Subramani, R. Kettimuthu et al. // High Performance Distributed Computing (HPDC 2002): Proceedings of 11th IEEE Symposium (Edinburgh, Scotland, July 23–26, 2002). IEEE Computer Society, 2002. P. 359–366.
  12. El-Rewini, H. Task Scheduling in Parallel and Distributed Systems / H. El-Rewini, T. Lewis, H. Ali — Prentice Hall, 2010. 290 p.
  13. Radulescu, A. On the Complexity of List Scheduling Algorithms for Distributed Memory Systems / A. Radulescu, A.J.C. Gemund // Supercomputing (SC’99): Proceedings of 13th International Conference (Portland, Oregon, USA, November 13–19, 1999). IEEE Com-puter Society, 1999. P. 68–75.
  14. Sakellariou, R. A Low-cost Rescheduling Policy for Efficient Mapping of Workflows on Grid Systems / R. Sakellariou, H. Zhao // Scientific Programming. 2017. Vol. 12, No. 4. P. 253–262.
  15. Darbha, S. Optimal Scheduling Algorithm for Distributed Memory Machines / S. Darbha, D.P. Agrawal // IEEE Transactions on Parallel and Distributed Systems. 1998. Vol. 9, No. 1. P. 87–95.
  16. Ranaweera, S. A Task Duplication Based Scheduling Algorithm for Heterogeneous Systems/ S. Ranaweera, D.P. Agrawal // International Parallel and Distributed Processing Sym-posium (IPDPS'00): Proceedings of 14TH International Symposium (Cancun, Mexico, May 1–5, 2018). IEEE Computer Society, 2005. P. 445–450.
  17. Bajaj, R. Improving Scheduling of Tasks in A Heterogeneous Environment / R. Bajaj, D.P. Agrawal // IEEE Transactions on Parallel and Distributed Systems. 2004. Vol. 15, No. 2. P. 107–118.
  18. Yang, T. DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors /Yang, A. Gerasoulis // EEE Transactions on Parallel and Distributed Systems. 1994. Vol. 5, No. 9. P. 951–967.
  19. Liou, J. A Comparison of General Approaches to Multiprocessor Scheduling / J. Liou, M.A. Palis // International Parallel Processing Symposium (IPPS '97): Proceedings the 11th International Symposium (Geneva, Switzerland, April 1–5, 1997). IEEE Computer Society, 1996. P. 152–156.
Copyright (c) 2020 Roman Minailenko