협동 병렬 X-Match 데이타 압축 알고리즘 = The Cooperative Parallel X-Match Data Compression Algorithm

다국어 초록 (Multilingual Abstract)

X-Match algorithm is a lossless compression algorithm suitable for hardware implementation owing to its simplicity. It can compress 32 bits per clock cycle and is suitable for real time compression. However, as the bus width increases 64-bit, the compression unit also need to increase. This paper proposes the cooperative parallel X-Match (X-MatchCP) algorithm, which improves the compression speed by performing the two X-Match algorithms in parallel. It searches the all dictionary for two words, combines the compression codes of two words generated by parallel X-Match compression and outputs the combined code while the previous parallel X-Match algorithm searches an individual dictionary. The compression ratio in X-MatchCP is almost the same as in X-Match. X-MatchCP algorithm is described and simulated by Verilog hardware description language.

국문 초록 (Abstract)

X-Match 알고리즘은 비교적 간단하여 하드웨어로 구현하는 데에 적합한 무손실 압축 알고리즘이다. X-Match 알고리즘은 사이클 당 32비트의 압축이 가능하므로 고속 압축에 적합하다. 그렇지만 버스 폭이 증가됨에 따라서 이에 맞추어서 압축 단위를 증가시킬 필요가 있게 되었다. 본 논문에서는 X-Match 알고리즘을 병렬로 수행하여 압축 속도를 2배 향상시키고 X-Match 알고리즘 거의 비슷한 압축률을 제공하는 협동 병렬 X-Match 알고리즘, 즉 X-MatchCP 알고리즘을 제안한다. 기존의 병렬 X-Match 알고리즘이 X-Match 알고리즘을 병렬로 수행할 때에 각자의 사전을 검색하는 데 비해서 X-MatchCP 알고리즘에서는 X-Match 알고리즘이 병렬로 수행되지만 전체 사전을 검색하여 매칭빈도를 높이도록 하였고 run-length 부호화도 두 워드에 대해서 한꺼번에 하는 방식으로 서로 협동하면서 동작한다. 메모리 데이타와 파일 자료를 사용한 시뮬레이션 결과 X-MatchCP 알고리즘은 같은 사전 크기의 X-Match 알고리즘과 거의 비슷한 압축률을 보였다. 그리고 X-MatchCP 알고리즘의 하드웨어 구현을 위한 전체적인 구조 설계를 Verilog 언어를 사용하여 수행하였다.