АВТОРСКИЙ ПОДХОД К ТОПОЛОГИЧЕСКОМУ МОДЕЛИРОВАНИЮ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Виктор Александрович Мелентьев

ПРЕПРИНТ

Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.

АВТОРСКИЙ ПОДХОД К ТОПОЛОГИЧЕСКОМУ МОДЕЛИРОВАНИЮ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

В. А. Мелентьев

2020-03-19

https://doi.org/10.24108/preprints-3112009

Работа обобщает исследования Автора в части топологий параллельных вычислительных систем и решаемых на них задач, включая соответствующие инструменты их моделирования. Представлена оригинальная топологическая модель таких систем, основанная на модифицированном в работе законе Амдала – это позволило формализовать зависимость необходимого числа процессоров и предельного расстояния между информационно смежными вершинами в графе системы от директивных значений ускорения или эффективности. Зависимости этих величин от топологии интерконнекта системы и от информационного графа параллельной задачи также формализованы. Инструментарий сопоставительной оценки этих зависимостей, топологические критерии и функции масштабирования и отказоустойчивого функционирования параллельных систем основаны на авторском методе проективного описания графов и на использующих его алгоритмах.

Ссылка для цитирования:

Мелентьев В. А. 2020. АВТОРСКИЙ ПОДХОД К ТОПОЛОГИЧЕСКОМУ МОДЕЛИРОВАНИЮ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. PREPRINTS.RU. https://doi.org/10.24108/preprints-3112009

Список литературы

1. Angela Y Wu, Embedding of tree networks into hypercubes, Journal of Parallel and Distributed Computing, Volume 2, Issue 3, 1985, Pages 238-249, ISSN 0743-7315, https://doi.org/10.1016/0743-7315(85)90026-7.

2. Thomas Hayter, Graham R Brookes, Approach to the simulation of various LAN topologies, Computer Communications, Volume 12, Issue 4, 1989, Pages 204-212, https://doi.org/10.1016/0140-3664(89)90197-7.

3. Stefano Caselli, Gianni Conte, Ugo Malavolta, Topology and process interaction in concurrent architectures: A GSPN modeling approach, Journal of Parallel and Distributed Computing, Volume 15, Issue 3, 1992, Pages 270-281, ISSN 0743-7315, https://doi.org/10.1016/0743-7315(92)90008-B.

4. Jaime Lloret, Carlos Palau, Fernando Boronat, Jesus Tomas, Improving networks using group-based topologies, Computer Communications, Volume 31, Issue 14, 2008, Pages 3438-3450, ISSN 0140-3664, https://doi.org/10.1016/j.comcom.2008.05.030.

5. Mostafa Abd-El-Barr, Fayez Gebali, Reliability analysis and fault tolerance for hypercube multi-computer networks, Information Sciences, Volume 276, 2014, Pages 295-318, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2013.10.031.

6. Frank Emmert-Streib, Matthias Dehmer, Yongtang Shi, Fifty years of graph matching, network alignment and network comparison, Information Sciences, Volumes 346–347, 2016, Pages 180-197, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2016.01.074.

7. Chita R. Das, Laxmi N. Bhuyan, Dependability evaluation of interconnection networks, Information Sciences, Volume 43, Issues 1–2, 1987, Pages 107-138, ISSN 0020-0255, https://doi.org/10.1016/0020-0255(87)90033-8.

8. Ke Huang, Jie Wu, Fault-tolerant resource placement in balanced hypercubes, Information Sciences, Volume 99, Issues 3–4, 1997, Pages 159-172, ISSN 0020-0255, https://doi.org/10.1016/S0020-0255(96)00270-8.

9. Jianxi Fan, Xiaohua Jia, 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, Pages 2303-2315, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2010.12.011.

10. Natalia Chechina, Huiqing Li, Amir Ghaffari, Simon Thompson, Phil Trinder, Improving the network scalability of Erlang, Journal of Parallel and Distributed Computing, Volumes 90–91, 2016, Pages 22-34, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2016.01.002.

11. David Hutchison, James P.G. Sterbenz, Architecture and design for resilient networked systems, Computer Communications, Volume 131, 2018, Pages 13-21, ISSN 0140-3664, https://doi.org/10.1016/j.comcom.2018.07.028.

12. Giorgio Levi, Fabrizio Luccio, A technique for graph embedding with constraints on node and arc correspondences, Information Sciences, Volume 5, 1973, Pages 1-24, ISSN 0020-0255, https://doi.org/10.1016/0020-0255(73)90001-7.

13. VM Grout, PW Sanders, Communication network optimization, Computer Communications, Volume 11, Issue 5, 1988, Pages 281-287, ISSN 0140-3664, https://doi.org/10.1016/0140-3664(88)90039-4.

14. Shantanu Dutt, John P. Hayes, Designing fault-tolerant systems using automorphisms, Journal of Parallel and Distributed Computing, Volume 12, Issue 3, 1991, Pages 249-268, ISSN 0743-7315, https://doi.org/10.1016/0743-7315(91)90129-W.

15. Jianxi Fan, Xiaohua Jia, Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences, Volume 178, Issue 2, 2008, Pages 340-351, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2007.08.012.

16. Subharthi Paul, Jianli Pan, Raj Jain, Architectures for the future networks and the next generation Internet: A survey, Computer Communications, Volume 34, Issue 1, 2011, Pages 2-42, ISSN 0140-3664, https://doi.org/10.1016/j.comcom.2010.08.001.

17. Xian-He Sun, Yong Chen, Reevaluating Amdahl’s law in the multicore era, Journal of Parallel and Distributed Computing, Volume 70, Issue 2, 2010, Pages 183-188, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2009.05.002.

18. Hao Che, Minh Nguyen, Amdahl’s law for multithreaded multicore processors, Journal of Parallel and Distributed Computing, Volume 74, Issue 10, 2014, Pages 3056-3069, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2014.06.012.

19. L. Yavits, A. Morad, R. Ginosar, The effect of communication and synchronization on Amdahl’s law in multicore systems, Parallel Computing, Volume 40, Issue 1, 2014, Pages 1-16, ISSN 0167-8191, https://doi.org/10.1016/j.parco.2013.11.001.

20. James Nutaro, Bernard Zeigler, How to apply Amdahl’s law to multithreaded multicore processors, Journal of Parallel and Distributed Computing, Volume 107, 2017, Pages 1-2, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2017.03.006.

21. V.A. Melent'ev, “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.

22. V.A. Melent'ev, “On topological scalability of computing systems”, UBS, 58 (2015), 115–143. http://mi.mathnet.ru/eng/ubs844.

23. Xian-He Sun, Yong Chen, Reevaluating Amdahl’s law in the multicore era, Journal of Parallel and Distributed Computing, Volume 70, Issue 2, 2010, Pages 183-188, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2009.05.002.

24. L. Yavits, A. Morad, R. Ginosar, The effect of communication and synchronization on Amdahl’s law in multicore systems, Parallel Computing, Volume 40, Issue 1, 2014, Pages 1-16, ISSN 0167-8191, https://doi.org/10.1016/j.parco.2013.11.001.

25. Hao Che, Minh Nguyen, Amdahl’s law for multithreaded multicore processors, Journal of Parallel and Distributed Computing, Volume 74, Issue 10, 2014, Pages 3056-3069, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2014.06.012.

26. James Nutaro, Bernard Zeigler, How to apply Amdahl’s law to multithreaded multicore processors, Journal of Parallel and Distributed Computing, Volume 107, 2017, Pages 1-2, ISSN 0743-7315, https://doi.org/10.1016/j.jpdc.2017.03.006.

27. Melent'ev VA, Shubin VI, Zadorozhny AF (2015) Topological scalability of hypercubic parallel systems and tasks. ISJ Theoretical & Applied Science 11 (31): 122-129. Doi: http://dx.doi.org/10.15863/TAS.2015.11.31.19.

28. V. Melentiev, “Edge scaling of computing systems”, UBS, 64 (2016), 81–11. http://mi.mathnet.ru/eng/ubs898.

29. V. A. Melent'ev, “On topological fault-tolerance of scalable computing systems”, UBS, 70 (2017), 58–86. URL: https://doi.org/10.25728/ubs.2017.70.3

30. Melent'ev VA (2016) Fault-tolerance of hypercubic and compact topology of computing systems. ISJ Theoretical & Applied Science, 12 (44): 98-105. Doi: http://dx.doi.org/10.15863/TAS.2016.12.44.20.

31. Melent'ev VA (2017) 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): 101-105. Doi: https://dx.doi.org/10.15863/TAS.2017.10.54.20.

32. V.A. Melent'ev, “Bracket form of the graph description and its use in the structural investigations of enduring computer systems”, Avtometrija, 4 (2000), 36-51. https://elibrary.ru/item.asp?id=14954075.

33. 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. 2018; 13(5): 73-81. https://doi.org/10.32362/2410-6593-2018-13-5-73-81.

34. V.A. Melentiev 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.

35. Melentiev VA (2004) Formalnye osnovy skobochnyh obrazov v teorii grafov. Trudy II Mezhdunarodnoj konferentsii "Parallelnyie vychisleniya i zadachi upravleniya" PACO'2004: In-t problem upravleniya RAN im. V.A. Trapeznikova, pp. 694-706. In-t problem upravleniya RAN im. V.A. Trapeznikova, pp. 694-706.

36. Melentiev VA (2005) Formalnyj podhod k issledovaniyu struktur vychislitelnyh sistem. Vestnik Tomskogo gosudarstvennogo universiteta. No.14, pp. 167-172.

37. V.A. Melent'ev, The metric, cyclomatic and synthesis of topology of systems and networks (2012) https://elibrary.ru/download/elibrary_22249411_42044045.pdf.

38. V. A. Melent'ev, “An analytical approach to the synthesis of regular graphs with preset values of the order, degree and girth”, Prikl. Diskr. Mat., 2010, no. 2(8), 74–86. http://mi.mathnet.ru/eng/pdm178.

39. Volkova, Asya, “A Technical Translation of Melentiev's Graph Representation Method with Commentary” (2018). University Honors Theses. Paper 503. http://dx.doi.org/10.15760/honors.507.

40. V. A. Melent'ev, “On topological fault-tolerance of scalable computing systems”, UBS, 70 (2017), 58–86. URL: https://doi.org/10.25728/ubs.2017.70.3

41. Melent'ev VA (2016) Fault-tolerance of hypercubic and compact topology of computing systems. ISJ Theoretical & Applied Science, 12 (44): 98-105. Doi: http://dx.doi.org/10.15863/TAS.2016.12.44.20.

42. Melent'ev, V. A. (2018). Use of Melentiev’s graph representation method for identification and enumeration of circuits of the given length. ISJ Theoretical & Applied Science, 11 (67), 85-91. Doi: https://dx.doi.org/10.15863/TAS.2018.11.67.16

43. V.A. Melentiev, "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.

44. V.A. Melentiev, “The limiting paralleling in the computing system with a hypercube topology under length restriction of interprocess connections. https://elibrary.ru/item.asp?id=23316608.

45. V. A. Melent'ev, “Compact structures of computer systems and their synthesis”, UBS, 32 (2011), 241–261. http://mi.mathnet.ru/eng/ubs536.

46. Melent'ev VA (2014) About topological compactness of computing systems. ISJ Theoretical & Applied Science 11 (19): 59-65. http://dx.doi.org/10.15863/TAS.2014.11.19.12

47. Melent'ev, V. A. (2018). 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), 201-211. Doi: https://dx.doi.org/10.15863/TAS.2018.12.68.28.

ПРЕПРИНТ

ИНФОРМАЦИЯ