[MobiSys 2022] mGEMM: Low-latency Convolution with Minimal Memory Overhead Optimized for Mobile Devices (3)

# 세미나를 위한 논문 summary

# 2022  MobiSys에서 발표된 논문

# 오역이 있을 수 있습니다.

# 2022 08 30 seminar

 

# ACM reference Format : JongseokPark,KyungminBin,andKyunghanLee.2022.mGEMM:LowlatencyConvolutionwithMinimalMemoryOverheadOptimizedforMobile Devices.InThe20thAnnualInternationalConferenceonMobileSystems, ApplicationsandServices(MobiSys’22),June25–July1,2022,Portland,

https://dl.acm.org/doi/10.1145/3498361.3538940

mGEMM | Proceedings of the 20th Annual International Conference on Mobile Systems, Applications and Services

 

https://strangecat.tistory.com/71 ( 1 ) 

https://strangecat.tistory.com/74 ( 2 )

 

##

##

3 mGEMM

3.1 Motivation

 컨볼루션 연산을 GEMM에 매핑하는 근본적인 문제는 행렬 곱셈의 계산 차원이 너무 제한되어 컨볼루션 연산의 모든 차원을 표현하지 못한다는 것이다. 훨씬 더 큰 연산이 더 작은 연산으로 압축되고 있으며 일부 차원은 맞지 않다.

 그러나 staic GEMMM 에 conv 를 압축하기 위해 노력하는것 대신에, 만약 H(fil) 과 W(fil) 차원의 속성을 포함한 알고리즘으로 부터 더 많은 계산 차원을 추가하여 GEMM 계산 자체를 확장하면 어떨까?

 이 아이디어를 기반으로 현재 GEMM 커널이 어떻게 설계되고 구조에서 확장되는지 연구한다. 우리는 GEMM 라이브러리가 사용하는 최적화 전략과 하드웨어 지원을 활용하면서 컨볼루션 차원을 나타내기 위해 계산 차원을 추가한다. 이를 통해 데이터를 사전 처리하거나 수정할 필요 없이 컨볼루션 작업을 수용할 수 있게 되어 기존 솔루션이 겪었던 오버헤드 및 처리량 손실에서 자유로워진다는 것을 알 수 있다. 

 또한 우리의 수정은 컨볼루션의 계산 결과를 변경하지 않는다. 수학적으로, 우리의 계산 방법은 동일한 데이터에 대해 동일한 계산을 수행하는 기존의 GEMM 기반 컨볼루션 방법과 동일하다. 계산 순서는 다르지만, 교환적 특성 및 연관적 특성은 결과가 변하지 않음을 보장한다.

 

3.2 Design Goals

 우리의 설계 목표는 현재 GEMM 기반 솔루션의 구조와 최적화를 기반으로 하지만 컨볼루션 필터 공간 차원의 속성을 가진 추가 차원을 사용하여 고성능 컨볼루션 솔루션을 만드는 것이다. 이를 달성하기 위해 기존 고성능 GEMM 알고리즘[13, 14, 27, 41]의 구조와 기술을 취하여 설계에 맞게 재구성한다.

 GEMM 루틴의 구조는 내부 계산 커널과 내부 커널 외부의 루프라는 두 부분으로 구성된다. 또한 그에 따라 솔루션을 두 부분으로 설계한다. 아래에서는 알고리즘 구조의 각 부분에서 설계의 목표를 설명한다.

 

Inner computation kernels:

 내부 계산 커널에 대한 우리의 목표는 알고리즘을 완료하기 위해 반복될 수 있는 고도로 최적화된 계산 블록을 제공하는 것이다. 이를 성취해기 위해서, 우리는 Tiling 이라 불리는 기술에 중점을 둔다. Tiling 은 고정된 크기 의 computation dimension set 또는 blocking parameters 를 사용하여 대상 계산의 작은 타일(이 경우 컨볼루션)을 만드는 접근 방식이다. 

주어진 아키텍처와 알고리즘의 제약 하에서 하드웨어를 최대한 활용하고 메모리 액세스를 최소화하는 blocking parameter 값을 검색한다. 이러한 값을 찾으면 벡터화 또는 FMA(fused-multiple-accumulate)와 같은 GEMM 커널에서 사용되는 다양한 하드웨어 기능과 최적화를 활용하여 주어진 blocking parameter  값에 최적화된 고성능 코드를 생성할 수 있다. 이것은 우리의 내부 커널이 되며, target 합성곱 작업을 채우도록 타일링할 수 있다. 

 

Loops outside the inner kernel:

 내부 커널 외부의 루프에 대한 우리의 목표는 내부 커널이 가장 효율적인 방식으로 호출될 수 있도록 계산을 분할하는 것이다. 이러한 level 의 계산 루프는 서로 다른 메모리 계층에서 최적의 메모리 이동을 촉진해야 하며 다중 threading 과 같은 더 높은 수준의 병렬 처리를 허용해야 한다. 이를 달성하기 위해 이 level 에 loop ordering 기술을 적용한다. 우리는 계산을 주의 깊게 분석하고 메모리 계층의 어느 수준에 어떤 데이터를 배치해야 하는지 결정하여 level 간의 메모리 이동을 최소화하고 계산 단위 간의 병렬화 및 데이터 재사용을 장려한다. 이 결정을 기반으로 각 계산 차원 루프를 분할하고 그에 따라 순서를 지정한다.

 

 텐서의 메모리 레이아웃은 메모리 액세스 사이의 stride 을 최소화하여 더 큰 액세스 인접성을 달성하고 궁극적으로 메모리 지연 시간을 낮출 수 있기 때문에 고성능 계산에 중요하다. 알고리즘의 계산 루프 순서를 기반으로, 우리는 stride를 최소화하고 SIMD 벡터 레인 크기 또는 캐시 라인 크기와 같은 하드웨어 특성을 더 잘 지원할 수 있는 메모리 레이아웃을 검색한다.

 이 섹션에서는 설계의 알고리즘 구조에만 초점을 맞춘다.  blocking parameter 의 값 선택 및 내부 커널의 코드 생성과 같은 구현 세부 사항은 기본 하드웨어와 밀접하게 연결되어 있으므로 섹션 4에서 다룬다.

 

3.3 Designing the Inner Computation Kernel

3.3.1 Tiling to maximize data reuse :

 타일링은 연산 operand를 원하는 메모리 수준의 크기에 맞는 더 작은 블록, 즉 타일로 분할한다. 이를 통해 하위 레벨에 대한 추가 메모리 액세스 없이 계산 블록을 처리할 수 있어 주어진 메모리 계층에서 데이터 재사용을 극대화할 수 있다. 우리는 블록 매개 변수 b, c(o), h(o), w(o), c(i), h(f) 및 w(f)를 사용하여 타일의 크기를 결정하며, 각각 원래 컨볼루션 치수의 파티션을 정의한다.

 주어진 blocking parameter 에 대해, 크기가 b × c(o) × h(o) × w(o), b × c(i) × h(o) × w(o) 및 c(o) × c(i) × h(f) × w(f)인 작은 텐서가 레지스터에 로드된다. 우리는 이러한 부분집합 텐서들을 하위 텐서라고 부를 것이다. 로드된 subtensors 로부터, 총 b × c(o) × h(o) × w(o) × c(i) × h(f) × w(f) MAC 계산을 수행할 수 있다. 로드된 각 subtensors 의 크기로 MAC의 수를 나누면 표 1과 같이 출력 subtensors 의 각 요소가 출력의 경우 c(i) × h(f) × w(f) MACs, 입력의 경우 c(o) × h(f) × w(f) MACs, 필터의 경우 b × h(o) × w(o) MACs로 재사용되고 있음을 알 수 있다.

재사용 없이 MAC당 메모리 작업 수는 출력의 경우 4:2, 입력의 경우 1, 필터의 경우 1 이다. 그러나 타일링으로 얻은 재사용을 통합하면

로 축소된다. 주어진 컨볼루션 레이어에 대해 총 MAC 계산 수가 고정됨에 따라 내부 커널에 대한 관심은 이제 blocking parameters 의 최적의 조합을 선택하여 MAC당 메모리 작동을 최소화하는 데로 이동한다.

 

3.3.2 Tiling parameter simplification :

 섹션 2에서 우리는 dimensions B, H(out) 및 W(out)이 동일한 dimension 특성을 공유하며 평평하게 하고 단일 차원으로 매핑할 수 있음을 관찰한다. 따라서 b = 1, h(o) = 1을 설정하고 커널에서 w(o)에 초점을 맞춘다. 우리가 w(o)를 선택하는 이유는 W(out)이 3차원 사이의 memory 순서에서 가장 빠른(가장 안쪽) 차원이기 때문이다. 만약 b =! 1이나 h(o) =! 1이라면, 이 차원들에 elements 를 로드하는 동안 large memory stride가 존재하여 캐시 miss를 유발 할 것이다.

 우리는 또한 커널에서 H(fil)가 아닌 W(fil) 차원을 활용하는 데 중점을 둔다. 현재 ARMv8 아키텍처와 벡터 확장 NEON의 한계로 인해 내부 커널에서 W(fil)와 H(fil)를 모두 효율적으로 표현하기에는 레지스터가 충분하지 않다. 이 문제에 대해서는 섹션 4에서 자세히 설명한다.

 단순화 후에도 매개 변수 c(o), w(o), c(i) 및 w(f)는 그대로 유지된다. MAC당 메모리 연산은

로 표현할 수 있으며, 데이터 재사용을 최대화하기 위해 MAC당 메모리 연산을 최소화해야 합니다. 이를 위해 섹션 4에서 최적의 매개 변수 값을 검색하고 MAC당 개선된 메모리 작업을 원래 GEMM 커널과 비교한다.

 섹션 2에서 우리는 차원 C(out), W(out) 및 C(in)이 행렬 차원 M, N 및 K에 직접 매핑될 수 있음을 관찰한다. 결과적으로 매개 변수가 c(o), w(o), c(i) 및 w(f)인 내부 커널의 설계는 M, N 및 K에 없는 액세스 및 재사용 관계를 나타내기 위해 차원 W(fil)이 추가된 행렬 곱셈 커널로 해석될 수 있다. 이것이 우리의 방법을 GEMM 커널의 확장이라고 명명하는 이유이다. w(f) = 1인 경우, 그것은 GEMM 커널과 동일하지만 wf > 1인 경우, 로드된 subtensor에서 1D 합성곱 계산 커널이 되는 w(f)를 통해 반복하면서 여러 GEMM 계산을 수행하는 것과 동등해진다.

 

3.4 Designing the Outer Loops

3.4.1 Loop Ordering :

 내부 커널은 blocking parameters 에 해당하는 모든 subtensors 를 로드하고 SIMD FMA 명령을 사용하여 사용 가능한 모든 MAC 계산을 실행한다. 실행 후, 우리는 어떤 차원으로 반복할지 선택해야 한다.

 선택할 차원은 W(fil)이다. W(fil)는 입력 및 출력 subtensors 의 재사용 차원으로 이전 내부 커널 실행에서 최대 데이터 재사용을 허용한다. W(fil)를 통해 반복한 후, 입력 또는 필터 요소와 달리 MAC당 2개의 메모리 작업이 필요하기 때문에 C(in)를 통해 반복하고 출력 요소를 다시 사용하기로 선택한다.

 W(fil)을 통해 반복하면 레지스터에 로드된 입력 및 출력 subtensors 모두에 전체 W(fil) 재사용을 제공하기 때문에 내부 커널에서 w(f) = 1을 설정할 수 있다. 마찬가지로 C(in)을 통해 반복하면 출력 subtensors에 전체 C(in)을 제공하기 때문에 내부 커널에서 c(i) = 1을 설정할 수 있다. 그림 5(g)에서 (j)까지와 같이, 이를 통해 W(fil)과 C(in)을 통한 출력 subtensors, W(fil)을 나타내는 레지스터를 할당하지 않고도 W(fil)을 통한 입력 subtensors를 재사용할 수 있어 레지스터 사용을 줄이고 C(o)와 w(o)에 대한 더 큰 타일링 값을 허용할 수 있다.

그림 5

 c(i) = 1이 최적이지만 벡터화된 load instructions 을 사용하려면 c(i)가 SIMD 벡터 레인 크기의 4배 정도여야 한다. 다시 한 번 이 문제에 대해 섹션 4에 대해 자세히 설명한다.

 가장 바깥쪽 루프의 경우 W(out), H(out) 및 B demensions를 선택한다. 이러한 차원은 출력 텐서의 액세스 차원이므로 인덱스 간에 종속성이 없다. 다중 스레드 실행을 위해 여러 스레드에 분할 및 분산될 수 있다. 또한 이러한 차원은 필터 텐서의 재사용 차원이기 때문에 공유된 마지막 level 캐시의 필터 요소를 자연스럽게 차단하여 서로 다른 스레드가 데이터를 공유할 수 있도록 한다.

 입력 elements가 출력 elements보다 더 자주 액세스되고 입력 subtensors 가 내부 커널에서 C(in)을 통해 반복할 때 종종 큰 stride 을 일으키기 때문에 L1 캐시의 입력 elements를 차단한다. 이것은 입력 텐서의 재사용 차원이기 때문에 C(out)와 H(fil) 차원을 루프 중간에 넣는다.

 불행하게도, 모바일 프로세서의 제한된 캐시 크기 때문에, 필터 텐서는 종종 큰 채널 크기를 가진 계층들의 마지막 level 캐시에 맞지 않는다. 이를 보완하기 위해 매개 변수 cc(o)를 사용하여 C(out) 차원을 다시 분할하여 차단된 필터 크기가 마지막 수준 캐시보다 작아지도록 한다. 나머지 C(out) 루프는 B 앞에 가장 바깥쪽 루프로 배치되며, 다른 스레드 간에 분산되며, 마지막 level 캐시의 필터 데이터를 최대한 재사용할 수 있다.

 최종 알고리즘은 알고리즘 2에 나와 있다. 8~13행은 SIMD 벡터 명령어를 사용하여 전개되고 실행된다는 점에 유의 !

 

3.5 MemoryLayout

 메모리 액세스 간의 보폭을 최소화하면 액세스의 인접성이 증가하여 캐시의 활용률과 적중률이 증가합니다. 또한 프리페처 정확도를 높여 궁극적으로 각 액세스의 대기 시간을 최소화한다. 이를 위해 텐서의 메모리 레이아웃을 수정한다.

 입력 및 출력 텐서는 기존의 N-C-H-W 또는 N-H-W-C에서 N-(C/c(i))-H-W-c(i)로 수정되며, 여기서 c(i)는 입력 텐서 채널 blocking parameters 이며, 모든 레이어와 커널 구현에서 일정하다. NHWC  순서는 제안된 알고리즘 2와 함께 작동하지만, 채널 차원을 [26, 52]와 유사한 작은 SIMD 벡터 레인 크기(ci) chunks 로 나누기로 결정했다. 이는 채널 demensions 가 종종 2의 거듭제곱을 나타내기 때문에 인접 width index 의 elements 사이에 치명적인 stride를 초래한다. 채널 차원을 분할함으로써, 이러한 요소들은 지역성을 얻는 동시에 채널 차원에서 벡터화된 메모리 접근을 허용한다. 이전 솔루션과 달리 실행 중에 메모리 순서를 변경할 필요가 없다. 모든 입력 및 출력 텐서가 동일한 레이아웃을 공유하므로, 출력을 다음 레이어의 입력으로 직접 사용할 수 있다.

 필터 텐서는 알고리즘 2의 라인 5~11에 표시된 H(fil) - C(in) - W(fil) - c(o) 루프에서 반복하면서 단위 stride 을 보장하기 위해 기존의 K-C-R-S에서 (K/c(o))-R-C-S-c(o)로 수정된다. 이것은 우리의 알고리즘에서 필터 값이 가장 자주 교체된다는 것을 고려할 때 특히 중요하다. 필터 값의 스트림을 레지스터로 일정하게 유지하려면 필터 값의 순차적 액세스는 각 액세스의 대기 시간을 줄이기 때문에 중요하다.

 

3.6 Pointwise and Depthwise Convolution

 MobileNet[19, 39] 또는 MnasNet[43]과 같은 모바일용으로 설계된 많은 현대 CNN은 Pointwise 및 Depthwise 컨볼루션을 배포한다. Pointwise 컨볼루션(convolution)은 1×1 필터 공간 차원을 갖는 컨볼루션(convolution)으로 이해될 수 있으며, Depthwise 컨볼루션(depthwise convolution)은 독립적인 단일 채널 2D 컨볼루션(convolution)의 집합으로 이해될 수 있다.

 

 Pointwise 컨볼루션은 H(fil)과 W(fil)이 모두 1인 경우 GEMM 커널에 직접 매핑된다. 우리의 mGEMM 커널은 또한 W(fil) = 1일 때 GEMM 커널로 축소될 수 있다. 이는 Pointwise 컨볼루션에서 mGEMM과 기존 GEMM 사이의 알고리듬 차이가 작다는 것을 의미한다. 따라서 GEMM 최적화에 더 적합하기 때문에 포인트별 커널에 대한 개선 사항은 논의하지 않는다.

 

 그러나 Depthwise 컨볼루션에서 H(fil) 및 W(fil) 차원의 재사용 특성을 활용하려는 우리의 아이디어는 큰 영향을 미친다. Depthwise 컨볼루션에서, 다른 채널 반복에서의 계산은 서로 완전히 독립적이며 모든 출력, 입력 및 필터 요소의 교체가 필요하다. 즉, C(in) 및 C(out) demensions 는 기존의 컨볼루션과 달리 출력 및 입력 요소에 대해 더 이상 재사용을 제공하지 않는다. 따라서 출력 및 입력 요소의 재사용 기회는 H(fil) 및 W(fil) demensions 뿐이다.

 

이 속성을 더 잘 활용하기 위해 출력 및 입력 subtensors 를 재사용하기로 선택하는 기존 솔루션 커널과 달리, 우리는 내부 커널에서 필터 elements 를 재사용하고 그에 따라 계산을 루프하도록 알고리즘을 재구성한다. 그 이유는 단일 출력 채널의 완전한 Depthwise 계산에 필요한 필터 elements 의 수가 (Hfil) × W(fil)에 불과하기 때문인데, 이는 종종 레지스터에 완전히 들어갈 정도로 작다. 우리는 공동 채널에 필요한 모든 H(fil) × W(fil) 필터 요소를 load 하고, 모든 B × H(out) × W(out) 계산에서 필터 elements 를 재사용한다. 입력 및 출력 elements 는 레지스터의 필터 elements 와 함께 한 번만 사용하면 되고 다른 필터 elements 와는 함께 사용하면 안 되기 때문에 메모리에서 스트리밍된다. 따라서 데이터 재사용이 크게 증가하여 섹션 5에서 볼 수 있듯이 기존 솔루션에 비해 대기 시간이 훨씬 단축된다.