ARM System Developer's Guide 국문판 P473 ~ P475에 보면 캐시 라인 교체 정책에 대한 예제 12.1이 나옵니다.
라운드 로빈 교체 방식과 랜덤 교체 방식의 테스트에서 엔트리 하나의 차이에 의해 라운드 로빈이 약 3배에 가까운 이상한?
시간 비효율성을 보이고 있습니다. 제가 이해한 책의 예제는 다음과 같습니다.
64개의 캐시라인을 가지는 하나의 way에서 numset = 64인 경우는 하나의 way에 존재하는 모든 캐시라인을 교체합니다.
numset = 65인 경우 라운드 로빈에서는 64라인을 모두 채우고 남은 1개는 0번 캐시라인을 교체 할거라 생각합니다.
반면 랜덤에서는 64라인을 모두 채우고 남은 1개는 0 ~ 63 캐시 라인 중 임의의 라인을 교체 할거라 생각합니다.
그런데 어찌하여 한개의 라인차이에 의해서 랜덤 방식은 0.51 => 0.58 초로 시간이 증가하나
라운드 로빈 방식은 0.51 => 2.56 초로 시간이 증가하게 되는것인가요?
예제를 잘못 이해한것 같기도 하고.
하나만 더 질문 드리겠습니다. ㅋ
캐시 미스시의 할당 정책으로 read-allocate와 read-write-allocate 두가지 방식이 있습니다.
메모리 쓰기 동작에 비해 읽기 동작이 훨씬 많이 발생 하므로 이렇게 방식을 나눠놨지 않나 생각합니다.
범용 PC든 임베디드 제품군이든 read-allocate와 read-write-allocate 두가지 중 어느 방식을 더 많이 사용하나요?
답변 부탁드립니다. ^^;
댓글 6
-
myskan
2011.07.05 15:38
-
myskan
2011.07.06 11:19
1, 3번 지우겠습니다.
김용욱님의 댓글에서 보듯이 ARM940T 의 캐시가 CAM으로 구성 된것을 고려하지 않고 설명한 것이기 때문에
질문의 답변으로 틀린것 이기 때문입니다.
-
홍문화
2011.07.05 16:02
감사합니다. 충분한 답변이 되었습니다. ㅋ
상철님께서 쓰시는 글 덕분에 많이 배우고 있습니다. ^^;
-
myskan
2011.07.05 16:58
답변이 되었다니 다행이네요.
전 홍문화님께서 올리시는 글을 보면서 스스로에게 좀더 집요하게 파고 들어야 겠다라는 생각을 많이 하고 있습니다. ^^
-
김용욱
2011.07.06 02:03
저는 해당 부분을 보고 조금 다르게 생각하였습니다. 여기서 몇가지 가정은 믿음의 도약(leap of faith)입니다. 불확실한 부분이 있기 때문에 정확한 내용을 아시는 분이 보충해주시길 부탁드리겠습니다. 제 생각은 아래와 같습니다.
테스트 루틴 readSet이 ARM940T에 최적화되어 있다고 하니 4개의 CAM입력과 64개의 way을 가진 모델[그림 12.9]일 것입니다.
주소를 0x40씩 증가시키고 있는데요. 31~8가 태그 7~4가 세트 3~0이 데이터 인덱스이니깐 세트 인덱스를 4씩 증가시키는 것입니다. (물론 태그도 변경되겠지만 일단 세트만 보겠습니다.) 세트 인덱스는 CAM 세트 선택 로직에 의해 CAM 주소로 변환 되니깐 총 16개의 세트 인덱스가 4개의 CAM주소로 변환되겠죠.
인접한 세트 인덱스가 동일한 CAM주소를 가지지 않는다고 가정하겠습니다. ARM940T는 웨이 당 4캐시 라인을 채택하고 64웨이입니다. 만약 64란 숫자가 의의가 있을려면 데이터가 같은 캐쉬 라인에서 처리되어야 합니다. 그래서 소스 코드가 항상 같은 캐쉬 라인을 지적하도록 간격을 두었을 거라 생각합니다. 또 동시에 인접한 세트 인덱스가 동일한 CAM 주소를 가지지 않아야 인접한 코드가 동일 WAY에 올라갈 가능성이 높을 거라고 생각합니다. 최대한 입접한 세트 인덱스가 동일 CAM 주소를 피하게 할려면 세트 인덱스가 4씩 증가할 때 동일한 CAM을 가지도록 설계하였을 겁니다. 아마도 4씩 세트인덱스를 증가시킨다면 항상 같은 캐시라인에 기록할 수 있을 겁니다.
그렇다면 소스코드에서 64번 데이터를 접근하는 행위는 ARM 940T의 동일한 캐쉬라인을 64웨이 모두에서 사용하는 것이라고 생각할 수 있을 겁니다. 한번 개별 웨이의 캐쉬라인에 데이터를 적재하고 나면 캐쉬 미스없이 읽어올 수 있지 않을까 생각됩니다.
반면에 65개 데이터를 접근하는 경우는 두번째 반복부터 1개씩 캐쉬 미스가 발생해서 하나의 웨이를 비우고 다른 데이터를 적재해야할 것입니다.
이때 데이터 교체를 위해 전략이 필요할텐데 랜덤 방식과 라운드 로빈 방식이 사용되는 것으로 생각됩니다. 라운드 로빈을 사용했다면 1번부터 64번까지 웨이에 데이터를 넣은 다음 65번째 데이터를 1번 웨이에 넣을 겁니다. 그럼 1번째 데이터가 필요해서 찾으면 방금 1번 웨이에 있던 1번째 데이터가 비워졌기 때문에 캐쉬 미스가 나고 2번 웨이를 비우고 1번째 데이터를 넣게 될겁니다. 2번째 데이터를 찾을 때는 또 방금 2번째 웨이를 비웠기 때문에 캐쉬 미스가 나서 실패했겠지요.
반면에 랜덤 방식을 선택했다면 어딘가는 비워졌지만 다음 데이터가 살아있을 확률이 훨씬 높습니다. 물론 바로 캐쉬 미스가 발생할 수도 있겠지만요. 65번째 데이터를 64번째 웨이를 비우고 집어넣었다면 63번째 데이터를 찾는 것은 모두 성공할 것입니다. 평균적으로 절반정도의 캐쉬라인은 건질 수 있을 겁니다.
연속으로 65개의 데이터를 접근했을 때 알고리즘의 성능차이는 그런 이유에 의해 발생하지 않았나 생각합니다. 평균적으로 수행성능이 비슷하다면 최악의 경우가 더 효율적인 애를 고르는게 좋을 것입니다.
-
홍문화
2011.07.06 12:38
와우~ 놀랍습니다. ㅋ
원채 오탈자가 많아서 ARM940T의 한 way가 64라인이라고 무심코 생각을 했었는데
그림 12.9를 참고하고 P.484를 기반으로 다시 계산한 결과 한 way가 4라인이고 한 라인은 4 word가 맞네요.
말씀 하신대로 라운드 로빈에서는 지속적으로 무식하게 캐시 미스가 발생하네요.
이렇게 생각하니 2초라는 어마어마한 시간 차이가 발생 할 수도 있다는게 확실히 이해가 됩니다.
CAM 관련 이해가 살짝 안되는 부분이 있는데 찾아보고 정 안되면 오후에 정리해서 올리겠습니다. ㅋ
상철님, 김용욱님 진심으로 감사드립니다. ^^;
.
1. 예제일 뿐입니다. 예제에서 시간의 차이는 캐시 컨트롤러의 하드웨어 구성 때문입니다.2. 캐시 라인 교체 알고리즘은 Direct Mapped Cache (1way라고 표현하겠습니다.)에서는 적용 되지 않으며
set associative 혹은 full associative 캐시의 경우에만 적용이 됩니다.
3. 네 잘못 이해 하셨습니다.예제에서 사용한 프로세서의 캐시는 64way를 가지면 하나의 way는 64개의 라인을 가지고 있습니다.그리고 예제에서는 캐시 초기화가 진행이 된 이후에 64번 접근 혹은 65번 접근이 발생합니다.예제의 캐시 초기화가 어떤 동작을 하는지 정확히 파악되지 않지만...제 생각에는 하나의 way를 초기화 할것 같습니다.따라서 초기화 이후 64번 접근 할 동안은 캐시 교체가 발생하지 않으며65번째 접근할 때 캐시 교체가 발생할 것입니다.따라서 1번에서 말씀드렸듯이 캐시 컨틀로러의 하드웨어 구성에 의한 시간차 입니다.4. 범용 캐시의 경우 WT, WB, r/w allocate 방식이 모두 독립적으로 사용자 설정이 가능합니다. 따라서 사용자가 캐시 정책을 결정 할 수 있습니다.
일반적으로 WT 방식의 캐시에서는 read-allocate을, WB 방식의 캐시에서는 read-write allocate 방식으로 운용합니다.
(당연히 하버드 아키텍쳐 구조의 명령어 캐시는 write 동작이 없으므로 read-allocate만 사용하겠지요)
충분한 답변이 되었는지 모르겠네요.