This thesis considers flexible decoder implementation of low density parity check (LDPC) codes via compute-unified-device-architecture (CUDA) programming on graphics processing unit (GPU), a research subject of considerable recent interest. An important issue in LDPC decoder design based on CUDA-GPU is realizing coalesced memory access, a technique that reduces memory transaction time considerably. In previous works along this direction, it has not been possible to achieve coalesced memory access in both the read and write operations due to the asymmetric nature of the bipartite graph describing the LDPC code structure. In this thesis, a new algorithm is proposed that enables coalesced memory access in both the read and write operations for one half of the decoding process -- either the bit-to-check or the check-to-bit message passing. For the remaining half of the decoding step, proposed scheme requires address transformation in both the read and write operations but one translating array is sufficient. This thesis also describes the use of on-chip shared memory and texture cache. Overall, experimental results show that proposed GPU-based LDPC decoder achieves more than 230x-speedup compared to CPU-based LDPC decoders and also outperforms existing GPU-based decoders by a significant margin. Error rate performance of several LDPC codes and trapping set behaviors are also presented to provide the application examples of proposed GPU-based LDPC decoder.
LDPC 부호는 강한 오류정정 능력을 바탕으로 WiFi, 10G Ethernet, WiMAX 등 여러 통신 응용 분야에서 채택되고 있다. 그러나 정확한 오류정정 능력 평가를 위한 수학적 방법이 알려지지 않아 소프트웨어 또는 하드웨어를 이용한 시뮬레이션의 사용이 불가피하다. LDPC 의 복호는 복잡도가 매우 높은 message passing 알고리즘에 기반을 두고 있다. 따라서 최근 몇 년간 하드웨어 기반의 LDPC 복호기에 대한 많은 연구가 진행되어 왔다. 하지만 하드웨어 기반 복호기를 설계하기 위해서는 많은 비용과 노력을 필요로 하고 구현에 있어서 시간이 오래걸린다는 단점이 있다. 또한 복호기의 구조가 parity check matrix 에 따라 변하기 때문에 새로운 LDPC 복호기의 구현을 위해서는 새로운 하드웨어의 설계가 필요하다.
최근 들어 일반적인 컴퓨팅을 위해 GPU를 활용하는 연구가 떠오르고 있다. GPU는 수천개의 멀티 쓰레드 동작을 통해 강력한 컴퓨팅 능력을 제공한다. 특히 NVIDIA 사에서는 CUDA 라는 C 언어 기반의 프로그래밍 언어를 공개하여 프로그램 개발자로 하여금 GPU 기반 프로그래밍을 수월하게 만들었다.
본 학위논문에서는 CUDA 를 이용해서 GPU 기반 LDPC 복호기를 구현하는 방법을 다룬다. 먼저 GPU 기반 LDPC 복호기에 대한 기존 기술을 돌아보고 속도 개선 및 최적화를 위한 새로운 방법을 제안하고 있다. 속도 최적화를 위해서는 병합된 메모리 접근 (coalesced memory access) 방식이 필요하다. 기존 기술은 LDPC 복호기의 메모리 읽기 동작에 병합된 메모리 접근을 가능하도록 구현하였지만 쓰기 동작에는 병합된 메모리 접근을 구현하지 않고 있다. 기존논문이 다루고있는 읽기 동작에서의 병합된 메모리 접근을 위해서는 두개의 변환배열 (translating array) 이 필요하다. 본 학위논문에서는 복호 과정을 둘로 나누고 처음 과정은 읽기, 쓰기 모든 동작에서 병합된 메모리 접근이 가능하도록 구현하였다. 나머지 과정은 하나의 변환배열을 사용해서 병합되지 않은 메모리 접근으로 동작한다. 또한 변환 배열을 shared memory 에 저장함으로써 off-chip 메모리로의 접근을 최소화하는 방법을 제안하고 있다. Texture 캐싱을 이용한 메모리 접근의 최적화 역시 다루고 있다.
또한 기존 기술들과의 복호기 속도 비교, CPU 기반 복호기와의 속도 비교를 제공한다. 마지막으로 제안한 GPU 기반 복호기를 이용해 LDPC 부호의 성능을 알아보고 분석하는 예를 다루고자 한다.