for 문과 캐시메모리.
글쓴이: kid1402 / 작성시간: 목, 2009/12/10 - 3:57오후
Cache Friendly Code 에 대해 공부하고 있는데
다음과같은 예제 코드가 나왔습니다.
Miss Rate = 1/4 = 25%
int sumarrayrows(int a[M][N])
{
int i, j, sum = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
sum += a[i][j];
return sum;
}Miss Rate = 100%
int sumarraycols(int a[M][N])
{
int i, j, sum = 0;
for (j = 0; j < N; j++)
for (i = 0; i < M; i++)
sum += a[i][j];
return sum;
}두 코드의 차이점은, 바깥문과 안쪽문에서 반복하는 행/렬이 다른것인데
무엇이 Miss rate의 차이를 만드는걸까요?
Forums:
아시다시피 캐시는
아시다시피 캐시는 메모리의 데이타를 가져 오면서 주변 데이타까지 같이 가져다가 캐시에 붙이게 되는데, 이를 감안하면 가능한한 인접한 데이타를 순차적으로 액세스하는 것이 캐시 프렌들리하다고 볼 수 있습니다.
이런.... N개의 요소가
이런.... N개의 요소가 M개 만큼 있다고 생각했었는데
처음에 나온 M개의 요소가 N개 만큼 있다고 생각해야겠군요.
Miss Rate 가 적을수록 좋은건가요?
Miss Rate가 적다라는 것은 캐시에 있을 확율이 높다라는 것인가요?
첫번째코드의 Miss Rate == 25% 가 더 좋다라면,
M < N 조건이 성립한다고 봅니다만...
From:
*알지비 (메일: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
M, N 의 크기와
M, N 의 크기와 관계없이 데이터들이 얼마나 인접해 있는가가 문제입니다.
첫번째 코드는 인접한 데이타를 액세스하므로 한번 액세스할 때 주변 데이타가 같이 따라와서 연속적인 데이타 액세스 시에 캐시 히트가 발생하게 되죠.
두번째 경우는 띄엄띄엄 떨어진 데이타를 액세스하므로 캐시 미스 확률이 높고 루프를 도는 과정에서 이전 캐시가 클리어되게 됩니다.
댓글 달기