Locality 그리고 false-sharing

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

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

즉,

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

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

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

간략히 요약하자면,

프로그래머들이 멀티스레드 프로그래밍에 어느 정도 익숙해지면서 “convoying”³ 과 같은 성능 문제를 피해야한다.

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

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

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

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

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