메모리 계층 구조

위의 연결 리스트를 따라가는 처리가, 같은 수의 요소를 가진 배열을 차례로 읽는 것보다 훨씬 느려지기 쉬운 이유는 무엇입니까?

struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
    sum += p->val;
  1. A다음 요소의 주소를 현재 요소를 읽기 전까지 알 수 없어, 미스가 하나씩 차례로 일어나기 때문
  2. B연결 리스트의 요소는 캐시에 전혀 들어가지 않도록 정해져 있기 때문
  3. C포인터를 사용하는 처리에서는 CPU의 분기 예측이 반드시 실패하기 때문
정답과 해설 보기

정답: A. 다음 요소의 주소를 현재 요소를 읽기 전까지 알 수 없어, 미스가 하나씩 차례로 일어나기 때문

연결 리스트에서는 다음 요소의 주소를 p->next를 읽어야 비로소 알 수 있습니다. 요소가 메모리상에 흩어져 있으면 접근할 때마다 미스가 일어나고, 게다가 다음 주소를 알 수 없으므로 여러 미스를 겹칠 수 없어, 주기억장치의 대기 시간이 요소마다 고스란히 쌓입니다. 배열이라면 다음 주소를 계산으로 알 수 있어 프리페치나 미스의 중첩이 작동합니다. 연결 리스트의 요소도 캐시에 들어가며, 루프의 분기는 예측하기 쉬워 반드시 실패하는 것은 아닙니다.

  • A. 올바릅니다. 다음 주소를 알 수 없어 미스의 대기 시간이 하나씩 쌓입니다.
  • B. 연결 리스트의 요소도 캐시에 들어갑니다.
  • C. 루프의 분기는 규칙적이며 예측이 반드시 실패하는 것은 아닙니다.
이 분야 연습하기 분야로 돌아가기

메모리 계층 구조의 다른 문제

  1. 한 번의 미스로 64바이트 라인을 읽고 주기억장치의 대기 시간이 100 ns일 때, 동시에 처리할 수 있는 미스가 하나뿐이면 읽기 대역폭은 약 0.64 GB/s에 그칩니다. 동시에 10개의 미스를 처리할 수 있다면 대역폭은 대략 얼마가 됩니까? (다른 제약은 없다고 가정합니다)
  2. 한 번 쓴 뒤 당분간 다시 읽지 않는 큰 데이터를 쓸 때, 캐시를 거치지 않는 스토어(논템포럴 스토어, non-temporal store)를 사용하는 주된 이점은 무엇입니까?
  3. 캐시의 히트율이 95%일 때, 미스율은 얼마입니까?
  4. 미스한 라인을 주기억장치에서 읽어 올 때, CPU가 필요로 하는 워드(word)를 먼저 보내고 나머지를 나중에 보내는 기법은 무엇입니까?
  5. 위의 두 루프를 하나로 합치면(루프 융합, loop fusion) N이 클 때 빨라지기 쉬운 이유는 무엇입니까?

이 분야의 비교