（计算机科学与技术专业论文）trace驱动并行模拟中的性能优化技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 并行模拟是一种利用并行宿主机平台将模拟任务并行化从而加速性能模拟的 技术，能够较好地满足对大规模计算机系统模拟所需的计算与存储资源。随着未 来并行计算机系统和应用的规模、复杂性等的急剧增加，并行模拟本身的效率也 迫切需要提高。 本文围绕提高计算机体系结构并行模拟效率这一主题，对t r a c e 驱动并行模拟 中逻辑进程的映射与同步技术做了深入分析研究，取得了一些创新性成果。主要 贡献和创新工作包括以下几个方面： ( 1 ) 深入分析了并行模拟框架p o s e ，重点研究了其中的映射策略和同步策 略。对不同的策略采用不同的基准程序进行深入的分析和大量的对比测试，得到 一些具有启发式意义的结论，可为并行模拟中映射与同步技术的优化提供参考。 ( 2 ) 逻辑进程到物理进程的映射对并行性能模拟的开销影响很大，尤其是 对大规模目标并行系统和应用的并行性能模拟。针对t r a c e 驱动的并行性能模拟， 本文提出了t r a c e 信息指导的通信最小化映射方法m i n i c o m ，利用从t r a c e 中提取 的目标应用程序的通信信息，以物理进程间通信最小化为目标，兼顾负载均衡， 生成逻辑进程到物理进程的映射。测试结果表明，相对于块映射和循环映射方式， m i n i c o m 可提高并行模拟性能最多达1 4 7 。 ( 3 ) 针对有规则交互应用程序并行性能模拟中逻辑进程到物理进程的映射 问题，在m i n i c o m 基础之上提出了a 2 l p 3 m 方法，根据不同的宿主机规模、不同 的目标机规模、不同的目标应用参数设置，从所有循环块映射中选取通信最小化 的映射方式。实验表明，相对于常见映射方法a 2 l p 3 m 提高了映射方法的可扩展 性并最多可使并行模拟器性能提高达1 6 2 。 ( 4 ) 针对s m p 集群宿主机平台上的并行性能模拟中逻辑进程到物理进程的 映射问题，在m i n i c o m 基础上提出了t p s m p l p 3 m 方法，能够利用从t r a c e 中提 取的逻辑进程间的通信信息和s m p 集群的拓扑信息找到高效的映射方法。实验表 明，t p s m p l p 3 m 可以提高模拟性能达2 0 2 。 ( 5 ) 针对现有自适应乐观同步策略中存在的调整滞后问题，提出了基于事 件触发度的实时自适应同步算法，能够同时利用的历史统计信息和从t r a c e 文件中 提取的关于事件触发度的信息，使得关键事件得到及时调度，从而减少模拟时间。 实验表明，该同步算法可提高模拟性能最多达1 4 2 。 ( 6 )在模拟时间窗口经过精心修正后，固定时间窗口乐观同步策略能够取 得比自适应乐观策略更好的模拟性能，特别是对于迭代并行应用。基于此，提出 了一种适合于迭代应用模拟的混合同步策略，即采用自适应同步策略调整窗口到 第i 页 国防科学技术大学研究生院硕士学位论文 慈琵形添_ 再莱用固定眄词窗口同步策略执行后续模拟，该方法能够汲取两类方 法的优点，可提高并行模拟性能最多达1 8 3 。 主题词：并行性能模拟，t r a c e 驱动模拟，同步策略，映射策略，通信最小化， 事件触发度 第i i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t p a r a l l e ls i m u l a t i o ni sa l li m p o r t a n tt e c h n i q u et os p e e d u ps i m u l a t i o n ，w h i c hm a k e s f u l lu s eo fp a r a l l e lh o s tm a c h i n e st op a r a l l e l i z et a s k sa n dt h u sa c c e l e r a t e ss i m u l a t i o n n 啪u g hp a r a l l e ls i m u l a t i o n ，t h ed e m a n df o rc o m p u t i n ga n dm e m o r yr e s o u r c e sc a nb e b e r e rs a t i s f i e dw h e ns i m u l a t i n gl a r g e s c a l ec o m p u t e rs y s t e m s w i t ht h ei n c r e a s i n g c o m p l e x i t yo ft a r g e tc o m p u t e rs y s t e m sa n dt a r g e ta p p l i c a t i o n s ，t h ee f f i c i e n c yo fp a r a l l e l s i m u l a t i o nn e e d si m p r o v i n gu r g e n t l y a i m i n ga tb o o s t i n gt h ee f f i c i e n c yo fp a r a l l e ls i m u l a t i o n , w er e s e a r c ho i lt h ek e y t e c h n i q u e so ft r a c e - d r i v e np a r a l l e ls i m u l a t i o n ，i n c l u d i n gt h em a p p i n go fl o g i c a l p r o c e s s e st op h y s i c a lp r o c e s s e sa n ds y n c h r o n i z a t i o ns t r a t e g i e s m a i nc o n t r i b u t i o n sa r e l i s t e da sf o l l o w s f i r s t l y ，w ea n a l y z ea l lo b j e c t - o r i e n t e dt y p i c a lp a r a l l e ls i m u l a t i o ne n v i r o n m e n t - p o s e ，f o c u s i n go ni t sm a p p i n ga n ds y n c h r o n i z a t i o ns t r a t e g i e s ，b ym a k i n gp l e n t yo f a n a l y s i sa n dd o i n gl o t so ft e s t sf o rd i f f e r e n tb e n c h m a r k s s o m eh e u r i s t i cc o n c l u s i o n s ， w h i c hc a np r o v i d eu s e f u lr e f e r e n c e sf o rt h e o p t i m i z a t i o n o fm a p p i n ga n d s y n c h r o n i z a t i o ni np a r a l l e ls i m u l a t i o n , h a v eb e e nr e a c h e d s e c o n d l y ，m a p p i n gs t r a t e g i e sf r o ml o g i c a lp r o c e s s e st op h y s i c a lp r o c e s s e sa r eo f g r e a ti m p o r t a n c et ot h ep e r f o r m a n c eo fp a r a l l e ls i m u l a t i o n , e s p e c i a l l yf o rl a r g es c a l eo f t a r g e ts y s t e m sa n da p p l i c a t i o n s a i m i n ga tm i n i m i z i n gt h en u m b e ro fc o m m u n i c a t i o n b e t w e e np h y s i c a lp r o c e s s e sa n db a l a n c i n gl o a d s ，w ed e v e l o pat r a c e - g u i d e dm a p p i n g m e t h o dc a l l e dm i n i c o mw h i c hc a r lg e n e r a t em a p p i n gb ye x t r a c t i n gt h ec o m m u n i c a t i o n i n f o r m a t i o no ft a r g e ta p p l i c a t i o n s e x p e r i m e n t a lr e s u l t ss h o wt h a tm i n i c o mc a nb o o t p e r f o r m a n c eb y u pt o14 7 ，c o m p a r e dw i t hc o m m o nm a p p i n gm e t h o d s t h i r d l y ，w ep r o p o s ea n o t h e rm i n i c o mb a s e dm a p p i n gm e t h o dc a l l e da 2 一l p j mt o s o l v em a p p i n g sp r o b l e mi nt h ep a r a l l e ls i m u l a t i o no ft a r g e ta p p l i c a t i o n sw i t hr e g u l a r c o m m u n i c a t i o np a t t e r n s i ts e l e c t st h em a p p i n gw i t hm i n i m a lc o m m u n i c a t i o nf r o ma l l b l o c k c y c l i cm a p p i n gs t r a t e g i e sa c c o r d i n gt ot h en u m b e ro fh o s ta n dt a r g e tm a c h i n e s a n dt h es e t t i n g so ft a r g e ta p p l i c a t i o n s s i m u l a t i o np e r f o r m a n c ec a l lb ei m p r o v e db y 1 6 2 a tm o s t f o u r t h l y ，f o rt h eh o s tp l a t f o r mo fs m pc l u s t e r ，a n o v e lm e t h o dn a m e d t p s m p l p 3 mi sa l s op u tu pw i t hb a s e do nm i n i c o ma n da 2 l p 3 m i tc a l lm a k ef u l lu s e o ft h ec o m m u n i c a t i o ni n f o r m a t i o no fl p se x t r a c t e df r o mt r a c ef i l e sa n dt o p o l o g y i n f o r m a t i o no fs m pc l u s t e r st og e n e r a t ee f f i c i e n tm a p p i n g e x p e r i m e n t a lr e s u l t ss h o w t h a tm i n i c o mc a l lb o o tp e r f o r m a n c eb yu pt o 2 0 2 ，c o m p a r e d 州t l lt r a d i t i o n a l m e t h o d s f i f t h l y ，i no r d e rt os o l v et h ep r o b l e mo fp o s t p o n e da d j u s t m e n to ft h ee x i s t i n g a d a p t i v es y n c h r o n i z a t i o ns t r a t e g i e s ，w ep r o p o s ear e a l t i m ea d a p t i v es y n c h r o n i z a t i o n 第i i i 页 国防科学技术大学研究生院硕士学位论文 s t r a t e g yw h i c hc a r lt a k ea d v a n t a g eo fs t a t i s t i c a li n f o r m a t i o na n de v e n tt r i g g e rd e g r e e f r o mt r a c ef i l e s t h u sk e ye v e n t sc a l lb es c h e d u l e di nt i m ea n dt h es i m u l a t i o nt i m ec a l l b er e d u c e d e x p e r i m e n t a lr e s u l t ss h o wt h a ts i m u l a t i o np e r f o r m a n c ec a nb eb o o t e db y u p t o1 4 2 f i n a l l y ，f i x e d s i z e d t i m e - w i n d o w o p t i m i s t i cs y n c h r o n i z a t i o ns t r a t e g i e s c a n o u t p e r f o r ma d a p t i v eo n e sw h e nt h es i z e o ft i m ew i n d o wh a sb e e ns e tp r o p e r l y ， e s p e c i a l l y f o ri t e r a t i v e p a r a l l e la p p l i c a t i o n s w ed e s i g n a h y b r i da d a p t i v e s y n c h r o n i z a t i o ns t r a t e g yb a s e do nt h ea b o v e m e n t i o n e do b s e r v a t i o n i tf i r s t 砌u s t st h e w i n d o ws i z et oas t a b l es i z eu s i n ga d a p t i v es t r a t e g ya n dt h e nt h ef i x e dt i m ew i n d o ww i l l b eu s e di nt h er e s to fs i m u l a t i o n n l i sm e t h o dc a nc o m b i n et h em e r i t so ff l x e d - s i z e d t i m e w i n d o wo p t i m i s t i cs y n c h r o n i z a t i o ns t r a t e g i e sa n da d a p t i v eo n e s ，t h u si m p r o v i n g s i m u l a t i o np e r f o r m a n c eb y18 3 a tm o s t k e yw o r d s ：p a r a l l e lp e 哟r m a n c es i m u l a t i o n ，t r a c e - d r i v e n s i m u l a t i o n 。 s y n c h r o n i z a t i o ns t r a t e g i e s ，m a p p i n gs t r a t e g i e s ，m i n i m u mc o m m u n i c a t i o n ，e v e n t t r i g g e rd e g r e e 第i v 页 国防科学技术大学研究生院硕士学位论文 表目录 表2 1p c c 实验环境配置13 表3 15 t 实验环境配置2 7 表3 2 映射方式规律观察2 9 表4 1各种自适应协议与它们的特征4 2 表4 2 事件调度粒度的变化4 9 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图2 1 3 图2 1 4 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图目录 计算机体系结构模拟过程2 t r a c e 驱动的模拟过程。3 并行模拟框架与模拟模型l1 p o s e 原理图1 2 p o s e 中的两种映射策略1 2 b i g s i m 组件图1 3 两类基准测试程序1 4 两种不同应用输入时的模拟时间1 4 两种不同应用输入时的通信开销1 5 p o s e 中同步策略的步进操作16 基本乐观同步策略选择下一事件1 7 乐观同步策略引入时间窗1 7 窗口增量值随目标机规模变化情况图2 1 窗口增量值随问题规模变化情况2 1 宿主机规模不同时各同步开销占有的比重2 2 两种策略的比较2 2 改进后的t r a c e 驱动模拟2 5 通信权重矩阵2 5 通信权重矩阵生成过程2 6 映射方式生成算法2 7 j a c o b i 3 d 计算原理2 7 三种映射方式的模拟耗费时间2 8 三种映射方式p p 间传递的消息数2 8 改进前后映射策略对比2 9 扩展后两种映射方式的性能表现3 0 两种映射方式的相对加速比3 0 不同映射时宿主机间交互次数3 1 h p l 程序设置改变时p p 间的交互次数3 2 l p 到p p 映射生成伪代码3 3 优化前后两种映射的对比。3 3 优化前后的相对加速比3 4 p p 间消息传递数量3 4 第l v 页 国防科学技术大学研究生院硕士学位论文 图3 1 7 图3 1 8 图3 1 9 图3 2 0 图3 2 l 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 l 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 1 7 图4 1 8 一种两阶段的映射方法3 5 映射l p 到p p 的伪代码3 6 从通信权重矩阵生成映射的子过程3 6 优化前后两种策略的比较3 7 相对加速比3 7 离散事件模拟系统结构3 9 并行模拟模型4 0 乐观策略中逻辑进程的体系结构图4 1 保守策略与乐观策略之间的权衡4 1 基于时间窗口的白适应同步策略4 4 乐观同步策略执行时空图4 5 实时自适应同步策略实现框图4 6 改进后实时时间窗口调整策略4 7 平均触发度的收集流程4 8 改进前后触发度计算开销的变化4 9 改进前后模拟时间的变化4 9 j a c o b i 3 d 模拟过程中的时间窗口调整5 0 迭代应用的基本模式5 1 混合同步策略模型5 1 混合自适应同步的核心实现5 3 优化前后事件调度粒度的变化5 3 改进前后回滚次数的比较5 4 改进前后模拟时间的比较5 4 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签名： 魄；秒刁年p 月力日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 研究背景 工艺的进步和体系结构的发展促使计算机系统的规模和复杂度剧增，而人们 追求高计算能力的步伐从未减缓。这与短周期、低成本的系统开发需求间产生了 尖锐的矛盾，并促使计算机系统性能评测在体系结构功能验证和性能度量中愈显 重要【l j 。通常情况下，研究人员需要对系统进行全面、深入的性能评测，从而在现 有技术条件和成本约束下寻找适合于应用需求的设计方案。 在计算机体系结构设计中，解析建模( a n a l y t i c a lm o d e l i n g ) 和模型模拟 ( s i m u l a t i o n ) 是两种常用的性能评测方法。其中，解析建模采用数学原理建立模 型，如：概率模型、排队模型、马尔可夫模型等，用若干参数来表示影响程序性 能的因素，然后通过对程序结构进行静态分析，估计这些参数的值，进而预测程 序性能【2 j 。然而，该方法不能捕捉系统行为的动态特征，且倾向于对目标系统作大 量的简化假设。模拟方法则能够根据所需的精度要求对系统建模，从而支持层次 化设计和体系结构动态行为的研究，具有高度的灵活性【3 1 。因此，模拟方法被广泛 的应用于体系结构设计、测试和评估中。 模拟技术通常是使用软件的方式来模拟计算机系统硬件在体系结构级别的功 能和性能特性【4 j ，从而导致模拟运行时间很长。为了评估计算机系统的性能，很多 组织不断发布更加复杂的基准性能测试程序，最终使得串行模拟器的运行速度不 能满足实际需求。并行性能模拟是一种利用并行宿主机平台将大规模模拟任务并 行化的加速性能模拟技术，能够有效缓解传统串行模拟方法效率低下的问题【5 1 ，能 够充分利用并行宿主机丰富的计算资源、存储资源及快速缓存。随着多处理器系 统和基于高速网络的工作站集群变得普及，并行化性能模拟也日俱魅力。此外， 并行计算机体系结构模拟中存在大量可用的并行性，充分挖掘这些潜在的并行性 可加速模拟执行州。 然而，随着未来目标并行系统和应用的规模、复杂性等的持续急剧增加，并 行模拟本身的效率也迫切需要提高，例如，i b m 的超级计算机r o a d r u n n e r 含有多 达1 2 9 6 0 0 个计算核一0 7 j ；2 0 0 9 年1 0 月国防科技大学发布的“天河一号 千万亿 次超级计算机系统则包含结构复杂规模巨大的计算阵列、加速阵列、服务阵列等【引， 模拟如此庞大规模的并行目标系统无疑对并行模拟本身的效率提出了更高的前所 未有的挑战。因此，本文就围绕着提高计算机体系结构并行模拟效率这一主题， 对并行模拟中逻辑进程的映射与同步策略展开深入的调查、分析和研究，取得了 一些有意义的成果。 第1 页 国防科学技术大学研究生院硕士学位论文 1 2 计算机系统性能模拟基础知识 为便于叙述，特别地对本领域中的重点概念进行阐述。 ( 1 ) 计算机体系结构模拟与仿真 4 1 计算机体系结构模拟( s i m u l a t i o n ) 是指使用软件或者硬件原型的方法来模拟 某种体系结构计算机系统的计算过程，其目标是对未来计算机体系结构的功能或 者性能进行预测和分析，其重点是研究计算机执行计算任务的过程。 计算机体系结构仿真( e m u l a t i o n ) 是使用软件或者硬件原型的方法来模仿某 种体系结构计算机的计算结果，其目标是在另一平台上重现一个已有计算机系统 的功能，重点是确保某个计算任务在另一平台上得到与原系统一样的计算结果， 计算任务执行的过程不是主要的关注目标。 一般来说，在计算机体系结构模拟中包含了部分计算机体系结构仿真。体系 结构模拟中首先要得到正确的输出结果，在此基础上研究得到输出结果的过程。 因此，本文在没有特别说明的情况下统称为计算机体系结构模拟。 计算机体系结构模拟过程通常是基于模拟器( s i m u l a t o r ) ，该模拟器一般用 软件方法实现了机器的体系结构，能够模拟机器内部操作。模拟器以执行程序、 经过某种编译变换得到的程序或者程序执行所产生的踪迹( t r a c e ) 数据为输入， 虚拟地执行它们，并记录和统计性能事件，从而获得一些与体系结构相关的性能 数据【2 1 。其中，运行模拟器的机器称为宿主机( h o s tm a c h i n e ) ，输入到模拟器中 的并行应用称为目标应用( t 鲫辩a p p l i c a t i o n ) ，要建模的尚不可用或不存在的并 行计算机称为目标机( t a r g e tm a c h i n e ) 9 1 。其关系如图1 1 所示。 图1 1 计算机体系结构模拟过程 ( 2 ) 踪迹驱动模拟 基于t r a c e 的性能模拟是一种主流的体系结构模拟技术。它是将一工作负载执 行产生的所有信息作为模拟器的输入，从而模拟某种体系结构处理器的性能。如 图1 2 所示，假设要模拟执行的工作负载为w ，该程序负载运行的目标环境为t ， 则在环境t 中模拟执行w 的问题可以分为两个子问题：踪迹信息的生成和踪迹信 息的模拟。踪迹信息生成的环境为g ，则当在g 中执行w 时所发生的所有事件均 第2 页 国防科学技术大学研究生院硕士学位论文 被记录下来，比如：计算和通信发生时间等，这些记录被称为踪迹信息( t r a c e ) ， 可看作是应用程序的特征化表示。然后，模拟器将踪迹信息作为输入，从而在目 标环境中执行w 的行为1 1 0 1 。基于t r a c e 的性能模拟比较简单且容易理解；相应的 模拟器也易于调试；实验数据可以重现，因为使用同一踪迹信息，在不同的模拟 执行中，模拟器的输入、输出数据不会发生变化。因此，本文重点研究t r a c e 驱动 的并行性能模拟。 图1 2t r a c e 驱动的模拟过程 1 3 研究现状 1 3 1 映射策略的研究现状 1 3 1 1 映射策略概述 将一个计算分解成许多小的任务，再把它们分配到不同的处理器中以便并行执 行是并行算法设计中的两个关键步骤。映射( m a p p i n g ) 指的是子任务到物理进程 ( p h y s i c a lp r o c e s s ，p p ) 的指定u 。在并行模拟中，整个模拟被分解成大量的逻辑 进程( l o g i c a lp r o c e s s ，l p ) ，l p 到p p 的指定即为并行模拟中的映射。 并行模拟中总是存在由于通信量过大或者负载不均衡而导致的模拟性能下降 问题，而且当系统规模增大时这些问题所产生的后果还会更加严重。因此，如何 映射逻辑进程到物理进程进行模拟显得尤为重要，是进行并行模拟研究不可缺少 的一个环节。 好的映射方法应该设法把相互独立的任务映射到不同的进程以获取最大的并 行度；好的映射方法应该确保可用进程来执行关键路径上的任务，以使得任务变 成可执行的时候总计算时间最短；好的映射方法应该映射相互交互的任务到同一 个进程以便最小化进程间的交互【1 1 1 。然而，在实际的并行应用中，这些目标往往 第3 页 国防科学技术大学研究生院硕士学位论文 是矛盾的，关键是要找到整体并行性能间的最佳平衡。 1 3 1 2 现有的映射策略 映射策略在并行计算领域已得到了广泛深入的研究。图1 3 显示了现有映射策 略的分类情况：一类策略能够得到最优解；另一类则能够得到近似解【1 2 】。 、 m 孟q u i u e p h m 嘶么、删础 b 啪及删c t h e o r y w ? 弋枷卜i t e r a t i v e g r e e 打删cw e m n c md v a n db o u n d p r o g r a m m i n gh o m o m o 甲h i s mp a r t i t i o n i n g 。 1 、 图1 3 映射策略分类 文献中所提及的不同的映射策略是基于下面的方法：数学规划【1 3 】【1 4 】、图论 【1 5 】【1 6 】【1 7 】、排队论【1 8 】。这些方法虽然能够得到最优解，但通常非常耗时( 最优映射 求解已被证明是n p 难问题【1 9 1 ) 。为了解决搜索耗时的问题，学术界提出了两种解 决方案：一种方案是基于上述最优方法的近似算法 2 0 l ；另一种方案是采用启发式 方法【2 。其中采用启发式的映射策略又可分为贪婪的和迭代的两种。近几年的多 数研究都集中在启发式算法的研究上，使用的方法可以分为两大类，一类是采用 通用的优化求解算法，如遗传算法、模拟退火算法等进行求解，另一类是提出专 门的启发式求解算法。已有的相关算法种类众多，它们所基于的模型各有不同， 分别面向不同类型的系统，如消息传递型或共享存储型、同构型或异构型等；具 有不同的分配调度的目标和策略，如追求负载均衡、追求最短执行时间、追求 占用最少资源等；适用于不同并行粒度的应用程序，如进程线程级、迭代级、 指令级等【2 2 1 。 为了减少映射算法所带来的工作负担，多数并行性能模拟器如b i g s i m 2 3 】【2 4 1 ， m p i s i m t 5 】【2 5 】等的设计常采用简单的方式将模拟任务映射到各个物理进程上。比较 常用的映射策略有四种：随机映射、块映射、循环映射及自定义映射【2 6 1 。 ( 1 ) 随机映射 随机映射是将逻辑进程随机的分配到各个物理进程上。真正意义的随机映射 具有两个重要性质：均匀性和独立性。所谓均匀性是指如果在模拟系统中有m 个 l p 和n 个p p ，而且m 非常大，则每个p p 上分到的l p 期望值为m n 。所谓独立 第4 页 国防科学技术大学研究生院硕士学位论文 性是指一个l p 被分配到某个p p 上的概率与前面已经分配好的l p 无关。 ( 2 )块映射 块映射也称之为平均分配，按照连续的块的形式分发逻辑进程。块映射策略的 特点是将模拟任务平均的分配到各个物理进程上。这里的平均分配的含义有两种： 一是逻辑进程数量的平均分配，即将系统中所有的逻辑进程按照个数统计后，平 均分配到各个物理进程上；二是逻辑进程类型的平均分配，由于一般并行模拟系 统的结构复杂，划分好的模拟子任务类型多样，特点各异，如果将特点相近的模 拟任务进行归类，然后将其平均分配，这样就可以在一定程度上缓解负载不平衡 的程度。 ( 3 )循环映射 循环映射也称之为分散分配，按照发牌的方式分发逻辑进程到物理进程。这种 映射方式适合于逻辑进程间通信具有树形结构的并行模拟。 ( 4 )自定义映射 自定义映射是根据自定义的映射标准将逻辑进程分配到物理进程。这种映射 方式常常是在用户得到映射方式后，以文件的形式将所生成的映射输入到模拟的 初始化阶段中。这种映射方式给用户提供了使用的接口，具有高度灵活的特点。 从严格意义上讲，前面三种映射策略可看做自定义映射的特例。 现有并行模拟器常忽略输入负载的通信模式而采用单一的映射策略，生成不 合理的映射，给模拟宿主机网络带来额外的压力，进而导致并行模拟中大量回滚、 取消操作的产生，使得模拟性能恶化。因此，开拓新思路，基于t r a c e 驱动并行性 能模拟中出现的新特点，构建简单高效的映射方法，进一步提高模拟效率仍值得 深入的研究和探讨。 1 3 2 同步策略的研究现状 1 3 2 1 同步策略概述 并行离散事件模拟( p a r a l l e ld i s c r e t ee v e n ts i m u l a t i o n ，p d e s ) 将逻辑进程分 散到各个物理进程上，通过协同计算共同完成一个系统的模拟过程。为了保证模 拟结果的正确性不受破坏，必须采取某种机制，使得并行模拟的各子系统之间能 够协调向前推进，得到和串行模拟同样的结果。这就是p d e s 中的同步机制。 传统的单机串行模拟将所有模拟事件按照其时间戳非降序原则放入事件列 表，然后按序模拟执行所有事件，直至所有事件计算完毕，模拟正常结束，或由 于出现异常情况导致模拟被迫提前终止。由于是单机模拟，所以无论出现何种情 况，在模拟过程中都将按照时间戳非降序计算所有事件。也就是说，模拟事件的 有序性不会遭到破坏，己经模拟完的结果总是正确的。 第5 页 国防科学技术大学研究生院硕士学位论文 然而在并行模拟时，多个逻辑进程分别在不同的处理器上模拟。在这种情况 下，不仅要确保每个子系统内的所有事件在计算过程中满足非降序模拟条件，而 且要确保整个系统的所有事件在总的模拟过程中满足非降序模拟条件。由于各个 子系统所处的计算环境很难完全相同，使得系统中所有事件的整体有序模拟难以 保证。同时，它们之间存在的消息传递在网络延迟下又会加剧予系统内部模拟事 件的无序性。这两种情况都会使模拟产生错误的结果。为了避免这一问题，在进 行并行模拟时，必须提供同步机制，对整个系统中所有事件的计算过程进行协调， 使之最终按有序规则进行模拟，从而保证模拟结果的正确性。 1 3 2 2 现有的同步策略 在并行模拟中当且仅当每个l p 处理的事件按时间戳非递减的方式排列，才能 保证无因果关系错误，这也称为本地因果关系约束。为在并行离散事件模拟中满 足该约束，需要在不同l p 之间进行同步。研究人员针对同步策略进行了大量研究， 提出的一些同步策略。这些策略大致上可分为两类：保守同步策略和乐观同步策 略【2 7 】。前者严格避免乱序模拟事件的发生。而后者则尽可能地推进各子系统的模 拟进度，同时提供检测功能，当发现某子系统出现乱序模拟时，通过回滚机制取 消错误计算的所有事件，并将模拟进度恢复至错误计算处再次进行模拟。 c h a n d y m i s r a - b r y a n t ( c m b ) 1 2 8 】【2 9 】算法是一个典型的保守同步算法：当且仅当 l p 能够保证事件是“安全”的时候才允许处理该事件【3 0 】【3 l 】，所谓具有时间戳t 的 事件是安全的，指的是不可能有时间戳早于t 的事件到达该l p 。为确定事件是否 “安全 ，l p 之间需要进行全局同步，这会引起死锁问题，所以避免死锁或是死 锁探测及解决是保守算法必须具备的功能。保守策略的缺点是l p 之间的全局同步 开销较大，特别是在模拟大规模系统时，不能充分利用模拟中可用的并行性，l p 可能会经常阻塞。乐观同步策略最早的工作是由j e f f e r s o n 和s o w i z r a l 所提出来的 时间偏差协议( t i m ew a r p ) 1 3 2 1 1 3 3 1 。该类策略允许l p 不考虑事件安全性便执行事件 队列中时间戳最早的事件。当发生因果关系错误时，需要通过回滚机制进行处理。 因此，一方面l p 需要周期性地运行检查点操作，保存自己的模拟状态，若出现因 果关系错误，模拟会回滚到早期的检查点，重新执行被回滚的事件，并通过发送 反消息以更正其他l p 的状态。另一方面，也需要适时地将用于保存检查点状态的 内存释放掉，以免内存耗尽。 保守策略与乐观策略的相对优越性直是学术界争辩的焦点。然而，学者们一 致认为证明一种协议优于另一种协议是比较困难的。于是他们采用了介于纯保守 ( 阻塞一恢复) 与纯乐观( 前瞻一回滚) 两极端之间的中间路线，此类协议称之 为混合策略。混合策略大体上可分为两类：一类是在保守策略中引入乐观因素， 如m e h l 的前瞻执行协议【3 4 1 、s t a i n m a n 提出的呼吸时间桶算法【3 5 】、l u b a k e v s k y 扩 第6 页 国防科学技术大学研究生院硕士学位论文 展的有界延迟协议【3 6 j 等；另一类是将阻塞引入到乐观策略中，如s o k o l 等人提出 的m t w 协议【3 7 】、m i m d i x 系统中采用的随机重同步的思想【3 8 】、s t e i n m a n 提出的 呼吸时间偏差协议( b t w ) 【3 9 】、c o m p o s i t ee l s a 协议1 4 0 、r a j a e i 等人提出的局部 时间偏差协议【4 l 】等。 自适应策略本质上是一种混合同步策略，但它可以随着系统的变化，动态的 修改其执行的方式，使自适应策略可贴近任何一种策略。r e y n o l d s 在1 9 8 8 年最初 阐述了自适应协议的重要作用【4 2 】。他定义“自适应性”为逻辑进程能够基于“选 定的模拟状态知识”动态的调整一个或者多个控制参数，其目标是最小化并行模 拟的执行时间。基于此，学术界已经提出了大量的自适应同步策略。根据自适应 决策仅仅依赖于一个l p 的局部状态还是所有l p 的全局状态，可以宽泛的将自适 应协议分为两类： 一类协议是基于局部状态 r e i t h e r ，w e i l a n d ，j e f f e r s o n 是最早提出了基于惩罚的限制机制( p e n a l t yb a s e d t h r o t t l e ) ，即：最近经历回滚的l p 将遭受惩罚，这种方法是在j p l 时间偏差的 操作系统t w o s 中实现，却没有比t i m ew a r p 协议获得更好的性能1 4 3 ； f e r s c h a 和l u t h i 提出了一种类似于自适应时间偏差协议( a t w ) m 】却更复杂的方法，基 于随机代价期望函数( p c e f ) ，使用包含回滚概率和代价的显式代价模拟代替逻 辑响应函数，实验证明该方法能够超过时间偏差协议【4 习；m a s e a r e n h a s 等人提出了 与f e r s c h a 和l u t h i 相似的模型，然而该模型假设到达消息间隔在真实时间和模拟 时间上的分布是独立的，因为自适应机制本身存在实现开销，一些应用实例难以 获得良好的性能提升【删；f e r s c h a 提出了一种随机自适应直接乐观度控制( p a d o c ) 协议，实质上与上述协议是相似的，区别之处在于它增加了概率部件并增量的计 算阻塞窗口7 1 。每个逻辑进程维护了在最近的过去到达消息的模拟时间差值的记 录，用来预测即将到达消息的时间戳，该方法被证明能够在p e t r i 网模拟且在负载 平衡时能够超过时间偏差协议；p