비순차 프로세서 파이프라인 (Out-of-order Processor Pipeline)의 핵심기술 (2)

지난 포스팅에서 비순차 프로세싱의 핵심기술인 register renaming, reoder buffer, reservation station 에 대해서 알아보았는데요. 여기에 또 하나 빠지지말아야할 기술이 있습니다.
바로 메모리 연산을 위한 로드-스토어 큐(Load-Store Queue)입니다. 이번 시간에는 이 로드스토어큐에 대해 알아보겠습니다.
Load-Store Queue 는 다음과 같이 여러가지 이름으로 불립니다. 모두 같은 것이니 혼동하지 마세요.
이러한 Load-Store Queue 는 아키텍쳐에 따라 구조가 약간씩 다릅니다. Load Queue 와 Store Queue 가 별도로 나누어져 있는 경우도 있습니다.

  • Load-Store Buffer
  • Store Buffer or Store Queue
  • Memory Order Buffer

명령어의 비순차적 처리 측면에서 볼 때 Load/Store 연산은 일반 연산과 크게 다른 점이 한가지 있습니다.
일반 명령어의 경우 의존성을 검사하려면 operand register 만 따져보면 되었지요. 그래서, reservation station 에서 눌러앉아서 자신이 필요로 하는 operand 가 읽혀질 때까지 주구장창 기다리면 되었었습니다.
하지만, Load/Store 는 메모리(또는 캐쉬)에 접근을 해야하는 명령어이므로 기본적으로 주소가 중요한 의존성 검사 기준이 됩니다. 같은 주소를 보는 놈들끼리 의존성이 있다고 보면 되는 것입니다.
그래서, 메모리 연산(Load/Store)은 데이터 의존성이 아니라 메모리 의존성을 띠고 있다고 말합니다.
메모리 연산이 엄청 느리다는 것은 삼척동자도 다 아는 사실이기 때문에, 이러한 메모리 연산도 병렬성을 발휘할 수 있다면 성능에 큰 영향을 미칠 것입니다.
이러한 메모리 의존성의 검사를 수행하기 위해 필요한 것이 Load-Store Queue 입니다.
Load-Store Queue 는 Reorder Buffer 와 아주 유사합니다. 실제로 Reorder Buffer 를 기초로 하여 만들어졌다고 합니다. Reorder Buffer 의 경우 명령어가 Reservation Station 으로 Issue 되는 시점에 똑같이 Entry 를 할당받는다고 했는데, Load-Store Buffer 역시 마찬가지로 이 시점에 Entry 를 할당받습니다. 다만 Load/Store 명령일 때만 할당받을 뿐이지요. 그러므로, Load-Store Buffer 에 Load 및 Store 명령이 쌓이는건 Reorder Buffer 와 마찬가지로 순차적(In-order)으로 쌓이게 됩니다.
예제 코드를 하나 보면서 생각해봅시다.

add r1, r1, #5    ->    add F1, r1, #5  (가)
add r2, r1, #4    ->    add F2, F1, #4  (나)
add r1, r2, #3    ->    add F3, F2, #3  (다)  @ r1 은 (가)와 의존성 없으므로 F3 으로 변경
add r1, r3, #2    ->    add F5, F4, #2  (라)  @ (가)와는 의존성 없으나 (마)와 의존성 존재 
add r4, r1, #1    ->    add F6, F5, #1  (마)  @ (라)와의 의존성 고려하여 F5 로 변경

0x104 명령과 0x112 명령을 보면 [r1], [r4] 메모리에 대한 Store -> Load 를 수행하고 있습니다. 그런데, r1 과 r4 의 값이 어떠냐에 따라 두 명령은 메모리 의존성이 있을 수도 있고 없을 수도 있겠군요.
그러니, 아래와 같은 3 가지 처리방향이 생길 것입니다.

  • r1 != r4 :
    의존성이 없으므로 비순차적 처리를 하면 됩니다. 즉, 0x112 명령이 0x104 의 완료를 기다릴 필요가 없다는 것이지요.
  • r1 = r4 :
    ldr 명령은 반드시 str 명령 뒤에 처리되어야 합니다.
  • 0x112 수행 시점에 0x104 의 r1 값이 아직 결정되지 않아서(이 또한 load 중일 수 있음) 의존성을 알 수 없을 경우 :
    메모리 의존성 예측기(Memory Dependancy Speculator)를 사용하여 예측실행을 합니다.
    분기예측처럼 일단 예측기의 결과에 따라 진행해보고 틀리면 rollback 하는 방식입니다.

개념적인 Pipeline 그림과 함께 Load-Store Buffer 가 어떻게 사용되는지 간단히 살펴볼까요 ?

그림을 보면 위에서 언급한대로 Fetch Buffer 에서 꺼낸 명령을 Decode 후 reservation station 및 reorder buffer, load-store buffer 쪽에 할당하는 화살표를 볼 수 있습니다. 같은 시점에 명령어를 동시에 reorder buffer 와 load-store queue 에 쌓는 것입니다. 원래 명령어의 순서대로(In-order) 말이죠.
그 뒤의 scheduling 과 execution 단계가 비순차적이라는 것을 지난 포스팅에서도 언급했었고, 그림의 위쪽 부분에 넣은 Pipeline Stage 단계를 보아도 알 수 있을 것입니다.
위의 그림을 바탕으로 위쪽 예제 코드에서 str 와 ldr 의 처리 과정을 잠깐 살펴보면 다음과 같습니다. 정확한 처리 순서는 Pipeline 그림과 함께 cycle 을 따져봐야할 것이지만 간단히 처리흐름만을 보기 위해 아래와 같이 정리했습니다.

  • fetch buffer 에서 str 명령어 인출
  • decode 및 register renaming 처리
  • reservation station, reorder buffer, load-store buffer entry 할당하여 저장
  • r1, r3 operand(source operand)가 이미 준비되었으면 AGU(Address Generation Unit)에게 r1 에 대한 주소계산 요청
  • str 명령과 sub 명령은 의존성이 없으므로 sub 명령은 곧 바로 실행됨
  • ldr 명령은 decode 후 reservation station 에서 이전 명령(sub)의 결과를 대기 (Read-After-Write 의존성)
    현재 load-store buffer 에는 str 와 ldr 명령어를 위한 entry 가 존재함.
  • str 명령의 r1 operand 주소 계산 결과가 load-store buffer 에 기록됨.
  • sub 의 결과를 받은 ldr 명령은 해당 r4 operand 를 AGU 에게 주소계산 요청.
    주소계산 완료 후 메모리 주소 의존성 검사를 수행하는데, str 명령의 주소계산이 완료된 상태이면 r1, r4 간의 주소 의존성을 dependancy matrix 를 이용하여 검사함.
  • 주소가 일치할 경우 ldr 는 캐쉬에 요청할 필요없이 str 의 값을 바로 load 함. (Store-to-Load Forwarding)
    일치하지 않으면 캐쉬에 load 요청.
  • 저장된 상태에서 str 가 load-store buffer 에서 가장 오래된 명령어라면 메모리(캐쉬)에 반영하고 entry 삭제함.
    ldr 명령이 가장 오래된 명령어라면 register 에 반영하고 entry 삭제함.

만약 프로그램의 모든 load/store 가 서로 메모리 의존성으로 완벽하게 묶여있다면, load/store 를 순차적으로 처리해야한다는 말이므로 성능이 많이 느릴 수 밖에 없습니다.
하지만, 실제적으로는 의존성이 존재하지 않는 메모리 연산들이 상당히 많이 존재하고, 이러한 경우 다른 연산들처럼 실행의 완료 순서가 서로 바뀔 수 있습니다. 그래서, load-store queue 도 reorder buffer 처럼 실행이 완료된 것(주소와 값이 모두 얻어진 것)들을 표시해두고, 해당 명령이 queue 에서 가장 오래된 명령일 경우 register(ldr) 및 메모리/캐쉬(str)에 flush 하게 됩니다.
이것이 핵심입니다. reorder buffer 와 동작방식이 상당히 유사하죠.

만약 str 연산이 아직 메모리(캐쉬)에 반영이 안된 채로 load-store queue 에 남아있는 상태라면, 뒤의 ldr 연산이 해당 buffer 의 내용을 참고할 수 있는데 이를 Store-to-Load Forwarding 이라고 부릅니다.

참고로 load-store queue 의 entry 에 기록되는 내용은 다음과 같습니다. 번호와 명령어 타입, PC 값은 초기 할당 시 바로 기록이 됩니다. 반면 위에 설명한대로 Address 는 AGU 의 주소계산 결과가 저장되고, Value 의 경우는 Load 또는 Store 할 실제 값이 기록되게 됩니다. 이러한 Value 는 Store 의 경우 Immediate 값 또는 이전 연산의 결과를 읽어들인 값이 될 것이고, Load 의 경우는 메모리(캐쉬)에서 읽어들인 값이 될 것입니다.

  • 번호(순번)
  • 명령어 타입 (Load or Store)
  • PC 값
  • Address (Load 또는 Store 할 메모리 주소) -> 의존성을 검사하는 기준이 됨.
  • Value (Load 또는 Store 할 값)

References:

  1. http://www.arm.com/files/pdf/armcortexa-9processors.pdf
  2. http://www.arm.com/files/pdf/armcortexa-9processors.pdf
  3. http://inst.eecs.berkeley.edu/~cs152/sp09/lectures/L15-OoO-Superscalars.pdf
  4. http://www.arm.com/files/pdf/at-exploring_the_design_of_the_cortex-a15.pdf
  5. http://www.bdti.com/InsideDSP/2011/11/17/ARM
  6. http://www.arm.com/files/downloads/big_LITTLE_Final_Final.pdf
  7. http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf
  8. http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0363e/Chdcahcf.html
  9. http://en.wikipedia.org/wiki/Re-order_buffer
  10. 김민장의 “프로그래머가 몰랐던 멀티코어 CPU 이야기”

You may also like...

0 0 votes
Article Rating
Subscribe
Notify of
guest
4 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
승원

왠만하면 댓글 잘 남기지 않는데 정말 너무 큰 도움이 되었습니다. 감사합니다.

cloudrain21

도움이 되셨다니 기쁩니다~^^ 감사합니다.

진호용

예제코드가 잘못된것 같아요 ㅠㅠㅠ

Juntae Kim

그림 올린 소스쪽이 그림을 내린거같네요ㅠㅠ

4
0
Would love your thoughts, please comment.x
()
x