2023 № 3(60)

СОДЕРЖАНИЕ

Бредихин С. В., Щербакова Н. Г. Модель сети соавторства научного журнала
Герб А.Р., Омарова ГА. Алгоритмы разбиения графов: обзор литературы
Снытникова Т.В. Processing-in-Memory: текущие направления развития технологии
Малышкин В. Э., Перепелкин В. А. Мультиагентный подход к повышению эффективности исполнения фрагментированных программ в системе LuNA
Симонов В. С., Хайретдинов М. С. Метод преобразования императивного кода для платформ параллельной обработки данных

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

МОДЕЛЬ СЕТИ СОАВТОРСТВА НАУЧНОГО ЖУРНАЛА

УДК 519.177

DOI: 10.24412/2073-0667-2023-3-5-18

EDX: QADKBW

Традиционный подход к изучению сети научного соавторства основан на бинарных отношениях, возникающих между авторами, создавшими по крайней мере одну совместную публикацию. В работе представлена модель сети соавторства, учитывающая групповые отношения, возникающие между соавторами. Сеть моделируется с помощью гиперграфа, вершины которого соответствуют авторам, а ребра - публикациям. Представлен метод построения гиперграфа сети соавторства, основанный на данных, извлеченных из архива журнала. Измерены параметры гиперграфа и выявлены его топологические свойства. Данная работа продолжает изучение и апробацию методов анализа сетей соавторства (см. [1]).

Ключевые слова: комплексная сеть, гиперграф, соавторство, архив научных статей, библиометрия.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН (0251-2021-0005).

Список литературы

1. БРЕДИХИН С. В., ЛЯПУНОВ В. М., ЩЕРБАКОВА Н. Г. Гиперсеть научного соавторства. Анализ данных БД Repec // Пробл. информ. 2022. К2 4. С. 70-83. DOI: 10.24412/2073-0667-2022¬4-70-83.

2. NEWMAN М. Е. J. Networks: An introduction. Oxford Univ. Press, 2010. ISBN: 9780199206650.

3. ESTRADA Е. The structure of complex network: Theory and applications. Oxford Univ. Press, 2011. ISBN: 9780199591756.

4. LATORA V., NICOSIA V., Russo G. Complex networks: Principles, methods and applications. Cambridge Univ. Press, 2017. ISBN: 9781316216002.

5. NEWMAN, M. E. J. Scientific collaboration networks. I. Network construction and fundamental results // Phys. Rev. 2001. E 64, 016131. DOI: 10.1103/PhysRevE.64.016131.

6. NEWMAN, M. E. J. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality // Phys. Rev. 2001. E 64, 016132. DOI: 10.1103/PhysRevE.64.016132.

7. BARABASI A. L., JEONG H., NEDA Z., RAVASZ E., SCHUBERT A., VICSEK T. Evolution of the social network of scientific collaborations // Physica A. 2002. V. 311. P. 590-614. DOI: 10.1016/S0378- 4371(02)00736-7.

8. UDDIN S., HOSSAIN L., ABBASI A., RASMUSSEN K. Trend and efficiency analysis of coauthorship network // Scientometrics. 2012. V. 90, No 2. P. 687-699. DOI: 10.1007/sl 1192-011-0511-x.

9. SAVIC M., IVANOVIC NT, RADOVANOVIC NT, OGNJANOVIC Z., PEJOVIC A. Exploratory analysis of communities in co-authorship networks: A case study // Intern. Conf, on ICT Innovations. Springer, 2019. P. 55-64. ISBN 978-3-319-91194-6.

10. Сно H., YU Y. Link prediction for interdisciplinary collaboration via co-authorship network // Soc. Network Analysis and Mining. 2018. 8, 25. DOI: 10.1007/sl3278-018-0501-6.

11. CHUAN P.M., SON L.H., ALI M. ET AL. Link prediction in co-authorship networks based on hybrid content similarity metric // Appl. Intell. 2018. V. 48. P. 2470-2486. DOI: 10.1007/sl0489-017- 1086-x.

12. YOSHIKANE F., NOZAWA T., TSUJI K. Comparative analysis of co-authorship networks considering authors’ roles in collaboration: Differences between the theoretical and application areas// Scientometrics. 2006. V. 68, iss. 3. P. 643-655. DOI: 10.1007/slll92-006-0113-l.

13. ЩЕРБАКОВА H. Г. Моделирование групповых взаимодействий комплексных систем. Обзор // Пробл. информ. 2022. № 3. С. 24-45. DOL 10.24412/2073-0667-2022-3-24-45.

14. WILSON Т. Р. Relational networks: An extension of sociometric concepts // Soc. Networks. 1982. V. 4, iss. 2. P. 105-116. DOL 10.1016/0378-8733(82)90028-4.

15. BORGATTI S. P., EVERETT M. G. Network analysis of 2-mode data // Soc. networks. 1997. V. 19. P. 243-269. DOI: 10.1016/S0378-8733(96)00301-2.

16. FAUST K. Centrality in affiliation networks // Soc. Networks. 1997. V. 19. P. 157-191. DOI: 10.1016/80378-8733(96)00300-0.

17. WASSERMAN S., FAUST K. Social network analysis. Cambridge Univ. Press, 1984. ISBN 9780511815478.

18. BENKO G., FLAMM C., STADLER P. F. Generic properties of chemical networks: Artificial chemistry based on graph rewriting//Leet. Notes Comput. Sci. 2003. V. 2801, 10. DOL 10.1007/978- 3-540-39432-7_2.

19. BANERJEE S., JENAMANI NL, PRATHAR D. K. Properties of a projected network of a bipartite network // arXiv:1707.00912vl. DOL 10.48550/arXiv.l707.00912.

20. BERGE C. Graphs and hypergraphs. Amsterdam: North-Holland, 1976. ISBN 10.0444103996.

21. SEIDMAN S. Structures induced by collections of subsets: A hypergraph approach // Math. Soc. Sci. 1981. V. 1, iss. 4. P. 381-396. DOI: 10.1016/0165-4896(81)90016-0.

22. ESTRADA E., RODRIGUEZ-VELAZQUEZ J. A. Complex networks as hypergraphs // arXiv: physics/0505137, 2005. DOI: 10.1016/j.physa.2005.12.002.

23. HAN Y., ZHOU B., PEI J., JIA Y. Understanding importance of collaborations in coauthorship networks: A supportiveness analysis approach // Proc. 2009 SIAM Internal. Conf, on Data Mining. 2009. P. 1112-1123. DOI: 10.1137/1.9781611972795.95.

24. LUNG R. L, GASCO N., SUCIU M. A. A hypergraph model for representing scientific output // Scientometrics. 2018. V. 117. P. 1361-1379. DOL 10.1007/sl 1192-018-2908-2.

25. ATKIN R. Н. From cohomology in physics to q-connectivity in social science // Intern. J. Man-Machine Studies. 1972. V. 4, iss. 2. P. 139-167. DOI: 10.1016/S0020-7373(72)80029-4.

26. ATKIN R. H. An algebra for patterns on a complex, I // Intern. J. Man-Machine Studies. 1974. V. 6, iss. 3. P. 285-307. DOI: 10.1016/S0020-7373(74)80024-6.

27. ATKIN R. H. An algebra for patterns on a complex, II // Intern. J. Man-Machine Stud. 1976. V. 8, iss. 5. P. 483-498. DOI: 10.1016/80020-7373(76)80015-6.

28. PATANIA A., PETRI G., VACCARINO F. The shape of collaborations // EPJ Data Science. 2017. V. 6, 18. DOI 10.1140/epjds/sl3688-017-0114-8.

29. ZHOU D., ORSHANSKIY S. A., ZHA H., GILES C. L. Co-ranking authors and documents in a heterogeneous network // 7th IEEE International Conference on Data Mining (ICDM 2007), Omaha (USA), 2007. P. 739-744. DOI: 10.1109/ICDM.2007.57.

30. VOLOSHIN V. I. Introduction to graph and hypergraph theory. NY: Nova Science Publ., 2009. ISBN: 978-1-60692372-6.

31. BRETTO A. Hypergraph theory. Springer, 2013. ISBN 978-3-319-00079-4.

32. КОРМЕН T., ЛЕЙЗЕРСОН Ч., РИВЕСТ T. Алгоритмы: построение и анализ. М.: МЦНМО. 2002. ISBN: 978-5-907114-11-1

Библиографическая ссылка: Бредихин С. В., Щербакова Н. Г. Модель сети соавторства научного журнала //"Проблемы информатики", 2023, № 3, с.5-18. DOI: 10.24412/2073-0667-2023-3-5-18.

А.Р. Герб . Г. А. Омарова*

Новосибирский государственный университет, 630090, Новосибирск, Россия

*Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

АЛГОРИТМЫ РАЗБИЕНИЯ ГРАФОВ: ОБЗОР ЛИТЕРАТУРЫ

УДК 519.17+519.61

DOI: 10.24412/2073-0667-2023-3-19-36

EDN: LXQVVD

Работа посвящена разбору современных методов и алгоритмов разбиения графов. Исследованы и проанализированы точные решения, последовательные итерационные, многоуровневые, потоковые и параллельные алгоритмы. Отмечены как преимущества, так и слабые места ал-горитмов, выявленные при их реализации.

Ключевые слова: графы, огрубление, последовательные и параллельные алгоритмы, мно-гоуровневые алгоритмы.

Работа выполнена при финансовой поддержке Министерства пауки и высшего образования Российской Федерации (код проекта 0251-2020-0001)

Список литературы

1. Итоги третьего квартала 2022 года соцсети Вконтакте. [Electron. Res.]: https://vk.com/ press/q3-2022-results.

2. Annual Report 2022 (SEC Filing Form 10-K). Meta Platforms, Inc. [Electron. Res.]: https://dl8rn0p25nwr6d.cloudfront.net/СIK-0001326801/e574646c-c642-42d9-9229- 3892bl3aabfb.pdf.

3. Annual Report 2022 (SEC Filing Form 10-K). Twitter, Inc. [Electron. Res.]: https://www.sec. gov/ix?doc=/Archives/edgar/data/1418091/000141809122000029/twtr-20211231.htm.

4. Gottesbiiren L. et al. Shared-memory n-level hypergraph partitioning // Proc, of the Symp. on algorithm engineering and experiments (ALENEX). Soc. for Industrial and Appl. Math., 2022.

5. Hamers L. et al. Similarity measures in scientometric research: The Jaccard index versus Salton’s cosine formula // Inform. Process, and Manag. 1989. V. 25, iss. 3. P. 315-318.

6. Bourse F., Lelarge M., Vojnovic M. Balanced graph edge partition // Proc, of the 20th ACM SIGKDD Intern, conf, on knowledge discovery and data mining. 2014.

7. Brandes U. et al. On modularity clustering // IEEE Trans. On Knowledge And Data Engineering. 2007.

8. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

9. Armbruster М. Branch-and-cut for a semidefinite relaxation of large-scale minimum bisection problems. PhD-thesis. Technische Universit?t Chemnitz. Chemnitz, 2007.

10. Delling D. et al. Exact combinatorial branch-and-bound for graph bisection // Proc, of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX). Soc. for Industrial and Applied Mathematics, 2012.

11. Felner A. Finding optimal solutions to the graph partitioning problem with heuristic search // Ann. Math. Artif. Intell. 2005. V. 45. P. 293-322.

12. Feldmann A. E., Widmayer P. An O(n4) time algorithm to compute the bisection width of solid grid graphs // Proc, of the Algorithms-ESA 2011: 19th Annual European Symp., Saarbriicken, Germany, Sept. 5-9, 2011. Springer Berlin Heidelberg, 2011.

13. Hager W. W., Phan D. T., Zhang H. An exact algorithm for graph partitioning. Mathematical Programming. 2013. V. 137. P. 531-556.

14. Karisch S. Е., Rendl F., Clausen J. Solving graph bisection problems with semidefinite programming // INFORMS J. on Comput. 2000. V. 12, iss. 3. P. 177-191.

15. Sellmann M., Sensen N., Timajev L. Multicommodity flow approximation used for exact graph partitioning // Algorithms-ESA 2003: 11th Annual European Symp., Budapest, Hungary, Sept. 16-19, 2003. Proc. 11. Springer Berlin Heidelberg, 2003.

16. Fiduccia С. M., Mattheyses R. M. A linear-time heuristic for improving network partitions // Proc, of the 19th Conf, on Design Automation. 1982. P. 175-181.

17. Bui T. N., Jones C. A heuristic for reducing fill-in in sparse matrix factorization // Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (United States), 1993.

18. Walshaw C. An exploration of multilevel combinatorial optimization / Multilevel Optimization in VLSICAD. Combinatorial Optimization. V. 14. Springer, Boston, MA, 2003.

19. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs // SIAM Journal on scientific Computing. 1998. V. 20, N 1. P. 359-392.

20. Герб A. P., Омарова Г. А. Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ // Пробл. информ. 2022. № 3. С. 77-89.

21. Akhremtsev У., Sanders Р., Schulz С. High-quality shared-memory graph partitioning // IEEE Trans, on Parallel and Distributed Systems. 2020.

22. Qatalyiirek U. V., Aykanat C. Patoh (partitioning tool for hypergraphs). Encyclopedia of parallel computing. Springer, 2011.

23. Preen R. J., Smith J. Evolutionary n-level hypergraph partitioning with adaptive coarsening // IEEE Trans, on Evolutionary Computation. 2019. V. 23, iss. 6. P. 962-971.

24. Sanders P., Schulz C. Engineering multilevel graph partitioning algorithms // Algorithms-ESA 2011: 19th Annual European Symp., Saarbrucken, Germany, Sept. 5-9, 2011. Proc. 19. Springer Berlin Heidelberg, 2011.

25. Hamann M., Strasser B. Graph bisection with Pareto optimization. Journal of Experimental Algorithmics (JEA). 2018. V. 23. P. 1-34.

26. Henzinger A., Noe A., Schulz C. ILP-based local search for graph partitioning // ACM J. of Experimental Algorithmics (JEA). 2020. V. 25. P. 1-26.

27. Godenschwager C. et al. A framework for hybrid parallel flow simulations with a trillion cells in complex geometries // Proc, of the Intern, conf, on high performance computing, networking, storage and analysis. 2013.

28. Alpert C. J., Huang J. H., Kahng A. B. Multilevel circuit partitioning // Proc, of the 34th Annual design automation Conf. 1997.

29. Osipov V., Sanders P. n-Level graph partitioning // Algorithms-ESA 2010: 18th Annual European Symp., Liverpool, UK, Sept. 6-8, 2010. Proc., Part I 18. Springer Berlin Heidelberg, 2010.

30. Schlag S. et al. High-quality hypergraph partitioning // ACM J. of Experimental Algorithmics. 2023. V. 27. P. 1-39.

31. Alpert C. J. The ISPD98 circuit benchmark suite // Proc, of the 1998 Intern, symp. on physical design. 1998.

32. Garey M. R., Johnson D. S. Computers and intractability. San Francisco: Freeman, 1979.

33. Heuer T., Maas N., Schlag S. Multilevel Hypergraph Partitioning with Vertex Weights Revisited. arXiv preprint arXiv:2102.01378. 2021.

34. Patwary M. A. K., Garg S., Kang B. Window-based streaming graph partitioning algorithm // Proc, of the Australasian Computer Science Week Multiconf. 2019.

35. Faraj M. F., Schulz C. Buffered streaming graph partitioning. arXiv preprint arXiv:2102.09384. 2021.

36. Jafari N., Selvitopi O., Aykanat C. Fast shared-memory streaming multilevel graph partitioning //J. of Parallel and Distributed Computing. 2021. V. 147, iss. 2. P. 140-151.

37. Stanton I., Kliot G. Streaming graph partitioning for large distributed graphs // Proc, of the 18th ACM SIGKDD Intern, conf, on knowledge discovery and data mining. 2012.

38. Slota G. M. et al. Scalable, multi-constraint, complex-objective graph partitioning // IEEE Trans, on Parallel and Distributed Systems. 2020. V. 31, iss. 1. P. 2789-2801.

39. Zhang W., Chen Y., Dai D. AKIN: A streaming graph partitioning algorithm for distributed graph storage systems. 2018 18th IEEE/АСМ Intern. Symp. on Cluster, Cloud and Grid Computing (CCGRID). IEEE, 2018.

40. Tsourakakis C. et al. Fennel: Streaming graph partitioning for massive scale graphs // Proc, of the 7th ACM Intern, conf, on Web search and data mining. 2014.

41. Qatalyiirek U. V. et al. Multithreaded clustering for multi-level hypergraph partitioning // IEEE 26th Intern. Parallel and Distributed Proc. Symp. IEEE, 2012.

42. Meyerhenke H., Sanders P., Schulz C. Partitioning complex networks via size-constrained clustering // Experimental Algorithms: 13th Intern. Symp., SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proc. 13. Springer International Publishing, 2014.

43. LaSalle D., Karypis G. Multi-threaded graph partitioning. 2013 IEEE 27th Intern. Symp. on Parallel and Distributed Processing. IEEE, 2013.

44. Maleki S. et al. Bipart: a parallel and deterministic hypergraph partitioner // Proc, of the 26th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. 2021.

45. Slota G. M., Madduri K., Rajamanickam S. Complex network partitioning using label propagation // SIAM J. Scien. Comput. 2016. V. 38, iss. 5.

46. Gottesbiiren L. et al. Scalable shared-memory hypergraph partitioning // Proc, of the Workshop on algorithm engineering and experiments (ALENEX). Soc. for Industrial and Appl. Math., 2021.

47. Gottesbiiren L., Hamann M. Deterministic parallel hypergraph partitioning // Euro-Par 2022: Parallel Processing: 28th Intern, conf, on parallel and distributed computing, Glasgow, UK, Aug. 22-26, 2022. Proc. Cham: Springer International Publishing, 2022.

48. Savage J. E., Wloka M. G. Parallelism in graph-partitioning // Journal of Parallel and Distributed Computing. 1991. V. 13, iss. 3. P. 257-272.

49. Gottesbiiren L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.

50. Hamann M. et al. Distributed graph clustering using modularity and map equation // Euro¬Par 2018: Parallel Processing: 24th Intern. Conf, on Parallel and Distributed Computing, Turin, Italy, Aug. 27-31, 2018. Proc. Springer International Publishing, 2018.

51. Andersen R., Peres Y. Finding sparse cuts locally using evolving sets // Proc, of the 41st Annual ACM symp. on theory of computing. 2009.

52. Back T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press, 1996.

53. Barnard S. T., Simon H. D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and experience. 1994.

54. Benlic U., Hao J. K. An effective multilevel memetic algorithm for balanced graph partitioning // 22nd IEEE Intern, conf, on tools with artificial intelligence. IEEE. 2010.

55. Boppana R. B. Eigenvalues and graph bisection: An average-case analysis // 28th Annual Symp. on Foundations of Computer Science (sfcs 1987). IEEE, 1987.

56. Donath W. E., Hoffman A. J. Lower bounds for the partitioning of graphs // IBM J. of Research and Development. 1973.

57. Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory // Czechoslovak Math. J. 1975. V. 25, iss. 4. P. 619-633.

58. Grigni M., Manne F. On the complexity of the generalized block distribution. LNCS. 1996. V. 1117.

59. LaSalle D. et al. Improving graph partitioning for modern graphs and architectures // Proc, of the 5th Workshop on Irregular Applications: Architectures and Algorithms. 2015.

60. Manne F., S0orevik T. Partitioning an array onto a mesh of processors // Applied parallel computing industrial computation and optimization: 3rd Intern. Workshop, PARA’96 Lyngby, Denmark, Aug. 18-21, 1996. Proceedings 3. Springer Berlin Heidelberg, 1996.

61. Meyerhenke H., Sanders P., Schulz C. Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering // J. of Heuristics. 2016. V. 22, iss. 1. P. 759-782.

62. Sanders P., Schulz C. Distributed evolutionary graph partitioning // Proc, of the 14th workshop on algorithm engineering and experiments (ALENEX). Soc. for Industrial and Appl. Math., 2012.

63. Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages. DOL https://doi.org/10.1145/2049662.2049663, 2011

64. Ugander J., Backstrom L. Balanced label propagation for partitioning massive graphs // Proc, of the sixth ACM Intern, conf, on Web search and data mining. 2013.

65. Van Bevern R. et al. On the parameterized complexity of computing balanced partitions in graphs // Theory of Computing Systems. 2015. V. 57, iss. 1. P. 1-35.

66. Yasar A. et al. On symmetric rectilinear matrix partitioning. arXiv preprint arXiv:2009.07735. 2020.

67. Yasar A., Qatalyurek U. V. Heuristics for symmetric rectilinear matrix partitioning. arXiv preprint arXiv: 1909.12209. 2019.

Библиографическая ссылка: Герб А.Р., Омарова ГА. Алгоритмы разбиения графов: обзор литературы //"Проблемы информатики", 2023, № 3, с. 19-36. DOI: 10.24412/2073-0667-2023-3-19-36.

Т. В. Снытникова

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

PROCESSING-IN-MEMORY: ТЕКУЩИЕ НАПРАВЛЕНИЯ РАЗВИТИЯ ТЕХНОЛОГИИ

УДК 004.272

DOI: 10.24412/2073-0667-2023-3-37-54

EDX: FSPSXV

Перемещение данных между центральным процессором и оперативной памятью является препятствием первого порядка на пути повышения производительности, масштабируемости и энергоэффективности современных систем. Компьютерные системы используют ряд методов для снижения накладных расходов, связанных с перемещением данных, начиная с традиционных механизмов и заканчивая новыми методами, такими как вычисления в памяти (Processing¬in-Memory, PIM). Эти методы можно разделить на два больших класса: вычисления рядом с памятью (processing-near-memory, PNM), когда вычисления выполняются в выделенных элементах обработки, и вычисление с использованием памяти (processing-using-memory, PUM), когда вычисления выполняются внутри массива памяти за счет использования внутренних аналоговых рабочих свойств запоминающего устройства. В работе рассматривается парадигма архитектур PIM и приводится обзор архитектур PUM, основанных на параллельных операциях DRAM и ассоциативных процессорах.

Ключевые слова: архитектуры вычислений в памяти, ассоциативные процессоры, RDRAM.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН 0251-2021-0005.

Список литературы

1. Boroumand A. et al. Google Workloads for Consumer Devices: Mitigating Data Movement Bottlenecks //In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’18). Association for Computing Machinery, New York, NY, USA, 2018, P. 316-331.

2. Mutlu O. et al. Processing Data Where It Makes Sense: Enabling In-Memory Computation // Microprocessors and Microsystems, 2019. V. 67, P. 28-41.

3. Ghose S. et al., The Processing-in-Memory Paradigm: Mechanisms to Enable Adoption Beyond-CMOS Technologies for Next Generation Computer Design, 2019.

4. Mutlu O. et al. Enabling Practical Processing in and Near Memory For Datalntensive Computing // Enabling Practical Processing in and near Memory for Data-Intensive Computing, 2019, P. 1-4.

5. Ghose S. et al. Processing-in-Memory: A Workload-Driven Perspective //in IBM Journal of Research and Development, 2019, V. 63. N 6. P. 3:1-3:19.

6. Siegl P. et al. Data-Centric Computing Frontiers: A Survey on Processing-in-Memory // Data- Centric Computing Frontiers: A Survey On Processing-In-Memory, 2016, P. 295-308.

7. Mutlu O. et al. Processing Data Where It Makes Sense: Enabling In-Memory Computation // Microprocessors and Microsystems, 2019, V. 67, P. 28-41.

8. Wulf W. A., McKee S. A. Hitting the Memory Wall: Implications of the Obvious // SIGARCH Comput. Archit. News, 1995, V. 23, P. 20-24.

9. Alshahrani R. The Path to Exascale Computing // https://bit.ly/3CIzcll, 2015.

10. Oliveira G. F. et al. DAMOV: A New Methodology and Benchmark Suite for Evaluating Data Movement Bottlenecks // IEEE Access, 2021, V. 9, P. 134457-134502.

11. Mutlu O. et al. A modern primer on processing in memory // Emerging Computing: From Devices to Systems: Looking Beyond Moore and Von Neumann. Singapore: Springer Nature Singapore, 2022. P. 171-243.

12. Santoro G., Turvani G., Graziano M. New logic-in-memory paradigms: An architectural and technological perspective // Micromachines, 2019, V. 10. N 6. P. 368.

13. Singh G. et al. Near-memory computing: Past, present, and future // Microprocessors and Microsystems, 2019, V. 71, P. 102868.

14. Seshadri V., Mutlu O. The Processing Using Memory Paradigm: In-DRAM Bulk Copy, Initialization, Bitwise AND and OR // arXiv preprint arXiv:1610.09603, 2016.

15. Seshadri V., Mutlu O. Simple operations in memory to reduce data movement // Advances in Computers, Elsevier, 2017, V. 106, P. 107-166.

16. Kim J. S. et al. GRIM-filter: Fast seed filtering in read mapping using emerging memory technologies //arXiv preprint arXiv:1708.04329, 2017.

17. Kim J. S. et al. GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies // BMC genomics, 2018, V. 19, N 2. P. 23-40.

18. Boroumand A. et al. LazyPIM: An efficient cache coherence mechanism for processing-in-memory // IEEE Computer Architecture Letters, 2016, V. 16. N 1. P. 46-50.

19. Hashemi M., Mutlu O., Patt Y. N. Continuous runahead: Transparent hardware acceleration for memory intensive workloads // 2016 49th Annual IEEE/АСМ International Symposium on Microarchitecture (MICRO), IEEE, 2016, P. 1-12.

20. Hashemi M. et al. Accelerating dependent cache misses with an enhanced memory controller // ACM SIGARCH Computer Architecture News, 2016, V. 44. N 3. P. 444-455.

21. Seshadri V. et al. Gather-scatter DRAM: In-DRAM address translation to improve the spatial locality of non-unit strided accesses // Proceedings of the 48th International Symposium on Microarchitecture, 2015, P. 267-280.

22. Pattnaik A. et al. Scheduling techniques for GPU architectures with processing-in-memory capabilities // Proceedings of the 2016 International Conference on Parallel Architectures and Compilation, 2016, P. 31-44.

23. Zhang D. et al. TOP-PIM: Throughput-oriented programmable processing in memory // Proceedings of the 23rd international symposium on High-performance parallel and distributed computing, 2014, P. 85-98.

24. Ahn J. et al. A scalable processing-in-memory accelerator for parallel graph processing // Proceedings of the 42nd Annual International Symposium on Computer Architecture, 2015, P. 105¬117.

25. Gao M., Kozyrakis C. HRL: Efficient and flexible reconfigurable logic for near-data processing // 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA), leee, 2016, P. 126-137.

26. Ahn J. et al. PIM-enabled instructions: A low-overhead, locality-aware processing-in-memory architecture // ACM SIGARCH Computer Architecture News, 2015, V. 43, N 3S, P. 336-348.

27. Lee J. H., Sim J., Kim H. BSSync: Processing near memory for machine learning workloads with bounded staleness consistency models // 2015 International Conference on Parallel Architecture and Compilation (PACT), IEEE, 2015, P. 241-252.

28. Nai L. et al. Graphpim: Enabling instruction-level pim offloading in graph computing frameworks // 2017 IEEE International symposium on high performance computer architecture (HPCA), IEEE, 2017, P. 457-468.

29. Seshadri V. et al. Ambit: In-memory accelerator for bulk bitwise operations using commodity DRAM technology // Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, 2017, P. 273-287.

30. Seshadri V. et al. Fast bulk bitwise AND and OR in DRAM // IEEE Computer Architecture Letters, 2015, V. 14, N 2, P. 127-131.

31. Seshadri V., Mutlu O. Simple operations in memory to reduce data movement // Advances in Computers, Elsevier, 2017, V. 106. P. 107-166.

32. Kang Н. В., Hong. S. К. One-Transistor Type DRAM // US Patent 7701751, 2009

33. Lu S. L., Lin У. C., Yang C. L. Improving DRAM latency with dynamic asymmetric subarray // Proceedings of the 48th International Symposium on Microarchitecture, 2015, P. 255-266.

34. Gao F., Tziantzioulis G., Wentzlaff D. Computedram: In-memory compute using off-the-shelf drams // Proceedings of the 52nd annual IEEE/ACM international symposium on microarchitecture, 2019, P. 100-113.

35. Seshadri V. et al. RowClone: Fast and energy-efficient in-DRAM bulk data copy and initialization // Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture, 2013. P. 185-197.

36. Kim J. S. et al. D-RaNGe: Using commodity DRAM devices to generate true random numbers with low latency and high throughput // 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA), IEEE, 2019, V. 582-595.

37. Hajinazar N. et al. SIMDRAM: a framework for bit-serial SIMD processing using DRAM // Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, 2021, P. 329-345.

38. Olgun A. et al. QUAC-TRNG: High-throughput true random number generation using quadruple row activation in commodity DRAM chips // 2021 АСМ/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), IEEE, 2021, P. 944-957.

39. Ferreira J. D. et al. pluto: In-dram lookup tables to enable massively parallel general-purpose computation //arXiv preprint arXiv:2104.07699, 2021.

40. Olgun A. et al. PiDRAM: A Holistic End-to-end FPGA-based Framework for Processing-in- DRAM // ACM Transactions on Architecture and Code Optimization, 2022, V. 20, N 1, P. 1-31.

41. Yaglikci A. G. et al. HiRA: Hidden Row Activation for Reducing Refresh Latency of Off- the-Shelf DRAM Chips // 2022 55th IEEE/АСМ International Symposium on Microarchitecture (MICRO), IEEE, 2022, P. 815-834.

42. Garzon E. et al. AM 4: MRAM crossbar based CAM/TCAM/ACAM/AP for in-memory computing // IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2023, V. 13, N 1, P. 408-421.

43. Снытникова T. В. Развитие ассоциативных параллельных архитектур // Проблемы ин-форматики. 2019. No 2. С. 36-50.

44. Мартышкин, А. И. Специализированный аппаратный модуль ассоциативного сопроцессора на базе ПЛИС для вычислительных систем с изменяемой структурой / А. И. Мартышкин, А. Н. Перекусихина // XXI век: итоги прошлого и проблемы настоящего плюс, 2019, Т. 8, № 3(47), С. 42-50.

45. Бондаренко М. Ф., Хаханов В. И., Литвинова Е. И. Структура логического ассоциативного мультипроцессора // Автоматика и телемеханика, 2012, № 10, С. 71-92.

46. Гайдук С. и др. Сферический мультипроцессор PRUS для решения булевых уравнений // Радиоэлектроника и информатика, 2004, № 4 (29). С. 69-78.

47. Yantir Н. Е. et al. An ultra-area-efficient 1024-point in-memory EFT processor // Micromachines, 2019, V. 10, No 8, P. 509-514.

48. Kaplan R., Yavits L., Ginosasr R. BioSEAL: In-memory biological sequence alignment accelerator for large-scale genomic data // Proceedings of the 13th ACM International Systems and Storage Conference, 2020, P. 36-48.

49. Sander C., Schneider R. Database of homology-derived protein structures and the structural meaning of sequence alignment //Proteins: Structure, Function, and Bioinformatics, 1991, V. 9, N 1, P. 56-68.

50. Hanhan R. et al. Edam: edit distance tolerant approximate matching content addressable memory // Proceedings of the 49th Annual International Symposium on Computer Architecture, 2022, P. 495-507.

51. Zhong Н. et al. ASMCap: An Approximate String Matching Accelerator for Genome Sequence Analysis Based on Capacitive Content Addressable Memory // arXiv preprint arXiv:2302.07478. — 2023.

52. Снытникова T. В., Непомнящая А. Ш. Решение задач на графах с помощью STAR- машины, реализуемой на графических ускорителях // Прикладная дискретная математика. 2016. Т. 3(33). С. 98-115.

53. Снытникова Т. В. Реализация модели ассоциативных вычислений на СРи:библиотека базовых процедур языка STAR // Вычислительные методы и программирование. Новые вычислительные технологии. 2018. Т. 19. С. 85-95.

Библиографическая ссылка: Снытникова Т.В. Processing-in-Memory: текущие направления развития технологии //"Проблемы информатики", 2023, № 3, с. 37-54. DOI: 10.24412/2073-0667-2023-3-37-54.

В.Э. Малышкин, В. А. Перепелкин

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия,

Новосибирский национальный исследовательский государственный университет, 630090, Новосибирск, Россия,

Новосибирский государственный технический университет, 630073, Новосибирск, Россия

МУЛЬТИАГЕНТНЫЙ ПОДХОД К ПОВЫШЕНИЮ ЭФФЕКТИВНОСТИ ИСПОЛНЕНИЯ ФРАГМЕНТИРОВАННЫХ ПРОГРАММ В СИСТЕМЕ LUNA

УДК 004.4’242

DOI: 10.24412/2073-0667-2023-3-55-67

EDN: LYEAKS

Применение систем параллельного программирования и систем автоматического конструи-рования параллельных программ предоставляет возможности к статической и/или динамической адаптации исполнения параллельной программы к особенностям вычислителя и хода вычислений, но при этом возникает проблема снижения накладных расходов, возникающих из-за работы исполнительной системы (динамических системных алгоритмов). Существенное снижение таких накладных расходов возможно за счет переноса как можно большего количества работы по конструированию и адаптации параллельной программы на этап трансляции, но при этом важно сохранять возможность динамической настройки исполнения параллельной программы в части, где настройка должна по существу выполняться динамически (например, для осуществления динамической балансировки нагрузки на вычислительные узлы). В работе предлагается технологичный подход к переносу существенного объема работ по конструированию и исполнению параллельных программ в системе LuNA, который сохраняет возможность обеспечения динамических свойств исполнения программы. Предложенный подход позволил существенно снизить накладные расходы на исполнение LuNA-программ по сравнению с традиционным подходом распределенной динамической интерпретации LuNA-программ.

Ключевые слова: фрагментированное программирование, система LuNA, автоматизация конструирования параллельных программ, высокопроизводительные вычисления, мультиа- гентный подход, частичные вычисления.

Исследование выполнено в рамках государственного задания ИВМиМГ СО РАН 0251-2022-0005

Список литературы

1. Malyshkin, V.E., Perepelkin, V. A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem. // Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2011. Lecture Notes in Computer Science, 2011. V. 6873. Springer, Berlin, Heidelberg. DOL 10.1007/978-3-642-23178-0_5.

2. Вальковский В. А., Малышкин В. Э. Синтез параллельных программ и систем на вычис-лительных моделях / Отв. ред. В.Е. Котов; АН СССР, Сиб. отд-ние, ВЦ. Новосибирск: Наука. Сиб. отд-ние, 1988.

3. Малышкин В. Э. Технология фрагментированного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2012. № 46 (305).

4. Malyshkin V. Е. Active Knowledge, LuNA and Literacy for Oncoming Centuries // Essays Dedicated to Pierpaolo Degano on Programming Languages with Applications to Biology and Security. 2015. V. 9465. Springer-Verlag, Berlin, Heidelberg. P. 292-303.

5. Лебедев Д. В., Перепелкин В. А. Численное решение одномерной краевой задачи филь-трации жидкости для системы «нефть-вода» и ее реализация в системе фрагментированного программирования LuNA // Вестник Казахского национального университета им. Аль-Фараби, серия математика, механика информатика. № 3 (82). 2014. С. 64-73.

6. Akhmed-Zaki D. Zh., Lebedev D.V., Perepelkin V. A. Implementation of a Three-Phase Fluid Flow (“Oil-Water-Gas”) Numerical Model in the LuNA Fragmented Programming System //In Proc 13th International Conference on Parallel Computing Technologies. LNCS 9251. Springer, 2015. P. 489¬497. DOL 10.1007/978-3-319-21909-7_47.

7. Лебедев Д. В., Перепелкин В. А. Решение трехмерного модельного уравнения теплопровод¬ности в системе фрагментированного программирования LuNA // Параллельные вычислитель¬ные технологии (ПаВТ’2016): труды международной научной конференции (28 марта - 1 апреля 2016 г., г. Архангельск). Челябинск: Издательский центр ЮУрГУ, 2016. С. 784.

8. Akhmed-Zaki, D., Lebedev, D., Perepelkin, V. Implementation of a three dimensional three-phase fluid flow (“oil-water-gas”) numerical model in LuNA fragmented programming system // Journal of Supercomputing (2017). N 73 (2). Springer, 2017. P. 624-630. DOL 10.1007/sl1227-016-1780-1.

9. Malyshkin V.E., Perepelkin V. A., Schukin G. A. Distributed Algorithm of Data Allocation in the Fragmented Programming System LuNA //In Proc 13th International Conference on Parallel Computing Technologies. LNCS 9251. Springer, 2015. P. 80-85. DOL 10.1007/978-3-319-21909-7_8.

10. Malyshkin. V., Perepelkin. V., Schukin G. Scalable Distributed Data Allocation in LuNA Fragmented Programming System // Journal of Supercomputing, S.I.: Parallel Computing Technologies. Springer, 2017. P. 1-7. DOL 10.1007/sll227-016-1781-0.

11. Akhmed-Zaki, D., Lebedev, D., Malyshkin, V., Perepelkin, V. Automated construction of high performance distributed programs in LuNA system // 15th International Conference on Parallel Computing Technologies, PaCT 2019; Almaty; Kazakhstan. LNCS 11657. Springer, 2019. P. 3-9. DOL 10.1007/978-3-030-25636-4_l.

12. Кудрявцев А. А., Малышкин В. Э., Нуштаев Ю. Ю., Перепелкин В. А., Спирин В. А. Эф-фективная фрагментированная реализация краевой задачи фильтрации двухфазной жидкости // Проблемы информатики. 2023. № 2. С. 45-73. DOL 10.24412/2073-0667-2023-2-45-73.

13. Belyaev, N., Kireev, S. LuNA-ICLU Compiler for Automated Generation of Iterative Fragmented Programs. // Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2019. Lecture Notes in Computer Science, V. 11657. Springer, Cham. DOL 10.1007/978-3-030-25636-4_2.

Библиографическая ссылка: Малышкин В. Э., Перепелкин В. А. Мультиагентный подход к повышению эффективности исполнения фрагментированных программ в системе LuNA //"Проблемы информатики", 2023, № 3, с.55-67. DOI: 10.24412/2073-0667-2023-3-55-67.

В. С. Симонов*. М.С. Xaйpeтдинов*,**

*Новосибирский государственный технический университет, 630087, Новосибирск, Россия

*,**Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

МЕТОД ПРЕОБРАЗОВАНИЯ ИМПЕРАТИВНОГО КОДА ДЛЯ ПЛАТФОРМ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ

УДК 004.89

DOI: 10.24412/2073-0667-2023-3-68-80

EDX: HGORYY

Существует множество платформ для обработки данных, которые позволяют последовательным программам получать доступ к возможностям параллельной обработки. Чтобы извлечь выгоду из преимуществ таких платформ, существующий код приходится переписывать на языки, специфичные для конкретной предметной области, которые поддерживает каждая платформа. Данное преобразование — утомительный и подверженный ошибкам процесс — также требует от разработчиков выбора нужной платформы, которая оптимизирует производительность с учетом конкретной рабочей нагрузки.

В данной статье описывается формальный метод, результатом применения которого на им-перативном коде являются эквивалентные инструкции, пригодные для исполнения в системе параллельной обработки данных, например, Hadoop, реализующей парадигму MapReduce. Метод применяется для вывода высокоуровневой сводки, выраженной на нашем языке спецификации программы, которая затем компилируется для выполнения в Apache Spark [1]. Было показано, что метод позволяет преобразовать императивный код в пригодный для исполнения на платформе Apache Spark . Приведенные результаты выполняются в среднем в 3,3 раза быстрее, чем последовательные реализации, а также лучше масштабируются для больших наборов данных.

Ключевые слова: императивный код, параллельная обработка данных.

Список литературы

1. Apache Spark. [Electron res.]: https://spark.apache.org. Accessed: 2023-01-19.

2. Apache Hadoop. [Electron res.]: http://hadoop.apache.org. Accessed: 2023-01-19.

3. Apache Storm. [Electron res.]: http://storm.apache.org. Accessed: 2023-01-19.

4. GraphLab Create. [Electron res.]: https://dato.com/. Accessed: 2023-01-20.

5. MongoDB [Electron res.]: https://www.mongodb.org. Accessed: 2023-01-19.

6. Akidau T., Bradshaw R., Chambers C., Chernyak S., Fernandez-Moctezuma R. J., Lax R., McVeety S., Mills D., Berry F., Schmidt E., Whittle S. The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing // Proceedings of the VLDB Endowment 8, 2015. P. 1792-1803.

7. TensorFlow. [Electron res.]: http://tensorflow.org/. Accessed: 2023-01-20.

8. Ragan-Kelley J., Barnes C., Adams A., Paris S., Durand F., Amarasinghe S. Halide: A Language and Compiler for Optimizing Parallelism, Locality, and Recomputation in Image Processing Pipelines // Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2013. PLDIT3, ACM, New York, NY, USA. P. 519-530, DOL 10.1145/2491956.2462176.

9. Apache Hive. [Electron res.]: http://hive.apache.org. Accessed: 2023-01-20.

10. Solar-Lezama A., Arnold G., Tancau L., Bodik R., Saraswat V., Seshia S. Sketching Stencils // Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2007. PLDI ’07, ACM, New York, NY, USA. P. 167-178, DOI: 10.1145/1273442.1250754.

11. Arvind K. Sujeeth A.K., Kevin J. Brown K. J., Lee H., Rompf T., Chafi H., Odersky M., Olukotun K. Delite: A Compiler Architecture for Performance-Oriented Embedded Domain-Specific. 2014.

12. Hoare С. A. R. An Axiomatic Basis for Computer Programming // Communications of the ACAI 12(10), 1969. P. 576-580, DOI: 10.1145/363235.363259.

13. Cheung A., Solar-Lezama A., Madden S. Optimizing Database-backed Applications with Query Synthesis // Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2013. PLDI ’13, ACM, New York, NY, USA. P. 3-14, DOL 10.1145/2491956.2462180.

14. Kamil S., Cheung A., Itzhaky S., Solar-Lezama A. Verified Lifting of Stencil Computations // SIGPLAN Not. 2016. 51(6), P. 711-726, DOL 10.1145/2980983.2908117.

15. Radoi C., Fink S. J., Rabbah R., Sridharan M. Translating Imperative Code to MapReduce // Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA T4, 2014. ACM, New York, NY, USA. P. 909-927, DOL 10.1145/2660193.2660228.

16. Ernst M. D., Perkins J.H., Guo P. J., McCamant S., Pacheco C., Tschantz M.S., Xiao C. The Daikon System for Dynamic Detection of Likely Invariants. Sci. Comput. Program. 2007.

17. Srivastava S., Gulwani S. Program Verification Using Templates over Predicate Abstraction // Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, ‘09, 2009. ACM, New York, NY, USA. P. 223-234, DOL 10.1145/1542476.1542501.

Библиографическая ссылка: Симонов В. С., Хайретдинов М. С. Метод преобразования императивного кода для платформ параллельной обработки данных //"Проблемы информатики", 2023, № 3, с. 68-80. DOI: 10.24412/2073-0667-2023-3-68-80.

Main menu

You are here

2023 № 3(60)

Languages