Locality 그리고 false-sharing

object님의 art.oriented 블로그에서 얼마 전에 false-sharing이 일어날 경우에 성능이 떨어지는 것에 관해 퀴즈를 내고 / 정답과 설명을 한 적이 있다. 퀴즈에서는 false-sharing이 아주 극단적으로 일어나는 경우를 보여주고, 실제 실행시켜보면 성능이 크게 떨어지는 것을 확인할 수 있다 — 물론 multi-core CPU 여야 하지만 :)

False-sharing 은 현대의 멀티코어 CPU가 메모리에서 데이터를 읽어올 때 Word 단위 (=native int 의 크기) 로 읽어오는게 아니라, 메모리 I/O의 효율성을 위해 cache에 저장하는 단위[1] 로 읽어오면서 생기는 문제다.

즉,

  1. Core 0가 메모리 1000 번지에 write 연산
  2. Core 1가 메모리 1008 번지에 write 연산

이런 두 개의 흐름이 동시에 진행될 때, 1, 2가 독립적으로 실행되지 못하고((다만 1000번지와 1008번지는 같은 캐쉬라인 위에 있다고 생각해야 한다)), CPU – Memory 버스사이에서 하드웨어적인 lock 을 잡게 되서 생기는 문제다. (각각 실행되는게 아니라 둘 중 하나가 먼저, 나머지 하나가 나중에 실행된다) 즉, 1이 실행되면 CPU의 cache-coherency protocol[2] 로 인해서 2가 실행되기전에 업데이트가 이루어지고, 이로 인해 HW 병목이 생긴다.

오늘자의 DDJ 에서도 허브 셔터가 "Maximize Locality, Minimize Contention"이란 제목을 걸고 비슷한 문제를 설명한다 — 다만 메모리를 프로그래머가 보통 다루게 되는 2개의 레벨에서 모두 설명한다.

간략히 요약하자면,

프로그래머들이 멀티스레드 프로그래밍에 어느 정도 익숙해지면서 "convoying"[3] 과 같은 류의 삽질은 하지 않게 되었다.

그렇지만 false-sharing 처럼 캐쉬라인을 고려하지 않고 프로그래밍을 하는 경우에 사실상의 convoying이 나타나게 되고 — 동일 메모리 영역(=동일 캐쉬라인) 에 접근하게 되면 말짱 꽝이란 것. HW단에서 convoying — 이로 인해 멀티코어 CPU를 제대로 활용하지 못하게 된다는 것

이런 식으로 문제를 제기하고 있다.

그리고는 메모리 I/O의 두 단계에서 지역성(locality)를 확보할 것을 권고(?)하고 있다. 그리고 글 제목에서처럼 캐쉬라인을 정말 필요한 때만 공유되게해서, 한 데이터 영역(=CPU 관점에서는 캐쉬라인, 페이징 관점에서는 페이지)에 대한 contention을 억제할 수 있게 프로그래밍 하라고 설명.

  • OS가 관리해주는 메모리 단위인 페이지에서 같이 쓰는 데이터가 같이 올라가도록 할 것
  • 서로 다른 코어에서 접근할 수 있는 영역이면 캐쉬 라인 단위로 떨어질 수 있게 적절한 패딩을 사용할 것[4]
  • 논리적으로 같이 사용되는 데이터라도, 성능을 위해선 서로 떨어뜨리는 것을 고려할 것 — 즉 정말 자주 같이 쓰이면 한 캐쉬라인 + 한 페이지 안에 있게히고, 자주 같이 안 쓰이면 페이지까지 달라도 괜찮게 할 것

뭐 고전적이라면 고전적일 컴퓨터 구조 / OS 의 주제이긴한데, 그래도 다시 한 번 곱씹어보게 읽어보면 좋은 글이다 :)

  1. 흔히 cache-line 이라고 부름 []
  2. 각각의 코어가 가지고 있는 cache의 데이터 중 주소가 겹치는 영역에 대해 어느 한 쪽이 업데이트되면 다른 쪽에도 이를 반영해주는 HW 구현 []
  3. 단일 lock에 개별 스레드들이 한 줄로 서서 그 lock을 잡지 않고선 별다른 연산을 못하는 현상. 즉 동시실행이 안되고 직렬 실행이 되는 것 []
  4. 허브 셔터가 언급하는 것처럼 공간을 더 써서 속도를 올리는 고전적인 예일듯 []

Published by

rein

나는 ...

3 thoughts on “Locality 그리고 false-sharing”

  1. 회사에서 숙제로 scalable malloc 구현하라고 해서 찾아보던 중 false sharing 문제가 중요하다고 하길래 구글링을 했더니 여기로 오네요… 방가방가워요;ㅁ;/

Leave a Reply