ИССЛЕДОВАНИЕ ПОДХОДОВ К РЕАЛИЗАЦИИ PAGERANK НА ЯЗЫКЕ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ CHARM++

Александр Сергеевич Фролов; Александр Сергеевич Семенов

Александр Сергеевич Фролов Научно-исследовательский центр электронной вычислительной техники
Александр Сергеевич Семенов Научно-исследовательский центр электронной вычислительной техники

Abstract

В статье представлены результаты исследования подходов к реализации задачи ранжирования вершин графа – PageRank, на языке параллельного программирования Charm++, основанном на асинхронной модели вычислений с управлением потоком сообщений. Предложены и реализованы три алгоритма PageRank с разной степенью асинхронности, приведены результаты экспериментов по исследованию производительности реализаций PageRank на 36-узловом вычислительном кластере Ангара-К1 на базе коммуникационной сети Ангара. Для сравнения результатов использовалась реализация PageRank из библиотеки Parallel BGL. Результаты исследования показали, что при небольшом количестве узлов (до 32) на задаче PageRank алгоритмы, разработанные на основе принципов асинхронных вычислений и управления потоком сообщений, но использующие механизмы агрегации коротких сообщений, имеют такую же эффективность, как и алгоритм, использующий классическую BSP- модель.

Author Biographies

Александр Сергеевич Фролов, Научно-исследовательский центр электронной вычислительной техники

начальник отдела

Александр Сергеевич Семенов, Научно-исследовательский центр электронной вычислительной техники

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

References

1. Brin S., Page L. Reprint of: The anatomy of a large-scale hypertextual web search engine //Computer networks. – 2012. – Т. 56. – №. 18. – С. 3825-3833.
2. Langville A. N., Meyer C. D. Google's PageRank and beyond: The science of search engine rankings. – Princeton University Press, 2011.
3. Suri P. R., Taneja H. An integrated ranking algorithm for efficient information computing in social networks //arXiv preprint arXiv:1204.1413. – 2012.
4. Sharma D. et al. A ranking algorithm for online social network search //Proceedings of the 6th ACM India Computing Convention. – ACM, 2013. – С. 17.
5. Winter C. et al. Google goes cancer: improving outcome prediction for cancer patients by network-based ranking of marker genes //PLoS Comput Biol. – 2012. – Т. 8. – №. 5.
6. Morrison J. L. et al. GeneRank: using search engine technology for the analysis of microarray experiments //BMC bioinformatics. – 2005. – Т. 6. – №. 1. – С. 1.
7. Page L. et al. The PageRank citation ranking: bringing order to the web. – 1999.
8. Kale L. V., Krishnan S. CHARM++: a portable concurrent object oriented system based on C++. – ACM, 1993. – Т. 28. – №. 10. – С. 91-108.
9. Acun B. et al. Parallel programming with migratable objects: charm++ in practice //SC14: International Conference for High Performance Computing, Networking, Storage and Analysis. – IEEE, 2014. – С. 647-658.
10. Official MPI Forum web-site, http://mpi-forum.org
11. Official OpenMP web-site, http://openmp.org
12. Фролов А.С., Семенов А.С., Марков А.С. Обзор инструментальных средств разработки параллельных графовых приложений для суперкомпьютерных комплексов // «Вычислительные нанотехнологии». – №4. – 2015.
13. McCune R. R., Weninger T., Madey G. Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing //ACM Computing Surveys (CSUR). – 2015. – Т. 48. – №. 2. – С. 25.
14. Malewicz G. et al. Pregel: a system for large-scale graph processing //Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. – ACM, 2010. – С. 135-146.
15. Seshadhri C., Pinar A., Kolda T. G. An in-depth study of stochastic Kronecker graphs //2011 IEEE 11th International Conference on Data Mining. – IEEE, 2011. – С. 587-596.
16. Murphy R. C. et al. Introducing the graph 500 //Cray User’s Group (CUG). – 2010.
17. Симонов А.С., Жабин И.А., Макагон Д.В. Разработка межузловой коммуникационной сети с топологией «многомерный тор» и поддержкой глобально адресуемой памяти для перспективных отечественных суперкомпьютеров. // Научно-техническая конференция «Перспективные направления развития вычислительной техники», ОАО «НИЦЭВТ», 2011.
18. Симонов А.С., Макагон Д.В., Жабин И.А., Щербак А.Н., Сыромятников Е.Л., Поляков Д.А. Первое поколение высокоскоростной коммуникационной сети «Ангара» // Наукоемкие технологии. — 2014. — Т. 15, No1. — С. 21-28.
19. Wesolowski L. et al. Tram: Optimizing fine-grained communication with topological routing and aggregation of messages //2014 43rd International Conference on Parallel Processing. – IEEE, 2014. – С. 211-220.
20. Gregor D., Lumsdaine A. The parallel BGL: A generic library for distributed graph computations //Parallel Object-Oriented Scientific Computing (POOSC). – 2005. – Т. 2. – С. 1-18.
21. Cheatham T. et al. Bulk synchronous parallel computing—a paradigm for transportable software //Tools and Environments for Parallel and Distributed Systems. – Springer US, 1996. – С. 61-76.
22. Willcock J. J. et al. Active pebbles: parallel programming for data-driven applications //Proceedings of the international conference on Supercomputing. – ACM, 2011. – С. 235-244.
23. Nelson J. et al. Grappa: A latency-tolerant runtime for large-scale irregular applications //International Workshop on RackScale Computing (WRSC w/EuroSys). – 2014.
24. Kaiser H., Brodowicz M., Sterling T. Parallex an advanced parallel execution model for scaling-impaired applications //2009 International Conference on Parallel Processing Workshops. – IEEE, 2009. – С. 394-401.