ISSN 0021-3454 (печатная версия)
ISSN 2500-0381 (онлайн версия)
Меню

11
Содержание
том 62 / Ноябрь, 2019
СТАТЬЯ

DOI 10.17586/0021-3454-2019-62-6-524-533

УДК 004.272

МЕТОД ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНО-ПАРАЛЛЕЛЬНОЙ КОММУТАЦИИ ПАКЕТОВ В МУЛЬТИПРОЦЕССОРАХ

Мохаммед Д. А.
Юго-Западный государственный университет, кафедра информационных систем и технологий;


Зотов И. В.
Курский государственный технический университет, кафедра вычислительной техники; профессор


Передельский Г. И.
Курский государственный технический университет ; профессор


Аннотация. Рассмотрена задача повышения скорости работы и пропускной способности коммуникационной среды мультипроцессора при использовании коммутационных устройств с входными FIFO-буферами и выходной матрицей регистров. Предложен метод коммутации пакетов в мультипроцессорах, новизна которого заключается в параллельно-конвейерной загрузке пакетов в матрицу регистров из входных буферов без ожидания выдачи всех ранее загруженных пакетов. Рассмотрена структурная модель коммутационного устройства, реализующего разработанный метод. Сформулирован алгоритм обработки пакетов коммутационным устройством, основанный на представлении множества пакетов, находящихся в матрице регистров в каждом такте работы устройства, графом совместности, отражающим возможность одновременной выдачи пакетов на выходы. Представлено правило взвешивания вершин графа совместности, учитывающее время нахождения пакетов в матрице регистров. Показано, что выбор множества пакетов, подлежащих выдаче, можно свести к выделению клики графа совместности, обладающей наибольшим весом, что позволяет минимизировать время обработки пакетов. Выведена формула для оценки среднего времени прохождения пакета через матрицу регистров коммутационного устройства при использовании разработанного метода. Исследованы зависимости указанного времени от числа входов/выходов устройства, выполнен их сравнительный анализ для предлагаемого метода и метода параллельно-последовательной коммутации пакетов. Показано, что разработанный метод позволяет снизить среднее время прохождения пакета через матрицу регистров более чем на 41 % во всех практически значимых случаях.
Ключевые слова: мультипроцессор, коммуникационная среда, коммутация пакетов, аппаратные средства, конвейерный режим

Список литературы:
  1. Jerraya A. A., Wolf W. et al. Multiprocessor systems-on-chips. Elsevier Inc., 2005.
  2. Misra S., Goswami S. Network routing: fundamentals, applications, and emerging technologies. Wiley Telecom, 2014.
  3. Tilera: Tile processor architecture overview for the TILE-GX series [Электронный ресурс]: .
  4. Olofsson A. Epiphany-V: A 1024 processor 64-bit RISC System-On-Chip [Электронный ресурс]: .
  5. Pat. 8531943 B2 USА. Mesh network / A. Olofsson. Sep. 10, 2013.
  6. Chen Y. Cell switched network-on-chip – candidate for billion-transistor system-on-chips // 2006 IEEE Intern. SOC Conf. 2006. P. 57—60.
  7. Karol M., Hluchyj M. Queueing in high-performance packet switching // IEEE J. on Selected Areas in Communications. 1988. Vol. 6. Dec. P. 1587—1597. DOI: 10.1109/49.12886.
  8. Ganjali Y., Keshavarzian A., Shah D. Cell switching versus packet switching in input-queued switches // IEEE/ACM Transactions on Networking. 2005. Vol. 13, N 4. Aug. P. 782—789. DOI: 10.1109/TNET.2005.852884.
  9. Karol M., Hluchyj M., Morgan S. Input versus output queueing on a space-division packet switch // IEEE Transactions on Communications. 1987. Vol. 35, N 12. P. 1347—1356. DOI: 10.1109/TCOM.1987.1096719.
  10. Chen D. X., Mark J. W. SCOQ: a fast packet switch with shared concentration and output queueing // IEEE/ACM Transactions on Networking. 1993. Vol. 1, N 1. P. 142—151. DOI: 10.1109/90.222914.
  11. Dong Z., Rojas-Cessa R., Oki E. Buffered Clos-network packet switch with per-output flow queues // Electronics Letters. 2011. Vol. 47, N 1. P. 32—34. DOI: 10.1049/el.2010.2677.
  12. Chuang S.-T., Goel A., McKeown N., Prabhakar B. Matching output queueing with a combined input/output-queued switch // IEEE J. on Selected Areas in Communications. 1999. Vol. 17, N 6. P. 1030—1039. DOI: 10.1109/49.772430.
  13. Kang K., Park K.-J., Sha L., Wang Q. Design of a crossbar VOQ real-time switch with clock-driven scheduling for a guaranteed delay bound // Real-Time Systems. 2013. Vol. 49, N 1. P. 117—135. DOI: 10.1007/s11241-012-9169-6.
  14. Neely M. J., Modiano E., Cheng Y.-S. Logarithmic delay for NxN packet switches under the crossbar constraint // IEEE/ACM Transactions on Networking. 2007. Vol. 15, N 3. P. 657—668. DOI: 10.1109/TNET.2007.893876.
  15. Chang C.-S., Lee D.-S., Yue C.-Y. Providing guaranteed rate services in the load balanced Birkhoff-von Neumann switches // IEEE/ACM Transactions on Networking. 2006. Vol. 14, N 3. P. 644—656. DOI: 10.1109/TNET.2006.876202.
  16. Крикунов О. В. и др. Коммутационный процессор с параллельно-конвейерной обработкой сообщений // Телекоммуникации. 2006. № 10. С. 11—16.
  17. Емельянов С. Г., Зотов И. В., Титов В. С. Архитектура параллельных логических мультиконтроллеров. М.: Высш. школа, 2009. 233 с.
  18. Беляев Ю. В. Параллельно-последовательный коммутатор для систем параллельной и распределенной обработки данных: Автореф. дис. … канд. техн. наук. Курск, 2003. 17 с.