Merging Control-flow and Dataflow Architectures on a Single Chip

  • Nenad Korolija School of Electrical Engineering, University of Belgrade, Serbia
  • Svetlana Štrbac-Savić Academy of Technical and Art Applied Studies Belgrade, Serbia https://orcid.org/
DOI: https://doi.org/10.5937/jcfs3-49392
Keywords: dataflow, control-flow, GPU, high performance computing

Abstract


 

Computing power rises predominantly by increasing the number of cores of modern processors, and the number of cores in cluster and cloud architectures. Along with increasing the processing power, high performance computing requirements also rise. Vast of the computing infrastructure includes control-flow processors that are based on von Neumann paradigm. In contrary, the principle of dataflow architectures is based on the data flowing through the already configured hardware. Dataflow architectures are often implemented using FPGAs. Recent research has proposed hybrid architectures, where both control-flow and dataflow hardware would exist on the same chip die. In this article, a new hybrid control-flow and dataflow architecture is proposed, where control-flow hardware would be similar to modern graphical cards, consisting of thousands of cores, but with a reasonable small amount of dataflow hardware available on each GPU core. The proposed architecture is tested by analyzing the conjugate gradient method executed on both control-flow and dataflow hardware. The execution of a the algorithm is divided onto GPU cores, and the execution of repeated instructions on each GPU core is delegated to the assigned dataflow hardware. Results indicate that it is possible to accelerate the execution of algorithms using the proposed architecture.

 

Author Biography

Nenad Korolija, School of Electrical Engineering, University of Belgrade, Serbia

 

 

References

[1] I. I. Arikpo, F. U. Ogban, and I. E. Eteng: Von neumann architecture and modern computers. Global Journal of Mathematical Sciences, 6(2), 97-103 (2007).
[2] V. Milutinović, J. Salom, N. Trifunović, and R. Giorgi: Guide to dataflow supercomputing. Springer Nature, 10, 978-3 (2015).
[3] M. J. Flynn, O. Mencer, V. Milutinovic, G. Rakocevic, P. Stenstrom, R. Trobec, and M. Valero: Moving from petaflops to petadata. Communications of the ACM, 56(5), 39-42 (2013).
[4] V. Milutinović, B. Furht, Z. Obradović, and N. Korolija: Advances in high performance computing and related issues. Mathematical problems in engineering (2016).
[5] N. Korolija, T. Djukic, V. Milutinovic, and N. Filipovic: Accelerating Lattice-Boltzman Method using Maxeler DataFlow Approach. Transactions on Internet Research, 9(2), 5-10 (July 2013).
[6] S. Stojanovic, D. Bojic, and V. Milutinovic: Solving Gross Pitaevskii Equation using Dataflow Paradigm. Transactions on Internet Research, 9(2), (July 2013).
[7] A. Kos, V. Rankovic, and S. Tomazic: Sorting Networks on Maxeler Dataflow Supercomputing Systems. Advances in Computers, 96, 139-186. Amsterdam, Elsevier, Academic Press (2015).
[8] I. Stanojevic, V. Senk, and V. Milutinovic: Application of Maxeler Dataflow Supercomputing to Spherical Code Design. Transactions on Internet Research, 9(2), 1-4 (July 2013).
[9] N. Bezanic, J. Popovic-Bozovic, V. Milutinovic, and I. Popovic: Implementation of the RSA Algorithm on a DataFlow Architecture. Transactions on Internet Research, 9(2), 11-16 (July 2013).
[10] J. Popovic, D. Bojic, and N. Korolija: Analysis of task effort estimation accuracy based on use case point size. IET Software, 9(6), 166-173 (2015).
[11] N. Korolija and A. Zamuda: On Cloud-Supported Web-Based Integrated Development Environment for Programming DataFlow Architectures. In Exploring the DataFlow Supercomputing Paradigm, New York: Springer Cham, pp. 41‒51 (2019).
[12] N. Korolija, J. Popović, M. Cvetanović, and M. Bojović: Dataflow-based parallelization of control-flow algorithms. Advances in computers, 104:73-124, Elsevier (2017).
[13] V. Milutinovic, J. Salom, D. Veljovic, N. Korolija, D. Markovic, and L. Petrovic: Transforming applications from the control flow to the dataflow paradigm. Dataflow Supercomputing Essentials, New York: Springer Cham, 107‒129 (2017).
[14] N. Trifunovic, V. Milutinovic, N. Korolija, and G. Gaydadjiev: An AppGallery for dataflow computing. Journal of Big Data, 3(1), 1-30 (2016).
[15] N. Trifunovic, B. Perovic, P. Trifunovic, Z. Babovic, and A. R. Hurson: A novel infrastructure for synergistic dataflow research, development, education, and deployment: the Maxeler AppGallery project. Advances in Computers, Elsevier, 106:167-213 (2017).
[16] V. Milutinovic, J. Salom, D. Veljovic, N. Korolija, D. Markovic, and L. Petrovic: Maxeler AppGallery Revisited. DataFlow Supercomputing Essentials: Research, Development and Education, 3-18 (2017).
[17] R. Trobec et al.: Interconnection networks in petascale computer systems: A survey. ACM Computing Surveys (CSUR), 49(3), 1-24 (2016).
[18] V. Milutinovic, M. Tomasevic, B. Markovi, and M. Tremblay: A new cache architecture concept: the split temporal/spatial cache. Proceedings of 8th mediterranean electrotechnical conference on industrial applications in power systems, computer science and telecommunications (MELECON 96). Vol. 2. IEEE (1996).
[19] V. Milutinovic, B. Markovic, M. Tomasevic, and M. Tremblay: The split temporal/spatial cache: A complexity analysis, In Proceedings of the SCIzzL, Vol. 6, pp. 89-96 (September 1996).
[20] F. Yazdanpanah, C. Alvarez-Martinez, D. Jimenez-Gonzalez, and Y. Etsion: Hybrid dataflow/von-Neumann architectures. IEEE Transactions on Parallel and Distributed Systems, 25(6), 1489-1509 (2013).
[21] D. Miladinović, M. Bojović, V. Jelisavčić, and N. Korolija: Hybrid Manycore Dataflow Processor, Proceedings, IX International Conference IcETRAN, Novi Pazar, Serbia, June 6 – 9 (2022).
[22] V. Milutinović et al., The ultimate dataflow for ultimate supercomputers-on-a-chip, for scientific computing, geo physics, complex mathematics, and information processing. 10th Mediterranean Conference on Embedded Computing, IEEE, pp. 1-6 (June 2021).
[23] V. Milutinović, M. Kotlar, I. Ratković, N. Korolija, M. Djordjevic, K. Yoshimoto, and M. Valero: The Ultimate Data Flow for Ultimate Super Computers-on-a-Chip. Handbook of Research on Methodologies and Applications of Supercomputing, IGI Global, 312-318 (2021).
[24] J. Popović, V. Jelisavčić, and N. Korolija: Hybrid Supercomputing Architectures for Artificial Intelligence: Analysis of Potentials. In 1st Serbian International Conference on Applied Artificial Intelligence (SICAAI), Kragujevac, Serbia (2022).
[25] V. Milutinović, N. Trifunović, N. Korolija, J. Popović, and D. Bojić: Accelerating program execution using hybrid control flow and dataflow architectures. In 2017 25th Telecommunication Forum (TELFOR), pp. 1-4, IEEE (November 2017).
[26] Z. Babović, B. Bajat, V. Đokić, F. Đorđević, D. Drašković, N. Filipović, et al.: Research in computing-intensive simulations for nature-oriented civil-engineering and related scientific fields, using machine learning and big data: an overview of open problems. Journal of Big Data, 10(1), 1-21 (2023).
[27] Z. Babović, B. Bajat, D. Barac, V. Bengin, V. Đokić, F. Đorđević, et al.: Teaching computing for complex problems in civil engineering and geosciences using big data and machine learning: synergizing four different computing paradigms and four different management domains. Journal of Big Data, 10(1), 89 (2023).
[28] L. Egharevba, S. Kumar, H. Amini, M. Adjouadi, and N. Rishe: Detecting and Removing Clouds Affected Regions from Satellite Images Using Deep Learning. IPSI Bgd Transactions on Internet Research, 19(2), 13-23 (July 2023).
[29] N. Korolija, D. Bojić, A. R. Hurson, and V. Milutinovic: A runtime job scheduling algorithm for cluster architectures with dataflow accelerators. Advances in computers, Elsevier, 126 (2022).
[30] K. Milfeld and N. Korolija: Towards hybrid supercomputing architectures. Journal of Computer and Forensic Sciences, 1(1), 47-54 (2022).
[31] M. Popović, N. Korolija, and S. Štrbac-Savić: Hybrid control-flow and dataflow processor: algorithm granularity analysis. In Zbornik 29. konferencije YUINFO (2023).
[32] K. Huang, Y. Liu, N. Korolija, J. M. Carulli, and Y. Makris: Recycled IC detection based on statistical methods. IEEE transactions on computer-aided design of integrated circuits and systems, 34(6), 947-960 (2015).
[33] K. Huang, Y. Liu, N. Korolija, J. M. Carulli, and Y. Makris.: Statistical Methods for Detecting Recycled Electronics: From ICs to PCBs and Beyond. IEEE Design & Test. (2023).
[34] V. Blagojević, D. Bojić, M. Bojović, M. Cvetanović, J. Đorđević, Đ. Đurđević, et al.: A systematic approach to generation of new ideas for PhD research in computing. Advances in computers. 104, 1-31. Elsevier (2017).
[35] T. Lebailly, Conjugate gradient algorithm implementation:
https://github.com/tileb1/CG-CUDA/blob/master/sequential.c, visited on February 16th, 2024.
Published
2024/04/10
Issue
Vol. 3 No. 1 (2024): Journal of Computer and Forensic Sciences
Section
Članci

I (we), the author(s), hereby declare under full moral, financial and criminal liability that the manuscript submitted for publication to the Journal of Computer and Forensic Sciences

a) is the result of my (our) own original research and that I (we) hold the right to publish it;

b) does not infringe any copyright or other third-party proprietary rights;

c) complies with the Journal’s research and publishing ethics standards;

d) has not been published elsewhere, under this or any other title;

e) is not under consideration by another publication, under this or any other title.

I (we) also declare under full moral, financial and criminal liability:

f) that all conflicts of interest that may directly or potentially influence or impart bias on the work have been disclosed in the manuscript;

g) that if the article has been accepted for publishing I (we) will transfer all copyright ownership of the manuscript to the University of Criminal Investigation and Police Studies in Belgrade.

Signed by the Corresponding Author on behalf of the all other authors.