Cache latency와 cache hit/miss

1.
2010년 Latency가 한창 유행일 때 고민했지만 한동안 잊었던 주제입니다. 그러다가 우연한 기회에 HFT와 관련한 해외 글을 읽었습니다. 다시금 생각해보면 유의미한 이야기입니다. 특히나 요즘과 같이 마이크로초나 나노단위 초를 기준으로 경쟁을 할 때는 중요합니다. 무슨 주제냐 하면 ‘CPU Cache’입니다. 2012년에 IBM이 만든 자료중 다음과 같은 문장이 있습니다.

• Minimize memory latencies (cache misses, non-local memory accesses, page faults, swapping…)
– numactl -membind
– mlockall()
– taskset

• Minimize scheduling latencies (context switches,migration, unnecessary pre-emption…)
– taskset, cgroups
– irq binding
– real-time scheduling attributes

• Offload to hardware
– network offload

이중에서 Cache Miss가 주제입니다. 스스로 질문을 해봅니다.

“CPU Cache란?”

L1,L2,L3 Cache가 있다는 정도는 아닙다만 자세히 고민하지 않았습니다. CPU Cache Basics에 있는 내용입니다. L1, L2, L3 Cache에 대한 설명입니다.

L1 Cache (Level 1 Cache):

• L1 cache is the smallest but fastest cache located closest to the CPU cores.
• It’s divided into two parts: L1i (instruction cache) and L1d (data cache). L1i stores instructions, and L1d stores data.
• The purpose of L1 cache is to store the most frequently used instructions and data to speed up the CPU’s operations.
• It has low latency (the time it takes to access data) and is usually separate for each CPU core.

L2 Cache (Level 2 Cache):

• L2 cache is larger than L1 cache but slightly slower.
• It is shared among CPU cores in many multi-core processors.
• Its role is to store additional frequently used data and instructions that couldn’t fit in L1 cache.
• L2 cache is still faster than accessing data from RAM (main memory).

L3 Cache (Level 3 Cache, if available):

• L3 cache is even larger but slightly slower than L2 cache.
• It is shared across all CPU cores in a multi-core processor.
• L3 cache acts as a backup storage for frequently used data and instructions that couldn’t fit in L1 or L2 cache.
• Having an L3 cache can help reduce bottlenecks when multiple CPU cores are accessing memory simultaneously.

그러면 CPU Cache는 어떻게 동작할까요? Cache에서 데이타를 찾으면 Hit, 없으면 Miss입니다. Miss가 발생하면 RAM에서 데이타를 확인해야 합니다. Miss Rate가 Latency에 영향을 주는 이유입니다.

How it works:

• When the CPU needs data or instructions, it first checks if they are in the L1 cache.
• If the needed information is in the L1 cache (or L2 cache if not found in L1), it’s called a cache hit, and the CPU can quickly retrieve it.
• If the data is not in the cache, it’s called a cache miss. In this case, the CPU has to fetch the data from slower main memory (RAM), which takes more time.
• The goal of the cache hierarchy is to reduce the number of cache misses by storing the most frequently used data and instructions in the faster, smaller caches.

그러면 Latency를 줄이기 위하여 어떻게 최적화를 하여야 할까요? 같은 글입니다.

Optimization principles

Caches like L1, L2, and L3 are managed by the hardware, and as a software engineer, you don’t have direct control over which programs or data are stored in them. However, you can follow certain programming and optimization principles to increase the likelihood that your program benefits from cache usage. Here’s how:

1. Locality of Reference: Caches work best when your program exhibits good locality of reference. There are two types of locality:
   • Temporal Locality: This means that if you access a piece of data once, you’re likely to access it again in the near future. To leverage temporal locality, try to reuse data that you’ve recently accessed.
   • Spatial Locality: This refers to the tendency to access data located near recently accessed data. To benefit from spatial locality, try to access data in a sequential or predictable pattern.
2. Cache-Friendly Data Structures: Use data structures and algorithms that are cache-friendly. For example, when iterating over an array, processing elements that are stored close to each other in memory is more cache-efficient than jumping around in memory.
3. Cache Line Awareness: Cache systems typically work with fixed-size cache lines (e.g., 64 bytes). Be aware of this when designing your data structures. If you only need a small portion of a cache line, avoid loading the entire line to reduce cache pollution.
4. Compiler and Compiler Flags: Compilers can optimize code to improve cache locality. Use compiler flags (e.g., -O2 or -O3 in GCC) to enable optimizations. Additionally, understand how your compiler optimizes code for your target architecture.
5. Profiling and Benchmarking: Use profiling tools to analyze cache behavior in your program. Tools like perf (on Linux) or performance analyzers in integrated development environments (IDEs) can help you identify cache-related issues.
6. Thread Affinity: If you’re working with multi-threaded programs, consider using thread affinity techniques to bind threads to specific CPU cores. This can help minimize cache contention between threads.

2.
Cache Memory를 대략 이해했습니다. Cache Memory와 Latency를 연결할 차례입니다. Latency와 관련한 자료를 찾으면 반드시 접하는 그림중 하나가 “개발자가 알아야 하는 숫자(Latency)”라는 그림이 있습니다. 예를 들면 아래입니다.

Cache Latency는 CPU별로 다릅니다. 그리고 제조사가 내놓은 숫자와 실제로 측정한 값이 다릅니다. 앞서 소개한 자료가 설명하는 Latency입니다.

Cache latencies

Let’s compare the latencies of different memory levels, including CPU caches and RAM (main memory):

L1 Cache Latency:

• L1 cache is the fastest and has the lowest latency among all memory levels.
• Typical latency ranges from 1 to 3 cycles, which is extremely fast.
• Accessing data from L1 cache is significantly faster than any other memory level.

L2 Cache Latency:

• L2 cache has slightly higher latency compared to L1 cache.
• Typical latency ranges from 4 to 10 cycles, depending on the CPU architecture.
• It is still much faster than accessing RAM.

L3 Cache Latency:

• L3 cache has higher latency compared to L2 and L1 caches.
• Typical latency ranges from 10 to 40 cycles, depending on the CPU and cache design.
• While slower than L1 and L2, it is still much faster than RAM.

다른 글을 읽어보면 Cache Latency를 직접 측정해보라고 합니다. 이와 관련한 많은 글중 아래를 살폈습니다.

Smarter CPU Testing – How to Benchmark Kaby Lake & Haswell Memory Latency

위에서 시험한 소스는 Applied Benchmark: Memory Latency을 확인할 수 있습니다. 저는 The Mechanism behind Measuring Cache Access Latency을 따라 하였습니다.

먼저 제가 사용하는 CPU 종류와 Cache line size입니다.

위 시험을 아래의 순서를 따라 시험하고 결과를 보여줍니다.

1. Naive Thinking
2. Thinking with Hardware: Cache Line
3. Thinking with Hardware: Prefetch
4. Thinking with Compiler: Register Keyword
5. Thinking with Compiler: Touch It!

변수중 stride가 있습니다. Stride는 Strided memory access Pattern을 말하네요.

The memory access pattern is called strided when memory fields accessed are equally distant. This distance is called a stride (not to be mistaken with SIMD-stride!). A simple visualization of strided access:

1번과 2번의 시험결과입니다.

Memory latency for application software developers을 보면 Perf 명령어를 이용한 성능시험까지 합니다.

Introduction
About memory latency
How latency impacts performance – part 1
How latency impacts performance – part 2
Cache alignment
Cache prefetching
Review

3.
Cache를 보다가 예전에 Branchless Computing에서 소개한 논문을 다시금 읽었습니다.

C++ Design Patterns for Low-latency Applications Including High-frequency Trading

Download (PDF, 1.67MB)

소프트웨어를 직접적으로 개발하지 않는 입장에서 이런 글을 읽을 때면 머리에 쥐가 납니다. 그래도 겉핥기라도 하려고 시도는 합니다.. 논문에서 유심히 본 부분은 Cache와 관련한 부분입니다.

Caching: Cold Cache vs. Warm Cache는 다음과 같은 도표로 쉽게 설명합니다.

앞서 코드로 시험한 결과입니다.시험결과를 보면 267,685,006 나노초와 25,635,035나노초입니다. 차이가 큽니다.

Latency에 영향을 주는 요소들은 보면 cache가 중요합니다.

C++ patterns for low-latency applications including high-frequency trading (arxiv.org)은 앞서 논문에 대한 토론입니다. 논문에 있는 소스는 Low-Latency Programming Repository for High-Frequency Trading (HFT)에서 확인할 수 있습니다.

Cache Warming과 관련하여 좀더 읽어보도록 하죠. 두가지 Warming이 있다고 하네요. 앞서와 같은 방식이 Software Cache Warming입니다. 또다른 방식은 Hardware Cache Warming입니다. Hardware Warming은 CPU가 제공하는 기술을 이용하는 방식입니다.

On Intel, the technology is called Cache Pseudo Locking and it is implemented as a part of Intel Resource Director technology. Setting it up is not simple. The user first needs to configure a part of the cache that will be reserved for holding critical data, then this part of the cache is exposed as a character device and can be accessed using mmap system call. More info about it is available here.

AMD has a similar technology called L3 Cache Range Reservation. It allows the user to reserve a physical address range that will be kept in L3 cache. Unfortunately, AMD’s user manual only mentions this feature and doesn’t give examples on how to use it from user space.
Latency-Sensitive Applications and the Memory Subsystem: Keeping the Data in the Cache중에서

두서없지만 Cache가 Latency에서 중요함을 확인하는 시간입니다. 한걸음 더 나아가는 공부를 해볼까 합니다. 리눅스 시스템 성능을 주제로..