Block-interleaving based parallel CRC computation for multi-processor systems

A coarse-grained parallel computation method for cyclic redundancy check (CRC) is developed for efficient multiprocessor implementation. A received message is divided into a number of blocks, and several interleaved blocks are processed concurrently by multiple processing units. The synchronization overhead is minimized by resolving the dependency problem such that the individual results of multiple processing units can be combined at the last stage only. The block-interleaved parallel CRC computation method can be applied for variable length messages. The proposed coarsegrained parallel computation method can be easily combined with fine-grained parallel CRC computation algorithms to further increase the processing speed. The performance of the developed method is measured by an OpenMP-based parallel software implementation.