ELF64 Relocation 처리(1) - ELF64 구조

원문 : http://kkamagui.springnote.com/pages/1709220

들어가기 전에...

0.시작하면서...

 이 문서는 ELF64 파일을 Relocation하는 데 필요한 정보가 기술된 문서입니다. 이 문서는 2부분으로 나누어져있으며, 첫번째 문서는 ELF64 파일 포맷에 대한 내용을 다루고 있고, 두번째 문서는 예제 코드를 통해 Relocation을 실제로 수행하는 내용을 담고 있습니다.

1.데이터 타입(Data Type)

 ELF64의 경우 데이터 타입은 아래와 같습니다. ELF32와 다른 점은 8Byte 크기의 데이터 타입이 추가되었다는 것입니다.

 데이터 타입은 ELF의 각 파트를 설명할 때 값의 표현범위를 나타내기위해 사용할 것이므로, 한번쯤 훓어보면 됩니다. ^^;;;

2.ELF 기본 구조(ELF Basic Structure)

 ELF64 또는 ELF32는 크게 아래와 같이 두가지 구조를 가집니다( 이 글에서 다룰 구조는 Relocation File 형태의 구조입니다).

 Relocation File은 일반적으로 Relocation에 대한 정보를 포함하고 있으며, 각 Section 마다 해당 Section의 Relocation 정보를 담당하는 Section이 별도로 존재합니다. 따라서 특수한 Section만 골라서 쉽게 Relocation을 수행할 수 있습니다.

3.File Header

 File Header는 ELF 파일 포맷의 가장 앞쪽에 위치하는 정보로 ELF 파일 포맷에 대한 각종 정보를 포함하고 있습니다. File Header에 포함된 데이터는 아래와 같습니다.

1. typedef struct
   {
       unsigned char e_ident[16]; /* ELF identification */
       Elf64_Half e_type; /* Object file type */
       Elf64_Half e_machine; /* Machine type */
       Elf64_Word e_version; /* Object file version */
       Elf64_Addr e_entry; /* Entry point address */
       Elf64_Off e_phoff; /* Program header offset */
       Elf64_Off e_shoff; /* Section header offset */
       Elf64_Word e_flags; /* Processor-specific flags */
       Elf64_Half e_ehsize; /* ELF header size */
       Elf64_Half e_phentsize; /* Size of program header entry */
       Elf64_Half e_phnum; /* Number of program header entries */
       Elf64_Half e_shentsize; /* Size of section header entry */
       Elf64_Half e_shnum; /* Number of section header entries */
       Elf64_Half e_shstrndx; /* Section name string table index */
   } Elf64_Ehdr;

 여러 필드가 있지만, 몇가지 특징적인 부분과 Relocation에 관련된 부분만 살펴보겠습니다.

• e_ident[ 0 ~ 3 ] : 0x7F, 'E', 'L', 'F' 가 각각 들어가있음. ELF  파일 포맷임을 인식하기위함
• e_ident[ 4 ] : 1이면 ELF32, 2면 ELF64를 의미함
• e_ident[ 5 ] : 1이면 Little Endian, 2이면 Big Endian을 의미
• e_type : 1이면 Relocatable Object File, 2이면 Execute File을 의미
• e_shoff : Section Header Table이 존재하는 곳의 파일 Offset을 의미함
• e_ehsize : ELF Header의 크기
• e_shnum : Section Header Table에 포함된 Section의 개수
• e_shstrndx : Section Header에서 Section Name String Table의 Index

 우리는 코드가 존재하는 Section(.text)을 돌면서 Relocation을 수행해야하므로, 위에서 언급한 것 중에 파란색으로 마킹한 부분만 유심히 보면 됩니다.

4.Section Header Entries

1. typedef struct
   {
       Elf64_Word sh_name; /* Section name */
       Elf64_Word sh_type; /* Section type */
       Elf64_Xword sh_flags; /* Section attributes */
       Elf64_Addr sh_addr; /* Virtual address in memory */
       Elf64_Off sh_offset; /* Offset in file */
       Elf64_Xword sh_size; /* Size of section */
       Elf64_Word sh_link; /* Link to other section */
       Elf64_Word sh_info; /* Miscellaneous information */
       Elf64_Xword sh_addralign; /* Address alignment boundary */
       Elf64_Xword sh_entsize; /* Size of entries, if section has table */
   } Elf64_Shdr;

 역시나 많은 필드가 있지만, 특징적인 몇가지와 Relocation에 필요한 부분 위주로 살펴보겠습니다. ^^;;; (자세한 내용이 궁금하신분을은 ELF64  파일 포맷에 대한 Spec 문서를 참조하세요).

• sh_name : Section Name Table 내에서 Section Name이 존재하는 Offset
• sh_type : Section의 타입. 자세한 타입은 아래 테이블 참조
• sh_flag : Section의 속성. 자세한 속성값은 아래 테이블 참조
• sh_addr : Section이 메모리에 로드될 때, Base 주소를 의미함
• sh_offset : 파일 내에서 Section이 존재하는 Offset. 위의 sh_addr의 값과 같을 수도 있으며, 다를 수도 있음
• sh_size : Section의 실제 크기. Byte 수로 표현
• sh_link : 현재 Section과 연결된 Section의 정보. sh_type에 따라서 이 필드는 다양한 의미를 가짐. 자세한 의미는 아래 테이블 참조
• sh_info : 현재 Section에 대한 정보. 위의 sh_link와 마찬가지로 sh_type에 따라 다양한 의미를 가짐. 자세한 의미는 아래 테이블 참조
• sh_entsize : Section에 포함되는 데이터, 즉 여러 개의 엔트리가 동일한 크기를 가진다면 0이 아닌 값으로 설정. 그렇지 않다면 0으로 설정. Symbol table 같은 경우 동일한 크기의 엔트리가 반복되므로 이 값이 0x18을 가짐

4.1 Section Type, sh_type

 sh_type은 Section의 타입을 단적으로 보여주는 값입니다. Section의 목적에 따라 아래와 같이 다양한 값을 가질수 있습니다.

 일반적으로 코드 및 데이터, 그리고 초기화되지 않은 데이터 Section을 의미하는 .text, .data, .bss의 경우는 SHT_PROGBITS를 가집니다. 즉 Program이 정의한 데이터를 삽입하는 영역이라는 의미입니다.

 하지만 Section의 Relocation 정보를 담고있는 Section의 경우는 SHT_RELA를 가지며, Symbol 정보를 포함하는 Symbol Table Section의 경우는 SHT_SYMBTAB의 값을 가집니다.

 이 타입에 따라서 sh_link 및 sh_info의 의미가 달라지는데, SHT_PROGBITS가 설정된 Section의 경우는 특별한 의미를 지니지 않습니다. 하지만 SHT_SYMTAB이나 SHT_RELA의 경우는 다릅니다. 다름 챕터를 같이 한번 볼까요?

4.2 sh_link 및 sh_info의 의미

 sh_link 및 sh_info는 sh_type 값에 따라 아래와 같은 의미를 가집니다.

 그렇다면 우리가 Relocation을 수행할 때는 어떤 정보를 봐야 할까요?

 일단 SHT_RELA 타입을 가지는 Section을 검색해서 찾은 후, 해당 Section의 sh_link 필드를 이용해서 Symbol Table Section을 찾습니다. 그리고 SHT_RELA 타입을 가지는 Section의 sh_info 필드를 이용하면 Relocation을 적용해야하는 Section을 찾습니다. 그리고 SHT_RELA 타입을 가지는 Section의 Relocation 정보를 가지고 Relocation을 수행하면 됩니다.

 그런데 Relocation 정보를 가지는 Section의 Relocation 정보와 sh_info가 가리키는 Relocation을 적용해야할 Section 정보만 알면 되지, 왜 Symbol 정보를 봐야할까요? 눈치가 빠른 분들은 이미 감을 잡으셨을 겁니다. ^^ 그것은 바로 Relocation Section에 포함되는 Relocation 엔트리 정보는 Symbol Table에 있는 Symbol 엔트리를 참고해서 실질적으로 얼마를 더하고 뺄지가 정해지기 때문입니다. 자세한 내용은 뒤쪽 챕터에서 설명하도록 하고, 지금은 SHT_RELA 타입을 가지는 Section을 찾고 그 Section의 sh_link 및 sh_info 정보를 이용한다는 것만 알고 넘어가겠습니다. ^^

4.3 Section Attribute, sh_flags

 속성 값은 아래와 같이 쓰기가 가능한지, 메모리를 할당받아서 실제로 로딩해야하는 Section인지, 코드가 포함되어있어서 실행가능한지에 대한 내용을 포함합니다. 우리가 Relocation 해야하는 Section(.text) 같은 경우,  .text Section은 메모리에 로딩되어 실행되야하는 Section이기 때문에 SHF_ALLOC 및 SHF_EXECINSTR 값을 설정합니다.  sh_flag는 Relocation 수행 시에는 크게 중요한 필드가 아니므로, 이런 것이 있다는 것만 알고 넘어가겠습니다. ^^;;;

4.4 Special Section

 Section의 속성은 위에서 언급한 각가지 필드를 이용해서 설정할 수 있지만, 관습적으로 사용하는 Section 이름들이 있습니다. 예를 들면 실행파일 코드가 있는 Section은 .text, 데이터가 존재하는 Section은 .data, 초기화 되지 않은 데이터는 .bss와 같이 말이지요. ^^

 아래는 Elf 파일 포멧에서 정의해놓은 Special Section들의 이름과 Type, 그리고 Attribute를 나타낸 테이블입니다.

 주의해서 볼 점은 .relname과 .relaname 라는 이름을 가진 Section이 있다는 겁니다. Section 이름에서 알 수 있듯이 name이 의미하는 Section의 Relocation 정보를 포함하고 있습니다. Section Type 뿐만 아니라 이름에서까지 Relocation Section 임을 알 수 있게 해놓다니... 여차하면 Section Name으로도 Relocation Section을 찾을 수 있을 것 같습니다(물론 권장하지는 않아요~!!! ^^;;;).

5.Symbol Table

 Symbol Table은 코드에서 사용된 각종 변수명 및 함수명, 그리고 Section 이름까지 많은 정보를 포함할 수 있습니다. Symbol Table은 아래와 같은 구조체의 배열로 구성되어 있습니다.

 역시나 각 필드의 의미를 살펴봐야겠지요? ^^ Symbol Table은 특별히 모든 필드를 살펴보겠습니다.

• st_name : String Table Section 내에서 Section 이름이 존재하는 Offset. String Table은 SHT_SYMTAB의 경우 sh_link 값이 가리키는 Section 임
• st_info : 상위 4bit는 Symbol Binding 정보를 나타내고 하위 4bit는 Symbol Type을 나타냄. Symbol Binding 및 Symbol Type에 대한 정보는 아래 참조
• sh_other : 추후 사용을 위해 예약된 영역. 반드시 0으로 설정
• st_shndx : Symbol이 정의된 Section의 Index. 함수이름 같은 경우 .text Section의 Index를 가리킬 것이고, 변수 이름 같은 경우는 .data Section의 Index를 가리킬 것임
• st_value : Relocatable 파일의 경우 Section 내에서 Symbol이 정의된 Offset을 의미. Executable 및 Shared Object 파일일 경우 Symbol이 정의된 Virtual Address를 의미
• st_size : Symbol의 크기를 의미. 함수의 경우 함수의 크기를 나타내며, 변수의 경우 변수가 차지하는 메모리 공간의 크기를 나타냄

 Symbol Table의 경우 각 필드의 의미를 정확하게 알고 있어야 Relocation을 수행할 수 있기 때문에, 모든 필드를 다 살펴봤습니다. 이제 Symbol Table 중에 남은 것은 st_info의 상위 4bit 및 하위 4bit에 대한 내용입니다만, 그리 중요한 부분은 아니니 슬쩍 보고 넘어가겠습니다. ^^;;; Relocation을 수행하는데 Symbol Binding(상위 4bit)과 Symbol Type(하위 4bit)은 그리 중요하지 않기 때문이지요. 일단 Symbol이 있으면 코드 내에 참조하는 곳이 있을테니 Relocation 준비를 (거의 무조건) 해야합니다. 다만 st_shndx의 값이 SHN_ABS 및 SHN_COMMON 일 때는 좀 생각을 해야합니다.

 SHN_ABS의 의미는 Value의 값이 Relocation의 영향을 받지않는 절대값이라는 의미이므로 이 Symbol은 Relocation을 하면 안됩니다. SHN_COMMON의 의미는 아직 메모리 공간이 할당되지 않은 Section이라는 의미이므로, 아래에서 언급할 일반적인 방식으로는 Relocation을 수행할 수 없습니다. 만약 하려면 SHN_COMMON으로 설정된 Symbol을 다른 Section에 공간을 할당해주고 Relocation 해야하는데, 이 작업 자체가 쉽지 않고 임의로 할당했다가는 다른 Section의 데이터를 엉망으로 만들 위험이 있습니다.

 따라서 수동으로 Relocation하려면 SHN_COMMON을 Section Index로 갖는 Symbol을 줄일 필요가 있는데, 이것은 배열이나 구조체를 "0"으로 초기화 함으로써 해결할 수 있습니다. ^^;;;; 구조체나 배열을 0으로 초기화하면 .bss나 .data 쪽으로 들어가기 때문이지요. 초기화하지 않으면 대용량의 배열이나 구조체 같은 경우는 SHN_COMMON으로 들어갈 확률이 높습니다.

 Symbol Binding(st_info의 상위 4bit) 정보는 아래와 같은 값들이 있습니다(하지만 패스~!!).

 Global Symbol인지 Local Symbol인지를 나타내는 값이 정의되어있군요. STB_LOCAL이 Object 파일 내에서만 보인다는 것을 보니 static으로 사용한 변수명쯤 되는 것 같습니다.

 Symbol types(st_info의 하위 4bit) 정보는 아래와 같은 값들이 있습니다(역시 중요하지 않으므로 패스~!!).

 변수명 같은 경우는 STT_OBJECT로 표시되고, 함수명 같은 경우는 STT_FUNC로 표시됨을 추측할 수 있습니다. Section 이름도 Symbol Table에 표시되는데, 이런 경우는 STT_SECTION 타입으로 표시되더군요. ^^;;;

6.Relocations

 드디어 Relocation 과정에서 핵심이 되는 Section인 Relocation Section까지 넘어왔습니다. Relocation Section은 Relocation에 대한 정보를 가지고 있는  Elf64_Rel 및 Elf64_Rela 구조체의 배열로 이루어져 있으며, 각각은 아래 그림과 같이 구성되어 있습니다.

 Relocation Entry는 아주 중요하므로 전 필드를 다 살펴보겠습니다.

• r_offset : Relocation 파일인 경우, 이 값은 Relocation을 수행해야하는 대상 Section 내에서 Relocation이 적용되어야하는 시작 위치를 나타냄. Executable 파일 또는 Shared Object 파일인 경우, Virtual Address를 의미함
• r_info : 상위 32bit는 Symbol Table 내의 Symbol Offset을 나타냄. 하위 32bit는 Relocation Type을 나타냄. Relocation Type에 대한 정보는 아래 참조
• r_addend : Relocation이 적용될때 더해줘야하는 값

 Relocation Entry의 필드중에 r_info를 보시면, Symbol Table의 Symbol 값을 이용하는 것을 볼 수 있습니다. 그럼 Symbol 값과 r_addend 값을 더해서 r_offset이 가리키는 영역에다가 덮어쓰면 될까요? 정답은 "아니요" 입니다. ^^;;;;

 Relocation도 단순히 Symbol 값을 대입하는 것부터, r_addend를 더하고 r_offset 값을 빼는 것같은 다양한 방식으로 계산을 수행합니다. 그럼 어떠한 연산을 수행해야 하는지 어떻게 알 수 있을까요? 그렇습니다. 바로 r_info의 하위 32bit 값인 Relocation Type을 보면 됩니다.

 Relocation Type은 아래와 같이 정의되어있습니다. ^^

 표의 가장 오른쪽에 있는 Calculation 항목에 있는 각 항목들은 아래와 같은 의미를 가지고 있습니다.

• S : Symbol Table에 정의된 Symbol의 값
• A : Relocation Entry의 r_addend 필드 값
• P : Relocation Entry의 r_offset 필드 값
• G : Global Offset Table 안에 Relocation Symbol이 위치한 Offset
• GOT : Global Offset Table의 Offset
• B : 프로그램 실행 시에 Shared Object가 메모리에 로드된 Base Address
• L : Procedure Linkage Talbe 안에 Relocation Symbol이 위치한 Offset

 위 항목 중에 G, GOT, B 그리고 L 항목은 공유 라이브러리(Shared Library)나 특수한 옵션(-fPic 등)을 사용하지 않으면 보기 힘든 항목이므로, 일반적으로 많이 사용되는 S, A, P를 위주로 보시면 됩니다. 위 테이블에 나와있는 계산 과정을 가만히 보면 지극히 간단한 규칙을 가지는 것을 알 수 있습니다. 대부분 계산 방법이 Symbol 값에 r_addend 값을 더하고 r_offset의 값을 빼서 Field 항목에 나와있는 크기만큼을 덮어쓰는 것으로 끝입니다. 다음 문서의 Relocation 수행 예제를 보시면 너무 간단해서 허무해 하실지도 모르겠군요. ^^;;;;

 다음 챕터로 넘어가기 전에 한마디 덧붙이자면, 정의를 보시면 비슷한 방식으로 계산하지만 Relocation이 수행되어야할 크기에 따라 다르게 분류되어 있습니다.. 이것은 x86 어셈블리어 코드가 다양한 크기의 메모리 및 레지스터를 가지고 연산할 수 있기 때문이며, 그로인해 Relocation을 수행해야하는 영역의 크기도 다양해졌기 때문입니다. 이부분은 값을 실제로 삽입할때 잘라서 넣어주면 처리할 수 있습니다.

7.마치면서...

 지금까지 Relocation을 수행하기위해 알아야할 ELF64 파일 포맷에 대한 몇가지 내용들을 봤습니다. Relocation을 수행하기 위해서 위 내용들을 달달 외울 필요는 없습니다. 그냥 "알고" 있으면 되는 것지요. 지금까지 표와 말로 많은 설명을 했습니다만, 아직 감이 잘 안오실 겁니다. ^^;;;; 프로그래머에게는 백마디 말보다 한줄의 코드가 더 좋은 법~!!!! 다음 문서(~!!!)에서는 예제 코드를 작성해서 Relocation을 실제로 해보겠습니다. >ㅁ<)-b

이 글은 스프링노트에서 작성되었습니다.

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

원문 : http://kkamagui.springnote.com/pages/1092170

참고 1 : http://softwarecommunity.intel.com/articles/eng/2760.htm

참고 2 : http://minjang.egloos.com/1848130

들어가기 전에...

• 이 글은 kkamagui에 의해 작성된 글입니다.
• 마음껏 인용하시거나 사용하셔도 됩니다. 단 출처(http://kkamagui.tistory.com, http://kkamagui.springnote.com)는 밝혀 주십시오.
• 기타 사항은 mint64os at gmail.com 이나 http://kkamagui.tistory.com으로 보내주시면 반영하겠습니다.
• 상세한 내용은 책 "64비트 멀티코어 OS 구조와 원리"를 참고하기 바랍니다.

• 

OS 개발에 관한 서적

하위 페이지에 있는 자료들은 OS를 개발하면서 관련된 자료들을 일부 정리해 놓은 것이다. OS 개발에 대한 보다 자세한 내용은 "64비트 멀티코어 OS 원리와 구조"를 참고하기 바란다.

   <64비트 멀티코어 OS 원리와 구조>

0.시작하면서...

 이 글은 Multiple Processor System에서 발생할 수 있는 Shared Cache의 문제를 어떻게 해결할 수 있는지를 설명하는 문서이다. 참고 자료의 내용 중에 테스트 가능한 부분만 요약하고 추가적인 내용을 덧붙였으니, 원문이 궁금하면 참고 1(http://softwarecommunity.intel.com/articles/eng/2760.htm) 문서를 보면 된다.

1.Processor, Core, Cache

 최근의 Processor는 Core를 2개 이상 탑재하는 방식으로 제작되고 있으며, 그에 따라 Cache의 중요성이 점점 높아지고 있다. CPU 업계를 이끌어 나가는 INTEL과 AMD는 Cache 구성에 대해 서로 다른 정책을 펴고 있으나, 공통적으로 Cache의 크기를 점차 넓혀가는 추세이다.

 Processor에 포함된 Core가 많고 Cache의 크기가 커지면 커질수록 성능이 배로 좋아질 것 같지만, 실제로는 각 Cache Level(L1, L2, L3)간의 동기화 문제가 발생하기때문에 정비례하지 않는다. 다시말하면 Core 0와 Core 1이 동일한 Data에 접근하거나 같은 Cache Line에 있는 데이터에 접근해서 Read/Write를 하게 될 경우, 각 Cache Level의 Data를 Syncronization(동기화)해야하기 때문에 성능이 저하되는 것이다. 이에대한 자세한 내용은 다음 장에서 살펴보자.

 아래는 2개의 Core를 가지는 Processor 2개를 연결한 그림이다. Processor 0에 L2 Cache가 Core 0와 Core 1에 공통으로 사용되고 있으며, L1 Cache는 각 Core에 할당되어 공유되지 않음을 볼 수 있다. L1 Cache 공유되지 않기 때문에 위에서 언급했던 L1 Cache와 L2 Cache간에 Syncronization 문제가 발생하게 된다.

<2 Dual Core Processor>

 그럼 지금부터 Cache를 효율적으로 사용할 수 있는 몇가지 방법에 대해 알아보자.

2.Cache Optimization Tip

2.1 Processor Affinity

  Multithread 프로그램의 경우, 개별 Thread는 개별 Core에 할당되서 동시에 실행될 수 있다. Core에 할당되는 Thread는 Scheduling Algorithm에 따라 달라지며, 하나의 Core에서 실행되거나 여러 Core를 돌며 실행될 수 있다. Thread A가 Core A와 Core B에서 교대로 실행되는 경우, Thread A가 사용하는 Data를 매번 L2 Cache에서 L1 Cache로 옮겨오는 최악의 상황이 발생할 수 있으며 그로 인해 성능이 저하될 수 있다.

 이러한 경우 Thread를 특정 Core에 할당해서 실행함으로써 Overhead를 줄일 수 있다. 또한 각 Thread가 Data를 공유하지 않는다면, 개별 Thread를 특정 Core에서만 수행되도록 할당함으로써 성능을 높이는 것이 가능하다.

 Windows 환경과 Linux 환경에서는 아래의 2가지 API를 사용해서 Thread와 Process의 Processor Affinity를 설정할 수 있다.

1. // Windows API
2. BOOL SetProcessAffinityMask(
     HANDLE hProcess,
     DWORD_PTR dwProcessAffinityMask
   );
   DWORD_PTR SetThreadAffinityMask(
     HANDLE hThread,
     DWORD_PTR dwThreadAffinityMask
   );
3. // Linux API
4. /* Get the CPU affinity for a task */
   extern int sched_getaffinity(
     pid_t pid,
5.   size_t cpusetsize,
6.   cpu_set_t *cpuset
7. );
8. /* Set the CPU affinity for a task */
   extern int sched_setaffinity(
     pid_t pid,
9.   size_t cpusetsize, 
     const cpu_set_t *cpuset
10. );

 하지만 Affinity가 좋은 점만 있는 것은 아니다. 할당된 Core에 Load가 몰리는 경우, Scheduling 순서를 기다리느라(Waiting Queue에 대기) 오히려 더 지연 될 수 있으니 주의해야 한다.

2.2 Cache Blocking(Data Tiling)

 Cache Blocking 또는 Data Tiling 기법은 Loop를 수행할 때, Loop에서 사용되는 Data가 Cache Line에 존재하도록하는 기법이다. 만약 Data Block이 크다면, Cache에 Load된 Data가 Loop시에 한번만 사용되고 버려지고 현상이 반복될 수 있다. 이러한 최악의 상황은 Cache의 Hit Ratio를 떨어뜨리며 성능을 저하시키는 요인이 된다. 이러한 현상을 해결하는 좋은 방법은 Data를 Tile 처럼 잘게 쪼개서 작은 Loop로 처리하는 것이다.

 아래의 그림과 같이 (A)와 같이 큰 Data를 사용하는 Loop를 (B)처럼 작은 Data를 사용하는 Loop로 나눔으로써, Data Block을 Cache에 올려 성능을 높일 수 있다.

<Cache Blocking(Data Tiling)>

2.3 Hold Approach

 Hold Approach는 빈번하게 Read/Write하는 것을 Local Copy를 사용하여 줄임으로써 Cache 효율을 높이는 방법이다. Thread Local Storage나 Local Variable을 사용하여 작업한 후, 결과를 Reporting하는 것이 이에 해당한다. 아래의 그림은 Hold Approach를 그림으로 표현한 것이다.

<Holding Approach>

 좌측의 (A)와 같이 빈번하게 Read/Write하던 것을 Local Copy를 통해 (B)와 같이 줄여서 효율을 높일 수 있다.

2.4 Avoid False Sharing

 False Sharing이란 Multiple Processor System의 유명한 문제이다. 각 Core에서 수행중인 Thread간의 공유하는 Data가 없지만, 동일한 Cache Line에 있는 Data를 접근함으로써 매번 Evict와 Load가 반복되는 현상이다. 실제로는 Cache Coherency Problem(협업 문제)가 전혀 발생하지 않지만, Cache의 정보가 변경되었으므로 어쩔 수 없이 L1 Cache의 내용을 L2 Cache에 옮기고 다시 다른 Core의 L1 Cache로 옮겨야 한다. 아래의 그림은 Flase Sharing을 그림으로 표현한 것이다.

<False Sharing>

 Core 0의 Thread 0와 Core 1의 Thread 1은 서로 공유하는 Data가 없지만 동일한 Cache Line에 위치함으로 Evict와 Load가 반복되게 된다.

 이러한 False Sharing을 피하는 방법은 아래와 같다.

• 공유되지 않는 Data는 다른 Cache Line에 둔다. 즉 Padding Data를 두거나 다른 Memory Address에 할당한다. 단, 너무 많은 Cache Line을 할당하지 않도록 Data를 잘 묶어서 적당히 배열한다.
• Hold Approach와 마찬가지로 Data를 Local 영역에 저장하고 필요할때만 Read/Write하여 Evit/Load 회수를 줄인다.
• Thread의 Affinity를 설정하여 Thread 0와 Thread 1이 동일한 Core에서 수행되도록 한다.

3.Test

 아래는 Cache Optimazation Test에 사용한 간단한 코드이다. 윈도우즈 환경에서 VC++ 6.0으로 테스트했으며 Release 모드에서 Optimization 옵션은 Debug 모드와 같이 사용하지 않는 것으로 설정하고, 8Byte Aling, MultiThread DLL을 사용하도록 설정했다.

 테스트에 사용된 PC는 INTEL Core 2 Duo 2.6GHz에 4G의 RAM으로 구성되어있다.

3.1 Affinity & Cache Blocking Test

 아래는 Affinity와 Cache Blocking을 테스트하는 간단한 코드이다.

1. #include <windows.H>
   #include <stdio.H>
   #include <tchar.H>
2. #define UNIT      32
   #define MULTIPLE  200000
   #define MAX_DATA  UNIT * MULTIPLE
   #define MAX_LOOP  200
3. // 계산할 데이터가 들어있는 배열
   volatile int g_iData[ MAX_DATA ] = { 1, 2, };
4. // 실제 메인 함수
   int main(int argc, char* argv[])
   {
       DWORD dwSum;
       int i;
       int j;
       int k;
       int l;
       DWORD dwStartTime;
       DWORD dwEndTime;
       DWORD dwTimeSum;
5.     // Processor High Priority로 만든다.
       SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
6.     // Affinity 설정
       SetProcessAffinityMask( GetCurrentProcess(), 0x1 );
7.     // 카운팅 시작
       dwSum = 0;
       dwTimeSum = 0;
       printf( "Start Processing...\n" );
       for( l = 0 ; l < 20 ; l++ )
       {
           dwStartTime = GetTickCount();
          
           // Normal Loop
           for( j = 0 ; j < MAX_LOOP ; j++ )
           {
               for( i = 0 ; i < MAX_DATA ; i++ )
               {
                   dwSum += g_iData[ i ];
               }
           }
8.         /*
           // Cache Blocking
           for( k = 0 ; k < MULTIPLE ; k++ )
           {
               for( j = 0 ; j < MAX_LOOP ; j++ )
               {
                   for( i = k * UNIT ; i < ( k + 1 ) * UNIT ; i++ )
                   {
                       dwSum += g_iData[ i ];
                   }
               }
           }
           */
          
           //결과 출력
           dwEndTime = GetTickCount() - dwStartTime;
           dwTimeSum += dwEndTime;
           printf( "%d Time = %d ms\n", l + 1, dwEndTime );
       }
9.     printf( "Average Time = %0.2f\n", dwTimeSum / 20.0 );
       return 0;
   }

아래는 위의 코드를 이용해서 테스트한 결과이다.

• Normal Loop

  • Affinity 미사용

    • Average Time = 4225.00

    • Average Time = 4201.55

  • Affinity 1 사용 - 하나의 Core에서만 동작시킴

    • Average Time = 4275.00

    • Average Time = 4256.25

• Cache Blocking

• • Affinity 미사용

    • Average Time = 3836.70
    • Average Time = 3818.70

  • Affinity 1 사용 - 하나의 Core에서만 동작시킴

  • • Average Time = 3875.80

    • Average Time = 3860.90

 테스트 결과 Data Block 크기가 클수록, 즉 Cache Evit가 발생할 확률이 높으면 높을수록 Cache Blocking의 효과가 커졌다. Processor Affinity 부분은 오히려 Affinity를 적용한 결과가 근소하게 더 느리게 나왔다. 이것은 Thread가 Core를 옮겨다니며 Cache를 Reflesh하는 시간 보다 할당 받은 Core의 Wait Queue에서 대기하는 시간이 더 길기 때문에 발생한 듯하다. 이 결과는 어디까지나 테스트 프로그램의 결과이고, 만약 더 큰 Data에 접근하고 보다 복잡한 코드로 이루어져 있다면 충분히 달라질 수 있는 부분이다.

3.2 Affinity & Avoid False Sharing Test

 아래는 Affinity와 False Sharing을 테스트하는 간단한 코드이다.

1. #include <windows.H>
   #include <stdio.H>
   #include <tchar.H>
2. // 각 스레드에서 사용하는 전역 변수
   volatile int g_iData1 = 0;
   volatile int g_iData2 = 0;
3. // Cache line을 맞추기위해 정의한 구조체
   // 강제로 공간을 할당한다.
   typedef struct dataStruct
   {
       volatile int iData1;
       int viData[32];
       volatile int iData2;
   } DATA;
4. // Cache line 정렬용 구조체
   DATA g_stData = { 0, {0,}, 0 };
5. // 테스트 Thread 1
   DWORD CALLBACK TestThread1( void* pData )
   {
       /*
       // 지역변수 사용
       int i;
       int iTemp;
6.     iTemp = g_iData1;
7.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
       {
           iTemp = iTemp + 1;
       }
       g_iData1 = iTemp;
       return g_iData1;
       */
8.     /*
       // 바로 접근
       int i;
9.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
       {
           g_iData1 = g_iData1 + 1;
       }
       return g_iData1;
       */
       // False Sharing
       int i;
10.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            g_stData.iData1 = g_stData.iData1 + 1;
        }
        return g_stData.iData1;
    }
     
    // 테스트 Thread 1
    DWORD CALLBACK TestThread2( void* pData )
    {
        /*
        // 지역변수 사용
        int i;
        int iTemp;
11.     iTemp = g_iData2;
12.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            iTemp = iTemp + 1;
        }
        g_iData2 = iTemp;
        return g_iData2;
        */
13.     /*
        // False Sharing
        int i;
14.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            g_iData2 = g_iData2 + 1;
        }
        return g_iData2;
        */
15.     // False Sharing
        int i;
16.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            g_stData.iData2 = g_stData.iData2 + 1;
        }
        return g_stData.iData2;
    }
     
    // 실제 메인 함수
    int main(int argc, char* argv[])
    {
        HANDLE vhThread[2];
        int i;
        DWORD dwStartTime;
        DWORD dwEndTime;
        DWORD dwTimeSum;
17.     // Processor High Priority로 만든다.
        SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
18.     dwTimeSum = 0;
        printf( "Start Processing...\n" );
        for( i = 0 ; i < 20 ; i++ )
        {
            // Thread 생성
            vhThread[0] = CreateThread( NULL, 0, TestThread1, ( LPVOID ) 0, CREATE_SUSPENDED, NULL );
            vhThread[1] = CreateThread( NULL, 0, TestThread2, ( LPVOID ) 0, CREATE_SUSPENDED, NULL );
19.         // Affinity 설정
            SetThreadAffinityMask( vhThread[ 0 ], 0x1 );
            SetThreadAffinityMask( vhThread[ 1 ], 0x1 );
20.         // 카운팅 시작
            dwStartTime = GetTickCount();
            ResumeThread( vhThread[ 0 ] );
            ResumeThread( vhThread[ 1 ] );
21.         // Thread 종료
            WaitForMultipleObjects( 2, vhThread, TRUE, INFINITE );
22.         //결과 출력
            dwEndTime = GetTickCount() - dwStartTime;
            printf( "%d Time = %d ms\n", i + 1, dwEndTime );
            dwTimeSum += dwEndTime;
        }
23.     printf( "Average Time = %0.2f\n", dwTimeSum / 20.0 );
        return 0;
    }

 아래는 위의 코드를 이용해서 각 옵션으로 테스트한 결과이다.

• 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

• Local Variable을 사용한 Hold Approach

• • Affinity 미사용

    • Average Time = 1330.50
    • Average Time = 1332.00

  • Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴

    • Average Time = 2671.85
    • Average Time = 2672.65

  • Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴

  • • Average Time = 1335.95
    • Average Time = 1335.95

 위의 굵은 숫자는 가장 해당 파트에서 가장 빠른 수행 결과를 나타낸 것이다. 결과는 당연히 Local Variable(Hold Approach)을 사용하는 것이 가장 빠르게 나왔다. 첫번째 Global Variable에 직접 접근하는 결과에서는 두 Thread 모두 Core 0에 할당해서 수행한 결과가 제일 빨랐다. 이는 Thread 수행 시에 발생하는 Cache Evit/Load가 상당하기 때문에 발생한 결과인 듯 하다. 다른 테스트의 경우는 하나의 Core에 할당한 결과가 가장 느렸다.

 이 테스트에서 눈 여겨볼 것은 Avoid False Sharing 테스트이다. Cache Line 정렬을 사용한 것과 하지 않은 것의 차이가 거의 1.8 배의 속도 차이가 난다. 다시 말하면 Data Structure를 손보는 것 만으로도 MultiCore 환경에서의 Performance를 1.8배 향상 시킬 수 있는 것이다. Performance가 중요시되는 프로그램이라면 Cache Line 정렬은 충분히 고려해 볼만 하다.

4.결론

 Processor Affinity는 윈도우즈 환경에서 기대만큼 큰 효과를 발휘하지 못했지만, Cache Blocking과 Hold Aproach 및 Avoid False Sharing 기법은 충분히 효과적인 것으로 나타났다. Processor Affinity가 윈도우즈 환경에서 큰 효과를 발휘하지 못하는 것은 윈도우즈의 Scheduler가 Affinity를 어느정도 보장해주며, Wait Queue에서 대기하는 시간이 Cache Evit & Laod 시간보다 더 길기 때문인 것으로 추측된다.

 테스트 결과 Cache Blocking과 Avoid False Sharing은 성능 향상에 충분한 효과가 있는 것으로 나타났다. Cache Blocking과 Avoid Flase Sharing은 Data Structure와 밀접한 관련이 있으며, 이는 Data Structure를 Cache-Friendly 하게 설계하는 것이 Multiple Processor의 성능을 향상시키는 좋은 포인트임을 말해주는 것이다. 따라서 Multiple Processor System에서 Cache-Friendly한 Data Structure를 사용하면 프로그램의 성능을 일정 수준 이상 높일 수 있다.

5.마치면서...

 이미 우리는 Multiple Processor의 시대에 살고 있다. 프로그래머에게 또 하나의 장을 열어준 Multiple Processor System, Multiple Processor-Friendly한 Architecture로 프로그램의 Performance를 높이자.

이 글은 스프링노트에서 작성되었습니다.