[Embedded System Lab] Chapter 8 - Tiling

"Tiling"

[Objective]

Tiling을 통해 제한된 On-Chip Memory 환경에서 데이터 재사용을 극대화하고, Deep Learning 가속기의 연산 효율을 향상시키는 원리 이해하기

[Theory]

▣ Limited On-Chip Memory

> Scale

· 심층 신경망 Model은 일반적으로 (수백만 ~ 수십억)개의 Parameter와 연산을 포함

→ 이를 저장하고 처리하기 위해 (수십 MB ~ 수 GB) 단위의 방대한 메모리 용량을 요구

> Constraint

· Deep Learning 가속기의 On-Chip Buffer(SRAM)는 Chip 면적과 비용의 제약으로 인해 용량이 매우 제한적(수백 KB ~ 수 MB)

→ 거대한 Model Data를 한 번에 모두 수용 불가

Q) 수 GB의 거대한 데이터를 수 MB의 On-Chip Buffer를 갖는 가속기에서 한 번에 처리할 수 있는가?

▣ Tiling

· Deep Learning 가속기 설계에서 제한된 On-Chip Memory 용량 내에서 데이터 재사용을 극대화

    → 에너지 효율성과 처리량을 향상 시킴

· 거대한 DNN 연산 작업을 작은 조각(Tile)으로 나누어 Memory 계층 구조의 각 Level에 맞추는 과정을 의미

· 값비싼 Off-Chip Memory로 이동하는 횟수를 줄이고, 데이터가 PE 근처의 빠른 Buffer에 오래 머물게 하여 성능 최적화

▣ Nested Loop (중첩 Loop)

· 심층 신경망의 고차원 연산을 Index 공간에서 기술한 기본 계산 표현

· 다차원의 데이터를 처리하기 위해 여러 개의 Loop가 중첩된 형태로, Algorithm의 실행 순서와 방법을 정의

▣ Nested Loop for Memory Hierarchy

· Memory 계층 구조를 명시적으로 반영한 계층적 중첩 Loop 기반 계산 표현

· 각 Memory Level별 Tiling을 통해 작업 단위(Tile)와 데이터 상주 범위를 정의

· 각 Tile Level은 Memory Level(Ex. DRAM, On-Chip Buffer 계층) 및 병렬 자원(Ex. PE Array)에 대응됨

    + Tile의 시공간적 실행 구간 동안 해당 Level에서 처리되도록 Scheduling됨

▣ HW Constraint

· 메모리 계층과 병렬 자원을 고려하여, Loop Tiling 및 병렬화 과정에서 반드시 만족해야 하는 HW 한계

> On-Chip Buffer Capacity

· Tile 연산 수행 시점에 필요한 Input/Weight/Output Tile 데이터의 총합은 Buffer 용량을 초과할 수 없음

→ T_Input + T_Weight + T_Output ≤ C_Buffer

· 한 Buffer 계층에 저장되는 Tile들의 크기 총합은 Buffer 용량을 초과할 수 없으며, 이를 초과할 경우 Tile을 더 잘게 쪼개야 함

· On-Chip Buffer 용량은 각 메모리 계층에서 허용 가능한 최대 Tile 크기를 결정하는 1차 제약

> PE Array Sizes & Shapes

· 사용 가능한 PE의 총 개수와 배열의 차원(Ex. 1D, 2D)은 어떤 Loop 차원을 병렬로 Mapping 할 수 있는지를 규정

    (Ex. 2D PE Array에서는 병렬화로 한 번에 처리 가능한 작업 크기가 배열의 가로, 세로 크기에 의해 제한)

→ PE 배열의 크기와 모양은 공간 병렬화의 형태와 병렬도(Parallelism Degree)를 결정

> NoC(Network-On-Chip) Topology & Routing Flexibility

· PE 배열이 공간 병렬도의 물리적 상한(크기/형상)을 정한다면, NoC는 해당 병렬도를 위해 필요한 데이터 분배/집계 방식을 규정하여 "어떤 Loop 차원을 어느 PE 축(x, y)에 Mapping 할 수 있는가"를 제한

    (Ex. PE Array의 x축 연결이 Broadcast로 고정되어 있다면, x축에는 PE들이 동일 데이터를 공유가 가능한 Loop 차원만 가능하며, 서로 다른 데이터 조각을 요구하는 차원은 불가)

→ NoC의 Routing 유연성에 따라 특정 차원은 공간적 분할 가능성이 달라짐

▣ Temporal Reuse

· 동일한 데이터 Tile을 시간 축으로 Reuse하는 형태로, On-Chip Buffer에서 발생

· Loop Tiling과 순서는 데이터가 Buffer에 상주하는 시간을 결정 → 시간적 재사용 정도를 좌우

· 충분한 시간적 재사용은 하위 메모리 계층으로의 반복적인 데이터 이동을 줄이는 핵심 수단

→ 어떤 데이터(Input/Weight/Output)가 해당 Buffer에서 오래 유지되며 재사용되도록 Scheduling 되는지에 따라 Buffer Level에서 Input/Weight/Output 고정 IS/WS/OS Dataflow가 결정됨

▣ Spatial Reuse

<출력 재사용>

<입력 재사용>

· 동일한 데이터 Tile을 여러 PE가 동시에 활용하는 Reuse 형태로, 병렬화된 연산기 배열(Ex. PE Array)에서 발생

· 동일 데이터를 여러 연산에 동시에 사용함으로써, 메모리 접근을 줄이고 병렬 처리 효율 향상 가능

· 단, 이러한 재사용은 병렬 구조와 데이터 전달 방식에 의해 제한

▣ Spatio-Temporal Mapping(HW Mapping)

· 시공간 Mapping은 HW 제약을 만족하는 범위 내에서 시공간 재사용을 극대화 하는 것을 목표

· 병렬 연산 자원을 효과적으로 활용하고, Off-Chip Memory 접근을 최소화하여 연산 성능 및 에너지 효율을 향상 시킴

· 하나의 데이터 Type (Input/Weight/Output)에 대한 재사용을 강화하면, 다른 데이터의 재사용이나 병렬성은 제한될 수 있음

    (Ex. Weight를 오래 유지하려면 출력이나 입력 Tile의 접근 수가 증가할 수 있음)

∴ 시공간 Mapping은 어떤 데이터의 재사용을 우선할지 선택 필요

▣ Scheduling Scheme(계획)

· 연산을 시공간에 배치(Mapping)하고, 데이터의 Stationary 위치(Dataflow)를 함께 결정

→ HW 제약을 만족하며, 동시에 데이터 이동을 최소화 하도록 설계됨

▣ Layer별 Tensor/연산 특성 차이

· 각 Layer는 서로 다른 Input/Weight/Output Tensor의 크기와 차원 비율이 서로 다름

→ Layer마다 재사용 특성과 병렬화 가능성이 달라지며, 선호하는 Scheduling 계획 또한 서로 다름

∴ 모든 Layer에 완벽하게 들어맞는 단일 Scheduling Scheme은 존재 X

[Summary]

· Tiling : 제한된 On-Chip Memory 환경에서 큰 DNN 연산을 처리하기 위한 핵심 기법

· Nested Loop를 통해 Convolution 연산의 반복 구조를 표현

· Memory Hierarchy에 맞게 Tile 단위로 분할함으로써 Buffer Capacity Constraint를 만족시킬 수 있음

· Tile Size는 Input/Weight/Output Tile의 총 크기가 On-Chip Buffer 용량을 넘지 않도록 결정 & 데이터 재사용성과 병렬성 고려

· Temporal Reuse : 동일 데이터를 시간적으로 반복 사용하는 방식

· Spatial Reuse : 동일 데이터를 여러 PE가 동시에 사용하는 방식

· Dataflow : 어떤 데이터를 Stationary하게 유지할 것인지를 결정(IS/WS/OS)

· Scheduling Scheme : HW 제약을 만족하면서 시공간적 재사용을 극대화하고 Off-Chip Memory 접근을 최소화하는 방향으로 설계

[Reference]

· Tiling_8 (Embedded System Lab : Chapter8) - William J. Song