🧠 4-Layer Memory Hierarchy Simulation

(L3: 2-Way Set Associative Cache)

---

1. 프로젝트 개요

본 프로젝트는 배열만 사용하여 4계층 메모리 계층 구조를 직접 설계·구현하고,
실세계 데이터 접근 시나리오를 기반으로 캐시 hit ratio를 분석하는 것이 목표이다.

특히 **L3 계층에 2-way set associative cache(E=2)**를 적용하여
direct-mapped 캐시와의 차이를 실제 예시를 통해 검증한다.

---

2. 프로젝트 목표

• 배열만 사용한 4계층 메모리 계층 구현
• L3 계층에 2-way set associative 캐시 적용
• 4096개 초과 실세계 데이터 사용
• 캐시 hit / miss 정확한 계산
• 실제 데이터 접근 패턴 기반 hit ratio 분석
• 코드 + 보고서(report.pdf) 제출

---

3. 메모리 계층 구조 설계

계층	크기 (elements)	매핑 방식
L1	1	Direct-mapped
L2	16	Direct-mapped
L3	256	2-Way Set Associative (LRU)
L4	4096	Direct-mapped

계층별 크기는 데이터 특성에 따라 일부 조정 가능하나,
전체 구조는 반드시 4계층을 유지한다.

---

4. 실세계 데이터 시나리오

데이터 설명

• 실세계 접근 패턴을 모사한 정수 주소 배열
• 데이터 크기: 최소 4096 초과 (권장 20,000 이상)
• 예시 시나리오:
  • 웹 페이지 ID 반복 조회
  • 뉴스 기사 ID 접근
  • 사용자 행동 로그 기반 접근 패턴

접근 특징

• 특정 주소 반복 접근 → Temporal Locality
• 인접 주소 접근 → Spatial Locality

---

5. 구현 구조 (클래스 전개도 + 담당자 매핑)

🧩 클래스 다이어그램 (텍스트 기반)

[Main]

• 역할: 프로그램 시작점
• 책임:
  • access trace 로딩
  • MemorySystem 생성 및 실행
• 사용 클래스:
  • TraceLoader
  • MemorySystem
  • Stats

---

[TraceLoader]

• 역할: 실세계 데이터 접근 패턴 생성/로딩
• 책임:
  • accessTrace(int[]) 생성
  • 파일 기반 trace 로딩
• 제공 메서드:
  • int[] loadTrace(String path)
  • int[] generateTrace()

---

[MemorySystem]

• 역할: 메모리 계층 접근 흐름 제어
• 책임:
  • L1 → L2 → L3 → L4 순차 접근
  • 상위 캐시 hit 시 하위 접근 중단
• 포함 객체:
  • L1Cache
  • L2Cache
  • L3Cache2Way
  • L4Cache
  • Stats
• 제공 메서드:
  • void access(int address)
  • void runSimulation(int[] trace)

---

[L1Cache]

• 역할: 최상위 캐시 (Direct-mapped)
• 크기: 1 element
• 책임:
  • tag / valid / data 배열 관리
  • hit / miss 판단
• 제공 메서드:
  • boolean access(int address)
• 담당자:
  • 역할 A

---

[L2Cache]

• 역할: 상위 캐시 (Direct-mapped)
• 크기: 16 elements
• 책임:
  • index / tag 계산
  • hit / miss 처리
• 제공 메서드:
  • boolean access(int address)
• 담당자:
  • 역할 A

---

[L3Cache2Way]

• 역할: 중간 캐시 (2-way Set Associative)
• 크기: 256 elements
• 구조:
  • valid[set][2]
  • tag[set][2]
  • data[set][2]
  • lru[set]
• 교체 정책:
  • LRU (Least Recently Used)
• 책임:
  • set / way 탐색
  • eviction 처리
• 제공 메서드:
  • boolean access(int address)
• 담당자:
  • 역할 B

---

[L4Cache]

• 역할: 최하위 캐시 (메인 메모리 역할)
• 크기: 4096 elements
• 책임:
  • miss 시 데이터 저장
• 제공 메서드:
  • boolean access(int address)
• 담당자:
  • 역할 C

---

[Stats]

• 역할: 통계 및 결과 관리
• 책임:
  • 계층별 hit / miss 카운트
  • hit ratio 계산
• 제공 메서드:
  • void recordHit(int level)
  • void recordMiss(int level)
  • void printResult()
• 담당자:
  • 역할 C

원칙: 각 캐시 계층은 독립 클래스, 내부 자료구조는 배열만 사용
MemorySystem은 “L1→L2→L3→L4” 접근 흐름만 책임짐

---

2) 클래스별 역할 요약 (한 줄 정의)

• Main: 프로그램 시작점, 입력(trace) 받아서 실행/결과 출력 트리거
• TraceLoader: 실세계 시나리오 기반 accessTrace(int[]) 생성 또는 파일 로딩
• MemorySystem: 계층 접근 흐름 제어(상위 hit이면 하위 접근 중단)
• L1Cache: direct-mapped 1라인 캐시 (valid/tag/data + hit/miss)
• L2Cache: direct-mapped 16라인 캐시 (valid/tag/data + hit/miss)
• L3Cache2Way: 2-way set associative + LRU (valid[set][2], tag[set][2], lru[set])
• L4Cache: direct-mapped 4096라인 (최하위 계층 저장소 역할)
• Stats: 계층별/전체 hit ratio 계산, 표 형태 출력

---

3) 담당자 배정 (누가 어떤 클래스 맡는지)

👤 역할 A (L1/L2 + 설계 파트)

• L1Cache
• L2Cache
• (선택) MemorySystem의 기본 흐름 설계에 참여(접근 규칙 합의)

👤 역할 B (L3 2-way + LRU 핵심)

• L3Cache2Way
• (필수) eviction 검증용 테스트 케이스/로그 포맷 같이 정의

👤 역할 C (데이터 + L4 + 실험 결과)

• TraceLoader
• L4Cache
• Stats
• Main (최종 실행/통합 담당)

---

4) 통합 시 “겹치지 않게” 합의할 인터페이스 (필수)

각 캐시 계층 공통 메서드:

boolean access(int address);   // hit이면 true, miss이면 false

if (L1.hit) return;
else if (L2.hit) return;
else if (L3.hit) return;
else L4.load;