Nimble: Lightweight and Parallel GPU Task Scheduling for Deep Learning
Abstract
Deep learning (DL) frameworks는 GPU를 활용하여 DL 추론 및 학습 속도를 개선합니다. 이상적으로, DL 프레임 워크는 GPU에 할당된 계산량에 따라 실행 시간이 달라지도록 GPU의 계산 능력을 완전히 활용할 수 있어야합니다. 그러나 GPU 작업을 예약 할 때 기존 DL frameworks는 대규모 예약 오버 헤드 및 불필요한 serial 실행과 같은 비효율적인 문제를 겪고 있습니다. 이를 위해 최소한의 스케줄링 오버헤드로 GPU 작업을 병렬(parallel)로 실행하는 DL 실행 엔진 인 Nimble을 제안합니다. Nimble은 AoT (Ahead-of-Time) 스케줄링이라는 새로운 기술을 도입했습니다. 여기서 스케줄링 절차는 GPU 커널을 실행하기 전에 완료되므로 런타임 동안 대부분의 스케줄링 오버 헤드가 제거됩니다. 또한 Nimble은 단일 GPU에서 여러 GPU 스트림을 활용하여 GPU 작업 실행을 자동으로 병렬화합니다. 다양한 Neural networks에 대한 평가에 따르면 PyTorch에 비해 Nimble은 inference and training 속도를 각각 최대 22.34배 및 3.61배까지 가속화합니다. 또한 Nimble은 최첨단 추론 시스템인 TensorRT 및 TVM보다 각각 최대 2.81배 및 1.70배 성능이 뛰어납니다.
1 Introduction
최근 몇 년 동안 딥 러닝 (DL)에 대한 수요가 증가함에 따라 Caffe2, MXNet, PyTorch 및 TensorFlow와 같은 DL frameworks의 발전이 촉진되었습니다. 이러한 프레임 워크는 사용자가 일반적인 Python 프로그램처럼 신경망의 의미를 표현할 수있는 high-level API와 함께 GPU-based neural network computations의 구현을 제공합니다. 또한 이러한 프레임 워크를 통해 사용자는 GPU를 직접 제어 할 필요없이 네트워크의 훈련 및 추론 절차를 설명 할 수 있습니다. 그런 다음 DL 프레임 워크는 신경망 가중치를 GPU에 복사하고 GPU에서 DL 연산자를 시작하는 것과 같은 복잡한(intricacies) GPU를 자동으로 처리합니다. Operators는 convolution and batch normalization와 같은 수치 계산을 나타내며 하나 이상의 GPU 작업 (예 : GPU 커널 및 GPU 메모리 작업)으로 구성됩니다.
GPU가 작업을 처리하기 전에 DL 프레임 워크는 먼저 일련의 준비 단계 (GPU task scheduling)를 거친 다음 작업을 GPU에 제출(GPU task submission)해야합니다. 기존 DL 프레임 워크는 런타임 도중에 GPU 작업 스케줄링을 수행합니다. 예를 들어 TensorFlow, Caffe2, MXNet은 neural network을 DL 연산자의 계산 그래프로 나타내며, 연산자의 종속성이 충족되면 런타임에 연산자의 GPU 작업을 예약합니다. 한편 PyTorch 및 TensorFlow Eager의 경우 Python 코드가 한 줄씩 해석되므로 GPU 작업이 런타임에 예약됩니다.
이상적인 상황에서 neural networks의 실행 시간은 대부분 GPU에 할당 된 계산량에 따라 다르지만 실제로는 그렇지 않습니다. 프레임 워크 성능을 크게 제한 할 수있는 런타임 작업 예약의 두 가지 중요한 문제를 지적합니다. 첫째, 스케줄링 오버 헤드라고 부르는 스케줄링에 소요되는 시간은 전체 실행 시간의 상당 부분을 차지할 수 있습니다. GPU 작업의 실행 시간이 오버 헤드를 숨길만큼 충분히 길 때 스케줄링 오버 헤드는 무시할 수 있지만 많은 경우, 특히 신경망의 추론 및 훈련이 작고 짧은 GPU 작업으로 구성된 경우에 그렇습니다. 최신 GPU에는 Tensor Core와 같은 특수 프로세서와 함께 수천 개의 computation units이 있으며 고 대역폭 메모리를 사용하여 메모리 대역폭으로 인한 병목 현상을 방지합니다. GPU 작업 실행에 소요되는 시간은 이러한 GPU에 의해 크게 줄어들 수 있지만 스케줄링 오버 헤드는 모든 GPU 작업에 의해 지속적으로 부과되며 종종 DL 추론 및 훈련의 실행 시간에 지배적입니다.
DL 프레임 워크가 직면한 또 다른 문제는 GPU 작업의 직렬 실행이 작업을 병렬화하여 성능을 더욱 향상시킬 기회를 놓친다는 것입니다. 최근의 neural networks은 상호 운용자 수준의 병렬성을 보여줍니다. 예를 들어, Neural Architecture Search (NAS)에서 얻은 신경망의 토폴로지는 선형 체인이 아닌 여러 분기가있는 방향성 비순환 그래프 (DAGs)입니다. 또한 최근 연구에서는 MixConv 및 Split-Attention 블록과 같이 병렬로 배열 된 더 작은 연산자로 구성된 새로운 유형의 레이어를 제안했습니다. 운영자 간 병렬 처리를 활용하면 특히 추론의 경우 이러한 신경망을 실행할 때 성능이 향상 될 수 있습니다. 그러나 기존 DL 프레임 워크는 GPU 작업이 한 번에 하나씩 실행되도록 스케줄 하는데 설계 및 최적화되어 있으므로 상호 운용자 병렬 처리를 거의 활용하지 않습니다.
위 제한을 해결하기 위해, 최소한의 스케줄링 오버 헤드를 갖고 병렬로 실행되도록 GPU 작업을 스케줄링하는 새로운 DL 실행 엔진인 Nimble을 제시합니다. Nimble의 key observation은 static neural networks의 경우 네트워크의 동작이 아키텍처에 의해 미리 결정된다는 것입니다. 추론과 훈련 모두에 대해 DL 프레임 워크는 동일한 형태의 입력으로 똑같은 계산 그래프를 반복해서 실행합니다. 따라서 계산 그래프 및 input shape에 대한 자세한 정보를 활용하여 GPU 작업 일정을 최적화 할 수 있습니다.
스케줄링 오버 헤드를 피하기 위해 Nimble은 새로운 AoT (Ahead-of-Time) 스케줄링 기술을 도입했습니다. Nimble은 주어진 신경망 실행을위한 GPU 작업을 미리 예약합니다. 나중에 Nimble에 입력이 주어지면 Nimble은 스케줄링을 건너 뛰고 즉시 task submission을 진행합니다. GPU task의 준비 단계는 각 neural network execution (즉, 입력 값과 무관)에 따라 다르기 때문에 task scheduling을 한 번만 수행하면됩니다. Nimble의 AoT 스케줄러는 GPU task scheduling을 수행하는 동안 GPU 작업 및 GPU 메모리 요청의 자취를 기록하고 task schedule을 생성합니다. Task schedule에는 GPU 작업 간의 제출 순서, GPU 작업에 대한 함수 인수, GPU 작업을 병렬로 실행하는 방법을 포함하여, neural network 실행에 필요한 모든 정보와 리소스 (예 : schedule 결과)가 포함됩니다. 런타임에서 Nimble은 작업 스케줄에 따라 GPU 작업의 raw submission으로 high-overhead scheduling 절차를 대체하여 스케줄링 오버 헤드를 크게 줄입니다.
GPU에서 여러 GPU 작업을 병렬로 실행하기 위해 Nimble은 자동 멀티 스트림 실행을 사용합니다. CUDA 프로그래밍 인터페이스는 동시 커널 실행을위한 Stream API를 제공하지만 neural network operators를 적절한 스트림에 할당하는 것은 사용자에게 어려운 작업입니다. Nimble은 스트림 할당 및 동기화 프로세스를 자동화합니다. AoT 스케줄링 이전에 Nimble은 오퍼레이터 간 종속 관계를 분석하고 가능한 한 많은 오퍼레이터를 병렬화하면서 스트림간에 동기화 수를 최소화하는 최적의 스트림 할당을 찾습니다. Operator-to-stream mapping이 주어지면, Nimble은 적절한 동기화를 통해 해당 스트림에서 연산자의 GPU 작업을 실행하기 위해 주어진 neural network의 computation graph를 다시 작성합니다. 수정된 그래프는 AoT 스케줄러에 대한 입력으로 사용되며, 이는 task schedule에 스트림 매핑 및 동기화에 대한 정보를 포함합니다.
Nimble은 PyTorch를 기반으로 구축되었으며 신경망의 추론과 훈련을 모두 지원합니다. 사용자는 Nimble 객체에 DL 모델 인스턴스를 래핑하여 Nimble을 PyTorch 프로그램에 원활하게 적용 할 수 있습니다. 다양한 심층 신경망에 대한 평가에 따르면 Nimble은 PyTorch에 비해 추론 및 훈련 속도를 각각 최대 22.34 배 및 3.61 배 향상 시켰습니다. 또한 Nimble은 최첨단 추론 시스템인 TensorRT 및 TVM보다 각각 최대 2.81 배 및 1.70 배 성능이 뛰어납니다. Nimble is pubilcly available at https://github.com/snuspl/nimble
2 Background
여기에서는 기존 프레임 워크 및 GPU 스트림의 GPU 작업 스케줄링에 대한 배경 지식을 제공합니다.
GPU Task Scheduling in DL Frameworks 기존 DL 프레임 워크의 작업 스케줄링 메커니즘은 크게 두 가지 범주로 나뉩니다. 첫째, TensorFlow, Caffe2 및 TorchScript를 포함한 DL 프레임 워크는 각 노드가 DL 연산자를 나타내고 각 에지가 두 연산자 간의 종속성을 나타내는 computation 그래프로 신경망을 표현합니다. 이러한 DL 프레임 워크의 런타임 스택은 두 가지 주요 시스템 구성 요소 (C ++로 작성 됨), 즉 the operator emitter와 the workers로 구성됩니다. Operator Emitter는 종속성이 충족되는 연산자 큐를 유지하고 큐 맨 앞에있는 연산자를 워커 스레드로 내보냅니다. 워커는 방출된 연산자를 가져와 일련의 준비 단계를 수행하고 마지막으로 각 연산자에 대한 GPU 커널을 제출합니다. 따라서 이 카테고리의 DL 프레임 워크는 오퍼레이터 이미터와 워커의 상호 작용을 통해 런타임에 GPU 작업을 예약합니다.
둘째, PyTorch 및 TensorFlow Eager를 포함한 DL 프레임 워크는 신경망을 명령형 Python 프로그램으로 설명합니다. 이러한 DL 프레임 워크에는 런타임 스택에 신경망이나 연산자 이미터에 대한 명시적인 계산 그래프가 없습니다. 즉, 프로그램이 한 줄씩 실행될 때 Python 인터프리터가 연산자를 내보냅니다. 생성된 연산자는 첫 번째 범주의 DL 프레임 워크와 유사한 방식으로 작업자에 의해 처리됩니다. 따라서 두 번째 범주의 DL 프레임 워크는 Python 인터프리터와 작업자를 통해 GPU 작업의 런타임 스케줄링도 수행합니다.
그림 1은 TensorFlow 및 Caffe2와 같은 DL 프레임 워크가 런타임 스케줄링을 수행하는 방법을 자세히 보여줍니다. GPU 작업을 제출하려면 런타임 스케줄러가 다음 프로세스를 거쳐야합니다. (1) 준비된 대기열에서 연산자를 선택합니다. (2) 작업자를 빈 작업자 스레드로 내보내십시오. (3) 입력 텐서의 유형과 모양을 확인하십시오. (4) 출력 텐서의 유형과 모양을 계산합니다. (5) 텐서 유형 및 모양을 기반으로 연산자에 적합한 GPU 커널을 배포합니다. (6) 일반적으로 캐시된 GPU 메모리 풀에서 메모리 블록을 검색하여 출력 텐서에 GPU 메모리를 할당하고 커널에 작업 공간을 할당합니다. 그리고 (7) 커널 제출에 필요한 함수 인수를 준비합니다. 특정 단계는 DL 프레임 워크에 따라 다를 수 있지만 전체 프로세스는 동일하게 유지됩니다.
GPU Streams GPU는 수천 개의 스레드를 병렬로 실행할 수있는 기능으로 인해 텐서 계산에서 높은 처리량을 제공합니다. GPU의 계산 능력을 최대한 활용하려면 GPU 커널에 충분한 수준의 커널 내 병렬 처리가 있어야합니다. 불행히도 스레드 수는 종종 커널 구현 및 계산되는 텐서의 크기를 비롯한 다양한 요인에 의해 제한되기 때문에 항상 가능한 것은 아닙니다. GPU 활용도를 높이는 또 다른 방법은 여러 GPU 스트림을 사용하여 여러 GPU 작업을 병렬로 실행하도록 예약하는 것입니다. GPU 스트림은 작업이 FIFO 순서로 순차적으로 예약되는 GPU 작업 대기열입니다. 동일한 스트림의 커널은 동시에 실행할 수 없지만 다른 스트림의 커널은 GPU 리소스의 다른 부분을 차지하면서 병렬로 계산 될 수 있습니다. 그러나 스트림 동기화 프리미티브에 의해 명시적으로 지정되지 않는 한 이들 간의 실행 순서는 보장되지 않습니다. 기존 DL 프레임 워크는 GPU 커널을 단일 GPU 스트림에 제출하도록 설계 및 최적화되었습니다. 예를 들어 TensorFlow는 커널 실행을 위해 GPU 당 단일 컴퓨팅 스트림을 사용합니다.
3 Motivation
이 섹션에서는 현재 DL 프레임 워크의 GPU 작업 스케줄링 문제를 설명하는 실험을 제시합니다. 실험은 가장 인기있는 두 가지 DL 프레임 워크 인 TensorFlow와 PyTorch에서 수행됩니다. 실험 설정은 섹션 5의 평가와 동일합니다.
High Scheduling Overhead Makes GPUs Idle 우리는 런타임 스케줄링이 종종 엄청난 양의 스케줄링 오버 헤드를 발생시켜 GPU idle 시간이 DL 실행의 전체 실행 시간을 지배한다는 것을 실험적으로 보여줍니다. 그림 2a는 배치 크기가 1 인 신경망의 추론에 소요된 전체 실행 시간에 대한 GPU가 idle 상태가 아닌 시간 간격의 합인 GPU 활성 시간의 비율을 보여줍니다. 결과적으로 TensorFlow와 PyTorch는 GPU 실행 시간의 상당 부분 (각각 최대 71 % 및 91 %) 동안 유휴 상태입니다. PyTorch의 비효율성은 부분적으로 Python 인터프리터가 느린탓으로 돌릴 수 있지만, TensorFlow의 높은 오버헤드는 성능 병목의 주요 원인이 프레임워크의 핵심 런타임 스택에 있으며, 런타임이 C++와 같은 낮은 오버헤드 언어로 작성되더라도 오버헤드가 상당하다는 것을 의미합니다.
우리의 아이디어를 더욱 뒷받침하기 위해 스케줄링 절차가 최소화 될 때 DL 프레임 워크의 성능을 측정합니다. 실험을 위해 고정된 입력 형태로 특정 신경망의 추론만 수행 할 수 있고 PyTorch와 동일한 GPU 커널 및 메모리 작업을 사용하는 C ++ 프로그램을 작성합니다. 주어진 신경망이 정적이고 입력 텐서의 모양이 고정되어 있다는 가정에서 런타임 전에 수행 할 수있는 중복 루틴을 제거합니다. 예를 들어, 신경망 구조와 미리 정해진 입력 형태를 기반으로 모든 형태 정보를 미리 추론 할 수 있기 때문에 shape check가 생략되고 출력 텐서의 형태가 프로그램에서 하드 코딩됩니다. 이러한 방식으로 프로그램은 배포를 위해 PyTorch의 런타임 스택을 거치지 않고 런타임에 GPU 커널을 직접 제출합니다. 마찬가지로, GPU 메모리 할당은 건너 뛰고 task는 주소 또한 프로그램에 하드코딩 되어있는 매 iteration에 대해 고정되고 사전 할당 된 메모리 영역을 재사용합니다.
그림 2b는 이러한 최적화가 스케줄링 절차에 미치는 영향을 보여줍니다. 정확히 동일한 GPU 커널 세트가 계산된다는 사실에도 불구하고 PyTorch와 스케줄링 최소화 버전은 현저하게 다른 추론 지연 시간을 나타냅니다. ResNet-50에서는 스케줄링 절차를 최소화함으로써 x2.37 속도 향상을 얻을 수 있습니다. 결과는 GPU idle 시간의 주요 소스가 섹션 2에 설명 된 스케줄링 절차의 오버 헤드임을 확인합니다. 낮은 GPU 활성 시간 비율을 갖는 신경망 (예 : EfficientNet-B0)에서는 더 큰 성능 향상이 예상됩니다.
Non-Parallel GPU Task Execution GPU 작업을 병렬화하여 프레임 워크 성능을 더욱 향상시킬 수 있습니다. 그림 2c는 배치 크기가 1인 신경망의 추론에서 GPU 활성 시간에 대한 critical path time의 비율을 보여줍니다. critical path time은 계산 그래프의 가장 긴 경로(시간 측면에서)에 있는 오퍼레이터에 소비된 GPU 활성 시간의 합입니다. 결과는 GPU 작업이 완전히 병렬화되고 충분히 강력한 GPU (즉, 모든 동시 커널을 동시에 계산할 수있는 GPU)에서 실행될 때, 추론 지연 시간을 최대 3배까지 줄일 수 있음을 의미합니다.
잠재적인 성능 향상에도 불구하고, 기존 DL 프레임 워크는 다중 GPU 스트림 사용을 효과적으로 지원하지 않습니다.
우리가 발견 한 한 가지 주요 장애물은 높은 스케줄링 오버 헤드가 다른 스트림의 GPU 작업이 병렬로 계산 될 기회를 크게 감소 시킨다는 것입니다. 예를 들어 그림 3은 GPU 작업 A와 B가 서로 다른 스트림으로 예약 된 타임 라인을 보여줍니다. 두 작업이 동시에 처리 될 것이라는 예상과는 달리 스케줄링 오버 헤드는 두 작업의 시작 시간 사이에 간격을 생성하며 이는 GPU 작업 A의 기간보다 더 깁니다. 결과적으로 GPU는 한 번에 하나씩 작업을 실행합니다.
4 System Design
섹션 3의 관찰을 모티브하여, DL 프레임 워크의 스케줄링 오버 헤드를 자동으로 방지하고 여러 GPU 스트림을 사용하여 GPU 작업을 병렬화하는 DL 실행엔진인 Nimble을 소개합니다. Nimble은 DL 프레임 워크를 기본 시스템으로 사용하고 프레임워크 런타임을 재설계하지 않고 GPU 작업 스케줄링의 비효율성을 해결합니다. 현재 구현에서 Nimble은 PyTorch를 기반으로 구축되지만 시스템 설계는 다른 DL 프레임 워크에 적용 할 수 있습니다.
그림 4는 Nimble의 실행 단계를 요약 한 것입니다. 시스템은 Graph Rewriter와 AoT Scheduler로 구성됩니다. Nimble은 먼저 신경망의 계산 그래프를 입력으로받습니다. 계산 그래프는 PyTorch에서 TorchScript 그래프로 표시됩니다. Graph Rewriter는 계산 그래프를 분석하고 섹션 4.2에서 제시한 알고리즘으로 operator-to-stream mapping을 구성합니다. 각 연산자에 대해 연산자가 발급될 스트림을 표시하고 추가한 커스텀 노드를 사용하여 그래프에 동기화 루틴을 포함합니다. 그 후 Nimble의 AoT 스케줄러는 GPU 작업을 미리 실행하기위한 일련의 준비 단계를 거칩니다. 프로세스 중에 스케줄러는 GPU execution trace를 수집하고 GPU 작업 실행에 사용되는 GPU 메모리를 예약합니다. 마지막으로 Nimble은 GPU 트레이스와 예약된 메모리를 작업 스케줄로 압축(pack)합니다. 런타임에서, 기록된 GPU 작업은 모든 DL 실행에 대한 작업 스케줄을 기반으로 재생됩니다.
4.1 Ahead-of-time (AoT) Scheduling
AoT 스케줄러는 GPU 작업을 미리 제출하는 데 필요한 일정 절차를 완료하여 작업 일정을 생성하는 것을 목표로합니다. 우리의 관찰은 컴파일러의 loop-invariant code motion과 유사하게 신경망 실행의 의미를 변경하지 않고 런타임 실행 루프 외부로 GPU 작업 스케줄링을 이동할 수 있다는 것입니다. 즉, 기존 프레임 워크는 모든 신경망 실행시 스케줄링 절차를 반복하는 반면 Nimble의 AoT 스케줄러는 미리 한 번 스케줄링을 완료하여 신경망 실행 속도를 크게 향상시킵니다. 이는 Nimble이 다른 실행에 대해 동일한 계산 세트를 수행하는 정적 신경망을 가정하기 때문에 가능합니다. 즉, 한번 수행된 후에 스케줄링을 위해 수행된 작업을 재사용 할 수 있음을 의미합니다. 그러나 이 AoT 스케줄링은 두 가지 문제를 제기합니다. (a) 런타임 실행에서 안전하게 제거할 수 있는 스케줄링 절차를 구별하는 방법; 및 (b) 예약 절차를 런타임 실행 밖으로 이동하는 방법.
우리는 일반적인 성능 병목현상 최적화와 다른 방향에서 문제에 접근하여 이러한 문제를 해결합니다. 런타임 실행에서 스케줄링 절차를 구별하고 제거하는 대신 Nimble은 스케줄링되지 않은 작업, 즉 GPU 작업을 식별합니다. 즉, Nimble은 주어진 정적 신경망의 계산이 fixed set of GPU tasks로 전부 설명된다는 것과 GPU task set이 결정되면 DL 프레임 워크의 스케줄링 절차가 중복된다는 것을 활용합니다. AoT 스케줄링 중에 Nimble은 생성된 스트림 매핑에 따라 주어진 신경망을 한번 사전 실행하고 모든 GPU 작업을 execution trace으로 기록합니다. 사전 실행 프로세스는 Nimble의 베이스 프레임 워크를 사용하여 주어진 신경망의 추론/훈련 실행의 단일 반복입니다. 사전 실행 프로세스에서, 베이스 프레임 워크의 스케줄링 절차가 평소와 같이 수행되는 동안 프레임 워크에서 제출 된 GPU 작업이 가로 채서 기록됩니다. 생성된 execution trace에는 보내진 GPU 커널, 커널의 함수 인수, 작업 제출 순서, task-to-stream 할당 등과 같은 스케줄링으로 인한 모든 필수 정보가 포함됩니다. 사전 실행 프로세스가 완료되면 Nimble은 execution trace을 활용하여 작업을 GPU에 제출하고 스케줄링 절차를 건너 뛸 수 있습니다.
수집된 GPU 작업을 실행하려면 작업의 입력 및 출력에 GPU 메모리를 할당해야합니다. 정적 신경망은 다른 실행에 대해 동일한 순서의 메모리를 요청하므로 실행에 필요한 GPU 메모리의 정확한 양을 미리 할당 할 수 있습니다. 이를 위해 사전 실행 프로세스 중에 Nimble은 베이스 프레임 워크의 메모리 할당 / 해제 요청도 가로 채고 사전 실행을 위해 할당된 GPU 메모리를 예약합니다. 예약된 메모리는 Nimble의 런타임 실행에 사용됩니다.
AoT 스케줄링이 끝나면 Nimble은 execution trace와 예약된 메모리를 task schedule로 압축합니다. 런타임에서 Nimble은 예약된 메모리 영역의 주소와 함께 작업 스케줄에 기록된 GPU 작업을 직접 제출하여 주어진 신경망의 추론/훈련을 수행합니다. 이러한 방식으로 GPU 작업은 베이스 프레임워크의 런타임 및 메모리 할당 절차에 묶이지 않고 베이스 DL 프레임 워크와 독립적으로 실행될 수 있습니다.
그림 5는 AoT 스케줄링 기술에 대한 자세한 내용을 제공합니다. 스트림 할당 결과에 따라 AoT 스케줄러는 더미 입력 텐서를 사용하여 신경망을 한 번 사전 실행합니다. 사전 실행 프로세스 중에 스케줄러는 GPU 작업 호출 및 GPU 메모리 할당을 가로채 작업 스케줄을 구성합니다. 구체적으로 말하면 CUDA Stream Capture API를 사용하여 사전 실행의 시작과 끝에서 CUDA 스트림에서 발행된 GPU 작업의 정보를 캡처합니다. 그런 다음 캡처 된 정보에서 CUDA 10에 도입된 기능 (즉, Nimble의 execution trace)인 CUDA Graph를 인스턴스화합니다. 런타임에서 새로운 입력 텐서에게 요청이있을 때, Nimble은 태스크 스케줄을 기반으로 기록된 GPU 작업을 재생하여 신경망을 실행해 스케줄링 오버 헤드를 방지합니다. CUDA Graph의 정보를 기반으로 GPU 작업을 제출하는 CUDA Graph Launch API를 사용하여 신경망을 실행합니다.
4.2 Stream Assignment Algorithm
Nimble은 GPU 작업을 단일 GPU의 여러 GPU 스트림에 제출하여 병렬로 실행되도록 예약합니다. 이 섹션에서는 GPU 작업을 스트림에 할당하기위한 효율적인 알고리즘을 설명합니다.
Stream Synchronization 동시성(concurrency)을 허용하려면 스트림간에 적절한 동기화가 필요합니다. 예를 들어 두 개의 독립적인 GPU 작업 A와 B가 주어지고 또다른 GPU 작업 C가 A와 B의 output을 모두 사용한다고 가정합니다. 세개의 GPU 작업이 단일 스트림에 제출되는 경우 (A→B→C 또는 B→A→C), 동기화(synchronization)가 필요하지 않습니다. 반대로, 3개의 GPU 작업이 3개의 서로 다른 스트림에 제출되는 경우 GPU 작업 A와 B가 모두 완료된 후에만 GPU 작업 C가 실행을 시작하도록해야합니다. CUDA에서는 장벽 역할을 할 수있는 특별한 유형의 GPU 작업인 event를 사용하여 다양한 스트림에 대한 이러한 종속성을 적용 할 수 있습니다. 이 예에서 실행 순서를 보장하는 바람직한 방법은 GPU 작업 A 또는 B가 수행되는 각 스트림에 대해 이벤트를 만들고 제출하는 것입니다. 그런 다음 각 이벤트에 대해 cudaStreamWaitEvent를 호출하여 두 이벤트가 모두 처리 될 때까지 GPU 작업 C의 스트림을 차단합니다. 이는 GPU 작업 A와 B의 실행이 완료되었음을 의미합니다. 우리는 작업 X의 스트림에서 이벤트를 발행하고 작업 Y의 스트림을 차단하는 것을 에지 (X, Y)에서 동기화(synchronization on the edge (X, Y))라고합니다. 동기화 수를 동기화가 발생하는 에지 수로 계산합니다.
일부 DL 프레임 워크에는 프로그래머가 GPU 작업이 실행되는 스트림을 생성, 전환 및 차단할 수있는 high-level API가 있습니다. 그럼에도 불구하고 섹션 3에서 지적했듯이 이러한 프레임 워크에서 다중 스트림을 활용하면 GPU 작업 스케줄링 오버 헤드로 인해 성능이 거의 향상되지 않습니다. 또한 프레임 워크 사용자가 멀티 스트림 실행을 활용할 수있는 경우에도 사용자가 안전하고 효율적인 방식으로 스트림을 할당하고 동기화하는 것은 상당한 부담으로 남아 있습니다. Nimble은 GPU 작업을 자동으로 병렬화하여 이러한 문제를 해결합니다. 병렬화 및 동기화 프로세스는 사용자에게 투명하지만 병렬화 가능한 구조로 신경망을 실행할 때 속도가 향상됩니다.
Goal of the Algorithm DL 연산자의 DAG인 계산 그래프가 주어지면, Nimble은 계산 그래프의 노드 집합에서 GPU의 스트림 집합으로의 매핑인 스트림 할당(stream assignment)을 찾습니다. Nimble의 스트림 할당 알고리즘은 다음 두 가지 목표를 충족합니다.:
• Maximum logical concurrency. a neural network G = (V,E)와 a set of streams S = {s_1; s_2; ··· , s_n}이 주어지면 a mapping f : V→S을 찾습니다. 그런경우 x, y ∈ V이고 x, y 간 종속성이 없어서 (즉, 둘 사이에 설정된 순서가 존재하지 않는), f(x) ≠ f(y) (즉, 두 노드가 서로 다른 스트림에 할당됩니다.)
• Minimum number of synchronizations. 이러한 함수 중, 스트림에서 가장 적은 수의 동기화를 발생시키는 f를 찾습니다.
Maximum logical concurrency은 일반적인 관행을 일반화하는 최적화 전략입니다. GPU 리소스가 완전히 활용될 가능성을 높이려면 동시성을 최대화하는 것이 바람직합니다. 또한 알고리즘은 안전한 동시 실행에 필요한 동기화 수를 고려합니다. 동기화는 작업의 빠른 시작을 방해하기 때문에 알고리즘은 최대 동시성을 유지하면서 이론적으로 가장 적은 수의 동기화를 발생시키도록 설계되었습니다.
Algorithm Description Nimble의 스트림 할당 알고리즘은 알고리즘 1에 설명되어 있습니다. 그림 6은 알고리즘이 계산 그래프 G에 어떻게 적용되는지 보여줍니다. 1단계에서는 기존 G와 동일한 도달 관계를 유지하는 동일한 노드 집합과 엣지의 가장 작은 subset을 갖는 계산 그래프 G의 subgraph인 최소 등가 그래프(minimum equivalent graph, MEG) G'를 계산합니다. 유한 DAG의 MEG는 고유하며 다항시간(polynomial time)에 구성 될 수 있습니다. 2단계와 3단계에서는 G'에서 이분 그래프 B를 정의한 다음 가장 많은 수의 엣지를 포함하는 매칭인 B의 최대 매칭(maximum matching)을 찾습니다. 이분 그래프의 maximum matching은 Ford-Fulkerson 알고리즘으로 계산할 수 있습니다. 4단계에서 먼저 그래프 G'의 각 노드가 별도의 집합인 노드 집합 모음을 만듭니다. 그런 다음 M의 각 에지 (x_i, y_j)에 대해 v_i 및 v_j가있는 두 노드 세트를 결합합니다. 5단계에서 동일한 세트에 속하는 노드는 동일한 스트림에 매핑되고 다른 세트에 속하는 노드는 다른 스트림에 매핑됩니다.
이제 알고리즘 1에서 구성된 스트림 할당이 다음 정리를 사용하여 두 가지 목표를 충족 함을 보여줍니다. 정리에 대한 자세한 증명은 부록 A에 나와 있습니다.
Theorem 1. 스트림 할당 f는 G에서 최대 논리적 동시성을 충족합니다(f가 G'에서 최대 논리적 동시성을 충족하는 경우에만). 또한 최대 논리적 동시성을 충족하는 스트림 할당 f의 경우, f (on G)에 필요한 최소 동기화 수는 f (on G')에 필요한 최소 동기화 수와 같습니다.
Theorem 2. 이분 그래프 B의 일치 집합에서 G '에 대한 최대 논리적 동시성을 충족하는 스트림 할당 집합에 대한 일대일 대응 Φ가 있습니다. 실제로 Φ는 알고리즘 1의 4 단계와 5 단계에 의해 구성됩니다.
Theorem 3. 이분 그래프 B의 어떠한 매칭 m에 대해 해당 스트림 할당에 필요한 최소 동기화 수 Φ(m)는 | E '|-| m |입니다.
Theorem 4. 이분 그래프 B의 최대 매칭 M의 경우, Φ(M)는 최대 논리적 동시성을 만족하는 스트림 할당이며 최대 논리적 동시성을 만족하는 스트림 할당 중 최소 동기화 횟수가 필요합니다.
Proof of Theorem 4. Theorem 1을 기반으로 알고리즘은 G 대신 G'에서 이상적인 스트림 할당을 유도합니다. Theorem 2에서 Φ(M)은 최대 논리적 동시성을 갖는 스트림 할당임을 따릅니다. 이제 Φ(M)보다 훨씬 적은 수의 동기화로 최대 논리적 동시성을 충족하는 스트림 할당 g : V→S가 있다고 가정합니다. Theorem 2와 Theorem 3에 의해 g는 B의 일부 매칭 Φ^(-1)(g)와 일치한다 such that |M| < |Φ^(-1)(g)|. 그러나 불평등은 M이 이분 그래프 B의 최대 일치이므로 M의 정의와 모순됩니다. 따라서 정리 4는 다음과 같습니다.
5 Evaluation
Experimental Setup We implement Nimble on PyTorch v1.4 with CUDA 10.2 and cuDNN 8.0.2. For evaluation, we use an NVIDIA V100 GPU along with 2.10GHz Intel Xeon CPU E5-2695 v4.
DL 추론을 평가하기 위해 Nimble을 인기있는 DL 프레임 워크인 PyTorch, TorchScript 및 Caffe2와 최신 추론 시스템인 TensorRT (v7.1) 및 TVM (v0.6.1)과 비교합니다. DL 트레이닝을 평가하기 위해 Nimble은 PyTorch 및 TorchScript와 비교됩니다. TensorRT 및 TVM은 그래프 최적화 (예 : aggressive operator fusion) 및 커널 선택/튜닝을 사용하며, 이는 우리 아이디어에 직교합니다. Nimble에서는 또한 연산자 융합 (TensorRT의 하위 집합) 및 기본 커널 선택을 구현하여 cuDNN과 PyTorch의 기본 구현간에 컨볼루션 연산자를 더 빠르게 구현하도록 선택합니다. 평가 설정에 대한 자세한 내용은 부록 B에 나와 있습니다.
5.1 Inference Latency
그림 7은 Nimble과 다른 시스템의 상대적 추론 속도를 보여줍니다. PyTorch를 기준으로 설정했습니다. 결과는 Nimble이 PyTorch, TorchScript 및 Caffe2를 상당히 능가한다는 것을 보여줍니다. 이 성능 차이의 주된 이유는 상당한 스케줄링 오버 헤드로 인해 GPU가 대부분의 시간 동안 idle 상태가됩니다. 또한 DL 프레임 워크는 신경망에서 연산자 간 병렬화를 거의 활용하지 않기 때문에 NASNet-A (모바일) (최대 22.34 배)와 같이 병렬화 가능한 구조를 가진 신경망에서 성능 격차가 벌어집니다. 또한 Nimble은 테스트 된 모든 신경망에서 TensorRT보다 최대 2.81 배 높은 성능을 보여줍니다 (NASNet-A (모바일)). 또한 Nimble은 대부분의 경우 TVM 성능을 최대 1.70 배 (EfficientNet-B5) 능가합니다. 유일한 예외는 MobileNetV2입니다. TVM은 커널 튜닝 (각 컨볼 루션에 대해 1,500 번의 시도)에 이틀을 보내고, cuDNN 및 PyTorch보다 MobileNetV2 용 GPU 커널이 훨씬 더 빠릅니다. 다른 GPU에 대한 결과는 부록 C에 나와 있습니다.
5.2 Impact of Multi-stream Execution
병렬화 가능한 구조를 가진 심층 신경망 세트를 선택하고 Nimble의 다중 스트림 실행이 이러한 신경망의 추론 레이턴시에 미치는 영향을 조사합니다. 표 1은 Nimble의 단일 스트림 실행과 비교하여 다중 스트림 실행의 상대적 속도 향상을 보여줍니다. 그 결과 Nimble의 멀티 스트림 실행은 단일 스트림 실행에 비해 DL 추론을 최대 1.88 배까지 가속화 할 수 있으며 Nimble은 프로그래머가 스트림을 효과적으로 할당하고 수동으로 동기화 할 수없는 수준(15)까지 논리적 동시성을 활용합니다 . 또한 가속률은 신경망에서 상당히 다릅니다. 더 높은 수준의 논리적 동시성을 가진 신경망은 다중 스트림 실행에서 더 많은 이점을 얻는 경향이 있습니다. 예를 들어, 논리적 동시성이 가장 낮은 신경망 (Inception-v3)은 가장 작은 속도 향상을 얻습니다. 또한 계산량이 적은 신경망이 다중 스트림 실행에 의해 가속화 될 가능성이 더 높은 경향을 볼 수 있습니다. 예를 들어 NASNet-A(large)는 NASNet-A(mobile)보다 논리적 동시성이 더 높지만, 전자(L)는 각각 GPU 리소스의 대부분을 차지하는 multiply-and-accumulate (MAC) operation이 많은 커널로 구성되어 있기 때문에 전자(L)는 후자(M)에 비해 속도가 제한됩니다. Inception-v3와 DARTS의 비교는 동일한 경향을 보입니다.
5.3 Training Throughput
그림 8은 신경망 훈련에 대한 Nimble의 성능을 보여줍니다. 신경망의 훈련은 일반적으로 큰 배치 크기로 수행되기 때문에 훈련 중에 부과되는 GPU 스케줄링 오버 헤드가 덜 뚜렷하고 다중 스트림 실행의 영향도 제한됩니다. 따라서 ImageNet 데이터 세트 및 BERT에 대한 ResNet의 결과에서 Nimble은 약간의 성능 향상을 보여줍니다. 그러나 Nimble은 신경망이 작은 크기의 입력 (예 : 저해상도 이미지)으로 훈련 될 때 여전히 상당한 속도 향상을 가져옵니다. 예를 들어 컴퓨터 비전 분야에서 CIFAR-10 데이터 세트는 연구자들 사이에서 널리 사용되며 많은 신경망이 데이터 세트에 대해 훈련됩니다. 그림 8은 신경망이 CIFAR-10에서 훈련되었을 때 Nimble의 성능을 보여줍니다. 결과는 스케줄링 오버 헤드가 훈련 중에도 여전히 주요 성능 병목이 될 수 있음을 의미합니다. Nimble은 이러한 비 효율성을 제거하고 트레이닝 처리량을 최대 3.61 배까지 늘립니다. 다양한 배치 크기에 대한 결과는 부록 D에 나와 있습니다.
7 Conclusion
정적 신경망을위한 고속 DL 실행 엔진인 Nimble을 소개합니다. 먼저 GPU 작업의 런타임 스케줄링의 두 가지 문제인 스케줄링 오버 헤드와 직렬 실행을 보여줍니다. Nimble은 런타임에서 GPU 작업을 실행하기 전에 스케줄링 절차를 미리 완료하여 스케줄링 오버 헤드를 최소화합니다. 또한 Nimble은 독립적인 GPU 작업이 병렬로 실행되도록 예약하여 성능을 더욱 향상시킵니다. 다양한 신경망에 대한 평가에 따르면 Nimble이 인기있는 DL 프레임 워크 및 최첨단 추론 시스템을 능가합니다.
