Happy to visit my research note ^^

Digital Design & Computer Arch. More Caches & Multiprocessor Caches 본문

System Storage & Security

Digital Design & Computer Arch. More Caches & Multiprocessor Caches

Liam Lim 2023. 3. 10. 14:25
728x90

prof. Onur Mutlu

ETH Zürich

Spring 2020

 

 Cache는 Main Memroy에서 읽은 데이터를 빠르게 접근할 수 있도록하는 임시 storage이다. Cache는 속도가 빠른 장치와 속도가 느린 장치 사이에 위치하며, 속도가 빠른 장치에서 읽어온 데이터를 캐시에 저장하여 빠르게 접근할 수 있다.

 Cache는 주로 block이라고 부르는 fixed size의 데이터 덩어리로 구성되어 있다. 캐시에 데이터가 저장될 때, 해당 데이터를 찾기 위한 Key 역할을 하는 고유한 Address가 함께 저장된다. 이러한 주소를 통해 cache에 저장된 데이터를 검색하고 접근할 수 있다.

 Cache의 structure는 크게 두 가지로 나눌 수 있다. Direct Mapped Cache와 Associative Cache이다. direct mapping cache는 main memory의 block을 하나의 cache line에 저장한다. 이 때, block address를 cache line address로 사용한다. associative cache는 main memory의 block을 여러 줄에 나누어 저장한다. 이 때, block address를 cache의 line address가 아닌 cache 내에서 random하게 선택된 tag와 비교한다.

 cache는 주로 성능을 향상시키기 위한 목적으로 사용된다. 하지만 cache의 크기는 제한되어 있으므로 cache miss가 발생하면 느린 main memory에서 데이터를 가져와야 하므로 성능이 저하될 수 있다. 따라서 적절한 캐시 크기와 캐시 알고리즘을 선택하는 것이 중요하다.

 Cache 구조에서 " address "는 메모리에서 가져온 데이터 블록이 캐시에 저장될 위치를 나타내는 주소이다. 이 주소는 cache의 index와 tag로 변환된다.

 

 " Tag "는 cache에서 저장된 block의 메모리 주소와 일치하는 정보를 포함하는 bit pattern이다. cache의 tag는 # cache line에 대한 메모리 주소의 일부를 나타내며, tag와 index를 조합하여 cache line의 실제 메모리 주소를 계산할 수 있다.

 

 " Tag store "는 cache에서 검색된 data block이 cache line에 저장될 때, 해당 data block과 관련된 메모리 주소의 정보를 저장하는 공간이다. Tag store는 cache line에 저장된 data block의 memory address information을 비교하여 cache에서 원하는 데이터를 검색한다. Tag store는 cache index와 함께 사용되며, cache index와 일치하는 cache line에서 cache block을 찾고, tag를 사용해서 해당 block이 필요한 데이터인지 확인한다. cache line의 크기와 같은 cache의 다른 속성들과 함께, tag store는 cache capacity, performance and 동작 방식에 영향을 미친다.

 

 " Data store "는 메모리에서 가져온 data block이 cache에 저장되는 공간을 말한다. cache에서 데이터를 저장하거나 검색할 때 data store가 사용된다.

 

 " Hit "은 cache에서 data block이 검색되는 경우를 나타내며, 이 경우 해당 data block이 cache에 존재한다.

 

 " Miss "는 cache에서 data block이 검색되지 않는 경우를 나타내며, 이 경우 해당 data block이 cache에 없어서 memory에서 가져와야 한다. 이 과정은 cache performance에 부정적인 영향을 미친다.

Set Associativity 

 

 Set-associative (set 연관성)은 cache 구조에서 사용되는 cache mapping 방식 중 하나이다. 이 방식에서는 cache 내의 모든 block이 동일한 index를 가지지만, 각각의 index는 여러 개의 set으로 구성된다.

 예를 들어, 2-way set-associative cache는 index를 두 개의 set으로 구성하고, 각 set은 2개의 cache line을 포함한다. 따라서, 2-way set-associative cache는 전체 cache block 수의 절반만큼의 set이 있고, 각각의 set은 2개의 cache line을 포함한다.

 이러한 set-associative 방식은 direct mapped cache와 비교하여 적은 메모리를 사용하면서도 더 나은 cache performance를 제공한다. set-associative cache는 direct mapped cache와 달리, cache line이 여러 개의 set 중 하나에 할당될 수 있기 때문에, cache line이 적중되지 않는 경우에도 cache line이 존재하는 set에서 더 높은 performance를 발휘할 수 있다.

 하지만, set-associative cache는 전체 cache block 중 일부만을 포함하는 set에 대해서도 검색을 수행해야 하기 때문에, 검색 시간이 더 오래 걸릴 수 있다. 또한, set-associative cache는 direct mapped cache보다 복잡한 하드웨어 회로가 필요하다.

 

 Addresses 0 and 8 always confict in direct mapped cache 는 (+참고 1) direct mapped cache에서 발생하는 현상 중 하나이다. 

 direct mapped cache에서는 memory address를 cache line에 직접 매핑한다. 이렇게 하면 memory address가 한 개의 cache line에만 mapping되므로, 서로 다른 두 개의 memory address가 같은 cache line에 mapping될 수 없다.

 그러나, 만약 두 개의 memory address가 cache index 부분에서 동일한 값을 가지면, 같은 cache line에 mapping될 수 있다. 이러한 상황을 cache conflict라고 한다.

 Addresses 0 and 8 always confict in direct mapped cache는 이러한 cache conlifct 현상을 나타내는 문장이다. 예를 들어, 8 byte 크기의 cache가 있다고 가정하면, 주소 0과 주소 8은 모두 cache index 부분에서 0을 가지므로, 같은 cache line에 매핑된다. 이러한 cache conflict는 cache performance를 저하시킬 수 있으며, 이를 해결하기 위해 associative 를 높인 cache를 사용하는 등의 방법이 있다.

 direct mapped cache에서는 cache line의 index 부분이 cache size를 결정한다. 즉, cache size가 2^n일 때, index 부분은 n bit로 표현된다.

 따라서, 8byte 크기의 cache가 잇다면, index의 3bit로 표현되며, cache line의 주소는 index와 tag로 구성된다. 이때, 주소 0과 8은 index부분에서 0을 가지므로, 같은 index를 가지게 된다. 이에 따라, 같은 cache line에 매핑되게 된다.

 이 현상은 direct mapped cache에서는 발생하는 일이다. 반면, assosiativity가 높은 cache에서는 index 부분 뿐 아니라, tag 부분도 함께 사용되어 cache line의 주소가 결정되므로, 이러한 충돌이 발생하지 않는다.

 

 또한 이것의 해결방안으로 8개의 block을 가진 하나의 열 대신 4개의 block을 가진 2개의 열을 가지면 된다. 즉, associativity가 높은 cache를 사용하는 것 외에도, cache를 더 작은 block으로 분할하고, 각 block을 서로 다른 열에 mapping하므로써 충돌 문제를 해결할 수 있다. 이렇게 하면 한 열의 index에 여러 block이 mapping되지 않으므로 conflict 문제를 해결할 수 있다.

 집합에 대한 연관성 memory를 사용하는 것은 복잡성과 성능 사이의 trade-off를 갖는 것이다. 이 방법을 사용하면 충돌을 줄일 수 있지만, cache performance가 더 많이 제한될 수 있다.

What is in a Tag store Entry?

 Valid bit, Tag, Replacement policy.

 

Replacement policy bit는 cache line이 치환될 때 사용되는 bit이다. 이 bit는 tag store 내부의 각 cache line과 함께 저장된다. cache line이 처음에 load될 때, 이 bit는 일반적으로 0으로 설정된다. 그러나 cache line이 다른 라인으로 치환될 때, bit 값이 변한다. 이 비트는 일반적으로 가장 오래된 cache line을 나타내는 LRU(Least Recently Used) 방식의 치환 policy를 사용한다.

 Tag store의 각 entry는 tag field, valid bit, Dirty bit와 함께 replacement policy bit를 사용하여 가장 오래된 cache line을 식별하고, 그것을 치환하는 새로운 데이터로 업데이트한다. 이를 통해 cache line의 치환을 최적화하고, cache performance를 향상시킨다.

 Dirty bit는 cache line의 데이터가 main memory와 다르게 변형되었는지 여부를 나타내는 bit이다. 만약 cache line의 data가 main memory와 다르게 변형되었다면, dirty bit는 1로 설정된다. 이렇게 함으로써, memory에서 cache로 데이터가 복사될 때, cache line이 메모리와 일치하지 않는 경우 memory에 해당 데이터를 쓰기전에 cache line의 내용을 memory에 갱신해야 함을 나타낼 수 있다.

 Write-back과 write-through cache는 memory에 data를 쓰는 방식에서 차이가 있다.

 Write-through cache는 memory에 write operation이 발생할 때마다, 해당 데이터가 동시에 cache와 memory에 모두 쓰인다. 이 방식은 write operation을 보장하고, cache line과 memory의 consistency를 유지할 수 있다. 하지만 이것은 write operation에 대한 부담이 크기 때문에, performance의 하락을 야기시킨다.

 Write-back cache는 cache line에 데이터가 변경될 때, 해당 데이터가 cache에만 쓰여지고, memory에는 쓰이지 않는다. 이 방식은 memory에 대한 write operation이 줄어들기 때문에 performance의 향상을 볼 수 있다. 그러나, 이 방식은 cache line이 memory와 일치하지 않게 되는 문제가 발생할 수 있으며, 이 경우 dirty bit가 사용된다.

 Dirty bit는 cache lne의 변경 여부를 나타내기 때문에, cache line이 memory와 일치하지 않는 경우, cache line의 data가 memory에 쓰일 때, 변경된 memory만을 memory에 쓰게 된다.

 따라서, write-back과 write-through cache는 memory에 대한 데이터의 write 방식에서 차이가 있으며, 어떤 방식을 사용할지는 system의 요구 사항과 성능 등을 고려해서 결정된다.

Handling Writes (1)

 Cache에서 수정된 데이터를 다음 레벨로 쓰는 시점은

 Write through cache : write가 발생하는 시점에 즉시 쓴다.

 Write back cache : block이 제거될 때 쓴다.

 

 Wrie-back cache는 cache block을 제거하기 전에 여러번 수정 작업이 일어날 수 있다는 특징이 있다. 이는 cache level 간 bandwidth를 적게 사용하고 energy를 절약할 수 있는 장점이 있다. 그러나, 이를 위해서는 해당 block이 수정됐다는 것을 알리는 dirty bit을 tag store에 추가해야 한다.

 

 Write-through는 더 간단한 방식으로 cache를 처리할 수 있다. 모든 레벨이 항상 최신 데이터를 유지하기 때문에 consistency coherence가 더욱 단순해진다. 그러나, write operation의 bandwidth를 많이 사용하며, (+참고 2) no combining of writes.

 

Handling Writes (2)

 Write miss가 발생하면, 해당 데이터가 cache에 없다는 것을 의미한다. 이때, allocate on write miss 방식은 cache에 해당 block을 할당하고 그 후 데이터를 기록하는 방식이다. 반면, No-allocate on write miss 방식은 해당 block이 cache에 없을 때 기록을 포기하고 다른 memory level에서 데이터를 가져오는 방식이다.

 "Allocate on write miss" 방식은 캐시에 write miss가 발생했을 때 해당 block을 할당하고 그 후 데이터를 기록하는 방식입니다. 이 방식은 여러 개의 write operation을 하나의 block으로 결합할 수 있어서, 다음 memory level로 전송하는 데이터 양을 줄일 수 있습니다. 또한, read miss와 write miss를 동일하게 처리할 수 있어서, 코드를 더 간단하게 유지할 수 있다. 하지만, 전체 cache block을 전송해야 한다는 단점이 있다. 이는 불필요한 데이터 전송으로 인해 대역폭이 낭비될 수 있습니다.

 "No-allocate on write miss는 write miss"가 발생했을 때 캐시 블록이 할당되지 않는 캐시 관리 기술로, 쓰기 연산이 캐시를 건너뛰고 다음 수준의 메모리 계층에서 직접 수행됩니다. 쓰기의 지역성이 낮은 경우 이 기술은 캐시 공간을 절약하고 읽기 작업의 캐시 적중률이 더 좋아질 수 있어 이점이 될 수 있습니다. 그러나 이로 인해 더 많은 읽기 미스가 발생할 수 있으며, 캐시에 할당되지 않은 블록은 다시 캐시에 가져올 때까지 후속 읽기 요청에 의해 검색될 수 없습니다.

Handling Writes (3)

만약 프로세서가 짧은 시간 동안 전체 블록에 대해 쓰기 작업을 수행한다면 어떻게 될까요?

 이 경우, 캐시 일관성 유지 문제가 발생할 수 있습니다. 만약 블록의 일부만 캐시에 로드되어 있다면, 프로세서가 다른 부분에 대해 쓰기 작업을 수행할 때, 캐시에는 해당 블록의 일부만 업데이트 되고, 나머지 부분은 이전 값이 그대로 남아 있을 수 있습니다. 이러한 경우, 캐시 일관성 유지를 위해 캐시 블록 전체를 무효화하고, 다시 메모리로부터 로드해야 합니다. 이는 쓰기 작업의 오버헤드를 증가시키는데, 이러한 문제를 해결하기 위해 캐시 일관성 프로토콜을 사용합니다. 캐시 일관성 프로토콜은 캐시 블록을 무효화하고 다시 로드하는 등의 일관성 유지 작업을 자동으로 수행합니다.

 

캐시 관리에서 발생할 수 있는 문제를 짚고 가야하는 데, 만약 processor가 전체 block을 작은 시간동안에 걸쳐 쓴다면, block을 cache로 가져올 필요가 있는 지?

 이 경우, cache의 write policy와 관련이 있다. 일반적으로 cache는 데이터를 읽을 때 빠른 응답 속도를 제공하기 위해 사용됩니다. 그러나 데이터를 쓸 때 캐시를 사용하는 방식은 쓰기 정책에 따라 다릅니다. 만약 Write-Through 캐시 정책을 사용한다면, 데이터는 메모리와 캐시 모두에 쓰이기 때문에 블록을 먼저 캐시로 가져오는 것이 좋습니다. 하지만 Write-Back 캐시 정책을 사용한다면, 데이터는 캐시에만 쓰이고, 메모리는 갱신되지 않습니다. 이 경우 전체 블록을 캐시로 가져오지 않고, 데이터를 쓸 때마다 캐시 블록을 갱신하면 됩니다.

 

 cache block은 일반적으로 고정된 크기를 가지고 있으며, 예를 들어 64바이트일 수 있습니다. 만약 프로세서가 해당 블록 전체에 대해 짧은 시간 동안 여러 번 쓰기 작업을 수행한다면, 이를 모두 메모리에 기록하는 것보다 캐시에 데이터를 유지하는 것이 더 효율적일 수 있습니다. 하지만 캐시 블록은 일반적으로 유효 비트와 dirty 비트가 블록 전체에 대해 설정되기 때문에, 블록 전체가 아닌 일부분만 수정하는 경우에도 해당 블록 전체가 dirty로 표시되어 메모리로 전체 블록을 기록해야 합니다. 이는 불필요한 대역폭 낭비를 초래할 수 있습니다.

Subblocked (Sectored) Cache

 이 아이디어는 cache block을 subblock(또는 sector)으로 나누는 것이다. 각 subblock마다 별도의 valid 및 dirty bit가 있다. 요청 시 subblock(또는 일부 subblock)만 할당한다.

 이 방법의 장점으로는 다음과 같다.

   - 전체 cache block을 cache에 전송할 필요가 없다. (write는 subblock을 유효하게 하고 업데이트하기만 하면 된다.)

   - cache에 subblock을 전송할 때 자유도가 더 높아진다. (전체 cache block을 전송하지 않고 subblock만들 전송해도 된다.) ( 독자적인 판단에 따라 몇 개의 subblock을 읽을지 ..)

 단점으로는 다음과 같다.

   - 더 복잡한 design이 필요하다.

   - 공간 지역성을 완전히 활용하지 못할 수 있다. ㅡ> cache block을 세분화하여 일부만 가져오는 방식을 사용할 경우, 인접한 데이터 block이 전부 가져와지지 않을 가능성이 있다. 이 경우, 인접한 데이터 block에 대한 cache miss가 발생할 수 있으며, 공간 지역성을 완전히 활용하지 못한 것으로 볼 수 있다.

Instruction vs. Data Cache

 

 Instruction cache와 data cache는 프로세서가 필요한 명령어(instruction)와 데이터(data)를 저장하고 불러오는 역할을 한다.

  Instruction cache는 프로세서가 다음에 실행할 명령어를 가져와서 미리 저장해두는 cache이다. processor가 다음에 실행할 명령어는 메모리에서 가져와야 하는데, 이를 매번 가져오면 시간이 많이 소요됩니다. Instruction cache는 이러한 지연을 줄이기 위해 메모리에서 가져온 명령어를 캐시에 저장해두고, 다음에 실행될 때 캐시에서 빠르게 가져오는 역할을 합니다.

  Data cache는 프로세서가 작업할 데이터를 가져와서 미리 저장해두는 캐시입니다. 프로세서가 작업하는 데이터는 메모리에서 가져와야 하는데, 이를 매번 가져오면 시간이 많이 소요됩니다. Data cache는 이러한 지연을 줄이기 위해 메모리에서 가져온 데이터를 캐시에 저장해두고, 다음에 작업할 때 캐시에서 빠르게 가져오는 역할을 합니다.

 Instruction cache와 Data cache는 각각 프로세서가 필요로 하는 정보를 저장하고 불러오는 역할을 하지만, 저장하는 정보의 종류와 특성이 다르기 때문에 별도의 캐시로 구분됩니다. 또한, 각각의 캐시는 독립적으로 동작하며, Instruction cache에서 저장된 정보는 Data cache에서 사용할 수 없으며, 그 반대도 마찬가지입니다.

 

Unified 캐시는 명령어 캐시와 데이터 캐시를 하나의 캐시로 합친 것입니다. 

 장점: 캐시 공간의 동적 공유: 분리된 명령어 캐시와 데이터 캐시의 정적 분할로 인해 과다한 공간 할당이 없으며, 따라서 캐시는 언제든지 어떤 것이 더 필요한지에 따라 명령어나 데이터 중 필요한 것에 동적으로 더 많은 공간을 할당할 수 있습니다. 

 단점: 명령어와 데이터가 서로 간섭하여 cache hit rate이 감소하고 캐시 미스가 증가할 수 있습니다. 명령어와 데이터 접근은 프로세서 파이프라인의 서로 다른 단계에서 발생합니다. 따라서, 효율적인 명령어와 데이터 접근을 위한 적절한 위치를 찾기 어려울 수 있습니다.

Multi-level Caching in a Pipelined Design

 첫 번째 레벨 캐시는 명령어 캐시와 데이터 캐시로 구성되며, 주기 시간에 크게 영향을 받습니다. 이러한 캐시는 작고 연관성이 낮으며, 지연 시간이 매우 중요합니다. 태그 저장소와 데이터 저장소는 병렬로 액세스됩니다.

 두번째 레벨 캐시는 적중률과 접근 지연 시간을 균형잡는 결정이 필요합니다. 보통 대용량이며, 고 연관성을 가지며, 지연 시간은 그다지 중요하지 않습니다. 태그 스토어와 데이터 스토어는 직렬로 액세스됩니다.

 시리얼 vs. 병렬 액세스

시리얼: 두 번째 레벨 캐시는 첫 번째 레벨 캐시 미스시에만 액세스됩니다.

따라서 두 번째 레벨은 첫 번째 레벨에서와는 다른 액세스 패턴을 볼 수 있습니다. 첫 번째 레벨 캐시는 일부 시간 및 공간 지역성을 걸러내므로 관리 정책이 다릅니다.

Cache Size

 캐시 크기는 데이터 전체(태그를 제외한)의 용량을 의미합니다. 크기가 더 크면 시간적 지역성을 더 잘 활용할 수 있습니다. 하지만 항상 크다고 좋은 것은 아닙니다. 캐시 크기가 무조건 크면 성능이 더 좋아진다는 것은 아니며, 캐시 크기를 적절히 선택하는 것이 중요합니다. 적절하지 않은 크기의 캐시는 적중률을 저하시키고, 적절한 크기의 캐시는 적중률을 향상시키는 효과를 발휘할 수 있습니다.

 Working set : application이 실행되는 동안 참조하는 데이터의 전체 집합을 의미한다. 이 동안의 시간 간격 내에서 해당 application이 접근하는 모든 데이터를 포함하는 것이 working set이다.

Block Size

 블록 크기(Block size)는 address tag와 관련된 데이터의 크기를 말합니다. 여러 계층 간 전송 단위가 되지 않을 수도 있습니다. 서브 블로킹(Sub-blocking)은 블록을 여러 조각으로 나눈 것입니다. 각 조각마다 별도의 유효(valid) 비트와 변경(dirty) 비트를 가집니다.

 블록 크기가 너무 작으면 공간 지역성을 잘 활용하지 못하며 태그 오버헤드가 커집니다.

 반면 블록 크기가 너무 크면 블록 수가 적어져 시간 지역성을 활용하는 데 제한을 받으며, 공간 지역성이 높지 않은 경우 캐시 공간과 대역폭/에너지를 낭비합니다.

Large Blocks : Critical-Word and Subblocking

 대용량 캐시 블록은 캐시로 채우는 데 시간이 오래 걸릴 수 있습니다. 이 경우 캐시 라인의 중요한 워드를 먼저 채우거나, 채우는 작업이 완료되기 전에 캐시 액세스를 다시 시작함으로써 시간을 단축할 수 있습니다.

 큰 캐시 블록은 버스 대역폭을 낭비할 수 있습니다. 이를 해결하기 위해서는 블록을 서브블록으로 나누어 각각에 대해 별도의 유효 비트와 더티 비트를 할당하는 것이 좋습니다. 이 기법은 쓰기 지역성이 낮을 때 캐시 공간과 대역폭을 절약할 수 있기 때문에 유용합니다.

Associativity

 인덱스 (set)에 있는 블록의 개수는 캐시의 직접 연관성, 연관성 및 집합 연관성과 같은 구조에 따라 다릅니다. 직접 연관성 캐시에서는 한 인덱스에 하나의 블록만 할당되므로 인덱스에 하나의 블록만 존재할 수 있습니다. 반면에 연관성이 있는 캐시나 집합 연관성 캐시에서는 여러 개의 블록이 같은 인덱스에 존재할 수 있습니다. 이 수는 캐시의 연관성 수와 집합의 크기에 따라 결정됩니다. 예를 들어, 4-way set associative cache에서는 하나의 인덱스에 4개의 블록이 존재할 수 있습니다.

Larger associativity

 보다 큰 연관성은 충돌을 줄이는 데 도움이 되어 더 낮은 미스율을 가져옵니다. 그러나 그만큼 높은 히트 지연 시간과 면적 비용을 야기하며, 어느 정도 이상은 성능 향상에 한계가 있을 수 있습니다.

Smaller associativity

적은 associativity는 캐시 구성 요소 비용을 낮출 수 있으며, 캐시에 액세스할 때 더 낮은 지연 시간을 제공할 수 있습니다. 특히 L1 캐시에서는 중요합니다.

 

 캐시의 associativity가 2의 거듭제곱이어야 한다는 규칙은 아니지만, 대개는 2의 거듭제곱으로 구성됩니다. 이는 캐시 인덱스와 태그를 쉽게 계산할 수 있기 때문입니다. 또한 2의 거듭제곱으로 만들면, 하드웨어의 구현이 간단해지고, 논리 회로가 작아질 수 있어 전력 소모가 줄어들게 됩니다. 따라서 대부분의 캐시에서는 2의 거듭제곱의 associativity를 사용합니다.

Classification of Cache Misses

 

Compulsory miss는 주소 (블록)에 대한 첫 번째 참조가 항상 미스를 발생시키는 것을 말합니다. 그 이후의 참조는 캐시 블록이 아래의 이유로 대체되지 않는 한 항상 캐시 히트가 되어야 합니다. 이는 해당 데이터에 대한 최초 접근이기 때문에 이전에 캐시에 저장되어 있지 않으므로 발생하는 현상입니다.

 

용량 미스(Capacity miss)는 캐시가 필요한 모든 것을 저장할 만큼 충분히 크지 않은 경우 발생합니다. 용량 미스는 동일한 용량을 가진 최적의 대체를 가진 완전히 연관된 캐시와 비교하여 발생하는 미스를 의미합니다. 즉, 용량 미스는 캐시 용량 자체의 한계로 인해 발생하는 미스입니다.

 

캐시의 associativity가 낮을 때, 둘 이상의 메모리 블록이 같은 셋 (set)에 매핑되는 경우 충돌 (conflict)이 발생하며, 이는 conflict miss로 분류됩니다. 충돌은 대개 높은 연관성의 캐시에서 발생하는 경우가 많습니다. 충돌 미스는 캐시에서 필요한 데이터가 이미 캐시에 있는데도 불구하고 캐시 블록이 이미 가득 차 있는 경우에 발생할 수 있습니다. 충돌 미스는 대개 교체 알고리즘을 통해 해결됩니다.

 

How to Reduce Each Miss Type

 Compulsory Miss(의무적 미스)는 특정 블록이 최초로 참조될 때 발생하는 캐시 미스입니다. 이는 캐시에서 아직 블록이 존재하지 않기 때문에 발생하는 것입니다. 이 경우 캐시를 사용하여 미스를 방지할 수 없지만, Prefetching(미리 가져오기)를 사용하여 필요한 블록을 미리 가져와서 이후의 미스를 방지할 수 있습니다. 이를 통해, 실행되어야 할 다음 블록이 미리 캐시에 로드되어 처리가 가능해집니다.

 Conflict miss는 보통 직접 연관성 캐시에서 발생하는데, 인덱스가 한정되어 있기 때문입니다. 이를 해결하기 위해 연관성을 높이는 방법으로는 보조 캐시(victim cache)를 사용하거나 더 나은 무작위 인덱싱 방식을 적용하는 등의 방법이 있습니다. 또한 소프트웨어 힌트를 사용하여 캐시 라인에 적극적으로 접근하거나 일부 데이터를 캐시해두는 등의 최적화를 할 수 있습니다. 이를 통해 캐시 충돌을 최소화하고 캐시의 성능을 향상시킬 수 있습니다.

 Capacity miss는 캐시 용량이 충분하지 않아 모든 필요한 데이터를 담지 못한 경우 발생합니다. 이는 동적으로 크기가 조정되는 fully-associative cache에서 최적의 교체를 수행하는 것과 같은 용량의 fully-associative cache에서 발생하는 미스로 정의됩니다. 따라서, 이러한 용량 미스를 줄이기 위해 우리는 캐시 공간을 더욱 효율적으로 활용하거나, 각 "계산 단계"가 캐시에 적합하게 들어갈 수 있도록 작업 집합과 계산을 나누는 소프트웨어 관리를 할 수 있습니다.

How to improve Cache Performance

 

캐시 성능을 향상시키는 데 있어서 3가지의 기본적인 목표가 있다. 

미스율(Miss rate)을 줄이는 것: 블록을 다시 가져오는 데 비용이 더 많이 드는 블록이 제거되어 성능이 저하될 수 있음에 유의해야 한다. 

miss latency 또는 miss cost을 줄이는 것 

hit latency 또는 hit cost을 줄이는 것 

 

위의 세 가지 목표는 모두 성능에 영향을 미친다.

Improving Basic Cache Performance

 

Miss rate 감소 :

더 높은 결합도(associativity),

결합도 대안/보완 Victim cache, hashing, pseudo-associativity, skewed associativity 등 ,

더 나은 교체/삽입 정책,

소프트웨어 접근 방법

 

Miss latency/cost 감소 :

다중 레벨 캐시,

Critical word first,

Subblocking/sectoring ,

더 나은 교체/삽입 정책

Non-blocking caches(여러 캐시 미스 동시 처리) ,

초당 여러번의 캐시 접근 ,

소프트웨어 접근 방법

Software Approaches for Higher Hit Rate

 

 데이터 액세스 패턴 재구성 및 데이터 레이아웃 재구성은 캐시 성능 개선을 위한 소프트웨어 접근 방식입니다. 

이를 통해 데이터 액세스 패턴과 레이아웃을 최적화하여 캐시 사용을 최대화할 수 있습니다. 대표적인 기술로는 루프 교환(loop interchange), data structure separation/merging (데이터 구조 분리/병합), blocking(블로킹) 등이 있습니다. 이러한 기술을 사용하여 캐시의 공간 지역성과 시간 지역성을 최대한 활용할 수 있습니다.

Restructuring Data Access Patterns (1)

 

아이디어: 데이터 레이아웃 또는 데이터 액세스 패턴 재구성 예시: 만약 열우선 메모리 레이아웃인 경우 x[i+1,j]는 x[i,j] 뒤에 따라옵니다. x[i,j+1]은 x[i,j]에서 멀리 떨어져 있습니다.

Poor code		
for i = 1, rows
      for j = 1, columns
            sum = sum + x[i,j]

 

Better code			
for j = 1, columns
      for i = 1, rows
           sum = sum + x[i,j]

 

이를 loop interchange라고 합니다. 

다른 최적화도 캐시 히트율을 높일 수 있습니다. 루프 퓨전, 배열 병합 등

Restructuring Data Access Paterns (2)

 Blocking 또는 Tiling은 배열을 다루는 루프를 계산 청크로 분할하여 각 청크가 캐시에 데이터를 보관할 수 있도록 하는 기술입니다. 이를 통해 서로 다른 계산 청크 사이에서 캐시 충돌을 피할 수 있습니다. 기본적으로 작업 집합을 캐시 크기에 맞게 분할하여 각 부분이 캐시에 들어갈 수 있도록 하는 것입니다. 이 기술은 Tiling이라고도 불립니다.

Restructuring Data Layout (1)

struct Node {
     struct Node* next;
     int key;
     char [256] name;
     char [256] school;
}

while (node) {
      if (nodekey == input-key) {
      	// access other fields of node
      }
      node = nodenext;
}

 

 위 코드에서는 포인터를 이용해 링크드 리스트를 traversal하고, 각 노드의 키를 검사한 뒤 해당 노드의 다른 필드에 접근합니다. 이때, 각 노드의 다른 필드인 name과 school은 크기가 256바이트로 매우 큽니다. 그러나 노드를 한 번에 하나씩 순회하므로 각 노드의 키만이 캐시 라인에 저장되고, name과 school은 저장되지 않습니다. 그 결과, 다른 필드에 접근할 때마다 캐시 미스가 발생하며, 캐시의 히트율이 낮아집니다. 이는 매우 큰 링크드 리스트에서 성능 문제를 야기할 수 있습니다.

Restructuring Data Layout (2)

struct Node {
     struct Node* next;
     int key;
     struct Node-data* node-data;
}

struct Node-data {
     char [256] name;
     char [256] school;
}

while (node) {
      if (nodekey == input-key) {
      	// access nodenode-data
      }
      node = nodenext;
}

 

 위 코드는 연결 리스트를 순회하면서 노드에 저장된 key와 입력된 key가 같은지 비교하고, 같으면 노드의 다른 필드에 접근하는 코드입니다. 그러나 노드에는 key 이외에도 긴 문자열인 name과 school이 포함되어 있으며, 이들이 캐시 라인에 채워지면서 다른 필드에 대한 접근이 느려질 수 있습니다. 

 이에 대한 해결책으로, 자주 사용되는 필드를 따로 떼어내어 새로운 데이터 구조체에 저장하는 것이 제안됩니다. 이를 통해 빈번하게 사용되는 필드에 대한 접근 성능이 향상될 수 있습니다.

 누가 이 작업을 수행해야 할까요? 이는 프로그래머, 컴파일러, 프로파일링, 하드웨어 등 다양한 요소들이 결정할 수 있습니다. 어떤 필드가 자주 사용되는지는 동적 분석이나 프로파일링을 통해 확인할 수 있습니다.

Caches in Multi-Core Systems

캐시 효율성은 멀티코어/멀티스레드 시스템에서 더욱 중요해집니다. 

메모리 대역폭은 귀중한 자원입니다. 

캐시 공간은 코어/스레드 간에 한정된 자원입니다. 

멀티코어 시스템에서 캐시를 어떻게 설계해야 할까요? 많은 결정사항이 있습니다. 

공유 캐시 vs 개인 캐시 

전체 시스템 성능을 극대화하기 위한 방법은 무엇인가요? 

공유 캐시에서 다른 스레드에 대한 QoS를 어떻게 제공할까요? 

캐시 관리 알고리즘은 스레드를 인식해야 할까요? 

공유 캐시에서 각 스레드에 대해 공간을 어떻게 할당해야 할까요?

Private vs. Shared Caches

 

프라이빗 캐시 (Private cache): 캐시는 하나의 코어에 속해 있습니다. (공유 블록은 여러 캐시에 있을 수 있음) 

쉐어드 캐시 (Shared cache): 캐시는 여러 코어에 공유됩니다.

Resource Sharing Concept and Advantages

 

 하드웨어 컨텍스트를 위한 하드웨어 리소스를 전용으로 할당하는 대신, 여러 컨텍스트에서 공유할 수 있도록 하는 아이디어입니다. 이는 기능 단위, 파이프라인, 캐시, 버스, 메모리와 같은 여러 하드웨어 리소스에 적용될 수 있습니다.

 

이 아이디어의 장점은 다음과 같습니다. 

 리소스 공유는 활용도 및 효율성을 향상시킵니다. 즉, 처리량이 증가합니다. 리소스가 하나의 스레드에 의해 사용되지 않을 때 다른 스레드가 사용할 수 있으며, 공유 데이터를 복제할 필요가 없습니다. 

 통신 지연 시간을 줄입니다. 예를 들어, 멀티스레드 프로세서에서는 여러 스레드 간에 공유되는 데이터를 동일한 캐시에 유지할 수 있습니다. 

 공유 메모리 프로그래밍 모델과 호환됩니다.

Resource Sharing Disadvantages

 

 자원 공유는 자원 경합을 유발한다.

자원이 사용 중이면 다른 스레드는 사용할 수 없다.

한 스레드가 공간을 점유하면 다른 스레드는 재점유해야 한다.

때로는 각 스레드의 성능을 감소시킨다. 스레드 성능이 단독 실행할 때보다 떨어질 수 있다.

성능 격리를 제거한다. 실행 간 성능이 일관되지 않을 수 있다.

스레드 성능은 공동 실행 중인 스레드에 따라 달라질 수 있다. 제어되지 않은 (자유로운) 공유는 QoS를 저하시킨다.

불공정성과 굶주림을 유발한다.

 

공유 자원을 효율적이고 공정하게 활용해야 한다.

Shared Cachees Between Cores

 

장점: 

높은 유효 용량 

사용 가능한 캐시 공간의 동적 분할 

정적 분할로 인한 조각화 없음 

한 코어가 일부 공간을 사용하지 않으면 다른 코어가 사용 가능 

캐시 블록이 하나의 위치에 있으므로 일관성 유지가 더 쉬움

 

단점: 

느린 액세스(캐시가 코어와 긴밀하게 결합되어 있지 않음) 

코어가 다른 코어의 액세스로 인한 충돌 미스 발생 

상호 코어 간 간섭으로 인한 미스 발생 

일부 코어가 다른 코어의 히트 레이트를 떨어뜨릴 수 있음 

각 코어에 최소 서비스 수준 또는 공정성을 보장하기가 더 어려움(얼마나 많은 공간, 얼마나 많은 대역폭?)

Cache Coherence

 

여러 개의 프로세서가 동일한 블록을 캐시하는 경우, 모든 프로세서가 일관된 상태를 볼 수 있도록 어떻게 보장할까요?

 

이를 위해 캐시 일관성 프로토콜이 사용됩니다. 캐시 일관성 프로토콜은 다수의 캐시를 가진 시스템에서 데이터 일관성을 보장하기 위한 규약으로, 캐시 간에 데이터를 주고받을 때 지켜야 하는 규칙을 정의합니다.

 

캐시 일관성 프로토콜은 쓰기 일관성과 읽기 일관성으로 구성됩니다. 쓰기 일관성은 캐시 내의 데이터가 메인 메모리의 데이터와 일치하도록 하는 규칙을 정의합니다. 읽기 일관성은 캐시에서 데이터를 읽을 때, 해당 데이터가 다른 캐시에서 변경되지 않은 경우 항상 일관된 값을 반환하도록 하는 규칙을 정의합니다.

 

캐시 일관성 프로토콜은 캐시 라인에 상태 비트를 추가하여 구현됩니다. 상태 비트는 해당 캐시 라인이 어떤 상태인지 나타내며, 쓰기나 읽기 등의 작업이 수행될 때마다 적절하게 변경됩니다. 이를 통해 다른 프로세서에서 해당 캐시 라인을 변경할 때, 해당 상태 비트가 변경되어 캐시 일관성이 유지됩니다.

Cache Terminology

 

Capacity (C):

캐시에 저장된 데이터 바이트의 수입니다.

 

Block Size(b) :

cache에 한 번에 가져오는 데이터의 byte 수이다.

 

Number of blocks (B = C/b) :

캐시에 있는 블록의 수이다. B =  C/b

 

Degree of associativity (N) :

하나의 집합(set)에 포함된 block 수이다.

 

Number of sets (S = B/N) :

각 memory address가 정확히 하나의 캐시 집합에 매핑된다.

How is data found?

 

Cache는 S개의 set으로 구성됩니다. 

각 메모리 주소는 정확히 하나의 set에 매핑됩니다. 

캐시는 세트 당 블록 수에 따라 분류됩니다. 

직접 매핑 캐시: 세트 당 1개의 블록 

N-way set associative 캐시: 세트 당 N개의 블록 

완전 연관 캐시: 모든 캐시 블록이 하나의 세트에 있음 

각 조직을 용량 (C = 8 words), 블록 크기 (b = 1 word), 블록 수 (B = 8)로 가정하여 캐시를 분석합니다.

Direct Mapped Cache

 

 

 

 

Multiprocessor Caches

Example : Problem with Shared Caches 1,2

 

 

Kim et al., “Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture,” PACT 2004.

 

 Kim et al.의 논문에서는 shared cache에서 발생할 수 있는 문제를 예시로 제시한다. 여러 개의 core가 동시에 같은 shared cache에 접근할 경우, cache resource를 두고 경쟁하게 된다. 이는 conflict을 일으키고 cache hit 비율의 감소로 이어지며, performance degradation을 유발할 수 있다. 또한, 몇몇 core가 cache resource를 독점하는 반면, 다른 core가 cache resource가 부족해질 수 있다. This can lead to unfair outcomes.

 

 

Kim et al., “Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture,” PACT 2004.

 

 또한, shared cache architecture에서 cache가 개별 core와 긴밀하게 결합되어 있지 않기 때문에, private cache와 비교하여 access latency가 높아질 수 있으며, 이는 performance 측면에도 영향을 미친다. 이러한 문제를 해결하기 위해 kim et al.은 shared cache를 dynamic하게 분할하여 처리하는 fair하고 effective한 cache sharing & partitioning mechanism을 소개한다. 이를 통해 throughput을 극대화하고 fairness를 챙기고 interference를 최소화한다.

 

Kim et al., “Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture,” PACT 2004.

 

t2's throughput can be significantly reduced due to unfair cache sharing.

 

 정리하자면, system의 대부분은 data를 저장하고 이동시키는 shared resource이다. 예를 들어, memory, cache, bus, disk 등이 shared resource에 해당된다. 이러한 shared resource는 여러 processor나 core에서 동시에 접근하게 되는데, 이로 인한 priority를 기반으로한 데이터 접근 경쟁이 발생하고 이에 따른 performance degradation과 불공정한 cache 공유 등의 문제가 발생할 수 있다. 이러한 문제를 해결하기 위해서는 데이터 접근 경쟁을 최소화하고, shared resource를 효율적으로 사용할 수 잇는 mechanism과 algorithm이 필요하다.

Cache Coherence: Whose Responsibility?

 

 software :

  cache가 software에게 보이지 않을 때, programmer는 coherence를 보장할 수 있을 까

  ISA가 cache flush instruction을 제공하면 어떨지 ..?

    - FLUSH-LOCAL A : processor의 local cache에서 address A를 포함하는 cache block을 flush 혹은 invalidate한다.

    - FLUSH-GLOBAL A : 모든 다른 processor의 cache에서 address A를 포함하는 cache block을 flush 혹은 invalidate한다.

    - FLUSH-CACHE X : cache X의 모든 block을 flush 혹은 invalidate한다.

 

hardware :

  software의 작업을 단순화한다.

  하나의 아이디어는 processor가 write operation을 할 때 block A의 모든 다른 복사본을 invalidate하는 것이다.

A Very Simple Coherence Scheme (VI)

 

 Cache들은 shared bus를 통해 서로의 write/read operation을 감시한다. 만약 processor가 block에 write를 하면, 다른 모든 processor들은 해당 block을 invalidate한다.

 

A simple protocol :

write-through cache, no-write-allocate cache

local processor의 cache block 조작 : PrRd, PrWr

bus에 보내지는 block의 조작 : BusRd, BusWr

(Non-)Solutions to Cache Coherence

 

No hardware based coherence ( cache coherence는 hardware 기반이 없다)

  cache coherence는 software's responsibility

  microarchitecture의 일을 더 쉽게 만든다.

 

  일반 programmer의 일을 매우 어렵게 만든다.

    - program의 correctness를 유지하기 위해 hardare cache를 유지해야 하는가

 

  software coherence를 유지하기 위한 overhead (e.g., page protection and page-based software coherence)

 

모든 cache는 모든 processor 간에 공유된다.

  no need for coherence

  shared cache가 bandwidth bottleneck이 된다.

  low-latency cache access를 갖는 scalable system을 설계하는 것은 매우 어렵다.

Maintaining Coherence

 

 여러 processor들이 같은 memory 위치를 consistent하게 볼 수 있도록 보장해야한다.

 

 P0에 의한 location A의 write는 언젠가는 P1에서도 보여야 하고, A에 대한 모든 write는 어떤 순서로든 어떤 processor에서도 볼 수 있어야 한다.

 

 cache coherence는 (+참고) write propagation과 (+참고) write serialization을 제공해야 한다.

 write serialization을 위해서는 모든 processor에서 같은 memory 위치의 순서를 제공하기 위한 global point of serialization이 필요하다.

Hardware Cache Coherence

 

Basic idea :

  processor or cache는 memory 위치에 대한 write 또는 update를 모든 다른 processor에게 broadcast한다. 해당 위치를 가지고 있는 다른 cache는 local 복사본을 update or incalidate한다.

 

To major approach :

  snoopy bus : 모든 operations이 shared bus에 broadcast된다.

  Directory based : mediator가 각 request에 대한 permission을 부여한다.

 

자세한 내용은

해당 class에서 학습할 수 있다.

Capacity Misses

 

 cache는 모든 관심 데이터를 한 번에 보유할 수 없을 정도로 작다. cache가 가득 차고 program이 cache에 없는 data X에 access하려고하면, X를 위해 공간을 만들기 위해 Y data를 cache에서 제거해야 한다. 그리고 이어서 program이 다시 Y에 access하려고 하면 capacity miss가 발생한다. X는 주소에 따라 특정 집합(set)에 배치된다.

 

direct mapped cache에서는 X를 놓을 수 있는 곳이 한 곳 뿐이다.

 

associative cache에서는 set 내에 X를 놓을 수 있는 다른 방법이 있다.

 

Y를 어떻게 선택하여 다시 필요할 가능성을 최소화할지?? ㅡ> algorithm

LRU (least recently used) block으로 대체 : cache가 가득 차 있을 때, 집합 내에서 the least recently used block을 제거한다.

Types of Misses

 

Compulsory miss : 데이터가 처음 access될 때 발생하는 miss

 

Capacity miss : cache가 모든 관심 데이터를 한 번에 저장할 수 없을 정도로 작은 경우 발생하는 miss

 

Conflict miss : 관심 데이터가 cache에서 동일한 위치에 mapping되는 경우 발생하는 miss

 

Miss penalty : low level의 memory hierarchy에서 block을 검색하는 데 걸리는 시간

LRU Replacement

# MIPS assembly

lw $t0, 0x04($0)
lw $t1, 0x24($0)
lw $t2, 0x54($0)

 

 

lw $t0, 0x04($0) :

 해당 명령어는 차례대로 $0에서 0x04만큼 떨어진 memory 위치에서 data를 로드하고, 이를 register $t0에 저장하라라는 의미이다. 이후 명령어들은 해당 자리에 keyword만 바꿔서 해석해주면 된다.

 위 그림을 보면 가장 먼저 들어온 data를 지우고 LRU bit인 0을 1로 증가시킨 다음 새로운 the least LRU data를 지우고 그위에 새로운 데이터를 write하는 것을 확인할 수 있다.

 

 

 

 

 

 

 

 

+ 개념 참고

 

 

(+참고 1)

 Direct Mapped Cache는 가장 간단한 형태의 Cache이다. 이러한 Cache는 memory address를 cache line에 직접 매핑한다. 즉, 각 memory address는 오직 한개의 cache line에만 mapping된다.

 direct mapped cache는 구현이 간단하고, 적은 hardware resource를 사용하므로 일반적으로 작은 규모의 cache에서 많이 사용된다. 그러나, direct mapped cache는 cache conflict ( 캐시 충돌 ) 문제가 발생할 수 있다. cache conflict는 서로 다른 두 개의 memory address가 같은 cache line에 mapping되는 현상이다. 이러한 cache conflict는 cache performance를 저하시키는 원인이 된다.

 direct mapped cache는 # associativity(연관성)이 낮아 충돌이 발생할 가능성이 높지만, cache line의 memory address를 직접 매핑하기 때문에 검색 속도가 빠르다. 따라서, direct mapped cache는 작은 규모의 cache에서 주로 사용되며, 대규모의 cache에서는 보다 높은 associativity을 가지는 연관성 cache를 사용하는 것이 일반적이다.

+

 

(+참고 2)

 write-through cache에서 no combining of writes란, cache에서 write가 발생할 때마다 해당 데이터를 main memory에 즉시 쓰는 방식에서, 한 번의 write operation에 대해 여러 번의 memory access가 발생하지 않도록 하는 것을 의미한다. 다시 말해, 하나의 write operation이 발생하면 해당 data를 main memory에 빠르게 쓰고, 이후 다른 write operation이 발생하면 이전에 쓴 데이터를 다시 빠르게 읽어들이지 않고 바로 main memory에 쓰는 것이다. 이 방식은 write operation에 대한 latency를 최소화하여 처리 속도를 높이기 위해 사용된다.

+

 

 

 

 

 

# 용어 참고

 

# cache line

 cache line은 cache의 기본 단위 중 하나이다. cache line은 일반적으로 main memory에서 읽어온 데이터의 일부를 저장하며, 캐시에서 데이터 블록이 검색될 때 전체 데이터 블록이 아닌, 해당 데이터 블록의 일부인 cache line만 검색된다.

 cache line의 크기는 cache의 성능과 용량에 영향을 미치는 중요한 요소이다. cache line의 크기가 클수록 더 많은 데이터가 한 번에 cache에 저장될 수 있으므로, 높은 cache performance를 얻을 수 있다. 그러나 cache line의 크기가 너무 크면, cache line이 다른 데이터를 저장하지 못하고 메모리 공간을 차지하게 되므로, cache capacity가 낭비될 수 있다.

 cache line은 또한 데이터를 저장할 때 valid(유효) bit와 tag(태그)를 포함한다. valid bit는 해당 cache line이 유효한 데이터를 포함하는지 여부를 나타내며, tag는 cache line에 저장된 데이터의 메모리 주소 정보를 포함한다. 이를 통해, cache는 검색된 데이터 블록이 cache line에 존재하는 데이터인지를 확인할 수 있다.

 

 정리하면, cache line에는 memory에서 읽어온 데이터의 일부가 저장되고, cache에서 data block이 검색될 때 cache line을 통해 빠르게 찾아볼 수 있다. Data store는 cache에 저장되는 data block의 공간을 의미하고 address는 cache에 저장되어있는 data block의 주소를 의미한다. cache line은 데이터 저장시 valid bit와 tag를 같이 저장하는 데, tag는 cache line에 저장된 데이터의 메모리 주소 정보를 포함하고, tag store는 cache에서 data block을 검색할 때 사용되는 공간이다. 따러서, tag store는 cache line의 메모리 주소 정보와 tag 정보를 사용해서 cache line에서 검색할 데이터를 식별한다. cache에서 해당 data block이 있으면 hit, 없으면 miss.

#

 

# associativity (연관성)

 cache에서의 associativity는 cache 내의 하나의 셀이 몇 개의 memory block을 저장할 수 있는지를 나타내는 지표이다. cache 내의 셀이 여러 개의 메모리 블록을 저장할 수 있을 때, 이를 "연관성이 높다"고 이야기 한다.

 direct mapped cache에서는 cache의 한 셀이 메모리 상의 오직 하나의 block만을 저장할 수 있으므로, associativity가 매우 낮다. 반면에 높은 associativity를 가지는 associative cache는 한 셀이 여러 개의 memory block을 저장할 수 있으므로, cache의 크기를 줄이면서도 높은 적중률을 유지할 수 있다.

#

728x90

'System Storage & Security' 카테고리의 다른 글

Storage Systems and Security (prof. ahn)  (0) 2023.04.29
'System Storage & Security' Related Articles more
Comments