Метод автоматического поиска семейств оптимальных хордальных кольцевых сетей

Метод автоматического поиска семейств оптимальных хордальных кольцевых сетей

Монахова Э. А., Монахов О. Г.
Дискретный анализ и исследование операций, 31, 1, 85–108 (2024)
Скачать статью

УДК 519.176 
DOI: 10.33048/daio.2024.31.780

Аннотация:

Арден и Ли предложили класс хордальных кольцевых сетей степени три в качестве сетей связи мультикомпьютерных систем, получили формулу для вычисления диаметра и алгоритм поиска кратчайших путей для них. В настоящей работе показано, что найденные ими формула диаметра и алгоритм поиска кратчайших путей являются неточными. Нами построен большой массив экспериментальных данных (датасет), содержащий параметры описаний оптимальных по диаметру хордальных колец с числом узлов до 60 тысяч, и найдена точная нижняя граница диаметра хордальных колец. На основе анализа полученного массива данных предложен новый метод и реализованы алгоритмы автоматического поиска аналитических описаний семейств оптимальных хордальных колец, с помощью которых найдены аналитические описания более 500 новых семейств оптимальных хордальных кольцевых сетей для многих значений числа узлов (до этого в литературе были известны шесть семейств). 
Табл. 5, ил. 6, библиогр. 26.

Литература:
  1. Arden B. W., Lee H. Analysis of chordal ring network // IEEE Trans. Comput. 1981. V. C-30, No. 4. P. 291–295.
     
  2. Morillo P., Comellas F., Fiol M. A. The optimization of chordal ring networks // Communication technology. Singapore: World Scientific, 1987. P. 295–299.
     
  3. Yebra J. L. A., Fiol M. A., Morillo P., Alegre I. The diameter of undirected graphs associated to plane tessellations // Ars Comb. 1985. V. 20-B. P. 159–171.
     
  4. Bermond J. C., Comellas F., Hsu D. F. Distributed loop computer-networks: A survey // J. Parallel Distrib. Comput. 1995. V. 24, No. 1. P. 2–10.
     
  5. Hwang F. K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. V. 299, No. 1–3. P. 107–121.
     
  6. Monakhova E. A. A survey on undirected circulant graphs // Discrete Math. Algorithms Appl. 2012. V. 4, No. 1. Paper ID 1250002. 30 p.
     
  7. Pedersen J. M., Riaz M. T., Madsen O. B. Distances in generalized double rings and degree three chordal rings // Parallel and distributed computing and networks. Proc. IASTED Int. Conf. (Innsbruck, Austria, Feb. 15–17, 2005). Calgary: ACTA Press, 2005. P. 153–158.
     
  8. Parhami B. Periodically regular chordal rings are preferable to double-ring networks // J. Interconnect. Netw. 2008. V. 9, No. 1. P. 99–126.
     
  9. Farah R. N., Chien S. L. E., Othman M. Optimum free-table routing in the optimised degree six 3-modified chordal ring network // J. Commun. 2017. V. 12, No. 12. P. 677–682.
     
  10. Hwang F. K., Wright P. E. Survival reliability of some double-loop networks and chordal rings // IEEE Trans. Comput. 1995. V. 44, No. 12. P. 1468–1471.
     
  11. Chen S. K., Hwang F. K., Liu Y. C. Some combinatorial properties of mixed chordal rings // J. Interconnect. Netw. 2003. V. 4, No. 1. P. 3–16.
     
  12. Stojmenović I. Honeycomb networks: Topological properties and communication algorithms // IEEE Trans. Parallel Distrib. Syst. 1997. V. 8. P. 281–305.
     
  13. Ahmad M., Zahid Z., Zavaid M., Bonyah E. Studies of chordal ring networks via double metric dimensions // Math. Probl. Eng. 2022. V. 98. Paper ID 8303242. 7 p.
     
  14. Bujnowski S., Marciniak B., Oyerinde O. O., Lutowski Z., Flizikowski A., Galan S. G. The possibility of equalising the transmission properties of networks described by chordal rings // Proc. 15th Int. Conf. Signal Processing and Communication Systems (Sydney, Australia, Dec. 13–15, 2021). Piscataway: IEEE, 2021. 8 p.
     
  15. Irwan N., Othman M., Farah R. N. Network properties for classes of chordal ring network degree three topologies // 2010 Proc. Int. Conf. Intelligent Network and Computing (Kuala Lumpur, Malaysia, Nov. 26–28, 2010). Piscataway: IEEE, 2010. P. 16–20.
     
  16. Monakhov O. G., Monakhova E. A. A class of parametric regular networks for multicomputer architectures // Comput. Sist. J. 2000. V. 4, No. 2. P. 85–93.
     
  17. Huang H.-C. The diameter-edge invariant property of chordal ring networks: Master Thes. Hsinchu: Natl. Chiao Tung Univ., 2009. 30 p.
     
  18. Loudiki L., Kchkech M., Essaky E. H. A new approach for computing the distance and the diameter in circulant graphs. Ithaca, NY: Cornell Univ., 2022. 14 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2210.11116).
     
  19. Monakhov O. G., Monakhova E. A., Kireev S. E. Parallel generation and analysis of optimal chordal ring networks using Python tools on Kunpeng prosessors // Parallel computing technologies. Proc. 17th Int. Conf. (Astana, Kazakhstan, Aug. 21–25, 2023). Cham: Springer, 2023. P. 126–135. (Lect. Notes Comput. Sci.; V. 14098). 
     
  20. Mollin R. A. Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields // Acta Arithmetica. 1996. V. 74. P. 17–30.
     
  21. Marwan N., Romano M. C., Thiel M., Kurths J. Recurrence plots for the analysis of complex systems // Phys. Rep. 2007. V. 438, No. 5–6. P. 237–329.
     
  22. Barriere L. Symmetry properties of chordal rings of degree 3 // Discrete Appl. Math. 2003. V. 129. P. 211–232. 
     
  23. Lee H. Modeling of multi-microcomputer networks: PhD Thes. Princeton, NJ: Princeton Univ., 1979.
     
  24. Gutierrez J., Riaz T., Pedersen J., Labeaga S., Madsen O. Degree 3 networks topological routing // Image Process. Commun. 2009. V. 14, No. 4. P. 35–48.
     
  25. Gutierrez J., Riaz T., Pedersen J., Labeaga S., Madsen O. On topological routing on degree 3 chordal rings // Proc. 1st Int. Conf. Image Processing & Communications (Bydgoszcz, Poland, Sept. 16–18, 2009). Warsaw: Acad. Publ. House EXIT, 2009. Paper ID 59020255. 8 p.
     
  26. Monakhova E. A., Monakhov O. G., Romanov A. Yu. Routing algorithms in optimal degree four circulant networks based on relative addressing: comparative analysis for networks-on-chip // IEEE Trans. Netw. Sci. Eng. 2023. V. 10, No. 1. P. 413–425.

Исследование выполнено в рамках государственного задания Института вычислительной математики и математической геофизики СО РАН (соглашение № FWNM–2022–0005).

Монахова Эмилия Анатольевна
  1. Институт вычислительной математики и математической геофизики, 
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: emilia@rav.sscc.ru

Монахов Олег Геннадьевич
  1. Институт вычислительной математики и математической геофизики, 
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: monakhov@rav.sscc.ru

Статья поступила 9 августа 2023 г. 
После доработки — 30 августа 2023 г. 
Принята к публикации 22 сентября 2023 г.

Abstract:

Arden and Lee proposed a class of chordal ring networks of degree three as communication networks for multicomputer systems, derived a formula for the diameter, and produced an algorithm for finding the shortest paths for them. In this paper, it is shown that the formula for the diameter and the routing algorithm presented by them are inaccurate. We have obtained a large dataset containing parameters for describing optimal diameter chord rings for all the numbers of nodes up to 60 000 and found the exact lower bound for the diameter of chordal ring networks. A new method is proposed and the algorithms for automatic search for analytical descriptions of families of optimal chordal rings are realized based on an analysis of the database. Using the latter, analytical descriptions of over 500 new families of optimal chordal ring networks for many values of the number of nodes are found (only six families have been known until now in the literature). 
Tab. 5, illustr. 6, bibliogr. 26.

References:
  1. B. W. Arden and H. Lee, Analysis of chordal ring network, IEEE Trans. Comput. C-30 (4), 291–295 (1981).
     
  2. P. Morillo, F. Comellas, and M. A. Fiol, The optimization of chordal ring networks, in Communication Technology (World Scientific, Singapore, 1987), pp. 295–299.
     
  3. J. L. A. Yebra, M. A. Fiol, P. Morillo, and I. Alegre, The diameter of undirected graphs associated to plane tessellations, Ars Comb. 20-B, 159–171 (1985).
     
  4. J. C. Bermond, F. Comellas, and D. F. Hsu, Distributed loop computernetworks: A survey, J. Parallel Distrib. Comput. 24 (1), 2–10 (1995).
     
  5. F. K. Hwang, A survey on multi-loop networks, Theor. Comput. Sci. 299 (1–3), 107–121 (2003).
     
  6. E. A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl. 4 (1), ID 1250002 (2012).
     
  7. J. M. Pedersen, M. T. Riaz, and O. B. Madsen, Distances in generalized double rings and degree three chordal rings, in Parallel and Distributed Computing and Networks, Proc. IASTED Int. Conf. (Innsbruck, Austria, Feb. 15–17, 2005) (ACTA Press, Calgary, 2005), pp. 153–158.
     
  8. B. Parhami, Periodically regular chordal rings are preferable to double-ring networks, J. Interconnect. Netw. 9 (1), 99–126 (2008).
     
  9. R. N. Farah, S. L. E. Chien, and M. Othman, Optimum free-table routing in the optimised degree six 3-modified chordal ring network, J. Commun. 12 (12), 677–682 (2017).
     
  10. F. K. Hwang and P. E. Wright, Survival reliability of some double-loop networks and chordal rings, IEEE Trans. Comput. 44 (12), 1468–1471 (1995).
     
  11. S. K. Chen, F. K. Hwang, and Y. C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnect. Netw. 4 (1), 3–16 (2003).
     
  12. I. Stojmenović, Honeycomb networks: Topological properties and communication algorithms, IEEE Trans. Parallel Distrib. Syst. 8, 281–305 (1997).
     
  13. M. Ahmad, Z. Zahid, M. Zavaid, and E. Bonyah, Studies of chordal ring networks via double metric dimensions, Math. Probl. Eng. 98, ID 8303242 (2022).
     
  14. S. Bujnowski, B. Marciniak, O. O. Oyerinde, Z. Lutowski, A. Flizikowski, and S. G. Galan, The possibility of equalising the transmission properties of networks described by chordal rings, in Proc. 15th Int. Conf. Signal Processing and Communication Systems (Sydney, Australia, Dec. 13–15, 2021) (IEEE, Piscataway, 2021).
     
  15. N. Irwan, M. Othman, and R. N. Farah, Network properties for classes of chordal ring network degree three topologies, in 2010 Proc. Int. Conf. Intelligent Network and Computing (Kuala Lumpur, Malaysia, Nov. 26–28, 2010) (IEEE, Piscataway, 2010), pp. 16–20.
     
  16. O. G. Monakhov and E. A. Monakhova, A class of parametric regular networks for multicomputer architectures, Comput. Sist. J. 4 (2), 85–93 (2000).
     
  17. H.-C. Huang, The diameter-edge invariant property of chordal ring networks, Master Thesis (Natl. Chiao Tung Univ., Hsinchu, 2009).
     
  18. L. Loudiki, M. Kchkech, and E. H. Essaky, A new approach for computing the distance and the diameter in circulant graphs (Cornell Univ., Ithaca, NY, 2022) (Cornell Univ. Libr. e-Print Archive; arXiv:2210.11116).
     
  19. O. G. Monakhov, E. A. Monakhova, and S. E. Kireev, Parallel generation and analysis of optimal chordal ring networks using Python tools on Kunpeng prosessors, in Parallel Computing Technologies, Proc. 17th Int. Conf. (Astana, Kazakhstan, Aug. 21–25, 2023) (Springer, Cham, 2023), pp. 126–135 (Lect. Notes Comput. Sci., Vol. 14098).
     
  20. R. A. Mollin, Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields, Acta Arithmetica 74, 17–30 (1996).
     
  21. N. Marwan, M. C. Romano, M. Thiel, and J. Kurths, Recurrence plots for the analysis of complex systems, Phys. Rep. 438 (5–6), 237–329 (2007).
     
  22. L. Barriere, Symmetry properties of chordal rings of degree 3, Discrete Appl. Math. 129, 211–232 (2003).
     
  23. H. Lee, Modeling of multi-microcomputer networks, PhD Thesis (Princeton Univ., Princeton, NJ, 1979).
     
  24. J. Gutierrez, T. Riaz, J. Pedersen, S. Labeaga, and O. Madsen, Degree 3 networks topological routing, Image Process. Commun. 14 (4), 35–48 (2009).
     
  25. J. Gutierrez, T. Riaz, J. Pedersen, S. Labeaga, and O. Madsen, On topological routing on degree 3 chordal rings, in Proc. 1st Int. Conf. Image Processing & Communications (Bydgoszcz, Poland, Sept. 16–18, 2009) (Acad. Publ. House EXIT, Warsaw, 2009), ID 59020255.
     
  26. E. A. Monakhova, O. G. Monakhov, and A. Yu. Romanov, Routing algorithms in optimal degree four circulant networks based on relative addressing: comparative analysis for networks-on-chip, IEEE Trans. Netw. Sci. Eng. 10 (1), 413–425 (2023).