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

Аналіз алгоритмів планування ресурсами в розподіленому обчислювальному середовищі

Р.М. Минайленко

Об авторах

Р.М. Минайленко , доцент, кандидат технічних наук, Центральноукраїнський національний технічний університет, Кропивницький, Україна, e-mail: aron70@ukr.net, ORCID ID: 0000-0002-3783-0476

Анотація

В статті проведено аналіз алгоритмів планування ресурсами в розподіленому обчислювальному середовищі. Головним завданням, яке вирішують технології розподілених обчислень є забезпечення доступу до глобально розподілених ресурсів з допомогою спеціальних інструментів. Складність керування глобальними ресурсами обумовлена тим, що доступ до необхідних даних може відбуватись на різних комп’ютерах. Крім того, глобальні розподілені обчислювальні мережі, які формуються із автономних ресурсів, можуть змінювати свою конфігурацію динамічно. Керування ресурсами в неоднорідних розподілених обчислювальних системах потребує пошуку нових моделей обчислення і керування ресурсами.

Ключові слова

обчислювальні ресурси, комп’ютер, алгоритми планування, розподілені обчислення

Повний текст:

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].

Пристатейна бібліографія

  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 Р.М. Минайленко