Teragraph Computer Architecture

Abstract

The use of graph models is one of the most promising areas for the development of data analytics and artificial intelligence systems. Research in this field affects not only classical graphs, but also such complex types as hyper- and metagraphs. The scale and complexity of the emerging graph model processing tasks makes it urgent to develop specialized hardware and software tools that increase the efficiency of existing computing systems for this kind of workload. The article discusses the architecture and features of the Teragraf computing complex and cloud platform, designed for processing large-dimensional graphs. The main principle embedded in the architecture of the computing complex is the use of a multi-level associative memory subsystem, which significantly influenced the methodology of development and the features of the functioning of programs. A systematic description of the structure of the hardware and software of the computing complex is given. The main technical solutions that have made it possible to implement large-size associative memory based on addressable DDR4 DRAM memory are presented. The associative address translation for accessing such a drive is implemented on the basis of the trace processing unit of the Leonard Euler microprocessor. It is proposed to further improve the technical means of the subsystem of network interaction based on a bidirectional ring topology and high-speed 100Gb Ethernet lines

Please cite this article in English as:

Popov A.Yu., Ibragimov S.V., Dubrovin E.N., et al. Teragraph computer architecture. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering, 2025, no. 1 (150), pp. 113--136 (in Russ.). EDN: XQZRQE

References

[1] Majeed A., Rauf I. Graph theory: a comprehensive survey about graph theory applications in computer science and social networks. Inventions, 2020, vol. 5, iss. 1, art. 10. DOI: https://doi.org/10.3390/inventions5010010

[2] Mondal B., De K. Overview applications of graph theory in real field. IJSRCSEIT, 2017, vol. 2, no. 5, pp. 751--759.

[3] Popov A.Yu. On the implementation of the Ford-Fulkerson algorithm on the Multiple Instruction and Single Data computer system. Nauka i obrazovanie: nauchnoe izdanie [Science and Education of the BMSTU], 2014, no. 9 (in Russ.). EDN: TDPOMV

[4] Popov A.Yu. The study of Kruskal’s and Prim’s algorithms on the Multiple Instruction and Single Data stream computer system. Nauka i obrazovanie: nauchnoe izdanie [Science and Education of the MSTU], 2015, no. 11 (in Russ.). EDN: VDRHNX

[5] Ibrahim A.H., Abdelhalim M.B., Hussein H., et al. Analysis of x86 instruction set usage for Windows 7 applications. 2nd Int. Conf. on Computer Technology and Development, 2010, pp. 511--516. DOI: https://doi.org/10.1109/ICCTD.2010.5645851

[6] Qian Z., Wei J., Xiang Y., et al. A performance evaluation of DRAM access for in-memory databases. IEEE Access, 2021, vol. 9, pp. 146454--146470. DOI: https://doi.org/10.1109/ACCESS.2021.3123379

[7] Aananthakrishnan S., Ahmed N.K., Cave V., et al. PIUMA: programmable integrated unified memory architecture. arXiv:2010.06277. DOI: https://doi.org/10.48550/arXiv.2010.06277

[8] Aasawat T.K., Reza T., Ripeanu M. How well do CPU, GPU and hybrid graph processing frameworks perform? IEEE IPDPSW, 2018, pp. 458--466. DOI: https://doi.org/10.1109/IPDPSW.2018.00082

[9] Zou Y., Lin M. GridGAS: an I/O-efficient heterogeneous FPGA+CPU computing platform for very large-scale graph analytics. FPT, 2018, pp. 246--249. DOI: https://doi.org/10.1109/FPT.2018.00045

[10] Lumsdaine A., Gregor D.P., Hendrickson B., et al. Challenges in parallel graph processing. Parallel Process. Lett., 2007, vol. 17, no. 1, pp. 5--20. DOI: https://doi.org/10.1142/S0129626407002843

[11] Cormen T.H., Leiserson C.E., Rivest R.L., et al. Introduction to algorithms. MIT Press, 2009.

[12] Ahn J., Hong S., Yoo S., et al. A scalable processing-in-memory accelerator for parallel graph processing. ACM/IEEE 42nd ISCA, 2015, pp. 105--117. DOI: https://doi.org/10.1145/2749469.2750386

[13] Angizi S., Fan D. GraphiDe: a graph processing accelerator leveraging In-DRAM-computing. GLSVLSI ’19, 2019, pp. 45--50. DOI: https://doi.org/10.1145/3299874.3317984

[14] Dysart T., Kogge P., Deneroff M., et al. Highly scalable near memory processing with migrating threads on the emu system architecture. IA3, 2016, pp. 2--9. DOI: https://doi.org/10.1109/IA3.2016.007

[15] Gui C., Zheng L., He B., et al. A survey on graph processing accelerators: chal-lenges and opportunities. J. Comput. Sci. Technol., 2019, vol. 34, no. 2, pp. 339--371. DOI: https://doi.org/10.1007/s11390-019-1914-z

[16] Hennessy J., Patterson D. Domain specific architectures. In: Computer architecture. Elsevier, 2017, pp. 540--606.

[17] Popov A., Ibragimov S., Dubrovin E. Teragraph heterogeneous system for ultra-large graph processing. In: Voevodin V., Sobolev S., Yakobovskiy M., Shagaliev R. (eds). Supercomputing. RuSCDays 2022. Lecture Notes in Computer Science, vol. 13708. Cham, Springer, 2022, pp. 574--590. DOI: https://doi.org/10.1007/978-3-031-22941-1_42

[18] Popov A. An introduction to the MISD technology. Proc. Annual Hawaii Int. Conf. on System Sciences, 2017, pp. 1003--1012.

[19] Popov A.Yu. Principles of the organization of a heterogeneous computing system with a set of commands of discrete mathematics. Informatsionnye tekhnologii [Information Technologies], 2020, vol. 26, no. 2, pp. 67--79 (in Russ.). DOI: https://doi.org/10.17587/it.26.67-79

[20] Popov A.Yu. Application of a heterogeneous computing system with a discrete mathematics instruction set to solve large-scale graphs problems. Informatsionnye tekhnologii [Information Technologies], 2019, vol. 25, no. 11, pp. 682--690 (in Russ.). DOI: https://doi.org/10.17587/it.25.682-690