기술 요약: 분산 컴퓨팅 시스템을 위한 생성적 마르코프 모델 (Generative Markov Model)

문제 정의

컴퓨팅 컨티뉴엄(computing continuum)과 같은 신흥 분산 컴퓨팅 패러다임은 본질적인 이질성, 확률성 및 복잡성을 특징으로 합니다. 클라우드 컴퓨팅은 온디맨드 프로비저닝과 같은 장점을 제공하지만, 증가하는 수요에 맞춰 AI 추론 인프라를 확장하는 것은 상당한 비용과 환경적 부담을 초래합니다. 사용자 기기, 에지(edge), 클라우드를 통합하는 볼런티어 컴퓨팅(volunteer computing) 및 컴퓨팅 컨티뉴엄과 같은 대안적 패러다임은 효율성 향상의 잠재력을 제공합니다. 그러나 이러한 시스템은 자원의 이질성과 사용자의 간헐적인 가용성으로 인해 안정적인 서비스 품질(QoS) 보장에 어려움을 겪습니다.

식별된 핵심 과제는 자원 이질성, 확률적 가용성 및 높은 차원의 시스템 상태를 모두 고려할 수 있는 통합된 정형 모델의 부재입니다. 이러한 모델 없이는 대규모 배포를 저해하는 성능 트레이드오프에 대한 추론과 대규모 스케일에서의 의사결정 정책 최로 최적화하는 것이 어렵습니다.

방법론

저자들은 분산 컴퓨팅 시스템을 모델링하기 위한 생성적 마르코프 모델(Generative Markov Model, GMM) 프레임워크를 제안합니다. 이 방법론은 트랙터빌리티(tractability, 계산 용이성)를 확보하기 위해 구조화되고 인수 분해된(factorized) 시스템 상태 표현에 의존합니다.

1. 이론적 프레임워크

시간 $t$에서의 시스템 상태 $s_t$는 $N$개의 고차원 변수로 구성된 튜플로 정의됩니다. 상태 시퀀스에 대한 결합 분포의 복잡성을 관리하기 위해, 모델은 마르코프 성질을 부과하고 두 단계의 희소 인수 분해(two-level sparse factorization)를 활용합니다:

• 변수 인수 분해 (Variable Factorization): 결합 분포 $p(s_t | s_{t-1})$은 현재 및 이전 상태의 특정 부모 변수 집합 $Pa(v_t)$에 조건화된 각 고수준 변수 $v_t$에 대한 조건부 분포(인수)로 분해됩니다.
• 요소 인수 분해 (Element Factorization): 각 고차원 변수 $v_t$는 다시 개별 요소 $v_t \in v_t$에 대해 인수 분해됩니다. 이는 노드나 태스크와 같은 구성 요소가 글로벌 상태가 아닌 로컬 정보에 기반하여 진화하는 분산 시스템 특유의 희소한 의존 구조를 활용합니다.

이러나 인수 분해는 원래라면 계산적으로 불가능했을 시스템 상태에 대한 시뮬레이션, 추론 및 정책 학습을 가능하게 하는 트랙터블한 모델을 산출합니다.

2. 사례 연구: 협업형 분산 AI 추론

본 프레임워크는 전용 서버($v_0$)와 사용자 노드 집합($I$)이 참여하는 협업 AI 추론 시나리오에 적용됩니다.

• 시스템 상태: 상태 벡터 $s_t$는 사용자 가용성($o_t$), 요청 상태($q_t$), 자원 할당($a_t$), 준비 상태($x_t$), 실행 상태($y_t$), 자원 소비($c_t$), 그리고 지속 시간 변수($d_t$)를 포함합니다.
• 의존성: 모델은 자원 자기상관(히스토리 버퍼를 통해 처리됨) 및 데이터 전송 단계와 실행 단계 간의 결합과 같은 복잡한 의존성을 포착합니다.
• 정책: 의사결정은 두 가지 정책 인수에 의해 제어됩니다:
  • 스케줄러 ($\pi$): 서버에서 실행되며, 서브태스크 다운로드 및 실행 할당을 결정합니다.
  • 실행기 ($\varsigma$): 각 노드에서 실행되며, 로컬 자원 제약(예: 중단, 일시 정지)을 강제합니다.
• 최적화 문제:
  • 스케줄러 정책 최적화: 장기적인 QoS(지연 시간 최소화)를 극대화하기 위해 평균 보상 강화 학습(RL) 문제로 정식화됩니다.
  • 전용 자원 최적화: 고정된 정책 하에서 특정 태스크 유형에 대한 지연 시간 임계값을 충족하기 위해 필요한 최소 명목 서버 자원을 찾기 위한 찬스 제약(chance-constrained) 최적화 문제입니다.

주요 기여

1. 생성적 마르코프 모델링: 본 논문은 전체 분산 컴퓨팅 시스템을 생성적 마르코프 모델로 모델링하는 프레임워크를 도입합니다. 특정 결정 문제를 MDP로 정식화하는 기존 연구와 달리, 이 접근 방식은 시스템 역학 자체를 모델링하여 분산 컴퓨팅과 마르코프 체인 이론 및 RL을 연결합니다.
2. 새로운 인수 분해 구조: 프레임워크는 새로운 두 단계 희소 인수 분해(변수 및 요소 수준)와 모듈형 구조를 채택합니다. 이를 통해 각 시스템 변수에 적합한 기술을 사용하여 조건부 분포를 독립적으로 추정할 수 있으며, 고차원임에도 불구하고 모델을 트랙터블하게 유지합니다.
3. 실제적 구현: 저자들은 전용 서버 자원과 자원 봉사 사용자 자원 간의 상호작용을 모델이 어떻게 처리하는지 보여주는 구체적인 협업 AI 추론 구현체를 제공합니다.

결과

프레임워크는 최대 10,000명의 사용자와 다양한 서버 용량을 가진 분산 추론 시스템 시뮬레이션을 통해 평가되었습니다. 두 가지 스케줄링 정책이 비교되었습니다: 중앙 집중형(모든 서브태스크를 서버에서 처리) 및 분산형(서버와 온라인 사용자 사이에 서브태스크를 균등하게 분배).

• 지연 시간 성능: 사용자 수가 증가함에 따라 중앙 집중형 정책은 병목 현상이 발생하여 P99 지연 시간이 크게 높아졌습니다. 반면, 분산형 정책은 점진적으로 중앙 집중형 방식을 능가하며, 단순한 분포 전략에서도 더 낮은 지연 시간을 기록했습니다.
• 자원 효율성: 분산형 정책은 중앙 집중형 정책에 비해 서버의 CPU 및 메모리 사용량을 지속적으로 낮게 유지했습니다. 특히, 1,000명의 사용자 시점에서 두 정책은 유사한 P99 지연 시간을 달랐으나, 분산형 정책은 훨씬 더 적은 서버 자원 소비를 달着했습니다.
• 확장성: 결과는 계산을 사용자 기기로 분산시키는 것이 지연 시간과 서버 자원 소비를 모두 줄인다는 것을 보여주며, 이러한 환경에서 적응형 의사결정의 효용성을 입증합니다.

의의 및 주장

본 논문은 제안된 프레임워크가 복잡하고 이질적인 분산 시스템에서 성능 트레이드오프를 추론하고 의사결정을 최적화하기 위한 필수적인 정형 모델을 제공한다고 주장합니다. 희소 인수 분해를 통해 시스템 상태를 트랙터블하게 만듦으로써, 프레임워크는 다음을 가능하게 합니다:

• 시뮬레이션 및 평가: 전체 규모의 물리적 배포 없이도 다양한 조건(예: 부하, 자원 가용성) 하에서 시스템 동작을 시뮬레이션할 수 있습니다.
• 정책 최적화: (최적화 문제로 정의된 것처럼) 최적의 스케줄링 정책을 학습하기 위한 RL 방법론으로의 직접적인 연결을 제공합니다.
• 모듈성: 전체 프레임워크를 재설계하지 않고도 새로운 자원 유형, 태스크 구조 또는 노드 동작을 모델에 확장할 수 있는 능력을 갖추고 있습니다.

저자들은 중앙 집중형 스케줄링이 규모가 커짐에 따라 실패하는 반면, 계산을 사용자 기기로 분산하는 것이 상당한 효율성 이득을 제공한다고 결론짓습니다. 또한, 그들은 이러한 적응형 의사결정 전략을 개발하고 최적화하는 것은 제공된 통합된 확률적 구조 없이는 불가능하다고 강조합니다. 향후 연구는 실제 환경 검증, 확장성 조사, 그리고 스케줄러 및 자원 할당 정책의 추가 최적화에 집중될 예정입니다.