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

Анатолий Филиппович Задорожный,Виктор Александрович Мелентьев

ПРЕПРИНТ

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

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

А. Ф. Задорожный,

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

2020-04-12

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

Исследуются аспекты топологической совместимости парал-лельных вычислительных систем и задач, предложено и обосновано введение соответствующих показателей, базирующихся на оригинальной топологической модели параллельных вычислений и на нетрадиционном описании графа его проекциями. На примере гиперкубической вычислительной системы (ВС) и задач с кольцевой и звездной информационными топологиями продемонстрировано определение показателей и их использование в сопоставительном анализе применимости интерконнекта с заданной топологией для решения задач с однотипной и разнотипной ему информационными топологиями.

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

Задорожный А. Ф., Мелентьев В. А. 2020. О ТОПОЛОГИЧЕСКОЙ СОВМЕСТИМОСТИ ПАРАЛЛЕЛЬНЫХ ЗАДАЧ И ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. PREPRINTS.RU. https://doi.org/10.24108/preprints-3112026

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

1. Amdahl G.M., Validity of the single-processor approach to achieving large scale computing capabilities. In: AFIPS Conference Proceedings, vol. 30 (Atlantic City, N.J., Apr. 18-20). AFIPS Press, Reston, Va., 1967, pp. 483-485. URL: http://www-inst.eecs.berkeley.edu/~n252/paper/Amdahl.pdf (дата обращения: 22.01.2020)

2. Deng Yuefan, Graph Theory Guided Designs of Interconnection Network Topologies (Stony Brook University, New York, USA, National University of Singapore and National Supercomputer Cen-ter in Jinan, China) URL: https://manualzz.com/doc/9164700/design-of-optimal-interconnection-network-topologies-for-... (дата обращения: 09.04.2020)

3. Dégila J. R., Sanso B. A survey of topologies and performance measures for large-scale networks //IEEE Communications Surveys & Tutorials. – 2004. – Т. 6. – №. 4. – С. 18-31. URL: https://ieeexplore.ieee.org/abstract/document/5342296/ (дата обра-щения: 09.04.2020)

4. V.A. Melent'ev, “Embedding of subsystems limiting length and number of paths between vertexes of computing system graph”, UBS, 47 (2014), 212–246. URL: http://mi.mathnet.ru/eng/ubs749 (дата обращения: 09.04.2020)

5. V.A. Melentiev, "Limit configuring of subsystems in hypercubic computing systems", Journal of Information Technologies and Computing Systems, 2 (2015), 20-30. URL: http://www.jitcs.ru/images/documents/2015-02/20_30.pdf (дата об-ращения: 09.04.2020)

6. V.A. Melentiev, “The limiting paralleling in the computing system with a hypercube topology under length restriction of interpro-cess connections. URL: https://elibrary.ru/item.asp?id=23316608 (дата обращения: 09.04.2020)

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

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

9. Мелентьев В. А. Скобочная форма описания графов и ее использование в структурных исследованиях живучих вычисли-тельных систем // Автометрия. 2000. Т. 38. № 4. С. 36–52.

10. Melent'ev V. A. The bracket Pattern of a Graph //The 6th International Conference on Pattern Recognition and Image Analysis: New Information Technologies, PRIA-6-2002. – 2002. – С. 57-61.

11. Мелентьев В. А. Формальные основы скобочных образов в теории графов //Труды Второй Междунар. конф. Параллельные вычисления и задачи управления PACO – 2004. – С. 694-706.

12. Мелентьев В. А. Проективное описание графа вычислительной системы и его минимизация //Материалы XIII Между-народной научно-технической конференции "ИТ-технологии: развитие и приложения". – 2012. – С. 14-15.

13. Мелентьев В. А. Операции над проекциями графов и актуализация описаний отказоустойчивых систем //Вестник ТГУ. Приложение. – 2006. – №. 17. – С. 208-213.

14. Мелентьев В. А. Формальный подход к исследованию структур вычислительных систем //Вестник Томского госуни-верситета. Приложение. – 2005. – №. 14. – С. 167-172.

15. Мелентьев В. А. Проблемы изоморфизма и толерантности графов в теории отказоустойчивости систем // Труды IV Меж-дународной конференции «Идентификация систем и задачи управления» SICPRO’05. – 2005. – С. 532-549.

16. Мелентьев В. А. Изоморфизм графов и их образов в исследованиях отказоустойчивости систем // Вестник Томского гос-университета. Приложение. – 2005. – №. 14. – С. 182-190.

17. Мелентьев В. А. Поиск вершинных (s, t)-сечений графа вычислительной системы с ограничением по диаметру компонент связности // ПДМ. 2008. №2 (2). URL: https://cyberleninka.ru/article/n/poisk-vershinnyh-s-t-secheniy-grafa-vychislitelnoy-sistemy-s-ogranicheniem-po-diametru-komponent-svyaznosti (дата обращения: 29.03.2020).

18. Мелентьев В. А. Детерминированность структурной отказоустойчивости вычислительной системы размером и диамет-ром компонент связности ее графа //Труды IV Международной конф. «Параллельные вычисления и задачи управления» PACO‘08. – 2008. – С. 250-264.

19. Мелентьев В. А. Метрические характеристики и цикломатика графов вычислительных систем // Материалы XIII Между-народной научно-технической конференции "ИТ-технологии: развитие и приложения", Владикавказ, 2012. – С. 115-130.

20. Мелентьев Виктор Александрович Аналитический подход к синтезу регулярных графов с заданными значениями порядка, степени и обхвата // ПДМ. 2010. №2 (8). URL: https://cyberleninka.ru/article/n/analiticheskiy-podhod-k-sintezu-regulyarnyh-grafov-s-zadannymi-znacheniyami-poryadka-stepeni-i-obhvata (дата обращения: 29.03.2020).

21. Volkova A. A Technical Translation of Melentiev's Graph Rep-resentation Method with Commentary. – 2018. University Honors Theses. Paper 503. URL: https://pdxscholar.library.pdx.edu/honorstheses/503 (дата обраще-ния: 29.03.2020).

22. Мелентьев Виктор Александрович Компактные структуры вычислительных систем и их синтез // УБС. 2011. №32. URL: https://cyberleninka.ru/article/n/kompaktnye-struktury-vychislitelnyh-sistem-i-ih-sintez (дата обращения: 29.03.2020).

23. Мелентьев Виктор Александрович Ограничения на обхваты в компактных графах // ПДМ. Приложение. 2011. №4. URL: https://cyberleninka.ru/article/n/ogranicheniya-na-obhvaty-v-kompaktnyh-grafah (дата обращения: 29.03.2020).

24. Мелентьев Виктор Александрович Компактные графы и детермини-рованный алгоритм их синтеза // ПДМ. Приложе-ние. 2011. №4. URL: https://cyberleninka.ru/article/n/kompaktnye-grafy-i-determinirovannyy-algoritm-ih-sinteza (дата обращения: 29.03.2020).

25. Мелентьев В. А. Метрика, цикломатика и синтез топологии систем и сетей связи // Труды шестой Международной кофе-ренции « ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ PACO'2012», – 2012. – С. 10-25.

26. Melent'ev V. A. About topological compactness of computing systems //ISJ Theoretical & Applied Science. – 2014. – V. 11. – №. 19. – С. 59-65. doi: http://dx.doi.org/10.15863/TAS.2014.11.19.12

27. Мелентьев В. А. Обобщенная модель отказоустойчивой системы // Вестник Томского госуниверситета. – 2007. – №. 23. – С. 242-246.

28. Мелентьев Виктор Александрович Аналитический подход к синтезу регулярных структур отказоустойчивых систем // ПДМ. Приложение. 2010. №3. URL: https://cyberleninka.ru/article/n/analiticheskiy-podhod-k-sintezu-regulyarnyh-struktur-otkazoustoychivyh-sistem (дата обращения: 29.03.2020).

29. Мелентьев В. А. Моделирование систем, устойчивых к отказам заданной кратности //Труды VII Международной конфе-ренции «Иденти-фикация систем и задачи управления» SICPRO. – 2008. – Т. 8. – С. 1210-1223.

30. Melent'ev V. A. FAULT-TOLERANCE OF HYPERCUBIC AND COMPACT TOPOLOGY OF COMPUTING SYSTEMS //ISJ Theoretical & Applied Science. – 2016. – V. 12. – №. 44. – С. 98-105.

31. Melent'ev V. A. Author's approach to the topological modeling of parallel computing systems //arXiv preprint arXiv:2003.10092. – 2020.

32. Мелентьев В. А. Авторский подход к топологическому моделированию параллельных вычислительных систем // PREPRINTS.RU. http://dx.doi.org/10.24108/preprints-3112009.

33. Melent'ev V. A. About topological modeling of parallel systems and tasks // Scientific research of the SCO countries: synergy and integration. – 2019. Part 2: Participants’ reports in English. P. 184-192.

34. Melent'ev V. A., Shubin V. I. , Zadorozhny A. F. Topological scalability of hypercubic parallel systems and tasks. //ISJ Theoretical & Applied Science. –2015. –V. 11 – №. 31. P. 122-129. Doi: http://dx.doi.org/10.15863/TAS.2015.11.31.19

35. Корнюшко В.Ф., Богунова И.В., Флид А.А., Николаева О.М., Гребенщиков А.А. ИНФОРМАЦИОННО-АЛГОРИТМИЧЕСКАЯ ПОДДЕРЖКА РАЗРАБОТКИ ТВЕРДЫХ ЛЕКАРСТВЕННЫХ ФОРМ. Тонкие химические техно-логии. 2018;13(5):73-81. https://doi.org/10.32362/2410-6593-2018-13-5-73-81

36. Sumin V. I. et al. Determining the reliability of network infor-mation systems //Journal of Physics: Conference Series. – IOP Pub-lishing, 2019. – Т. 1203. – №. 1. – С. 012083.

37. Громов Ю. Ю. и др. АНАЛИЗ НАДЕЖНОСТИ В СЕТЕВЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ //Вестник Воро-нежского института ФСИН России. – 2018. – №. 1. – С. 33-41.

38. Елисеев А. И. и др. Оценка надёжности сетецентрических структур //Механизация строительства. – 2017. – Т. 78. – №. 2. – С. 59-62.

39. Елисеев А. И. и др. Контроль состояния надёжности и безопасности сетевой информационной структуры на основе алго-ритма разрезания скобочной проекции графа //Информация и безопасность. – 2015. – Т. 18. – №. 3. – С. 424-427.

40. Мелентьев Виктор Александрович О топологической отказоустойчивости масштабируемых вычислительных систем // УБС. 2017. №70. URL: https://cyberleninka.ru/article/n/o-topologicheskoy-otkazoustoychivosti-masshtabiruemyh-vychislitelnyh-sistem (дата обращения: 03.04.2020).

41. Mills W. H. Some complete cycles on the n-cube //Proceedings of the American Mathematical Society. – 1963. – Т. 14. – №. 4. – С. 640 643. https://dx.doi.org/10.2307%2F2034292

42. Schmeichel E., Mitchem J. Bipartite graphs with cycles of all even lengths //Journal of Graph Theory. – 1982. – Т. 6. – №. 4. – С. 429-439. https://doi.org/10.1002/jgt.3190060407.

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

44. V.A. Melent'ev Use of Melentiev’s graph representation method for detection of cliques and the analysis of topologies of computing systems //ISJ Theoretical & Applied Science. –2018. –V. 12 – №. 68. P. 201-211. DOI: https://dx.doi.org/10.15863/TAS.2018.12.68.28.

ПРЕПРИНТ

ИНФОРМАЦИЯ