워프 스케쥴링 기법에 따른 GPU 성능 분석

요약

GPU에서 실제 연산을 담당하는 세이더코어는 다수의 워프를 동시에 할당받아 수행함으로써, 연산자원 활용률을 극대화한다. 세이더코어가 할당받은 다수의 워프들 중에서 어떠한 워프를 선택하여 수행하는지에 따라 GPU의 성능은 달라질 것으로 예상된다.
효과적인 워프 스케줄링 기법을 개발하기 위해서는 워프 스케줄링 기법의 특성 분석이 선행되어야 한다. 본 논문에서는 워프 스케줄링 기법에 따른 GPU의 성는을 분석하고자 한다. 무작위 스케쥴링, 라운드로빈 스케쥴링, 그리고 선입선처리 스케쥴링 기법을 분석 대상으로 사용한다. 실험 결과에 따르면, 분기 명령어를 포함하지 않는 응용프로그램을 수행하는 경우에는 스케쥴링 기법에 따른 성능 차이가 거의 없는 반면에, 분기 명령어를 다수 포함하는 응용프로그램을 수행하는 경우에는 스케쥴링 기법에 따른 성능 차이가 상당히 발생함을 알 수 있다. 그 이유는 분기 명령어는 워프 스케쥴링 기법에 따라 무작위적인 메모리 접근으로 유발되는 병목현상을 완화 또는 악화시키기 때문으로 분석된다.
본 논문의 분석 결과는 범용 응용프로그램을 수행하는 GPU를 위한 워프 스케쥴링 기법을 개발하고자 하는 경우 가이드라인을 제시할 수 있을 것으로 기대된다.
 

---

1. 서론

GPU는 병렬 처리 연산을 효과적으로 수행하기 위하여 설계된 프로세서로써, 응용프로그램의 데이터 병렬성을 최대한 활용하고자 다수의 스레드드들을 병렬적으로 수행한다.
 
GPU를 활용하여 범용 작업을 수행하는 기술을 그래픽 처리장치 병렬컴퓨팅(GPGPU; General Puerpose computation on the Graphics Processing Unit) 이라고 한다.
최근 GPU 회사들이 제공하는 응용 프로그램 인터페이스(API; Application Programmin Interface)를 활용하는 경우, 프로그래머들은 보다 쉽게 GPU이 높은 병렬성을 활용할 수 있다.
 
GPU는 단일 명령어 다중 데이터(SIMD; Single Instruction Multiple Data) 구조를 채택하고 있으며, 스레드 수준 병렬성을 향상시키기 위하여 스레드들을 SIMD 구조로 집단화한다. SIMD 구조로 집단화된 스레드 그룹들을 NVIDIA에서는 워프(warp)라 부른다. NVIDIA에서 명명한 워프는 32개의 스레드의 집합으로 GPU에서 연산을 수행하는 데 있어서 가장 기본적인 단위이다. GPU에서 워프를 수행하는 경우, 워프 내의 스레드들은 동일한 명령어를 순차적 명령어 실행 순서(in-order) 방식으로 명령어를 수행한다.
 
GPU는 세이더코어로 불리는 멀티스레드 프로세서를 다수 포함하고 있으며, 하나의 세이더코어는 다수의 스레드들을 동시에 수행한다.
세이더코어는 워프 안의 스레드들을 수행하기 위하여 데이터를 요구한다.
요구된 데이터가 지역 메모리에 존재하지 않는 경우, GPU는 메모리 요구를 처리하기 위하여 DRAM으로 접근한다.

• Problem: DRAM으로의 접근은 내부연결망을 사용하기 위한 경쟁으로 발생한 지연 + DRAM의 프리차리(precharge)와 행 활성화(row-active) 등으로 인한 오버헤드로 인해 수 백 사이클을 필요로 한다. 즉, DRAM으로 접근하는 수 백 사이클 동안 GPU의 연산은 정지된다.

▶ CPU
: 비순차적 명령어 실행 순서(out-of-order) 방식으로 명령어를 수행하기 때문에, 메모리 실패(miss)로 인한 정지 문제가 발생된 스레드는 문제를 해결하기 위하여 메모리 실패로 인해 수행이 정지된 명령어 대신 다른 명령어를 수행하도록 한다.
 
▶ GPU
: 순차적(in-order) 방식으로 명령어를 실행하기 때문에, 다른 명령어를 수행할 수 없다.

• Solution: 메모리 실패로 인한 정지 문제를 해결하기 위해, GPU는 정지된 스레드 대신 다른 스레드를 수행하게 하는 방식을 활용한다. 파이프라인의 정지를 유발하는 스레드 대신 다른 스레드를 수행하게 하는 기술을 FGMT(Fine-Grained Multithreading)라고 한다. 
  GPU에서 메모리 실패는 매우 많은 사이클을 요구하기 때문에, GPU는 매우 많은 수의 워프들을 할당받아 연산을 수행한다.

 
▶ CPU

• Problem: 기존의 CPU에서 운영체제에 의해 제공되던 일반적인 멀티태스킹에서는 스레드를 전환하는 경우, 수행 중인 파이프라인의 정보나 레지스터 값을 따로 저장해야 하는 문맥 교환(context switching)으로 성능 저하가 발생하였다.

 
▶ GPU

• Solution:FGMT 프로세서에서는 각 연산 장치에서 해당하는 파이프라인 단계를 독립적으로 수행하기 때문에, 수행 중이던 명령어와 스레드들의 PC와 레지스터 정보와 같은 문맥(context)이 저장된 레지스터 파일은 그 스레드가 종료될 때까지 유지된다. 그러므로 FGMT 기술을 사용하면 수행 중인 스레드를 다른 스레드로 변환하는 과정에서 수행 중인 파이프라인의 정보나 레지스터 값을 따로 저장하지 않기 때문에, 문맥 교환으로 인한 성능 저하는 발생하지 않는다.

 
▶ FGMT 기술
: FGMT 기술을 채택한 GPU에서는 각각의 세이더코어가 긴 메모리 접근 지연시간을 숨기기 위해 다수의 워프를 동시에 할당받아 수행한다. 다수의 워프들 중에서 어떠한 워프를 선택하여 수행하는지는 연산 자원과 메모리 시스템 자원의 활용률 측면에 큰 영향을 미칠 것으로 판단된다.
특히, 최신 GPU에서는 GPGPU 기술을 활용하여 다양한 범용 응용프로그램을 수행하며, 범용 응용프로그램은 그래픽 프로그램과 달리 수행 흐름이 불규칙하기 때문에 스케쥴링 기법에 따른 효율성 변화가 클 것으로 예상된다.
 
그러므로 본 논문에서는 워프 스케쥴링 기법에 따른 GPU의 성능을 다양한 종류의 범용 응용프로그램의 특성에 따라 분석하고자 한다. 
분석 결과는 GPGPU 기술을 지원하는 GPU에 적합한 워프 스케쥴링 기법을 개발하고자 하는 연구의 기반 자료로 활용될 것으로 기대된다.
 
 

2. GPU 구조

• CPU는 GPU에게 작업 명령과 병렬 데이털르 넘겨주고, GPU는 작업을 수행한 결과를 CPU에게 반환한다.

▶ GPU
: GPU는 다수의 세이더코어(SHADER CORE)와 내부연결망(INTERCONNECTION NETWORK) 그리고 DRAM으로 구성되어 있다.
 
▷ 세이더코어
: GPU 내부에 존재하는 각 세이더코어는 동일한 코드를 수행하는 다수의 스레드들을 동시에 실행시키며, 텍스쳐 캐쉬(TEXTURE CAHCE), 상수 캐쉬(CONSTANT CACHE) 그리고 L1 데이터 캐쉬(L1 DATA CACHE)와 같은 지역 메모리를 가지고 있다. 
세이더코어에서 수행되는 스레드들의 명령어는 세이더코어 내부의 연산 처리 장치(EXE UNITS)에서 순차적 명령어 실행 순서(in-order) 방식으로 수행된다.

• 세이더코어는 실행할 명령어가 선택되면, 상응되는 피연산자를 다수의 뱅크로 구성된 레지스터 파일(RF; Register File)로부터 읽어온다.
• 만약, 레지스터 파일에 원하는 데이터가 존재하지 않으면(miss) 세이더코어는 명령어 수행을 위해 필요한 데이터를 다수의 뱅크로 구성된 지역 메모리에 접근하여 요청한다. 불행히도 지역 메모리에서 메모리 요구(또는 데이터 요구)가 실패(miss)할 경우, 해당 메모리 요구가 하위 레벨 캐쉬 또는 DRAM으로 접근할 수 있도록 메모리 포트(MEM PORT)를 통해 요청한다. 특히, DRAM으로 접근되는 메모리 요구는 내부연결망을 통해 메모리 컨트롤러(MEMORY CONTROLLER)에 의해 처리된다.

세이더코어는 GPU에서 실제 연산을 담당하는 연산 수행 장치이다. 일반적으로 세이더코어의 수가 증가하면, 이에 비례하여 GPU의 병렬성 또한 증가한다.

• 최근 NVIDIA에서 출시한 Fermi 구조에서는 세이더코어와 같이 실제 연산을 수행하는 연산 장치를 스트리밍 멀티프로세서(SM; Streaming Multiprocessors)라는 용어를 사용하여 명명하기도 하지만, 본 논문에서는 세이더코어라는 용어를 사용하고자 한다.

GPU는 매우 많은 수의 세이더코어를 보유하고 있기 때문에, GPU 프로그래밍 모델에서 프로그래머가 같은 코드를 수행하는 데 있어서 수업이 많은 스레드를 생성하도록 허용함으로써 스레드 수준 병렬성을 극대화 시킬 수 있도록 지원한다.

• 하나의 세이더코어가 동시에 수행할 수 있는 최대의 스레드(또는 연산) 수를 표시하고자 하는 경우, 세이더코어의 SIMD 폭(width)이라는 용어를 사용한다.
  예) "세이더코어의 SIMD 폭이 32이다" == 세이더코어가 하나의 명령어로 동시에 최대 32개의 연산을 수행할 수 있다

따라서 GPU는 세이더코어에서 연산을 효율적으로 수행시키기 위해, 스레드들을 세이더코어의 SIMD 폭에 맞추어 집단화한다. 즉, 하나의 세이더코어에서 하드웨어적인 연산 자원에 따라 동시에 연산 가능한 최대의 스레드 수가 SIMD 폭과 동일하기 때문에, SIMD 폭만큼의 스레드들이 하나의 워프로 구성되는 것이 가장 효율적이라고 할 수 있다.
 

2.1 파이프라인

• Problem: GPU에서는 메모리 실패(miss)로 인한 손해가 매우 크다.
• Solution: GPU에서는 세이더코어에 매우 많은 수의 스레드들을 할당하고, 할당된 스레드들을 SIMD 폭의 수만큼 집단화하여 다수의 워프를 생성한다.

1. 워프들은 워프 풀(pool)에서 대기하고 있으며, 실행 준비가 완료된 레디 워프(ready warp)들 중 하나를 워프 선택 정책(warp scheduling)에 따라 워프 스케쥴러(Warp Scehdular)가 선택한다.
2. 선택된 워프는 자신의 프로그램 카운터(PC; Program Counter) 값으로 명령어 캐쉬에서 워프가 수행해야 하는 명령어를 인출(INSTRUCTION FETCH)한다.
3. 그리고 난 다음, 인출한 명령어를 해석(DECODE)하고, 해석된 명령어와 해당 워프와 상응하는 레지스터 파일에서 읽어 온 피연산자 값을 SIMD 파이프라인으로 보내 다수의 스칼라파이프라인을 활용하여 병렬적으로 연산을 수행한다.
   - 해당 워프와 상응하는 피연산자 값을 레지스터 파일에서 읽어오기 위하여 워프가 워프 스케쥴러에 의해 선택되면, 해당 워프의 ID(Warp ID)와 이에 상응하는 레지스터 ID(Reg ID)는 명령어가 인출 및 해석되는 동안 레지스터 파일로 보내진다.
   - SIMD 파이프라인은 다수의 스칼라파이프라인(SCALAR PIPELINE)으로 구성되어 있으며, 하나의 스칼라파이프라인은 하나의 스레드 연산을 수행한다. 따라서 스칼라파이프라인의 수는 SIMD 폭과 동일하다.
4. 모든 스레드 연산(또는 스칼라파이프라인)이 종료된 워프가 세이더코어의 파이프라인의 마지막에 도착하자마자, 해당 워프의 PC값을 포함한 모든 정보들이 갱신된다.
5. 다음에 수행할 명령어가 남은 워프는 워프 스케쥴러에 의해 다시 선택되어 세이더코어의 파이프라인을 반복하여 수행하고, 종료된 워프는 제거된다.

(그림 3)은 세이더코어 파이프라인에서의 연산을 수행하는 스칼라 파이프라인(SCALAR PIPELINE)의 집합인 SIMD 파이프라인 구조를 보여주고 있다.

• 스칼라파이프라인은 하나의 스레드 연산을 수행하고, 스칼라파이프라인의 집합인 SIMD 파이프라인의 폭은 워프 내의 최대 스레드 수와 동일한 N이다.

선택된 워프의 명령어를 수행하기 위해서 선택된 워프 내의 스레드들과 상응하는 레지스터 값이 각 스칼라파이프라인의 연산장치(ALU)로 들어간다.
ALU 연산 종료 후, 연산 결과는 지역 메모리에 접근(MEMORY ACCESS)하여 쓰기(WRITE BACK) 작업을 수행한다

1. 하지만 메모리 요구가 캐쉬에서 실패(miss)하면, 해당 워프는 메모리 실패 대기 장치(MSHR; Miss Status Hold Register)로 보내져 대기한다.
2. 해당 워프가 메모리 실패 대기 장치에서 대기하는 동안 메모리 요구는 메모리 시스템으로 보내진다. 그와 동시에, 파이프라인이 정지되지 않도록 실행 가능한 새로운 워프가 세이더코어에 할당되어 세이더코어 파이프라인을 시작한다.
3. 워프에서 요구하는 데이터를 메모리 시스템으로부터 읽어오면, 메모리 실패 대기 장치는 그 데이터를 레지스터와 지역 메모리에 적재하고, 파이프라인에서 순서를 기다려 재수행한다.

 

2.2 세이더코어 구조

• 인출 단계(FETCH): 인출기를 활용하여 워프를 선택하고, 선택된 워프의 PC값으로 명령어 캐쉬(INST.CACHE)에 접근하여 해당 명령어를 인출한다.
• 해석 단계(DECODE): 인출된 명령어는 해석 단계에서 해석되어 명령어 버퍼(INST.BUFFER)에 저장된다.
  만약 해석된 명령어가 분기명령어로 판별되면, 분기명령어가 수행되어 정확한 결과가 나오기 전까지는 그 워프의 다른 PC는 인출되지 않도록 처리한다.

▶ 명령어 버퍼
명령어 버퍼의 엔트리에 저장된 워프의 정보는 

• 현재 명령어의 상태: 해당 워프가 선택되어 실행 중이라면 무효(I: Invalid)로 표시되며, 선택되기 전이라면 유효(V: Valid)로 표시된다. 현재 명령어 상태가 무효라면, 인출기는 해당 워프의 다음 명령어를 인출할 수 있다.
• 현재 워프의 명령어: 해당 워프의 명령어 정보를 담고 있다. 
• 워프의 실행 준비 상태: 현재의 워프가 수행될 수 있는지 없는지를 표시하는 것으로, 스코어보드(SCORE BOARD)에 의해 제어된다. 실행 준비 상태는 해당 명령어의 피연산자가 레지스터에 적재되어 연산을 수행할 준비가 완료되면 스코어보드에 의해 준비(Ready) 상태로 표시된다. 

등 3가지이다. 
 
▶ 인출 단계(FETCH) & 해석 단계(DECODE)

1. 매 사이클마다 인출기는 워프와 워프의 정보를 저장할 명령어 버퍼 안의 엔트리를 선택한다.
2. 선택된 워프의 PC값에 따라 명령어 캐쉬로 접근하여 명령어를 인출한다.
3. 인출된 명령어는 해석되어 명령어 버퍼안의 선택된 엔트리에, 현재 명령어의 상태와 워프의 실행 준비 상태 정보와 더불어 입력된다.
   워프의 현재 상태를 명령어 버퍼와 스코어보드가 저장하고 있기 때문에 명령어 버퍼와 스코어보드의 정보를 활용하면 실행 준비가 완료된 워프들을 알 수 있다.

▶ 이슈 단계(ISSUE)
: 실행 준비가 완료된 워프들 중 하나를 워프 스케쥴링 기법에 따라 선택한다.
이슈 단계에서 하나의 워프를 선택할 때 분기 스택(BRANCH STACK)에서 선택된 워프의 분기 정보(PC, 활성화 스레드 정보, 결합 명령어)를 제공한다.
 
▶ 실행 단계(EXE)
: 선택된 워픈느 활성화 스레드 정보를 기반으로 활성화 스레드와 상응하는 레지스터 파일로부터 피연산자를 읽어와 해당 스칼라파이프라인에서 명령어에 따라 ALU 연산/MEM 연산을 수행한다.
 
▶ 쓰기 단계(WB)
: 수행 결과를 레지스터 파일에 쓰며, 분기스택과 스코어보드에 명령어 종료여부와 관련 정보를 통보한다. 즉, 명령어가 종료되면 분기스택과 스코어보드는 완료된 명령어와 관련된 정보를 업데이트 한다.
 
 

3. 워프

3.1 워프 생성 기법

• Problem: GPU에서 수행되는 경우 대부분의 응용프로그램에서의 성능 향상은 기대에 미치지 못한다. 그 이유는 텍스쳐 연산과 같은 그래픽 처리 연산들은 대부분 분기명령어를 필요로 하지 않는 반면, 일반 목적 응용프로그램은 많은 분기 명령어(또는 제어 흐름 명령어)를 가지고 있기 때문이다.

▶ 분기 명령어
: 분기 명령어가 수행되는 경우, 하나의 경로는 테이큰(taken)이고, 다른 하나의 경로는 언테이큰(untaken)이다. 즉, 분기 명령어는 하나의 워프가 동시에 다른 명령어를 수행하도록 한다.

• Problem: GPU는 SIMD 구조를 사용하기 때문에 분기 명령어를 수행하는 워프를 수행할 수 없다. 
• Solution: SIMD 재수렴(reconvergence) 기법 -- 분기 명령어로 인하여 워프가 분기된 경우, 워프를 분기 결과에 따라서 각 경로마다 수행한다. 즉, 워프 내에서 테이큰(taken)된 스레드들만으로 한 번 수행하고, 언테이큰(untaken)된 스레드들만으로 한 번 수행한다. 각각의 명령어를 수행하고 난 다음, 분리되어 명령어를 수행한 워프 내의 스레드들은 결합점(merging point)에서 하나의 경로를 갖는 워프로 다시 합쳐진다.

▷ Post-dominator 기법
: 분기 명령어를 처리하기 위하여 최신 상용 GPU에서 널리 사용되는 워프 생성 기법

• 지시자(dominance)는 코드 최적화를 위해 컴파일러에서 식별된다.
• Post-dominator 알고리즘의 핵심은 하나의 노드에서 갈라진 분기 흐름들이 하나의 노드에서 만난다는 것이다. 그러므로 Post-dominator 기법을 사용하면 하나의 분기 명령어로 인해 갈라진 명령어 흐름이 다시 만나는 결합점에 대해 알 수 있다.

 

3.2 워프 스케쥴링

• 무작위(Random) 스케줄링: GPU 내부의 난수를 활용하여, 워프 풀에 대기 중인 레디 워프들 중 하나를 선택하는 스케줄링 기법
• 라운드 로빈(Round Robin) 스케줄링: 가장 최근에 수행한 워프와 가장 가까운 다음 순서의 레디 워프를 선택하는 스케줄링 기법
• 선입선처리(First Ready First Come First Service) 스케줄링: 워프 풀 안의 워프들 중 가장 먼저 실행 준비가 된 워프부터 순차적으로 선택하는 스케줄링 기법

 
 

4. 실험환경 및 결과 분석

▶ 분기 명령어를 포함하지 않은 응용프로그램 수행 시 스케줄링 기법에 따른 GPU의 성능 평가
: 스케줄링 기법에 따른 성능 차이는 거의 보이지 않는다.
 
▶ 분기 명령어를 포함한 응용프로그램 수행 시 스케줄링 기법에 따른 GPU의 성능 평가
: 스케줄링 기법에 따른 성능 차이가 상대적으로 크게 발생한다.
 
적절한 워프 스케줄링 기법을 개발하기 위해서는 공통적인 특성이 관찰되어야만 한다.
불행하게도 본 논문에서는 평가한 분기 명령어를 포함한 응용프로그램 수행 시 스케줄링 기법에 따른 GPU의 성능은 특별한 패턴을 보이지 않는다.
 
다만, 분기 명령어를 포함한 응용프로그램 수행 시 스케줄링 기법에 따른 큰 폭의 성능 변화는 무작위적인 메모리 접근 때문인 것으로 분석된다.
 
워프는 생성될 때, 순차적인 스레드들의 집합으로 구성되기 때문에 워프 내 스레드들의 메모리 요구 또한 순차적인 메모리 공간을 요구한다.
하지만 분기 명령어로 인해 하나의 워프가 두 개의 워프로 나뉘어 수행되기 때문에 메모리 접근이 무작위로 발생된다. 즉, 워프 내의 스레드들 중 일부만이 수행됨으로써 발생된 무작위적인 메모리 접근이 메모리 지역성의 원리를 위배하여 성능을 저하시킨다. 뿐만 아니라, 무작위적인 메모리 접근은 내부연결망에 병목현상 또한 유발시킨다.
그러므로, 범용 응용프로그램에서 분기 명령어로 인한 무작위적인 메모리 접근을 줄일 수 있는 스케줄링 기법이 효율적일 것으로 판단된다. 하지만 RAN, RR, FC-FCFS 등 워프 스케줄링 기법은 무작위적인 메모리 접근을 고려하고 있지 않기 때문에 수행되는 범용 응용프로그램의 특성에 따라 적합한 스케줄링 기법이 다르게 나타난다.
 
 

5. 결론

본 논문에서 우리는 GPU에서 실제 연산을 담당하는 세이더코어가 수행할 워프를 선택하는 워프 스케줄링 기법의 효율성을 측정하였다.
 
우리는 분기 명령어를 포함 또는 미포함하는 응용프로그램을 수행하였으며, 그 결과를 분석하였다.
 
실험 결과에 따르면, 분기 명령어를 포함하지 않은 응용프로그램의 경우에는 워프 스케줄링 기법에 따라 해당 응용프로그램 수행 중 발생하는 메모리 접근 패턴이 크게 변화하지 않기 때문에, 워프 스케줄링 기법의 변화에 따른 성능 차이가 거의 없다. 
 
반면, 분기 명령어를 포함하는 응용프로그램의 경우에서는 워프 스케줄링 기법에 따라 메모리 접근 패턴을 예측하기 어렵기 때문에 기존의 워프 스케줄링 기법들 중 어떠한 워프 스케줄링 기법이 적합하다고 말할 수 없다.
불행히도, 분기 명령어를 포함한 응용프로그램에서 발생하는 메모리 접근은 지역성의 원리에 위배되기 때문에 GPU의 성능을 상당히 저하시킨다. 그러므로 분기 명령어를 포함한 응용프로그램을 수행하는 GPU를 위한 워프 스케줄링 기법은 무작위적인 메모리 접근에 따른 오버헤드를 완화시킬 수 있어야 한다.
 
 
 
 
https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE10877824 

워프 스케쥴링 기법에 따른 GPU 성능 분석 | DBpia