Abstract. The problem of increasing the speed and throughput of multiprocessor communication networks using input FIFO-queued switches with an output register matrix is under consideration. A packet switch-ing method is proposed featuring a parallel packet transfer pipeline which makes it possible to load packets from the input buffers to the register matrix with no delay needed to spin until the matrix is empty. The proposed method is shown to provide parallel and concurrent packet processing in the input and output circuits of the packet switch. A structural model of a packet switching unit based on the proposed approach is presented. A packet switching algorithm is formulated based on the representation of the set of packets loaded into the register matrix in the form of a packet consistency graph reflecting the packet set ability of being issued in parallel. A graph vertex weight assignment rule is stated taking into account the idle time packets spend in the register matrix. A maximum total weight clique of the consistency graph is shown to be searched for to pick up a proper subset of packets that can be issued currently which makes it possible to reduce the idle time. A formula is deduced to calculate the average time needed for a packet to be transferred through the register matrix of a switch based on the proposed method. The average packet transfer time versus the number of input/output terminals graphs are investigated and the comparison is made for the parallel-sequential switching method and the proposed approach. The developed method is demonstrated to decrease the average packet transfer time by 41 % for all cases of practical significance.

Keywords: multiprocessor, communication network, packet switching, hardware, pipeline mode

References:

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, http://www.mellanox.com/repository/solutions/tile-scm/docs/UG130-ArchOverview-TILE-Gx.pdf.
4. Olofsson A. Epiphany-V: A 1024 processor 64-bit RISC System-On-Chip, https://www.parallella.org/docs/e5_1024core_soc.pdf.
5. Patent 8531943 B2 USА, Mesh network, Olofsson A. Published Sep. 10, 2013.
6. Chen Y. 2006 IEEE International SOC Conference, 2006, рp. 57–60.
7. Karol M., Hluchyj M. IEEE Journal on Selected Areas in Communications, 1988, vol. 6, Dec., рp. 1587–1597. DOI: 10.1109/49.12886.
8. Ganjali Y., Keshavarzian A., Shah D. IEEE/ACM Transactions on Networking, 2005, no. 4(13), pp. 782–789. DOI: 10.1109/TNET.2005.852884.
9. Karol M., Hluchyj M., Morgan S. IEEE Transactions on Communications, 1987, no. 12(35), pp. 1347–1356. DOI: 10.1109/TCOM.1987.1096719.
10. Chen D.X., Mark J.W. IEEE/ACM Transactions on Networking, 1993, no. 1(1), pp. 142–151. DOI: 10.1109/90.222914.
11. Dong Z., Rojas-Cessa R., Oki E. Electronics Letters, 2011, no. 1(47), pp. 32–34. DOI: 10.1049/el.2010.2677.
12. Chuang S.-T., Goel A., McKeown N., Prabhakar B. IEEE Journal on Selected Areas in Communica-tions, 1999, no. 6(17), pp. 1030–1039. DOI: 10.1109/49.772430.
13. Kang K., Park K.-J., Sha L., Wang Q. Real-Time Systems, 2013, no. 1(49), pp. 117–135. DOI: 10.1007/s11241-012-9169-6
14. Neely M.J., Modiano E., Cheng Y.-S. IEEE/ACM Transactions on Networking, 2007, no. 3(15), pp. 657–668. DOI: 10.1109/TNET.2007.893876.
15. Chang C.-S., Lee D.-S., Yue C.-Y. IEEE/ACM Transactions on Networking, 2006, no. 3(14), pp. 644–656. DOI: 10.1109/TNET.2006.876202.
16. Krikunov O.V. et al. Telekommunikatsii, 2006, no. 10, pp. 11–16. (in Russ.)
17. Emel'yanov S.G., Zotov I.V., Titov V.S. Arkhitektura parallel'nykh logicheskikh mul'tikontrollerov (Archi-tecture of Parallel Logic Multicontrollers), Moscow, 2009, 233 р. (in Russ.)
18. Вelyayev Yu.V. Parallel'no-posledovatel'nyy kommutator dlya sistem parallel'noy i raspredelennoy obrabotki dannykh (Parallel-Serial Switch for Parallel and Distributed Data Processing Systems), Ex-tended abstract of candidate’s thesis. Kursk, 2003, 17 р. (in Russ.)