Accelerating Network Coding on Graphics Processors

Abstract:

Network coding has recently been widely applied in various distributed systems for throughput improvement and/or resilience to network dynamics. However, the computational overhead introduced by network coding operations is not negligible and has become the obstacle for practical deployment of network coding. In this paper, I exploit the computing power of commodity many-core Graphic Processing Units (GPUs) and multi-core CPUs to accelerate the network coding computation. With the implementation of the algorithms, significant encoding and decoding throughput can be achieved.

• Periodical: Applied Mechanics and Materials (Volumes 513-517)
• Pages: 1573-1576
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.513-517.1573
• Online since: February 2014
• Authors: Xiao Hui Pan*
• Keywords: Graphics Processors, Network Coding, Random

References

[1] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung: Network Information Flow. IEEE Trans. on Information Theory, vol. 46, July (2000).

DOI: 10.1109/18.850663

[2] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Effros: The benefits of coding over routing in a randomized setting. In ISIT, July (2003).

DOI: 10.1109/isit.2003.1228459

[3] P. Sanders, S. Egner, and L. Tolhuizen: Polynomial time algorithms for network information flow. Proc. 15th ACM Symposium on Parallel Algorithms and Architectures, (2003).

DOI: 10.1145/777412.777464

[4] C. Fragouli and E. Soljanin: Network Coding Applications. Now Publishers Inc, January (2008).

[5] Tracey Ho T. Ho and D. Lun: Network Coding: An Introduction. Cambridge University Press, (2008).

[6] T. Ho, M. Medard, J. Shi, M. Effros, and D. Karger, On Randomized Network Coding, in Proceedings of the 41st Allerton Conference on Communication, Control, and Computing, Oct. (2003).

[7] M. Wang, and B. Li. How practical is network coding? In Proceedings of the 14th International Workshop on Quality of Service (IWQoS), 2006, 274-278.

[8] H. Shojania, and B. Li. Parallelized progressive network coding with hardware acceleration. In Proceedings of the 15th International Workshop on Quality of Service (IWQoS), (2007).

DOI: 10.1109/iwqos.2007.376547

[9] M. Wang, and B. Li. Lava: a reality check of network coding in peer-to-peer live streaming. In Proceedings of IEEE INFOCOM07, (2007).

DOI: 10.1109/infcom.2007.130

[10] J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone, and J. C. Phillips. GPU computing. IEEE Proceedings, May 2008, 879-899.

DOI: 10.1109/jproc.2008.917757

[11] M. Hussein andW. Abd-Almageed, Efficnent Band Approximation of Gram Matrices for Large Scale Kernel Methods on GPUs, in Proc. of the Conference on High Performance Computing Networking, Storage and Analysis, Oregon, (2009).

DOI: 10.1145/1654059.1654091

[12] H. Shojania and B. Li. Pushing the envelope: Extreme network coding on the GPU. In Proc. of International Conference on Distributed Computing Systems (ICDCS09), pages 490-499, Montreal, Canada, June (2009).

DOI: 10.1109/icdcs.2009.68

[13] H. Shojania, B. Li, and X. Wang, Nuclei: GPU-accelerated Many-core Network Coding. In Proceedings of IEEE INFOCOM09, Apr. (2009).

DOI: 10.1109/infcom.2009.5061951

[14] X. Chu, and K. Zhao. Practical random linear network coding on GPUs. In GPU Solutions to Multi-scale Problems in Science and Engineering, 115 Lecture Notes in Earth System Science, 2013, 115-130.

DOI: 10.1007/978-3-642-16405-7_6