Exploiting SIMD parallelism on dynamically partitioned parallel network coding for P2P systems

Due to the decoding complexity of network coding, there have been concerns on adopting network coding in the practical P2P systems. To provide rapid decoding speed in practical network coding systems, various multi-threaded approaches which successfully exploit hardware supported TLP have been proposed. Among those parallel approaches, a dynamic partitioning method is known to be the best solution so far. However, the algorithm dynamically changes workload distribution and inherently contains some limits to utilize the SIMD instruction set which are designed to work on a fixed size of data. In this paper, we present a new data manipulation method to utilize SIMD instruction sets, which can be successfully integrated into the dynamic partitioning of thread-level workload distribution. With exploiting both SIMD and thread-level parallelism, we achieve the speed-up of 10.86 using eight running threads compared to the serial algorithm.

Network coding is one of the popular techniques to increase efficiency of network flow. Several parallel algorithms and hardware acceleration methods have been proposed to adopt network coding in practical systems. This paper proposes three data manipulation methods to utilize SIMD instruction sets, considering the previously proposed thread-level parallel algorithms to efficiently reduce decoding time.Figure optionsDownload as PowerPoint slideHighlights
► Three different parallel algorithms with SIMD instructions for network coding are introduced.
► Interactions between thread-level parallelism and instruction-level parallelism for network coding is investigated.
► Performance evaluation on real multi-core processors is provided to show the advantages of the proposed method.