Динамическое построение прогноза времени завершения вычислительного эксперимента в Desktop Grid

Desktop Grid является мощным инструментом высокопроизводительных вычислений. Desktop Grid — это форма распределенной высокопроизводительной вычислительной системы, которая использует время простоя географически распределенных вычислительных узлов, объединенных низкоскоростной сетью. При этом, системы типа Desktop Grid имеют существенные отличия от традиционных вычислительных кластеров и вычислительных GRID и требуют специальных инструментов организации вычислений. В статье представлен механизм динамического прогнозирования времени завершения вычислительного эксперимента в Desktop Grid. Мы предлагаем статистический подход, основанный на линейной регрессионной модели с вычислением доверительного интервала, учетом накопления статистической ошибки и соответствующим — при необходимости — изменением прогноза. На основе предложенного подхода разработан алгоритм прогнозирования и программный модуль для Desktop Grid на базе BOINC. Мы представляем результаты экспериментов, основанные на данных проекта добровольных вычислений RakeSearch.

1. Ивашко Е.Е., Никитина Н.Н. Использование BOINC-грид в вычислительноемких научных исследованиях. Вестник Новосибирского государственного университета. Серия: Информационные технологии, том 11, вып. 1, 2013 г., стр. 53-57 / E.E. Ivashko, N.N. Nikitina. Employment of boinc-grid in computationally intensive scientific research. Vestnik NSU. Series: Information Technologies, vol. 11, issue 1, pp. 53-57 (in Russian).

2. Wu W., G. Chen, W. Kan, D. Anderson, F. Grey. Harness public computing resources for protein structure prediction computing. In Proc. of the International Symposium on Grids and Clouds (ISGC), 2013.

3. Anderson D. P., Christensen C., Allen B. Designing a Runtime System for Volunteer Computing. In Proc. of the 2006 ACM/IEEE Conference on Supercomputing, 2006, p. 126.

4. Amstel D. van. Scheduling for Volunteer Computing on the BOINC server infrastructure. PhD Thesis, 2012.

5. Ivashko E., Litovchenko V. Batch of Tasks Completion Time Estimation in a Desktop Grid. Communications in Computer and Information Science, vol. 965, 2019, pp. 500–510.

6. Khan M.Kh., Mahmood T., Hyder S.I. Scheduling in Desktop Grid Systems: Theoretical Evaluation of Policies and Frameworks. International Journal of Advanced Computer Science and Applications, vol. 8, issue 1, 2017, pp. 119–127.

7. Ивашко Е.Е. Desktop Grid корпоративного уровня. Программные системы: теория и приложения, том 5, № 1, 2014, стр. 183-190 / Ivashko E.E. Enterprise Desktop Grids. Program Systems: Theory and Applications, vol. 5, № 1, pp. 183-191 (in Russian).

8. Anderson D.P. A system for public-resource computing and storage. In Proc. of the Fifth IEEE/ACM International Workshop on Grid Computing, 2004, pp. 4–10.

9. Bazinet A. L., Cummings M. P. Computing the Tree of Life: Leveraging the Power of Desktop and Service Grids. In Proc. of the International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, 2011, pp. 1896–1902.

10. Peter Hellinckx, Sam Verboven, Frans Arickx, Jan Broeckhove. Predicting Parameter Sweep Jobs: From Simulation to Grid Implementation. In Proc. of the 2009 International Conference on Complex, Intelligent and Software Intensive Systems, 2009, pp. 402–408.

11. Hellinckx P., Verboven S., Arickx F., Broeckhove J. Runtime prediction based Grid scheduling of parameter sweep jobs. In Proc. of the IEEE Asia-Pacific Services Computing Conference, 2008, pp. 33–38.

12. Estrada, T., Taufer M. and Reed K. Modeling Job Lifespan Delays in Volunteer Computing Projects. In Proc. of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, 2009, pp. 331-338.

13. Kolokoltsev Y., Ivashko E., Gershenson C. Improving “tail” computations in a BOINC-based Desktop Grid. Open Engineering, vol. 7, issue 1, 2017, pp. 119–127.

14. Villela D. Minimizing the Average Completion Time for Concurrent Grid Applications / Journal of Grid Computing, 2010, vol. 8, issue 1, pp. 47–59.

15. Reynolds C. J., Winter S., Terstyanszky G.Z., Kiss T., Greenwell P., Acs S., Kacsuk P. Scientific Workflow Makespan Reduction through Cloud Augmented Desktop Grids. In Proc. of the IEEE Third International Conference on Cloud Computing Technology and Science, 2011, pp. 18–23.

16. Estrada T., Taufer M. Challenges in Designing Scheduling Policies in Volunteer Computing. In Desktop Grid Computing, Chapman & Hall/CRC, 2012, pp. 167–190.

17. Beaumont O., Bobelin L., Casanova H. et al. Towards Scalable, Accurate, and Usable Simulations of Distributed Applications and Systems. Institut National de Recherche en Informatique et en Automatique, Research Report RR-7761, 2011.

18. Estrada T., Taufer M., Anderson D.P. Performance Prediction and Analysis of BOINC Projects: An Empirical Study with EmBOINC. Journal of Grid Computing, no. 7, 2009, pp. 537-554.

19. Estrada T., Taufer M., Reed K., Anderson D.P. EmBOINC: An emulator for performance analysis of BOINC projects. In Proc. of the International Symposium on Parallel & Distributed Processing, 2009, pp. 1–8.

20. Taufer M., Kerstens A., Estrada T., Flores D.A., Teller P.J. SimBA: A Discrete Event Simulator for Performance Prediction of Volunteer Computing Projects. In Proc. of the21st International Workshop on Principles of Advanced and Distributed Simulation, 2007, pp. 189–197.

21. Чучуева И.А. Модель прогнозирования временных рядов по выборке максимального правдоподобия. Диссертация на соискание ученой степени кандидата технических наук. МГТУ, 2012 / Chuchueva I.A. Time Series Prediction Model for Maximum Credibility Sampling. The dissertation for the degree of candidate of technical sciences. MSTU, 2012 (in Russian).

22. Четыркин Е М. Статистические методы прогнозирования. М., Статистика, 1977, 200 стр. / Chetyrkin E. M. Statistical methods of forecasting. M., Statistics, 1977, 200 p. (in Russian).

23. Мамаева З.М. Введение в эконометрику. Нижегородский госуниверситет, 2010, 72 стр. / Mamaeva Z.M. Introduction to Econometrics. Nizhny Novgorod State University, 2010, 72 p. (in Russian).

24. Manzyuk M., Nikitina N., Vatutin E. Employment of Distributed Computing to Search and Explore Orthogonal Diagonal Latin Squares of Rank 9. In Proc. of the XI All-Russian research and practice conference "Digital techologies in education, science, society", 2017, pp. 97-100.