Самомаршрутизируемая неблокируемая системная сеть с прямыми каналами: сложность и быстродействие

Самомаршрутизируемая неблокируемая системная сеть с прямыми каналами: сложность и быстродействие

Автор: Подлазов Виктор Сергеевич

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение для супер ЭВМ

Статья в выпуске: 4 (55) т.13, 2022 года.

Бесплатный доступ

Разработана неблокируемая самомаршрутизируемая сеть с прямыми каналами, в которой конфликты пакетов разрешаются на входе в сеть посредством процедуры борьбы источников за вход в первый каскад сети, обеспечивая пакетную дуальность. Заблокированные при борьбе пакеты повторно передаются источниками с минимальными задержками. Дуальность подразумевает совместное использование шинного (с разведением во времени) и мультиплексного (с разведением по каналам) способов разрешения конфликтов пакетов. Внутри сети возникновение конфликтов предупреждается посредством ее внутреннего распараллеливания, т.е. созданием заведомо бесконфликтных путей. Сеть разработана в 2-, 4-, и 8-каскадном вариантах с масштабированием числа каналов от нескольких сот до многих миллионов при неизменном быстродействии сети. В сети возможно обеспечение 1-, или 2-канальной отказоустойчивости при сохранении ее быстродействия. Накладными затратами на достижение указанных свойств является повышенная сложность сети, которая сопоставима со сложностью теоретического неблокируемого коммутатора Клоза. Хотя его структура известна, но практическая реализация отсутствует вследствие неизвестности процедуры параллельной самомаршрутизации в нем. Практическая ориентация предложенных сетей - это системные сети с передачей маршрутной информации в заголовках пакетов с однократным использованием в каждом каскаде управляющей маршрутной информации для базового полного коммутатора. Предложенные сети выполнены в расширенном схемном базисе, состоящем из полных коммутаторов и отдельных мультиплексоров и демультиплексоров. В работе представлены характеристики построенных сетей при указанном способе представления маршрутной информации.

Еще

Полный коммутатор, дуальный коммутатор, пакетная дуальность, мультиплексоры и демультиплексоры, многокаскадный коммутатор, бесконфликтная самомаршрутизация, неблокируемый коммутатор, статическая самомаршрутизация, квазиполный орграф, квазиполный граф, инвариантное расширение сетей, коммутационные свойства, прямые каналы, масштабируемость и быстродействие

Еще

Короткий адрес: https://sciup.org/143179418

IDR: 143179418   |   УДК: 004.724.2   |   DOI: 10.25209/2079-3316-2022-13-4-47-76

Multichannel non-blocking system area network with direct channels

An unblockable non-blocking self-routing network with direct channels has been developed, in which packet conflicts are resolved at the entrance to the network by the procedure of connecting sources to the first cascade of the network , providing a packet duality. Packets blocked during conflict resolution are retransmitted by sources with minimal delays. Within the network, the occurrence of conflicts is prevented by means of parallelization of the network itself. The network is designed in 2-, 4- and 8-stage versions with scaling of the number of channels from several hundred to many millions, keeping the same network performance. The network can provide 1- or 2-channel fault tolerance at the same link rate. The overhead cost of achieving these properties is higher complexity of the network, that becomes comparable to the complexity of the theoretical non-blocking Clos switch, which has no known practical implementation.The purpose of the proposed networks is photonic networks with routing information transmission in packet headers represented as one-time-use binary numbers. The proposed networks are made in an extended circuit basis, consisting of switches and separate multiplexers and demultiplexers. The paper presents the characteristics of the constructed networks with the specified method of presenting routing information.

Еще

Список литературы Самомаршрутизируемая неблокируемая системная сеть с прямыми каналами: сложность и быстродействие

  • Барабанова Е. А., Вытовтов К. А., Подлазов В. С. Неблокируемые отказоустойчивые двухкаскадные дуальные фотонные коммутаторы // Проблемы управления.– 2021.– №4.– с. 82–92. https://doi.org/10.25728/pu.2021.4.7
  • В. С. Подлазов Неблокируемые отказоустойчивые дуальные фотонные коммутаторы широкой масштабируемости // Пробл. управл.– 2021.– №5.– с. 70–87. https://doi.org/10.25728/pu.2021.5.6
  • Stepanenko S. Structure and Implementation Principles of a Photonic Computer // EPJ Web of Conferences.– 2019.– Vol. 224.– 04002.– 7 pp. https://doi.org/10.1051/epjconf/201922404002
  • Каравай М. Ф., Подлазов В. С. Метод инвариантного расширения системных сетей многопроцессорных вычислительных систем. Идеальная системная сеть // Автомат. и телемех.– 2010.– №12.– с. 166–177. hMttNp://mi.mathnet.ru/at1124
  • Каравай М. Ф., Подлазов В. С. Расширенные блок-схемы для идеальных системных сетей // Пробл. управл.– 2012.– №4.– с. 45–51. MhttNp://mi.mathnet.ru/pu728
  • Барабанова Е. А., Вытовтов К. А., Подлазов В. С. Многокаскадные коммутаторы для оптических и электронных суперкомпьютерных систем // Материалы 8-го Национального Суперкомпьютерного Форума, НСКФ-2019 (26–29 ноября 2019 года, ИПС имени А.К. Айламазяна РАН, Переславль-Залесский, Россия).
  • Newman P. Fast packet switching for integrated services, A dissertation submitted for the degree of Doctor of Philosophy.– Wolfson College, University of Cambridge.– 1988.– 159 pp. hUtRtpL://pnewman.com/papers/thesis/thesis.pdf
  • Pipenger N. On rearrangeable and non-blocking switching networks // J. Comput. Syst. Sci.– 1978.– Vol. 17.– No. 2.– pp. 145–162. https://doi.org/10.1016/0022-0000(78)90001-6
  • Scott S., Abts D., Kim J., Dally W. The Black Widow High-radix Clos Network // Proc. 33rd Intern. Symp. Comp. Arch., ISCA’2006 (17–21 June 2006, Boston, MA, USA).– IEEE.– 2006.– ISBN 0-7695-2608-X.– pp. 16–28. https://doi.org/10.1109/ISCA.2006.40
  • Mellanox OFED for Linux User Manual, Rev 2.3–1.0.1.– Melanox Technologies, Ltd..– 2014.– 208 pp.
  • Bhuyan L. N., Agrawal D. P. Generalized hypercube and hyperbus structures for a computer network // IEEE Trans. on Computers.– 1984.– Vol. C-33.– No. 4.– pp. 323–333. https://doi.org/10.1109/TC.1984.1676437
  • Lubiw A. Counterexample to a conjecture of Szymanski on hypercube routing // Inform. Proc. Let.– 1990.– Vol. 35.– No. 2.– pp. 57–61. https://doi.org/10.1016/0020-0190(90)90106-8
  • Gu Q.-P., Tamaki H. Routing a permutation in hypercube by two sets of edge-disjoint paths // J. of Parallel and Distributed Comput.– 1997.– Vol. 44.– No. 2.– pp. 147–152. https://doi.org/10.1006/jpdc.1997.1358
  • Efe K. A variation on the hypercube with lower diameter // IEEE Trans. Computers.– 1991.– Vol. 40.– No. 11.– pp. 1312–1316. https://doi.org/10.1109/12.102840
  • Alverson B., Froese E., Kaplan L., Roweth D. Cray® XCTM Series Network, WP-Aries01-1112.– Cray Inc..– 28 pp. hUtRtpLs://www.alcf.anl.gov/files/CrayXCNetwork.pdf
  • Kim J., Dally W.J., Scott S., Abts D. Technology-driven, highly-scalable dragonfly topology // Proceedings of the 35th annual International Symposium on Computer Architecture, ISCA 2008 (21–25 June, 2008, Beijing, China).– 2008.– ISBN 978-0-7695-3174-8.– pp. 77–88. https://doi.org/10.1109/ISCA.2008.19
  • De Sensi D., Di Girolamo S., McMahon K. H., Roweth D., Hoefler T. An in-depth analysis of the slingshot interconnect.– 2020.– 13 pp. arXivarXiv 2008.08886 [cs.DC]
  • Холл М. Комбинаторика, Главы 10–12.– M.: Мир.– 1970.– 424 с.
  • Clos C. A study of non-locking switching networks // Bell System Tech. J.– 1953.– Vol. 32.– No. 2.– pp. 406–424. https://doi.org/10.1002/j.1538-7305.1953.tb01433.x
  • Бенеш В. Э. // Математические основы теории телефонных сообщений, М.: Связь.– 1968.– с. 83–150.
  • Arimili B., Arimilli R., Chung V., Clark S., Denzel W., Drerup B., Hoefler T., Joyner J., Lewis J., Li J., Ni N., Rajamony R. The PERCS high-performance interconnect // HOTI ’10: Proceedings of the 2010 18th IEEE Symposium on High Performance Interconnects (18–20 August 2010, Mountain View, CA, USA).– 2010.– ISBN 978-0-7695-4208-9.– pp. 75–82. https://doi.org/10.1109/HOTI.2010.16
  • Alverson R., Roweth D., Kaplan L. The Gemini system interconnect // HOTI’10: Proceedings of the 2010 18th IEEE Symposium on High Performance Interconnects (18–20 August 2010, Mountain View, CA, USA).– 2010.– ISBN 978-0-7695-4208-9.– pp. 83–87. https://doi.org/10.1109/HOTI.2010.23
  • Stegailov V., Agarkov A., Biryukov S., Ismagilov T., Khalilov M., Kondratyuk N., Kushtanov E., Makagon D., Mukosey A., Semenov A., Simonov A., Timofeev A., Vecher V. Early performance evaluation of the hybrid cluster with torus interconnect aimed at molecular dynamics simulations // PPAM 2017: Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science.– vol. 10777, Cham: Springer.– 2017.– ISBN 978-3-319-78023-8.– pp. 327–336.
  • Ajima Y., Inoue T., Hiramoto Sh., Shimiz T. Tofu: Interconnect for the K computer // FUJITSU Sci. Tech. J.– 2012.– Vol. 48.– No. 3.– pp. 280–285. hUtRtpLs://www.fujitsu.com/global/documents/about/resources/publications/fstj/archives/vol48-3/paper05.pdf
  • Flajslik M., Borch E., Parker M. A. Megafly: A topology for exascale systems // ISC High Performance 2018: High Performance Computing, Lecture Notes in Computer Science.– vol. 10876, Cham: Springer.– 2018.– ISBN 978-3-319-92039-9.– pp. 289–310. https://doi.org/10.1007/978-3-319-92040-5_15
  • De Sensi D., Di Girolamo S., Ashkboos S., Li Sh., Hoefler T. Flare: flexible in-network allreduce // SC ’21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (14–19 November, 2021, St. Louis, Missouri, USA), New York: ACM.– 2021.– ISBN 978-1-4503-8442-1.– 16 pp. https://doi.org/10.1145/3458817.3476178
  • Прангишвили И. В., Подлазов В. С., Стецюра Г. Г. Локальные микро-процессорные вычислительные сети, Гл. 6.– М.: Наука.– 1984.– 175 с.
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp