캐시 라인은 어떻게 작동합니까?

캐시 라인은 어떻게 작동합니까?

---

프로세서는 캐시 라인을 통해 데이터를 캐시에 가져옵니다. 예를 들어, Atom 프로세서에서 실제 데이터의 크기에 관계없이 한 번에 약 64 바이트를 가져옵니다.

내 질문은 :

캐시에서 가져올 64 바이트는 메모리에서 1 바이트를 읽어야한다고 상상해보십시오.

내가 볼 수있는 두 가지 가능성은 64 바이트가 관심있는 바이트 아래의 가장 가까운 64 바이트 경계에서 시작하거나 64 바이트가 미리 결정된 방식으로 바이트 주위에 퍼져 있다는 것입니다 (예 : 절반 이하, 절반 위 또는 모든 것 위에).

무엇 이니?

---

로드중인 바이트 또는 단어를 포함하는 캐시 라인이 캐시에 아직없는 경우 CPU는 캐시 라인 경계에서 시작하는 64 바이트 (필요한 것보다 큰 주소 인 64의 배수)를 요청합니다. .

최신 PC 메모리 모듈은 한 번에 64 비트 (8 바이트)를 8 번의 전송 버스트로 전송 하므로 한 명령으로 메모리에서 전체 캐시 라인의 읽기 또는 쓰기를 트리거합니다. (DDR1 / 2 / 3 / 4 SDRAM 버스트 전송 크기는 최대 64B로 구성 가능합니다. CPU는 캐시 라인 크기와 일치하도록 버스트 전송 크기를 선택하지만 64B는 일반적입니다)

일반적으로 프로세서가 메모리 액세스를 예측할 수없고 (프리 페치 할 수없는 경우) 검색 프로세스는 ~ 90 나노초 또는 ~ 250 클럭 사이클 (주소를 알고있는 CPU에서 데이터를 수신하는 CPU까지)이 걸릴 수 있습니다.

대조적으로 L1 캐시의 적중은 3 또는 4주기의로드 사용 대기 시간을 가지며, 상점 재로드는 최신 x86 CPU에서 4 또는 5주기의 상점 전달 대기 시간을 갖습니다. 다른 아키텍처에서도 상황이 비슷합니다.

추가 자료 : Ulrich Drepper의 모든 프로그래머가 기억해야 할 사항 . 소프트웨어 프리 페치 조언은 약간 구식입니다. 최신 HW 프리 페처는 더 똑똑하고 하이퍼 스레딩은 P4 일보다 훨씬 좋습니다 (따라서 프리 페치 스레드는 일반적으로 낭비입니다). 또한 x86 태그 위키에는 해당 아키텍처에 대한 많은 성능 링크가 있습니다.

---

캐시 라인의 폭이 64 바이트 인 경우, 이는 64로 나눌 수있는 주소에서 시작하는 메모리 블록에 해당합니다. 어떤 주소의 최소 6 비트는 캐시 라인에 대한 오프셋입니다.

따라서 임의의 주어진 바이트에 대해, 페치되어야하는 캐시 라인은 주소의 가장 중요한 6 비트를 클리어함으로써 찾을 수 있는데, 이는 64로 나눌 수있는 가장 가까운 어드레스로 반올림하는 것에 해당한다.

이 작업은 하드웨어에서 수행되지만 일부 참조 C 매크로 정의를 사용하여 계산을 표시 할 수 있습니다.

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)

---

우선 주 메모리 액세스는 매우 비쌉니다. 현재 2GHz CPU (가장 느린 속도)에는 초당 2G 틱 (사이클)이 있습니다. CPU (현재 가상 코어)는 틱당 한 번 레지스터에서 값을 가져올 수 있습니다. 가상 코어는 여러 처리 장치 (ALU-산술 논리 장치, FPU 등)로 구성되므로 가능한 경우 특정 명령을 실제로 병렬로 처리 할 수 ​​있습니다.

메인 메모리 액세스 비용은 약 70ns ~ 100ns입니다 (DDR4가 약간 빠름). 이번에는 기본적으로 L1, L2 및 L3 캐시를 찾고 메모리 (메모리 컨트롤러에 명령을 보내 메모리 뱅크로 전송)를 누르고 응답을 기다렸다가 완료합니다.

100ns는 약 200 틱을 의미합니다. 따라서 기본적으로 프로그램이 항상 각 메모리가 액세스하는 캐시를 놓치면 CPU는 메모리를 기다리는 동안 유휴 상태 (메모리 만 읽는 경우)의 약 99,5 %를 소비합니다.

속도를 높이기 위해 L1, L2, L3 캐시가 있습니다. 그들은 칩에 직접 놓인 메모리를 사용하고 다른 종류의 트랜지스터 회로를 사용하여 주어진 비트를 저장합니다. CPU는 일반적으로 고급 기술을 사용하여 생성되고 L1, L2, L3 메모리에서 생산 오류가 발생하여 CPU를 쓸모 없게 만들 수 있기 때문에 더 많은 공간과 에너지가 필요하며 주 메모리보다 비용이 많이 듭니다. 큰 L1, L2, L3 캐시는 오류율을 증가시켜 ROI를 직접 감소시키는 수율을 감소시킵니다. 따라서 사용 가능한 캐시 크기와 관련하여 큰 절충안이 있습니다.

(현재 실제 생산 결함이 캐시 메모리 영역이 CPU 결함을 전체적으로 렌더링 할 가능성을 줄이기 위해 특정 부분을 비활성화 할 수 있도록 L1, L2, L3 캐시를 더 생성합니다).

타이밍 아이디어를 제공하려면 (출처 : 캐시 및 메모리 액세스 비용 )

• L1 캐시 : 1ns ~ 2ns (2-4주기)
• L2 캐시 : 3ns ~ 5ns (6-10 사이클)
• L3 캐시 : 12ns ~ 20ns (24-40주기)
• RAM : 60ns (120 회)

우리는 서로 다른 CPU 유형을 혼합하기 때문에 추정치 일 뿐이지 만 메모리 값을 가져올 때 실제로 어떤 일이 발생하는지 알고 특정 캐시 계층에서 적중이나 누락이 발생할 수 있습니다.

따라서 캐시는 기본적으로 메모리 액세스 속도를 크게 향상시킵니다 (60ns 대 1ns).

값을 가져 와서 다시 읽을 수 있도록 캐시에 저장하면 자주 액세스하는 변수에는 적합하지만 메모리 복사 작업의 경우 값을 읽고 어딘가에 값을 쓰고 절대 읽지 않기 때문에 여전히 느려집니다. 다시 ... 캐시 적중이없고, 죽은 느린 (이것은 우리가 순서가 잘못되어 병렬로 발생할 수 있습니다).

이 메모리 사본은 매우 중요하므로 속도를 높일 수있는 다른 방법이 있습니다. 초기에는 메모리가 종종 CPU 외부의 메모리를 복사 할 수있었습니다. 메모리 컨트롤러에서 직접 처리했기 때문에 메모리 복사 작업으로 인해 캐시가 오염되지 않았습니다.

그러나 일반 메모리 사본 외에도 메모리의 다른 직렬 액세스가 매우 일반적이었습니다. 일련의 정보를 분석하는 것이 한 예입니다. 정수 배열을 가지며 합계, 평균, 평균 또는 더 간단한 특정 값 찾기 (필터 / 검색)는 범용 CPU에서 매번 실행되는 또 다른 매우 중요한 알고리즘 클래스였습니다.

따라서 메모리 액세스 패턴을 분석함으로써 데이터를 매우 자주 읽는다는 것이 명백해졌습니다. 프로그램이 인덱스 i에서 값을 읽는 경우 프로그램도 값 i + 1을 읽을 가능성이 높습니다. 이 확률은 같은 프로그램이 i + 2 등을 읽는 확률보다 약간 높습니다.

따라서 메모리 주소가 주어지면 미리 읽고 추가 값을 가져 오는 것이 좋습니다. 이것이 부스트 모드가있는 이유입니다.

Memory access in boost mode means, that an address is send and multiple values are sequentially send. Each additional value send only takes about additional 10ns (or even below).

Another problem was an address. Sending an address takes time. In order to address a large portion of memory large addresses has to be send. In early days it meant that the address bus was not big enough to send the address in a single cycle (tick) and more than one cycle was needed to send the address adding more delay.

A cache line of 64 bytes for instance means that the memory is divided in distinct (non-overlapping) blocks of memory being 64bytes in size. 64bytes mean the start address of each block has the lowest six address bits to be always zeros. So sending these six zero bits each time is not needed increasing the address space 64 times for any number of address bus width (welcome effect).

Another problem the cache line solves (beside reading ahead and saving / freeing six bits on the address bus) is in the way the cache is organized. For example if a cache would be divided in 8 byte (64bit) blocks (cells) one needs to store the address of the memory cell this cache cell holds the value for along with it. If the address would also be 64bit this means that half the cache size is consumed by the address resulting in an overhead of 100%.

Since a cache line is 64bytes and a CPU might use 64bit - 6bit = 58bit (no need to store the zero bits too right) means we can cache 64bytes or 512bits with an overhead of 58bit (11% overhead). In reality the addresses stored are even smaller than this but there are status informations (like is the cache line valid and accurate, dirty and needs to wrote back in ram etc).

Another aspect is that we have set-associative cache. Not every cache cell is able to store a certain address but only a subset of those. This makes the necessary stored address bits even smaller, allows parallel access of the cache (each subset can be accessed once but independent of the other subsets).

There is more especially when it comes to synchronize cache/memory access between the different virtual cores, their independent multiple processing units per core and finally multiple processors on one mainboard (which there are boards housing as much as 48 processors and more).

This is basically the current idea why we have cache lines. The benefit from reading ahead is very high and the worst case of reading a single byte out of a cache-line and never read the rest again is very slim since the probability is very slim.

The size of the cache-line (64) is a wise chosen trade-off between larger cache-lines makes it unlikely for the last byte of it to be read also in the near future, the duration it takes to fetch the complete cache line from memory (and to write it back) and also the overhead in cache organization and the parallelization of cache and memory access.

---

Processors may have multi-level caches (L1, L2, L3), and these differ on size and speed.

Yet, to understand what exactly goes into each cache you'll have to study the branch predictor used by that specific processor, and how the instructions/data of your program behave against it.

Read about branch predictor, CPU cache and replacement policies.

이것은 쉬운 일이 아닙니다. 하루가 끝나고 성능 테스트를 원하는 경우 Cachegrind 와 같은 도구를 사용할 수 있습니다 . 그러나 이것은 시뮬레이션이므로 결과가 다소 다를 수 있습니다.

---

모든 하드웨어가 다르기 때문에 확실하게 말할 수는 없지만 일반적으로 "64 바이트는 가장 가까운 64 바이트 경계에서 시작합니다"는 CPU에 대한 매우 빠르고 간단한 조작이기 때문입니다.

참고 URL : https://stackoverflow.com/questions/3928995/how-do-cache-lines-work