이벤트 구동 시뮬레이션

1. 개요[편집]

이벤트 구동 시뮬레이션 Event-driven / Discrete-Event Simulation (DES)
전진 방식	고정 Δt 가 아니라 다음 사건 시각으로 점프
핵심 자료구조	미래사건목록(FEL) — 이진 힙 · 캘린더 큐 · 사다리 큐
비용	모의 시간이 아니라 사건 개수에 비례
시각 정확도	사건 시각을 풀 수 있으면 기계 정밀도
고전 응용	큐잉망 · 강체 충돌 · 경성구 분자동역학 · 스파이크 망 · 화학반응 SSA
병렬화	보수적(찬디-미스라-브라이언트) ↔ 낙관적(타임 워프)
천적	제논 거동 · 동시 사건 · 상호작용이 조밀한 계

이벤트 구동 시뮬레이션(event-driven simulation), 다른 이름으로 이산사건 시뮬레이션(discrete-event simulation, DES)은 계의 상태가 유한 개의 이산적인 순간에만 바뀐다고 보고, 그 순간들 사이는 통째로 건너뛰면서 시간을 전진시키는 시뮬레이션 방식이다. 시계를 일정한 간격으로 째깍거리게 하는 대신, “다음에 뭔가 일어나는 시각”으로 시계를 순간이동시킨다.

이 한 문장이 전부이고 나머지는 그 결과다. 손님이 없는 은행 창구는 아무리 오래 비어 있어도 계산할 것이 없고, 자유비행 중인 당구공은 다음 충돌 전까지 등속직선운동이라 중간을 볼 이유가 없다. 그래서 계산량이 모의 시간 길이가 아니라 사건 개수에만 비례한다. 사건이 드문 계에서는 고정 스텝 대비 몇 자릿수의 이득이 나오고, 덤으로 사건 시각이 격자에 반올림되지 않아 정확해진다. 수치해석에서 “빠른데 정확하기까지 하다”는 조합은 흔치 않은데, 여기에는 조건이 붙는다 — 다음 사건 시각을 풀 수 있어야 한다.

2. 시간 구동과의 비교[편집]

항목	시간 구동(클록)	이벤트 구동
전진	고정 $\Delta t$	다음 사건 시각으로 점프
비용	모의 시간 / $\Delta t$	사건 개수 × $\log$(대기 사건 수)
사건 시각 오차	$O(\Delta t)$, 항상 늦는 쪽 편향	원리상 없음(해를 풀 수 있을 때)
유휴 구간	그대로 다 계산	공짜로 건너뜀
구현 난이도	낮음	큐 관리·동시성 처리 필요
동시 다발 상호작용	자연스러움	사건 폭발로 불리
벡터화·GPU	쉬움	어려움(분기와 포인터 추적)

마지막 두 줄이 실무에서 판을 가르는 경우가 많다. 사건이 조밀하면 이벤트 구동은 큐 유지비만 내고 이득을 못 보며, 최신 하드웨어에서는 “쓸모없는 계산을 많이 하지만 벡터화되는” 쪽이 이기기도 한다. 이벤트 구동은 희소한 계의 기법이다.¹

3. 미래사건목록[편집]

엔진의 심장은 미래사건목록(future event list, FEL)이다. 예정된 사건들을 시각 순으로 들고 있다가 가장 이른 것을 꺼내 준다. 주 루프는 정말로 이게 전부다.

clock ← 0
while FEL 이 비지 않았고 clock < T_end:
    e ← FEL.pop_min()          # 가장 이른 사건
    clock ← e.time             # 시계를 그 시각으로 점프
    새 사건들 ← handle(e)       # 상태 갱신 + 후속 사건 생성
    FEL.push(새 사건들)
    무효화된 사건 처리          # 취소하거나 꺼낼 때 걸러낸다

필요한 연산은 삽입과 최소 원소 추출 둘뿐이므로 우선순위 큐가 그대로 들어간다.²

• 이진 힙 — 두 연산 모두 $O(\log n)$. 무난한 기본값이고, 대부분의 경우 여기서 끝내도 된다.
• 캘린더 큐(Brown, 1988) — 시간축을 폭이 일정한 버킷으로 쪼개 달력처럼 쓴다. 사건 시각 분포가 버킷에 고르게 퍼지면 상각 $O(1)$ 이 나오지만, 분포가 치우치면 한 버킷에 몰려 선형 탐색으로 퇴화한다. 그래서 버킷 폭을 주기적으로 재조정하는 코드가 붙는다.
• 사다리 큐(ladder queue) — 캘린더 큐의 퇴화를 막으려고 버킷을 계층적으로 다시 쪼갠다. 대규모 병렬 DES 엔진에서 널리 쓰인다.

FEL 관리에서 초보자가 반드시 밟는 지뢰가 무효화된 사건이다. 예약해 둔 사건이 그 사이의 다른 사건 때문에 더 이상 일어나지 않게 되는 상황 — 당구공 A가 B와 부딪히기로 예약돼 있었는데 그 전에 C가 A를 쳐 버리는 경우가 전형이다. 큐에서 임의 원소를 지우는 것은 비싸므로, 실무에서는 객체마다 충돌 카운터를 두고 사건에 생성 시점의 카운터 값을 박아 둔 뒤, 꺼낼 때 값이 다르면 조용히 버리는 지연 삭제(lazy deletion)를 쓴다.

두 번째 지뢰는 동시 사건이다. 같은 시각에 여러 사건이 걸리면 처리 순서에 따라 결과가 달라질 수 있는데, 부동소수점 시각은 정확히 같기가 오히려 어려워서 이 버그는 재현이 안 되는 형태로 나타난다. 대책은 시각과 함께 결정론적 타이브레이커(사건 종류 우선순위, 삽입 일련번호)를 키에 넣어 순서를 전순서로 만드는 것이다.

세 번째는 제논 거동(Zeno behavior)이다. 유한한 모의 시간 안에 무한히 많은 사건이 몰리는 상황으로, 튀는 높이가 등비수열로 줄어드는 공이 바닥에 정착하는 순간이 교과서 예다. 시뮬레이터는 그 시각에 영원히 도달하지 못하고 멈춘 것처럼 보인다. 실무 대책은 물리적이지 않고 공학적이다 — 상대속도가 임계값 아래면 접촉 상태로 강제 전이시킨다.

4. 어디서 쓰이나[편집]

4.1. 큐잉망과 시스템 성능[편집]

DES의 고향이다. 도착·서비스 시작·서비스 종료·이탈 네 종류의 사건만으로 은행 창구, 공장 라인, 패킷 스위치, 병원 응급실을 모형화한다. 해석적으로 풀리는 것은 M/M/1 같은 극히 단순한 경우뿐이고, 우선순위·재작업·유한 버퍼가 하나만 들어가도 시뮬레이션 외에는 답이 없다. 출력은 늘 표본이므로 결과는 반드시 신뢰구간과 함께 보고해야 하며, 초기 과도 구간(warm-up)을 잘라내는 것과 반복 실행의 독립성을 확보하는 것이 몬테카를로 방법의 통계 요령 그대로 요구된다.

4.2. 정확한 스파이크 시각[편집]

적분-발화 모형 문서에서 본 문제가 여기 그대로 연결된다. LIF 뉴런은 역치 아래 동역학이 선형이라 다음 입력까지의 궤적이 닫힌 형태로 나오고, 지수형 시냅스까지는 다음 역치 교차 시각을 뉴턴 반복 몇 번으로 정확히 구할 수 있다. 그러면 스파이크 시각이 $\Delta t$ 격자에 반올림되지 않는다.

이게 왜 중요하냐면, 클록 구동에서 스파이크 시각 오차 $O(\Delta t)$ 는 내부 ODE 적분기의 차수와 무관하게 망 전체를 1차로 주저앉히기 때문이다. RK4를 넣어도 소용없다. 게다가 그 시각 오차가 다음 뉴런의 입력 시각 오차로 전파되어, 스파이킹 신경망의 동기화나 진동 같은 집단 현상을 정성적으로 왜곡하기도 한다. 한계도 분명하다. EIF·AdEx처럼 역치 아래가 비선형이면 다음 교차 시각을 못 푸므로, 실무 시뮬레이터는 대개 하이브리드로 간다 — 고정 스텝으로 밀되 교차가 검출된 스텝에서만 시각을 보간해 정확한 리셋을 걸고, 그 스텝 안의 스파이크들을 시간 순으로 처리한다.

4.3. 강체 충돌과 경성구 분자동역학[편집]

물리 엔진의 충돌 감지는 두 갈래로 갈린다. 게임에서 흔한 이산 검사는 매 프레임 겹침을 확인하는 시간 구동 방식이고, 빠른 물체가 얇은 벽을 한 프레임 만에 통과하는 터널링을 낸다. 반대쪽이 연속 충돌 검사(CCD)로, 프레임 구간 안에서 접촉이 처음 성립하는 시각 $t^\ast \in [t, t+\Delta t]$ 를 풀어서 그 시각으로 점프한다. 볼록체 사이의 거리가 0이 되는 시각을 보수적 전진(conservative advancement)으로 좁혀 가는 것이 표준 구현이며, 형태는 위의 FEL 루프와 정확히 같다.

이 방식이 가장 순수하게 성립하는 곳은 경성구 분자동역학이다. 딱딱한 구는 충돌 순간을 빼면 등속직선운동이므로 다음 충돌 시각이 2차방정식 하나로 정확히 나오고, 적분오차라는 개념 자체가 사라진다. 앨더와 웨인라이트가 1950년대에 이 방식으로 경성구계의 고체-액체 상전이를 발견한 것이 컴퓨터 시뮬레이션 역사의 이정표다.³ 그런데 바로 이 예가 방법의 한계도 보여 준다. 퍼텐셜이 레너드-존스 퍼텐셜처럼 매끄러워지는 순간 “모든 입자가 항상 모든 입자와 상호작용 중”이 되어 사건 개념이 무너지고, 일반적인 분자동역학은 시간 구동으로 돌아간다. 마찬가지로 이산요소법에서도 조밀한 다접촉 더미는 이벤트 구동이 불리하다.

4.4. 확률적 화학반응[편집]

반응속도론을 분자 수가 적은 계에서 풀 때 쓰는 확률적 시뮬레이션 알고리즘(SSA, 길레스피 1976·1977) 역시 이벤트 구동이다. 다음 반응이 일어날 때까지의 대기시간을 지수분포에서 뽑고 어느 반응인지 고르는 직접법이 원형이고, 각 반응 채널마다 다음 발생 시각을 우선순위 큐에 넣어 두는 깁슨-브룩의 다음-반응법(2000)이 개량판이다. 반응 채널이 많을 때 이득이 크며, 의존성 그래프를 써서 실제로 성향(propensity)이 바뀐 채널만 갱신하고 나머지 예약 시각은 재사용한다. 큐가 있으면 시간을 아낀다는 DES의 논리가 화학에서 그대로 반복된 사례다.

5. 병렬 이산사건 — 인과성이라는 벽[편집]

문제를 여러 프로세스(논리 프로세스, LP)에 나누고 나면 즉시 벽에 부딪힌다. 각 LP가 자기 시계를 자기 속도로 밀면, 이미 시각 100까지 처리한 LP에게 시각 50짜리 메시지가 뒤늦게 도착할 수 있다. 이것이 인과성 위반이고, 시각 순서를 어긴 사건을 뒤늦은 사건(straggler)이라 부른다. 병렬 컴퓨팅 일반의 동기화 문제와 달리 여기서는 시간 자체가 공유 자원이라는 점이 고약하다.

보수적 동기화(찬디-미스라-브라이언트)는 인과성 위반을 아예 허용하지 않는다. LP는 “이 시각 이전에 도착할 메시지가 더 없음”이 보장될 때만 전진한다. 채널마다 도착 시각의 하한을 추적해야 하고, 아무것도 보낼 게 없어도 “적어도 시각 $T$ 까지는 안 보낸다”는 널 메시지를 흘려 교착을 막는다. 성능을 좌우하는 것은 선견(lookahead) — 각 LP가 “앞으로 최소 이만큼은 조용하다”고 약속할 수 있는 시간 폭이다. 선견이 크면 잘 확장되고, 0에 가까우면 널 메시지 폭풍만 남는다. 신경망 시뮬레이션에서 축삭 전도 지연의 최솟값이 그대로 선견이 되어 놀랍도록 잘 확장되는 것이 좋은 예다.

낙관적 동기화(제퍼슨의 타임 워프, 1985)는 정반대로 간다. 일단 전진하고, 뒤늦은 사건이 오면 되감는다. 필요한 장치는 셋이다. 상태 저장(주기적 체크포인트), 잘못 보낸 메시지를 취소하는 반메시지(anti-message), 그리고 아무도 그보다 앞으로 되감을 수 없는 하한선인 전역 가상 시각(GVT). GVT 아래의 저장 상태와 로그는 회수(fossil collection)해 메모리를 되찾는다. 선견이 없어도 병렬성이 나오는 대신, 롤백이 롤백을 부르는 연쇄가 터지면 성능이 폭락하고 메모리도 먹는다.

항목	보수적	낙관적
인과성 위반	금지	허용 후 롤백
필수 조건	충분한 선견	상태 저장 여력
오버헤드	널 메시지, 대기	체크포인트, 반메시지, GVT 계산
최악의 경우	직렬화	롤백 연쇄, 메모리 고갈
궁합	지연이 물리적으로 보장된 계	상호작용이 드물고 불규칙한 계

실제 대규모 엔진은 둘을 섞고, 롤백 거리에 제한을 두는 등 완충 장치를 얹는다. 부하 분산도 여전히 필요한데, 여기서 균형을 맞춰야 하는 것은 계산량이 아니라 사건 밀도라는 점이 보통의 영역 분할과 다르다.

6. 실무 체크리스트[편집]

• 먼저 물어라 — 다음 사건 시각을 풀 수 있는가? 못 풀면 이벤트 구동은 후보가 아니다. 부등식 근을 반복법으로 좁히는 비용이 고정 스텝보다 싸야 한다는 조건도 함께 본다.
• 사건 밀도를 재라. 사건이 조밀하면 큐 유지비만 내고 진다. 대략의 손익분기는 “고정 스텝 한 스텝당 사건이 하나 이상 나느냐”다.
• 큐 키에 타이브레이커를 넣어라. (시각, 사건종류우선순위, 일련번호) 삼중키가 국룰이다. 이걸 안 하면 재현되지 않는 버그로 몇 주를 태운다.
• 무효화는 지연 삭제로. 큐에서 지우지 말고 스탬프를 검사해 버려라.
• 제논 방어선을 깔아라. 사건 간격 하한, 접촉 상태 강제 전이, 그리고 무한 루프 감지.
• 재현성을 위해 난수 스트림을 사건 종류별로 분리해라. 하나의 스트림을 공유하면 사건 순서가 조금만 달라져도 궤적 전체가 갈라진다.

7. 관련 문서[편집]

• 적분-발화 모형 · 스파이킹 신경망 · 계산 신경과학
• 물리 엔진 · 충돌 감지 · 강체 동역학
• 분자동역학 · 이산요소법 · 반응속도론
• 몬테카를로 방법 · 셀룰러 오토마타
• 병렬 컴퓨팅 · 부하 분산 · MPI
• 큐잉 이론 · 우선순위 큐 · 확률적 시뮬레이션 알고리즘
• 실시간 시뮬레이션 · 하드웨어 인 더 루프

8. Footnotes[편집]

1. “이벤트 구동이 항상 빠르다”는 오해는 은근히 오래간다. 반례를 하나 들면, 조밀한 알갱이 더미의 이산요소법 해석에서 접촉은 사실상 항상 유지되므로 사건이 무한히 쏟아진다. 이때는 접촉을 스프링-댐퍼로 두고 고정 스텝으로 미는 쪽이 몇 자릿수 빠르다. 도구를 고르는 기준은 우아함이 아니라 사건 밀도다. ↩

2. DES 교과서가 말하는 세 가지 세계관(event scheduling / activity scanning / process interaction)은 결국 “같은 루프를 어떤 문법으로 적을 것인가”의 문제다. 코루틴이 흔해진 요즘은 프로세스 상호작용 관점(yield hold(3.0) 식으로 서술)이 압도적으로 읽기 좋은데, 밑에서 도는 것은 여전히 위의 FEL 루프 하나다. ↩

3. 앨더와 웨인라이트의 경성구 계산(1957)은 “입자에 인력이 전혀 없어도 결정화가 일어난다”는, 당시로서는 믿기 힘든 결과를 냈다. 순수하게 엔트로피가 만든 상전이였고, 시뮬레이션이 이론적 직관을 뒤집은 초기 사례로 늘 인용된다. 그리고 그 계산이 이벤트 구동이었던 이유는 우아함이 아니라 궁핍이었다 — 그 시절 컴퓨터로 고정 스텝을 밟았다면 계산이 끝나지 않았다. ↩