2020. 7. 7. 00:11ㆍResearch
이 포스팅에서 리뷰할 논문은 2011년 SOSP에 나온 "PTask: Operating System Abstractions To Manage GPUs as Compute Devices"이다. 상당히 오래된 논문이지만 GPU 기반 이기종 시스템과 관련하여 중요하게 여겨지는 개념들과 아이디어들이 많기 때문에 구체적으로 리뷰를 하려고 한다. 염두에 두어야할 점은 이 연구에선 딥러닝의 맥락에서 GPU 스케줄링을 언급하고 있지 않으며 그 당시와 현재의 상황이 꽤 많이 달라졌다는 것이다.
ABSTRACTION
이 논문에서는 GPU를 CPU와 같은 1순위 계산 자원으로 활용할 수 있도록 하기 위한 OS abstraction(OS API)인 PTask API를 소개한다. PTask API에서 OS가 관리하는 여러 객체들은 PTask 그래프의 컴포넌트들로 표현이 되고, 이렇게 만들어진 그래프를 기반으로 dataflow programming model을 제공한다. Dataflow 그래프로 프로그램을 표현하면 시스템의 전체적인 정보를 활용하여 스케줄링에서의 효율성과 fairness를 증대시킬 수 있기 때문에 CUDA나 OpenCL만을 사용하는 GPU programming model과 비교하였을 때 큰 이점을 얻을 수 있다.
이 논문에서는 Windows 7과 Linux 상에서 PTask API를 개발하여 gestural interface 프로그램에 대해 성능 실험을 하였고, 그 결과 최대 throughput에서 5배까지의 성능 향상을 얻었다.
INTRODUCTION
2011년 기준으로 성능 TOP 5 안에 드는 슈퍼컴퓨터들은 모두 GPU를 프로세싱 유닛으로 사용하고 있었다. GPGPU를 위한 프레임워크인 DirectX, CUDA, OpenCL 등이 등장하면서 프로그래머들은 GPU를 병렬 연산장치로 활용하여 고성능 프로그램을 만들 수 있게 되었다. 이와 같이 GPU 프로그래밍 플랫폼이 등장함에 따라 GPU를 연산 장치로 적극 활용할 수 있게 되었지만, GPU가 연산에 활용되는 경우는 주로 렌더링과 같은 batch-oriented computation이며, interactive 어플리케이션(e.g: gestural input, brain-computer interface, interative video recognition, ...)에 대해서는 OS abstraction이 부족하여 제대로 활용되지 못하고 있다.
이 연구에서는 interative application에서 GPU가 제대로 활용되지 못 하는 이유가 적절한 OS-level abstraction이 없기 때문이라고 보고, GPU를 더 이상 I/O device가 아닌 CPU와 동등한 computational device로 관리하여 이러한 문제를 해결하고자 하였다.
위의 그림에서는 각각 CPU(왼쪽)와 GPU(오른쪽)의 abstraction layer를 보여준다. 그림에서 알 수 있는 건 CPU와 비교하였을 때 GPU에 대해서 제공되는 kernel-level abstraction이 상당히 제한적이라는 것이다. OS는 기본적으로 GPU를 shared compute resource가 아니라 주변 기기로 취급, 관리하고 있기 때문에 OS는 GPU 자원의 관리를 제조업체에서 제공하는 드라이버와 유저 모드에서 동작하는 런타임에 맡기고 있다.
이 연구에서는 interative, compute-intensive device를 위한 새로운 kernel-level abstarction을 구현한다. 새롭게 정의되는 abstraction은 모듈화와 고성능 두 가지 조건을 모두 만족시켜야 한다. 이를 위해서 커널은 프로그래머에게 주변 기기에 대한 충분한 하드웨어 정보를 제공하여 micro-tuning을 통한 성능상의 이점을 누릴 수 있도록 해야하고, 성능을 해치지 않으면서도 복잡한 정보들에 대해 유저가 신경쓰지 않고 프로그래밍 할 수 있도록 적절한 고수준 API를 제공해야 한다.
PTask API
(1) PTask graph
PTask API는 dataflow graph를 통해 프로그램을 표현하는 dataflow programming model을 기반으로 한다. 그래프의 노드는 ptask(parallel task)라고 불리며, 이는 GPU에서 돌아가는 프로그램, 또는 CPU나 다른 가속기에서 돌아가는 프로그램들을 표현한다. 각 노드들은 입력 포트와 출력 포트를 가지고 있고, 포트끼리는 그래프의 엣지를 통해 연결된다. 이 엣지를 channel이라고 부르며, 프로그램에서의 데이터 흐름을 표현한다.
(2) Usability
위와 같은 그래프 컴포넌트들을 통해서 PTask graph는 프로그램에서 데이터의 흐름과 잠재적인 동시성을 직접적으로 표현할 수 있고, 이를 통해 프로그래밍 과정을 간단하게 만들 수 있다. 그래프의 정보를 통해 시스템이 자동으로 최적화를 할 수 있기 때문에, 프로그래머는 어떻게(how), 언제(when) 데이터를 옮길 것인가에 대해서 신경 쓸 필요없이 오직 어디(where)에서 어디로 데이터를 옮길지만 생각해서 프로그램을 짜면 된다.
(3) GPU scheduling by OS kernel
PTask graph는 OS-managed object들로 구성되어 있기 때문에 OS 커널은 이들에 대한 충분한 컨트롤을 가질 수 있다. 즉, PTask 런타임은 GPU 커널의 상태에 대해서도 파악을 하면서 마치 CPU 프로세스를 스케줄링하듯이 효율적인 스케줄링을 할 수 있다. 기존의 GPU 프레임워크에서 GPU 스케줄링은 OS 커널에게는 블랙 박스로 감춰져있고 전적으로 제조업체가 제공하는 드라이버에 의해 이루어졌다. (이 경우 주로 round-robin 방식으로 단순하게 스케줄링을 하는 것이 일반적이다.) PTask는 performance와 fairness가 제대로 보장되지 않던 기존 GPU 프레임워크와는 달리 OS 커널에서 직접 효율적인 GPU 스케줄링을 수행할 수 있다.
(4) Efficient data movement
PTask의 또 다른 장점은 데이터의 이동을 최적화할 수 있다는 것이다. 예를 들어 카메라와 같은 주변기기를 통해 들어오는 데이터를 가지고 실시간 이미지 처리를 하는 데에 GPU를 사용한다고 해보자. 기존의 GPU 프레임워크에서 이러한 상황을 처리하려면 CPU와 GPU간에 반복적인 데이터 카피가 발생하게 되고, 굳이 CPU를 거치지 않아도 됨에도 불구하고 CPU를 거쳐 GPU로 메모리가 전달되기 때문에 double buffering 문제가 생길 수 있다. 반면, PTask를 사용하는 경우엔 PTask graph에서 데이터의 origin과 destination에 대한 정확한 정보를 제공하기 때문에 OS가 이 정보들을 통해 불필요한 데이터 복사를 제거할 수 있다. 이 경우엔 카메라 드라이버의 데이터를 CPU host로 불필요하게 카피하지 않고 즉시 GPU 드라이버로 카피할 수 있다.
MOTIVATION
이 연구에서는 interactive application에 GPU를 활용하는 것에 초점을 두고 있으며, interative application이라 함은 다음과 같은 프로그램을 의미한다.
- Gestural interface: 물리적인 제스처를 감지하고 디지털 데이터화하여 입력으로 사용하는 프로그램
- Neural interface: BCI(brain computer interface)와 같이 뇌를 통해 장치를 조종하는 인터페이스
- Encrypting file system
- Real-time audio/visual interface: 실시간 음성 인식...
빠른 연산를 통한 데이터 처리가 필요한 이러한 어플리케이션들은 latency를 줄이기 위해 GPU를 사용하면 큰 이득을 볼 가능성이 있지만, 적절한 OS의 지원이 없기 때문에 GPU를 제대로 활용하지 못 하고 있다.
이 연구에서는 카메라를 통해 감지된 손의 제스처를 마우스 이동/클릭과 같은 OS 입력 이벤트로 처리하는 제스처 인식 프로그램을 예시로 하여 case study를 진행하였다. 이러한 제스처 인식 프로그램은 처리해야 할 계산의 양이 상당히 크고, 동시에 실시간으로 서빙가능한 짧은 latency를 요구하는 interactive 프로그램이다. 따라서 GPU를 활용한 데이터 병렬화를 통해 성능 향상을 보기 좋은 예시라고 할 수 있다. 아래의 Figure 2는 제스처 인식 프로그램의 전체적인 시스템 구조를 보여준다. 시스템은 몇 개의 카메라 센서들, 카메라로부터 얻은 이미지를 분석, 처리하기 위한 소프트웨어로 이루어져 있다. 인식된 데이터가 마우스나 키보드 입력과 같이 빠르게 처리 되기 위해선 제스처 인식 결과가 high frequency & low latency로 전달될 수 있어야 한다. 제스처 인식 프로그램의 구성 요소는 다음과 같다.
- catusb: USB 버스와 연결된 카메라로부터 이미지 데이터를 얻는다.
- xform: geometric transformation을 통해 여러 개의 카메라로부터 얻은 이미지를 단일 point cloud로 변환한다.
- filter: xform이 생성한 point cloud는 노이즈가 많이 낀 상태이기 때문에 filter를 통해 노이즈 필터링을 수행한다. 데이터 병렬화를 통해 처리된다.
- hidinpit: 노이즈가 처리된 point cloud를 통해 제스처를 감지하고, 감지한 결과를 HID(human interface device) 입력으로 보낸다. (병렬화는 사용하지 않는다.)
제스처 인식 시스템은 이와 같이 모듈화된 네 단계 시스템 파이프라인으로 구성되어 있으며, 이 중에서 연산량이 많고 병렬화 적용의 여지가 큰 xform과 filter 프로그램에는 GPU를 통한 데이터 병렬화를 적용한다. 만약 GPU를 사용하지 않고 4-core CPU만을 사용해서 이와 같은 시스템을 서빙하려 한다면 거의 100% CPU 자원을 사용해야 가까스로 실시간 서빙이 가능하다. 반면 GPU를 사용한다면 무거운 계산은 GPU에 맡길 수 있기 때문에 CPU는 거의 사용하지 않을 수 있다.
Motivation 1: 데이터 이동의 문제
GPU를 위한 OS abtraction이 없는 상태에서 제스처 인식 시스템을 돌리려면 유저 레벨 GPU 프로그래밍 프레임워크인 DirectX, CUDA, OpenCL 등을 사용할 수밖에 없다. xform과 filter 프로그램을 이러한 프레임워크를 통해 구현한다면 병렬화를 통해 연산 자체에 드는 시간은 크게 단축시킬 수 있지만, PCIe 버스를 통해 CPU(host)와 GPU(device) 간에 왔다갔다 하는 데이터 복사 오버헤드가 매우 크기 때문에 성능상의 이점이 사라질 수 있다. 제스처 인식 프로그램에서도 catusb -> xform -> filter -> hidinput으로 넘어가는 사이사이마다 CPU-GPU 간의 메모리 복사가 이루어지기 때문에 오버헤드가 상당히 크다. 아래의 그래프는 실제로 시스템에서 오버헤드가 얼마나 큰지 보여주는데, 짙은 색으로 표시된 부분이 GPU에서 실제 커널 연산이 이루어지는 시간에 해당하고, 밝은 부분으로 표시된 부분이 커뮤니케이션 오버헤드를 나타낸다.
이와 같은 커뮤니케이션 오버헤드를 효과적으로 줄이기 위해서는 OS 레벨의 지원이 필요하다. 만약 충분한 OS의 지원이 있다면, catusb에서 캡처한 이미지 데이터를 CPU를 거치지 않고 바로 GPU 메모리로 보내서 xform을 수행할 수 있을 것이고, xform 이후에 이어지는 filter도 GPU에서 연산이 이루어지기 때문에 CPU로 메모리를 복사할 필요없이 GPU에 있는 데이터를 그대로 사용할 수 있게 된다.
Motivation 2: 데이터 이동 문제 해결을 위한 구현이 쉽지 않다.
CPU-GPU 간의 데이터 복사 문제는 GPGPU 프레임워크 개발자들에게 이미 잘 알려진 문제이며, 이를 해결하기 위한 몇 가지 해결책들이 만들어져 왔다. 예를 들어 CUDA는 비동기 버퍼 복사, CUDA stream를 지원하고, 메모리 버퍼를 고정하여 computation과 communication을 중첩시킴으로써 데이터 이동의 latency hiding을 하기도 한다. 하지만 이러한 기능들을 프로그래머가 제대로 활용하려면 메모리 매핑과 같은 OS 레벨의 이해가 필요하다.
멀티 스트림을 효율적으로 사용하기 위해서는 어떤 GPU computation이 데이터 이동과 중첩될 수 있는지에 대한 정적인 정보(디펜던시 등)가 필요한데, 이러한 정보는 항상 정적으로 고정되어 있지가 않다. 이러한 문제가 해결되기 위해선 CPU-GPU 간의 메모리 관리를 위한 아키텍쳐와 소프트웨어 차원의 지원이 필요하다. AMD Fusion은 CPU와 GPU를 하나의 die로 집적시킴으로써 양 쪽 프로세서에서 shared memory에 접근할 때 coherency를 보장하고자 하였다. 하지만 GPU 프로그래밍 경험이 있는 사람들을 알다시피 성능을 높이기 위해서는 coherency를 희생하여 GPU private memory 접근을 높여야하기 때문에 한계가 있다. Intel Sandy Bridge 역시도 CPU와 GPU를 하나의 die에 통합시키는 등의 시도가 있었다. 하지만 여전히 고성능과 coherency를 동시에 만족시키기엔 부족함이 많다.
Motivation 3: 스케줄링 문제
아직까지 OS는 계산에 GPU를 사용하는 경우 performance와 fairness를 동시에 만족시키기 위한 스케줄링을 제공하지 못하고 있다. 근본적인 이유 중에 하나는 OS는 GPU를 입출력 장치와 같은 주변기기로 대할 뿐, 공유 계산 자원으로 여기고 있지 않는다는 점이다. 설령 OS에서 GPU task의 priority를 어느 정도 조절하려고 하더라도 이는 블랙박스로 감춰진 GPU driver에 의해 의도대로 스케줄링이 되지 않을 수 있다는 문제도 있다. 밑에서 살펴볼 두 가지 케이스는 CPU task와 GPU task와 서로 무관함에도 불구하고 한쪽에 부하가 걸리면 다른 한 쪽의 성능이 크게 저하되는 경우이다.
(1) GPU work가 CPU work를 멈추게 할 수 있다.
위의 그림은 60초 동안 HID class driver에 전달된 마우스 이벤트의 frequency를 보여준다. 앞서 gestural interface 시스템의 GPU 프로그램인 xform이 CPU task와 동시에 돌아가지 않을 때, 시스템은 마우스 이벤트를 120Hz 정도에서 안정적으로 전달하고 있다. 반면, xform이 동시에 실행 중일 때는 마우스 이벤트의 주기가 요동치며 20Hz 아래까지 떨어진다. GPU task는 근본적으로 CPU가 아닌 GPU에서 돌아가기 때문에 설령 무거운 GPU 프로그램(xform)이 실행되더라도 CPU utilization은 25%를 넘지 않는다. 즉 CPU에 사용 가능한 자원이 있음에도 불구하고 성능 저하가 발생하는 것이다.
OS에서 GPU를 컨트롤하기 어려운 이유 중에 하나는 GPU는 preemptive하지 않다는 점이다. 즉, request가 한 번 전송되어서 GPU task가 시작되면 끝날 때까지 OS에서 control을 뺏어서 중지시키는 것이 불가능하다. 특히나 GPU 런타임을 개발할 때 GPU 프로그램의 throughput을 높이기 위해서 큰 단위로 request batching을 하기 때문에 preemption이 불가능한 GPU task 하나의 수행시간이 더욱 길어질 수 있다. 이처럼 OS가 GPU를 CPU task와 통합하여 전체적인 맥락에서 로드 밸런싱할 수 없다는 사실은 상당히 큰 비효율을 낳는다.
(2) CPU work가 GPU throughput을 저하시킬 수 있다.
위의 그림은 서로 무관한 CPU, GPU 프로그램이 동시에 수행되고 있을 때 Windows 7에서 로드 밸런싱을 하지 못하는 상황을 보여준다. CPU에서는 4개의 코어를 모두 사용하는 CPU-bound task가 실행되고 있고, CPU에서는 xform 프로그램이 돌아가는 상황이다. xform은 CPU에서 커널을 실행할 때를 제외하면 CPU의 자원을 사용하지 않는데도 불구하고 CPU에 부하가 걸린 상태에서는 frame rate가 2배나 떨어진다.
이와 같은 문제를 해결하기 위해서는 OS가 GPU를 CPU와 동일한 지위의 연산 자원으로 다루어야 하고, 프로그램에서 GPU를 사용하는 경우엔 CPU 쓰레드와 프로세스를 다루는 것처럼 처리될 수 있어야 한다.
DESIGN
앞에서는 GPU 프로그램, 특히 interactive GPU 프로그램에서 왜 새로운 OS abstraction이 필요한지에 대한 이유를 살펴보았다. 이번 섹션에서는 본격적으로 문제 해결을 위한 새로운 abstraction인 PTask API에 대해서 살펴볼 것이다.
INTRODUCTION에서 언급했다시피 PTask는 dataflow programming model에 기반하며, 프로그램은 노드(ptask)와 엣지(channel)로 이루어진 DAG 형태로 표현 된다. PTask의 디자인에는 다음 세 가지의 철학이 반영되어 있다.
- 스케줄링의 fairness와 isolation을 위하여 리소스 매니저가 GPU를 CPU와 더불어 하나의 통합적인 시스템 하에서 파악할 수 있도록 한다.
- GPU 프로그래밍 편의성을 높인 programming model을 제공한다. OpenCL이나 CUDA 같은 기존 GPU 프레임워크에서는 실제 GPU에서 실행되는 커널의 코드 자체는 그리 길지 않음에도 불구하고, CPU와 GPU 간의 데이터 이동을 조작하기 위한 코드의 양이 매우 많았다. (context, command queue, buffer, argument 셋업을 해주고 명시적으로 memcpy 코드를 작성해야하는 것 등) PTask는 device-specific한 코드들은 캡슐화하여 프로그래머들이 오직 커널 자체의 알고리즘 구현과 데이터 흐름에만 신경 쓸 수 있도록 고수준 API를 제공한다.
- 모듈화와 빠른 속도, 두 가지 이점을 모두 챙길 수 있는 시스템을 구축한다. 현재 GPU 프로그래밍 프레임워크에서는 커널을 실행하고, 메모리를 복사하는 CPU host 코드와 GPU 커널 코드가 타이트하게 커플링되어 있기 때문에 GPU 커널 코드와 데이터 이동을 위한 host 코드를 모두 작성해야 한다. 이러한 프로그래밍 방식은 최적의 데이터 이동을 보장할 수 없기 때문에 성능 저하를 일으킨다.
1. PTask 스케줄링을 OS와 통합
기존에 CPU task에 대해서만 적용되던 OS 스케줄링이 GPU task에도 적용되었을 때 얻을 수 있는 이점은 크게 두 가지이다.
- Efficiency: 스케줄링을 통해 CPU와 GPU의 utilization을 올릴 수 있다.
- Fairness: task priority를 통해 로드 밸런싱을 하던 기존 OS 스케줄러에 GPU task를 통합시킴으로써 interative한 CPU task와 batch-oriented GPU task 사이에 contention이 발생한 상황 등에서 보다 공평하고 효율적인 로드 밸런싱을 적용할 수 있다.
2. Efficiency & Modularity
matrix gemm(A, B) {
matrix res = new matrix();
copyToDevice(A);
copyToDevice(B);
invokeGPU(gemm_kernel, A, B, res);
return res;
}
matrix modularSlowAxBxC(A, B, C) {
matrix AxB = gemm(A, B);
matrix AxBxC = gemm(AxB, C);
return AxBxC;
}
matrix modularFastAxBxC(A, B, C) {
matrix intermed = new matrix();
matrix res = new matrix();
copyToDevice(A);
copyToDevice(B);
copyToDevice(C);
invokeGPU(gemm_kernel, A, B, intermed);
invokeGPU(gemm_kernel, intermed, C, res);
copyFromDevice(res);
return res;
}위의 pseudo-code는 $((A \times B) \times C)$를 계산하는 gemm 서브루틴 예시이다. GPU는 CPU와는 독립적인 private memory 공간을 가지고 있기 때문에 GPU에서 gemm 연산을 하기 위해서는 CPU 메모리에서 입력 행렬인 $A$와 $B$의 데이터를 GPU 메모리로 복사해야 한다. 이후 GPU 커널이 호출되면 실제 연산이 이루어지고, 계산 결과는 다시 CPU 메모리 공간으로 복사된다. 만약 프로그래머가 modularity를 위해서 gemm 커널을 위의 예시에서 modularSlowAxBxC처럼 단일 행렬 곱 연산을 하도록 구현한다면, $((A \times B) \times C)$는 gemm(gemm(A, B), C)와 같이 함수가 nesting 되어 계산 될 것이다. 이 경우 중간 계산 결과인 $(A \times B)$는 첫번째 gemm 커널의 계산 후에 CPU 메모리로 복사될 것이고, 두 번째 gemm 커널 런치시에 다시 GPU 메모리 공간으로 복사된다. 이와 같이 granularity가 작은 모듈화된 커널 구현에서는 불필요한 여러 번의 데이터 복사로 인해 상당한 오버헤드가 발생한다. 반대로 $((A \times B) \times C)$를 한 번에 계산하는 modularFastAxBxC와 같이 커널 하나에서 많은 연산을 하도록 granularity를 증가시키면 메모리 복사로 인한 오버헤드는 감소하지만 modularity와 코드의 재사용성이 떨어지는 문제가 있다.
PTask에서는 런타임이 CPU와 GPU task 간의 디펜던시를 파악하여 자동으로 불필요한 데이터 복사와 버퍼링을 제거하여 위와 같은 modularity와 performance 간의 trade-off 문제를 해결할 수 있다. PTask API를 통해 행렬곱을 구현하는 경우 행렬곱 연산은 위의 그림과 같이 그래프 형태로 표현된다. 행렬 $A$와 $B$는 gemm ptask의 입력으로 사용되고, 그 계산 결과는 출력으로 나간다. 출력으로 나간 중간 계산 결과($(A \times B)$)는 또 다른 gemm ptask의 입력으로 사용되어 또 다른 입력인 $C$와 함께 처리된다. 이와 같이 PTask API를 사용하면 프로그래머는 단지 그래프를 구성하여 노드 간의 데이터 흐름(where to where)만 표현하면 되고, 그 밖의 정보는 시스템에서 그래프를 통해 자동으로 파악할 수 있다. 예를 들어, 시스템은 중간 계산 결과인 $(A \times B)$가 GPU 커널로부터 생산되었고 뒤에 이어지는 GPU 커널의 입력으로 사용될 것임을 그래프를 통해 파악할 수 있다. 따라서 굳이 중간 계산 결과를 CPU 메모리로 복사할 필요가 없음을 알 수 있고 CPU-GPU 간의 불필요한 메모리 복사를 제거할 수 있게 된다. 동시에 gemm 커널은 단일 행렬 연산만을 수행하기 때문에 메모리 복사 오버헤드를 줄이면서도 modularity를 유지 가능하다.
프로그램을 DAG 형태의 dataflow graph로 표현하여 얻을 수 있는 또 다른 이점은 DAG 자체가 명시적으로 프로그램의 병렬화 가능 부분을 표현한다는 것이다. DAG 상에서 디펜던시가 없는 연산끼리는 동시에 수행이 가능하기 때문에 멀티 GPU를 사용하는 경우에도 유저가 직접 멀티 GPU를 위한 셋업 코드를 작성하지 않더라도 시스템이 알아서 처리를 할 수 있다.
3. Limitations
PTask graph는 반드시 DAG 형태를 만족해야 하며, 그래프는 반드시 정적으로 고정되어야 한다는 제약이 있다. 따라서 recursion이나 dynamic한 특성을 가진 프로그램을 표현하는 것이 불가능하다.
PTASK API
PTask API는 아래의 표(Table 1)과 같은 OS 레벨의 abstraction으로 구성되어 있다. (시스템 콜로 구현됨)
(1) PTask
ptask는 OS 프로세스와 비슷하지만 GPU를 비롯한 다른 가속기에서 실행되는 task를 포함한다는 점에서 차이가 있다. 각 ptask는 stdin, sdtout, sdterr file descriptor와 같은 입출력 포트를 가지고 있다.
(2) Port
Port는 데이터의 ptask에 사용되는 데이터의 source나 sink가 된다. Port는 다음과 같은 세 가지 종류가 있다.
- InputPort: 입력 포트
- OutputPort: 출력 포트
- StickyPort: 여러번 ptask가 호출되더라도 지속적으로 유지되는 값을 가진 입력 포트
PTask graph에서 각 ptask는 자신의 모든 InputPort가 계산에 사용될 데이터를 가지고 있을 때 실행되며, 생산된 결과값은 OutputPort로 전달된다.
(3) Channel
특정 port와 또 다른 port를 연결하는 pipe 역할을 한다. channel은 반드시 한 개의 source와 한 개의 destination port 간에 연결되며, InputPort와 StickyPort는 오직 하나의 channel에만 연결될 수 있고, OutputPort는 여러 개의 channel들에 연결 가능하다.
(4) Graphs
여러 ptask들의 port가 channel을 통해 연결되어 하나의 graph를 형성한다. 여러 개의 graph가 존재할 경우, 각각은 독립적으로 생성, 수행되며 PTask 런타임이 각각의 그래프를 공평하고 효율적으로 스케줄링 한다.
(5) Datablock & Template
Datablock은 graph에서 특정 channel을 따라서 흐르는 개별 dataflow의 단위이며, template은 datablock에 대한 meta-data(data layout 등)를 표현하고 datablock에 흐르는 raw data를 GPU 하드웨어 쓰레드에 매핑하는 데 도움을 준다.
1. Graph에서의 dataflow
PTask에서의 데이터는 개별 datablock 단위로 channel을 통해 흐르게 되며, ptask의 입력 port가 channel을 통해 데이터를 받았을 때 해당 ptask가 실행될 수 있고, 생산된 결과는 출력 port에 전달된다. Port는 port가 datablock을 가지고 있는지 여부에 따라서 "Occupied", 또는 "Unoccupied" 두 가지 상태를 가질 수 있다. 이 때 port는 종류에 따라서 다른 방식으로 동작한다.
- InputPort
- Occupied: 이전 노드와 연결된 channel로부터 datablock을 읽는다.
- Unoccupied: 비어있던 channel의 queue에 새로운 데이터가 들어오면 즉시 해당 datablock을 읽는다.
- OutputPort
- Occupied: 뒤에 이어지는 모든 channel들로 datablock을 push한다. (OutputPort는 여러 channel들과 연결 가능)
- Unoccupied: 비어있던 queue에 새로운 데이터가 들어오면 즉시 push한다.
- StickyPort: 새로운 datablock이 연결된 channel에 쓰이기 전까지는 이전에 쓰인 datablock을 보존하며 Occupied 상태를 유지한다.
Port들은 ptflags라는 meta-data를 가지는데 , 이는 해당 port가 GPU 측 자원에 바운드되어 있는지, 아니면 런타임에 바운드되어 있는지를 나타낸다.
Channel들은 주어진 capacity 양만큼의 datablock들을 큐잉할 수 있다. 이는 Producer-Consumer 상황을 생각하면 되는데, sys_push 시스템콜을 통해서 어플리케이션이 데이터를 channel로 push하면, 이미 큐가 capacity만큼 꽉 찬 상태라면 공간이 날 때까지 request blocking 된다. 마찬가지로 sys_pull 시스템콜은 channel의 큐에 데이터가 하나도 없는 상황이라면 데이터가 들어올 때까지 request blocking 된다.
Datablock은 메모리 공간 간에 이동이 이루어지는 데이터들에 대해서도 coherent view를 제공한다. Datablock은 메모리 공간을 특정 디바이스의 버퍼 객체로 매핑하는 buffer-map을 통해서 여러 메모리 공간의 버퍼들을 캡슐화한다. buffer-map은 어떤 버퍼가 해당 데이터에 대해서 가장 최신 업데이트 값을 가지는지 추적하여 서로 다른 주소 공간 사이에서도 coherency를 유지한다. Datablock은 record-count를 가지는데, channel에 push되면 record-count가 증가한다. 컴파일러 ref-count와 마찬가지로 record-count가 0이 되면 garbage collect된다.
Iteration Space
SIMT방식으로 동작하는 GPU는 iteration space(= index space, grid, NDRange...)에 따라서 하나의 커널 인스턴스에서 병렬적으로 수행할 work-item(= thread)의 개수(dimension)을 정의하고, 이에 따라 하드웨어 쓰레드를 할당하여 병렬 연산을 수행한다. PTask에서는 sys_get_geometry 시스템 콜을 통해서 프로그래머가 명시적으로 iteration space를 정의할 수 있으며, 일반적인 경우에는 프로그래머가 명시를 하지 않더라도 PTask 런타임이 template의 정보를 통해서 적절한 iteration space와 GPU thread configuration을 파악하여 자동으로 세팅할 수 있다.
Template은 datablock 버퍼에 있는 raw data에 대한 meta-data 정보를 담는다. 다음은 template이 포함하고 있는 멤버들의 예시이다.
- dimension: 3차원 iteration space 정보
- dbtflags: 데이터가 바운드된 리소스의 유형을 명시 (e.g: GPU global memory, constant memory, ...)
PTask에서 template이 필요한 이유는 3가지이다.
- 프로그래머가 명시를 하지 않더라도 런타임이 자동으로 iteration space를 추론할 수 있게 하기 위해서
- channel을 통해서 소비될 datablock을 런타임이 할당할 수 있도록 하기 위해서
- 프로그래머가 잘못된 API call을 하였을 때 런타임이 이를 파악하여 유저 피드백을 제공할 수 있도록 하기 위해서
2. PTask invocation
ptask는 다음 4가지 상태 중 하나의 상태를 갖는다.
- Waiting: 입력이 오길 기다림
- Queued: 입력은 준비되었고 GPU 자원을 기다림
- Executing: GPU에서 실행 중
- Completed: 계산이 끝나고 출력이 소비되길 기다림
위와 같은 상태를 통해 ptask가 실행되는 과정을 살펴보면 다음과 같다.
(1) Waiting => Queued
특정 ptask의 모든 입력 port가 Occupied 상태면, 런타임은 해당 ptask를 런큐에 넣고 상태를 Waiting에서 Queued로 바꾼다.
(2) Queued => Executing
런큐에 큐잉된 ptask는 GPU 자원이 free해졌을 때 런큐의 head에 있다면 비로소 실행될 수 있다. 실행시엔 ptask의 상태를 Executing으로 변경한다. ptask가 실행되면 런타임은 ptask의 InputPort에 있는 datablock들을 읽는다. Port에서 datablock이 읽히면 (StickyPort가 아닌 경우에) datablock은 port로부터 제거되며, channel로부터 새로운 데이터를 pull한다. 이 때 channel에 큐잉된 datablock이 없다면, 해당 port는 Unoccupied 상태가 된다.
(3) Executing => Completed
실행이 끝나면 ptask는 Completed 상태가 되고, 출력 datablock을 출력 port로 이동시킨다. 이 때 모든 출력 port는 Unoccupied 상태여야 한다. 만약 하나의 출력 port라도 Occupied 상태라면 ptask는 계속해서 Completed 상태에서 기다린다. 출력 port로 데이터 이동이 끝난 후엔 ptask는 다시 Waiting 상태로 되돌아간다. Completed 상태가 따로 필요한 이유는 channel이 유한한 capacity만큼의 datablock만 큐잉할 수 있기 때문이다.
PTask의 핵심 중 하나는 SEDA 아키텍처 구조와 비슷하게 channel에서 datablock을 큐잉을 하는 것이다. 큐잉을 하면 다음 ptask에서 아직 GPU 연산이 이루어지고 있더라도 이전 ptask는 (적어도 channel의 큐가 꽉찰 때까지는) GPU를 놀게 하지 않고 연산 결과를 계속 생성해낼 수 있다.
3. Gestural Interface PTask Graph
이 논문에서 케이스 스터디 대상으로 선정한 gestural interface를 PTask graph로 표현하면 다음과 같은 이점이 있다.
(1) 그래프 정보를 통해 불필요한 커뮤니케이션을 없앨 수 있다.
위의 그림(Figure 8)에서 USB 포트(usbsrc_0, usbsrc_1)과 이미지 입력 포트(raw_0, raw_1)는 channel을 통해 연결되어 있다. 여기에서 USB => CPU 메모리 => GPU 메모리로 이어지는 더블 버퍼링 문제가 발생할 수 있는데, USB 드라이버, PTask 런타임, GPU 드라이버 간에 버퍼 공유가 있다면 USB의 데이터를 CPU 메모리를 거치지 않고 즉시 GPU 메모리로 이동시킬 수 있다.
xform의 출력 port(cloud0, cloud1)은 filter의 입력 port(i_0, i_1)과 연결되어 있는데, xform과 filter 모두 GPU에서 실행되는 ptask임을 PTask 런타임이 파악할 수 있기 때문에 CPU 메모리로의 불필요한 데이터 카피를 하지 않을 수 있다.
(2) Concurrency 파악이 가능하다.
그래프를 통해 프로그램을 표현하면 프로그래머가 따로 명시하지 않더라도 런타임이 concurrency를 파악할 수 있다. 예를 들어 위의 그림에서는 여러 개의 GPU 환경이라면 두 개의 xform ptask가 동시에 수행될 수 있다.
SCHEDULING
PTask에서 스케줄링에는 몇 가지 어려운 점이 있다.
- GPU 하드웨어는 preemptive하지 않고, CPU task 처럼 context switch가 불가능하다.
- GPU를 완전히 컨트롤할 수 있는 인터페이스가 존재하지 않기 때문에 CPU 프로세스 스케줄러를 통해 GPU task를 온전히 컨트롤하는 것은 불가능하다.
- 멀티 GPU 환경에서 GPU 메모리의 locality가 성능에 매우 중요한 요소이기 때문에 잘 고려되어야 한다. (만약 GPU 간의 메모리 이동 오버헤드가 크다면 여러 GPU를 사용하는 것이 오히려 성능을 저하시킬 수도 있다.)
위의 사항을 고려하여 PTask에서는 4가지 방식의 스케줄링 방식을 실험하였다.
(1) First-available
모든 ptask가 하나의 매니저 쓰레드에 할당된다. ptask는 큐잉되지 않기 때문에 READY 상태의 ptask가 사용 가능한 GPU 자원의 수보다 많다면 GPU를 할당 받지 못한 ptask들은 lock이 걸려 blocking 된다. 사용 가능한 GPU 자원이 생긴다면 signal이 발생하고, lock을 잡고 기다리던 ptask가 깨어나서 GPU를 할당 받을 수 있다.
(2) FIFO
큐를 사용하여 FIFO 순서로 ptask를 스케줄링한다.
(3) Priority
각 ptask는 static priority와 proxy priority를 갖는데, static priority는 말 그대로 정적으로 고정된 priority이고, proxy priority는 ptask의 실행 및 데이터 관리를 담당하는 매니저 쓰레드의 priority이다. 스케줄러는 ptask들의 ready queue와 사용가능한 GPU 리스트를 동시에 관리하는데, ptask의 상태가 Queued, Executing, Completed로 바뀔 때마다 스케줄러가 깨어나서 ready queue 내의 각 ptask의 effective priority를 계산한다. Effective priority는 static priority, proxy priority, 큐에서 기다린 시간, 평균 수행 시간을 weigted sum하여 계산된다.
ptask의 effective priority는 다음과 같은 경우에 증가한다. (priority boosting)
- 평균 대기 시간보다 더 오랜 시간을 큐에서 대기한 경우
- 평균 GPU 수행시간보다 더 짧은 수행 시간을 가질 경우
- proxy priority가 높은 경우
전통적인 OS 스케줄링에서 priority boosting의 목적과 마찬가지로 ptask에서 priority boosting이 존재하는 이유 역시 starvation을 방지하기 위함이다. 짧은 수행 시간의 interative job의 priority를 높이는 방향으로 스케줄링을 해야 throughput을 늘릴 수 있으므로 위와 같은 방식으로 priority를 조절한다.
스케줄러는 ready queue의 head에 있는 ptask에 fitness와 strength를 고려하여 사용가능한 GPU 리스트 중 하나를 할당한다. Fitness는 GPU가 실행환경 및 ptask의 세팅에 대해 지원을 하는지 여부를 의미하고, strength는 GPU의 코어 개수, 클락 속도와 같은 성능 관련 요소를 의미한다. 스케줄러는 항상 strength가 가장 강한 GPU부터 선택하여 ptask와 매칭을 시킨다. 성공적으로 매칭이 된 경우, 스케줄러는 ptask를 큐에서 제거하고 ptask 매니저 쓰레드에 signal을 보내 실행을 시키면서 Executing 상태가 된다.
다음은 priority policy를 구현한 pseudo-code이다.
void update_eff_prio(ptasks) {
avg_gpu = avg_gpu_time(ptasks);
avg_cwait = avg_current_wait(ptasks);
avg_dwait = avg_decayed_wait(ptasks);
avg_pprio = avg_proxy_prio(ptasks);
// weight sum을 통해 effective priority 계산
foreach(p in ptasks) {
boost = W_0 * (p->last_cwait - avg_cwait);
boost += W_1 * (p->avg_wait - avg_dwait);
boost += W_2 * (p->avg_gpu - avg_gpu);
boost += W_3 * (p->proxy_prio - avg_pprio);
p->eff_prio = p->prio + boost;
}
}
gpu match_gpu(ptask) {
// 사용 가능한 GPU 리스트를 얻음
gpu_list = available_gpus();
// fitness 체크
remove_unfit(gpu_list, ptask);
// strength가 큰 것부터 내림차순으로 정렬
sort(gpu_list);
// head에 있는 가장 strength가 큰 GPU를 가용 GPU 리스트에서 제거
return remove_head(gpu_list);
}
void schedule() {
update_eff_prio(ptask);
sort(ptasks); // effective prio가 큰 것부터 내림차순 정렬
while(gpus_available() && size(ptasks) > 0) {
foreach(p in ptasks) {
best_gpu = match_gpu(p);
if (best_gpu != null) {
remove(ptasks, p);
p->dispatch_gpu = best_gpu;
signal_dispatch(p);
return;
}
}
}
}
(4) Data-aware
위에서 살펴본 priority policy를 따르되, GPU 선택 알고리즘에서 ptask의 입력이 가장 최신 버전으로 업데이트된 메모리 공간이 어디인지를 고려한다.