Обзор методов планирования заданий в Desktop Grid

Автор: Чернов Илья Александрович, Ивашко Евгений Евгеньевич, Никитина Наталия Николаевна

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем

Статья в выпуске: 3 (34) т.8, 2017 года.

Бесплатный доступ

В статье представлен научный обзор современного состояния исследований в области планирования заданий в вычислительных системах типа Desktop Grid. Проведен обзор научных публикаций за период с 1999 по 2017 гг. и выполнен анализ критериев и методов оптимизации, предложенных в научных работах для повышения эффективности планирования заданий в Desktop Grid.

ID: 14336125 Короткий адрес: https://sciup.org/14336125

Список литературы Обзор методов планирования заданий в Desktop Grid

S. J. Choi, H. S. Kim, E. J. Byun, C. S. Hwan. A taxonomy of desktop grid systems focusing on scheduling, Technical report KU-CSE-2006-1120-02, Department of Computer Science and Engeering, Korea University, 2006.
F. Xhafa, A. Abraham. "Computational models and heuristic methods for grid scheduling problems", Future Generation Computer Systems, V. 26. No. 4. 2010. P. 608-621.
T. Estrada, M. Taufer. "Challenges in designing scheduling policies in volunteer computing", Desktop Grid Computing, eds. C. Cérin, G. Fedak, CRC Press, 2012. P. 167-190.
N. M. Durrani, J. A. Shamsi. "Volunteer computing: requirements, challenges, and solutions", Journal of Network and Computer Applications, 39 2014. P. 369-380.
А. П. Афанасьев, И. В. Бычков, О. С. Заикин, М. О. Манзюк, М. А. Посыпкин, А. А. Семенов. Концепция многозадачной грид-системы с гибким распределением свободных вычислительных ресурсов суперкомпьютеров//Известия Российской академии наук. Теория и системы управления, 4 (2017) (в печати).
A. Afanasiev, Y. Evtushenko, M. Posypkin. "The layered software infrastructure for solving large-scale optimization problems on the grid", International Journal of Computer Research, 18:3/4 2011. P. 307.
D. Thain, T. Tannenbaum, M. Livny. "Distributed computing in practice: the Condor experience", Concurrency-Practice and Experience, V. 17. No. 2-4. 2005. P. 323-356.
М. А. Посыпкин, В. А. Сухомлин, Н. П. Храпов. Комбинированные распределенные инфраструктуры в науке и образовании//Современные информационные технологии и ИТ-образование, Т. 1, № 11. 2015. С. 31-36.
J. Rius, F. Cores, F. Solsona. "Cooperative scheduling mechanism for large-scale peer-to-peer computing systems", Journal of Network and Computer Applications, V. 36. No. 6. 2013. P. 1620-1631.
Y. Ch. Lee, A. Y. Zomaya, H. J. Siegel. "Robust task scheduling for volunteer computing systems", Journal of Supercomputing, V. 53. No. 1. 2010. P. 163-181.
D. P Anderson. "BOINC: A system for public-resource computing and storage", Grid Computing, Proceedings Fifth IEEE/ACM International Workshop on IEEE, 2004. P. 4-10.
BOINCstats (accessed Mar 2017), URL: https://boincstats.com
J. Atlas, T. Estrada, K. Decker, M. Taufer. "Balancing scientist needs and volunteer preferences in volunteer computing using constraint optimization", Computational Science, ICCS 2009, Springer, 2009. P. 143-152.
C. Anglano, M. Canonico. "Scheduling algorithms for multiple bag-of-task applications on desktop grids: A knowledge-free approach", IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2008, IEEE, 2008. P. 1-8.
D. P. Anderson. "Emulating volunteer computing scheduling policies", IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, IPDPSW 2011, IEEE, 2011. P. 1839-1846.
O. Beaumont, L. Bobelin, H. Casanova, P.-N. Clauss, B. Donassolo, L. Eyraud-Dubois, S. Genaud, S. Hunold, A. Legrand, M. Quinson. Towards scalable, accurate, and usable simulations of distributed applications and systems, Research Report RR-7761, Institut National de Recherche en Informatique et en Automatique, 2011.
T. Estrada, M. Taufer, D. P. Anderson. "Performance prediction and analysis of BOINC projects: An empirical study with EmBOINC", Journal of Grid Computing, V. 7. No. 4. 2009. P. 537-554.
T. Estrada, M. Taufer, K. Reed, D. P. Anderson. "EmBOINC: An emulator for performance analysis of BOINC projects", IEEE International Symposium on Parallel & Distributed Processing, IPDPS 2009, IEEE, 2009. P. 1-8.
M. Taufer, A. Kerstens, T. Estrada, D. A. Flores, P. J. Teller. "SimBA: A discrete event simulator for performance prediction of volunteer computing projects", 21st International Workshop on Principles of Advanced and Distributed Simulation. V. 7, 2007. P. 189-197.
H. Casanova, F. Dufossé, Y. Robert, F. Vivien. "Scheduling parallel iterative applications on volatile resources", 2011 IEEE International Parallel & Distributed Processing Symposium, IEEE, 2011. P. 1012-1023.
M. Maheswaran, Sh. Ali, H. J. Siegel, D. Hensgen, R. F. Freund. "Dynamic mapping of a class of independent tasks onto heterogeneous computing systems", Journal of Parallel and Distributed Computing, V. 59. No. 2. 1999. P. 107-131.
X. Wang, Ch. Sh. Yeo, R. Buyya, J. Su. "Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm", Future Generation Computer Systems, V. 27. No. 8. 2011. P. 1124-1134.
I. A. Chernov, N. N. Nikitina. "Virtual screening in a desktop grid: Replication and the optimal quorum", International Conference on Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 9251, ed. V. Malyshkin, Springer, 2015. P. 258-267.
D. Kondo, D. P. Anderson, J. McLeod VII. "Performance evaluation of scheduling policies for volunteer computing", Third IEEE International Conference on E-Science and Grid Computing, IEEE, 2007. P. 221-227.
M. Kh. Khan, T. Mahmood, S. I. Hyder. "Scheduling in desktop grid systems: Theoretical evaluation of policies and frameworks", International Journal of Advanced Computer Science and Applications, V. 8. No. 1. 2017. P. 119-127.
T. Estrada, O. Fuentes, M. Taufer. "A distributed evolutionary method to design scheduling policies for volunteer computing", ACM SIGMETRICS Performance Evaluation Review, V. 36. No. 3. 2008. P. 40-49.
D. Kondo, H. Casanova. Computing the optimal makespan for jobs with identical and independent tasks scheduled on volatile hosts, Technical Report CS2004-0796, Dept. of Computer Science and Engineering, University of California, 2004.
E. J. Byun, S. J. Choi, M. S. Baik, J. M. Gil, C. Y. Park, C. S. Hwang. "MJSA: Markov job scheduler based on availability in desktop grid computing environment", Future Generation Computer Systems, 23 2007. P. 616-622.
V. V. Mazalov, N. N. Nikitina, E. E. Ivashko. "Task scheduling in a desktop grid to minimize the server load", International Conference on Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 9251, ed. V. Malyshkin, Springer, 2015. P. 273-278.
Sh. Yasuda, Ya. Nogami, M. Fukushi. "A dynamic job scheduling method for reliable and high-performance volunteer computing", 2nd International Conference on Information Science and Security, ICISS 2015, IEEE, 2015. P. 1-4.
N. M. Durrani, J. A. Shamsi, S. Fatima. "Towards efficient resource grouping in heterogeneity-aware volunteer computing", Sindh University Research Journal, 2013. P. 1-11.
K. Watanabe, M. Fukushi, M. Kameyama. "Adaptive group-based job scheduling for high performance and reliable volunteer computing", Journal of Information Processing, 19 2011. P. 39-51.
Н. Н. Никитина, Е. Е. Ивашко. Цена анархии в игре заполнения для поиска лекарств//Вероятностные методы в дискретной математике, расширенные тезисы, IX Международная Петрозаводская конференция (30 мая-3 июня 2016 г., Петрозаводск, Россия), 2016. С. 67-69.
J. Sonnek, A. Chandra, J. Weissman. "Adaptive reputation-based scheduling on unreliable distributed infrastructures", IEEE Transactions on Parallel and Distributed Systems, V. 18. No. 11. 2007. P. 1551-1564.
M. Taufer, A. Kerstens, T. P. Estrada, D. A. Flores, R. Zamudio, P. J. Teller, R. Armen, C. L. Brooks III. "Moving volunteer computing towards knowledge-constructed, dynamically-adaptive modeling and scheduling", IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2007, IEEE, 2007. P. 1-8.
T. Estrada, D. A. Flores, M. Taufer, P. J. Teller, A. Kerstens, D. P. Anderson. "The effectiveness of threshold-based scheduling policies in BOINC projects", Second IEEE International Conference on E-Science and Grid Computing, IEEE, 2006. P. 88-88.
J. Sonnek, M. Nathan, A. Chandra, J. Weissman. "Reputation-based scheduling on unreliable distributed infrastructures", 26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006, IEEE, 2006. P. 30-30.
D. Kondo, A. A. Chien, H. Casanova. "Scheduling task parallel applications for rapid turnaround on enterprise desktop grids", Journal of Grid Computing, V. 5. No. 4. 2007. P. 379-405.
B. Qu, Y. Lei, Y. Zhao. "A new genetic algorithm based scheduling for volunteer computing", International Conference on Computer and Communication Technologies in Agriculture Engineering. V. 3, CCTAE 2010, IEEE, 2010. P. 228-231.
M. O. Alieksieiev, O. V. Maiboroda, A. O. Onysko, O. M. Alekseev. "Repeating tasks scheduling in desktop grid systems", 24th International Crimean Conference on Microwave & Telecommunication Technology, CriMiCo 2014, IEEE, 2014. P. 342-343.
A. Essafi, D. Trystram, Z. Zaidi. "An efficient algorithm for scheduling jobs in volunteer computing platforms", 28th International Parallel & Distributed Processing Symposium Workshops, IEEE, 2014. P. 68-76.
J.-M. Gil, S. Kim, J. Lee. "Task scheduling scheme based on resource clustering in desktop grids", International Journal of Communication Systems, V. 27. No. 6. 2014. P. 918-930.
А. С. Румянцев. Задача оптимизации времени выполнения проекта в вычислительной сети из персональных компьютеров//Программные системы: теория и приложения, Т. 5, № 1. 2014. С. 175-182, URL: http://psta.psiras.ru/read/psta2014_1_175-182.pdf
M. Ujhelyi, P. Lacko, A. Paulovic. "Task scheduling in distributed volunteer computing systems", IEEE 12th International Symposium on Intelligent Systems and Informatics, SISY 2014, IEEE, 2014. P. 111-114.
M. Smaoui, M. Garbey. "Improving volunteer computing scheduling for evolutionary algorithms", Future Generation Computer Systems, V. 29. No. 1. 2013. P. 1-14.
M. S. Bouguerra, D. Kondo, D. Trystram. "On the scheduling of checkpoints in desktop grids", 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGrid 2011, 2011. P. 305-313.
L.-C. Canon, A. Essafi, G. Mounié, D. Trystram. "A bi-objective scheduling algorithm for desktop grids with uncertain resource availabilities", Parallel Processing, Euro-Par 2011, Springer, 2011. P. 238-249.
J. Celaya, L. Marchal. "A fair decentralized scheduler for bag-of-tasks applications on desktop grids", 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, IEEE, 2010. P. 538-541.
L. Gao, G. Malewicz. "Toward maximizing the quality of results of dependent tasks computed unreliably", Theory of Computing Systems, V. 41. No. 4. 2007. P. 731-752.
I. Kurochkin. "Determination of replication parameters in the project of the voluntary distributed computing NetMaxhome", International Scientific Conference "High technologies. Business. Society" (14-17.03.2016, Borovets, Bulgaria). P. 10-12.
I. Al-Azzoni, D. G. Down. "Dynamic scheduling for heterogeneous desktop grids", Journal of Parallel and Distributed Computing, V. 70. No. 12. 2010. P. 1231-1240.
И. А. Чернов. Оптимальное дублирование заданий в вычислительной системе//Труды Карельского научного центра Российской академии наук, 2014, №4. С. 130-136.
Yu. Miyakoshi, K. Watanabe, M. Fukushi, Ya. Nogami. "A job scheduling method based on expected probability of completion of voting in volunteer computing", 2014 Second International Symposium on Computing and Networking, IEEE, 2014. P. 399-405.
L.-C. Canon, E. Jeannot, J. Weissman. "A scheduling and certification algorithm for defeating collusion in desktop grids", 2011 31st International Conference on Distributed Computing Systems, IEEE, 2011. P. 343-352.
E. M. Heien, D. P. Anderson, K. Hagihara. "Computing low latency batches with unreliable workers in volunteer computing environments", Journal of Grid Computing, V. 7. No. 4. 2009. P. 501-518.
M. Kh. Khan, S. I. Hyder, Gh. U. Ahmed, S. Begum, M. Aamir. "A group based replication mechanism to reduce the wastage of processing cycles in volunteer computing", Wireless Personal Communications, V. 76. No. 3. 2014. P. 591-601.
T. Desell, M. Magdon-Ismail, B. Szymanski, C. Varela, H. Newberg, N. Cole. "Robust asynchronous optimization for volunteer computing grids", Fifth IEEE International Conference on E-Science, IEEE, 2009. P. 263-270.
L. Klejnowski, Y. Bernard, C. Muller-Schloer, J. Hahner. "Using trust to reduce wasteful computation in open desktop grid systems", Tenth Annual International Conference on Privacy, Security and Trust, PST 2012, IEEE, 2012. P. 250-255.
V. V. Mazalov, N. N. Nikitina, E. E. Ivashko. "Hierarchical two-level game model for tasks scheduling in a desktop grid", 6th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops, ICUMT 2014, IEEE, 2014. P. 541-545.
G. D. Ghare, S. T. Leutenegger. "Improving speedup and response times by replicating parallel programs on a SNOW", Workshop on Job Scheduling Strategies for Parallel Processing, Springer, 2004. P. 264-287.

Еще

Ред. заметка