메모리 의존성 판별 (Memory Disambiguation)

개요

메모리 의존성 판별(Memory Disambiguation)은 고성능 비순차 실행(out-of-order execution) 마이크로프로세서에서 로드와 스토어를 프로그램 순서와 다르게 실행할 때 사용하는 하드웨어 기술 모음입니다. 이 기술은 실행 시점에 메모리 작업 간 실제 의존성을 판별하고, 잘못된 추측이나 순서 위반이 발생했을 때 프로세서가 안전하게 복구할 수 있도록 합니다.

레지스터 의존성은 디코드 단계에서 비교적 일찍 판별할 수 있지만, 메모리 의존성은 실제 주소가 계산되기 전까지 확정할 수 없습니다. 따라서 프로세서는 스토어 큐, 로드 큐, store-to-load forwarding, 메모리 의존성 예측기 같은 구조를 사용해 모호한 의존성(ambiguous dependency)을 관리하며, 이를 통해 정확성을 유지한 채 명령어 수준 병렬성(ILP)을 끌어올립니다.

핵심 개념

메모리 의존성 유형

메모리 의존성은 세 가지 유형으로 분류됩니다:

1. RAW (Read-After-Write) - 실제 의존성: 스토어가 메모리에 값을 기록한 후, 같은 주소를 읽는 로드가 존재할 때 발생합니다. 로드는 스토어가 기록한 최신 값을 읽어야 합니다.

2. WAR (Write-After-Read) - 역 의존성: 로드가 메모리에서 값을 읽은 후, 같은 주소에 값을 기록하는 스토어가 존재할 때 발생합니다. 스토어는 로드가 읽은 값 이후에 기록되어야 합니다.

3. WAW (Write-After-Write) - 출력 의존성: 두 스토어가 같은 메모리 주소에 값을 기록할 때 발생합니다. 올바른 순서로 기록되어야 합니다.

메모리 주소의 모호성

레지스터 기반 의존성은 명령어 디코딩 시점에 정적으로 결정할 수 있지만, 메모리 의존성은 런타임에 레지스터 값이 결정되어야 알 수 있습니다:

store $1, 2($2)      # Mem[R2+2] <= R1
load  $3, 4($4)      # R3 <= Mem[R4+4] (위 스토어와 같은 주소일 수 있음)

이러한 모호한 의존성은 비순차 실행 코어가 메모리 명령어를 공격적으로 발행하는 데 가장 큰 제약 중 하나입니다.

LSQ와 예측기의 역할

현대 코어는 로드 큐와 스토어 큐를 분리하거나 하나의 LSQ(Load-Store Queue)로 통합해 in-flight 메모리 명령어를 추적합니다. 스토어는 주소와 데이터를 큐에 보관한 채 retire 시점까지 캐시나 메모리 계층에 commit을 미루고, 로드는 이 구조를 조회해 같은 주소의 이전 스토어가 있는지 확인합니다.

여기에 메모리 의존성 예측기까지 더해지면, 아직 주소가 계산되지 않은 상태에서도 특정 로드가 이전 스토어를 기다려야 하는지 추측할 수 있습니다. 대표적으로 store set 계열 예측기는 반복적으로 충돌하는 load/store 쌍을 학습해 불필요한 flush를 줄이고, 반대로 지나치게 보수적인 대기로 인한 성능 손실도 완화합니다.

비교/분석

메모리 의존성 판별 구현 비교

스토어 큐 vs 로드 큐 비교

동작 원리

1. 스토어 버퍼링 및 포워딩

스토어 명령어는 실행 시 즉시 캐시나 메모리 계층에 기록되지 않고 스토어 큐에 버퍼링됩니다. 값은 retire 시점에 아키텍처 상태로 commit되며, 이 덕분에 분기 오예측이나 예외가 발생해도 잘못된 경로의 스토어를 외부 메모리 상태에 반영하지 않을 수 있습니다.

스토어-로드 포워딩 과정:
1. 스토어가 실행되면 주소와 데이터가 스토어 큐에 저장됩니다
2. 후속 로드가 실행될 때 스토어 큐를 CAM으로 검색합니다
3. 같은 주소의 이전 스토어가 있으면 해당 데이터를 직접 전달합니다
4. 없으면 메모리 시스템에서 값을 읽습니다

2. RAW 위반 감지 및 복구

로드 큐 CAM 검색 방식:
1. 스토어가 실행될 때 로드 큐를 CAM으로 검색합니다
2. 같은 주소의 완료된 로드가 있으면 RAW 위반을 감지합니다
3. 위반된 로드는 위반 상태로 표시됩니다
4. 해당 로드가 은퇴될 때 파이프라인을 플러시하고 재시작합니다

은퇴 시점 탈출 방식:
1. 먼저 실행된 로드가 은퇴 시점에 다시 실행됩니다
2. 두 번째 읽기 값과 첫 번째 값이 다르면 RAW 위반을 감지합니다
3. 위반 시 파이프라인을 플러시하고 재시작합니다

3. 메모리 의존성 예측

고성능 프로세서는 로드/스토어 주소가 알려지기 전에 의존성을 예측합니다:
- 예측된 의존성이 있는 로드는 해당 스토어의 주소 또는 데이터가 준비될 때까지 대기합니다
- 의존성이 없다고 예측되면 로드를 먼저 발행해 메모리 지연을 숨깁니다
- 예측이 맞으면 파이프라인 플러시 없이 높은 처리량을 유지합니다
- 예측이 틀리면 위반 load 이후 파이프라인을 flush하고 재실행합니다

특히 반복 루프에서는 같은 load/store 쌍이 지속적으로 충돌하는 경우가 많아, 예측기가 과거 위반 이력을 이용해 보수적으로 대기시킬 대상을 좁혀 가는 방식이 널리 연구되었습니다. 이 영역은 단순 성능 최적화가 아니라, 큰 LSQ의 탐색 비용과 flush 빈도 사이의 균형을 맞추는 핵심 설계 지점입니다.

장단점

장점

1. ILP 극대화: 독립적인 로드와 스토어를 앞당겨 발행해 메모리 지연을 숨깁니다
2. 성능 향상: 캐시 miss가 없는 경우 로드를 빠르게 완료해 IPC(Instructions Per Cycle)를 높입니다
3. 유연한 실행: 의존성이 없는 메모리 작업은 프로그램 순서를 엄격히 기다리지 않아도 됩니다
4. 정확한 복구: 위반 감지 시 파이프라인 flush와 재실행으로 정확한 아키텍처 상태를 회복합니다

단점

1. 하드웨어 복잡도: CAM 구조, 복잡한 검색 로직, 복구 메커니즘이 필요합니다
2. 전력 소모: 연관 검색(associative search)은 상당한 전력을 소모합니다
3. 타이밍 문제: 큰 로드/스토어 큐에서 검색은 어려운 타이밍 경로가 될 수 있습니다
4. 면적 오버헤드: 추가 큐와 제어 로직은 칩 면적을 증가시킵니다

관련 기술

참고 문헌

1. Roth, A. "Load-Queue Cleanup for Load-Queue-Based Memory Dependence Prediction." IEEE/ACM International Symposium on Microarchitecture, 2005.
2. González, J., et al. "Memory Disambiguation for Out-of-Order Processors." IEEE Transactions on Computers, 1999.
3. Intel Corporation. "Intel 64 and IA-32 Architectures Optimization Reference Manual." 2023.
4. ARM Limited. "ARM Architecture Reference Manual: ARMv8-A." 2023.
5. Hennessy, J.L. & Patterson, D.A. "Computer Architecture: A Quantitative Approach." 6th Edition, Morgan Kaufmann, 2017.
6. Chrysos, G.Z. & Emer, J.S. "Memory Dependence Prediction using Store Sets." ISCA, 1998.

관련 문서

• Out-of-Order 실행 - 비순차 실행 코어의 전체 흐름
• CPU 캐시 아키텍처 - 캐시와 메모리 시스템
• 메모리 일관성 모델 - 멀티프로세서 메모리 일관성

핵심 정리

1. 메모리 의존성 판별은 비순차 실행 코어에서 로드와 스토어의 실제 선후관계를 런타임에 판별하는 핵심 기법입니다.
2. 세 가지 메모리 의존성(RAW, WAR, WAW)을 안전하게 다루기 위해 스토어 버퍼링, 포워딩, 위반 감지 구조가 함께 동작합니다.
3. 현대 프로세서는 로드 큐 CAM 검색 또는 retire 시점 재실행 방식으로 RAW 위반을 탐지하고 복구합니다.
4. LSQ와 CAM 검색은 전력, 면적, 타이밍 비용을 유발하지만 ILP와 IPC 향상 효과가 매우 큽니다.
5. 메모리 의존성 예측기는 반복 충돌 패턴을 학습해 불필요한 flush와 과도한 대기를 동시에 줄이는 방향으로 발전해 왔습니다.