A race condition is a common trigger for concurrency bugs. As a special case, a race condition can also occur across the kernel and user space causing a doublefetch bug, which is a field that has received little resea...A race condition is a common trigger for concurrency bugs. As a special case, a race condition can also occur across the kernel and user space causing a doublefetch bug, which is a field that has received little research attention. In our work, we first analyzed real-world doublefetch bug cases and extracted two specific patterns for doublefetch bugs. Based on these patter ns, we proposed an approach of multi-taint parallel tracking to detect double-fetch bugs. We also implemented a prototype called DFTracker (doublefetch bug tracker), and we evaluated it with our test suite. Our experiments demonstrated that it could effectively find all the double-fetch bugs in the test suite including eight realworld cases with no false negatives and minor false positives. In addition, we tested it on Linux kernel and found a new double-fetch bug. The execution overhead is approximately 2x for single-file cases and approximately 9x for the whole kernel test, which is acceptable. To the best of the authors1 knowledge, this work is the first to introduce multi-taint parallel tracking to double-fetch bug detection—an innovative method that is specific to double-fetch bug features—and has better path coverage as well as lower runtime overhead than the widely used dynamic approaches.展开更多
By constructing an accumulated-crossover relationship in multiple parallel concatenated single parity check （M-PC-SPC） codes, a class of error-correcting codes, termed multiple accumulated-crossover parallel concate...By constructing an accumulated-crossover relationship in multiple parallel concatenated single parity check （M-PC-SPC） codes, a class of error-correcting codes, termed multiple accumulated-crossover parallel concatenated single parity check （M-ACPC-SPC） codes, is proposed. M-ACPC-SPC codes possess linear encoding complexity and can be decoded iteratively with low complexity by the sum-product algorithm （SPA）. Simulation results show that M-ACPC-SPC codes have lower error floors than M-PCSPC codes with the same dimension, and when the dimension is 5, M-ACPC-SPC codes achieve bit error rate （BER） better than （3, 6） regular low density parity check （LDPC） codes.展开更多
Low-Density Parity-Check （LDPC） codes are powerful error correcting codes adopted by recent communication standards. LDPC decoders are based on belief propagation algorithms, which make use of a Tanner graph and ver...Low-Density Parity-Check （LDPC） codes are powerful error correcting codes adopted by recent communication standards. LDPC decoders are based on belief propagation algorithms, which make use of a Tanner graph and very intensive message-passing computation, and usually require hardware-based dedicated solutions. With the exponential increase of the computational power of commodity graphics processing units （GPUs）, new opportunities have arisen to develop general purpose processing on GPUs. This paper proposes the use of GPUs for implementing flexible and programmable LDPC decoders. A new stream-based approach is proposed, based on compact data structures to represent the Tanner graph. It is shown that such a challenging application for stream-based computing, because of irregular memory access patterns, memory bandwidth and recursive flow control constraints, can be efficiently implemented on GPUs. The proposal was experimentally evaluated by programming LDPC decoders on GPUs using the Caravela platform, a generic interface tool for managing the kernels＇ execution regardless of the GPU manufacturer and operating system. Moreover, to relatively assess the obtained results, we have also implemented LDPC decoders on general purpose processors with Streaming Single Instruction Multiple Data （SIMD） Extensions. Experimental results show that the solution proposed here efficiently decodes several codewords simultaneously, reducing the processing time by one order of magnitude.展开更多
文摘A race condition is a common trigger for concurrency bugs. As a special case, a race condition can also occur across the kernel and user space causing a doublefetch bug, which is a field that has received little research attention. In our work, we first analyzed real-world doublefetch bug cases and extracted two specific patterns for doublefetch bugs. Based on these patter ns, we proposed an approach of multi-taint parallel tracking to detect double-fetch bugs. We also implemented a prototype called DFTracker (doublefetch bug tracker), and we evaluated it with our test suite. Our experiments demonstrated that it could effectively find all the double-fetch bugs in the test suite including eight realworld cases with no false negatives and minor false positives. In addition, we tested it on Linux kernel and found a new double-fetch bug. The execution overhead is approximately 2x for single-file cases and approximately 9x for the whole kernel test, which is acceptable. To the best of the authors1 knowledge, this work is the first to introduce multi-taint parallel tracking to double-fetch bug detection—an innovative method that is specific to double-fetch bug features—and has better path coverage as well as lower runtime overhead than the widely used dynamic approaches.
基金Supported by the National High-Tech Research & Development Program of China (Grant No. 2007AA01Z288)the National Science Fund for Distinguished Young Scholars (Grant No. 60725105)the Program for Changjiang Scholars and Innovative Research Team in University and the 111 Project (Grant No. B08038)
文摘By constructing an accumulated-crossover relationship in multiple parallel concatenated single parity check （M-PC-SPC） codes, a class of error-correcting codes, termed multiple accumulated-crossover parallel concatenated single parity check （M-ACPC-SPC） codes, is proposed. M-ACPC-SPC codes possess linear encoding complexity and can be decoded iteratively with low complexity by the sum-product algorithm （SPA）. Simulation results show that M-ACPC-SPC codes have lower error floors than M-PCSPC codes with the same dimension, and when the dimension is 5, M-ACPC-SPC codes achieve bit error rate （BER） better than （3, 6） regular low density parity check （LDPC） codes.
基金Supported by the Portuguese Foundation for Science and Technology,through the FEDER program,and also under Grant No.SFRH/BD/37495/2007
文摘Low-Density Parity-Check （LDPC） codes are powerful error correcting codes adopted by recent communication standards. LDPC decoders are based on belief propagation algorithms, which make use of a Tanner graph and very intensive message-passing computation, and usually require hardware-based dedicated solutions. With the exponential increase of the computational power of commodity graphics processing units （GPUs）, new opportunities have arisen to develop general purpose processing on GPUs. This paper proposes the use of GPUs for implementing flexible and programmable LDPC decoders. A new stream-based approach is proposed, based on compact data structures to represent the Tanner graph. It is shown that such a challenging application for stream-based computing, because of irregular memory access patterns, memory bandwidth and recursive flow control constraints, can be efficiently implemented on GPUs. The proposal was experimentally evaluated by programming LDPC decoders on GPUs using the Caravela platform, a generic interface tool for managing the kernels＇ execution regardless of the GPU manufacturer and operating system. Moreover, to relatively assess the obtained results, we have also implemented LDPC decoders on general purpose processors with Streaming Single Instruction Multiple Data （SIMD） Extensions. Experimental results show that the solution proposed here efficiently decodes several codewords simultaneously, reducing the processing time by one order of magnitude.
