이산사건 시뮬레이션에서의 효율적인 이벤트 리스트 관리를 위한 MList의 개선 방안

• 영문명: An Improved MList for Efficient Event List Management in Discrete Event Simulation
• 발행기관: 한국시뮬레이션학회
• 저자명: 김성곤(Seong-Gon Kim) 임동순(Dong-Soon Yim)
• 간행물 정보: 『한국시뮬레이션학회 논문지』제18권 제4호, 29~37쪽, 전체 9쪽
• 주제분류: 공학 > 기타공학
• 파일형태: PDF
• 발행일자: 2009.12.30

국문 초록

본 논문은 기존의 멀티 리스트 기반 엠리스트(MList)의 성능을 개선하기 위하여 동적 쉬프트 방식을 적용한 방법을 소개한다. 개선된 엠리스트는 일정한 수의 이벤트가 Tier 3에 쌓이게 되면 삭제 이벤트가 발생하지 않더라도 자동 쉬프트 작업을 통해 Tier 3에 저장된 이벤트들을 Tier 2의 새로운 칼렌다 큐로 이동시킨다. 즉, 기존에는 Tier 2에 하나의 칼렌다 큐가 있었으나, 개선된 방법에서는 다수의 칼렌다 큐가 동적으로 생성, 삭제된다. 이러한 동적 구조는 저장된 이벤트 수에 따라 적응력을 갖는 장점을 가져 성능측정 실험 결과 동적 쉬프트를 적용한 엠리스트는 기존의 엠리스트에 비해 20% 이상의 성능개선을 보였다.

영문 초록

This paper deals with the priority queues exploited for the management of future event list in discrete event simulation. Among several implementations of priority queues, MList which consists of 3 tiers has been known to reveal the good performance. To improve the performance of MList, Dynamic-Shift MList (DSMList) is proposed in this paper. Whenever the number of events in tier 3 exceeds a critical number, DSMList creates new calendar queue in tier 2, then moves events from Tier 3 to the calendar queue. Instead of one calendar queue, therefore, a number of calendar queues are dynamically created in tier 2. Throughout experiments for the performance evaluation of DSMList, i t shows that at least 20% improvement is obtained compared with MList.

목차

1. 서론

2. 칼렌다 큐와 엠리스트

3. 동적 쉬프트 엠리스트(DSMList)

4. 성능 실험 및 분석

5. 결 론

참고문헌

키워드

사건 리스트 관리 우선순위 큐 이산사건 시뮬레이션 Event list management Priority queue Discrete event simulation