离散事件仿真的CPU缓存加速算法  

The CPU Cache Speedup Algorithm for Discrete Event Simulation

作　　者：王文鼐[1] 林川[1] 孙虎[1] 高同[2] 孙知信[2] 李刚[3] 董继雄[3] 

机构地区：[1]南京邮电大学通信与信息工程学院,江苏南京210003 [2]南京邮电大学计算机学院,江苏南京210046 [3]华为技术有限公司,广东深圳610041

出　　处：《南京邮电大学学报（自然科学版）》2011年第3期1-5,13,共6页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：江苏省"青蓝工程"资助项目

摘　　要：针对大规模离散事件仿真的应用需求,提出了CPU(中央处理器)缓存加速算法。采用空间局域化的环型链表存储事件摘要,兼具离散事件仿真(DES)事件分类和缓存加速作用。算法性能分析显示,入队时间复杂度为O(sqrt(n)),出队复杂度为O(1),优于目前主流的日历调度算法及改进算法。100节点9 900并发业务的网络仿真实验结果证实,相比于线性链表算法,文中提出的算法可使DES计算加速21倍。In this paper,a speedup algorithm for discrete event simulation is proposed by using CPU cache mechanism for simulating large scale networks.A space localized ring-typed queue is carefully designed to store digests,which are used for DES events portioning and CPU caching.The analysis of time complexity of the proposed algorithm shows that the en-queuing is O（sqrt（n）） and de-queuing is about O（1）,indicating a better performance than the traditional calendar queue algorithms.Experiments for a network with 100 nodes and 9 900 concurrent demands result in about 21 time speedup for the algorithm,compared with a simple linear queuing list.

关 键 词：离散事件仿真 事件调度 CPU缓存加速 算法设计 

分 类 号：TN915[电子电信—通信与信息系统]