[Computer Architecture] (2) Memory Alignment

Memory Alignment는 일반적으로 Memory에 저장되어 있는 데이터를 접근 하는 방식을 고려하여 데이터를 저장하는 방법을 의미한다. 데이터를 저장하는 방법에 따라 Memory를 접근하는 횟수가 달라질 수 있다. 

 

 현재까지도 CPU와 Memory의 성능 차이는 좁혀지고 있지 않다. 과거 컴퓨터 아키텍처 연구가 활발히 수행되었던 시점에도 마찬가지였다. 그래서 많은 연구들이 어떻게 하면 이 차이를 좁혀서 전체 성능을 높일 수 있을 까에 대한 해결책을 찾기위해 진행되었다. Memory Alignment 기법도 Memory 접근을 효율적으로 하기 위한 방법 중에 하나이다.   Memory로부터 Address Map과 읽어오는 데이터 크기 관점으로 어떻게 데이터를 읽어오는 지 알아 보자.  Address Map을 구성할 때, 현재 주로 쓰이는 방법은 Byte-addressable 이다. Byte-addressable이란 각각의 byte 단위의 데이터들이 서로 다른 고유의 주소를 가지고 있다는 것을 의미한다. 아래와 같이 Address 하나당 8-bit의 데이터가 Mapping되어 있다. 

==================

Address | Data

0x000    |  0000_00000

x001     |  0011_11100

x002    |  0101_0001...

==================

예전에는 bit-addressable 방식도 사용하였다. bool type과 같이 크기가 1-bit인 데이터를 취급할 때 사용하기도 하였다. 그런데 현재는 거의 모든 data type이 byte의 배수형태로 설정되어 있으므로 Bit 단위로 읽어올 필요가 없다.  bit 단위를 표현하기 위한 하위 2-bit을 제거 할 수 있으며(Byte 단위일 때는 항상 0이므로), Address를 이용하여 데이터를 가져오는 동작도 조금 더 간단해 진다. 그래서 Byte-addressable을 사용한다. 

 

 그렇다면 주소는 알았으니, 얼마나 많은 데이터를 한번에 읽어오는 지를 살펴보자. CPU가 Register로 Load를 수행하는 데이터의 크기는 다양하였으나(8-bit, 16-bit 등), 현재는 32-bit, 64-bit을 주로 사용한다. 물론 vector 연산를 수행하기 위하여 큰 데이터를 저장하는 Register도 존재한다.  4B(32-bit) 크기의 Register를 가지는 CPU로 가정하면, Address 기준으로 4개 주소의 데이터를 읽어올 수 있다. 즉 지정된 address 기준으로 4B를 읽어 올 수 있다는 것이다. 그런데 이 시작 주소를 4B 단위로 맞춘 다면 위에서 bit->byte에서처럼 하위 2-bit을 제거하여 (4B 단위일 때는 항상 0이므로), Address를 줄일 수 있다. 아래와 같이 0x000를 읽으면 0x000~0x003까지 데이터를 가져올 수 있다. 

==================

Address | Data

0x000    |  0000_0000

0x001    |  0011_1110

0x002    |  0101_0001

0x003    |  0111_1111

0x004    |  0101_1011

0x005    |  0111_1110

...

==================

 

Memory로부터 데이터를 가져올 때의 주소와 크기에 대해서 알아보았다. 다음은 데이터 타입에 대해서 알아보자. 각 데이터는 타입에 따라 크기가 결정된다. 아래와 같이 C Standard로 사용되는 data type의 크기를 나타내었다. 각 크기는 Byte단위이며, Machine의 type에 따라 크기가 달라지는 부분도 있다. 

C Data Type

 

long double를 제외하고는 아래와 같이 2^n(n>=0)으로 표현 가능하다. 

the Size of 'Char'   = 2^0

the Size of 'Short'  = 2^1

the Size of 'int'      = 2^2

the Size of 'long'   = 2^3

the Size of 'float'   = 2^2

 

이런 크기를 기반으로 어떻게 Address Map에 배치를 해야 가장 적은 Load를 수행하여 모든 데이터를 읽어올 수 있을 까?

위 메모리 예시 처럼, 4B 단위로 읽어 올 수 있고, 하위 2-bit은 사용하지 않는다고 생각해보자. 

데이터의 크기는 N(개수)*S(data type의 크기)이다. 이 때, 읽어오는 데이터 크기를 M(Read 횟수)*2^2(4B_이라고 하자. S = 2^T로 표현 가능하다.

그 크기를 비교하면 N*2^T <= M*2^2이 성립하는 데, 이 때 가장 작은 M 값이 메모리로부터 읽어와야 하는 횟수이다.

이상적인 상황은 N*2^T = M*2^2이다.

'int'인 경우 T = 2이므로 N = M으로 'int' 개수 만큼 읽어오면 된다. 

'Short'인 경우 T = 1 이므로 N <= 2*M이므로 1, 2개 일 때도 1번 읽고, 3,4개 일 때도 2번 읽어야 한다. 

'long' 인경우 T = 3이므로 N <= M/2 이므로 1개 일 때 2번, 2개 일 때 4번을 읽어야 한다.

이상적인 횟수를 계산하는 방법을 알아보았다. 그렇다면 어떻게 배치를 해야할 까?

제일 쉽게 생각할 수 있는 방법은 address 0부터 배치하는 것이다. 그렇다면 순차적으로 배치될 것이며, 어떤 바이트 단위로 읽더라도 나머지로 인한 접근은 1번만 발생할 것이다. 아래와 같이 Type에 따라 배치를 해보자.

Data type 별 저장 위치.

위의 그림과 같이 배치를 해보면 각 type 별로 시작하는 주소는 각 data type 크기의 배수임을 알 수 있다.

그러므로 '0'이 아닌 주소 값에서 시작하더라도 data type 크기의 n배가 되는 주소를 계산하여 배치를 하면 된다. 

 

C 언어에서의 Struct는 다양한 타입의 변수 집합을 하나의 타입으로 나타낸 것이다. 아래와 같은 예제를 보면 Struct type 안에 int / char / short 과 같이 다양한 data type이 모여 있다. 이 때, struct 내부의 변수들은 순차적으로 메모리에 할당된다. 

Struct {
 int a;
 char* c;
 char d[5];
 short f;
} myStruct

myStruct A;

 

구조체 A의 주소를 살펴봤더니 0x103이었다. 이런 경우 Struct 내 각 변수들이 어떻게 할당되는 지 살펴보자. 

여기서 Pointer는 어떤 type인지 관계 없이 32-bit machine이면 4B이고 64-bit machine이면 8B로 Alignment를 수행하면 된다. 

• Any pointer (four bytes) will be 4-byte aligned. (e.g.: char*, int*) [1]

각 type별 저장 가능한 위치

 

이 위치에 각 struct 내의 변수들을 기술되어있는 순서대로 각자가 들어갈 수 있는 영역에 넣어주면 아래와 같이 Mapping이 된다. 

변수 A의 Address Map

 

즉, 순차적으로 각 변수들의 Alignmemt 크기에 따라 저장될 수 있는 공간에 할당하는 형태로 진행된다.

 

요약하면 아래와 같다. 

1. Memory Alignment는 일반적으로 Memory에 저장되어 있는 데이터를 접근 하는 방식을 고려하여 데이터를 저장하는 방법을 의미한다. 데이터를 저장하는 방법에 따라 Memory를 접근하는 횟수가 달라질 수 있다.

2. 현재는 거의 모든 data type이 byte의 배수형태로 설정되어 있으므로 Byte-addressable을 사용한다. 

3.  4B(32-bit) 크기의 Register를 가지는 CPU로 가정하면, Address 기준으로 4개 주소의 데이터를 읽어올 수 있다. 

4. 각 type 별로 시작하는 주소는 각 data type 크기의 배수로 지정될 경우, 메모리 접근 시 가장 적은 횟수로 수행가능.

5.  struct 내부의 변수들은 순차적으로 메모리에 할당된다. 

6.  순차적으로 각 변수들의 Alignmemt 크기에 따라 저장될 수 있는 공간에 할당하는 형태로 진행된다.

 

 

[1] : https://en.wikipedia.org/wiki/Data_structure_alignment

Data structure alignment - Wikipedia