[논문] ACEAPEX: 인코딩 시 절대 오프셋 해결로 병렬 LZ77 디코딩

Source: arXiv - 2606.04268v1

Overview

이 논문은 ACEAPEX라는 새로운 LZ77 기반 압축 해제 방식을 소개한다. 기존의 순차적 병목을 없애고 모든 백레퍼런스를 절대 오프셋으로 변환함으로써 이를 구현한다. 데이터를 자체 포함형 1 MiB 블록으로 패킹함으로써 ACEAPEX는 각 블록을 완전히 독립적으로 디코딩할 수 있어 CPU와 GPU에서 대규모 병렬 처리를 가능하게 한다. 저자들은 최신 AMD EPYC CPU에서 3배 이상의 멀티코어 속도 향상과, 표준 수준의 압축 비율을 유지하면서 기록적인 GPU 디코드 속도를 보여준다.

Key Contributions

• 절대 오프셋 인코딩: 백레퍼런스를 현재 디코드 포인터에 대한 상대 거리가 아니라 압축 해제된 스트림 내 위치로 저장한다.
• 자체 포함형 1 MiB 블록: 각 블록이 디코딩에 필요한 모든 정보를 담고 있어, 완전한 병렬 처리가 가능하다.
• CPU 구현: 널리 사용되는 lzbench 스위트에 통합되어 FASTQ 유전체 데이터에 대해 8코어 EPYC CPU에서 최대 10.9 GB/s를 달성한다.
• GPU 웨이브프론트 디코더: NVIDIA H100 GPU용 새로운 웨이브프론트 스타일 알고리즘으로, 대용량 텍스트 코퍼스에서 44 GB/s(단일 GPU) 및 77 GB/s(깊이 제한 인코더)를 기록했으며, 비트‑완전 출력을 검증했다.
• 압축 비율 동등성: 최신 zstd -3와 비슷한 압축 비율을 유지하며, 깊이 제한 변형에서는 단지 1.5 %만 손실한다.

Methodology

1. 인코딩 시 절대 오프셋 해결 – 압축 과정에서 인코더는 각 백레퍼런스가 최종 압축 해제 파일에서 차지하게 될 정확한 위치를 계산하고, 상대 거리가 아닌 절대 주소를 저장한다.
2. 블록 분할 – 입력 스트림을 고정 크기 1 MiB 블록으로 나눈다. 각 블록 헤더는 해당 블록 내부 백레퍼런스들의 절대 오프셋을 기록해, 블록 밖을 참조하지 않도록 보장한다.
3. CPU에서의 병렬 디코딩 – 블록이 독립적이므로 스레드 풀은 각 블록을 코어에 할당할 수 있다. 디코딩은 단순 복사 루프로 진행되며 동기화나 선행 탐색이 필요하지 않는다.
4. GPU 웨이브프론트 디코더 – GPU 버전은 각 블록을 워프(32 스레드)에 매핑한다. “웨이브프론트 매치” 단계에서 매치를 병렬로 해결하고, 이어지는 복사 단계에서 리터럴과 매치 데이터를 출력 버퍼에 기록한다. 알고리즘은 데이터 의존성을 깊이 우선 순서로 처리해 GPU의 방대한 스레드 병렬성에 맞춘다.
5. 검증 – 저자들은 레퍼런스 디코더와 바이트‑대‑바이트 비교를 수행해 손실 없는 정확성을 보장한다(BIT‑PERFECT).

Results & Findings

• zstd -3 대비 속도 향상: CPU에서는 최대 3.1× 빠른 디코딩을 달성하면서 압축 비율은 비슷하게 유지한다.
• GPU 확장성: NVLink를 통해 두 번째 H100을 추가했을 때 거의 선형에 가까운 스케일링을 보여, 고처리량 데이터 파이프라인에 적합함을 입증한다.
• 정확성: 모든 출력이 레퍼런스 디코더와 바이트‑대‑바이트 일치해, 공격적인 병렬화가 손실 없는 결과를 해치지 않음을 확인한다.

Practical Implications

• 고처리량 유전체 파이프라인 – FASTQ 파일은 I/O가 병목이 되기 쉬운데, ACEAPEX는 단일 서버에서 10 GB/s 이상으로 압축 해제해 변이 호출이나 정렬 단계의 병목을 크게 완화한다.
• 빅데이터 분석 – 웹 크롤링 로그, 텔레메트리 등 텍스트 로그를 저장소에서 컴퓨트 노드로 GPU당 40 GB/s 이상 스트리밍할 수 있어 페타바이트 규모 아카이브에 대한 실시간 분석이 가능해진다.
• 엣지‑투‑클라우드 데이터 전송 – 블록 기반 포맷은 객체 스토어나 HDFS 같은 분산 스토리지와 잘 맞으며, 각 블록이 자체 포함형이라 별도 조정 없이 병렬 fetch가 가능하다.
• GPU 가속 워크플로 – 기존 GPU 중심 파이프라인(딥러닝 전처리, 비디오 트랜스코딩 등)에서 LZ77 압축 해제를 동일 가속기로 오프로드해 CPU 자원을 절약할 수 있다.
• 라이브러리 통합 – ACEAPEX가 lzbench에 플러그인 형태로 제공되므로 개발자는 최소한의 코드 변경만으로 채택할 수 있으며, libdeflate, zstd 등 다른 압축 라이브러리에도 이 방식을 이식할 여지가 있다.

Limitations & Future Work

• 블록 크기 트레이드오프 – 고정 1 MiB 블록은 독립성을 단순화하지만, 긴 매치가 블록 경계를 넘는 경우 압축 크기가 약간 증가할 수 있다.
• 인코더 오버헤드 – 절대 오프셋을 계산하는 과정이 압축 시 약간의 CPU 작업을 추가한다. 논문은 디코드 속도에 초점을 맞추었으므로 인코더 성능 최적화가 향후 과제로 남는다.
• GPU 메모리 압박 – 웨이브프론트 디코더는 여러 블록과 보조 버퍼를 동시에 보관할 만큼 충분한 GPU 메모리가 필요하며, 매우 큰 데이터셋은 세심한 청크 관리가 요구된다.
• 다른 코덱 지원 확대 – 현재는 LZ77에 한정된 기술이며, 절대 오프셋 인코딩을 Zstandard와 같은 최신 사전 기반 코덱(시퀀스)으로 확장하는 연구가 필요하다.

핵심 요약: ACEAPEX는 백레퍼런스를 저장하는 방식을 재고함으로써 오랫동안 존재해 온 LZ77 디코딩의 순차적 한계를 깨고, 압축 품질을 희생하지 않으면서 CPU와 GPU 모두에서 획기적인 속도 향상을 제공한다. 이는 유전체학, 빅데이터 분석 등 LZ77 기반 포맷에 의존하는 모든 분야에서 데이터 집약적 파이프라인을 한층 빠르게 만들 수 있는 길을 열어준다.

Authors

• Yakiv Shavidze

Paper Information

• arXiv ID: 2606.04268v1
• Categories: cs.DC
• Published: June 2, 2026
• PDF: Download PDF