Graph decomposition for parallel data processing on MISD computer

A conceptually new computing system dealing with multiple instruction stream and single data stream (MISD) is being developed at Bauman Moscow State Technical University. The system contains the hardware to accelerate discrete optimization algorithms. The MISD studies resulted in the conclusion that its effective implementation demands to modify the occurring algorithms and adapt them to the architectural MISD features. However, modification of each sequential algorithm to a required parallel representation is a time-consuming process. So, the development of formal approaches for the automated algorithm transformation is urgent. In the paper the way of MISD algorithm representation as a graph model is proposed. Also, the task of graph decomposition of a sequential program into arithmetic-logic processing graphs and data structure processing graphs has been solved. The representation of the algorithm graph in the R programming language is given.

References

[1] Clements A. Principles of Computer Hardware. OUP Oxford, 2006. 672 p.

[2] Popov A.Yu. Elektronnaya vychislitel’naya mashina s mnogimi potokami komand i odnim potokom dannykh [Computer with Multiple Instruction Streams and Single Data Stream]. Pat. no. 71016. Russian Federation, 2008. Bull. no. 5.

[3] Popov A.Yu. Computer with Hardware Support for Operations on Data Structures. Aerokosmicheskie tekhnologii, 2009. T. 1. Tr. Vtoroy Mezhdunar. nauch.-tekhn. konf., posvyashchennoy 95-letiyu so dnya rozhdeniya akademika V.N. Chelomeya. OAO "VPK "NPO mashinostroeniya" [Aerospace Technologies. Proceedings of the 2nd International scientific and technical conference dedicated to the 95th anniversary of the birth of academician V.N. Chelomey]. MIC "NPO Mashinostroyeniya". Vol. 1. 2009. Bauman MSTU. Moscow, 2012, pp. 296-301 (in Russ.).

[4] Popov A.Yu. Application of Computing Systems with Multiple Instruction Streams and Single Data Stream for Solving Optimization Problems Jelektr. nauchno-tekh. izd. "Inzhenernyy zhurnal: nauka i innovacii" [El. Sc.-Tech. Publ. "Eng. J.: Science and Innovation", 2012, iss. 1. Available at: http://engjournal.ru/catalog/it/hidden/80.html

[5] Popov A.Yu. On the Implementation of the Ford-Fulkerson Algorithm in the Multiple Instructions and Single Data Computer System. Nauka i obrazovanie. MGTU im. N.E. Baumana [Science & Education of the Bauman MSTU. Electronic Journal], 2014, no. 9. Available at: http://technomag.bmstu.ru/doc/726416.html DOI: 10.7463/0914.0726416

[6] Podol’skii V.E. On the Organization of Parallel Operation of Some Algorithms for Finding the Shortest Path on a Graph on a Computer System with Multiple Instruction Stream and Single Data Stream. Nauka i obrazovanie. MGTU im. N.E. Baumana [Science & Education of the Bauman MSTU. Electronic Journal], 2015, no. 4. Available at: http://technomag.bmstu.ru/doc/764268.html DOI: 10.7463/0415.0764268

[7] Ovchinnikov V.A. Grafy v zadachakh analiza i sinteza struktur slozhnykh system [Graphs in problems of analysis and synthesis of complex system structures]. Moscow, MGTU im. N.E. Baumana Publ., 2014. 423 p.

[8] Ovchinnikov V.A., Ivanova G.S. Method for Formal Synthesis of Combined Data Structures for Graph Representation. Jelektr. nauchno-tekh. izd. "Inzhenernyy zhurnal: nauka i innovacii" [El. Sc.-Tech. Publ. "Eng. J.: Science and Innovation", 2012, iss. 1. Available at: http://engjournal.ru/articles/79/79.pdf DOI: 10.18698/2308-6033-2012-1-79

[9] Ovchinnikov V.A., Ivanova G.S. Optimizing Transformations of Algorithms using Properties of Sets, Predicates, and Operations over Them. Vestn. Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2013, no. 4 (93), pp. 53-66 (in Russ.).

[10] Gentleman R., Whalen E., Huber W., Falcon S. Graph: graph: A package to handle graph data structures. R package version 1.44.1. Technical document. May 2015. Available at: http://www.bioconductor.org/packages/release/bioc/manuals/graph/man/graph.pdf (accessed 25.05.2015).

[11] Hansen K.D., Gentry J., Long L., Gentleman R., Falcon S., Hahne F., Sarkar D. Rgraphviz: Provides plotting capabilities for R graph objects. R package version 2.10.0. Technical document. May 2015. Available at: http://mas-ter.bioconductor.org/packages/release/bioc/manuals/Rgraphviz/man/Rgraphviz.pdf (accessed 25.05.2015).