[Arm프로세서] 캐시 알고리즘: 알고리즘 지역성(algorithm locality)

프로그램은 함수의 호출과 자료 구조로 구성돼 있습니다. 코드를 유심히 분석하면 자주 사용하는 자료 구조나 알고리즘이 어느 정도 정해져 있습니다. 예를 들어 링크드 리스트나 스택과 같은 데이터 구조나 알고리즘을 사용해 데이터를 관리하는 패턴을 볼 수 있습니다. 

그런데 데이터 구조나 알고리즘을 사용할 때 메모리에 접근하는 패턴을 관찰하면 시간 지역성이나 공간 지역성을 확인하기 어렵습니다. 한 가지 예를 들까요? 링크드 리스트로 데이터 관리할 때 메모리에 접근하는 패턴을 살펴보면 특정 위치에 있는 데이터에 다시 접근하지 않을 확률이 높습니다. 시간 지역성과 같은 특징을 지니지 않습니다. 또한 링크드 리스트는 배열과 달리 인접한 메모리 주소 공간에 접근하지 않아 공간 지역성에도 맞지 않습니다. 

그런데 링크드 리스트로 구성된 데이터를 어떤 패턴으로 접근할 지는 예측이 가능한데, 이를 위해서는 링크드 리스트라는 자료구조와 알고리즘적인 특정을 이해해야 합니다. 알고리즘의 특정을 활용해 프로그램이 메모리에 접근하는 패턴을 예측하는 과정을 알고리즘 지역성이라고 합니다.

#Reference Armv8: 캐시(Cache)

캐시 소개

   캐시란 무엇인가  

   메모리 아키텍처에서 캐시란  

   L1 캐시와 L2 캐시란  

       시간적 지역성(temporal locality)  

       공간 지역성(Spatial Locality)  

       알고리즘 지역성(algorithm locality)   

캐시의 기본 동작 원리

   캐시의 검색 방법

       캐시에 접근하기 위해 주소를 분류하는 방식  

       캐시의 구성 요소  

   캐시 lookup 기본 동작 원리

       캐시 히트 동작  

       캐시 미스 동작  

멀티 레벨 캐시   

   캐시의 성능 지표  

   멀티 캐시를 구성하는 원리   

   멀티 캐시 정책  

Arm Cortex 프로세서의 캐시 구조   

   Direct-Mapped 캐시 구조   

   Set-associative 캐시 구조    

   Arm Cortex 프로세서 별 캐시 스팩    

캐시 제어 레지스터

   CTR_EL0 레지스터  

   CLIDR_EL1 레지스터  

   CCSIDR_EL1 레지스터