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 동작 과의 상호작용을 빠르게 가늠 가능.