kernbench2/docs/adr-ko/ADR-0048-mem-allocator-algorithms.md

# ADR-0048: Memory Allocator Algorithms — VirtualAllocator + PEMemAllocator

## Status

Accepted (2026-05-22).

`policy/address/allocator.py` 의 `_FreeList` / `PEMemAllocator` 와
`va_allocator.py` 의 `VirtualAllocator` 가 사용하는 free-list 알고리즘,
페이지 정렬, coalescing 규칙을 명시한다. ADR-0001 (PhysAddr 레이아웃) 과
ADR-0011 (PA/VA/LA 모델) 이 주소 스킴을 정의하나, **할당 알고리즘**은 별도
ADR 이 없었다.

## First action (제일 처음에 하는 일)

### `_FreeList(capacity)`

생성 즉시 `self._capacity = capacity`, `self._used = 0`, `self._free =
[(0, capacity)]` 로 초기화. 첫 일은 **전 영역을 single free block 으로
세우는 것** — 즉 `(offset=0, size=capacity)` 한 튜플이 free list 의 유일한
원소다.

### `PEMemAllocator(sip_id, die_id, pe_id, cfg)`

생성 즉시 두 개의 `_FreeList` 를 만든다:

- `self._hbm = _FreeList(cfg.hbm_slice_bytes)` — 이 PE 가 소유한 HBM
  slice 의 바이트 크기 (`hbm_bytes_per_cube // hbm_slices_per_cube`) 만큼.
- `self._tcm = _FreeList(cfg.tcm_allocatable_bytes)` — `tcm_bytes_per_pe -
  tcm_scheduler_reserved_bytes` 만큼 (scheduler 예약분은 사전 분리).

따라서 PEMemAllocator 의 첫 일은 **이 PE 의 HBM slice 와 사용자
TCM 영역을 각각 단일 free block 으로 세우는 것**.

### `VirtualAllocator(va_base, va_size, page_size=2*1024*1024)`

생성 즉시 `self._va_base = va_base`, `self._va_size = va_size`,
`self._page_size = page_size`, `self._used = 0`, `self._free = [(va_base,
va_size)]`. 첫 일은 **VA base 부터 size 까지 single block 으로 세우고
page_size 를 회수**.

## Context

`runtime_api/context.py::_ensure_allocators` 는 다음 단계로 allocator 세트를
구성한다:

1. spec 으로부터 `hbm_total_gb_per_cube`, `hbm_slices_per_cube`,
   `tcm_size_mb`, target_device 별 SIP 범위 등을 읽음.
2. `AddressConfig` 로 모든 파라미터를 frozen 하게 패킹.
3. target SIP 범위 × cube × PE 의 모든 조합에 대해
   `PEMemAllocator(sip, cube, pe, cfg)` 인스턴스를 1개씩 생성.
4. `VirtualAllocator(va_base=0x1_0000_0000, va_size=64 GiB,
   page_size=pe_mmu.page_size)` 를 1개 생성.

allocator 들의 책임:

- **PEMemAllocator**: PE-로컬 HBM slice / TCM 의 PA-공간 할당 (PhysAddr
  encoding 까지 포함).
- **VirtualAllocator**: device-wide VA 공간을 페이지 정렬로 할당. 이후
  `RuntimeContext._create_tensor` 가 VA → PA 매핑을 `MmuMapMsg` 로 fabric
  에 push.

이 알고리즘들은:

- **first-fit** 으로 단순.
- 자유 블록 리스트는 **offset 정렬 (sorted by start)** 유지.
- `free()` 시 **양쪽 인접 블록과 coalesce**.

이런 결정의 근거가 어디에도 없으므로, 향후 누군가 "왜 best-fit 이 아닌가",
"왜 buddy allocator 가 아닌가", "왜 partial overlap free 가 silently
허용되는가" 라는 질문에 답할 기준이 필요. 본 ADR 이 그 기준을 마련한다.

## Decision

### D1. `_FreeList` — offset-기반 first-fit + coalescing

`policy/address/allocator.py::_FreeList`:

- 내부 표현: `list[tuple[int, int]]` = `[(start_offset, size), ...]` —
  start offset 으로 정렬된 자유 블록의 sorted list.
- `alloc(nbytes)`:
  1. free list 를 앞에서부터 순회 (first-fit).
  2. 처음 만나는 `size >= nbytes` 인 블록에서 앞부분을 잘라 사용.
  3. 정확히 일치하면 블록 통째로 제거; 아니면 `(start+nbytes, size-nbytes)`
     로 축소.
  4. `_used += nbytes`, 잘라낸 `start` 반환.
  5. 맞는 블록이 없으면 `AllocationError("overflow ... largest free block
     ...")`.
- `free(offset, nbytes)`:
  1. `_used -= nbytes`.
  2. `bisect_left(self._free, (offset,))` 로 삽입 위치 결정.
  3. 직전 블록과 인접 (`prev_start + prev_size == offset`) 하면 흡수.
  4. 직후 블록과 인접 (`offset+nbytes == next_start`) 하면 흡수.
  5. coalesced range 를 정렬 위치에 insert.

이 알고리즘은 fragmentation 에 약점이 있으나 (best-fit / buddy 대비), 본
시뮬레이터의 워크로드 특성상 (deploy/free 패턴이 거의 stack-like) 충분
하다는 것이 디자인 가정이다. 워크로드가 변하면 D1 supersede 후보.

### D2. partial overlap free 는 **검사하지 않는다**

`_FreeList.free(offset, nbytes)` 는 호출자가 정확한 (offset, nbytes) 를
넘긴다고 신뢰한다. 다음을 검증하지 않는다:

- 그 range 가 실제로 alloc 된 것인지.
- 그 range 가 다른 alloc 된 영역과 겹치지 않는지.

이유: 시뮬레이터 컨텍스트에서 호출자는 항상 `alloc()` 의 반환값을 그대로
저장했다가 `free()` 에 넘기는 패턴이며, 외부 사용자 입력이 아니다. 안전성
검사를 추가하면 매 free 마다 O(N) 비용이 들어 시뮬 wall-clock 에 영향.

이 신뢰 모델이 깨지면 (예: 두 텐서가 같은 PA 를 가리키는 코드 경로 도입)
즉시 ADR-level 으로 재검토.

### D3. `PEMemAllocator` — HBM/TCM 두 채널 분리

`PEMemAllocator(sip_id, die_id, pe_id, cfg)` 는 두 `_FreeList` 를 보유:

- `_hbm`: `cfg.hbm_slice_bytes` 크기.
- `_tcm`: `cfg.tcm_allocatable_bytes` (= `tcm_bytes_per_pe -
  tcm_scheduler_reserved_bytes`) 크기.

`alloc_hbm(nbytes) -> PhysAddr`:

- `_hbm.alloc(nbytes)` 로 offset 획득.
- `PhysAddr.pe_hbm_addr(sip_id, die_id, pe_id, pe_local_hbm_offset=offset,
  slice_size_bytes=cfg.hbm_slice_bytes)` 로 PA 인코딩.
- 실패 시 `AllocationError("HBM overflow ...")`.

`free_hbm(pa, nbytes)`:

- `pa.hbm_offset - pe_id * cfg.hbm_slice_bytes` 로 PE-local offset 복원.
- `_hbm.free(offset, nbytes)`.

`alloc_tcm(nbytes) -> PhysAddr`: 유사하게 `PhysAddr.pe_tcm_addr` 로 인코딩.

`free_tcm(pa, nbytes)`: `pa.sub_offset` 을 그대로 사용 (TCM 은 PE-local
offset 이 곧 sub_offset).

scheduler-reserved TCM 영역 (`cfg.tcm_scheduler_reserved_bytes`) 은
allocator 가 인지하지 않는다 (`_tcm` 의 capacity 에서 사전 차감되어 있음).
이는 ADR-0014 의 PE_SCHEDULER 내부 buffer 예약과 정합된다.

### D4. `VirtualAllocator` — 페이지 정렬 first-fit + coalescing

`policy/address/va_allocator.py::VirtualAllocator`:

- 내부 표현: `_FreeList` 와 동일한 sorted `list[tuple[int, int]]`.
  최초: `[(va_base, va_size)]`.
- `_align_up(nbytes) = ceil(nbytes / page_size) * page_size`.
- `alloc(nbytes) -> int`:
  1. `aligned = _align_up(nbytes)`.
  2. first-fit 으로 `size >= aligned` 인 블록 탐색.
  3. 블록 앞부분 `aligned` 만큼 잘라 사용. 정확히 일치하면 제거.
  4. `_used += aligned`. 블록 `start` (= aligned 된 VA) 반환.
  5. 실패 시 `VaAllocationError`.
- `free(va, nbytes)`: `_align_up(nbytes)` 단위로 free. _FreeList 와 동일한
  coalesce 알고리즘.

`page_size` 의 실제 값은 두 곳에서 다른 기본을 갖는다:

- `VirtualAllocator.__init__` 의 매개변수 기본값: `2 MiB`. 직접 호출하는
  테스트가 그대로 받는다.
- `RuntimeContext._ensure_allocators` 가 인스턴스화할 때:
  `pe_mmu.attrs.get("page_size", 4096)` — `topology.yaml` 의
  `pe_mmu.attrs.page_size` 가 있으면 그 값, 없으면 fallback 4 KiB.

두 기본이 다른 이유: VirtualAllocator 의 standalone 기본은 ADR-0039 의
PE_MMU stopgap 기본 (2 MiB) 과 정합되어 직접 테스트가 자연스럽고, context
fallback 의 4 KiB 는 topology 미설정 시 안전한 minimum page 다. 실제 사용
경로는 항상 후자이며 (`_ensure_allocators` 가 인스턴스화하므로),
`topology.yaml` 에서 `page_size` 가 명시되면 그 값이 양쪽 (MMU + VA
allocator) 으로 일관되게 흐른다.

만약 이 일치가 깨지면 (예: VirtualAllocator 의 page_size 를 PE_MMU 와
다르게 인스턴스화) MMU `map()` 가 서브-페이지 region 모드 (ADR-0039 D3) 로
흐른다.

VA 기본 범위: `va_base = 0x1_0000_0000` (= 4 GiB), `va_size = 64 GiB`. 이
값은 `_ensure_allocators` 에 하드코딩되어 있으며 ADR-0011 의 VA 모델에서
직접적인 의미를 갖지는 않는다 — 단지 host 코드와 충돌하지 않을 만큼 큰
주소 공간을 device-wide 로 잡아둔 것.

### D5. allocator 인스턴스의 lifecycle

- `RuntimeContext._ensure_allocators` 가 lazy 하게 호출됨 (`_create_tensor`
  의 첫 호출 시점).
- 한 번 생성된 allocator dict (`self._allocators`) 는 RuntimeContext 의
  lifetime 동안 재사용. 같은 process 안의 두 번째 deploy 는 새 객체를
  만들지 않는다.
- `RuntimeContext.cleanup()` 이 모든 living tensor 의 `_free_tensor()` 를
  호출 → MMU unmap + `va_allocator.free` + `pemem_allocator.free_hbm` 으로
  free list 가 원상복구. 다음 RuntimeContext 가 다시 만들면 초기 상태부터.

allocator 상태가 RuntimeContext 간에 공유되지 않는 점이 단일 process 안의
연속 실행에서 deploy → cleanup → deploy 의 결정성을 보장한다.

### D6. Allocator 실패는 raise 한다 (silent OOM 금지)

`_FreeList.alloc` / `VirtualAllocator.alloc` 모두 충분한 free block 이
없으면 `AllocationError` / `VaAllocationError` 를 던진다. 메시지에는
"required size + largest available block" 가 포함되어, fragmentation
인지 진짜 OOM 인지 진단 가능.

silent fallback (예: 가장 큰 블록만큼만 alloc) 는 절대 금지 — 부분 할당된
텐서가 SimPy 단계에 들어가면 라우팅·DMA 가 잘못된 PA 를 인지하여 시뮬
정확도가 깨진다.

### D7. address space 와 allocator 의 1:1 대응

물리 주소 공간 분리는 PhysAddr 의 sub-unit (ADR-0001 D2.3) 으로 표현되며,
각 sub-unit 마다 별도 allocator 인스턴스를 둔다:

- HBM slice → `PEMemAllocator._hbm`.
- PE TCM → `PEMemAllocator._tcm`.
- (현재 미사용) M_CPU local memory, CUBE SRAM → 별도 allocator 필요. 현재
  구현은 아직 IPCQ-only slot 으로 처리 (ADR-0023 D9.7) 하며 PA 공간을
  share 하지 않으므로 별도 free-list 가 없음.

cube-level SRAM allocator 가 필요해지면 `_FreeList(cfg.sram_bytes_per_cube)`
인스턴스를 cube 단위로 추가한다 (`cfg.sram_bytes_per_cube` 는 이미
`AddressConfig` 에 정의되어 있어 데이터 모델은 준비됨).

## Alternatives Considered

### A1. best-fit / buddy allocator

기각 (현재). 워크로드의 alloc/free 패턴이 stack-like (deploy 순서 = free
순서) 라 first-fit + coalescing 으로 fragmentation 이 충분히 통제된다.
LLM kernel sweep 에서 long-running fragmentation 이 관찰되면 buddy 로
교체하는 ADR 을 별도로 만든다.

### A2. partial overlap free 검증 추가

기각. D2 의 신뢰 모델 + O(N) 검사 비용. 단, 디버그 모드 (`KERNBENCH_DEBUG`
env var 등) 에서 활성화하는 옵션은 후속 작업으로 가능.

### A3. VA 와 PA 의 통합 allocator

기각. VA 공간 (64 GiB device-wide) 과 PA 공간 (slice 별 ~6 GiB) 는 의미
차원이 다르다. VA 는 host kernel 의 view, PA 는 device sub-unit 의 view.
ADR-0011 의 VA 모델 정신 (MMU 가 둘 사이를 매핑) 과 정합하기 위해
allocator 도 분리.

### A4. page_size 의 multi-tier 지원 (large page + small page)

기각 (현재). 단일 page_size (현재 2 MiB) 가 LLM kernel 의 텐서 단위 (수
MiB~수 GiB) 에 맞고, ADR-0039 D3 의 서브-페이지 region 으로 작은 매핑이
필요할 때 흡수된다. multi-tier page 는 MMU 자체 모델을 확장해야 하므로
별도 ADR 후보.

## Consequences

- allocator 알고리즘이 ADR-level 에서 굳어져 (D1·D3·D4), 새로운 시뮬
  시나리오에서 fragmentation 이슈가 발생할 때 "여기서 first-fit + coalesce
  를 쓰고 있다" 가 명확.
- D2 의 신뢰 모델이 명시되어, 향후 사용자 입력으로부터 직접 alloc/free 를
  받는 경로가 도입되면 본 ADR supersede 가 필요함을 일찍 인지 가능.
- D7 의 sub-unit별 allocator 1:1 대응이 명시되어, M_CPU/SRAM 별도 영역이
  필요해질 때 어디에 free-list 를 추가해야 하는지 명확.
- `VirtualAllocator` 의 page_size 가 PE_MMU 설정과 일치해야 함이 D4 에
  적혀 있어, 향후 topology.yaml 의 page_size 변경 시 ADR-0039 stopgap 동작
  과의 상호작용을 빠르게 가늠 가능.