Volume 3(60)

CONTENTS

Bredikhin S. K, Scherbakova N. G. Scientific journal co-authorship network model
Gerb A.R., Omarova G.A. Graph partitioning algorithms: literature review
Snytnikova T. V. Processing-in-Memory: current trends in the development of technology
Malyshkin V.E., Perepelkin V. A. A Multi-Agent Approach to Improve Execution Efficiency of Fragmented Programs in LuNA System
Simonov V. S., Khairetdinov M. S. Imperative code conversion method for parallel data processing platforms

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

SCIENTIFIC JOURNAL CO-AUTHORSHIP NETWORK MODEL

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

EDN: QADKBW

The traditional representation of a complex system (CS) in the form of a network or a graph makes it possible to identify many aspects of the system’s behavior, see [2-4]. The network is based on pairwise relationships between network objects. In this case, the nodes of the co-authorship network correspond to the authors, and the edge between the nodes is constructed if there is at least one publication in which both authors participated, see the fundamental works [5, 6]. Such a model is able to express many complex properties of CS, its advantage lies in its simplicity and the ability to use graph theory in the analysis. The model has been studied quite well in terms of the distribution of degrees of network nodes [5], ranking of authors [6], dynamics of evolution [7, 8], identification of communities [9], and prediction of new co-author relations [10, 11].

However, this CS modeling does not reveal all the information that can be extracted directly from the list of articles and their authors, for example, does not reflect the total number of articles prepared by co-authors. To overcome this shortcoming, several methods for constructing networks of co-authorship, extending the traditional approach, were considered, see [6, 12]. But fixing only binary relations between system objects excludes interaction involving groups of network objects. A possible solution to the problem is to generalize the pair interaction to the interaction of an arbitrary set of nodes. In this case, the networks are called hypernetworks. The main mathematical structures used as a CS model include bipartite graphs, hypergraphs, and simplicial complexes [13].

The concept of a hypergraph [20] was proposed in [21] as applied to the analysis of CSs and providing a computationally feasible tool that can be adapted to many analytical situations. In the study of co-authorship, as a rule, the nodes corresponding to the authors form a hyperedge in the case of a joint publication [22, 23].

This paper presents a co-authorship network model that takes into account group relationships that arise between co-authors. The network is modeled using a hypergraph whose vertices correspond to authors and whose edges correspond to scientific articles (SA). The data we analyze is extracted from the electronic archive (https://www.dia-endojournals.ru/jour/issue/arcliive) of the quarterly scientific and practical medical peer-reviewed journal Diabetes Mellitus (ISSN 2072-0378), published since 1998. The journal is indexed in the international abstract and full-text databases. The hypergraph Hca, built on the basis of the selected archive data, lias size m(Hca) = 991 and order n(Hca) = 1694. Since only those SAs that have two or more authors are considered, there are no loops in the constructed hypergraph. The hypergraph Hca is not connected, it consists of 97 components, of which 68 components have one edge, the maximum component includes about 64.75 % vertices (authors) and 67.4% edges (articles).

The parameters of the hypergraph (and its components) are measured and its topological properties (simple, star, strong star, conformal, Helly) are revealed. The use of the hypergraph language allows to

get an idea of the shape of cooperation in the system under consideration. Most of the authors of the co-authored journal articles are indirectly related to each other due to the presence of joint works. The vertex degree distributions (the maximal component) have a long tail, i.e. most authors have a small number of joint SAs. The same can be said about the distribution of edge degrees, indicating that most SAs have a small number of co-authors. All components, except for the maximal, have one or another considered property. Moreover, the properties of conformity and Helly are common to all components, regardless of size and order. The property of simplicity is more characteristic of components with a small number of edges, the same can be said about the probability of being a star. Two components have all the considered properties.

It should be noted that based on the incidence matrix of a hypergraph, a traditional network of co-authorship can be built, in which two authors are connected if they have at least one joint work. The associated multigraph G(Hca) is one of the models of such a network in which the weight of an edge between two authors is equal to the number of joint works. This work continues the study and approbation of methods for analyzing networks of co-authorship, see [1].

Key words: complex network, hypergraph, co-authorship, archive of scientific articles, bibliometry.

This work was carried out under state contract with ICMMG SB RAS (0251-2021-0005).

References

1. BREDIKHIN S. V., LYAPUNOV V. M., SCHERBAKOVA N. G. The hypernetwork of scientifc co-authorship. DB RePEc data analysis // Problemy informatiki. 2022. №4. S. 70-83. DOI: 10.24412/2073¬0667-2022-4-70-83.

2. NEWMAN M. E. J. Networks: An introduction. Oxford Univ. Press, 2010. ISBN: 9780199206650.

3. ESTRADA E. 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 co-authorship network // Scientometrics. 2012. V. 90, No 2. P. 687-699. DOI: 10.1007/sl 1192-011-0511-x.

9. SAVIC M., IVANOVIC M., RADOVANOVIC M., 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. DOL 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. DOL 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. DOL 10.1007/slll92-006-0113-l.

13. SCHERBAKOVA N. G. Modeling group interactions of complex systems. Review // Problemy informatiki. 2022. .№.3. S. 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. DOI: 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. DOI: 10.1007/978- 3-540-39432-7_2.

19. BANERJEE S., JENAMANI M., PRATHAR D. K. Properties of a projected network of a bipartite network // arXiv:1707.00912vl. DOI: 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. H. From cohomology in physics to q-connectivity in social science // Intern. J. Man-Machine Studies. 1972. V. 4, iss. 2. P. 139-167. DOL 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. DOL 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. DOL 10.1016/S0020-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. DOL 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. CORMEN T. H., LEISERSON C., RIVEST R. L. Algoritmy: postroenie i analiz. M.: MTSNMO, 2002. ISBN: 978-5-907114-11-1.

Bibliographic reference: Bredikhin S. K, Scherbakova N. G. Scientific journal co-authorship network model //journal “Problems of informatics”. 2023, № 3. P.5-18. DOI:10.24412/2073-0667-2023-3-5-18.

article

A.R. Gerb*. G.A. Omarova**

Novosibirsk State University, 630090, Novosibirsk, Russia

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

GRAPH PARTITIONING ALGORITHMS: LITERATURE REVIEW

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

EDN: LXQVVD

This paper is devoted to the analysis of modern graph partitioning algorithms. We observe exact solutions, sequential, iterative, multilevel, streaming and parallel algorithms and note advantages and disadvantages of some algorithms.

Key words: graphs, coarsening, serial and parallel algorithms, optimization.

The work was supported by the Ministry of Science and Higher Education of the Russian Federation (project code 0251-2020-0001).

References

1. Itogi tretego kvartala 2022 goda soteseti Vkontakte. [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. Geri M., Johnson D. Vychislitelnye mashiny i trudnoreshaemye zadachi. M.: Mir, 1982.

9. Armbruster M. 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. E., 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. Gerb A. R., Omarova G. A. Primenenie teorii grafov v algebraicheskikh mnogosetochnykh metodakh dlia resheniia razrezhennykh SLAU // Probl. inform. 2022. № 3. S. 77-89.

21. Akhremtsev Y., Sanders P., Schulz C. 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., Saarbriicken, 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 М. А. К., Garg S., Kang В. 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. Е., 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., Sporevik 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. DOI: 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., Qatalytirek U. V. Heuristics for symmetric rectilinear matrix partitioning. arXiv preprint arXiv: 1909.12209. 2019.

Bibliographic reference: Gerb A.R., Omarova G.A. Graph partitioning algorithms: literature review //journal “Problems of informatics”. 2023, № 3. P.19-36. DOI:10.24412/2073-0667-2023-3-19-36.

article

T.V. Snytnikova

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

PROCESSING-IN-MEMORY: CURRENT TRENDS IN THE DEVELOPMENT OF TECHNOLOGY

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

EDN: FSPSXV

Moving data between the CPU and RAM is a first-order obstacle to improved performance, scalability, and energy efficiency in today’s systems. Computer systems use a number of methods to reduce the overhead associated with data movement, ranging from traditional mechanisms to new methods such as Processing-in-Memory (PIM) computation. These methods can be divided into two large areas: processing-near-memory (PNM), where computations are performed in dedicated processing elements, and processing-using-memory (PUM), where computations are performed inside a memory array by exploiting the internal analog operating properties of the memory device. This paper discusses the paradigm of PIM architectures and provides an overview of PUM architectures based on parallel DRAM operations and associative processors.

Key words: processing-in-memory, associative processors, PDRAM.

References

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 О. 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 H. B., Hong. S. K. 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. Snytnykova T. V. Razvitie assotciativnykh parallelnykh arhitektur // Problemy informatiki. 2019. No 2. S. 36-50.

44. Martyshkin, A. I. Spetcializirovannyi apparatnyi modul assotciativnogo soprotcessora na baze PLIS dlia vychislitelnykh sistem s izmeniaemoi strukturoi / A. I. Martyshkin, A. N. Perekusihina // XXI vek: itogi proshlogo i problemy nastoiashchego plius, 2019, T. 8, № 3(47), S. 42-50.

45. Bondarenko M. F., Hahanov V. L, Leetvinova E. I. Struktura logicheskogo assotciativnogo multiprotcessora // Avtomatika i telemehanika, 2012, № 10, S. 71-92.

46. Guyduk S. i dr. Sfericheskii multiprotcessor PRUS dlia resheniia bulevykh uravnenii // Radioelektronika i informatika, 2004, №4 (29). S. 69-78.

47. Yantir H. E. 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 H. 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. Snytneykova T. V., Nepomniashchaia A. Sh. Reshenie zadach na grafakh s pomoshchiu STAR- mashiny, realizuemoi na graficheskikh uskoriteliakh // Pricladnaia diskretnaia matematika. 2016. T. 3(33). S. 98-115.

53. Snytneykova T. V. Realizatciia modeli assotciativnykh vychislenii na GPU:biblioteka bazovykh protcedur iazyka STAR // Vychislitelnye metody i programmirovanie. Novye vychislitelnye tekhnologii. 2018. T. 19. S. 85-95.

Bibliographic reference: Snytnikova T. V. Processing-in-Memory: current trends in the development of technology //journal “Problems of informatics”. 2023, № 3. P.37-54. DOI:10.24412/2073-0667-2023-3-37-54.

article

V. E. Malyshkin, V.A. Perepelkin

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

Novosibirsk State University, 630090, Novosibirsk, Russia

Novosibirsk State Technical University, 630073, Novosibirsk, Russia

A MULTI-AGENT APPROACH TO IMPROVE EXECUTION EFFICIENCY OF FRAGMENTED PROGRAMS IN LUNA SYSTEM

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

EDN: LYEAKS

Development of efficient numerical parallel programs is an complex and laborious problem which impedes application of supercomputers to perform numerical simulations. Parallel programs construction languages and systems are of help by providing to a user a high-level language to describe a desired parallel program and generating the program automatically. The systems do not only reduce complexity of parallel programs development, but also provide static and/or dynamic adaptation of the program execution to particular hardware and execution conditions (e.g. workload balancing). This implies that a high-level parallel program specification may be transformed into a parallel program in diverse ways, many of which may be optimal for particular simulation. Such diversity can either be resolved statically or dynamically, the former causing less run-time overhead, while the latter preserves the ability to dynamically tune parallel program execution. Finding a good trade-off between static and dynamic decision making is a challenging problem in system parallel programming, which also depends on the computational model on which the system is based.

LuNA system [1] is a system for automatic construction of numerical parallel programs, which is being developed in ICMMG SB RAS. It is based on the theory of parallel programs synthesis based on the computational models [2] and follows the active knowledge concept [3]. Its input language LuNA comprises means to describe pieces of data and computations, called data and computational fragments correspondingly (DFs and CFs). DFs are immutable coarse-grained data objects, while CFs are side-effect free sequential procedure calls on particular DFs as input or output arguments. Such dataflow computational model allows the system to automatically execute CFs on a distributed memory machine either by generating a conventional distributed program which performs procedures invocation according to the information dependencies, or by dynamically interpreting the program on a multicomputer. The former approach lacks dynamic flexibility while the latter approach causes significant overhead.

In order to achieve a trade-off between those two options a multi-agent approach is suggested. For that a multi-agent system is defined, where each agent implements a single CF in a distributed environment, which allows an agent to consume and produce DFs and to create new agents. Each agent is controlled by an imperative sequential program in a conventional language (C++ to be specific).

This work was carried out under state contract with ICMMG SB RAS 0251-2022-0005.

The environment system supports agents with basic operations, such as storing a DF, migrating a CF to another computing node, etc. Usage of the C++ language to formulate agent programs is beneficial in sense that it is compiled into a highly efficient machine code using conventional C++ compiler. Such approach allows to make decisions on how to execute LuNA programs both statically (by generating corresponding behavior into agents’ programs) and dynamically (by adding dynamic properties support modules into run-time environment and making agents’ behavior depend on that modules). For example, distribution of agents to computing nodes may either be static (in this case each agent will have a particular computing node to migrate to for execution) or dynamic (in this case each agent will request a dynamic balancing module to assign a node to migrate to).

The proposed approach showed to be much more efficient than a naive distributed interpretation approach which is confirmed by works [4-5]. The fragmented structure of the program is preserved in run-time, which makes it possible to provide dynamic properties of LuNA-program execution. The efficiency achieved in practical cases appeared to be comparable with that of manual low-level programming, which makes LuNA system usable for automating construction of real numerical parallel programs at least in some application domains. The proposed approach takes advantage of well- developed tools for conventional sequential compilation to reduce the run-time overhead.

Key words: Fragmented programming, LuNA system, parallel programs construction automation, high performance computing, multi-agents approach, partial evaluation.

References

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. Sintez parallelnykh programm i sistem na vychislitelnykh modelyah / Valkovsky V. A., Malyshkin V. E. Novosibirsk: Nauka. 1988. 126 p. (In Russian)

3. Malyshkin V. E. Tekhnologiya fragmentirovannogo programmirovaniya // Vestnik YuUrGU. Seriya: Vychislitelnaya matematika i informatika. 2023. N 46(305). (In Russian)

4. Malyshkin V. E. 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. Lebedev D.V., Perepelkin V. A. Chislennoe reshenie odnomernody kraevoy zadachi filtracii zhidkosti dlya sistemy “neft-voda” i ее realizaciya v sisteme fragmentirovannogo programmirovaniya LuNA // Vestnik Kazahskogo nacionalnogo universiteta im. al-Farabi, seriya “matematika, mehanika, invormatica”. N 3 (82). 2014. S. 64-73 (In Russian).

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. Lebedev D. V., Perepelkin V. A. Reshenie trekhmernogo modelnogo uravneniya teploprovodnosti v sisteme fragmentirovannogo programmirovaniya LuNA // Parallelnye vychislitelnye tekhnologii (PaVT’2016): trydy mezhdunarodnoy nauchnoy konferencii (28 marta - 1 aprelya 2016 g., g. Arkhangelsk). Chelyabinsk: Izdatelskiy centr YuUrGU, 2016. S. 784 (In Russian).

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/sll227-016-1780-l.

9. Malyshkin V. Е., 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. DOI: 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/sl1227-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. DOI: 10.1007/978-3-030-25636-4_l.

12. Kudryavtsev A. A., Malyshkin V.E., Nushtayev Yu. Yu., Perepelkin V.A., Spirin V. A. Effektivnaya fragmentirovannaya realizatsiya kraevoy zadachi filtratsii dvuhfaznoy zhidkosti // Problemy Informatiki. 2023. N 2. S. 45-73. DOI: 10.24412/2073-0667-2023-2-45-73. (In Russian)

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.

Bibliographic reference: Malyshkin V.E., Perepelkin V. A. A Multi-Agent Approach to Improve Execution Efficiency of Fragmented Programs in LuNA System //journal “Problems of informatics”. 2023, № 3. P.55-67. DOI:10.24412/2073-0667-2023-3-55-67.

article

V. S. Simonov*. M.S. Kllaiгetdinov*,**

* Novosibirsk State Technical University, 630087, Novosibirsk, Russia

"Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

IMPERATIVE CODE CONVERSION METHOD FOR PARALLEL DATA PROCESSING PLATFORMS

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

EDN: HGORYY

There are many data processing platforms that allow sequential programs to access parallel processing capabilities. To benefit from the advantages of such platforms, existing code has to be rewritten into domain-specific languages that each platform supports. This transformation, a tedious and error—prone process, also requires developers to choose the right platform that optimizes performance based on a specific workload.

This article describes a formal method, the result of which on imperative code is code suitable for execution in a parallel data processing system, for example, Hadoop, implementing the MapReduce paradigm. Given a sequential code fragment, a method is used to output a high-level summary expressed in our the language of the program specification, which is then compiled for execution in Apache Spark [1]. We demonstrate that the method allows you to convert imperative code into suitable for execution on the Apache Spark platform. Translated results are executed 1.3 times faster on average than sequential implementations, and also scale better for large datasets.

As computing becomes more ubiquitous, storage becomes cheaper, and data collection tools become more sophisticated, more data is being collected today than ever before. Data-driven advances are becoming increasingly common in various scientific fields. Thus, efficient analysis and processing of huge data sets is a huge computational task.

For processing very large data sets, many parallel data processing platforms have been developed [1-5], and new ones continue to be developed [5-7]. Most parallel data processing frameworks come with domain-specific optimizations , which are provided either through the library application programming interface (API) [1-4, 6, 7], or using a high-level domain-specific language: domain-specific language (DSL), so that users can express their calculations [5, 8]. Calculations expressed using such API or DSL calls are more efficient due to the optimization of platforms for a specific domain [8-11].

However, many of the problems associated with this approach often make frameworks related to a specific subject area inaccessible to non-specialists, such as researchers studying physical or social sciences. First, domain-specific optimization for various workloads requires an expert to determine in advance the most appropriate structure for a given piece of code. Secondly, end users often have to learn new APIs or DSLs [1-3, 6, 7, 12] and transform existing code to take advantage of the advantages provided by some platforms. This requires not only considerable time and resources, but is also fraught with errors in the code. Moreover, even users who want to transform their applications must first understand the purpose of the code that could have been written by others, and manually written low-level optimizations in the code often hide high-level intentions. Finally, even after learning new APIs and rewriting code, newly emerging frameworks often turn newly written code into outdated

applications. Users then have to repeat this process in order to keep up with new advances, which requires considerable time, which would be better spent on promoting scientific discoveries.

One way to improve the availability of parallel data processing platforms involves creating compilers that automatically convert applications written in common general-purpose languages (such as C, Java or Python) into high-performance parallel processing applications such as Hadoop or Spark. These compilers allow users to write their applications in familiar general-purpose languages and allow the compiler to reassign parts of their code to high-performance DSL [13-15]. Then applications can use the performance of these specialized frameworks without the additional cost of learning to program individual DSLs. But such compilers do not exist for all cases, and their creation can be very difficult.

Key words: imperative code, parallel data processing.

References

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. PLDI’13, 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 C. A. R. An Axiomatic Basis for Computer Programming // Communications of the ACM 12(10), 1969. P. 576-580, DOL 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 T3, 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 ’14, 2014. ACM, New York, NY, USA. P. 909-927, DOL 10.1145/2660193.2660228.

16. Ernst М. D., Perkins J.H., Guo Р. 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, DOI: 10.1145/1542476.1542501

Bibliographic reference: Simonov V. S., Khairetdinov M. S. Imperative code conversion method for parallel data processing platforms //journal “Problems of informatics”. 2023, № 3. P.68-80. DOI:10.24412/2073-0667-2023-3-68-80.

article

Main menu

You are here

Volume 3(60)