Base-Delta-Immediate Compression: Practical Data Compression for On-Chip Caches

Abstract

Cache compression → on-chip cache capacity를 증가시키고, on-chip 및 off-chip bandwidth 사용을 감소시키는 기술이다. 기존의 알고리즘들은 대부분 SW에 의해 컨트롤되는데, HW 복잡도를 증가시키고 compression/decompression 레이턴시가 매우 크다.

본 논문에선 Base-Delta-Immediate compression을 소개한다.

본 방법론은, 한 cache block 안에 들어가는 값들은 작은 range를 가진다는 점에서 착안한다. 즉, 한 블락 안에 들어가는 값들은 Delta 가 작다. 그리고 0들만 들어가거나 같은 값이 들어가는 data pattern도 자주 등장한다!

Introduction

cache 에서 중요한 파라미터 중 하나는 바로, capacity. Data compression은 capacity를 증가시키기 위한 방법론으로 다양한 시스템에서 사용되어 왔는데, modern microprocessor에선 그닥… 왜? cache에 적용하기 위해선 Fast, simple, effective해야하는데 Decomposition latency가 문제가 된다!

Compression은 cache fill이후(critical word 도착 이후)에 BG에서 수행하면 되는데… decompression의 경우 cache hit이 났을 때 수행되므로 critical path에 포함된다! (L1 cache에선 hit time이 생명인데..)

Capacity의 증대와 latency의 증가, 이 사이에서의 밸런스를 맞추는게 중요한 목표가 된다.

HW complexity의 증가(파워 등의 오버헤드), decompression latency를 작게 하는 방법론으로 BDI를 제안.

BΔI Compression

대부분의 cache line에 들어가는 값들은 위와 같이 low dynamic range를 가진다.

이 사실을 이용해 common value인 base, 차이인 delta를 이용해 더욱 컴팩트한 사이즈로 모든 값을 나타낼 수 있으며, 심지어 여러 개의 base를 가질 수 있도록 하였다. base가 2개인 경우(하나는 actual contens로부터, 하나는 0)가 가장 효율적인 옵션임을 파악하였다.

이 방법론은 i) High compression ratio → 빈번히 발생하는 패턴을 이용하기 때문

ii) Low decompression latency → masked vector addition으로 처리된다.

iii) reletively modest HW overhead and implementation complexity

의 장점을 보인다.

Base + Delta Encoding

why work?

• Regularity in the way data is allocated in the memory
• Low dynamic range of cache/memory data

nature of computation에서 발생하는 것으로 본다. 예를 들면, sparse matrix, streaming application 등