큰 행렬을 전치(transpose)하는 처리(b[j][i] = a[i][j])에서 캐시 미스가 많아지기 쉬운 이유와 대표적인 대책의 조합으로 올바른 것은 무엇입니까?

정답: C. 이유는 읽기와 쓰기 중 한쪽이 열 방향이 되는 것. 대책은 블록 단위 전치

전치에서는 a를 행 방향으로 읽으면 b에는 열 방향으로 쓰게 되고, 반대로 b를 행 방향으로 쓰면 a를 열 방향으로 읽게 되므로, 어느 한쪽은 반드시 띄엄띄엄한 접근이 됩니다. 그래서 행렬을 캐시에 들어가는 작은 블록으로 나누고 블록 안에서 전치하면, 읽어 온 라인을 다 사용한 뒤에 다음으로 넘어갈 수 있어 미스가 크게 줄어듭니다. 쓰기 쪽만 연속으로 해도 읽기가 띄엄띄엄해질 뿐이어서 근본적인 해결이 되지 않습니다. 계산량의 문제도 아닙니다.

• A. 전치는 계산이 거의 없으며, 타입을 바꿔도 해결되지 않습니다.
• B. 한쪽을 연속으로 해도 다른 쪽이 띄엄띄엄해질 뿐입니다.
• C. 올바릅니다. 반드시 한쪽이 열 방향이 되므로 블록 단위로 전치합니다.