Authors:
Victor A. Melent'ev,DOI NO:
https://doi.org/10.26782/jmcms.spl.8/2020.04.00017Keywords:
Interconnect topology,parallel computation systems,projective description of graphs,topological scalability ,fault-tolerance functions,Abstract
The paper summarizes the author’s research of topologies of parallel computation systems and the tasks solved with them, including the relevant tools of their modeling. The original topological model of such systems is presented, based on the modified Amdahl’s law. It allowed formalizing the dependence of the necessary number of processors and the maximal distance between informational adjacent nodes in the graph on directive values of acceleration or efficiency. The dependences of these values on the topology of the system interconnection and on the informational graph of the parallel task are also formalized. The tools for comparative evaluation of these dependences, the topological criteria and the functions of scaling and fault-tolerant functioning of parallel systems are based on the author’s technique of projective description of graph and the algorithms using it.Refference:
I. Xian-He Sun, Yong Chen. Reevaluating Amdahl’s law in the multicore era, Journal of Parallel and Distributed Computing, Volume 70, Issue 2 (2010) 183–188. ISSN 0743-7315. https://doi.org/10.1016/j.jpdc.2009.05.002 (accessed 20 June 2019).
II. Abd-El-Barr, M., Gebali, F. Reliability analysis and fault tolerance for hypercube multi-computer networks, Information Sciences, Volume 276 (2014) 295–318. ISSN 0020-0255. https://doi.org/10.1016/j.ins.2013.10.031 (accessed 20 June 2019).
III. Caselli, S., Conte, G., Malavolta, U. Topology and process interaction in concurrent architectures: A GSPN modeling approach, Journal of Parallel and Distributed Computing, Volume 15, Issue 3 (1992) 270–281. ISSN 0743-7315. https://doi.org/10.1016/0743-7315(92)90008-B (accessed 20 June 2019).
IV. Chechina, N., Huiqing Li, Ghaffari, A., Thompson, S., Trinder, Ph. Improving the network scalability of Erlang, Journal of Parallel and Distributed Computing, Volumes 90–91 (2016). 22–34. ISSN 0743-7315. https://doi.org/10.1016/j.jpdc.2016.01.002 (accessed 20 June 2019).
V. Das, Ch. R., Bhuyan, L. N. Dependability evaluation of interconnection networks, Information Sciences, Volume 43, Issues 1–2 (1987) 107–138. ISSN 0020-0255. https://doi.org/10.1016/0020-0255(87)90033-8 (accessed 20 June 2019).
VI. Dutt, Sh., Hayes, J. P. Designing fault-tolerant systems using automorphisms, Journal of Parallel and Distributed Computing, Volume 12, Issue 3 (1991) 249–268. ISSN 0743-7315. https://doi.org/10.1016/0743-7315(91)90129-W (accessed 20 June 2019).
VII. Emmert-Streib, F., Dehmer, M.,Yongtang Shi. Fifty years of graph matching, network alignment and network comparison, Information Sciences, Volumes 346–347 (2016) 180–197. ISSN 0020-0255. https://doi.org/10.1016/j.ins.2016.01.074 (accessed 20 June 2019).
VIII. Grout, V. M., Sanders, P. W. Communication network optimization, Computer Communications, Volume 11, Issue 5 (1988) 281–287. ISSN 0140-3664. https://doi.org/10.1016/0140-3664(88)90039-4 (accessed 20 June 2019).
IX. HaoChe, Minh Nguyen. Amdahl’s law for multithreaded multicore processors, Journal of Parallel and Distributed Computing, Volume 74, Issue 10 (2014) 3056–3069. ISSN 0743-7315. https://doi.org/10.1016/j.jpdc.2014.06.012 (accessed 20 June 2019).
X. Hayter, Th., Brookes, G. R. Approach to the simulation of various LAN topologies, Computer Communications, Volume 12, Issue 4 (1989) 204–212.
ISSN 0140-3664, https://doi.org/10.1016/0140-3664(89)90197-7 (accessed 20 June 2019).
XI. Hutchison, D., Sterbenz, J. P.G. Architecture and design for resilient networked systems, Computer Communications, Volume 131 (2018) 13–21. ISSN 0140-3664. https://doi.org/10.1016/j.comcom.2018.07.028 (accessed 20 June 2019).
XII. Jianxi Fan, XiaohuaJia, Xin Liu, Shukui Zhang, Jia Yu. Efficient unicast in bijective connection networks with the restricted faulty node set, Information Sciences, Volume 181, Issue 11 (2011) 2303–2315. ISSN 0020-0255. https://doi.org/10.1016/j.ins.2010.12.011 (accessed 20 June 2019).
XIII. Jianxi Fan, XiaohuaJia. Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences, Volume 178, Issue 2 (2008) 340–351. ISSN 0020-0255. https://doi.org/10.1016/j.ins.2007.08.012 (accessed 20 June 2019).
XIV. Ke Huang, Jie Wu. Fault-tolerant resource placement in balanced hypercubes, Information Sciences, Volume 99, Issues 3–4 (1997) 159–172. ISSN 0020-0255. https://doi.org/10.1016/S0020-0255(96)00270-8 (accessed 20 June 2019).
XV. Kornushk, V. F., Bogunova, I. V., Flid, A. A., Nikolaeva, O. M., Grebenshchikov, A. A. Information-algorithmic support for development of solid pharmaceutical form. Fine Chemical Technologies, 13(5) (2018) 73–81. https://doi.org/10.32362/2410-6593-2018-13-5-73-81 (accessed 20 June 2019).
XVI. Levi, G., Luccio, F. A technique for graph embedding with constraints on node and arc correspondences, Information Sciences, Volume 5 (1973) 1-24. ISSN 0020-0255. https://doi.org/10.1016/0020-0255(73)90001-7 (accessed 20 June 2019).
XVII. Lloret, J., Palau, C., Boronat, F., Tomas, J. Improving networks using group-based topologies, Computer Communications, Volume 31, Issue 14 (2008) 3438–3450. ISSN 0140-3664. https://doi.org/10.1016/j.comcom.2008.05.030 (accessed 20 June 2019).
XVIII. Melent’ev ,V.A., Shubin, V.I., Zadorozhny, A.F. Topological scalability of hypercubic parallel systems and tasks. ISJ Theoretical & Applied Science 11 (31) (2015) 122–129. Doi: http://dx.doi.org/10.15863/TAS.2015.11.31.19 (accessed 20 June 2019).
XIX. Melent’ev, V. A. An analytical approach to the synthesis of regular graphs with preset values of the order, degree and girth, Prikl. Diskr. Mat., 2(8), (2010) 74–86. http://mi.mathnet.ru/eng/pdm178 (accessed 20 June 2019).
XX. Melent’ev, V. A. Bracket form of the graph description and its use in the structural investigations of enduring computer systems, Avtometriya, 4 (2000) 36–51. https://elibrary.ru/item.asp?id=14954075 (accessed 20 June 2019).
XXI. Melent’ev, V. A. Embedding of subsystems limiting length and number of paths between vertexes of computing system graph, UBS, 47 (2014) 212–246. http://mi.mathnet.ru/eng/ubs749 (accessed 20 June 2019).
XXII. Melent’ev, V. A. Fault-tolerance of hypercubic and compact topology of computing systems. ISJ Theoretical & Applied Science, 12 (44) (2016) 98–105. Doi: http://dx.doi.org/10.15863/TAS.2016.12.44.20 (accessed 20 June 2019).
XXIII. Melent’ev, V. A. On approach to the configuring of fault-tolerant subsystems in case of scarce topological fault-tolerance of the computing system. ISJ Theoretical & Applied Science, 10 (54) (2017) 101–105. Doi: https://dx.doi.org/10.15863/TAS.2017.10.54.20 (accessed 20 June 2019).
XXIV. Melent’ev, V. A. On topological fault-tolerance of scalable computing systems, UBS, 70 (2017) 58–86. URL: https://doi.org/10.25728/ubs.2017.70.3 (accessed 20 June 2019).
XXV. Melent’ev, V. A. On topological scalability of computing systems, UBS, 58 (2015) 115–143. http://mi.mathnet.ru/eng/ubs844 (accessed 20 June 2019).
XXVI. Melent’ev, V. A. The metric, cyclomatic and synthesis of topology of systems and networks (2012). https://elibrary.ru/download/elibrary_22249411_42044045.pdf (accessed 20 June 2019).
XXVII. Melent’ev, V. A. Use of Melentiev’s graph representation method for identification and enumeration of circuits of the given length. ISJ Theoretical & Applied Science, 11 (67) (2018) 85–91. Doi: https://dx.doi.org/10.15863/TAS.2018.11.67.16 (accessed 20 June 2019).
XXVIII. Melent’ev, V. A. Use of Melentiev’s graph representation method for detection of cliques and the analysis of topologies of computing systems. ISJ Theoretical & Applied Science, 12 (68), (2018) 201–211. Doi: https://dx.doi.org/10.15863/TAS.2018.12.68.28 (accessed 20 June 2019).
XXIX. Melentiev, V. A. Formalnyeosnovyskobochnyhobrazov v teoriigrafov [Formal bases of bracket images in graph theory]. 2nd International Conference “Parallel computations andy management tasks” PACO’2004: In-t problem upravleniya RAN im. V.A. Trapeznikova, (2004) 694–706.
XXX. Melentiev, V. A. Formalnyypodkhod k issledovaniyustrukturvychislitelnykh system [Formal approach to researching the structures of computation systems]. VestnikTomskogogosudarstvennogo universiteta,14 (2005) 167–172.
XXXI. Melentiev, V. A. The bracket pattern of a graph. 6th International Conference on Pattern Recognition and Image Analysis: New Information Technologies, PRIA-6-2002, October 21-26 (2002) Proceedings, Velikiy Novgorod, Russian Federation, 57–61.
XXXII. Melentiev, V. A. The limiting paralleling in the computing system with a hypercube topology under length restriction of interprocess connections. https://elibrary.ru/item.asp?id=23316608 (accessed 20 June 2019).
XXXIII. Melentiev, V. A., Limit configuring of subsystems in hypercubic computing systems, Journal of Information Technologies and Computing Systems, 2 (2015) 20–30. http://www.jitcs.ru/images/documents/2015-02/20_30.pdf (accessed 20 June 2019).
XXXIV. Melentiev, V. Edge scaling of computing systems, UBS, 64 (2016) 81–11. http://mi.mathnet.ru/eng/ubs898 (accessed 20 June 2019).
XXXV. Nutaro, J., Zeigler, B. How to apply Amdahl’s law to multithreaded multicore processors, Journal of Parallel and Distributed Computing, Volume 107 (2017) 1–2. ISSN 0743-7315. https://doi.org/10.1016/j.jpdc.2017.03.006 (accessed 20 June 2019).
XXXVI. Subharthi, P., Jianli Pan, Raj Jain. Architectures for the future networks and the next generation Internet: A survey, Computer Communications, Volume 34, Issue 1 (2011) 2–42. ISSN 0140-3664. https://doi.org/10.1016/j.comcom.2010.08.001 (accessed 20 June 2019).
XXXVII. Volkova, A. A Technical Translation of Melentiev’s Graph Representation Method with Commentary. University Honors Theses. Paper 503 (2018). http://dx.doi.org/10.15760/honors.507 (accessed 20 June 2019).
XXXVIII. Wu A. Y. Embedding of tree networks into hypercubes, Journal of Parallel and Distributed Computing, Volume 2, Issue 3 (1985) 238–249. ISSN 0743-7315, https://doi.org/10.1016/0743-7315(85)90026-7 (accessed 20 June 2019).
XXXIX. Xian-He Sun, Yong Chen. Reevaluating Amdahl’s law in the multicore era, Journal of Parallel and Distributed Computing, Volume 70, Issue 2 (2010) 183–188. ISSN 0743-7315. https://doi.org/10.1016/j.jpdc.2009.05.002 (accessed 20 June 2019).
XL. Yavits, L., Morad, A., Ginosar, R. The effect of communication and synchronization on Amdahl’s law in multicore systems, Parallel Computing, Volume 40, Issue 1 (2014) 1–16. ISSN 0167-8191. https://doi.org/10.1016/j.parco.2013.11.001 (accessed 20 June 2019).