（计算机科学与技术专业论文）分布并行模拟验证平台同步技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 高效的系统功能验证能有效地缩短设计周期并降低设计成本，成为系统设计 中至关重要的环节。随着大规模集成电路制造工艺的快速发展以及各种应用对系 统设计提出的大量新要求，使得数字系统的设计变得日趋复杂。传统的单机验证 方法已经难以满足目前系统验证对验证周期、计算资源和存储资源的要求。分布 并行模拟验证方法能满足大规模、复杂系统对大量资源的需求并提高模拟验证速 度，逐渐成为模拟验证的发展方向，具有良好的应用前景。分布并行模拟验证同 步技术主要用于对进行分布并行模拟验证的各个结点进行模拟流程控制，维持各 个结点状态的一致性以及保证各个结点之间相应的逻辑关系，因而同步技术是分 布并行模拟验证中的关键技术，是实现分布并行模拟验证的前提和基础。 本文首先对以c m b 和t i m ew a r p 算法为代表的两类分布并行模拟同步算法进 行了研究，对这两类同步策略在算法基本原理、同步方式和性能等方面进行了简 要的对比分析。随后在对分布并行模拟验证平台进行分析和对目前的分布并行模 拟同步算法研究的基础上设计了一种基于下一时间步时标的预约式同步算法 ( t n s a ) ，描述了该算法的主要思想、所需的数据结构和其基本流程，并对该算 法主要的开销进行了分析。在设计的t n s a 同步算法的基础上通过构建同步机制 和通信子系统，采用不同于目前已有同步环境的回调方式实现了应用于分布并行 模拟验证平台的同步环境。最后使用代表三种不同应用的千万门级测试模型进行 了性能测试，测试结果表明所实现的同步环境能够在消耗较少资源的情况下获得 较高的性能加速比，证实了分布并行模拟验证方法在资源需求和加速模拟等方面 的优势，并且通过对测试结果进行相应的分析为进一步提高同步环境的性能提供 了基础。 主题词：分布并行模拟验证，同步技术，c m b ，t i m ew a r p 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t e f f i c i e n tf u n c t i o n a lv e r i f i c a t i o ni sac r i t i c a l s t e p t ot h ed e s i g n ，w h i c hc a t l f f f e c t i v e l ys h o r t e nt h ed e s i g nc y c l ea n dr e d u c et h ec o s to fd e s i g n w i t ht h el a r g e s c a l e n t e g r a t e dc i r c u i tm a n u f a c t u r i n gd e v e l o pr a p i d l ya n daw i d er a n g eo fa p p l i c a t i o n so nt h e ；y s t e md e s i g np u tf o r w a r dal a r g en u m b e ro fn e wr e q u i r e m e n t s d i g i t a ls y s t e md e s i g n l o sb e c o m em o r ec o m p l e x t r a d i t i o n a ls t a n d a l o n e v e r i f i c a t i o nm e t h o dh a sb e e n i i f f i c u l tt om e e tt h er e q u i r e m e n to ff u n c t i o n a lv e r i f i c a t i o na b o u tt h ev e r i f i c a t i o nt i m e ， z o m p u t i n ga n ds t o r a g er e s o u r c e s d i s t r i b u t e da n dp a r a l l e lv e r i f i c a t i o nc a nm e e tt h e e q u i r e m e n to ft h el a r g e - s c a l ea n dc o m p l e xs y s t e mf o r t h er e s o u r c e ，a n di tc a ni m p r o v e d m u l a t i o ns p e e dt or e d u c et h et i m es p e n d i n go nt h ev e r i f i c a t i o n d i s t r i b u t e da n d 9 a r a l l e lv e r i f i c a t i o nh a sb e c o m et h et r e n do fv e r i f y i n ga n dh a sf lg o o dp r o s p e c tf o ri t s t d v a n t a g e s s y n c h r o n i z a t i o nt e c h n o l o g yo fd i s t r i b u t e da n dp a r a l l e lv e r i f i c a t i o ni su s e d | om a i n t a i ns t a t ec o n s i s t e n c ya n dt oo b e yt h ec a u s a l i t yc o n s t r a i n t t h e r e f o r ei ti st h ek e y ：e c h n o l o g yt h a tp r o v i d e st h ep r e r e q u i s i t ea n db a s i sf o ri m p l e m e n t i n gd i s t r i b u t e da n d 9 a r a l l e lv e r i f i c a t i o n t w oc l a s s i cd i s t r i b u t e da n dp a r a l l e ls i m u l a t i o np r o t o c o l s ，e s p e c i a l l yt h ec m ba n d f i m ew a r pa l g o r i t h m ，a r er e s e a r c h e df i r s t l yi nt h i sp a p e r s o m em a i na s p e c t so ft h e x o t o c o l sa r ea n a l y z e d ，i n c l u d i n gp r i n c i p l e ，s y n c h r o n i z a t i o nm o d ea n dp e r f o r m a n c e o n ：h eb o s eo fa n a l y s i so ft h ed i s t r i b u t e da n dp a r a l l e lv e r i f i c a t i o np l a t f o r ma n dt h er e s e a r c h t b o u tt h ec l a s s i c a l g o r i t h m s ，t h et i m e o fn e x t s t e p b a s e da p p o i n t m e n t ( t n s a ) ；y n c h r o n i z a t i o na l g o r i t h mi sp r o p o s e d t h e nt h ep r i n c i p l e ，d a t as t r u c t u r ea n db a s i cf l o w ) ft h i sa l g o r i t h ma r ed e s c r i b e da n dt h em a i no v e r h e a d sa r ea n a l y z e d b a s e do nt h e f n s aa l g o r i t h m ，t h es y n c h r o n i z a t i o nm e c h a n i s ma n dc o m m u n i c a t i o ns y s t e mb e ：o n s t r u c t e d ，t h i st h e s i si m p l e m e n tas y n c h r o n i z a t i o ne n v i r o n m e n tf o rt h ed i s t r i b u t e da n d ) a r a l l e lv e r i f i c a t i o np l a t f o r m t h r e ee v a l u a t i o n sw h i c hr e p r e s e n td i f f e r e n ta p p l i c a t i o n s l a v eb e e nd o n eb yu s i n gt e n so fm i l l i o ng a t e sc i r c u i t t h es i m u l a t i o nr e s u l t ss h o wt h a t ：h e s y n c h r o n i z a t i o ne n v i r o n m e n tc a ng e te f f i c i e n ts p e e d u pi nl e s sc o n s u m p t i o no f ：e s o u r c e t h er e s u l t so fe v a l u a t i o n sd e m o n s t r a t et h ea d v a n t a g e so ft h ed i s t r i b u t e da n d ) a r a l l e lv e r i f i c a t i o na n dt h ea n a l y s e so ni tp r o v i d et h eb a s i sf o rf u r t h e ri m p r o v i n gt h e ；y n c h r o n i z a t i o ne n v i r o n m e n tp e r f o r m a n c e k e yw o r d s ：d i s t r i b u t e da n dp a r a l l e lv e r i f i c a t i o n ，s y n c h r o n j z a t i o nt e c h n o i o g y ，c m b ，t i m ew a r p 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表2 1 两种同步策略对比1 4 表4 1u d p 与t c p 的对比3 0 表5 1 测试参数4 0 表5 2l o c a ls i m 模式时间消耗情况一4 1 表5 3l o c a ls i m 模式报文及同步情况4 1 表5 4l o c a ls i m 模式内存消耗情况。4 1 表5 5l o c a ls i m l 模式时间消耗情况4 3 表5 6l o c a ls i m l 模式报文及同步情况一4 3 表5 7l o c a ls i m l 模式内存消耗情况4 3 表5 8c r o s ss i m 模式时间消耗情况4 5 表5 9c r o s ss i m 模式报文及同步情况：4 5 表5 1 0c r o s ss i m 模式内存消耗情况4 5 第1 i i 页 国防科学技术大学研究生院硕十学位论文 图2 1 图2 2 图2 3 图2 4 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图4 1 图4 2 图4 3 图4 4 图4 5 图 图 图 图 1 2 3 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图目录 调度器的事件组织示意图5 l p 示意图6 并行离散事件模拟结构图7 保守类策略示意图8 乐观类策略示意图1 1 t n s a 同步算法示意图1 7 t n s a 同步算法l p 结构图1 9 不进行等待同步结束的情形2 1 信号值更新循环示意图2 2 信号值更新循环解决方法2 2 t n s a 同步算法简要伪码2 3 t n s a 同步算法示例图2 4 当前时间步同步开销状况2 6 分布并行模拟验证平台结构2 8 基于t c p 的两种服务器模型示意图。3 1 通信子系统示意图3 2 s i g _ _ v a l u e c h a n g e 函数流程图3 4 s y n 函数流程图35misctf 测试模型结构图3 8 测试程序示意图3 9 测试方案4 0 l o c a ls i m 模式开销分布4 2 l o c a ls i m 模式同步开销分布4 2 l o c a ls i m 模式报文分布4 3 l o c a ls i m l 模式开销分布4 4 l o c a ls i m l 模式同步开销分布4 4 l o c a ls i m l 模式报文分布4 4 c r o s ss i m 模式开销分布4 6 c r o s ss i m 模式同步开销分布4 6 c r o s ss i m 模式报文分布4 6 带宽和信号报文比例变化率4 7 三种测试模式加速比4 8 第1 v 页 国防科学技术大学研究生院硕士学位论文 图5 15复杂度和并行度变化率4 8 图5 1 6同步开销和等待开销比例变化率4 9 图5 1 7 有效同步比例一4 9 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 金查羞红搓赵坠适圣鱼回生技盔盈窒 一 一 学位论文作者签名：圣堕塑皇 一一 日期：2 。5 年j 2 月2 c f 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 金查羞短搓拯坠适垩鱼回生挞盔盟窥 学位论文作者签名：乃遁朋乌 作者指导教师签名：二窆芝墼 日期：2 0 0 5 年f 2 月研日 吼加矿年少月乡日 国防科学技术大学研究生院硕士学位论文 第一章绪论弟一早珀v 匕 1 1 课题背景和意义 随着时代的发展，数字系统的开发风险和成本变得越来越高，如何有效地降 低开发风险和成本成为了所有系统开发商必须面对的问题。目前数字系统的设计 已广泛采用可缩短开发周期的硬件设计描述语言( h d l ) 进行开发。系统功能验证 可对使用硬件设计描述语言设计的系统进行功能验证。“如何尽早发现更多的隐 藏在设计中的逻辑或功能错误，这是系统功能验证的任务。系统功能验证已成为 系统设计中至关重要的环节。，【l 】系统功能验证能有效地缩短设计周期并降低设 计成本，加速产品的上市时间以占领市场。传统的验证方法是通过在单机上运行 模拟验证软件来对设计进行验证，这对于中小规模的设计是比较有效的。但随着 集成电路制造工艺的飞速发展，单位面积硅片上能集成的晶体管数目以摩尔定律 的速度在增加，越来越多的功能模块能被集成在同一块芯片中；同时，各类新的 应用也对系统设计提出了新的要求，这使得各类系统设计有了更大的发展空间， 但也导致了系统设计日渐复杂。诸如流体系结构、多核多线程体系结构、 p i m ( p r o c e s s o ri nm e m o r y ) 等前瞻体系结构的系统设计非常复杂，规模一般在几千 万门以上。日趋增加的系统设计复杂性使得验证时间不断增加，并且对处理器、 内存等资源的需求也随之增长，加之单机的性能增长有限，因此传统的验证方法 已经难以满足系统规模和复杂度的增长，日渐成为大规模、复杂系统设计过程中 的瓶颈。 为了能快速有效地验证复杂系统和大规模系统的正确性，有人提出采用分布 并行模拟验证的方法。分布并行模拟验证就是将设计进行划分并分布到多台工作 站上，每台工作站上的模拟软件只负责模拟设计的一部分，并通过模拟软件问的 相互协作、并行执行来共同完成对整个设计的模拟验证。分布并行模拟验证以并 行的方式来对一个大规模、复杂系统设计进行模拟，提高了模拟的并行性，因此 提高了模拟的速度。并且在分布并行模拟验证环境中，计算资源取决于参与分布 并行模拟验证的结点数量，而在分布环境中结点的数量几乎可任意扩展而不受限 制，因而其可支持大规模设计对大量计算资源的需求。分布并行模拟的这些特点 使其能较好地支持大规模、复杂系统的模拟验证，因而被认为是未来模拟验证的 发展方向。分布并行模拟验证同步技术的主要研究内容是在分布并行模拟同步算 法的基础上构建出同步环境。同步环境主要用于对参与分布并行模拟验证的模拟 结点进行流程控制，保证划分到各个模拟结点上的设计之间固有的逻辑关系被保 持，从而确保分布并行模拟验证能够获得正确的模拟的结果。此外，分布并行模 第1 页 国防科学技术大学研究生院硕士学位论文 拟验证的性能与同步环境的性能紧密相关。所以同步环境对分布并行模拟验证的 正确性和性能有着决定性的影响。因此同步技术是实现分布并行模拟验证的关键 技术，高效的同步技术将成为设计与实现能实际应用于大规模、复杂系统的分布 并行模拟验证平台的前提和基础。目前已实现的同步环境还存在各种不足，因而 需要对分布并行模拟验证同步技术进行进一步的研究。 1 2 课题研究现状 国外已有许多研究学者、机构和公司对分布并行模拟验证同步算法进行了研 究并在此基础上设计和实现了相应的同步环境。 b r i n e r 等人采用惰性取消的时间卷回算法实现了一种并行模拟器【2 】，通过使用 具有3 2 个处理器的b b ng p l 0 0 0 系统取得了相比顺序模拟2 3 倍的加速比。同时 对标准的时间卷回算法在状态保存和同步粒度方面进行了改进以增加加速比。 b a u e r 等人基于事件驱动的模拟器l d s i m 3 】构建了一种并行逻辑模拟器【4 1 ，通过对 i s c a s 8 9 测试集中中等规模设计( 电路规模为3 5 0 0 至1 9 2 0 0 门) 在1 2 个l d s i m 模拟器上进行模拟，获得了2 到4 倍的加速比。m a n j i k i a n 和l o u c k s 在一个工作站 集群上实现了一种并行逻辑模拟器【5 】，在7 个模拟器上对i s c a s 8 9 测试集中的大 规模电路进行模拟得到了2 到4 2 倍的加速比。b a g r o d i a 在分布存储和共享存储的 并行结构系统上实现了一种针对m a i s i e 6 1 模拟语言的并行电路模拟器i _ 7 1 ，使用 i s c a s 8 5 测试集中4 个最大的电路( 规模分别为11 9 3 ，1 6 6 7 ，2 3 0 7 和2 4 1 8 门) 进行测试，在8 个s p a r e l 0 0 0 处理器上采用保守类策略和乐观类策略分别获得了3 倍和2 倍的加速比。m e i s t e r 采用保守类策略开发了一种针对v h d l 硬件设计语言 的并行事件驱动模拟器d v s i m 引，该模拟器是在l e v i t a n 开发的顺序模拟器 l v s i m 9 】的基础上改进实现的。对i s c a s 8 9 测试集中电路规模分别为8 9 2 ，1 5 7 0 9 和4 0 6 8 5 门的电路进行模拟，结果表明对于小规模电路无法取得加速比，对于更 大规模的测试集电路在1 2 个处理器上获得了4 倍的加速比。l i 等人设计并实现了 一种针对分布v e r i l o g 模拟的面向对象的同步机制d v s 1 0 】，该同步机制通过将 w i l l i a m s 开发的开源v e r i l o g 模拟器i c a r u sv e r i l o g 1 l j 与采用基于分簇时间卷回算法 ( c t w t l 2 】) 的模拟器( o o c t w ) 结合而实现。在本同步机制中，各模拟结点按 组分入多个簇中，在每个簇中使用顺序算法；在各个簇之间使用时间卷回算法。 使用规模为2 4 1 6 门的1 6 位乘法器在8 台互连的计算机上进行测试，试验结果显 示d v s 比顺序模拟的i c a r u sv e r i l o g 运行得慢，无法获得加速比。作者将其归因于 大量的网络开销和较小的测试电路规模，并认为需要对大规模电路进行测试才能 说明d v s 的性能。z h u 等人在旨在设计面向组成的离散事件模拟1 1 3 - 1 5 】的c o s t 项 引1 6 】的基础上采用改进的时间卷回算法发展了一种同步机制d s i m l l 7 】。对1 2 0 万 第2 页 国防科学技术大学研究生院硕士学位论文 门左右规模的设计在5 到3 3 个结点上获得了大约2 至2 7 倍的加速比。a v e r y 公司 采用保守类策略开发的商用分布并行模拟验证环境s i m c l u s t e r i s 】支持目前的主流 商用模拟器，在6 到1 5 个结点上对大规模设计可以取得5 到1 3 倍的加速比。 虽然已经设计和实现了上述的这些同步环境，但其中大多数还主要应用于研 究领域，只是在对同步环境的性能进行测试以及证实分布并行模拟验证相比传统 的顺序模拟验证方法的优越性，并不能实际应用于对大规模、复杂系统设计的模 拟验证。如d v s i m 、d v s 和d s i m 等同步环境所能验证的规模有限( 一般只有几 千门到最多一百多万门的规模) ，且获取的加速比有限：商用分布并行模拟验证 环境s i m c l u s t e r 能对大规模、复杂系统设计进行具有一定加速比的模拟验证，但 由于其具有军方背景，因而获取渠道困难。 1 3 本文研究内容和工作 本文介绍了分布并行模拟同步的基本原理，对目前的分布并行模拟同步算法 进行了研究，在此基础上设计了一种同步算法并据此实现了相应的同步环境，此 外还对该同步环境的性能进行了测试和分析。 本文的重点研究内容包含以下四个方面： 1 ) 分布并行模拟同步算法研究对目前已发展出的同步算法进行研究，分 析对比各种同步算法的主要思想、流程和性能等特点。为设计本文所需的分布并 行模拟验证同步算法提供理论依据和支持。 2 ) 同步算法设计在分析目前同步算法的基础上，根据需求设计了一种基 于下一时间步时标的预约式同步算法( t n s a ) ，主要包括算法的基本思想、算法 所需的数据结构以及算法的详细流程。并且对此同步算法的开销情况进行了初步 的理论分析。 3 ) 同步环境实现根据分布并行模拟验证平台的特点和所设计的同步算法 构建相应机制，采用回调方式实现了一种同步环境，使其能较好地应用于分布并 行模拟验证平台之上。 4 ) 同步环境性能测试分析通过对代表不同应用的大规模、复杂系统设计 进行模拟验证，证实本文所实现的同步环境能正确完成分布并行模拟验证任务， 且测试结果表明该同步环境能够获得相对顺序模拟验证较高的加速比，并且对同 步环境的主要性能因素在不同应用中的影响进行了相应的分析。 1 4 论文组织结构 本文对分布并行模拟验证的原理和关键技术进行了论述，重点研究了分布并 第3 页 国防科学技术大学研究生院硕士学位论文 行模拟同步算法，设计了一种同步算法并实现了相应的同步环境，并对同步环境 的性能进行了测试和分析。全文共分六章，各章节内容组织如下： 第一章是绪论，指出了课题的研究背景和意义、介绍了目前的研究现状和本 文的主要研究内容。 第二章研究了目前的分布并行模拟同步算法。论述了分布并行模拟的基本原 理，对目前两类主要的同步算法的基本思想、流程和优缺点作了对比分析。 第三章设计了一种基于下一时间步时标的预约式同步算法( t n s a ) 。通过对 该算法的基本思想和基本流程的介绍以及对同步算法开销的分析，论述了本文设 计的同步算法的特点。 第四章实现了同步环境。在分析分布并行模拟验证平台和所设计的同步算法 的基础上，通过对通信系统和同步机制的构建进行描述，介绍了使用回调方式进 行同步环境的具体实现。 第五章测试和分析了同步环境的性能。主要包括测试的目的、测试模型和相 应的测试指标，并根据测试结果证实该同步环境具有较高的加速比以及分析了各 种性能因素对同步环境的性能影响。 第六章对本文的工作进行了总结，并展望了未来进一步的研究方向。 第4 页 国防科学技术大学研究生院硕士学位论文 第二章分布并行模拟同步算法研究 2 1 分布并行离散事件模拟( p d e s ) 在离散事件模拟( d e s ) 中，所模拟的所有行为和动作都由带有时标的事件表 示，一般使用二元组( e ，t ) 表示事件，其中第一个元素e 表示模拟事件，第二个 元素t 表示该事件的时标，即事件的发生时间。调度器( s c h e d u l e r ) 负责对这些 时间和事件进行管理。在调度器中对事件的组织如图2 1 所示。从图中可以看出， 调度器根据各个事件所带时标的大小将这些时标按从小到大的次序划分为若干个 时间步( t i m es t e p 1 9 】) ，并为每一个时间步组织一个事件队列。在这个事件队列中 包含了所有时标大小等于该时间步时标的事件。当模拟时钟推进到某个时间步的 时标时，调度器就从该时间步的事件队列中取出事件送往逻辑处理器( l o g i c a l p r o c e s s ，以下简称l p 2 m 2 1 】) 进行相应的处理。对事件的处理可能会产生当前或以 后时间步的新事件。当l p 产生新事件时，调度器会依据该事件的时标依序将其插 入相应时间步的事件队列中。当某个时间步的事件队列中的所有事件都已经被处 理完成，调度器就将模拟推进至下一时间步并继续按照上述过程进行事件处理。 e v e n t sf o rt h et i m e t o 图2 1 调度器的事件组织不意图 调度器送来的事件由逻辑处理器( l p ) 负责处理。当l p 对带有时标的事件进 行处理时，通过状态变化函数改变目前的模拟状态，并产生某个时刻的新事件。 图2 2 表示l p 的示意图。每次l p 从调度器接收到一个事件时，首先查找哪些状 态值将被使用并取回这些状态值。接着l p 使用状态变化函数根据所接收的事件和 目前的状态值进行计算以决定是否需要改变模拟状态。如果l p 的输出值发生了变 化，则会产生一个新事件以表示在某个时刻将有一个事件需要被，随后这个新事 件被送回调度器进行相应的调度管理，然后l p 继续对接收的下一个事件进行上述 第5 页 国防科学技术大学研究生院硕士学位论文 处理。 f r o m s c h e d u l e r d i n c o m i n g k l t o f i s c h e d u l e r y e v e n t e v 、1 tproees n e w c 1 雕n ti s e v e n t s t a t e i l c h a n g e ds t a t e 图2 2l p 示慈图 在并行离散事件模拟( p d e s ) 的情况下，将有多个模拟结点同时参与模拟。 每个模拟结点都有自己的调度器和l p ，各个模拟结点之间通过事件消息通道传递 信息。其结构如图2 3 所示。采用这种结构进行模拟时，一个大的设计模块被划分 为若干个子模块并分配给各个模拟结点，每个模拟结点负责模拟其中的一个或几 个子模块。在进行模拟时，各个模拟结点中的调度器根据自己所组织的事件表将 事件发送给l p 进行处理。l p 在收到分发的事件后，根据目前自身的状态和收到 的事件决定是否发生状态的改变并产生新的事件。由于在并行离散事件模拟的条 件下，各个模拟结点所负责的子模块之间存在逻辑联系，因此l p 可能会产生需要 在其它模拟结点上进行处理的外部事件。这些事件将通过相应的消息通道以事件 消息的形式被发送给负责处理的相应模拟结点。收到外部事件的模拟结点的调度 器会将这些外部事件按序插入到自己的事件队列中然后对其进行调度分发。因而， 各个模拟结点既要处理自身产生的内部事件又要处理其它模拟结点产生的外部事 件，各个l p 对事件的处理结果都会对其它的l p 的状态变化产生影响。 为了获得正确的模拟结果，采用离散事件模拟方法必须保证以单调非减的时 标顺序对事件进行处理。在并行离散事件模拟的情况下，各个模拟结点都在同时 处理各自的事件且只保有自身的状态信息而没有全局的状态信息，除非收到其它 模拟结点发来的事件消息，否则即使每个模拟结点都以单调非减的时标顺序处理 事件，它也不可能获知其它模拟结点将要发送给自己的事件的信息。因此，任何 一个模拟结点都可能收到带有比当前本地时钟更小时标的外部事件，从而违背了 因果关系约束( c a u s a l i t yc o n s t r a i n t l 2 2 ) 。因为任何事件都不能被带有更大时标的事 件所影响，否则就会出现未来能影响过去的荒谬状况，导致模拟结果出现错误。 为了解决并行离散事件模拟中存在的这种问题，必须有相应的算法对各个模拟结 点的处理过程进行同步控制以保证各个模拟结点之间进行正常的交互，使所有结 第6 页 国防科学技术大学研究生院硕士学位论文 点对事件的处理都满足相应的凶果约束，进而获得正确的模拟结果。 图2 3 并行离散事件模拟结构图 目前的各种同步算法根据其是否服从因果关系约束被分为保守和乐观两类策 略。因果关系约束是指从任何模拟结点发来的外部事件所带的时标的大小都不能 小于目的结点的局部时钟的时标。保守类策略通过严格地满足因果关系约束从而 避免产生任何因果关系错误。乐观类策略试图利用在不满足因果关系约束的情况 下也不会产生因果关系错误的可能性，允许各个模拟结点独立地进行事件处理以 提高处理过程的并行度，但同时保证能及时地检测出因果关系错误的发生并提供 相应的恢复机制使模拟恢复到正确状态，从而保证模拟结果的正确性。 2 2 保守类策略 在保守类策略中，只有安全事件( s a f ee v e n t s ) 才会被模拟结点中的l p 处理。安 全事件是指时标不小于目前l p 的局部时钟的事件，这种事件能保证l p 永远不会 收到时标比该事件所带时标更小的事件，因而可以由l p 自由地进行处理。采用这 种策略时，各个l p 都以时标非减的顺序对自己的事件队列中的事件进行处理，并 且以相同的次序将生成的外部事件通过连接各l p 的事件消息信道发送给相应的 l p 。在进行事件处理时，每一次只有所有l p 中时标最小的未处理事件才能被处理。 这样能保证l p 不会收到时标比它的局部时钟更小的事件，从而只有安全事件被处 理。而没有安全事件的l p 则必须阻塞等待直至其自身拥有的事件满足条件成为安 第7 页 国防科学技术大学研究生院硕士学位论文 全事件为止。因此保守类策略依靠只处理安全事件和在无安全事件时阻塞等待保 证在任何时刻都能满足因果关系约束。 图2 4 保守类策略不慈图 图2 4 展示了n 个l p 采用保守类策略从模拟开始时刻t o 开始的推进过程。由 图中可看出l p l 有一个t l 时刻的事件e v e n t l a 和一个t 3 时刻的事件e v e n t m 。l p 2 有一个t 2 时刻的事件e v e m 2 a 。l p n 有一个t l 时刻的事件e v e n t n a 。首先在t o 时刻所 有l p 中时标最小的未处理事件是时标等于t l 的l p l 中的事件e v e n t l a 和l p n 中的 事件e v e n t n a ，因此这两个事件是目前系统中的安全事件，l p l 和l p n 将分别处理 事件e v e n t l a 和e v e n t n a 并将自己的时钟推进至t l ，而l p 2 则必须阻塞等待以防止 l p l 和l p n 在处理完事件e v e n t l a 和e v e n t n a 后可能会产生发送到自己的外部事件。 当系统中t l 时刻的事件e v e n t l a 和e v e n t n a 被处理完毕后，此时所有l p 中时标最小 第8 页 国防科学技术大学研究生院硕士学位论文 的未处理事件变为时标等于t 2 的l p 2 中的事件e v e n t 2 a ，于是事件e v e n t 2 a 成为目 前系统中的安全事件从而被l p 2 进行处理，而l p l 和l p n 由于无安全事件则阻塞 等待，以上过程反复进行直至模拟结束。在保守类策略中，由于需要严格满足因 果关系的约束而进行阻塞等待，所以采用保守类策略容易引起死锁的产生。 2 2 1c m b 算法 c h a n d y ，m i s r a 和b r y a n t 在上世纪七十年代末期发展了最早的一种分布并行模 拟同步算法，现在一般称之为c h a n d y m i s r a b r y a n t ( c m b 2 3 - 2 5 j ) 算法。在c m b 算法中，对于某个事件( e k ，t k ) ，只有当逻辑处理器l p i ( 表示第i 个l p ) 确定不 会接收到时标比事件e k 的时标t k 更小的事件的时候，l p i 才会对事件e k 进行处理， 以此保证l p i 所处理的事件e k 的时标t k c i ( 其中c i 为l p i 的局部时钟l v t 的时 标) 。该算法为每个l p 都建立了全互连的消息通道并保证在每个消息通道上总是 以时标非减的次序发送事件消息。每个消息通道都有一个f i f o 的输入队列和一个 通道时钟与之相联系，此外还设置有一个输入缓存( i b ) 和一个输出缓存( o b ) 。 输入缓存用于存放相应l p 发来的事件消息，输出缓存则用于存放发送给相应l p 的事件消息。对于某个消息通道而言，当其输入队列为空时，通道时钟的值被设 置为最后所接收的事件消息的时标的大小：否则该通道时钟的值被设置为队列中 的最早的事件消息的时标的大小。模拟开始时，l p 每次从自己的事件队列和具有 最小通道时钟值的消息通道的输入队列中选出时标最小的事件进行处理。当有具 有最小通道时钟值的消息通道的输入队列为空时，则该l p 阻塞等待；只有当该输 入队列装入事件不再为空时l p 才会解除阻塞重新恢复上述处理过程。c m b 算法 通过这种处理方式严格满足因果关系约束，避免了因果关系错误的发生。但是这 样的事件处理方式不能防止模拟进入死锁，因为可能会因某些l p 进入阻塞等待状 态而出现多个l p 互相无限等待的状况。 c m b 算法采用了空消息( n u l lm e s s a g e ) 来避免死锁的出现。当某个l p i 因进 行事件处理产生了向某些l p 发送的事件消息时，c m b 算法会为其余的l p 生成相 应的空消息( n u l l ，t 。u ) 并发送给这些l p ，这些空消息仅是用来进行同步作用的， 不代表任何模拟事件，其目的是l p i 保证肯定不会向这些l p 发送时标小于t n u l l 的 事件消息。因而接收到空消息的l p 可以利用这种消息所带的时标t 肌l i 来推进自己 的局部时钟l v t ，从而达到解除死锁的目的。但采用空消息的方法避免死锁有一 定的局限性，只有在空消息能使各个l p 持续地推进自己的局部时钟，从而使l p 的处理过程能一直进行下去的时候死锁才能被避免。如果当处于死锁状态的各个 l p 之间出现了l p 无法进行局部时钟的时标推进的情况( 这种情况在所模拟的实 际情况中很少出现) ，死锁则无法避免。除了所能解决的死锁情况有限之外，采 第9 页 国防科学技术大学研究生院硕十学位论文 用这种方式的另一个问题在于模拟过程中可能会出现大量的空消息，这会消耗大 量的网络带宽，加大进行同步的通信开销。 为了减少模拟过程中空消息的数量，一些基于按需发送空消息的算法1 2 6 - 2 7 1 被 提出，此外n i c o l 2 8 1 提出了利用未处理事件时标信息的算法。c a i 和t u r n e rt 2 93 0 弓f 入了一种增加了额外信息的空消息算法c a r r i e r n u l lm e s s a g e s ，这种算法通过在空消 息中增加未处理事件时标信息等信息减少了模拟过程中空消息的数量。f u j i m o t o f 3 1 】 指出了未处理事件时标信息在分布并行模拟中的重要性，他认为未处理事件时标 信息的获取程度对模拟性能有着重要的影响。 2 2 2 死锁检测与恢复算法 c h a n d y 和m i s r a 还提出了解决死锁的另一种算法1 3 2 1 。这种算法与基于空消息 的算法的不同之处在于它不是避免出现死锁而是允许死锁的发生。为此该算法提 供了用于检测和从死锁恢复的两种机制，采用类似于分布计算中普遍使用的方法 来检测死锁，并通过对系统中带有最小时标的事件进行处理以恢复死锁，这些机 制的细节如文章 3 2 - 3 3 j 所述。采用死锁检测与恢复算法的优点在于这种算法不使用 空消息进行通信，减少了收发这些同步消息的开销，而且能够处理使用空消息的 算法所不能解决的死锁情况。但这种算法常常导致模拟的顺序执行，降低了事件 处理的并行性，影响了模拟性能。 2 2 3 保守类时间窗口算法 一些研究者如l u b a c h e v s k y l 3 4 - 3 5 】等人提出了依靠l p 在某些模拟时间点进行协 同操作以决定安全事件，并进而处理这些事件的保守类算法。这种算法的主要思 想是为每个l p i 中的事件划定一个模拟时间上的窗口w i ，该窗口所包含的事件以 及与不同l p 的窗口内的事件都是相互独立的，因而包含在各l p 窗口内的事件都 是安全事件，能够被各个l p 同时进行处理。该算法的流程分为两个阶段，首先是 划分窗口阶段，在这一阶段中算法为每个l p i 划分一个事件集合w i ，且对于每个 事件e i w i 其独立于任何e i w j ，j i 。其次为事件处理阶段，各个l p i 以时标非 减的次序对各自窗口w i 中的事件进行处理。该算法的主要困难在于如何确定窗口 的大小以使对事件的划分能够满足上述条件。 2 3 乐观类策略 在乐观类策略中，每个l p 独立地以时标非减的顺序处理目前其各自事件队列 中的事件。由于这类策略没有严格地满足因果关系约束，因此无法防止l p 接收和 第1 0 页 国防科学技术大学研究生院硕士学位论文 处理时标小于l p 局部时钟时标的事件，导致因果关系错误的发生。所以乐观类策 略需要周期性地保存系统的模拟状态，以备以后进行状态的恢复操作。当某个局 部时钟为c i 的l p 收到带有时标t k c i 的事件消息( s t r a g g l e r ) 时，便认为检测到了因 果关系错误的发生。因为s t r a g g l e r 事件的出现表明在模拟时间t k 以后的模拟结果 都有可能是错误的。为了使模拟能够正确地继续进行下去，l p 会将系统的模拟状 态恢复至t k 时刻之前的己保存的正确模拟状态，并消除此期间对其