IPC와 False Sharing

1.
멀티코어시대가 열리면서 메시징시장은 변화합니다. 그중 하나가 IPC 지원입니다. 코어와 코어간의 통신이 중요해지면서 IPC가 각광을 받기 때문입니다. ZeroM도 그렇고 ZeroAOS도 IPC를 쓰레드간의 통신을 위하여 사용합니다. 시세<->OMS, OMS<->FEP게이트웨어는 IPC로 연결합니다. ZeroAOS의 성능측정을 위하여 여러번 시험을 해보았습니다. 시험을 할 때마다 이상한 증상이 보였습니다. Jitter로 해석할 수 없는 비정상적인 값들이 보이더군요. 무얼까 열심히 고민을 해보았습니다. 수많은 데이타를 보면서 일정한 패턴을 찾을 수가 없었습니다. 무엇이 이런 비정상적인 값을 만들까 고민을 해죠. 비정상적인 값=Bottleneck이라고 생각하고 이리저리 조사를 했습니다.

아래는 이런 조사를 진행하면서 추론한 결과에 대한 글입니다. False Sharing이 주제입니다. 시작은 아래 글이었습니다.

False Sharing

멀티 코어 CPU에서 발생할 수 있는 문제다. 멀티 코어 CPU에서는 데이터를 word 단위로 읽어오는 대신 메모리 I/O 효율성을 위해서 cache-line로 읽어오는데, 이대 문제가 생길 수 있다. 두개의 메모리 연산이 동일한 캐쉬라인에서 실행될 경우, CPU<->Memory 버스 사이에서 하드웨어적인 락이 걸리는데, 이때 하드웨어적인 병목현상이 발생한다.

병렬 프로그래밍중에서

False Sharing이라는 단어를 모르지 않았습니다. 앞서 Disruptor를 소개한 글에서 자주 등장하는 개념입니다. 그렇지만 CPU로 들어가면 머리가 아파서 잠시 멀리했던 말입니다. 어쩔 수 없이 다시금 좀더 들어가야 했습니다. False Sharing을 검색하면 가장 많이 볼 수 있는 그림이 아래입니다.

그림을 글로 설명하면 아래와 같을 듯 합니다.

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

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

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

대략 머리속에 그림이 그려집니다. 그러면 Intel이 설명하는 False Sharing을 인텔은 어떻게 설명할까요? 인텔자료를 참조하여 한글로 옮긴 자료입니다.

Core 1은 이 값을 읽을 때, 최신 값이 아닌 예전 값을 읽게 되는 문제가 발생한다. 이 경우가 배로 cache coherency, 캐쉬 일치성에 문제가 생긴 것이다. 이런 것을 막고자 자기가 쓰고 있는 캐쉬가 다른 코어도 들고 있다면 그 값을 바꾸라는 메세지를 보내야 한다. 이런 일련의 과정을 Cache Coherence Protocol이라는 규칙으로 해결하고 있다. 대표적으로 MESI가 있다. MESI는 각 캐쉬 라인이 가질 수 있는 4가지 상태 (Invalid, Shared, Exclusive, Modified)의 첫머리를 따서 만든 것이다.

간략하게 이 경우에 해당하는 상황만 설명하면, 처음 이 두 코어가 이 데이터를 캐쉬에 가지고 있을 때는 모두 shared 상태로 되어있다. 두 코어로부터 공유되고 있다는 뜻이다. 여기서 Core 0이 데이터를 고치면 먼저 이 캐쉬를 자기 것으로 만들기 위해 다른 공유자들에게 모두 무효 시키라는 메세지를 보내야만 한다. 그러면 Core 1은 shared 상태였던 캐쉬를 invalid로 고친다. 그런 뒤, Core 0는 이제 이 캐쉬 사본에 수정을 가하고 modified 상태로 바뀐다. 여기서 만약 core 1이 데이터를 읽으려면 캐쉬가 invalid 상태이므로 L2 캐쉬 혹은 Core 0의 캐쉬로부터 가져와야 하기 때문에 더 많은 시간이 걸린다.

그렇다면 false sharing은 정확히 어떤 것을 말하는가? 위에서 설명한 모든 캐쉬 작동에 있어서 그 단위는 바이트 혹은 4바이트 단위로 작동하는 것이 아니다. 보다 큰 단위인 캐쉬 라인 이라고 불리는 대략 64바이트, 128바이트 단위로 모든 작업이 이루어진다. 이건 spatial locality (공간 지역성)을 이용하기 위해서이다. 한번에 캐쉬로 데이터를 가져오는데 4바이트만 가져오는 것 보다 그 보다 큰 양을 가지고 오는 것이 당연히 좋을 것이다. 당연히 위에서 설명한 캐쉬 코히런시도 모두 바이트 단위가 아닌 64바이트 정도의 캐시 라인 단위로 이루어 진다. 즉, 캐쉬의 각종 상태들이 모두 라인 단위로 관리된다.

문제는 위 그림과 같이 지금 캐쉬 라인이 공유가 되고는 있는데, 실제 Core 0이 쓰는 데이터는 이 라인 중 첫 번째 4바이트뿐이다. 또, Core 1은 쓰는 것은 마지막 4바이트뿐이다. 즉, 서로 둘은 실제로 공유하고 있는 데이터가 전혀 없다. 그러나 이 데이터가 같은 캐쉬 라인에 있다. 그래서 어느 한 코어가 각각의 데이터에 접근할 때 마다, CPU는 캐쉬 공유가 이루어지는 것으로 착각하고 만다. 그래서 서로 서로를 invalid 시키는 등의 신호를 보내는 삽질을 하게 된다. 위에서 설명하였듯이 invalid 시켜버리면 다른 쪽은 데이터 읽을 때 마다 cache miss를 겪게 된다. 따라서 false sharing의 결과는 대단한 성능 하락으로 이어질 수 있다.
False Sharing중에서

False Sharing은 멀티코어 환경에서 나타날 수 있는 Contention의 한 부분이라고 합니다. Memory Contention뿐 아니라 Heap Contention도 발생할 수 있다고 하네요.

Memory Issues On Multicore Platform

2.
이제 어떤 기술로 해결할 수 있을까요? 인텔이 제안한 멀티코어 프로그램을 개발하는 기술입니다. 여러가지 내용중 False Sharing에 대해 언급한 부분이 있습니다.

Software Techniques for Shared-Cache Multi-Core Systems

문제는 영어죠. 그래서 한글로 정리해놓은 글을 같이 소개합니다.

Multiple Processor System(Multicore System)의 Cache 효율 높이기

다음과 같이 소개하고 있습니다.

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

조금 막막하나요? 개발자인 분들을 위한 실사례를 소개합니다. 프로그래머가 몰랐던 멀티코어 CPU 이야기의 저자가 운영하는 블로그에 False Sharing과 관련한 문제가 있습니다.

퀴즈: 다음 코드의 문제점은?
정답: 다음 코드의 문제점은 false sharing

퀴즈를 보시고 직접 컴파일해서 실행을 하신다음 수정을 해보시길 바랍니다. 그리고 정답을 보시면 False Sharing이 가져오는 성능저하를 짐작하실 수 있고 회피하는 방법도 짐작하실 수 있습니다. 여기까지 해보셨으면 이제 유명한 Dr.Dobb’s Jornal에 실린 논문을 보시면 아주 잘 이해하실 듯 합니다.(^^) Disruptor는 Cash line Padding으로 False Sharing을 해결하였습니다.

Eliminate False Sharing

그러면 False Sharing이 나타나지 않도록 구현할 경우 얻을 수 있는 이익이 어느 정도일까요? 앞서 Multiple Processor System(Multicore System)의 Cache 효율 높이기에 들어 있는 내용을 소개합니다. 판단은 각자의 몫입니다.

Global Variable에 직접 접근

Affinity 미사용
Average Time = 2841.40
Average Time = 2842.20

Affinity 1, 1 사용 – 하나의 Core에서만 동작시킴
Average Time = 2653.15
Average Time = 2651.55

Affinity 1, 2 사용 – 각각 Core에 할당해서 동작시킴
Average Time = 2842.95
Average Time = 2843.75

Cache Line 정렬을 통한 Avoid False Sharing

Affinity 미사용
Average Time = 1514.10
Average Time = 1514.80

Affinity 1, 1 사용 – 하나의 Core에서만 동작시킴
Average Time = 3043.75
Average Time = 3042.20

Affinity 1, 2 사용 – 각각 Core에 할당해서 동작시킴
Average Time = 1520.30
Average Time = 1519.55

3.
이런 주제의 글쓰기는 무척이나 어색합니다. 개발자가 아닌 관계로 개발자에게 도움을 줄 수 있는 글쓰기를 할 수 없기때문입니다. 그렇지만 함께 일하는 파트너들에게 문제의식을 전하고 – 저의 글쓰기중 상당부분이 파트너를 위한 글입니다 – 나아가 혹 자본시장IT에 관계하시는 분들중 관심이 있는 분이 있으면 작은 도움이 되었으면 하는 바람으로 썼습니다. X.86기반의 리눅스서버를 사용하는 범위가 넓어지면 질 수록 멀티코어환경에 대한 이해가 깊어졌으면 합니다. 앞서 잠깐 소개한 책같은 것을 사보는 것도 방법이 아닐까 합니다. 이전에 소개하였던 Disruptor 역시 멀티코어환경에 최적화한 프레임워크를 개발하여 고성능을 실현하였습니다.

예전에 Free Lunch is over라는 글을 소개한 적이 있습니다. 하드웨어와 무관한 소프트웨어 개발로는 높은 성능을 낼 수 없는 세상인듯 합니다.

concurrency와 parallelism

참고로 멀티코어 멀티쓰레드 어플리케이션에서 malloc을 사용하실 경우 아래를 검토해보시길 바랍니다. Informatica가 IPC Messaging제품을 이용한 어플리케이션을 개발할 때 malloc()을 대체하기 위해 추천한 라이브러리입니다.

Replace host OS default memory allocator with a high-performance memory allocator

WHY: Since 29West Ultra Messaging makes extensive use of malloc(), free(), etc., memory allocation efficiency is vital for lowest latency and reduction of jitter. A high-performance memory allocator can optimize an application in two primary ways: speed and lower memory consumption (due to less fragmentation).

HOW: Investigate 3rd party allocators like SmartHeap or Hoard. 29West Ultra Messaging already uses SmartHeap for some executables like the UME store. Applications written to our API do not by default use SmartHeap, but the install includes all the files you need to enable it

Hoard라는 라이브러리의 소개글중 일부입니다.

Contention
Multithreaded programs often do not scale because the heap is a bottleneck. When multiple threads simultaneously allocate or deallocate memory from the allocator, the allocator will serialize them. Programs making intensive use of the allocator actually slow down as the number of processors increases. Your program may be allocation-intensive without you realizing it, for instance, if your program makes many calls to the C++ Standard Template Library (STL)

False Sharing
The allocator can cause other problems for multithreaded code. It can lead to false sharing in your application: threads on different CPUs can end up with memory in the same cache line, or chunk of memory. Accessing these falsely-shared cache lines is hundreds of times slower than accessing unshared cache lines.

Blowup
Multithreaded programs can also lead the allocator to blowup memory consumption. This effect can multiply the amount of memory needed to run your application by the number of CPUs on your machine: four CPUs could mean that you need four times as much memory. Hoard is a fast allocator that solves all of these problems.

다음으로 cpu종류마다 Cache line 크기가 다릅니다. Cross-platform function to get your cache line size으로 보면 Cache Line크기를 구하는 소스가 있습니다. 참고를 하시길 바랍니다.
[c]
#ifndef GET_CACHE_LINE_SIZE_H_INCLUDED
#define GET_CACHE_LINE_SIZE_H_INCLUDED

// Author: Nick Strupat
// Date: October 29, 2010
// Returns the cache line size (in bytes) of the processor, or 0 on failure

#include <stddef.h>
size_t cache_line_size();

#if defined(__APPLE__)

#include <sys/sysctl.h>
size_t cache_line_size() {
size_t line_size = 0;
size_t sizeof_line_size = sizeof(line_size);
sysctlbyname(“hw.cachelinesize”, &line_size, &sizeof_line_size, 0, 0);
return line_size;
}

#elif defined(_WIN32)

#include <stdlib.h>
#include <windows.h>
size_t cache_line_size() {
size_t line_size = 0;
DWORD buffer_size = 0;
DWORD i = 0;
SYSTEM_LOGICAL_PROCESSOR_INFORMATION * buffer = 0;

GetLogicalProcessorInformation(0, &buffer_size);
buffer = (SYSTEM_LOGICAL_PROCESSOR_INFORMATION *)malloc(buffer_size);
GetLogicalProcessorInformation(&buffer[0], &buffer_size);

for (i = 0; i != buffer_size / sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION); ++i) {
if (buffer[i].Relationship == RelationCache && buffer[i].Cache.Level == 1) {
line_size = buffer[i].Cache.LineSize;
break;
}
}

free(buffer);
return line_size;
}

#elif defined(linux)

#include <stdio.h>
size_t cache_line_size() {
FILE * p = 0;
p = fopen(“/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size”, “r”);
unsigned int i = 0;
if (p) {
fscanf(p, “%d”, &i);
fclose(p);
}
return i;
}

#else
#error Unrecognized platform
#endif

#endif
[/c]