이산-사건 시뮬레이션에서 사건 큐 처리시간의 영향

Abstract

이산-사건 시뮬레이션은 사건 큐에서 발생시간이 가장 먼저인 사건을 순서대로 인출하여 사건을 수행한다. 사건 큐에 사건을 삽입하고 삭제할 때에는 사건의 발생시간 순서대로 사건 큐를 관리하는 시간이 필요하며, 그 처리시간은 사건 큐의 평균길이에 비례한다. 특히 작업부하의 크기가 커질수록 사건 큐의 평균길이가 길어지는 이산-사건 시뮬레이션의 경우에는 사건 큐의 처리시간이 전체 시뮬레이션 시간에 영향을 주는 주요한 요인이 된다. 그러나 대부분의 이산-사건 시뮬레이션을 다루는 연구들은 작업부하의 설정이나 사건 자체의 특성을 중심으로 진행되었으며, 사건 큐의 처리시간은 중요하게 여기지 않았다. 따라서 본 연구는 사건 큐의 처리시간이 전체 시뮬레이션 시간에 미치는 영향을 분석하고, 이 영향 때문에 병렬 이산-사건 시뮬레이션에서 superlinear 속도향상을 얻을 수 있다는 것을 보여준다. 한 사건의 시뮬레이션 시간에서 작업부하가 커질수록 사건의 동작을 처리하는 시간은 변함이 없지만, 사건 큐의 처리시간은 사건 큐의 길이가 길어지기 때문에 사건 큐를 관리하기 위하여 어떠한 알고리즘을 사용하더라도 길어진다. 이것은 병렬 이산-사건 시뮬레이션에서 사건 큐가 분할되어 사건 큐의 평균길이가 짧아지기 때문에 superlinear 속도향상을 얻을 수 있다는 것을 의미한다. 단순한 구조의 이산-사건 시뮬레이터를 구현하여 실험한 결과에 따르면, 작업부하가 커질수록 superlinear하게 증가한 시뮬레이션 시간이 병렬 시뮬레이션에서는 superlinear하게 감소하여 superlinear 속도향상을 얻을 수 있었다. 또한 사건의 발생시간 순서대로 정렬된 사건 큐에 새로운 사건이 삽입되고 사건 큐의 사건들 중에 발생시간이 가장 빠른 사건이 삭제되는 사건 큐의 특성 때문에, 사건 큐를 관리하기 위하여 구현한 알고리즘 중에서는 이진 탐색을 사용하는 연결리스트가 가장 적합하다는 것을 알 수 있었다.