메모리 얼라인먼트(Memory Alignment)

메모리 얼라인먼트는 레퍼런스마다 데이터 구조 얼라인먼트(Data Structure Alignment), 데이터 얼라인먼트(Data Alignment) 등으로 불리기도 하며, 위키피디아에서는 다음과 같이 개요가 작성되어 있습니다:

Data structure alignment는 컴퓨터 메모리에서 데이터가 정렬되고 액세스되는 방식을 나타냅니다. 데이터 정렬, 데이터 구조 패딩(padding), 패킹(packing) 과 같은 세 가지 개별적인 관련 문제로 구성됩니다.

최신 컴퓨터 하드웨어의 CPU는 데이터가 자연스럽게 정렬 (naturally aligned) 될 때(일반적으로 데이터 주소가 데이터 사이즈의 배수일 때) 메모리에 대한 읽기 및 쓰기를 가장 효율적으로 수행할 수 있습니다. 데이터 얼라인먼트는 정렬되는 요소가 자연 정렬(natural alignment) 을 따르는 것을 의미합니다. 자연 정렬(natural alignment) 을 보장하기 위해 구조 요소(structure elemetns) 사이에 또는 구조의 마지막 요소(the last element of a structure) 뒤에 패딩(padding)을 삽입해야 합니다.

데이터 구조 정렬은 모든 최신 컴퓨터에서 근본적인 문제이지만 만은 컴퓨터 언어 및 컴퓨터 언어 구현(implementation)이 데이터 정렬을 자동으로 처리합니다. Ada, PL/I, Pascal, 특정 C 및 C++ 구현, D, Rust, C#, 그리고 어셈블리는 최소한 데이터 구조체 패딩(data streucture padding)의 부분적인 제어를 허용하며, 이것은 특정 상황에서 유용할 수 있습니다.

 

 

 

이유

---

그렇다면 메모리 얼라인먼트 문제가 일어나는 문제는 무엇일까요. 그것은 바로 현대의 프로세서의 메모리 하위 시스템이 메모리에 접근하는 것을 프로세서의 워드 크기에 대해서 분할하고(granularity)하고 정렬(alignment)하는 것으로 제한하기 때문입니다.

 

이것을 쉽게 풀어서 설명하자면, 프로세서의 워드 크기가 4바이트(32비트)일 때, 메모리로부터 한 번 읽어들일 때마다 4바이트만큼 읽어들이고 기준 주소 역시 워드의 배수여야 한다는 것입니다.

 

프로세서가 메모리 접근을 워드 단위로 제한하는 것에 대한 이유는 여러 가지가 있으며 다음과 같습니다:

• 속도
• 범위
• 원자성

 

 

 

범위(Range)

---

32비트 프로세서로 가정하였을 때, 주어진 주소 공간에 대해 아키텍처가 2개의 LSB(Least Significiant Bit)가 항상 0이라고 가정할 수 있다면 메모리는 4배 더 많은 메모리에 액세스하거나(이 때 비축된(Saved) 2비트들은 4개의 구별된 상태를 표현하는 데 사용될 수 있습니다), 같은 메모리 양을 가지면서 플래그와 같은 것들에 대해 2비트를 허용 할 수 있습니다.

 

2 LSB를 메모리 주소에서 빼내는 것은 4바이트 정렬(4-byte alignment)이라는 결과를 가져옵니다(4 바이트 간격(4 byte stride) 라고도 합니다). 주소가 증가할 때마다 주소가 4씩 증가하게 되며, 마지막 2비트는 항상 00비트를 유지하게 됩니다.

 

이것은 시스템의 물리적 설계에도 영향을 줄 수 있습니다. 주소 버스가 2비트를 더 적게 필요로 한다면, CPU에 2개의 핀이 더 적을 수 있고, 회로 보드에 2개의 트레이스가 더 적을 수도 있습니다.

 

예시

메모리 얼라인먼트로 얻을 수 있는 주소의 4배 참조에 대한 예제를 잘 설명한 사이트를 찾아서 인용합니다:

가상의 machine, ASDF가 있다고 가정해 봅시다. 이 machine은 32-bit addressing을 하고, word (32-bit) 단위로 load/store를 제공합니다. machine instruction은 ir이란 레지스터에 저장되고, load 명령은 메모리의 한 word를 읽어서 레지스터 r0 또는 r1에 그 내용을 넣어 줍니다. 또한 모든 명령은 32-bit로 표현합니다.

load 명령은 32-bit로 이루어져 있으며, 다음과 같은 형태를 지닙니다:

IR: 1RXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX

이 때, bit 0은 1(load를 나타냄)이며, bit 1이 0일 경우 r0을, 1일 경우 r1을 뜻합니다. 그리고 나머지 30개의 비트는 메모리의 주소를 나타냅니다.

메모리는 32-bit이므로, byte단위로 addressing할려면 32bit가 필요합니다. 하지만, 위 load 명령에서는 한 명령의 길이가 32 bit이고, bit 0은 opcode를 나타내고 bit 1은 target register를 나타내므로, 실제 주소를 표현할 수 있는 bit의 수는 30 bit입니다.

따라서 32-bit의 주소를 가진 메모리 (최대 4GB)를 모두 addressing 하기 위해서 이 30bit 주소에 4를 곱해서 나타냅니다. 결국, 실제 메모리 주소는 load 명령의 XXXX로 표기한 값에 4를 곱해야 나옵니다. 그렇다면 load 명령으로 접근할 수 있는 실제 메모리 주소는 항상 4의 배수가 된다는 결론이 나옵니다.

실제 IR의 상위 30bit (bit 2에서 bit 31까지)의 배선은 RAM의 address pin (bit 2에서 bit 31까지)에 일대일로 연결되어 있으며 RAM의 address pin, bit 0과 bit 1은 항상 0으로 연결되어 있습니다. 이런 설계를 가진 ASDF는 무조건 4의 배수로 된 주소에서 한 word (32-bit)만 레지스터로 읽어 올 수 있습니다. 그렇다면 다음과 같은 상황에 대해 처리하는 것도 생각해 봐야 합니다:

4 byte로 align되지 않는 주소에서 한 word를 읽는 경우.

아쉽게도 제가 상상한 ADSF 머신은 이런 기능이 없습니다. 하지만 대부분 현존하는 processor는 이런 경우도 해결책을 제공합니다. (processor에 따라 약간씩 다름) 이 경우, 대부분 RISC processor는 bus error(SIGBUS)를 발생시킵니다. 즉, 4 바이트 배수가 아닌 주소에서 word 단위로 읽어올 수 없습니다.

어떤 processor에서는 이 경우에도 제대로 읽어 올 수 있도록 설계됩니다. 이 경우, 여러가지 옵션이 있는데, 첫째, load instruction이 모든 address를 다 지정할 수 있도록 32-bit address를 포함하도록 합니다. (이 경우 load instruction의 길이는 더 이상 32-bit가 아닙니다. opcode 부분을 포함해야 되기 때문) 이 경우 instruction의 길이가 가변적이 되거나, 아니면 64-bit 고정이 되겠지요. 또 다른 방식으론, load 명령을 두 번 발생시켜서, 두 개의 word를 읽게 한 다음, 절반씩 꺼내어 합치는 것입니다. 이 경우 4의 배수로 된 주소에서 꺼내는 것보다 훨씬 느리게 되지만, SIGBUS를 걱정할 필요가 없습니다. 어떤 RISC 머신은 설정에 따라 bus error를 낼 수도 있고, 바로 앞에서 설명한 것처럼, 두번의 load를 통해 읽어오게 할 수도 있습니다.

제가 설명한 내용이 모든 processor에 그대로 적용되는 것은 아니지만, 왜 특정 processor가 word 단위로 값을 읽을 때, alignment rule에 따라야 하는지, 설명은 될 것이라고 생각합니다.

 

 

 

속도(Speed)

---

현대의 프로세서는 데이터를 가져와야 하는 여러 단계 레벨의 캐시 메모리(L1, L2, ...)를 가지고 있습니다. 단일 바이트(single-byte) 읽기를 지원하면 메모리 서브시스템의 처리량(throughput)이 실행 유닛 처리량(execution unit throughput)에 타이트하게 바운딩될 수 있습니다(이것을 흔히 cpu-bound라고 합니다). 이것은 하드 드라이브에서 같은 이유로 DMA가 PIO(Programmed IO)를 능가하는지에 대해 상기시켜 줍니다.

 

CPU는 항상 워드 크기만큼 읽어들이므로(32비트 프로세서에서 4byte), 정렬되지 않은 주소에 접근하고자 한다면(물론, 이 때 프로세서가 정렬되지 않은 주소에 접근할 수 있는 기능을 제공한다는 전제 조건 하에서의 이야기입니다) 프로세서는 여러 개의 워드를 읽어들이게 될 것입니다. 즉 CPU는 요청한 주소에 걸쳐져 있는 메모리의 각 워드들을 읽게 됩니다. 이로 인해 요청된 데이터에 액세스하는데 필요한 메모리 트랜잭션은 최대 2배까지 증폭하게 됩니다.

 

이러한 이유로 2바이트를 읽는 것은 4바이트를 읽는 것보다 느리게 읽혀질 수 있습니다. 예를 들어, 다음과 같은 구조체를 가진다고 가정하겠습니다:

struct some_struct
{
    char c;         // 1 바이트
    int i;            // 4 바이트
    short s;     // 2 바이트
}

32비트 프로세서에서는 이 구조체가 다음과 같은 형식으로 정렬될 것입니다:

프로세서는 이 구조체에 대한 모든 멤버들에 대해 한 번의 트랜잭션으로 읽어들일 수 있습니다. 위에서 언급한 구조체가 네트워크 전송의 효율성을 위해 1바이트로 패킹(packing)되었다고 가정해보겠습니다. 코드는 다음과 같을 것입니다:

#pragma pack(1)
struct some_struct
{
    char c;         // 1 바이트
    int i;            // 4 바이트
    short s;     // 2 바이트
}
#pragma pack()

이 경우에 첫 번째 바이트(멤버 변수 c)를 읽어들이는 경우에는 위와 같습니다. 만약 0x0005부터 16비트를 읽고자 한다면(멤버 변수 s) 프로세서는 0x0004에서 4바이트(워드 크기만큼)를 읽어들인다음 16비트 레지스터에 저장하기 위해 왼쪽으로 1바이트만큼 시프트할 것입니다. 약간의 추가 작업이 발생했지만, 대부분 한 번에 이 작업을 처리할 수 있습니다.

 

하지만 0x0001에서 32비트(멤버 변수 i)를 요청하면 2배 증폭됩니다. 프로세서는 결과 레지스터(result register)에 0x0000을 읽어서 1바이트를 왼쪽으로 시프트한 다음 0x0004에서 임시 레지스터(temporary register)로 다시 읽은 다음 오른쪽으로 3바이트 시프트 한다음 두 레지스터를 OR 연산을 한 값을 결과 레지스터에 쓰게 될 것입니다.

 

 

보너스 : 캐시(cache)

링크에 따르면 캐시 라인에서의 얼라인먼트와 성능의 연관 관계에 대한 글이 포스팅되어 있습니다. 이외에도 캐시 수준에서의 최적화에 대한 설명에 대한 글이 작성되어 있으니, 한 번 읽어보시는 것도 좋을 것 같습니다.

 

 

 

원자성(Atomicity)

---

CPU는 메모리의 정렬된 워드에 대해서만 원자적으로 연산할 수 있으며, 이것은 다른 명령어가 해당 작업을 방해할 수 없음을 의미합니다. 이는 많은 lock-free daqqta structures와 다른 동시성 패러다임의 정확한 작동에 중요합니다.

 

원자성과 메모리 얼라인먼트에 대한 관계는 다음의 상황으로 설명될 수 있습니다. 데이터가 메모리 얼라인먼트가 되어있지 않았을 때, 이 데이터가 두 페이지 가상 메모리에 걸쳐있게 된다면, 첫 번째 페이지가 메모리에 상주하고 마지막 페이지가 상주하지 않을 수 있습니다. 이 경우 액세스할 때 명령어 중간에 페이지 오류가 생성되어 가상 메모리 매니지먼트의 swap-in 코드가 실행되어, 명령의 원자성을 파괴하게 됩니다.

 

 

 

더 많은 이야기

---

메모리 얼라인먼트에 대해서 설명 해놓은 사이트들에 대한 링크를 레퍼런스 항목과 분할하여 정리하였습니다. 관심 있으신 분들은 참조하시면 도움이 되실 것 같습니다:

• https://developer.ibm.com/articles/pa-dalign/
• http://egloos.zum.com/wonchuri/v/2127834

 

 

 

레퍼런스

---

위키피디아 - Data structure alignment
Stack Overflow - purpose of memory alignment
Difference Bettween.net - Difference Between DMA and PIO
kldp - 메모리 정렬제한에 대해서...
igoro - Gallery of Processor Cache Effects