cpu cache line 원리

참고:
Direct Mapped Cache 를 설명 하 는 아주 심오 한 글:
http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/direct.html
CPU cache
http://en.wikipedia.org/wiki/CPU_cache
http://blog.csdn.net/zqy2000zqy/article/details/1137895
=============================================
총체 적 인식, 
cpu 의 cache 는 보통 비교적 크다.예 를 들 어 128 KB 는 고정된 크기 의 cache line 으로 나 뉘 는데 cache line 은 보통 32Byte 또는 64Byte 이다.
CPU 내부 의 cache 종 류 는 적어도 세 가지 가 있 습 니 다.
1)지령 cache
2)데이터 cache 는 보통 다단 계 multi-level 이 있다.
3)TLB 가속 가상 주소 2 물리 적 주소 변환
cache entry(cache 항목)
다음 부분 포함
1)cache line:메 인 저장 소 에서 copy 의 데이터 크기)
2)tag:cache line 에 대응 하 는 메 인 저장 소 주 소 를 표시 합 니 다.
3)falg:현재 cache line 이 올 바 르 지 않 은 지,데이터 cache 라면 dirty 가 있 는 지 표시 합 니 다.
cpu 액세스 메모리 규칙
1)cpu 는 메 인 저장 소 에 직접 접근 하지 않 고 cache 를 통 해 메 인 저장 소 에 간접 적 으로 접근 합 니 다.
2)메 인 저장 소 에 접근 할 때마다 모든 cache line 을 옮 겨 다 니 며 메 인 저장 소 주소 가 어떤 cache line 에 있 는 지 찾 습 니 다.
3)cache 에서 찾 지 못 하면 새 cache entry 를 할당 하고 메 인 메모리 copy 를 cache line 에 복사 한 다음 cache line 에서 읽 습 니 다.
cache 에 포 함 된 cache entry 항목 이 제한 되 어 있 기 때문에 적절 한 cache 도태 전략 이 있어 야 합 니 다.
일반적으로 LRU 정책 을 사용 합 니 다.
일부 메 인 저장 영역 을 non-cacheble 로 표시 하면 cache 명중률 을 높이 고 쓸모없는 cache 를 낮 출 수 있 습 니 다.
리 턴 정책
cache 의 데이터 가 업 데 이 트 된 후에 메 인 저장 소 에 다시 써 야 합 니 다.다시 쓰 는 시 기 는 여러 가지 가 있 습 니 다.
1)업데이트 할 때마다 다시 쓴다.write-through cache
2)업데이트 후 답장 하지 않 고 dirty 로 표시 하고 cache entry 가 evict 일 때 만 답장 합 니 다.
3)업데이트 후 cache entry 를 재 작성 대기 열 처럼 보 내 고 대기 열 이 여러 entry 에 수집 되 었 을 때 대량으로 재 작성 합 니 다.
질문
cache 의 데이터 가 만 료 될 수 있 는 두 가지 상황 이 있 습 니 다.
1)DMA,다른 장치 가 메 인 메모리 의 데 이 터 를 직접 업데이트 합 니 다.
2)SMP,같은 cache line 에 여러 개의 CPU 가 각각 cache 에 존재 합 니 다.그 중 하 나 는 CPU 가 업데이트 되 었 습 니 다.
cpu stall cpu 속도 위반
cache miss 때(특히 read cache miss)를 말 합 니 다.cpu 는 메모리 에서 cache 에 데 이 터 를 읽 기 를 기다 리 는 동안 할 일이 없습니다.
이 문 제 를 해결 하 는 방법 은
1)초 스 레 드 기술.CPU 는 하드웨어 차원 에서 하나의 CPU 를 두 개의 CPU 로 모 의 합 니 다.상부 에서 볼 때 두 개의 CPU 입 니 다.동시에 두 개의 스 레 드 를 실행 합 니 다.이렇게 하면 하나의 스 레 드 가 cache miss 로 인해 기다 릴 때 다른 스 레 드 가 실 행 될 수 있 습 니 다.
주 저장 소의 주 소 는 어느 cache line 에 비 춰 야 합 니까?(용어:Associativity)
맵 정책 에 따라 다 릅 니 다.
1)가장 멍청 한 주 소 는 임의의 cache line(fully associative)에 매 핑 될 수 있 습 니 다.
   문 제 는 하나의 주 소 를 찾 을 때 cache 라인 을 옮 겨 다 니 며 찾 아야 한 다 는 것 이다.이 대 가 는 받 아들 일 수 없다.
   주차 공간 을 모두 가 마음대로 세 울 수 있 듯 이 세 울 때 는 간단 하 다.차 를 찾 을 때 는 주차 공간 을 하나씩 찾 아야 한다.
   cpu 는 하나의 주소 가 cache 에 있 는 지 알 고 싶 습 니 다.모든 cache line 을 한쪽 으로 찾 아야 합 니 다.얼마나 느 려 야 합 니까?
2) Direct Mapped Cache  (1-way associative 에 해당 함)
   이것 은 hash 에 해당 합 니 다.모든 주소 가 매 핑 될 수 있 는 cache line 은 고정 되 어 있 습 니 다. 
   모든 사람의 주차 공간 은 고정 적 으로 분배 되 어 있 습 니 다.직접 찾 을 수 있 습 니 다.
   단점 은 사람 이 많 고 차 가 적 기 때문에 몇 사람 이 같은 차 를 다 투 는 바람 에 cache 탈락 이 빈번 할 수 있 습 니 다.메 인 저장 소 에서 데 이 터 를 자주 읽 어야 합 니 다.이 대가 도 비교적 높 습 니 다.
   cache 에서 cache line 의 개 수 는 모두 2 의 지수 개 이기 때문에 hash 알고리즘 은 매우 간단 합 니 다.모드 를 취하 지 않 고 메모리 주소 의 몇 bit 위 치 를 직접 꺼 내 면 됩 니 다.예 를 들 어 cache line 은 128(2^7)개 이 고 cache line 의 크기 는 32(2^5)바이트 입 니 다. 
   그러면 32 비트 주소 의 0~4 비트 는 cache line 내부 오프셋 이 고 5~11 비트 는 cache line 의 색인 으로 하면 됩 니 다.나머지 bit 12~31 은 현재 cache line 의 tag 입 니 다.tag 의 역할 을 할 때 다른 주소 도 같은 cache line 에 매 핑 될 때tag 는 두 주소 가 같은 주소 인지 비교 하 는 데 사 용 됩 니 다.같은 cache-line 이 대응 할 수 있 는 메모리 의 위치 가 매우 많 기 때 문 입 니 다.
3) 2-way associative
   fully associative 와 Direct Mapped Cache 의 절충 입 니 다.
   2-way,한 사람 에 게 두 개의 주차 공간 이 있 을 수 있 습 니 다.이렇게 주차 공간 이 차지 되 었 을 때 다른 하 나 를 찾 을 기회 가 있 습 니 다.비록 사람 이 많 지만 동시에 주차 공간 을 찾 는 사람 은 많 지 않 습 니 다.(많은 사람들의 차 가 밖 에 있 고 돌아 오지 않 은 것 과 같 습 니 다)
   그래서 2-way associative 는 2 배 크기 의 cache 와 비슷 하고 Direct Mapped Cache 전략 을 사용 합 니 다.
주의 하 세 요.이 그림 은 cache miss 율 만 통 계 했 습 니 다.full-associative 가 잘 만 든 것 이 분명 합 니 다.그러나 full-associative 로 인해 한 주소 가 cache 에 있 는 지 판단 하 는 대가 가 매우 비 쌉 니 다.따라서 생산 환경 은 보통 2-way associative 입 니 다.
======================================================
다 중 스 레 드 에서 오 류 를 피하 고 식별 하 는 공유 변수 방식 은 주로 SMP 환경 에서 cache line 이 자주 갱신 되 는 문 제 를 해결 합 니 다.
Avoiding and Identifying False Sharing Among Threads
http://software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads/
예:

//      SMP     cache      
double sum=0.0, sum_local[NUM_THREADS];
#pragma omp parallel num_threads(NUM_THREADS)
{
 int me = omp_get_thread_num();
 sum_local[me] = 0.0;

 #pragma omp for
 for (i = 0; i < N; i++)
 sum_local[me] += x[i] * y[i];

 #pragma omp atomic
 sum += sum_local[me];
}

...때문에
sum_local
배열 은 전역 변수 입 니 다.여러 스 레 드 가 접근 할 수 있 고 각 스 레 드 가 접근 하 는 곳 이 가 까 워 서 하나의 스 레 드 가 업데이트 되 고 다른 CPU 의 cache line 이 실 효 됩 니 다.
이 문 제 를 해결 하 는 방법 은?
1)서로 다른 스 레 드 간 에 전체 변 수 를 최대한 적 게 방문 하고 스 레 드 부분 변 수 를 사용 합 니 다.
2)꼭 방문 하려 면 각 스 레 드 가 직접 방문 한 지역 cacheline 을 정렬 하도록 합 니 다.
3)자주 업데이트 되 는 저장 소 와 자주 업데이트 되 지 않 는 저장 소 는 분리 된다.