唐丈杰等：面向多核的并行离散事件仿真服务优化 １３７７ 建模与仿真是设计和研究复杂系统的重要工具ｐ］．随着仿真应用在规模上不断扩展、粒度上不断细化和模 型复杂度不断提高，使得仿真很难在单机平台完成．并行与分布式仿真是解决这一问题的唯一手段［４，５】．作为支 撑仿真运行的基础平台，现有的并行仿真内核可运行在多核处理器上，但其设计基础是以单核处理器为构件的 紧耦合巨型机或松耦合机群．这种将多核处理器完全等同于多个处理器的方式忽略了多核体系结构的独有特 点，难以合理利用和分配多核资源以获得最佳性能． 针对这一问题，课题组初步实现了一个基于逻辑进程范型的多线程层次化并行仿真模型【６】，但其运行细粒 度仿真应用时存在可扩展性弱、加速比低等问题．本文的主要贡献在于，针对多核处理器和并行仿真应用特点， 基于ＨＰＳＫ模型对时间管理和事件管理服务进行优化：（１）基于混合时间推进模式，提出ＥＥＴＳ计算协议，可根据 仿真应用特点灵活配置为异步ＥＥＴＳ算法以支持高效的全局同步；（２）基于并行仿真事件交互的特点，提出无锁 创建、异步提交和指针通信的事件管理算法，最小化线程之间的锁开销和减少了内存的消耗． 本文第１节介绍相关研究工作．第２节介绍并行离散事件仿真及逻辑进程范型的形式化定义，提出面向多 核的层次化仿真内核模型及相关的仿真服务．第３节针对时间管理和事件管理两种服务，分别提出相应的优化 方法．第４节是实验与分析．第５节对本文工作进行总结和展望． １相关研究工作 物理系统可以视为一组物理进程及其之间的交互．在离散事件仿真中，通常使用一个逻辑进程（１ｏｇｉｃａｌ ｐｒｏｃｅｓｓ，简称ＬＰ）来模拟一个物理进程，而物理进程之间的交互则通过在对应逻辑进程之间交换带时戳的事件 来表示．每个ＬＰ的任务就是按照时戳序进行执行事件，事件的执行会改变ＬＰ的某些状态并产生一些新的事件． 并行离散事件仿真通过将多个ＬＰ分布到不同的计算节点（或进程）并行推进以减少执行时间，使得研究更大规 模更细粒度的复杂系统成为可能．并行离散事件仿真通常也被称为并行仿真． 如何构建高效的并行仿真平台一直是过去２０年仿真领域的研究热点．由于多核出现的时间尚短，大部分并 行仿真平台在设计的时候没有考虑多核特性．例如：美国喷气推进实验室开发的ＳＰＥＥＤＥＳ［ 、乔治亚理工学院 的ＧＴＷ［ ，ＲＯＳＳ Ｅ ，ＰＡＲＳＥＣ［ 和ｍｕｓｉｋ［ 。 等等；国防科学技术大学计算机学院研究的ＹＨ．ＳＵＰＥ［ ”，这些并行仿 真平台可以运行在多核处理器上，但其设计的目标平台是ＳＭＰ和集群，大都是以多进程架构实现并行（ＧＴＷ的 ＳＵＮ版本基于多线程架构，但仅支持ＳＭＰ）．通过将仿真系统的多个逻辑进程分配到各个进程以降低执行时间， 进程之间通过共享内存，ＭＰＩ或ＴＣＰ等方式进行消息通信．这种处理方式将多核处理器等同于多个处理器，忽略 了多核的独有特点，存在较大的同步和通信开销．另外，多核化作为一种发展趋势，还必须以可扩展的眼光重新 审视软件设计模型．相比于多进程模型，多线程模型具有如下优势： （１） 在并行离散事件仿真中，逻辑进程之间存在大量消息交互，涉及事件的发送、撤销和回滚．同一进程内 部的线程共享地址空间，可以基于指针完成事件交互，通信效率比进程之间通信更高； （２） 随着处理器核数的增多，每个处理核心拥有的内存相对减少．当事件需要在两个进程间传递时，每个 进程都要在内存中为事件分配空间，而多线程方式则避免了这种额外的内存开销．就事件的储存而 言，多进程模型的内存消耗量至少是多线程模型的２倍； （３） 负载平衡是影响并行程序的关键因素，而实现高效的负载平衡要求仿真平台提供低开销的任务迁移 机制．在并行离散事件仿真中，迁移的基本单位是逻辑进程，涉及到状态变量、事件队列等诸多对象． 在多个进程之间迁移这些对象的开销较大，而线程之间能够通过共享地址空间，以很小的开销实现 迁移． 当然，相比于多进程模型，多线程模型需要更多的逻辑控制来保证程序的正确性，而且过多的锁操作会严重 影响程序的性能．必须针对并行离散事件仿真的特点，充分利用多线程架构带来的好处，尽可能消除锁开销，以 构建高效能的多线程并行离散事件仿真平台． 近年来，也出现了一些针对多核的工作，如苏年乐等人【 】的工作，通过将并行仿真的思想引入桌面平台以 利用多核处理器获得仿真加速．但他们同样采用多进程模型，与传统并行仿真平台没有太大区别．本课题组的陈 ，１３７８ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．６，Ｊｕｎｅ ２０１３ 莉丽等人『ｌ ］提出了一种基于分布式队列的全局调度机制，从负载平衡的角度来提高多核处理器上的仿真平台 性能．但为实现高负载均衡能力可能导致逻辑进程的频繁迁移，产生大量的Ｃａｃｈｅ失效．Ｗａ￣ＩＶＩｉ ４Ｊ的 ＨｙｐｅｒＷａｒｐＳｐｅｅｄ技术利用多核并发处理事件分支，加速Ｍｏｎｔｅ Ｃａｒｌｏ多样本仿真．但优化的效果与应用紧密相 关，不适合通用仿真支撑环境．一个更相关的工作是由Ｍｉｌｌｅｒ［ ］完成的一一ｗＡＲＰＥＤ【１ ６＿的线程化版本． ＴｈｒｅａｄＷａｒｐｅｄ采用Ｍａｓｔｅｒ—Ｗｏｒｋｅｒ模式，一个管理线程负责分配事件到多个工作线程，通过并行处理多个事件获 得加速比．为确保时序关系的正确性，工作线程需要在每轮事件执行后进行同步．如果事件粒度不均匀，总存在 处理核心空闲．而本文工作采用对称的结构，每个处理核心都要进行逻辑进程调度、事件处理等工作，并且只进 行必要的非阻塞协同． 综上所述，针对多核的并行仿真平台研究还处于探索阶段．考虑到并行仿真平台作为一种基础平台，在发掘 底层硬件特性时，需向上支持仿真应用的开发与运行．而且经过多年发展，并行仿真领域也形成了一些成熟的技 术．因此，支持原有的仿真应用开发方式和最大可能继承原有技术十分必要．基于传统的逻辑进程范型，针对多 核进行仿真服务优化研究是一种比较合适的选择． ２面向多核的并行离散事件仿真服务 ２．１并行离散事件仿真及ＬＰ范型的形式化定义 并行离散事件仿真的核心问题是如何确保所有ＬＰ按照时戳顺序来处理事件．目前主要有两类时间管理协 议解决这一问题：保守协议和乐观协议．在保守协议下，只有在确保不会违反时戳序的条件下，事件才能被执行． 对于那些具有良好并行性的仿真应用，保守协议能够很好地工作．但是保守协议过于严格，限制了某些并不会违 反时戳序的事件执行，造成处理器的空闲等待从而影响效率；乐观协议则放松了执行限制，ＬＰ按当前可见的时 戳顺序执行事件．当时戳乱序确实发生后，通过回滚等方法来修复错误．相比于保守协议，乐观协议更能发掘仿 真应用潜在的并行性，但如果回滚开销过大，也会影响性能甚至得不偿失．为方便描述，下面分别给出仿真时间、 仿真事件（消息）和ＬＰ范型的形式化定义． 定义１（仿真时间）．仿真时间 定义在 ×Ｎ上，即ｔ＝（ｆ，ｃ），ｆ∈ ，ｃ∈Ｎ．对ｒ定义两种关系，＜和＝，分别为： １） （Ｚ＂１，ｃ０＜（ｒ２，ｅｇ＜＝＞（ｒｌ＜ｒｚ）ｖ（ｒｌ Ｉ＇２ＡＣＩ＜Ｃ２）； ２） （『１，ｃａ）＝（ｒ２，０２）§（『１＝ｒｇＡ（Ｃｌ＝ｃ２）． 仿真时间是仿真的基本概念，用于区分事件的先后顺序，其直观理解是：第１位对应物理系统的物理时间，第 ２位用于区分同一物理时间下具有因果关系的事件．若没有特别指出，本文中时戳就是指仿真时间． 定义２（仿真事件）．ＬＰ执行任务的基本单元．ＬＰ之间进行事件传递时被称为发消息，下文中不加区分地使用 消息和事件． ・ （Ｐ）：事件的时戳，即事件执行的仿真时间； ・ｓｉｇｎ（ｅ）：表示事件的正负，反事件是在ＬＰ回滚时产生的、用于取消因错误执行所产生的事件． 定义３（逻辑进程）．逻辑进程（１ｏｇｉｃａｌ ｐｒｏｃｅｓｓ，简称ＬＰ）定义为七元组结构ＬＰ－＝（ｓｆ，ｒ，ＰＥ ，ＦＥＬ，ＡｎｔｉＥ，ｓｅｑ）： ・ＦＥＬ：按时戳升序排列的事件链表，用于记录未处理事件； ・ＰＥＬ：按时戳升序排列的事件链表，用于记录已处理事件； ・ＡｎｔｉＥ：用于缓存先于正消息到达的反消息； ・ｓ￣Ｓ：ＬＰ的当前状态，ｔｓ（ｓ）表示该状态的仿真时间； ・ｓｅｑ￣ＳＥＱ：按时戳升序排列的检查点序列，用于记录ＬＰ在各个历史时间点的状态和发送的事件集合，乐 观ＬＰ可利用检查点序列恢复到最近的正确状态；对于每个检查点ｓｅ＝（ｓ，Ｏ）￣ｓｅｑ， ∈ ， ２ ； ・ｆ．ＳｘＥ－＞Ｓｘ２ ：事件处理函数，修改ＬＰ的状态，并产生一组新的事件（也可以产生０个事件）； ．，： Ｅ×ＳＥＱ－－＊Ｓ×２ｅｘＳＥＱ：回滚处理函数，将ＬＰ的状态恢复到输入事件的时戳之前，并把所有错序执行事 件对应的反事件发送出去． 唐文杰等：面向多核的并行离散事件仿真服务优化 １３７９ 图１描述了ＬＰ执行的处理流程，每次从ＦＥＬ中取出下一事件，根据事件类型和时戳来进行相应的处理．由 于保守ＬＰ不会遇到落伍消息和反消息，不需要对历史状态进行保存，仅仅执行第４行、第５行．需要说明的是， 如果ＡｎｔｉＥ不为空，每个发送到ＬＰ的消息都必须同ＡｎｔｉＥ中的反事件进行匹配：如果匹配成功，互相抵消；若不成 功，则加入ＬＰ的ＦＥＬ中．从算法可以看出，为保证ＬＰ的顺利执行，还需要底层提供一些基础服务，如ｓｅｎ ）发送 消息、全局同步等等． ＬＰ从ＦＥＬ中取出下一事件ｅ ， ｉｆ ｓｉｇｎ（ｅ “ｆ）＝１，ｔｈｅｎ ｉｆ ｔｓ（ｅ ｆ）＞ 。ｗ），ｔｈｅｎ （ Ｈ“ｆ， ，）：： ｎｏｗ，ｅ ｆ） Ｓｎｏｗ： “，，ｓｅｎｄ（Ｅ，￣ｅｘｔ） ｅｇ：＝ ｅｇ＋｛（ ， ｝，Ｐ—Ｅ ：＝Ｐ 三＋｛Ｐ ，） ｅ】ｓｅ ¨ ＂ 加 ／／正事件且非落伍 ／／落伍的正事件 ０６㈣ｋ Ｅａ ｉ，ｓｅｑｂ ｃ ：＝ｒ（ｓｎｏｗ，ｅ？ｌｅｘｔ￣ｓｅｑ ） Ｓｎｏｗ：＝ ６ ｃｋ，ｓｅｎ Ｅａｎｆ０ ｓｅｑ ：＝ 叼６。。 ，ＰＥＬ：：ＰＥＬ—Ｅ（ｔｓ（ｅ）＞ｔｓ（ｅ “ｆ）） ｅｎｄｉｆ ｅｌｓｅ ｉｆ ｅ—ｎｅｘｔ∈ＰＥＬ ，／反事件，对应正事件已被执行 ＥＩ ，ｉ，ｓｅｑｂｄｃｔ）： ， ，ｓｅｑ ） Ｓｎｏｗ： ６口ｃｋ，ｓｅｎ ） ｓｅｑ ：＝ ｅｇ６ ｋ ＰＥＬ： ＰＥＬ—Ｅ（ｔｓ（ｅ）＞ｔｓ（ｅ “ｆ）） ｃ ，ｅｌｓｅ ／／反事件，对应正事件未被执行 ＡｎｔｉＥ：＝ＡｎｔｉＥ＋ｔｅ ＾ ｅｎｄｉｆ ｅｎｄｉｆ Ｆｉｇ．１ Ｐｒｏｃｅｄｕｒｅ ｏｆ ＬＰ’Ｓ ｅｖｅｎｔ ｅｘｅｃｕｔｉｏｎ 图１ ＬＰ执行事件的处理流程 ２．２并行仿真服务和面向多核的并行仿真内核模型 并行仿真内核为ＬＰ提供一系列服务，以支持ＬＰ之问的通信和协同，从而确保整个并行仿真的正确和高效． 这些服务从下到上分为３类，包括基础服务、ＰＤＥＳ服务和优化扩展服务： （１） 基础服务：搭建并行系统的基本架构，支持一群实体（ＬＰ）进行消息交互，包括命名服务、事件管理服务； （２） 并行离散事件仿真服务：搭建并行离散事件仿真框架，包括时间管理服务、回滚服务等； （３） 优化扩展服务：针对应用特点提供性能优化，包括动态迁移服务、常用科学计算算法服务等． 为了充分利用多核ＣＰＵ资源，通常采用多线程方法分担计算负载，以优化软件性能．文献［１７】中提出了一种 层次化并行仿真内核模型（ｈｉｅｒａｒｃｈｉｃａｌ ｐａｒａｌｌｅｌ ｓｉｍｕｌａｔｉｏｎ ｋｅｒｎｅｌ，简称ＨＰＳＫ），该模型针对多核集群计算节点内 外交互能力的差异，采用多进程／多线程混合的平台架构．在计算节点之问、仿真内核之间以多进程方式通信与 协同：计算节点内部，则采用多线程方式优化通信，并透明地实现多核并行化，如图２所示．这样，从系统的角度 看，ＨＰＳＫ同现有仿真平台完全一样：而以单个节点的角度看，ＨＰＳＫ将多个仿真调度处理核心集成于一个进程 内，分为两层：第１层称为进程核（ＰｒｏｃｅｓｓＫｅｒｎｅ１），负责控制第２层所有的线程核（ＴｈｒｅａｄＫｅｒｎｅ１）的推进，包括产生、 初始化、启动、停止等功能．进程核启动后，不再占用任何计算资源，仅仅提供一些全局变量供同步使用．当所有 线程核执行结束后，ＣＰＵ执行权交还进程核，由其完成善后工作；第２层由一组线程核组成，每个线程核可视为一 个简化版的仿真内核，负责ＬＰ的调度、事件的执行与发送等．每个线程核与操作系统线程一一对应，最大值可设 定为ＣＰＵ的处理核数．为了支持节点间通信，一组通信逻辑进程（ｃｏｍｍｕｎｉｃａｔｉｏｎ ｌｏｇｉｃａｌ ｐｒｏｃｅｓｓ，简称ＣＬＰ）以代 理方式负责与对应节点的通信．ＣＬＰ之所以被称为逻辑进程，是因为可以将ＣＬＰ已发送事件列表和待发送事件 列表映射为ＬＰ的ＰＥＬ和ＦＥＬ，事件执行定义为发送到目标ＬＰ的事件．这样，ＣＬＰ被纳入到ＬＰ范型的框架内， 节点问消息发送还可以采用乐观或保守方式控制．这组ＣＬＰ被统一放置在０号线程核上，所有节点间消息被发 送到０号线程核转发，节点间通信从逻辑上转化为线程核问或核内通信． １３８０ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．６，Ｊｕｎｅ ２０１３ Ｆｉｇ．２ Ａｒｃｈｉｔｅｃｔｕｒｅ ｏｆ ｈｉｅｒａｒｃｈｉｃａｌ ｐａｒａｌｌｅｌ ｓｉｍｕｌａｔｉｏｎ ｋｅｒｎｅｌ ｍｏｄｅｌ 图２层次化仿真内核模型体系结构 ３面向多核的并行仿真服务优化 ３．１时间管理服务优化 时间管理是并行离散事件仿真的核心服务．在多核时代，处理器的并行度将持续增长，但每个处理核心所拥 有的内存可能减小．采用乐观与保守混合的时间管理协议，可综合利用乐观协议并行度高、保守协议所需内存 小的优点．因此，本文采用混合时间管理协议，参考Ｊｈａ等人提出的框架［ ，将时间管理服务分为全局控制机制和 局部控制机制两个部分．其中，局部控制机制负责ＬＰ调度，全局控制机制则负责全局时间同步． ＬＰ调度是指在ＬＰ之间合理地分配ＣＰＵ，以保证仿真快速正确地推进．每次循环开始时，线程核需要选择一 个ＬＰ，并为其设定可推进的时间范围，然后将ＣＰＵ执行权交与ＬＰ进行仿真推进．本文采用的调度算法同文献 ［１０】中类似．所不同的是，由于ＨＰＳＫ采用的异步消息发送方式（详见后文第３．２节），可能有消息存在于缓存区中， 需要清空缓存区中的消息．调度算法的可分为如下两个阶段： （１） 保守阶段：线程核中存在可推进的保守ＬＰ．从中选择下一事件具有最小时戳的保守ＬＰ，将其推进到设 定时限之后： （２） 乐观阶段：线程核中不存在可推进的保守ＬＰ选择下一事件具有最小时戳的乐观Ｌ 将其推进到设定 时限之后． 这种调度方式以ＬＰ为单位，通过最大化每次ＬＰ推进的范围，减少ＬＰ切换的次数，减小开销．需要说明的是， 调度算法中提到了两个设定时限，前者是当前保守ＬＰ可推进的时戳上限，与下文的全局时间同步紧密相关：而 后者可根据应用的具体情况设定，目前默认为线程核中其他ＬＰ的最小下一事件时戳． 全局时间同步的具体工作是计算所有逻辑进程的未来可能处理事件的最小时戳，这里记为（ＥＩＴ）．对于保守 ＬＰ来说，该值作为ＬＢＴＳ使用，定义了目前可安全执行（不会导致回滚）事件的时戳上限；而对于乐观ＬＰ而言，该 值作为ＧＶＴ使用，是提交事件，完成内存释放和Ｉ／Ｏ交互的时戳下限．计算ＥＩＴ时，可以选用已有ＬＢＴＳ栅栏算法 和ＧＶＴ算法［】９＿ 】．但是无论哪种算法，都需要参与仿真的进程提交其最小发送时戳（ＥＥＴＳ）．在多进程仿真内核 模型中，每个进程内部只有一个调度中心，确定ＥＥＴＳ十分简单．但ＨＰＳＫ中存在多个调度中心，如何在不干扰线 程核正常推进的前提下计算ＥＥＴＳ值相对复杂．从表面上看，通过移植基于共享内存模型的ＧＶＴ算’法【 】能够解 决这一问题．算法通过一个全局变量ＧＶＴＦｌａｇ来控制同步，由各个处理器异步地检测ＧＶＴＦｌａｇ状态并参与同步 唐文杰等：面向多核的并行离散事件仿真服务优化 １３８１ 值计算．但算法是面向纯粹乐观模式的，不支持混合时间推进模式；而且为了最优化仿真效率，通常要求在不同 时机发起全局时间同步计算，而单个全局变量难以满足不同的同步需求；第三，算法没有考虑到节点间通信对全 局同步值的影响．针对这些问题，本文提出了一种计算协议，可被灵活配置成ＥＥＴＳ算法，支持混合状态的线程核， 且能在不阻塞线程核正常推进的情况下计算ＥＥＴＳ，如图３所示． 变量定义 ｔＴＴＳｉ＝ｍｉｎ｛ｔｓ（ｅ）ｌｅ￣ＴＫＦＥＬ 或ｅ￣ＥＢ ，：线程核ｉ的线程时戳，用于记录当前线程核中事件时戳的最小值； ＴＫＦＥＬ是线程核上所有ＬＰ的ＦＥＬ集合，ＥＢ是缓存区（包括事件和反事件） ｔＯＥＴＳｉ：线程核ｉ的局部变量，用于记录所有发送到计算态线程核事件的时戳最小值 ｔＥＥＴＳ ：线程核ｉ的最早发送事件时戳 ＥＥ ：算法计算得到的进程核最早发送事件时戳 ＥＥＴＳ（ｗｔ）：墙钟时间为ｗｔ，通过系统快照得到的最早发送事件时戳（真实的ＥＥＴＳ） 线程核的计算协议 １．如果线程核ｉ需要计算ＥＥＴＳ，提交ｔＥＥＴＳ￣＝ｍｉｎ｛ｔ ，ｔＯＥＴＳｉ｝，更新ｔＯＥＴＳｉ＝ＳｉｍＴｉｍｅ：：ＭａｘＴｉｍｅ； ２．当线程核ｉ发送事件ｅ时，如果目标线程核，已经提交了ｔＥＥＴＳｉ且ｔｓ（ｅ）＜ｔＯＥＴＳｆ，则更新ｔＯＥＴＳｉ＝ｔｓ（ｅ）； 几 ３．最后一个提交ｔＥＥＴＳ￣的线程核ｉ负责计算ＥＥ ，ＥＥｚ ｍｉｎ｛ｔＥＥＴＳ ｝； ４．如果存在多个进程进行仿真，由０号线程核最后提交ｔＥＥＴＳｏ． Ｆｉｇ．３ Ｐｒｏｔｏｃｏｌ ｏｆ ＥＥＴＳ ｃｏｍｐｕｔａｔｉｏｎ ■ 口 口 图３ ＥＥＴＳ计算协议 只要保证进程中的所有线程核都提交了，ｔＥＥＴＳ就能得到可接受的ＥＥＴＳ值．协议为ＥＥＴＳ计算提供了一个 ●．．■ ；■ Ｉ 灵活的框架，使得各个线程核可以根据实时需求合理地选择参与ＥＥＴＳ计算的时机．假设线程核在墙钟时间 ｗｔ】～ｗｔ２之间依次提交ｔＥＥＴＳ，并由最后提交的线程核负责统计最终的进程ＥＥ 值，ＥＥ 与真实的ＥＥＴＳ的 关系可由定理１和定理２得出．线程核提交ｔＥＥＴＳ的墙钟时问构成一个截断，如图４所示．截断之前为预备状态， 截断之后为计算状态．因此，可以将事件的发送接收方状态分为４类：Ｅ】：预备到计算；Ｅ２：预备到预备；Ｅ３：计算到预 备； ：计算到计算． ＴｈｍａｄＫｅｍｅｌ３一 ￣ｅａｄＫｅｒｎｅｌ２ ＴｂａｍａｄＫｅｍｅＩ１．． ＴｈｒｅａｄＫｅｒｎｅｌ０一 Ｗａｌ１ Ｃｌｏｃｋ Ｆｉｇ．４ Ｆｏｕｒ ｔｙｐｅｓ ｏｆ ｅｖｅｎｔｓ 图４ ４种不同事件类型 定理１．如果所有线程核都参与了ＥＥＴＳ计算，而且在计算过程中没有收到来自其他进程的消息，那么，按基 本算法规则１～规则３计算得到的ＥＥＴＳ值，满足ＥＥＴＳ（ｗｔ１）≤雎 ＜￣ＥＥＴＳ（ｗｔｚ）． 证明： （１）首先证明ＥＥ ￣ＥＥＴＳ（＜ｗｔ２） 假设ｅ１∈Ｅ１是满足ｔｓ（ｅＯ＝ｍｉｎｆ｛ｔＯＥＴＳ￣）的事件 是满足ｆ瞬那么ＥＥ ＝ｍｉｎ｛ｔｓ（ｅ１），ｔＴｒｓｊ｝． ｍｉｎｆ｛ｆＴＴＳｉ）的线程核， （１．１）如果ｔｓ（ｅ１）＜￣ｔＴＴＳｊ，往证存在后，使得ｔｓ（ｅ１）￣ｔ＜ＴＴＳｋ（ｗｔ２）； 若不然，则存在ｅ２∈ ，满足ｔｓ（ｅ１）＞ （Ｐ２）． １３８２ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．６，Ｊｕｎｅ ２０１３ 可以分为两种情况分析： 情况Ｉ．ｅ２有一个祖先事件ｅ３ｅＥ１，ｔｓ（ｅ３）＜ （ ２）．根据ｅ１的定义，ｔｓ（ｅ１）≤ （ ３）．所以ｔｓ（ｅ１）≤ （ ２），与 ｔｓ（ｅ１）＞ （Ｐ２）矛盾； 情况Ｉ１．Ｐ２不存在属于Ｅ１的祖先事件口３，则必有一个祖先事件ｅ４，ｅ４∈ＴＫＦＥＬ７或ｅ４∈ＥＢ；ｇ．所以 ｔｓ（ｅ４）＜ｔｓ（ｅ２），根据ｔＴＴＳｋ的定义，有ｆ 有ｔｓ（ｅ１）≤ （Ｐ４）＜ （ ２），矛盾． 所以，如果ｔｓ（ｅ１）￣ｔＴＴＳｊ，存在七，满足ｔｓ（ｅ１）￣ｔＴＴＳｇ（ｗｔ２）； ≤ｆ ≤ （ ４）．那么根据情况（１．１）的假设， （１．２）如果ｔｓ（ｅ１）＞ｔｒｒｓｊ，往证存在 ，使得ｔＴＴＳｊ＜￣ｔＴＴＳｋ（ｗ ）． ・如果ｔＴＴＳｊ＜￣ｔＴＴＳｊ（ｗｔ２），结论显然成立； ・若ｔＴＴＳｊ＞ｔＴＴＳｙ（ｗｔ２），则存在事件ｅ５ｅＥｌｕ ，满足ｔｓ（ｅ５）￣ｔｒｒＳｊ，在线程核．，提交ｔＥＥＴＳｊ之后收到： 如果ｅ５ｅＥｌ，则ｔｓ（ｅ１）≤如（ ５）￣ｔＴＴＳｊ，和ｔｓ（ｅＩ）＞ｔＴＴＳｊ矛盾； 如果ｅ５∈目，同样可分为两种情况分析： 情况Ｉ．Ｐ５有一个祖先事件ｅ６ｅＥ１，ｔｓ（ｅ１）≤ （ ６）≤ （Ｐ５）＜￣ｔＴＴＳｊ，和ｔｓ（ｅ１）＞ｆ刀 矛盾； 情况ＩＩ．ｅ５不存在属于Ｅ１的祖先事件，则必有一个祖先事件ｅ７，ｅ７∈ＴＫＦＥｆｆｉｇ或ｅ７∈船 ， 所以ｔｓ（ｅ７）＜ｔｓ（ｅｓ）．根据ｆ刀 的定义，有ｔＴＴＳｊ＜￣ｔｓ（ｅ７）＜ （Ｐ５），和 （。５）＜￣ｔＴＴＳｙ矛盾． 因此，如果ｔｓ（ｅ１）＞ｆ Ｚ ，存在Ｊｊ｝，使得ｔＴＴＳｊ＜￣ｔＴＴＳｋ（ｗｔ２）． 综合情况（１．１）和情况（１．２） ＥＥ乃 ｍｉｎｉ｛ｔＥＥＴＳｉ｝＝ｍｉｎｆ｛ｍｉｎ｛ｔ刀 ，ｔＯＥＴＳｉ｝｝＜￣ｍｉｎｉ｛ｔＥＥＴＳｋ（ｗｔ２）｝￣ＥＥＴＳ（ｗｔ２）． （２）然后证明ＥＥＴＳ（ｗｔ１）≤朋 根据定义，显然有，对于任意ｉ，ＥＥＴＳ（ｗｔ１）＜￣ｔＴＴＳｆ． 取前文定义的 ｌ，如果产生ｅｌ的墙钟时间大于Ｗｔｌ，必有ＥＥＴＳ（ｗｔ１）＜ （Ｐ１）；如果产生ｅｌ的墙钟时间小于ｗｔ１， 但因为发送ｅ１的墙钟时间大于ｗｔ１，所以ｅｌ的父亲事件ｅ８在ｗｔｌ时正在执行（即未完成）． 所以，ＥＥＴＳ（ｗｔ１）￣ｔｓ（ｅｓ）＜ｔｓ（ｅ１）＝ｍｉｎｆ｛ｔＯＥＴＳｉ｝，有ＥＥＴＳ（ｗｔ１）≤皿 ． 综上所述，ＥＥＴＳ（ｗｔ１）≤雎 ￣ＥＥＴＳ（＜ｗｔ２）． 口 如果在计算ＥＥＴＳ的过程中收到了来自其他进程的远程消息，设 在这类事件中具有最小时戳，如果 （ｅ ＥＥＴＳ（ｗｔ１），那么定理１依然成立．而如果ｔｓ（ｅ＂）＜￣ＥＥＴＳ（ｗｔ１），则有： 定理２．如果所有线程核都参与了ＥＥＴＳ计算，且 （Ｐ ≤衄ｚ ｗｆ１），那么按基本算法规则１～规则４计算得 到的ＥＥＴＳ值，满足 （Ｐ，）≤ＥＥ ￣ＥＥＴＳ（ｗｔ２）． 证明：根据ｅ 的定义，又因为ｔｓ（ｅ＇）＜￣ＥＥＴＳ（ｗｔ１），显然有ｔｓ（ｅ ）≤船 的ＴＫＦＥＬ中．不妨设ｄｅｓｔ（ｅ ）＝，，那么： ・如果被转发，则ｅｒｅＥ】ｕ ： ・和ｔｓ（ｅ ）＜￣ＥＥＴＳ（ｗｔ２）． 按照计算协议４，由线程核０最后提交ｔＥＥＴＳ，此时墙钟为ｗｔ２．ｅ 或被相应的ＣＬＰ进行转发，或被缓存在ＣＬＰ 情况Ｉ．ｅｒｅＥｔ，根据规则２，有ＥＥＴＳ￣ｇ≤ ｒ），所以 （Ｐ 情况ＩＩ．ｅｒｅ ： 一ｇ，那么ｔｓ（ｅ＇）＝ＥＥｒＳ．ｇ￣ＥＥＴＳ（ｗｔｚ）； ・若ｅ 已执行，ｆ ≥ （Ｐ ，所以 ≤ＥＥ ｇ； 一若ｅ 未执行，ｔ刀 ＝ｔｓ（ｅ５，同样有 （Ｐ ≤船 ； 所以，ｔｓ（ｅ＇）＝ＥＥ ２＜￣ＥＥＴＳ（ｗｔ２）． ・如果缓存在ＴＫＦＥＬ中，按ｅ 定义，有ｔＴＴＳｏ＝ｔｓ（ｅ￣）． 所以，ｔｓ（ｅ＇）＝ＥＥ 综上所述， （Ｐ ≤Ｅ ＥＥＴＳ（ｗｔ２）． ￣ＥＥＴＳ（ｗｔ＜２）． 被限定在一个合理的范围内．考虑到ＥＥ 被用来计算 且 （Ｐ ≥ 口 规 根据定理１和定理２，皿 则４是充要的．计算协议定义了一个灵活的框架，用户可以根据仿真应用特点指定各个线程核参与ＥＥＴＳ计算， 唐文杰等：面向多核的并行离散事件仿真服务优化 １３８３ 以配置需要的全局同步算法，如图５所示．如果仿真应用乐观执行的风险较大，线程核可以在进入乐观模式后马 上提交ｔＥＥＴＳ；￣ｔｌ果仿真应用乐观执行的风险较小，则让线程核的乐观推进到一定时戳上限后提交ｔＥＥＴＳ．函数 ＮｅｅｄＵｐｄａｔｅＥＥＴＳＯ为用户提供了一个可配置的接口，用于判断线程核是否需要提交ｔＥＥＴＳ．但由于ＨＰＳＫ采用的 是以ＬＰ为单位的调度策略，两次调用ＮｅｅｄＵｐｄａｔｅＥＥＴＳＯ的间隔可能会很长，从而推迟ＥＥＴＳ计算并延缓 计 算．线程核发送事件后，当检测到目标线程核已提交后，便可立刻参与ＥＥＴＳ计算．但如果线程核长期不发送消息， 也就无法检测是否可以提交ｔＥＥＴＳ，这时就需要ＮｅｅｄＵｐｄａｔｅＥＥＴＳＯ来协助．两种检测机制相互配合，从不同粒度 上控制线程核参与ＥＥＴＳ计算，以实现高效的全局同步． 进程核变量（所有线程可见）： ｉｎｔＥＥＴＳｌａｇ；ｆ 标识是否正在进行ＥＥＴＳ计算 ／ ＳｉｍＴｉｍｅｔＥＥＴＳ［ＮＵＭ＿ＴＨＲＥＡＤ］； 线程核提交的ＥＥＴＳ ／ ＳｉｍＴｉｍｅ ＥＥＴＳ； 最终计算的ＥＥＴＳ＊／ 发送事件ｅ后，与ＥＥＴＳ计算相关的代码 ｉｆ（ＣｈｋＴａｒｇｅｔｔＥＥＴＳｌａｇ（）ｆ＝ｔｒｕｅ＆＆ｔＥＥＴＳｌａｇ＝ｆａｌｆｓｅ） ｔ０ＥＴＳ：＝ｍｉｎ（ｔＯＥＴＳ，ｔｓ（ｅ））； ｉｆ（ＴＫｍｏｄｅ＝ｔｒｕｅ＆＆ｉｍｍｅｄｉａｔｅ＝ｔｒｕｅ） ｔＥＥＴｓｘｔｈｒｅａｄ ｉｄ、：＝ｍｉｎ（ｔｏＥＴＳ，ｔＴＴＳ）； 线程核变量： ＳｉｅＴｉｒｍｅｔＯＥＴＳ； ＳｉｍＴｉｍｅｔＴＴＳ； ｂｏｏｌ ｔＥＥＴＳｌａｇ；ｆ 标识线程核是否正进行ＥＥＴＳ计算 ／ ／ 检查目标线程核的ｔＥＥＴＳｌａｇ是否为真 ／ｆ ／牛且线程核本身尚未提交ｔＥＥＴＳ计算＋／ 线程核已进入乐观模式且需要立刻更新ＥＥＴＳ・／ ｔＥＥＴＳｌａｇ：ｆ＝ｔｒｕｅ，ＥＥＴ ｎｇ： ＥＥＴ ｎｇ一１ ｅｎｄｉｆ ｅｎｄｉｆ 线程核推进主程序中的ＥＥＴＳ计算代码 ｗｈｉｌｅ（Ｓｉｍｕｌａｔｉｏｎ ｉｓ ｎｏｔ ｏｖｅｒ）ｄｏ ｉｆ（ＮｅｅｄＵｐｄａｔｅＥＥＴＳＯ＝ｔｒｕｅ） ，幸线程核判断是否需要发起ＥＩＴ计算 ／ ＥＥＴＳｌａｇ：ｆ＝ＥＥＴＳｆｌａｇ－１； ｔＥＥＴＳ［ｔｈｒｅａｄ ｉａ］：＝ｍｉｎ（ｔＯＥＴＳ，ｔＴＴＳ）； ｔＥＥＴＳｆｌａｇ：－ｔｒｕｅ； ｅｎｄｉｆ ｉｆ（ＥＥＴＳｌａｇ＝Ｏ）ｆ ／＋最后提交ｔＥＥＴＳ的线程核负责计算进程ＥＥＴＳ，并开始节点间规约算法 ／ ＥＥＴＳ：＝ｍｉｎ（ｔＥＥＴＳ［ＮＵＭ＿ＴＨＲＥＡＤ］）； ＥＥＴＳｆｌａｇ： ＮＵＭ ＴＨＲＥＡＤ； ｅｎｄｉｆ ｅｎｄｗｈｉｌｅ Ｆｉｇ．５ Ｐｓｅｕｄｏ ｃｏｄｅ ｏｆ ＥＥＴＳ ａｌｇｏｒｉｔｈｍ 图５ ＥＥＴＳ算法伪代码 ３．２事件管理服务优化 事件管理服务属于基础服务，主要为仿真系统提供事件创建、传递和提交等服务．在并行离散事件仿真中， ＬＰ之间通常存在大量的事件交互，且每个事件都要经历创建、传递和提交这一过程．事件管理服务是否高效， 对整个仿真平台的性能有重要影响． 事件创建和提交是一组对偶操作，分别对应于内存的ｎｅｗ和ｄｅｌｅｔｅ操作．虽然存在支持多线程应用的通用 内存分配器［ ，但由于ＨＰＳＫ独特的系统架构和应用特点，对事件分配回收机制进行针对性设计有助于获得最 佳性ｔｉ： ・通用内存分配器则需要复杂的机制来支持线程数目动态变化的应用．而在ＨＰＳＫ中，仿真运行后线程数 目保持固定： ・通用内存分配器希望同时最小化ｎｅｗ和ｄｅｌｅｔｅ的延迟．而在ＨＰＳＫ中，事件创建后需要尽快返回地址指 针，实时性要求高；而事件提交的实时性要求相对较低； ・相比于事件的数目，事件类型的数目很小： ・线程核内部和线程核之间的事件由不同的线程执行，通过物理上分隔内存可以减少ｃａｃｈｅ的假共享 冲突． ｌ３８４ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．６，Ｊｕｎｅ ２０１３ 针对这些特点，本文设计了一种具有线程局部性的双列多级栈结构的事件管理器，采用一种无锁创建、异 步提交的机制来解耦和线程之间的关系，以实现高效的事件服务．如图６所示，每个线程核预先分配两个私有的 事件管理堆，分别用于管理线程核内部和线程核之间两种类型事件．每个事件管理堆由若干个栈构成，每个事件 栈保存一组指向相同大小内存块的事件指针，内存块在物理上是连续的．事件的创建和回收都由源ＬＰ所在线程 核完成．当ＬＰ需要创建事件时，线程核首先检查事件的目的地，确定事件管理堆；然后根据事件的大小查找对应 的事件栈，弹出栈顶指针，获得事件．由于事件管理堆是线程局部的，这一过程是无锁的．当需要提交事件时，线程 核将事件发送到源ＬＰ所在线程核的事件回收站中，由线程核定时的从事件回收站中读取并将内存归还到原来 的事件管理堆中．这一过程可参照下文提到于事件的传递方式实现． 『１ Ｆｉｇ．６ Ｓｔｒｕｃｔｕｒｅ ｏｆ ｅｖｅｎｔ ａｌｌｏｃａｔｏｒ 图６事件分配器结构 ＨＰＳＫ中存在３种类型通信，线程核内部、线程核之间与进程之间．线程核内部通信十分简单，直接将消息 插入目标ＬＰ的未来事件队ＹｔＪ（ＦＥＬ）￣即可．进程之间通信等于两次线程核间通信加上一次网络通信，但多核处 理器不能改善网络通信．因此，本文主要针对线程核之间通信进行优化．由于进程内部的所有线程能够共享地址 空间，可以利用指针进行事件传递．这将显著地提高通信效率，并减少内存的消耗．然而在仿真执行过程中，各个 线程并行推进，同步通信会造成线程的互相干扰，从而极大地影响仿真效率．本文提出了一种事件缓存机制支持 基于指针的异步通信，并采用环式队列结构缓存事件，分离事件发送和接收操作，实现线程核之间的高速通信． 图７展示了两个线程核之间事件传递的整个过程．当线程核ｉ需要向线程核，发送事件，它不是直接将事件 插入目标ＬＰ的ＦＥＬ中，而是将事件指针存入事件缓存区中；同样，如果线程核ｉ向线程核，发送反事件，它将事 件指针缓存在反事件缓存区中．由于不存在网络通信延迟，事件必然先于反事件存入缓存区．线程核，在每次调 度循环开始时将两个缓存区的事件指针读入．正事件可直接插入目标ＬＰ的ＦＥＬ中；对于反事件，线程核，可根 据下面两种情况做出相应处理： （１）如果事件指针存在于目标ＬＰ的ＦＥＬ中，即事件已收到但未执行，直接从ＦＥＬ中删除事件指针即可； （２）如果事件指针存在于目标ＬＰ的ＰＥＬ中，即该事件已被执行，需要对ＬＰ进行回滚操作，从而使系统恢 复到正确的状态． 在读入事件时（正或反），线程核，可能会进行回滚，导致长时间占有缓存区，阻塞其他线程核发送事件．因此， 本文采用一种环式队列构建缓存区，如图７中圆形内部所示．两个队列轮流作为可写入队列供发送线程核使用． 当线程核ｉ发送事件时，首先获取可写入队列的序号，插入事件指针．当线程核，读入事件时，获取并更改可写入 ．队列的序号，然后读取原可操作队列的事件，执行相应的操作．线程核ｉ和．，通过读写锁控制对可写入队列序号的 唐文杰等：面向多核的并行离散事件仿真服务优化 １３８５ 访问 ◇． ．．． Ｆｉｇ．７ Ｐｒｏｃｅｓｓ ｏｆ ｅｖｅｎｔ ｔｒａｎｓｆｅｒ ｂｅｔｗｅｅｎ ＴｈｒｅａｄＫｅｒｎｅｌｓ 图７线程核之间的事件传递过程 ４实验分析 ４．１硬件环境￣ｌ：ｌＰｈｏｌｄ模型 并行仿真内核经过服务优化后，能否获得性能上的提升以及能否获得可扩展的提升，是本文所关注的问题． 测试平台是一个两路四核的服务器，ＣＰＵ为２．５３ＧＨｚ ＱｕａｄＣｏｒｅ Ｘｅｏｎ处理器，内存８Ｇ，操作系统为Ｒｅｄｈａｔ Ｓｅｒｖｅｒ ３．１，内核版本２．６．１８，ｇｃｃ版本为４．１．２． 测试用例选择ｐｈｏｌｄ模型．Ｐｈｌｏｄ是离散事件仿真领域中经典的ｂｅｎｃｈｍａｒｋ，无论在理论上【２ 】还是实践 中［８－１０，１３］，都经常作为仿真内核的标准测试用例使用．其基本描述是：仿真系统由Ⅳ个ＬＰ组成，这些个ＬＰ被平均 的分配到所有的线程核上．初始化时，每个ＬＰ产生 （事件密度）个事件，事件目标按一定规则随机选定．在仿真过 程中，各个ＬＰ接收来自其他或自身ＬＰ的消息事件，在完成一定计算任务后产生一个新事件，并将事件发送到某 个随机选择的目标（可能是自己）．事件局部率用来控制线程核内通信和线程核间通信的比例．新产生事件的时 戳等于所执行事件的当前时戳加上随机确定的时间增量．该模型可视为对离散事件仿真系统的一个抽象表示， 可通过设定不同参数模拟各种特征的仿真应用． ４．２－性能评估 ＬＰ数目（ＮＬＰ）、前瞻值（１ｏｏｋａｈｅａｄ）￣ｌ事件局部率（１ｏｃａｌｉｔｙ）是描述仿真应用特征的重要参数．ＮＬＰ可视为仿 真规模的度量；前瞻值定义为某个ＬＰ影响其他ＬＰ的最小仿真时间间隔，可用于衡量ＬＰ在时间域上的相关性； 事件局部率则用于衡量ＬＰ在空间域上的相关性．下文将从上述３个参数入手，深入分析优化效果． 实验１．可扩展性分析． 仿真内核能否随着处理器核数和逻辑进程数目的增加，提供可持续的性能增长是衡量服务优化质量的重 要指标．图８展示了１０ ０００个ＬＰ、４０ ０００个初始事件在不同的事件局部率和前瞻值下，使用不同处理器核数所 获得加速比．由于使用单个处理核心时消除了核间通信和同步，无法准确刻画应用和平台特征，这里采用２个处 理核心性能的一半作为比较标准．可以看出，服务优化的加速效果十分明显，加速效率在６０％以上．尤其在事件局 部率达到５０％时，可获得接近线性的加速比．当事件局部率偏低时，通信开销是影响整体性能的主要因素，而处理 器核数的增加难以缓解通信开销，导致加速比相对较低．图９展示了不同ＬＰ数目下，仿真内核处理单个事件所需 的平均时间．在不同的事件局部率下，虽然ＬＰ数目按指数增长，但事件执行时间可维持基本平衡ｒ相同条件下扰 唐文杰等：面向多核的并行离散事件仿真服务优化 ｌ３８７ 争仟局鄙率＇０％ 事件局部率＝２５％ ５０一—— —————一一————————一—— 莲 ｏ｝ ＿Ｉ 世 一ＨＰＳＫ １ 善３一 』 誓４０｝，ｓ３屋曾 墨３芒懈 ０｝Ｉ ｍｕｓｉｋ ＩＪ ｉ 基 Ｉ是 ２００ １１ １ １１＿ｌ Ｉ１ｌ ｛』｛ 一 ∞ 如 加：暮２２ ｍ ０ ｌ Ｏ ｌ』 耄ｌ怖ｏ［。ｌ Ｊ＿１ １＿ Ｌ 一ⅢＬ 【【ｉ］ １一 ｌ 至ｌ懈ｏ＿１ Ｉ Ｉ Ｉ．０．０１ ０．１ １ 一 ｌ ＿＿— ＿ｌ Ｊ＿ ＩＪⅡ＿Ｉ ｌ０ 局一＿１。● ｌＪ 一＿ 肿砌 ＿＿－ 事件局部率＝７５％ 迹 ４０ ｆ Ｊ －百ＨＰＳｍｕｓｉＫ Ｊｋ Ｉ３０｝ Ｊ 襄２里 ０｝ １ 薹１０｝ Ｊ 怖。Ｌ Ｊｌ＿Ｊ［Ｌ－ 一Ｊ ０．０１ ０．１ １ １０ Ｌｏｏｋａｈｅａｄ Ｆｉｇ．１ ０ Ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＨＰＳＫ ａｎｄ ｍｕｓｉｋ（Ｎ＝１ ００００，Ｒ＝４） 图１０ ＨＳＫ和ｍｕｓｉｋ的性能比较（Ｎ＝ＩＯ０００，Ｒ＝４） 事件局部率＝０％ 事件局部率＝２５％ ７＿ｌ＿一 一一————一］ 世 赫 怖 ６ ｌｏｏｋａｈｅａｄ＝Ｏ’ ……＂＂Ｖ＂＂ｌＯＯｇａｔＴｅａａ＝Ｉ３ ： 星 厘 苫 蓉 捆每 １ Ｌ…◆－＿ｌｏｏｋａｈｅａｄ＝１ Ｌ－＇￣＇－ｌｏｏｋａｈｅａｄ＝ｌ 慕 一］Ｊ ０ Ｉ ５ １０ １５ 事件密度Ｒ 事件密度 Ｆｉｇ．１ １ Ｅｘｅｃｕｔｉｏｎ ｔｉｍｅ ｐｅｒ ｅｖｅｎｔ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｅｖｅｎｔ ｐｏｐｕｌａｔｉｏｎ 图１１ 不同事件密度下事件执行时间 ５结束语 随着多核技术的不断进步，可执行的核心数目越来越多，将彻底改变高性能计算机的发展方向．就并行离散 事件仿真领域而言，面临应用需求扩张和底层硬件变革的双向压力，发展适应多核的并行仿真技术是一种迫切 的现实需求．虽然现有并行仿真平台能够不加修改地运行在多核处理器上，但由于对进程内并发性以及多核体 系结构发展的忽视，限制了性能进一步提升的空间．本文提出了一种层次化并行仿真内核，以多线程架构进行仿 真调度和事件执行．以此为基础，重点优化了时间管理服务和事件管理服务，从逻辑正确性和效能上对仿真内核 提供有力支持．实验表明，通过服务优化的仿真内核能够在多核平台上获得很好的加速效果，且性能明显优于 ｍｕｓｉｋ平台． 异构多核是多核技术发展的主要方向，如何充分考虑处理核心的多样性，最大化处理器的整体效能 将是我 １３８８ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．６，Ｊｕｎｅ ２０１３ 们下～步工作的重点 Ｒｅｆｅｒｅｎｃｅｓ＂ ［１】 Ａｓａｎｏｖｉｃ Ｋ，Ｂｏｄｉｋ Ｒ，Ｃａｔａｎｚａｒｏ Ｂ，Ｇｅｂｉｓ Ｊ，Ｈｕｓｂａｎｄｓ Ｐ，Ｋｅｕｔｚｅｒ Ｋ，Ｐａｔｔｅｒｓｏｎ Ｄ，Ｐｌｉｓｈｋｅｒ Ｗ，Ｓｈａｌｆ Ｊ，Ｗｉｌｌｉａｍｓ Ｓ，Ｙｅｌｉｃｋ Ｋ．Ｔｈｅ ｌａｎｄｓｃａｐｅ ｏｆｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ ｒｅｓｅａｒｃｈ：Ａ ｖｉｅｗ ｆｒｏｍ Ｂｅｒｋｅｌｅｙ．Ｂｅｒｋｅｌｅｙ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ，２００６． ［２］ Ａｋｈｔｅｒ Ｓ，Ｒｏｂｅｒｔｓ Ｊ．Ｍｕｌｔｉ—Ｃｏｒｅ Ｐｒｏｇｒａｍｍｉｎｇ：Ｉｎｃｒｅａｓｉｎｇ Ｐｅｒｆｏｒｍａｎｃｅ ｔｈｒｏｕｇｈ Ｓｏｆｔｗａｒｅ Ｍｕｌｔｉ－ｔｈｒｅａｄｉｎｇ．Ｉｎｔｅｌ Ｐｒｅｓｓ，２００６． ［３］Ｌａｗ ＡＭ，Ｋｅｌｔｏｎ ＤＷ．Ｓｉｍｕｌａｔｉｏｎ Ｍｏｄｅｌｌｉｎｇ ａｎｄ Ａｎａｌｙｓｉｓ．ＭｃＧｒａｗ—Ｈｉｌｌ Ｅｄｕｃａｔｉｏｎ，２０００． 【４］ Ｆｕｊｉｍｏｔｏ ＲＭ．Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ Ｓｙｓｔｅｍｓ．Ｎｅｗ Ｙｏｒｋ：Ｊｏｈｎ Ｗｉｌｅｙ＆Ｓｏｎｓ Ｉｎｃ．，２０００． （５】 Ｋｏｒｎｉｓｓ Ｇ，Ｎｏｖｏｔｎｙ ＭＡ，Ｇｕｃｌｕ Ｈ，Ｔｏｒｏｃｚｋａｉ ｚ，Ｒｉｋｖｏｌｄ ＰＡ．Ｓｕｐｐｒｅｓｓｉｎｇ ｒｏｕｇｈｎｅｓｓ ｏｆ ｖｉｒｔｕａｌ ｔｉｍｅｓ ｉｎ ｐａｒａｌｌｅｌ ｄｉｓｃｒｅｔｅ—ｅｖｅｎｔ ｓｉｍｕｌａｔｉｏｎｓ．Ｓｃｉｅｎｃｅ，２００３，２９９：６７７—６７９．［ｄｏｉ：１０．１１２６／ｓｃｉｅｎｃｅ．１０７９３８２】 ［６】 Ｓｔｅｉｎｍａｎ ＪＳ．Ｓｐｅｅｄｅｓ：Ａ ｕｎｉｉｆｅｄ ａｐｐｒｏａｃｈ ｔｏ ｐａｒａｌｌｅｌ ｓｉｍｕｌａｔｉｏｎ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ ６ｔｈ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ．１９９２．７５－８３． ［７］Ｄａｓ Ｓ，Ｆｕｊｉｍｏｔｏ Ｒ，Ｐａｎｅｓａｒ Ｋ，Ａｌｌｉｓｏｎ Ｄ，Ｈｙｂｉｎｅｔｔｅ Ｍ．Ｇｔｗ：Ａ ｔｉｍｅ ｗａｒｐ ｓｙｓｔｅｍ ｆｏｒ ｓｈａｒｅｄ ｍｅｍｏｒｙ ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ ２６ｔｈ Ｃｏｎｆ．ｏｎ Ｗｉｎｔｅｒ Ｓｉｍｕｌａｔｉｏｎ．Ｓａｎ Ｄｉｅｇｏ：ＩＥＥＥ，Ｉ９９４．Ｉ３３２－１３３９．［ｄｏｉ：ｌＯ．Ｉ １０９／ＷＳＣ．１９９４．７１７５２７】 ［８】 Ｃａｒｏｔｈｅｒｓ ＣＤ，Ｂａｕｅｒ Ｄ，Ｐｅａｒｃｅ Ｓ．Ｒｏｓｓ：Ａ ｈｉｇｈ－ｐｅｒｆｏｒｍａｎｃｅ，ｌｏｗ ｍｅｍｏｒｙ，ｍｏｄｕｌａｒ ｔｉｍｅ ｗａｒｐ ｓｙｓｔｅｍ．Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，２００２，６２：１６４８—１６６９．【ｄｏｉ：１０．１０１６／Ｓ０７４３－７３１５（０２）００００４—７］ 【９］ Ｂａｇｒｏｄｉａ Ｒ，Ｍｅｙｅｒ Ｒ，Ｔａｋａｉ Ｍ，Ｃｈｅｎ ＹＡ，Ｚｅｎｇ Ｘ，Ｍａｒｔｉｎ Ｊ，Ｓｏｎｇ ＨＹ．Ｐａｒｓｅｃ：Ａ ｐａｒａｌｌｅｌ ｓｉｍｕｌａｔｉｏｎ ｅｎｖｉｒｏｎｍｅｎｔ ｆｏｒ ｃｏｍｐｌｅｘ ｓｙｓｔｅｍｓ．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ，１９９８，３１：７７—８５＿［ｄｏｉ：１０．１１０９／２．７２２２９３】 ［１０】Ｐｅｒｕｍａｌｌａ Ｋ． ｓｉｋ——Ａ ｍｉｃｒｏ—ｋｅｒｎｅｌ ｆｏｒ ｐａｒａＩＩｅｌ／ｄｉｓｔｒｉｂｕｔｅｄ ｓｉｍｕｌａｔｉｏｎ ｓｙｓｔｅｍｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ １９ｔｈ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ａｄｖａｎｃｅｄ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ．２００５．５９—６８．［ｄｏｉ：１ ０．１ １ ０９／ＰＡＤＳ．２００５．１】 ［１ １】 Ｙａｏ ＹＰ，Ｚｈａｎｇ ＹＸ．Ｓｏｌｕｔｉｏｎ ｆｏｒ ａｎａｌｙｔｉｃ ｓｉｍｕｌａｔｉｏｎ ｂａｓｅｄ ｏｎ ｐａｒａｌｌｅｌ ｐｒｏｃｅｓｓｉｎｇ．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍ Ｓｉｍｕｌａｔｉｏｎ，２００８，２０（２４）： ６６１７－６６２１（ｉｎ Ｃｈｉｎｅｓｅ ｗｉｔｈ Ｅｎｇｌｉｓｈ ａｂｓｔｒａｃｔ）． ［１２】 Ｓｕ ＮＬ，Ｗｕ ＸＹ，Ｌｉ Ｑ，Ｗａｎｇ ｗＰ，Ｚｈｕ ＹＦ．Ｏｐｔｉｍｉｓｔｉｃ ｐａｒａｌｌｅｌ ｄｉｓｃｒｅｔｅ ｅｖｅｎｔ ｓｉｍｕｌａｔｉｏｎ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ—ｃｏｒｅ ｐｌａｔｆｏｒｍ．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍ Ｓｉｍｕｌａｔｉｏｎ，２０１０，２２（４）：８５８—８６３（ｉｎ Ｃｈｉｎｅｓｅ ｗｉｔｈ Ｅｎｇｌｉｓｈ ａｂｓｔｒａｃｔ）． ［１３】 Ｃｈｅｎ ＬＬ，Ｌｉｕ ＹＳ，Ｙａｏ ＹＰ，Ｐｅｎｇ ＳＬ，Ｗｕ ＬＤ．Ａ ｗｅｌｌ－ｂａｌａｎｃｅｄ ｔｉｍｅ ｗａｒｐ ｓｙｓｔｅｍ ｏｎ ｍｕｌｔｉ—ｃｏｒｅ ｅｎｖｉｒｏｎｍｅｎｔｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ ２５ｔｈ ＡＣＭ／ＩＥＥＥ／ＳＣＳＷｏｒｋｓｈｏｐ ｏｎＰｒｉｎｃｉｐｌｅｓ ｏｆＡｄｖａｎｃｅｄ ａｎｄＤｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ（ＰＡＤＳ ２０１１、．２０ｌ１．１－９． 【１４］ Ｓｔｅｉｎｍａｎ ＪＳ．Ｔｈｅ ＷａｒｐｌＶ ｓｉｍｕｌａｔｉｏｎ ｋｅｒｎｅ１．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ ２００５ Ｐｒｉｎｃｉｐｌｅｓ ｏｆＡｄｖａｎｃｅｄ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ Ｃｏｎｆ．２００５． ［１５】Ｍｉｌｌｅｒ ＲＪ．Ｏｐｔｉｍｉｓｔｉｃ ｐａｒａｌｌｅｌ ｄｉｓｃｒｅｔｅ ｅｖｅｎｔ ｓｉｍｕｌａｔｉｏｎ ｏｎ ａ Ｂｅｏｗｕｌｆ ｃｌｕｓｔｅｒ ｏｆ ｍｕｌｔｉ－ｃｏｒｅ ｍａｃｈｉｎｅｓ［ＭＳ．Ｔｈｅｓｉｓ］．Ｃｉｃｉｎａｔｉ Ｕｎｉｖｅｒｓｉｔｙ，２０１０． ［１６】Ｍａｒｔｉｎ ＤＥ，ＭｃＢｒａｙｅｒ ＴＪ，Ｗｉｌｓｅｙ ＰＡ．Ｗａｒｐｅｄ：Ａ ｔｉｍｅ ｗａｒｐ ｓｉｍｕｌａｔｉｏｎ ｋｅｒｎｅｌ ｆｏｒ ａｎａｌｙｓｉｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｄｅｖｅｌｏｐｍｅｎｔ．Ｉｎ：Ｐｒｏｃ． ｏｆｔｈｅ ２９ｔｈ Ｈａｗａｉｉ Ｉｎｔ’１ Ｃｏｎｆ．ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ，Ｖｏ１．１．Ｗａｓｈｉｎｇｔｏｎ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，１９９６．３８３－３８６－［ｄｏｉ：１０．１１０９／ ＨＩＣＳＳ．１９９６．４９５４８５】 ［１７］Ｔａｎｇ ＷＪ，Ｙａｏ ＹＰ．ＨＰＳＫ：Ａ ｈｉｅｒａｒｃｈｉｃａｌ ｐａｒａｌｌｅｌ ｓｉｍｕｌａｔｉｏｎ ｋｅｒｎｅｌ ｆｏｒ ｍｕｌｔｉｃｏｒｅ ｐｌａｔｆｏｒｍ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ ９ｔｈ ＩＥＥＥ Ｉｎｔ’１ Ｓｙｍｐ．ｏｎ Ｐａｒａｌｌｅｌ ａｎｄＤｉｓｔｒｉｂｕｔｅｄＰｒｏｃｅｓｓｉｎｇｗｉｔｈＡｐｐｌｉｃａｔｉｏｎｓ（ＩＳＰＡ ２０１１）．２０１１．１９－２４ｌ［ｄｏｉ：１０．１１０９／ＩＳＰＡ．２０１１．４２】 Ｉ１ ８】 Ｊｈａ Ｖ，Ｂａｇｒｏｄｉａ ＲＬ．Ａ ｕｎｉｆｉｅｄ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｃｏｎｓｅｒｖａｔｉｖｅ ａｎｄ ｏｐｔｉｍｉｓｔｉｃ ｄｉｓｔｒｉｂｕｔｅｄ ｓｉｍｕｌａｔｉｏｎ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ．１９９４．１２—１９［ｄｏｉ：１０．１ １４５／１８２４７８．１８２４８０】 【１９】 Ｓａｍａｄｉ Ｂ．Ｄｉｓｔｒｉｂｕｔｅｄ ｓｉｍｕｌａｔｉｏｎ，ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ａｎａｌｙｓｉｓ［Ｐｈ．Ｄ．Ｔｈｅｓｉｓ］．Ｌｏｓ Ａｎｇｅｌｓ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ，Ｌｏｓ Ａｎｇｅｌｓ，１９８５． ［２０】 Ｍａｔｔｅｒｎ Ｆ．Ｅｆｉｆｅｉｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｓｎａｐｓｈｏｔｓ ａｎｄ ｇｌｏｂａｌ ｖｉｒｔｕａｌ ｔｉｍｅ ａｐｐｒｏｘｉｍａｔｉｏｎ．Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，１９９３，１８（４）：４２３－４３４．［ｄｏｉ：１０．１００６／ｊｐｄｃ．１９９３．１０７５］ 【２ １】 Ｆｕｊｉｍｏｔｏ ＲＭ，Ｈｙｂｉｎｅｔｔｅ Ｍ，Ｃｏｍｐｕｔｉｎｇ Ｇｌｏｂａｌ ｖｉｒｔｕａｌ ｔｉｍｅ ｉｎ ｓｈａｒｅｄ－ｍｅｍｏｒｙ ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ．ＡＣＭ Ｔｒａｎｓ．ｏｎ Ｍｏｄｅｌｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｉｍｕｌａｔｉｏｎ，１９９７，７（４）：４２５－４４６．【ｄｏｉ：１０．１ １４５／２６８４０３．２６８４０４】 ［２２】Ｐｅｒｕｍａｌｌａ Ｋ，Ｆｕｊｉｍｏｔｏ Ｒ．Ｖｉｒｔｕａｌ ｔｉｍｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｏｖｅｒ ｕｎｒｅｌｉａｂｌｅ ｎｅｔｗｏｒｋ ｔｒａｎｓｐｏｒｔ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｉｍｕｌａｔｉｏｎ．２００１．１２９－１３６．［ｄｏｉ：１０．１１０９／ＰＡＤＳ．２００１．９２４６２９】 唐文杰等：面向多核的并行离散事件仿真服务优化 １３８９ 【２３］ Ｂｅｒｇｅｒ ＥＤ，ＭｃＫｉｎｌｅｙ ＫＳ，Ｂｌｕｍｏｆｅ ＲＤ，Ｗｉｌｓｏｎ ＰＲ．Ｈｏａｒｄ：Ａ ｓｃａｌａｂｌｅ ｍｅｍｏｒｙ ａｌｌｏｃａｔｏｒ ｆｏｒ ｍｕｌｔｉｔｈｒｅａｄｅｄ ａｐｐｌｉｃａｔｉｏｎｓ．Ｉｎ：Ｐｒｏｃ． ｏｆｔｈｅ ９ｔｈ ｌｎｔ’Ｉ Ｃｏｎｆ．ｏｎ Ａｒｃｈｉｔｅｃｔｕｒａｌ Ｓｕｐｐｏｒｔ ｏｒｆ Ｐｒｏｇｒａｍｍｉｎｇ Ｌａｎｇｕａｇｅｓ ａｎｄ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ．２０００．Ｉ １７—１２８．【ｄｏｉ：１０．１ １４５／ ３５６９８９．３５７０００】 ｒｕｃｔｉｎｇ ｏｐｔｉｍｉｓｔｉｃ ｓｉｍｕｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｄｉｓｃｒｅｔｅ ｅｖｅｎｔ ｓｙｓｔｅｍ ｓｐｅｅｉｉｃａｔｉｆｏｎ．ＡＣＭ Ｔｒａｎｓ．ｏｎ Ｍｏｄｅｌｉｎｇ 【２４】 Ｎｕｔａｒｏ Ｊ．Ｏｎ ｃｏｎｓｔａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｉｍｕｌａｔｉｏｎ，２００８，１９（１）：１—２１．［ｄ０ｉ：１０．Ｉ １４５／１４５６６４５．１４５６６４６】 附中文参考文献： ［１】】姚益平，张颖星．基于并行处理的分析仿真解决方案．系统仿真学报，２００８，２０（２４）：６６１７—６６２１． 【１２】苏年乐，李群，王维平，朱…凡．基于多核平台的乐观并行离散事件仿真．系统仿真学报，２０１０，２２（４）：８５８－８６３ 卫 主唐Ｅ－文要ｍａ研杰ｉｌ：究（ｔ１ａｎ９领８ｇ４域ｗ一ｅ为￣），并ｉｅ男＠行，ｎ湖离ｕｄ南散ｔ．ｅ长事ｄｕ沙件．ｃｎ人仿 ，真博． 士生， 圈 姚Ｅ师・，ｍ益主ａ平要ｉｌ：（研ｙ１ｐ９究ｙ６ａ３领ｏ一＠域）ｎ，ｕ为男ｄｔ，并．博ｅｄ行ｕ士．与ｃ，ｎ教 分授布，仿博真士． 生导
