Модели, методы и алгоритмы планирования в грид и облачных вычислениях

  • Виктор [Viktor] Васильевич [V.] Топорков [Toporkov]
  • Дмитрий [Dmitriy] Михайлович [M.] Емельянов [Emel'yanov]
Ключевые слова: планирование, распределенные вычисления, метапланировщик, эффективность

Аннотация

Некоторые сложные задачи, например, обработка результатов физических экспериментов на LHC (ЦЕРН), задействуют значительные распределенные вычислительные ресурсы, часть из которых используется совместно с их владельцами. Этот фактор, даже в рамках виртуальных организаций, обусловливает конкуренцию за использование ресурсов как независимых пользователей, так и глобальных (пользовательских) и локальных потоков заданий собственников вычислительных узлов и существенно усложняет проблему требуемого качества обслуживания масштабируемых вычислений. Известные на сегодняшний день алгоритмы планирования, их комбинации и эвристики не позволяют создавать эффективные планы в условиях разнородных распределенных сред с динамично изменяющимся составом вычислительных ресурсов. В этих условиях весьма эффективными являются так называемые экономические модели выделения неотчуждаемых ресурсов и планирования распределенных вычислений в таких областях как грид, облачные вычисления, мультиагентные системы. Проанализировано современное состояние исследований в области методов и алгоритмов эффективного планирования конкурирующих потоков структурированных, параллельных заданий в распределенных гетерогенных вычислительных средах — грид инфраструктурах и облачных сервисах. Основное внимание уделено методам и инструментальным средствам планирования сложных заданий и их потоков с учетом предпочтений стейкхолдеров (пользователей, владельцев ресурсов, администраторов), а также особенностей приложений. Учет этих факторов позволяет повысить эффективность использования ресурсов в распределенных вычислениях. Представлено комплексное решение проблемы планирования сложных заданий и их потоков. Задание пользователя требует выделения множества одновременно доступных вычислительных ресурсов. Выбор подходящих ресурсов усложняется наличием приоритетных локальных заданий, динамикой загрузки и предварительными резервированиями. Актуальность расписания загрузки вычислительных узлов поддерживается с помощью горизонта планирования. Перепланирование «на лету» требует минимизации вычислительной сложности соответствующих алгоритмов. Конкуренция между множеством различных потоков заданий снижает уровень доступности ресурсов и уменьшает число альтернативных вариантов планирования. Один из возможных подходов решения этой проблемы — упреждающее планирование, позволяющее увеличить число возможных альтернативных планов с помощью специальных механизмов отбора слотов. Процедура упреждающего планирования дает возможность оценить эффективность различных комбинаций ресурсов. На основе полученных данных формируется допустимый план выполнения потока заданий, в наибольшей степени приближенный к оптимальному решению.

Сведения об авторах

Виктор [Viktor] Васильевич [V.] Топорков [Toporkov]

Учёная степень:

доктор технических наук

Место работы

кафедра Вычислительной техники НИУ «МЭИ»

Должность

зав. кафедрой

Дмитрий [Dmitriy] Михайлович [M.] Емельянов [Emel'yanov]

Учёная степень:

кандидат технических наук

Место работы

кафедра Вычислительной техники НИУ «МЭИ»

Должность

доцент

Литература

1. Dimitriadou S.K., Karatza H.D. Job Scheduling in a Distributed System Using Backfilling with Inaccurate Runtime Computations // Proc. Intern. Conf. Complex, Intelligent and Software Intensive Syst. Krakow, 2010. Pp. 329—336.

2. Toporkov V.V. Heuristic Strategies for Preferencebased Scheduling in Virtual Organizations of Utility Grids // J. Ambient Intelligence and Humanized Comp. 2015. V. 6(6). Pp. 733—740.

3. Buyya R., Abramson D., Giddy J. Economic Models for Resource Management and Scheduling in Grid Computing // J. Concurrency and Computation. 2002. V. 14 (5). Pp. 1507—1542.

4. Kurowski K., Nabrzyski J., Oleksiak A., Weglarz J. Multicriteria Aspects of Grid Resource Management // Grid Resource Management. International Series in Operations Research & Management Sci. 2003. V. 64. Pp. 271—293.

5. Rodero I. e. a. Enabling Interoperability among Grid Meta-schedulers // J. Grid Comp. 2013. V. 11 (2). P. 311—336.

6. Ernemann C., Hamscher V., Yahyapour R. Economic Scheduling in Grid Computing // DJSSPP. 2002. V. 18. Pp. 128—152.

7. Baranov A., Telegin P., Tikhomirov A. Comparison of Auction Methods for Job Scheduling with Absolute Priorities // PaCT. LNCS. 2017. V. 10421. Pp. 387—395.

8. Rzadca K., Trystram D., Wierzbicki A. Fair Game-theoretic Resource Management in Dedicated Grids // IEEE Intern. Symp. Cluster Comp. and the Grid. Rio De Janeiro, 2007. Pp. 343—350.

9. Vasile M., Pop F., Tutueanu R., Cristea V., Kolodziej J. Resource-aware Hybrid Scheduling Algorithm in Heterogeneous Distributed Computing // J. Future Generation Comp. Syst. 2015. V. 51. Pp. 61—71.

10. Penmatsa S., Chronopoulos A.T. Cost Minimization in Utility Computing Systems // J. Concurrency and Computation: Practice and Experience. 2014. V. 16 (1). Pp. 287—307.

11. Mutz A., Wolski R., Brevik J. Eliciting Honest Value Information in a Batch-queue Environment // Proc. VIII IEEE/ACM Intern. Conf. Grid Comp. N.-Y., 2007. Pp. 291—297.

12. Blanco H., Guirado F., Lrida, J.L., Albornoz V.M. MIP Model Scheduling for Multi-clusters // Euro-par. Heidelberg: Springer, 2012. Pp. 196—206.

13. Takefusa A., Nakada H., Kudoh T., Tanaka Y. An Advance Reservation-based Co-allocation Algorithm for Distributed Computers and Network Bandwidth on QoS-guaranteed Grids // JSSPP. Lecture Notes in Comp. Sci. Heidelberg: Springer, 2010. V. 6253. Pp. 16—34.

14. Сухорослов О.В. Комбинированное использование высокопроизводительных ресурсов и грид инфраструктур в рамках облачной платформы Everest // Суперкомпьютерные дни в России: Труды Междунар. конф. 2015. С. 706—711.

15. Bencivenni M. e. a. Accessing Grid and Cloud Services Through a Scientific Web Portal // J. Grid Comp. 2015. V. 13. Pp. 159—175.

16. Ronchieri E. e. a. Accessing Scientific Applications through the WNoDeS Cloud Virtualization Framework // Proc. Intern. Symp. Grids and Clouds (ISGC). Taipei, 2013. Pp. 3—12.

17. EGI Federated Clouds Task Force [Офиц. сайт] https://https://www.egi.eu (дата обращения 19.07.2017).

18. Carroll T., Grosu D. Divisible Load Scheduling: An Approach Using Coalitional Games // Proc. VI Interna. Symp. Parallel and Distributed Comp. 2007. Pp. 36—45.

19. Kim K., Buyya R. Fair Resource Sharing in Hierarchical Virtual Organizations for Global Grids // Proc. VIII IEEE/ACM Intern. Conf. Grid Comp. Austin, 2007. Pp. 50—57.

20. Skowron P., Rzadca K. Non-monetary Fair Scheduling Cooperative Game Theory Approach // Proc. 25 Annual ACM Symp. Parallelism in Algorithms and Architectures. N.-Y., 2013. Pp. 288—297.

21. Dalheimer M. Pfreundt F., Merz P. Agent-based Grid Scheduling with Calana // Proc. Parallel Processing and Appl. Math. VI Intern. Conf. 2006. Pp. 741—750.

22. Jackson D., Snell Q., Clement M. Core Algorithms of the Maui Scheduler // Revised Papers from VII Intern. Workshop on Job Scheduling Strategies for Parallel Proc. 2002. Pp. 87—102.

23. Thain T., Livny M. Distributed Computing in Practice: the Condor Experience // J. Concurrency and Computation: Practice and Experience. 2005. V. 17. Pp. 323—356.

24. Богданова В.Г., Бычков И.В., Корсуков А.С., Опарин Г.А., Феоктистов А.Г. Мультиагентный подход к управлению распределенными вычислениями в кластерной GRID-системе // Известия РАН. Серия «Теория и системы управления». 2014. № 5. С. 95—105.

25. Toporkov V. e. a. Metascheduling and Heuristic Co-allocation Strategies in Distributed Computing // J. Comp. and Informatics. 2015. V. 34 (1). Pp. 45—76.

26. Toporkov V., Yemelyanov D., Bobchenkov A., Potekhin P. Fair Resource Allocation and Metascheduling in Grid with VO Stakeholders Preferences // IEEE 45 Intern. Conf. on Parallel Processing Workshops. 2016. Pp. 375—384.

27. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Slot Selection Algorithms in Distributed Computing // Journal of Supercomputing. 2014. V. 69 (1). Pp. 53—60.

28. Farahabady M.H., Lee Y.C., Zomaya A.Y. Pareto-optimal Cloud Bursting // IEEE Transac. on Parallel and Distributed Systs. 2014. V. 25. Pp. 2670—2682.

29. Cafaro M., Mirto M., Aloisi, G. Preference-Based Matchmaking of Grid Resources with CP-Nets // J. Grid Comp. 2013. V. 11 (2). Pp. 211—237.

30. Garg S.K., Konugurthi P., Buyya R. A Linear Programming-driven Genetic Algorithm for Metascheduling on Utility Grids // J. Par., Emergent and Distr. Syst. 2011. V. 26. Pp. 493—517.

31. Aida K., Casanova H. Scheduling Mixed-parallel Applications with Advance Reservations // 17 th IEEE Int. Symposium on HPDC. N.-Y., 2008. Pp. 65—74.

32. Ando S., Aida K. Evaluation of Scheduling Algorithms for Advance Reservations // Information Proc. Soc. Japan SIG Notes. 2007. Pp. 37—42.

33. Elmroth E., Tordsson J. A Standards-based Grid Resource Brokering Service Supporting Advance Reservations, Coallocation and Cross-Grid Interoperability // J. of Concurrency and Computation. 2009. V. 21(18). Pp. 2298—2335.

34. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Slot Selection Algorithms in Distributed Computing with Non-dedicated and Heterogeneous Resources // PaCT. LNCS. Heidelberg: Springer, 2013. V. 7979. Pp. 120—134.

35. Azzedin F., Maheswaran M., Arnason N. A Synchronous Co-allocation Mechanism for Grid Computing Systems // Cluster Comp. 2004. V. 7. Pp. 39—49.

36. Castillo C., Rouskas G.N., Harfoush K. Resource Co-allocation for Large-scale Distributed Environments // 18 th ACM Intern. Symp. High Performance Distributed Comp. N.-Y. 2009. Pp. 137—150.

37. Olteanu A., Pop F., Dobre C., Cristea V. A Dynamic Rescheduling Algorithm for Resource Management in Large Scale Dependable Distributed Systems // Computers and Mathematics with Appl. 2012. V. 63 (9). Pp. 1409—1423.

38. Топорков В.В., Емельянов Д.М. Экономическая модель планирования и справедливого разделения ресурсов в распределенных вычислениях // Программирование. 2014. № 1. С. 54—65.

39. Топорков В.В., Бобченков А.В., Емельянов Д.М., Целищев А.С. Методы и эвристики планирования в распределенных вычислениях с неотчуждаемыми ресурсами // Вестник ЮУрГУ. Cерия «Вычислительная математика и информатика». 2014. Т. 3. № 2. С. 43—62.

40. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Heuristic Co-allocation Strategies in Distributed Computing with Non-dedicated Resources // Studies in Computational Intelligence. Heidelberg: Springer, 2014. V. 511. Pp. 109—118.

41. Toporkov V. e. a. Preference-based Fair Resource Sharing and Scheduling Optimization in Grid VOs // Procedia Computer Sci. 2014. V. 29. Pp. 831—843.

42. Toporkov V. e. a. Heuristic Cycle-based Scheduling with Backfilling for Large-scale Distributed Environments // Advances in Intelligent Systems and Computing (AISC). Heidelberg: Springer, 2014. V. 286. Pp. 455—465.

43. Toporkov V., Tselishchev A., Yemelyanov D., Potekhin P. Metascheduling Strategies in Distributed Computing with Non-dedicated Resources // Dependability Problems of Complex Information Systems, Advances in Intelligent Syst. and Comp. (AISC). Springer International Publ., 2014. V. 307. Pp. 129—148.

44. Toporkov V., Yemelyanov D, Tselishchev A. Effective Slot Selection and Co-allocation Algorithms for Economic Scheduling in Distributed Computing // Procedia Comp. Sci. 2013. V. 18. Pp. 2424—2427.

45. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Slot Selection Algorithms for Economic Scheduling in Distributed Computing with High QoS Rates // New Results in Computer Systems and Dependability. AISC. Heidelberg: Springer, 2013. V. 224. Pp. 459—468.

46. Топорков В.В. Пакетная обработка заданий в распределенных вычислительных средах с неотчуждаемыми ресурсами // Автоматика и телемеханика. 2012. № 10. С. 52—70.

47. Toporkov V., Tselishchev A., Yemelyanov D., Bobchenkov A. Composite Scheduling Strategies in Distributed Computing with Non-dedicated Resources // Procedia Comp. Sci. Elsevier, 2012. V. 9. Pp. 176—185.

48. Toporkov V., Tselishchev A., Yemelyanov D., Bobchenkov A. Dependable Strategies for Job-flows Dispatching and Scheduling in Virtual Organizations of Distributed Computing Environments // Complex Systems and Dependability. Berlin, Heidelberg: Springer-Verlag, 2012;170:240—255.

49. Toporkov V., Toporkova A., Bobchenkov A., Yemelyanov D. Resource Selection Algorithms for Economic Scheduling in Distributed Systems // Proc. Comp. Sci. Elsevier, 2011. V. 4. Pp. 2267—2276.

50. Graham R.L., Lawler E.L., Lenstra J.K., Kan A.R. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey // Annals Discrete Mathematics. 1979;5:287—326.

51. Yu J., Buyya R., Ramamohanarao K. Workflow Scheduling Algorithms for Grid Computing // Metaheuristics for Scheduling in Distributed Computing Environments. Studies in Computational Intelligence. Berlin: Springer, 2008. V. 146. Pp. 173—214.

52. Casanova H., Giersch A., Legrand A., Quinson M., Suter F. Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms // J. Parallel and Distributed Comp. 2014. V. 74 (10). Pp. 2899—2917.

53. Chen W., Deelman E. Workflowsim: A toolkit for Simulating Scientific Workflows in Distributed Environments // IEEE E-science (e-science) VIII Intern. Conf. 2012. Pp. 1—8.

54. Topcuoglu H., Hariri S., Wu M.Y. Performanceeffective and Low-complexity Task Scheduling For Heterogeneous Computing // IEEE Trans. Parallel and Distributed Syst. 2002. V. 13 (3). Pp. 260—274.

55. Hagras T., Janecek J. A Simple Scheduling Heuristic for Heterogeneous Computing Environment // Proc. II Intern. Symp. Parallel and Distributed Comp. 2003. Pp. 104—110.

56. Bittencourt L.F., Sakellariou R., Madeira E.R.M. Dag Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm // Proc. XVIII Euromicro Conf. Parallel, Distributed and Networkbased. 2010. Pp. 27—34.

57. Arabnejad H., Barbosa J.G. List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table // IEEE Trans. Parallel and Distributed Syst. 2014. V. 25 (3). Pp. 682—694.

58. Armstrong R., Hensgen D. Kidd T. The Rela-tive Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-Time Predictions // IEEE Heterogeneous Computing Workshop. 1998. Pp. 79—87.

59. Maheswaran M. e. a. Dynamic Matching and Scheduling of a Class of Independent Tasks Onto Heterogeneous Computing Systems // IEEE Heterogeneous Computing Workshop. IEEE. 1999. Pp. 30—44.

60. Freund R.F. e. a. Scheduling Resources In Multiuser, Heterogeneous, Computing Environments with Smart-net // IEEE Heterogeneous Computing Workshop. 1998. Pp. 184—199.

61. Nazarenko A., Sukhoroslov O. An Experimental Study of Workow Scheduling Algorithms for Heterogeneous Systems // PaCT. LNCS. Springer Intern. Publ., 2017. V. 10421. Pp. 327—341.

62. Радченко Г.И., Лыжин И.А., Неповинных Е.А. Имплементация и сравнительное тестирование алгоритма проблемно-ориентированного планирования потоковых приложений в облачных средах PO-HEFT // Суперкомпьютерные дни в России: Труды Междунар. конф. 2016. С. 165—179.

63. Toporkov V., Yemelyanov D., Bobchenkov A. Job-flow Anticipation Scheduling in Grid // Proc. Comp. Sci. 2017. V. 108. Pp. 1394—1403.

64. Toporkov V., Yemelyanov D., Toporkova A. Anticipation Preference-based Heuristic Scheduling in Grid Virtual Organizations // Proc. Intern. Conf. Parallel Processing Workshops. 2017. Pp. 271—280.

65. Toporkov V., Toporkova A., Yemelyanov D. Heuristic of Anticipation for Fair Scheduling and Resource Allocation in Grid VOs // Studies in Computational Intelligence. Springer Verlag, 2018. V. 737. Pp. 27—37.
---
Для цитирования: Топорков В.В., Емельянов Д.М. Модели, методы и алгоритмы планирования в грид и облачных вычислениях // Вестник МЭИ. 2018. № 6. С. 75—86. DOI: 10.24160/1993-6982-2018-6-75-86.
#
1. Dimitriadou S.K., Karatza H.D. Job Scheduling in a Distributed System Using Backfilling with Inaccurate Runtime Computations. Proc. Intern. Conf. Complex, Intelligent and Software Intensive Syst. Krakow, 2010:329—336.

2. Toporkov V.V. Heuristic Strategies for Preferencebased Scheduling in Virtual Organizations of Utility Grids. J. Ambient Intelligence and Humanized Comp. 2015;6(6):733—740.

3. Buyya R., Abramson D., Giddy J. Economic Models for Resource Management and Scheduling in Grid Computing. J. Concurrency and Computation. 2002; 14 (5):1507—1542.

4. Kurowski K., Nabrzyski J., Oleksiak A., Weglarz J. Multicriteria Aspects of Grid Resource Management. Grid Resource Management. International Series in Operations Research & Management Sci. 2003;64:271— 293.

5. Rodero I. e. a. Enabling Interoperability among Grid Meta-schedulers. J. Grid Comp. 2013;11 (2):311—336.

6. Ernemann C., Hamscher V., Yahyapour R. Economic Scheduling in Grid Computing. DJSSPP. 2002;18:128—152.

7. Baranov A., Telegin P., Tikhomirov A. Comparison of Auction Methods for Job Scheduling with Absolute Priorities. PaCT. LNCS. 2017;10421:387—395.

8. Rzadca K., Trystram D., Wierzbicki A. Fair Gametheoretic Resource Management in Dedicated Grids. IEEE Intern. Symp. Cluster Comp. and the Grid. Rio De Janeiro, 2007:343—350.

9. Vasile M., Pop F., Tutueanu R., Cristea V., Kolodziej J. Resource-aware Hybrid Scheduling Algorithm in Heterogeneous Distributed Computing. J. Future Generation Comp. Syst. 2015;51:61—71.

10. Penmatsa S., Chronopoulos A.T. Cost Minimization in Utility Computing Systems. J. Concurrency and Computation: Practice and Experience. 2014;16 (1):287—307.

11. Mutz A., Wolski R., Brevik J. Eliciting Honest Value Information in a Batch-queue Environment. Proc. VIII IEEE/ACM Intern. Conf. Grid Comp. N.-Y., 2007:291—297.

12. Blanco H., Guirado F., Lrida, J.L., Albornoz V.M. MIP Model Scheduling for Multi-clusters. Euro-par. Heidelberg: Springer, 2012:196—206.

13. Takefusa A., Nakada H., Kudoh T., Tanaka Y. An Advance Reservation-based Co-allocation Algorithm for Distributed Computers and Network Bandwidth on QoS-guaranteed Grids. JSSPP. Lecture Notes in Comp. Sci. Heidelberg: Springer, 2010;6253:16—34.

14.Suhoroslov O.V. Kombinirovannoe Ispol'zovanie Vysokoproizvoditel'nyh Resursov i Grid Infrastruktur v Ramkah Oblachnoy Platformy Everest. Superkomp'yuternye Dni v Rossii: Trudy Mezhdunar. Konf. 2015:706—711. (in Russian).

15. Bencivenni M. e. a. Accessing Grid and Cloud Services Through a Scientific Web Portal. J. Grid Comp. 2015;13:159—175.

16. Ronchieri E. e. a. Accessing Scientific Applications through the WNoDeS Cloud Virtualization Framework. Proc. Intern. Symp. Grids and Clouds (ISGC). Taipei, 2013:3—12.

17. EGI Federated Clouds Task Force [Ofits. Sayt] https://https://www.egi.eu (Data Obrashcheniya 19.07.2017).

18. Carroll T., Grosu D. Divisible Load Scheduling: An Approach Using Coalitional Games. Proc. VI Interna. Symp. Parallel and Distributed Comp. 2007:36—45.

19. Kim K., Buyya R. Fair Resource Sharing in Hierarchical Virtual Organizations for Global Grids. Proc. VIII IEEE/ACM Intern. Conf. Grid Comp. Austin, 2007:50—57.

20. Skowron P., Rzadca K. Non-monetary Fair Scheduling Cooperative Game Theory Approach. Proc. 25 Annual ACM Symp. Parallelism in Algorithms and Architectures. N.-Y., 2013:288—297.

21. Dalheimer M. Pfreundt F., Merz P. Agent-based Grid Scheduling with Calana. Proc. Parallel Processing and Appl. Math. VI Intern. Conf. 2006:741—750.

22. Jackson D., Snell Q., Clement M. Core Algorithms of the Maui Scheduler. Revised Papers from VII Intern. Workshop on Job Scheduling Strategies for Parallel Proc. 2002:87—102.

23. Thain T., Livny M. Distributed Computing in Practice: the Condor Experience. J. Concurrency and Computation: Practice and Experience. 2005;17:323—356.

24. Bogdanova V.G., Bychkov I.V., Korsukov A.S., Oparin G.A.,Feoktistov A.G. Mul'tiagentnyy podhod k upravleniyu raspredelennymi vychisleniyami v klasternoy GRID-sisteme. Izvestiya RAN. Seriya «Teoriya i sistemy upravleniya». 2014;5:95—105. (in Russian).

25. Toporkov V. e. a. Metascheduling and Heuristic Co-allocation Strategies in Distributed Computing. J. Comp. and Informatics. 2015;34 (1):45—76.

26. Toporkov V., Yemelyanov D., Bobchenkov A., Potekhin P. Fair Resource Allocation and Metascheduling in Grid with VO Stakeholders Preferences. IEEE 45 Intern. Conf. on Parallel Processing Workshops. 2016:375—384.

27. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Slot Selection Algorithms in Distributed Computing. Journal of Supercomputing. 2014;69 (1):53—60.

28. Farahabady M.H., Lee Y.C., Zomaya A.Y. Pareto-optimal Cloud Bursting. IEEE Transac. on Parallel and Distributed Systs. 2014;25:2670—2682.

29. Cafaro M., Mirto M., Aloisi, G. Preference-Based Matchmaking of Grid Resources with CP-Nets. J. Grid Comp. 2013;11 (2):211—237.

30. Garg S.K., Konugurthi P., Buyya R. A Linear Programming-driven Genetic Algorithm for Metascheduling on Utility Grids. J. Par., Emergent and Distr. Syst. 2011;26:493—517.

31. Aida K., Casanova H. Scheduling Mixed-parallel Applications with Advance Reservations. 17 th IEEE Int. Symposium on HPDC. N.-Y., 2008:65—74.

32. Ando S., Aida K. Evaluation of Scheduling Algorithms for Advance Reservations. Information Proc. Soc. Japan SIG Notes. 2007:37—42.

33. Elmroth E., Tordsson J. A Standards-based Grid Resource Brokering Service Supporting Advance Reservations, Coallocation and Cross-Grid Interoperability. J. of Concurrency and Computation. 2009;21(18): 2298—2335.

34. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Slot Selection Algorithms in Distributed Computing with Non-dedicated and Heterogeneous Resources. PaCT. LNCS. Heidelberg: Springer, 2013;7979: 120—134.

35. Azzedin F., Maheswaran M., Arnason N. A Synchronous Co-allocation Mechanism for Grid Computing Systems. Cluster Comp. 2004;7:39—49.

36. Castillo C., Rouskas G.N., Harfoush K. Resource Co-allocation for Large-scale Distributed Environments. 18 th ACM Intern. Symp. High Performance Distributed Comp. N.-Y. 2009:137—150.

37. Olteanu A., Pop F., Dobre C., Criste. V. A Dynamic Rescheduling Algorithm for Resource Management in Large Scale Dependable Distributed Systems. Computers and Mathematics with Appl. 2012;63 (9):1409—1423.

38. Toporkov V.V., Emel'yanov D.M. Ekonomicheskaya Model' Planirovaniya i Spravedlivogo Razdeleniya Resursov V Raspredelennyh Vychisleniyah. Programmirovanie. 2014;1:54—65. (in Russian).

39. Toporkov V.V., Bobchenkov A.V., Emel'yanov D.M., TSelishchev A.S. Metody i Evristiki Planirovaniya V Raspredelennyh Vychisleniyah S Neotchuzhdaemymi Resursami. Vestnik YUUrGU. Seriya «Vychislitel'naya Matematika i Informatika». 2014;3;2:43—62. (in Russian).

40. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Heuristic Co-allocation Strategies in Distributed Computing with Non-dedicated Resources. Studies in Computational Intelligence. Heidelberg: Springer, 2014;511:109—118.

41. Toporkov V. e. a. Preference-based Fair Resource Sharing and Scheduling Optimization in Grid VOs. Procedia Computer Sci. 2014;29:831—843.

42. Toporkov V. e. a. Heuristic Cycle-based Scheduling with Backfilling for Large-scale Distributed Environments. Advances in Intelligent Systems and Computing (AISC). Heidelberg: Springer, 2014;286:455—465.

43. Toporkov V., Tselishchev A., Yemelyanov D., Potekhin P. Metascheduling Strategies in Distributed Computing with Non-dedicated Resources. Dependability Problems of Complex Information Systems, Advances in Intelligent Syst. and Comp. (AISC). Springer International Publ., 2014;307:129—148.

44. Toporkov V., Yemelyanov D, Tselishchev A. Effective Slot Selection and Co-allocation Algorithms for Economic Scheduling in Distributed Computing. Procedia Comp. Sci. 2013;18:2424—2427.

45. Toporkov V., Toporkova A., Tselishchev A., Yemelyanov D. Slot Selection Algorithms for Economic Scheduling in Distributed Computing with High QoS Rates. New Results in Computer Systems and Dependability. AISC. Heidelberg: Springer, 2013;224:459—468.

46. Toporkov V.V. Paketnaya Obrabotka Zada-niy V Raspredelennyh Vychislitel'nyh Sredah S Neotchuzhdaemymi Resursami. Avtomatika i Telemekhanika. 2012;10: 52—70. (in Russian).

47. Toporkov V., Tselishchev A., Yemelyanov D., Bobchenkov A. Composite Scheduling Strategies in Distributed Computing with Non-dedicated Resources. Procedia Comp. Sci. Elsevier, 2012;9:176—185.

48. Toporkov V., Tselishchev A., Yemelyanov D., Bobchenkov A. Dependable Strategies for Job-flows Dispatching and Scheduling in Virtual Organizations of Distributed Computing Environments . Complex Systems and Dependability. Berlin, Heidelberg: Springer-Verlag, 2012;170:240—255.

49. Toporkov V., Toporkova A., Bobchenkov A., Yemelyanov D. Resource Selection Algorithms for Economic Scheduling in Distributed Systems. Proc.Comp. Sci. Elsevier, 2011;4:2267—2276.

50. Graham R.L., Lawler E.L., Lenstra J.K., Kan A.R. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals Discrete Mathematics. 1979;5:287—326.

51. Yu J., Buyya R., Ramamohanarao K. Workflow Scheduling Algorithms for Grid Computing. Metaheuristics for Scheduling in Distributed Computing Environments. Studies in Computational Intelligence. Berlin: Springer, 2008;146:173—214.

52. Casanova H., Giersch A., Legrand A., Quinson M., Suter F. Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms. J. Parallel and Distributed Comp. 2014;74 (10):2899—2917.

53. Chen W., Deelman E. Workflowsim: A toolkit for Simulating Scientific Workflows in Distributed Environments. IEEE E-science (e-science) VIII Intern. Conf. 2012:1—8.

54. Topcuoglu H., Hariri S., Wu M.Y. Performanceeffective and Low-complexity Task Scheduling For Heterogeneous Computing. IEEE Trans. Parallel and Distributed Syst. 2002;13 (3):260—274.

55. Hagras T., Janecek J. A Simple Scheduling Heuristic for Heterogeneous Computing Environment. Proc. II Intern. Symp. Parallel and Distributed Comp. 2003:104—110.

56. Bittencourt L.F., Sakellariou R., Madeira E.R.M. Dag Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm. Proc. XVIII Euromicro Conf. Parallel, Distributed and Networkbased. 2010:27—34.

57. Arabnejad H., Barbosa J.G. List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table. IEEE Trans. Parallel and Distributed Syst. 2014;25 (3):682—694.

58. Armstrong R., Hensgen D. Kidd T. The Rela-tive Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-Time Predictions. IEEE Heterogeneous Computing Workshop. 1998:79—87.

59. Maheswaran M. e. a. Dynamic Matching and Scheduling of a Class of Independent Tasks Onto Heterogeneous Computing Systems. IEEE Heterogeneous Computing Workshop. IEEE. 1999:30—44.

60. Freund R.F. e. a. Scheduling Resources In Multiuser, Heterogeneous, Computing Environments with Smart-net. IEEE Heterogeneous Computing Workshop. 1998:184—199.

61. Nazarenko A., Sukhoroslov O. An Experimental Study of Workow Scheduling Algorithms for Heterogeneous Systems. PaCT. LNCS. Springer Intern. Publ., 2017; 10421:327—341.

62.Radchenko G.I., Lyzhin I.A., Nepovinnyh E.A. Implementatsiya i Sravnitel'noe Testirovanie Algoritma Problemno-orientirovannogo Planirovaniya Potokovyh Prilozheniy v Oblachnyh Sredah PO-HEFT. Superkomp'yuternye Dni v Rossii: Trudy Mezhdunar. Konf. 2016: 165—179. (in Russian).

63. Toporkov V., Yemelyanov D., Bobchenkov A. Job-flow Anticipation Scheduling in Grid. Proc. Comp. Sci. 2017;108:1394—1403.

64. Toporkov V., Yemelyanov D., Toporkova A. Anticipation Preference-based Heuristic Scheduling in Grid Virtual Organizations. Proc. Intern. Conf. Parallel Processing Workshops. 2017:271—280.

65. Toporkov V., Toporkova A., Yemelyanov D. Heuristic of Anticipation for Fair Scheduling and Resource Allocation in Grid VOs. Studies in Computational Intelligence. Springer Verlag, 2018;737:27—37.
---
For citation: Toporkov V.V., Yemelyanov D.M. Scheduling Models, Methods and Algorithms in Grid and Cloud Computing. MPEI Vestnik. 2018;6:75—86. (in Russian). DOI: 10.24160/1993-6982-2018-6-75-86.
Опубликован
2019-02-18
Раздел
Информатика, вычислительная техника и управление (05.13.00)