Advanced
Study of Parallelization Methods for Software based Real-time HEVC Encoder Implementation
Study of Parallelization Methods for Software based Real-time HEVC Encoder Implementation
Journal of Broadcast Engineering. 2013. Nov, 18(6): 835-849
Copyright © 2013, The Korean Society of Broadcast Engineers
  • Received : September 10, 2013
  • Accepted : October 23, 2013
  • Published : November 30, 2013
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
용조 안
태진 황
동규 이
상민 김
승준 오
동규 심
dgsim@kw.ac.kr

Abstract
ISO/IEC MPEG과 ITU-T VCEG이 공동으로 구성한 JCT-VC (Joint Collaborative Team on Video Coding)가 표준화를 진행한 HEVC (High Efficiency Video Coding)는 H.264/AVC 대비 약 2배 혹은 그 이상의 압축효율을 목표로 표준화가 시작되었다. 하지만, 계층적 구조를 갖는 가변크기 블록의 사용과 재귀적 부호화 구조에 따른 인코더의 복잡도 증가는 개선해야 할 문제점으로 지적되고 있다. HEVC 인코더의 복잡도를 감소시키기 위하여 다양한 고속화 알고리즘들이 제안되고 있으나, 고속화 알고리즘으로 얻을 수 있는 속도 향상만으로 HEVC 인코더의 실시간성을 확보하기에는 어려움이 있다. 본 논문에서는 현재 표준화가 완료된 HEVC 인코더의 실시간 구현을 위하여 SIMD 명령어를 이용한 데이터 수준 병렬화 기법, CPU 및 GPU를 이용한 멀티스레딩 기법과 같은 다양한 병렬화 기법을 소개한다. 또한, 이러한 병렬화 기법들을 HEVC 인코더에 적용하기 위해 적합한 연산 및 기능 모듈에 대하여 소개한다. 본 연구에서 제안한 방법을 HM (HEVC reference model) 10.0에 적용한 결과 832×480 영상의 경우 20~30fps의 부호화 속도를 나타냈으며, 1920×1080 영상의 경우 5~10fps의 부호화 속도를 나타내었다.
Keywords
Ⅰ. 서 론
최근 FHD (full high definition) 및 UHD (ultra high definition)와 같은 고품질 비디오 서비스에 대한 수요가 증가함에 따라, ISO/IEC MPEG (moving picture experts group)과 ITU-T VCEG (video coding expert group)에서는 JCT-VC (joint collaborative team on video coding)를 결성하여 H.264/AVC의 압축효율을 2배 이상 향상시키는 것을 목표로 새로운 비디오 압축 표준인 HEVC (high efficiency video coding)에 대한 표준화를 진행하였다 [1] [2] . HEVC는 종래의 비디오 압축 표준과 마찬가지로 블록 기반의 하이브리드 코딩에 기반하고 있으나, 추가적인 신규 기술들을 적용하여 H.264/AVC, MPEG-2, 4에서 사용된 매크로 블록의 개념에 CU (coding unit), PU (prediction unit), TU (transform unit)의 세분화된 부호화 단위를 적용하여 압축 효율을 향상시켰다. 현재, HEVC는 64×64 블록 크기부터, 32×32, 16×16, 8×8에 이르는 블록 크기의 CU 단위 부호화를 수행한다. 또한, 화면 내 예측 방향성의 증가, 움직임 예측 결정 기법의 향상, 움직임 벡터 병합 및 다양한 인-루프필터를 적용하여 압축 효율을 향상시켰다.
다양한 부호화 크기, 향상된 신규 기술들의 적용에 따라 높은 부호화 성능 향상이 있으나, 이로 인하여 부호화 모드 결정에 따른 연산 복잡도 또한 크게 증가하였다. 특히, 다양한 부호화 블록 크기와 세분화된 부호화 단위에 따른 재귀적 모드 결정이 가장 큰 원인으로 지적되고 있다. 64×64부터 8×8에 이르는 블록에 대한 최적의 부호화 모드 결정을 위하여 움직임 탐색과 율-왜곡 최적화 (RDO: rate-distortion optimization)에 사용되는 다양한 cost 연산 횟수가 증가하였다. 이러한 HEVC 인코더의 높은 복잡도를 감소시키기 위한 기법으로는 크게 고속화와 병렬화를 들 수 있다. 전술한 바와 같이, HEVC 인코더의 재귀적 모드 결정으로 인하여 발생하는 복잡도를 줄이기 위하여 다양한 고속화 알고리즘들이 제안되었다 [3] [4] [5] . 지금까지 제안된 고속 모드 결정 및 조기 종료 알고리즘들의 경우 HEVC 참조 소프트웨어 HM을 기준으로 높게는 50~60%의 부호화 속도 감소를 나타내었다. 하지만, 고속화 알고리즘으로 얻을 수 있는 속도 향상만으로는 HEVC 인코더의 실시간성 확보에 어려움이 있다. 본 논문에서는 HEVC 인코더의 높은 복잡도를 감소시키고, 실시간성 확보를 위하여 SIMD (single instruction multiple data) 명령어를 이용한 데이터 수준의 병렬화 (DLP: data level parallelism) 기법, CPU 및 GPU를 이용한 멀티스레딩 (multi threading) 기법과 같은 다양한 병렬화 기법을 소개하고, 이를 적용하기 적합한 연산 및 모듈에 대하여 소개한다.
본 논문의 구성은 다음과 같다. 2장에서는 SIMD를 이용한 HEVC 인코더의 데이터 수준 병렬화 기법에 대하여 소개하고, 3장에서는 CPU 및 GPU 멀티스레딩을 이용한 HEVC 인코더 병렬화 기법에 대하여 소개한다. 이후, 4장에서는 2, 3장에서 언급한 병렬화 기법을 HEVC 인코더 참조 소프트웨어인 HM에 적용해보고, HEVC 인코더의 속도 개선을 실험을 통하여 확인한다. 마지막으로 5장에서는 HEVC 인코더의 실시간성 확보를 위한 앞으로의 연구 방향을 살펴보고 결론을 맺는다.
Ⅱ. SIMD를 이용한 HEVC 인코더의 데이터 수준 병렬화 기법
본 장에서는 HEVC 인코더를 위한 병렬화 기법 중 하나인 SIMD 명령어를 이용한 데이터 수준 병렬화 기법에 대하여 소개한다. SIMD는 하나의 명령어로 레지스터에 저장된 여러 데이터를 벡터와 같이 취급하여 병렬적으로 처리하는 명령어 셋을 갖는 구조를 의미한다. 특히 SIMD 명령어를 이용한 데이터 수준 병렬화 기법은 서로 다른 데이터에 대하여 동일한 연산을 복적으로 수행하는데 적합한 병렬화 기법으로 비디오 코덱의 고속처리 및 최적화에 널리 사용되고 있다 [6] [7] [8] . SIMD 명령어를 이용한 데이터 수준 병렬화 기법을 적용하기 적합한 HEVC 인코더의 단일 연산 혹은 기능 모듈을 살펴보면, 율-왜곡 값을 계산하기 위한 cost 함수, 변환 (transform) 및 역-변환 (inverse-transform), 움직임 정밀도를 높이기 위한 화소 보간 필터 (interpolation filter)를 꼽을 수 있다. 본 장에서는 전술한 연산 및 기능 모듈에 SIMD를 적용하기 적합한 이유를 살펴보고 적용 방법에 대하여 살펴보도록 한다.
- 1. Cost 함수
HEVC 인코더에서는 최적의 율-왜곡 값을 계산하기 위하여 SAD (sum of absolute difference), SATD (sum of absolute transformed difference), SSE (sum of square error)의 세 가지 cost 함수를 사용한다. 이러한 cost 함수들은 HEVC 참조 소프트웨어인 HM을 기준으로 인코더 전체 복잡도의 30% 이상의 높은 비율을 차지한다 [9] . HM 인코더의 전체 동작 사이클에서 각 cost 함수가 차지하는 비율을 살펴보면 다음과 같다. 먼저, SAD 와 SATD는 각각 정수화소와 분수화소의 움직임 예측에서 원본 영상 블록과 예측 영상 블록간의 차를 구하는데 사용되며, HM 인코더의 전체동작 사이클에서 SAD는 10~12%, SATD는 15~16%의 비율을 차지한다. 또한, SSE는 최적의 율-왜곡 값을 계산하는데 사용되는 연산으로 HM 인코더의 전체 동작 사이클에서 2~3%의 비율을 차지한다. 전술한 세 연산은 모두 블록 단위로 수행되며, 여러 데이터에 대하여 동일한 연산을 수행하기 때문에 SIMD 명령어를 적용하기에 적합한 연산으로 꼽을 수 있다. 본 논문에서는 4×4 블록에서 64×64 블록에 대한 SAD, SSE 연산과 4×4, 8×8 SATD 연산을 SIMD 명령어를 사용하여 구현하였다.
먼저, SAD는 블록의 크기에 따라 원본 영상 블록과 예측영상 블록간의 차에 대한 절댓값의 합을 구하는 함수이다. 8비트 입력 데이터의 경우, 16개의 데이터에 대해 2개의 레지스터를 사용하여 16개 데이터에 대한 SAD를 한 번에 구할 수 있는 정수형 128비트 산술 연산 PSADBW 명령어를 사용하였다. PSADBW는 그림 1 과 같이 8비트 16개의 데이터에 대해 상위 8개의 SAD를 상위 16비트에 저장하고, 하위 8개의 SAD를 하위 16비트에 저장한다. SATD의 경우 하다마드 변환을 이용하여 원본 영상 블록과 예측 영상 블록과의 차를 입력으로 덧셈 및 뺄셈 연산만을 사용하여 변환된 계수를 구하고 해당 계수들의 절댓값의 합을 구하는함수이다. HM에서는 SATD 연산을 위해 butterfly 형태로 표현하였으며 2×2를 예로 그림 2 와 같이 표현할 수 있다. 이러한 덧셈, 뺄셈 및 절댓값 연산에 대해 SIMD 명령어를 통해 최적화 하였다. SSE의 경우 원본 영상과 예측 영상과의 차분에 대한 제곱합을 구하는 함수이다. SSE 역시 16비트 8개의 데이터에 대해 차값을 구하기 위하여 PSUBW 명령어를 사용하였고, PMADDWD 명령어를 통해 제곱합을 구하는데 사용하였다.
PPT Slide
Lager Image
PSADBW 명령어 Fig. 1. PSADBW instruction
PPT Slide
Lager Image
Butterfly 방식을 이용한 2×2 SATD Fig. 2. 2×2 SATD using butterfly method
- 2. 변환 및 역-변환
1절에서 전술한 cost 함수 외에도 비디오 코덱에서 SIMD 명령어를 적용하기 적합한 대표적인 연산으로 변환 및 역-변환을 꼽을 수 있다. HEVC에서는 기존의 비디오 코덱에 비하여 큰 단위의 변환 커널을 사용하고 쿼드-트리(quad-tree)구조의 TU를 사용함으로서 부호화 성능을 향상시킬 수 있었다. HEVC는 기존 비디오 코덱에서 사용되던 4×4 및 8×8 크기의 변환 커널 뿐만 아니라, 16×16 및 32×32 크기의 큰 변환 커널을 채택하고 있다. 특히, HM 인코더 소프트웨어에서는 행렬 곱 형태의 변환 및 역-변환뿐만 아니라 변환의 고속화를 위하여 partial butterfly 방식의 변환/역-변환을 지원하고 있다. 하지만, 다양한 크기의 변환 커널의 지원과 쿼드-트리구조의 TU의 사용으로 인하여 연산 복잡도는 크게 증가하였다. 본 논문에서는 변환 및 역-변환에 대하여 SIMD 명령어를 적용하여 연산 복잡도를 감소시킬 수 있었다.
변환 및 역-변환에 대해 SIMD 명령어를 적용함에 있어서 본 논문에서는 순차적인 산술 연산에 유리한 행렬 곱형태를 사용하여 나타낸다. 그림 3 은 4×4 역-변환에 대한 SIMD 명령어 적용을 나타낸다. 그림 3 에서는 변환 및 역-변환에 있어서 수직 방향의 메모리 로드가 필요하게 되므로 메모리 접근의 효율성이 떨어지게 된다. 이러한 문제점을 해결하기 위하여, 전치행렬 형태로 메모리에 저장하여 수직 방향의 메모리 로드로 발생하는 연산량을 줄일 수 있었다. 변환 및 역-변환에서 계수들은 16비트 데이터이므로 중간 연산과정이 32비트인 점을 고려하면 4개의 데이터에 대해 동시 처리가능하다.
PPT Slide
Lager Image
SIMD 명령어를 이용한 4×4 역-변환 Fig. 3. 4×4 inverse-transform using SIMD instruction
- 3. 보간 필터
HEVC 인코더에서 cost 함수, 변환 및 역-변환과 더불어 가장 높은 복잡도를 차지하는 연산은 보간 필터로서 인코더 전체 복잡도의 30%를 차지한다. HEVC는 휘도 성분에 대해서는 8-tap 과 7-tap DCT-IF, 채도 성분에 대해서는 4-tap DCT-IF를 사용하여 화소 보간을 수행한다. DCT-IF란, 역 DCT 과정에서 분수 화소 위치를 복원하는 계수를 구할 수 있으며, 이 계수 값을 이용하여 화소를 보간하는 필터 기술을 의미한다. HEVC의 DCT-IF는 tap 계수와 함께 산술 연산 및 메모리 참조가 증가하여 HEVC 인코더 복잡도 또한 크게 증가하였다 [10] . 하지만, 전술한 보간 필터와 같은 필터 연산의 경우 SIMD 명령어를 사용하여 DLP를 적용하기 적합한 구조이며, 본 논문에서는 보간 필터의 연산 복잡도를 낮추기 위하여 다음과 같은 과정을 수행하였다.
먼저 수평방향에 대해서는 8개의 데이터를 동시처리하기 위해 그림 4 와 같이 15개의 정수 화소가 필요하며, 따라서 8비트 16개의 데이터를 한 번에 로드하여 처리할 수 있다. 수직 방향에 대해서는 8개의 데이터를 동시처리하기 위해 그림 5 와 같이 64개의 정수 화소가 필요하며, 하나의 결과를 얻기 위해 수직방향으로 데이터를 로드하는 반면, 그림 5 와 같은 구조의 경우 64개의 데이터를 수평방향으로 로드함에 따라 수직방향 로드에 대한 연산량이 감소하게 된다. 이와 같은 구조를 통해 각 데이터를 레지스터에 할당하여 PADDW 및 PMULLW 명령어를 사용하여 산술 연산을 수행하였다.
PPT Slide
Lager Image
SIMD 명령어를 이용한 수평방향에 대한 보간 필터 Fig. 4. Horizontal directional interpolation filter using SIMD instruction
PPT Slide
Lager Image
SIMD 명령어를 이용한 수직방향에 대한 보간 필터 Fig. 5. Vertical directional interpolation filter using SIMD instruction
Ⅲ. CPU/GPU 멀티스레딩 기법을 이용한 HEVC 인코더 병렬화
본 장에서는 HEVC 인코더의 병렬화를 위한 CPU 및 GPU를 이용한 멀티스레딩 기법에 대하여 소개한다. 2장에서 소개한 SIMD 명령어를 통한 DLP와 더불어 비디오 코덱의 병렬처리를 위하여 널리 사용되고 있는 CPU 및 GPU를 이용한 멀티스레딩 기법은 SIMD 명령어보다 상위 수준의 병렬처리에 주로 사용된다. 본 장의 1절에서는 OpenMP를 이용한 CPU 멀티스레딩 기법을 슬라이스 및 타일 단위 병렬처리에 적용, 2절에서는 CUDA를 이용한 GPU 멀티스레딩 기법을 프레임 단위 움직임 예측에 적용하고, GPU 기반 움직임 예측을 통해 획득한 정보를 이용하여 GPU에서 블록 분할 (block partition) 결정을 수행하여 최적의 모드를 고속으로 결정하였다.
- 1. CPU multi-threading 기법을 이용한 슬라이스/타일 단위 병렬화
OpenMP는 CPU 환경의 다중 프로세싱을 지원하는 API로 포크-조인 (fork-join)모델에 기반하여 다양한 응용의 병렬처리에 사용되고 있다. 본 연구에서는 HEVC 인코더를 위한 CPU 멀티스레딩을 수행하기 위하여 OpenMP를 사용하였다. 병렬화 기법을 적용하기에 앞서, 적용하고자 하는 병렬화 기법의 선택을 위한 부호화 속도 개선, 부호화 성능, 코어의 확장성 등의 여러 요인들에 대한 고려가 필요하다. 먼저, 병렬처리에 따른 속도향상은 비디오 인코더의 병렬화의 가장 중요한 요소로서 단일 코어 대비 다중 코어를 이용한 병렬처리를 통해 얻을 수 있는 부호화 속도 개선을 의미한다. 이와 더불어, 병렬화의 주요한 고려사항으로 병렬처리에 따른 부호화 효율의 저하를 꼽을 수 있다. 다중코어를 사용한 병렬처리를 통하여 높은 속도 개선이 있더라도, 부호화 성능의 저하가 크다면 좋은 병렬화 기법이라고 할 수 없다. 마지막으로 코어의 확장성은 병렬화 기법이 허용하는 코어 개수를 의미하며, 이는 목적 플랫폼에 따라 부호화 속도에 영향을 받을 수 있다.
HEVC는 표준화의 시작 단계에서부터 병렬화 기술에 대한 고려가 이루어졌으며, 표준화 과정에서 다양한 병렬화 기술들이 제안되었다. HEVC version 1의 표준화 완료시점인 2013년 1월을 기준으로 HEVC MP (main profile)에 포함된 병렬화 기술은 타일과 WPP (wave-front parallel processing) 두 가지 기술이다. 여기에 덧붙여 비디오 코덱의 병렬처리에 널리 사용되고 있는 전송을 위한 분할 단위인 슬라이스를 병렬처리 관점에서 생각할 경우, HEVC에 적용 가능한 병렬화 도구들로 크게 슬라이스, 타일, WPP를 꼽을 수 있다. 따라서, 전술한 HEVC 병렬화 도구들을 기준으로 비디오 압축 표준을 위한 DLP는 크게 WPP와 같은 부호화 유닛 단위 병렬처리, 슬라이스와 타일 단위 병렬처리 및 프레임 단위 병렬처리로 나눌 수 있다. 부호화 유닛 단위 및 프레임 단위 병렬화의 경우, 인접한 블록 혹은 프레임에 대한 의존성이 높기 때문에 병렬처리에 따른 부호화 성능 저하를 최소화 할 수 있으나, 높은 속도 향상은 기대하기 어렵다. 반면, 슬라이스와 타일은 모드결정 및 예측, 엔트로피 부호화를 포함한 일련의 부호화 과정들을 인접한 슬라이스와 타일과 독립적으로 수행하기 때문에 병렬처리를 수행하는 슬라이스와 타일의 개수에 따라 부호화 성능에 영향을 받는다. 하지만, 본 연구에서는 실시간 HEVC 부호화에 초점을 맞추었기 때문에, 병렬화에 따른 높은 속도 향상을 얻을 수 있는 슬라이스와 타일 단위 병렬화를 선택하였다.
본 논문에서는 그림 6 과 같이 슬라이스와 타일 단위 병렬처리를 위해 하나의 프레임을 슬라이스와 타일로 분할하고, 분할된 슬라이스와 타일별로 스레드를 할당하였다. 그림 6 은 슬라이스와 타일의 병렬처리에 따른 스레드 할당 및 부호화 순서이며, 각 스레드는 해당 슬라이스와 타일에 포함된 CTU를 Z-스캔 순서에 따라 병렬적으로 부호화를 수행한다. HM 소프트웨어를 기반으로 슬라이스와 타일별로 스레드를 할당하기 위하여 OpenMP를 사용하였으며, 병렬 부호화에 필요한 다양한 클래스 인스턴스들을 스레드 개수에 맞춰 생성하여 슬라이스와 타일 단위 병렬화를 수행하였다. 표 1 은 HM에서 슬라이스와 타일 단위 병렬화를 수행하기 위하여 스레드 개수와 동일하게 생성하여야하는 인스턴스와 그 역할에 대하여 나타낸다. 해당 인스턴스들은 HM 인코더의 최상위 부호화 클래스인 TEncTop 클래스 내부에 선언되어 있으며, 하위 인코더 (GOP, 슬라이스, CU 인코더) 클래스들은 해당 인스턴스들을 포인터 형태로 참조하도록 구현되어있다. 표 1 의 클래스 중 슬라이스 인코더는 슬라이스 병렬처리를 사용하는 경우에만 스레드의 개수에 맞춰 생성되며 타일 병렬처리에서는 스레드 개수에 맞춰 생성된 CU 인코더를 사용하여 각 타일을 병렬로 처리한다. 또한, CABAC과 관련된 인스턴스들의 경우, RDO를 위한 CABAC 인코더와 비트스트림 생성을 위한 CABAC 인코더가 별도로 선언되어 있으므로 RDO를 수행하는 경우에는 두 종류의 CABAC 인코더를 모두 스레드 개수에 맞춰 생성하여야 한다.
PPT Slide
Lager Image
슬라이스와 타일의 병렬처리에 따른 스레드 할당 및 부호화 순서 ((a) 4 슬라이스, (b) 4 타일) Fig. 6. Threads allocation and coding order according to parallel processing of slice and tile ((a) 4 slices, (b) 4 tiles)
슬라이스와 타일 병렬처리를 위한 쓰레드별 요구 인스턴스의 클래스 및 역할
PPT Slide
Lager Image
Table 1. Required classes and roles of instances for parallel processing of slice and tile
- 2. GPU 멀티스레딩 기법을 이용한 움직임 예측 병렬화
많은 기술발전으로 GPU (graphics processing unit)의 메모리 대역폭 및 계산능력이 CPU (central processing unit)를 넘어섰다. 또한, GPU의 고정 파이프라인이 프로그래밍이 가능한 모듈로 대치되면서 GPU를 이용하여 그래픽 처리 및 3D 렌더링뿐만 아니라 많은 계산량을 요구하는 일반적인 과학 및 공학적 문제를 해결하는 GPGPU (generalpurpose computing on GPU) 기술이 연구되어 왔다. NVidia는 이러한 추세에 맞춰 CUDA (compute unified device architecture)로 대표되는 GPU를 이용한 병렬 프로그래밍 프레임워크를 발표하였다 [11] . CUDA의 등장으로 선형대수, 시뮬레이션, 영상신호처리 등과 같은 공학 분야에서 GPU를 이용한 고속화 방법들이 연구되어 왔으며, 비디오 코덱분야에서도 코덱의 고속화를 위하여 복잡한 모듈에 대한 병렬화 기법들이 연구되어 왔다. 특히, 비디오 코덱에서는 많은 양의 화소 데이터에 대하여 동일 연산을 반복해서 수행하는 움직임 예측이나 보간 필터, 변환-역변환에 적용하는 연구가 활발하게 이루어지고 있다 [12] [13] [14] . 움직임 예측모듈은 HM 인코더에서 70~80%정도의 복잡도를 차지하며, 많은 양의 화소 데이터에 대하여 동일 연산을 반복해서 수행하는 가장 대표적인 연산으로 GPU 적용이 적합한 연산 모듈이다. 보간 필터의 경우에도 GPU 멀티스레딩 기법의 적용이 적합하지만 보간 필터만을 단독으로 GPU에서 수행하는 경우 CPU와 GPU 사이에 메모리 전송 오버헤드가 커지는 문제점이 발생한다. 따라서, 보간 필터에 대한 병렬화를 GPU에서 수행하는 경우에는 보간 필터의 단독적인 수행보다는 보간 필터와 분수 화소 단위 움직임 예측이 결합되어 사용되어야한다.
본 연구에서는 HEVC 인코더에서 GPU 적용이 가능한 다양한 연산 중 움직임 예측, 보간 필터 및 블록 분할 결정에 적용하여 병렬화를 수행하였다. 이 움직임 예측 방법은 현재 프레임 내에 존재하는 모든 가능한 PU들의 움직임 벡터를 획득한다. GPU의 수천 개의 스레드를 사용하여 높은 병렬성을 얻기 위해 움직임 예측을 프레임 단위로 수행하는데, 이를 위해서는 HEVC에 존재하는 인접 CU 및 PU간의 종속성 문제를 해결해야 한다. HEVC는 AMVP (advanced motion vector prediction)를 통해 인접 CTU 혹은 PU의 움직임 정보를 참조하여 예측 움직임 벡터 (MVP : motion vector predictor)를 결정하고, 이를 움직임 예측을 위한 탐색영역의 기준으로 사용한다. 즉, 주변 CU들의 부호화가 완료되어야 현재 CU에 대한 AMVP를 수행할 수 있다. 이런 CU 간의 종속성을 제거하기 위해 이전 프레임의 움직임 벡터를 이용하여 현재 CTU의 MVP를 획득한다. 참조 프레임의 대응 (co-located) CTU 내의 모든 움직임 벡터의 평균을 취하여 대표 TMVP (temporal MVP)를 생성하고 이를 현재 CTU의 MVP로 사용한다. 따라서, 한 CTU내의 모든 PU들은 동일한 MVP를 사용하게 된다. 탐색 방법은 전역탐색 (full-search)를 사용하고, 작은 PU들의 SAD를 더하여 더 큰 PU의 SAD를 도출해 내는 계층적 SAD 계산 (hierarchical SAD computing)과 여러 율-왜곡값 중에서 최솟값을 찾기 위한 CPR (concurrent parallel reduction) 알고 리듬을 적용하였다[ 15 ]. 또한, 보다 정밀한 움직임 예측을 위해 참조 프레임에 대한 보간 필터 수행과 [16] 분수 화소 단위 움직임 예측도 GPU에서 수행하였다. GPU에서 보간필터를 수행함으로써 알고리듬 고속화와 CPU와의 통신을 최소화할 수 있었다. 그림 7 은 GPU 기반 움직임 예측 방법을 적용한 HEVC 인코더의 흐름도를 나타낸다.
PPT Slide
Lager Image
GPU 기반 움직임 예측을 이용한 HEVC 인코더 흐름도 Fig. 7. HEVC encoder flow chart using GPU-based motion estimation
HEVC는 다양한 부호화 블록 크기에 대한 재귀적 모드결정 방법으로 연산 복잡도가 크게 증가하였다. 본 연구에서는 본 절에서 설명한 GPU 기반 움직임 예측을 통해 얻은 정보를 이용하여 GPU에서 블록 분할 결정을 수행하고, 최적 블록 분할에 대한 정보를 CPU로 전송한다. 이를 통해 CPU상에서 수행하는 RDO 과정에 대한 부하를 줄여 부호화 속도를 향상시켰다. GPU는 움직임 예측을 통해 얻은 최적의 율-왜곡값을 기준으로 RDO 과정을 수행하여 각각의 CTU의 최적의 깊이, 움직임 벡터, 예측 블록을 생성한다. CPU에서는 RDO를 수행하지 않고, 이 정보들을 이용하여 변환 및 양자화, 엔트로피 코딩 등을 수행한다. 그림 8 은 GPU 기반 움직임 예측 방법 및 움직임 정보를 이용한 블록 분할 결정을 적용한 부호화기의 흐름도를 나타낸다.
PPT Slide
Lager Image
GPU 기반 움직임 예측 및 블록 분할 결정을 이용한 부호화기 흐름도 Fig. 8. HEVC encoder flow chart using GPU-based motion estimation and block partition decision
Ⅳ. 실험결과
본 장에서는 다양한 병렬화 기법을 적용한 HEVC 인코더의 부호화 속도를 측정하고 이에 대하여 분석한다. HEVC 인코더의 부호화 속도 측정을 위하여, HEVC 참조 소프트웨어인 HM 10.0을 기반으로 C 변환 및 최적화를 수행한 소프트웨어에 SIMD 명령어, OpenMP 기반 CPU 멀티스레딩, CUDA 기반 GPU 멀티스레딩 병렬화 기법을 적용하였다. 본 연구에서 제안하는 병렬화 기법들을 적용한 HEVC 인코더의 부호화 속도를 측정하기 위하여 표 2 의 실험 환경에서 HEVC 공통 실험 조건 [17] 에 따라 소프트웨어를 동작시켰다. 부호화 속도의 측정은 PC 환경에서의 프로그램 동작 시간을 초단위로 측정하였으며, 초당 영상 프레임 처리 수 (FPS : frames per second)를 계산 하였다. 또한, 각 병렬화 기법을 적용하여 향상된 속도의 측정은 수식 (1)의 ATS (average time saving)을 사용하여 제시한다. Etimeanchor 는 병렬화를 적용하기 이전의 부호화 시간을 의미하며, Etimeproposed 는 본 논문에서 제안하는 병렬화를 적용한 이후의 부호화 시간을 의미한다.
PPT Slide
Lager Image
HEVC 인코더 병렬처리를 위한 실험환경
PPT Slide
Lager Image
Table 2. Test environment for parallel processing of HEVC encoder
표 3 은 본 연구에서 SIMD 명령어를 적용하기 전과 후의 부호화 속도 향상을 나타낸다. SIMD 명령어를 적용하여 부호화 손실 없이 평균 45.92%의 ATS 효율을 얻을 수 있었다. SIMD 명령어를 적용한 연산별로 속도 향상을 살펴보면, SAD, SATD, SSE의 cost 함수의 경우 평균 4배의 연산 속도 향상을 나타내었으며, 변환 및 역-변환의 경우 partial butterfly 방식 대비 평균 3~4배의 연산 속도 향상을 나타내었다. 또한, 보간 필터의 경우 평균 4배의 연산 속도 향상을 나타내었다.
SIMD 명령어들을 이용한 DLP에 따른 HEVC 인코더의 부호화 속도 향상
PPT Slide
Lager Image
Table 3. Average time saving of HEVC encoder according to DLP using SIMD instructions
그림 9 는 본 연구에서 수행한 CPU 단위 멀티스레딩 기법을 사용하여 슬라이스 및 타일 단위 병렬처리 수와 그에 따른 부호화 속도 향상을 나타낸 그래프이다. 슬라이스와 타일은 최대 16개까지 분할하여 실험을 진행하였으며, 4개 슬라이스와 타일로 분할한 경우 평균 3.2배의 부호화 속도 향상을 얻을 수 있었다. 또한, 8개 슬라이스와 타일로 분할한 경우 평균 4.5배의 부호화 속도 향상이 있었으며, 16개 슬라이스와 타일로 분할한 경우 평균 5.5배의 부호화 속도 향상을 얻을 수 있었다. CPU 멀티스레딩 기법을 이용한 병렬화 기법의 경우 타겟 플랫폼이 지원하는 최대 스레드 수에 영향을 받으며, 슬라이스와 타일 수를 증가시키더라도 부호화 속도가 선형적으로 증가하지 않는다. 따라서 적용하고자하는 타겟 플랫폼에서 가장 효율적인 슬라이스와 타일 분할 수에 대한 결정이 필요할 것으로 예상된다.
PPT Slide
Lager Image
슬라이스와 타일 수에 따른 부호화 속도 향상 Fig. 9. Speed up of encoding time according to the number of slices and tiles
GPU 멀티스레딩 기법의 속도향상을 측정하기 위해 정수화소 움직임 예측 모듈의 수행시간을 측정하였다. GPU 기반 움직임 예측이 프레임 단위로 수행됨으로 anchor에 해당하는 HM 10.0의 정수화소 움직임 예측 방법의 수행시간도 프레임 단위로 측정하였다. GPU 기반 움직임 예측의 수행시간에는 CPU와 GPU 간의 통신시간을 포함시켰다. 실험을 위하여 Geforce GTX 470을 사용하였다. 표 4 는 HM의 전역탐색 및 고속탐색 대비 GPU 기반 정수화소 움직임 예측 모듈의 속도향상을 나타낸다. 전역탐색의 경우 평균 364배의 속도향상을 보이며, GPU 기반 움직임 예측이 전역탐색 방법을 사용함에도 불구하고 HM의 고속탐색 방법 대비 평균 11배의 속도향상을 보인다.
GPU 멀티스레딩을 이용한 정수화소 움직임 예측의 속도 향상
PPT Slide
Lager Image
Table 4. Speed up of integer-pel motion estimation execution time using GPU multi-threading
본 논문에서는 소개한 SIMD 명령어를 사용한 다양한 연산 및 기능 모듈에 대한 DLP와 CPU 및 GPU 멀티스레딩 기법을 적용한 병렬처리를 통하여 HEVC 인코더의 부호화 속도를 향상시켰다. 연산 및 기능 모듈 관점에서는 SIMD 명령어를 사용하여 cost 함수, 변환 및 역-변환, 보간 필터에 DLP를 적용하였다. 또한, CUDA를 이용한 움직임 예측 및 모드 결정에 GPU 멀티스레딩 기법을 적용하였다. 부호화 구조 관점에서는 OpenMP를 이용한 슬라이스 및 타일 병렬처리를 수행하여 CPU 멀티스레딩 기법을 적용하였다. 전술한 병렬화 기법들을 종합하여 소프트웨어 기반 실시간 HEVC 인코더를 구현하여 측정한 부호화 속도는 표 5 와 같다. 실험을 위한 부호화 구조는 LDP (low-delay P)를 사용하였으며, QP는 22, 27, 32, 37을 사용하였다. 또한, 참조픽쳐의 수는 1개로 고정하였으며, 최대 CTU 크기는 32×32를 사용하여 부호화를 수행하였다.
제안하는 병렬화 기법들을 적용한 HEVC 인코더의 부호화 속도 측정 결과
PPT Slide
Lager Image
Table 5. Encoding time of HEVC encoder with proposed parallel processing methods
Ⅴ. 결 론
본 논문에서는 소프트웨어 기반 실시간 HEVC 인코더 구현을 위하여 다양한 병렬화 기법에 대하여 소개하고, 이를 적용하기 용이한 연산 및 기능 모듈을 소개하였다. 서로 다른 데이터에 대한 동일한 연산을 반복적으로 수행하는 cost 함수, 변환 및 역-변환, 보간 필터에 SIMD 명령어를 적용하여 DLP를 수행하였다. SIMD 명령어를 이용한 DLP를 적용하여 HEVC 인코더 소프트웨어의 부호화 속도를 부호화 효율의 저하 없이 약 2배 향상시킬 수 있었다. 또한, OpenMP를 이용한 CPU 멀티스레딩 기법을 통해 슬라이스 및 타일 단위 병렬처리를 수행하였으며, CUDA를 이용한 GPU 멀티스레딩 기법을 통해 움직임 예측 및 모드 결정에 대한 병렬처리를 수행하였다. OpenMP를 이용한 CPU 멀티스레딩 기법을 적용하여 4개 슬라이스와 타일로 분할하는 경우 약 3.5배의 부호화 속도 향상을 얻을 수 있었으며, 16개로 분할하는 경우에는 약 6배의 부호화 속도 향상을 얻을 수 있었다. 전술한 다양한 병렬화 기법을 적용하여 HEVC 인코더의 부호화 속도를 832×480 영상의 경우 10~30fps, 1920×1080 영상의 경우 5~10fps로 향상시킬 수 있었다. 본 논문에서는 SIMD 명령어를 이용한 DLP를 cost 함수, 변환 및 역-변환, 보간 필터에 적용하였으나, 이외에도 화면 내 예측 수행과정에서의 참조샘플 필터 연산, 복원 영상 생성 등 SIMD 명령어를 적용할 수 있는 연산 및 모듈이 존재한다. 또한, CPU 및 GPU 멀티스레딩 기법의 병렬처리 속도 향상을 위하여 고속화 알고리즘 연구가 필요할 것으로 예상된다. 현재 832×480 영상의 경우 실시간 부호화가 가능하지만, 2K 및 4K 영상에 대한 실시간 부호화가 가능한 HEVC 인코더 개발을 위하여 추가적인 소프트웨어 최적화 및 병렬화 연구를 진행할 계획이다.
BIO
안 용 조
- 2010년 2월 : 광운대학교 컴퓨터공학과 학사
- 2012년 2월 : 광운대학교 컴퓨터공학과 석사
- 2012년 3월 ~ 현재 : 광운대학교 컴퓨터공학과 박사과정
- 주관심분야 : 영상압축, 최적화 및 병렬화
황 태 진
- 2012년 2월 : 광운대학교 컴퓨터공학과 학사
- 2012년 3월 ~ 현재 : 광운대학교 컴퓨터공학과 석사과정
- 주관심분야 : 영상압축, 멀티미디어시스템
이 동 규
- 2012년 2월 : 광운대학교 전자공학과 학사
- 2012년 3월 ~ 현재 : 광운대학교 전자공학과 석사과정
- 주관심분야 : 영상압축, 컴퓨터비전
김 상 민
- 2013년 2월 : 광운대학교 전자공학과 학사
- 2013년 3월 ~ 현재 : 광운대학교 전자공학과 석사과정
- 주관심분야 : 영상압축, 최적화 및 병렬화
오 승 준
- 1980년 2월 : 서울대학교 전자공학과 학사
- 1982년 2월 : 서울대학교 전자공학과 석사
- 1988년 5월 : 미국 Syracuse University 전기/컴퓨터공학과 박사
- 1982년 3월 ~ 1992년 8월 : 한국전자통신연구원 멀티미디어연구실 실장
- 1986년 7월 ~ 1986년 8월 : NSF Supercomputer Center 초청 학생연구원
- 1987년 5월 ~ 1988년 5월 : Northeast Parallel Architecture Center 학생연구원
- 1992년 3월 ~ 1992년 8월 : 충남대학교 컴퓨터공학부 겸임교수
- 1992년 9월 ~ 현재 : 광운대학교 전자공학과 교수
- 2002년 3월 ~ 현재 : SC29-Korea 의장 및 MPEG Forum 부의장
- 주관심분야 : 비디오 데이터 처리, 영상압축, 멀티미디어시스템
심 동 규
- 1993년 2월 : 서강대학교 전자공학과 공학사
- 1995년 2월 : 서강대학교 전자공학과 공학석사
- 1999년 2월 : 서강대학교 전자공학과 공학박사
- 1999년 3월 ~ 2000년 8월 : 현대전자 선임연구원
- 2000년 9월 ~ 2002년 3월 : 바로비젼 선임연구원
- 2002년 4월 ~ 2005년 2월 : University of Washington Senior research engineer
- 2005년 3월 ~ 현재 : 광운대학교 컴퓨터공학과 교수
- 주관심분야 : 영상신호처리, 영상압축, 컴퓨터비전
References
Sulivan G. J. , Ohm J.-R. 2010 “Recent developments in standardization of high efficiency video coding (HEVC),” SPIE Application of Digital Image Proc. XXXIII. Aug. vol. 7798 7798 - 30
JCT-VC 2010 “Report of subjective test results of responses to the joint call for proposals (CfP) on Video coding technology for high efficiency video coding (HEVC),” Dresden, DE Document JCTVC-A204
Gweon R. H. , Lee Y.-L. , Lim J. 2011 "Early termination of CU encoding to reduce HEVC complexity,” ITU-T/ISO/IEC Joint Collaborative Team on Video Coding (JCT-VC) document JCTVC-F045
Choi K. , Jang E. S. 2011 “Coding tree pruning based CU early termination,” ITU-T/ISO/IEC Joint Collaborative Team on Video Coding (JCT-VC) document JCTVC-F092
Wang J. , Kim J. , won K. , Lee H. , Jeon B. 2011 “Early skip detection for HEVC,” ITU-T/ISO/IEC Joint Collaborative Team on Video Coding (JCT-VC) document JCTVC-G543
Yan L. , Duan Y. , Sun J. , Guo Z. 2012 “Implementation of HEVC decoder on x86 processor with SIMD optimiation” CVIP Nov. 1 - 6
Chen K. , Duan Y. , Yan L. , Sun J. , Guo Z. 2012 “Efficient SIMD optimization of HEVC encoder over x86 processor” APSIPA ASC 2012 Asia-pacific Dec. 1 - 4
Alvarez-Mesa M. , chi C. C. , George V. , Schierl T. , Juurlink B. 2012 “Parallel video decoding in the emerging HEVC standard,” Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2012) Kyoto, Japan March
Ahn Y. J. , Hwang T. J. , Yoo S. E. , Han W.-J. , Sim D. G. 2012 "Statistical characteristics and complexity analysis of HEVC encoder software" Journal of Broadcasting & Electronic Media 17 (6) 1091 - 1105
Ahn Y. J. , Han W. J. , Sim D. G. 2012 “Study of decoder complexity for HEVC and AVC standards based on tool-by-tool comparision” SPIE Applications of Digital Image Proc. XXXV. Aug. vol. 8499 8499 - 32
NVIDIA 2012 “CUDA C programming guide,” document PG-02829-001_v5.0
Chen W.-N. , Hang H.-M. 2008 “H.264/AVC motion estimation implementation on compute unified device architecture (CUDA)” IEEE International Conference on Multimedia and Expo 2008 (ICME'08) April 697 - 700
Cheung N.-M. , Fan X. , Au O. C. , Kung M.-C. 2010 “Video coding on multi-core graphics processors,” in Proc. IEEE Siganl Process. Mag. 78 - 89
Jing Z. , Liangbao J. , Xuehong C. 2011 “Implementation of parallel full search algorithm for motion estimation on multi-core processors.” The 2nd International Conference on Next Generation Information Technology (ICNIT) June 31 - 35
Lee D.-K. , Oh S.-J. 2013 “Variable block size motion estimation implementation on compute unified device architecture (CUDA)” IEEE International Conference on Consumer Electronics Jan. 635 - 636
Kim S. , Lee D. , Ahn Y. , Hwang T.-J. , Sim D. , Oh S.-J. 2013 “DCT-based interpolation filter for HEVC on Graphics processing units” International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC) July 155 - 158
Bossen F. 2011 “Common test conditions and software reference configuration,” ITU-T/ISO/IEC Joint Collaborative Team on Video Coding (JCT-VC) document JCTVC-G1200