Cache prefetching

메모리 최적화의 목적은 수행에 필요한 최소량의 메모리(값)를 가능한 빠르게 전달하는 것이다. 따라서 가능한 cache hits 를 최대화 하기 위해 데이터구조와 메모리버퍼를 주의깊게 다룰 필요가 있다. 데이터가 cache 에 없을 때, 프로세서의 prefetch 기능을 이용하여 memory 의 값을 명시적으로 cache 위로 불러올 수 있다.

prefetch 명령은 프로세서에게 특정 메모리의 값을 곧 사용할테니 미리 cache 에 준비해두라고 지시한다. bus bandwidth 가 사용 가능하다면 프로세서는 지정된 메모리 주소의 데이터를 cache 로 로드해둔다. 실제로 메모리의 값이 사용될 때가 되면, 데이터가 이미 cache 에 있으니 바로 사용가능한 상태가 된다. 또는 적어도 데이터의 처음 부분은 바로 사용가능한 상태가 된다.

prefetch 명령은 어느 cache 로 (미리)로드해둘 것인지에 따라 네가지 타입이 존재한다. 그 중 Non-temporal aligned (NTA) 는 단 한번의 읽기read만 수행할 데이터에 한해서만 사용해야 한다.¹ 만약 알고리즘이 prefetch 후에 데이터를 업데이트(read-modify-write) 하거나 한번 이상 접근access할 경우 NTA 를 사용하지 말고 T0 을 사용해야 한다.

Types

아래는 네가지 prefetch 타입을 정리한 표이다.

More

prefetch 전략은 데이터가 필요로할 때 이미 cache 에 있을때 최고의 성능을 발휘한다. 즉 이 말은 데이터가 실제 필요로하기 이전에 충분히 미리 prefetch 를 수행해야 함을 뜻한다. 얼마나 미리 수행해야 하는지는 많은 요소들에 따라 달라진다. 그러나 대략 100 clocks 전 쯤이면 적당하다.

loop 에 사용되는 데이터를 prefetching 하는 것은 손쉽게 프로그램하여 좋은 결과를 얻을 수 있는 좋은 예이다. 때때로 최상의 결과를 얻기 위해서는 두번, 네번, 혹은 loop 횟수만큼 prefetch 해야 하는 경우도 있다. prefetch 를 할 최적의 장소와 데이터를 정하기 위해서는 여러번의 시행착오(시도)가 있어야 한다. 그러나 메모리, 메모리 컨트롤러, 그리고 버스 스피드는 (기술의 발전에 따라) 계속 변하기에 prefetch 할 장소 역시 다양해질 수 있다. prefetch 는 cache line 단위로 로드한다. 그래서 지정된 메모리로부터 64 바이트까지 로드되어진다.

너무 잦은 prefetch 사용은 오히려 성능을 저하시킨다.

Example

아래 코드는 16 번의 loop 후에 사용될 데이터를 미리 prefetch 하는 예제이다.

for ( i = 0; i < 1000; ++i )
{
    x = fn( array[ i ] );
    _mm_prefetch( array[ i + 16 ], MM_HINT_T0 );
}

See also

• SIMD
• Cache

Favorite site

• Wikipedia (en) Cache prefetching
• Software Prefetch - z3moon.com

References