СПОСОБИ СИНТЕЗУ ТОПОЛОГІЧНИХ ОРГАНІЗАЦІЙ НА ОСНОВІ КОДОВИХ ПЕРЕТВОРЕНЬ ДЕ БРУЙНА
DOI:
https://doi.org/10.25140/2411-5363-2020-4(22)-131-143%20Ключові слова:
граф де Бруйна; топологія; відмовостійкістьАнотація
Актуальність теми дослідження. На сьогодні такі топологічні організації, як дерева (tree), жирні дерева (fat tree), 3D-mesh, 6D-tor, DragonFly використовуються як спосіб мережевої організації в центрах обробки даних. Усі ці топології мають відмовостійкі властивості внаслідок наявності декількох альтернативних шляхів маршрутизації. Тому актуальною є задача розробки нових топологій, які будуть мати багато збалансованих маршрутів (one cost path). Одним із кращих варіантів для досліджень покращення топології дерева є комбінація з графами де Бруйна в різних системах числення, що дозволяє варіювати ступенем вершин, діаметром та кількістю альтернативних шляхів для маршрутизації. У статті пропонується використати новий спосіб, який дозволяє отримати задані характеристики при об’єднанні топологій на основі дерев з графом на основі кодових перетворень де Бруйна.
Постановка проблеми. При створенні високопродуктивних обчислювальних систем важливою є завчасна розробка їх топологічних організацій, яка дозволяє вчасно передбачити характеристики системи.
Аналіз останніх досліджень і публікацій. На цей час існує низка робіт, присвячених топологіям, що засновані на послідовності де Бруйна. Існує детальний огляд синтезу гібридних топологій на основі графів де Бруйна та гіперкуба.
Виділення недосліджених частин загальної проблеми. Не розглянутою на цей час залишається можливість використання гібридних топологій на основі дебруйнівських послідовностей та різних типів дерев.
Постановка завдання. Завданнями є розробка способу синтезу нових топологій на основі дерев і дебруйнівських послідовностей та аналізу характеристик синтезованих топологічних організацій для різних рівнів відмовостійкості.
Виклад основного матеріалу. Описано синтез п’яти топологій на основі дерев і дебруйнівських послідовностей. Проведено порівняльний аналіз усіх синтезованих топологій.
Висновки відповідно до статті. Виконано аналіз характеристик, виділено основні переваги та недоліки запропонованих топологічних структур, висунуто пропозиції щодо їх покращення.
Посилання
Alverson R., Duncan Roweth, Larry Kaplan. The gemini system interconnect. 2010 18th IEEE Symposium on High Performance Interconnects. 2010. Рp. 83-87.
Kim John, Wiliam J. Dally, Steve Scott, and Dennis Abts. Technology-driven, highly-scalable dragonfly topology. 2008 International Symposium on Computer Architecture. 2008. Рp. 77-88.
Ajima, Yuichiro, Shinji Sumimoto, and Toshiyuki Shimizu. Tofu: A 6D mesh/torus interconnect for exascale computers. Computer. 2009. № 11. Рр. 36-40.
Guan K. C., Chan V. W. S. Cost-efficient fiber connection topology design for metropolitan area WDM networks. OSA Journal of Optical Communications and Networking. 2009. Т. 1, № 1. С. 158-175.
Ganesan Elango, Dhiraj K. Pradhan. The hyper-debruijn networks: Scalable versatile architecture. IEEE Transactions on parallel and distributed systems. 1993. № 4.9. Рр. 962-978.
Dürr F. (2016). A Flat and Scalable Data Center Network Topology Based on De Bruijn Graphs. arXiv preprint arXiv:1610.03245.
Kamal, Md Sarwar, et al. De-Bruijn graph with MapReduce framework towards metagenomic data classification. International Journal of Information Technology. 2017. № 9.1. Рр. 59-75.
Peng G., Ji P., Zhao F. A novel codon-based de Bruijn graph algorithm for gene construction from unassembled transcriptomes. Genome Biol. 2016. № 17. Рр. 232. URL: https://doi.org/10.1186/ s13059-016-1094-x.
Olexandr G., Rehida P., Volokyta A., Loutskii H., Thinh V.D. Routing Method Based on the Excess Code for Fault Tolerant Clusters with InfiniBand. Advances in Computer Science for Engineering and Education II. ICCSEEA 2019. Advances in Intelligent Systems and Computing. 2020. Vol. 938. Springer, Cham.
Honcharenko O., Volokyta A., Loutskii H. Fault-tolerant topologies synthesis based on excess code usign the latin square. The International Conference on Security, Fault Tolerance, Intelligence ICSFTI2019, Ukraine, Kyiv, 14-15 May, 2019. Kyiv, 2019. Рp. 72-81.
Loutskii H., Volokyta A., Rehida P.,Goncharenko O. Using excess code to design fault-tolerant topologies. Technical sciences and technologies. 2019. № 1(15). Рр. 134–144. DOI: https://dx.doi.org/ DOI: 10.25140/2411-5363-2019-1(15)-134-144.
Loutskii H., Volokyta A., Rehida P., Honcharenko O., Thinh V. D. Method for Synthesis Scalable Fault-Tolerant Multi-level Topological Organizations Based on Excess Code. Advances in Computer Science for Engineering and Education III. ICCSEEA 2020. Advances in Intelligent Systems and Computing / Hu Z., Petoukhov S., Dychka I., He M. (eds.). 2020. Vol. 1247. Springer, Cham. https://doi.org/10.1007/978-3-030-55506-1_32.
Loutskii H., Volokyta A., Rehida P., Honcharenko O., Ivanishchev B., Kaplunov A. Increasing the fault tolerance of distributed systems for the Hyper de Bruijn topology with excess code. 2019 IEEE International Conference on Advanced Trends in Information Theory (ATIT). Kyiv, 2019. Рp.1-6. DOI: 10.1109/ATIT49449.2019.9030487.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
