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

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

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

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

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

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

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

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

Еще

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

Еще

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

IDR: 143179418   |   DOI: 10.25209/2079-3316-2022-13-4-47-76

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

  • Барабанова Е. А., Вытовтов К. А., Подлазов В. С. Неблокируемые отказоустойчивые двухкаскадные дуальные фотонные коммутаторы // Проблемы управления.– 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