（计算机应用技术专业论文）并行逻辑模拟中容错技术的研究.pdf

上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 摘要 在使用硬件描述语言设计数字电路的过程中，模拟是非常重要的一个环节， 通过模拟可以实时反馈设计结果，使用户发现设计中存在的问题。但是随着集 成电路设计规模的不断扩大和复杂度的日益增长，传统的串行模拟方法! e t 益成 为设计中的瓶颈。并行模拟由于在提高模拟速度方面有着巨大的潜力，得到了 越来越多的关注。但在并行环境中运行，错误发生率上升是难以避免的，会给 系统性能带来巨大的影响。因此，如何实现容错就成为并行逻辑模拟领域中 个急需解决的问题。 本文介绍了并行逻辑模拟的原理、系统组成和影响模拟性能的因素，论述 了和容错密切相关的时问偏差协议，此外针对分布式系统中实现容错会涉及的 若干问题以及常用的解决技术给予了简单介绍。 本文在对并行逻辑模拟系统的特殊性进行分析后，提出了针对系统特点的 特别容错方案可恢复时间偏差机制。与常规容错实现不同，它利用系统本 身就存在的大量数据冗余，用户透明地实现容错，最大化地降低容错给系统带 来的负载。该方案包括数据保存和系统恢复两个部分，涉及检查点算法选择、 保存内容筛选等各个方面。文中给出了具体的设计流程并对其正确性给予了证 明。 最后，通过自行设计和丌发的并行逻辑模拟平台，在高性能集群机上，对 容错功能的实现进行了测试。实验结果表明，作者提出的容错方案可以有效地 解决系统中存在的故障问题，弥补了系统在这方面的欠缺。 关键字：逻辑模拟；并行逻辑模拟系统；容错；可恢复时间偏差机制 上海大学硕士学位论文 ! 竺! 型塑! 型! ! 堕! ! ! ! ! ! ! g 墅! ! 竺! 型 a b s t r a c t s i m u l a t i o ni sa ne x t r e m e l yi m p o r t a n ts t e pd u r i n gt h ed e s i g no fd i g i t a lc i r c u i t s u s i n gv h d l i tc a nb eu s e dt of e e d b a c kt h er e s u l to fd e s i g nt i m e l ya n df i n dt h e f l a w s e x i s t i n g i nt h e d e s i g n a st h es c a l ea n d c o m p l e x i t y o fv l s is y s t e m c o n t i n u o u s l yi n c r e a s e s ，t r a d i t i o n a ls e q u e n t i a ls i m u l a t i o nb e c o m e st h eb o t t l e n e c ko f t h ed e s i g n p a r a l l e ll o g i cs i m u l a t i o nh a sa t t r a c t e dm o r ea n dm o r ea t t e n t i o nf o ri t s p o t e n t i a lo fs p e e d i n gu pt h es i m u l a t i o n p l e n t yo fe f f o r t sh a v eb e e nm a d et oi m p r o v e t h ep e r f o r m a n c eo fp a r a l l e ll o g i cs i m u l a t i o n h o w e v e r ，t h ef a u l tr a t eo ft h ep a r a l l e l s i m u l a t i o ni so nt h er a i s er a p i d l yw h i c hw i l la f t 、e c tt h ee f f i c i e n c yd r a m a t i c a l l y h o w t or e a l i z et h ef a u l tt o l e r a n c ei ns u c he n v i r o n m e n ti sb e c o m i n gav e r yi m p o r t a n tp a r t i np a r a l l e ls i m u l a t i o nf i e l d t h i st h e s i si n t r o d u c e st h et h e o r yo f p a r a l l e ll o g i cs i m u l a t i o nm a dc o m p o n e n t so f t h ew h o l es y s t e m b e s i d e s ，i ta n a l y z e st h ef a c t o r sw h i c hw i l la f f e c tt h ee f f i c i e n c yo f s i m u l a t i o ng r e a t l y f u r t h e r m o r ei ti n t r o d u c e st h et i m ew a r pp r o t o c o lw h i c hi sc l o s e l y c o n n e c t e dw i t ht h ef a u l tt o l e r a n c ef u n c t i o n a l s o ，i n t r o d u c t i o no fp r o b l e m sa n d r e s o l v i n gm e t h o d sw h i c ha r eu s u a l l yu s e di np a r a l l e le n v i r o n m e n ti sg i v e ni nt h i s p a p e r as p e c i a ls c h e m e - - - r e c o v e r a b l et i m ew a r pm e c h a n i s mi sc o m eu pa f t e rt h e a n a l y s i so ft h ep a r t i c u l a r i t yo ft h ep a r a l l e ll o g i cs i m u l a t i o ns y s t e m t h i ss c h e m ei s d i f f e r e n tf r o mn o r m a lf a u l tt o l e r a n c es c h e m e t h i sm e c h a n i s mc a nr e a l i z ef a u l t t o l e r a n c ef u n c t i o nw i t h o u ta d d i n gt o om u c hl o a dt ot h es y s t e mf o ri tf u l l ym a k e su s e o ft h ed a t ar e d u n d a n c yt h a ta l r e a d ye x i s t si nt h en o r m a lp a r a l l e l l o g i cs i m u l a t i o n s y s t e m t h es c h e m ec a nb ed i v i d e di n t ot w op a r t s ：d a t as a v i n ga n ds y s t e mr e s t o r a t i o n w h i c hi n c l u d ec h o i c eo f c h e c k p o i n ta l g o r i t h m 、a n a l y s i so fs a v i n gc o n t e n t sa n ds oo n f o r t h e r m o r e ，d e t a i l e df l o wo fd e s i g na n dv e r i f i c a t i o no ft h i sm e c h a n i s ma r ea l s o g i v e ni nt h i st h e s i s f i n a l l y , o n t h e p a r a l l e ls i m u l a t i o np l a t f o r md e v e l o p e db yt h ea u t h o r ， e x p e r i m e n t sa r eg i v e n t h et e s tr e s u l ts h o w st h a tt h em e t h o dd e s i g n e di nt h i st h e s i s c a nb eu s e dt or e a l i z ef a u l tt o l e r a n c ef u n c t i o ne f f i c i e n t l yw h i c hw i l lc o m p e n s a t et h e d e f i c i e n c yo ft h eo r i g i n a ls y s t e m k e y w o r d s ：l o g i cs i m u l a t i o n ；p a r a l l e ll o g i cs i m u l a t i o ns y s t e m ；f a u l tt o l e r a n c e r e c o v e r a b l et i m ew a r pm e c h a n i s m 原创性声明 本人声明：所呈交的沦文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：揣日期瑚i f 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布沦文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：玉鉴 导师签名：翌选日期 b 乃i 、 上海大学硕十学位论文 旦! ! ! 塑! ! ! ! ! ! ! 堕! ! 堕! ! ! ! g 型坐- 坚! 塑 第一章前言 随着超大规模集成电路( v l s iv e r yl a r g es c a l ei n t e gr a t i o n ) 集成度的增加，设计 v l s i 数字系统的复杂度也迅速增加，靠人工检查设计中的错误已经成为不可能 的事情。此外，为了降低成本，缩短研制周期，不允许产品投产以后再做任何逻 辑改动，所以必须把所有错误消灭在产品投产以前。使用逻辑技术，利用计算机 实现逻辑电路的验证和检查，是当今数字系统设计必不可少的步骤。 但随着集成电路规模和复杂度的迅速增长，模拟日益成为设计中的瓶颈。据 统计，在集成电路的设计过程中，9 0 以上的时间用于电路模拟。并行技术由于 在提高模拟速度方面具有巨大的潜力，学术界围绕如伺提高并行逻辑模拟的性能 展开了大量研究。钊对分布式模拟系统易出错的现状，作为一种能够挽救出错时 系统模拟结果，从而节约模拟时间，提高模拟性能的方法一容错技术成为了一 个重要的研究领域。 1 1 集成电路设计与v h d l 语言 迈进2 1 世纪，网络与通信技术、多媒体技术以及新型体系结构计算机设计， 随时都在向系统级芯片( s o cs y s t e m o n c h i p ) 的设计与制造提出新的挑战，要求 设计q k 能够更快更好的设计出性能更优良、功能更完美、更复杂的 a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 产品。这迫使我们必须研究新的设计策 略，方法和工具。但目前我国a s i c 设计业的基本情况是芯片设计开发工作严重 滞后于电子产品发展的需求，滞后于芯片生产线的吞吐能力，并且设计和投产的 产品单一，品种太少，性能较低。要改变这种状况，急需提高设计能力。最有效 的方法之一是要大力发展高层次v h d l ( v e r y h i g h s p e e di n t e gr a t e dc i r c u i th a r d w a r e d e s c r i p t i o nl a n g u a g e ) v e r i l o g 设计自动化。 硬件描述语言是和电子设计自动化( e d ae l e c t r o n i cd e s i g n a u t o m a t i o n ) 技术同 步发展的，v h d l 和v e r i l o g 是其中最常见的两种硬件描述语言。硬件描述语言 的优点极其突出，例如对一个3 2 位的加法器，利用图形输出软件需要输入5 0 0 至1 0 0 0 个门，工作量庞大j 而利用v h d l ，则只需书写1 行代码“a = b + c ”即可。 此外h d l 的可读性强，易于修改和发现错误。 v h d l 语言是美国国防部在v h s i c 计划的研究过程中开发出的硬件描述语 言。作为一种与实现技术独立的语言，它具有如下优点【2 】： ( 1 ) 支持从系统级到门级电路的描述，同时也支持多层次的混合描述；描述 形式可以是结构描述，也可以是行为描述，或二者兼而有之；描述中可以混合并 行和串行描述。 上海大学硕士学位沦文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y ( 2 ) 既支持自底向上的设计，也支持白项向下的设计，支持模块化、层次化 设计。 ( 3 ) 既支持同步电路，又支持异步电路：既支持同步方式，也支持异步方式。 ( 4 ) 支持传输延迟和惯性延迟，可以准确地建立复杂的电路硬件模型。 ( 5 ) 数据类型丰富，既支持预定义的数据类型，又支持白定义的数据类型； v 】i d l 是强类型语言，设汁电路安全性好。 ( 6 ) 支持过程和函数概念，有助于设计者组织描述，对行为功能进一步分类。 ( 7 ) v h d l 语言中的类属提供了向设计实体传送环境信息的能力。 由于v h d l 语言的优点，它于1 9 8 7 年被确定为美国硬件描述语言的工业标准， 1 9 9 3 年又推出a n s i i e e es t d1 0 7 6 1 9 9 3 标准。目前国际上各大e d a 公司( m e n t o r g r a p h i c s c a d e n c e ，s y n o p s y s ) 的产：品都支持利用v h d l 语言来设计超大规模集成电 路( v l s iv e r yl a r g es c a l ei n t e gr a t e dc i r c u i t ) ，可编程逻辑器件( f p g a c p l d ) 的供应商 ( x i l if i x ，a t e r a ) 在其开发环境中也提供了对v h d l 的支持。 1 2 逻辑模拟 121 逻辑模拟的概念 模拟是一种仿真过程，首先要对被模拟电路系统建立模型，使建立的模型从 数学上或功能上模拟实际系统的行为。建立模型必须使用一些必要的约束条件和 近似条件，因此，模型和实际系统之间会有差别。根据对系统的模拟要求，可以 对不同级别的元件建立模型，以功能块作为元件的模拟称为功能块级模拟，以门 作为元件的模拟称为门级模拟。 逻辑模拟是用一组随时间变化的信号，作用于数字系统的逻辑模型，计算出 模型中各节点的行为特征。在数字系统的设计中使用逻辑模拟的主要目的是： ( 1 ) 在硬件实现之前检查逻辑设计的正确性以及线路中的竞争、冒险等 ( 2 ) 对逻辑设计的方案做出评价，提供改进和修改的参考资料。 ( 3 ) 利用逻辑技术通过插入故障，可证实故障检测的过程。 ( 4 ) 通过逻辑模拟，可获得电路动作的详细参考数据，为产品的制造、测 试和验收提供宝贵的资料。 1 22 逻辑模拟的流程 用户使用逻辑模拟前，要用专用的逻辑描述语言对逻辑电路进行描述。逻辑 电路的描述包括两部分：电路描述和模拟参数描述。 被模拟电路的所有元件及其互连关系经描述后输入到计算机中，经过编译， ! 生堕! 墅型堕! 塑! 堕坐竖堕坐坚竺l 一 把逻辑图转换成计算机内部的数据表格或称计算机内部的拓扑图。计算逻辑元件 的状态值有两种方法：计算子程序方法和查真值表方法。如果使用子程序方法， 要对每种类型的元件编写一个计算子程序。子程序的输入参数就是元件的输入 值，子程序的返回值是元件的输出状态值。真值表法是把输入状态向量作为查表 的地址，返回元件的输出状态值。 模拟参数的描述是确定电路的初始状态、外部激励信号的波形数据、电路观 察点和观察时间、模拟步长、总模拟时间及其它模拟参数。当这些参数输入到计 算机后，由程序设置一个软件模拟时钟，在模拟时钟的控制下，在离散的时间问 隔上计算逻辑元件输出信号的状态值，追踪通过网络各结点逻辑状态值的变化。 继续这个过程，直到电路网络各结点的逻辑状态处于稳定，或者达到规定的模拟 时间为i l 。 123 逻辑模拟的模型 为了对数字系统进行模拟，需要对被模拟的电路建立模型。建立模型的过程， 就是对模拟的对象作某种假设，忽略次要的因素，突出主要的方面，从而把实际 电路化简。模型越复杂，则与实际电路的反映越是接近，模拟就越精确，但花费 的计算机代价也就越高。选取什么样的模型，取决于模拟的目的和对模拟的精度 要求。 不同的逻辑模拟系统对逻辑模拟的元件有不同的要求和规定，基本元件类型 可划分为以下几种元件模型。 门级：包括与门、或门、非门、与非门、或非门、异或门、司或门等。同一 类门元件的差别主要是输入端个数、延迟时间、扇入扇出系数等。门元件输出值 的计算比较简单，可利用函数子程序计算布尔表达式求值或通过查真值表求值。 功能块级：功能块是用来表示数字系统中具有一定逻辑功能的网络，如寄存 器、存储器、译码器、加法器等。在整个数字系统中，功能块作为独立的元件可 多次使用，对于大型数字系统，如果完全用门来描述，不仅繁琐，而且会大大增 加模拟的信息，需要更大的存储空间和运算时间。 在功能块级模拟中，通常包括有逻辑门，实际是门级和功能块级的混合模 拟( 3 1 1 24 并行方法在逻辑模拟中的应用 随着集成电路规模的迅速增长、复杂度的不断提升，模拟所耗费的时间越来 越长，模拟速度已经成为设计过程中的一个瓶颈。这主要是由以下因素造成的： ( 1 ) 电路中逻辑元素数量的增长使模拟中计算次数大量增加 上海大学硕士学位沦文 t h ep o s t g r a d u a t et h e s i so f s h a n 曲a ju n i v e r s i t y ( 2 ) 事件列表中越来越多的待处理事件急剧增加了操作事件队列的时间 ( 3 ) 需要更多的输入矢量对电路的功能进行验证 对于并行逻辑模拟的实现，首先需要考虑的是采用什么样的方法以及在何种 层次上来并行化逻辑模拟的操作，比较常见的几种方法是算法并行、数据并行和 模型并行。 算法并行：使用流水操作技术，通过在不同的处理器上执行独立的程序来加 速主循环的执行，使用这种方法的并行性受到主循环步数的限制。 数据并行：使用不同的处理器模拟独立的输入向量，这种技术在故障模拟中 特别有效，因为有大量独立的向量需要被模拟。然而在设计验汪阶段，这种方法 的效率不高，凶为在设计验证阶段，输入向量之间的关联性比故障模拟时要火的 多，即当前输入向量的模拟结果依赖于前一个输入向量的模拟结果，而数据并行 对于这类数据相关性比较高的情况不太适合。 模型并行：将整个电路划分为多个子模块，每个子模块由若干个逻辑元件构 成，通过将独立的子模块分配到各个处理机上来实现并行模拟。这是迄今为止最 为流行的一种并行逻辑模拟方法，本文讨论的即是这种并行化方法，若不特别说 明，并行逻辑模拟指的就是模型并行。 模型并行属于并行离散事件模拟( p d e sp 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 ) 的 范畴，它通常是基于事件驱动的。在一个离散事件模拟系统中，系统变量被建模 成一系列的离散量，这些离散量的值只会在各个离散时间点上发生改变。在一个 逻辑模拟系统中，状态变量典型地建模成各个元件互连线的信号，在最简单的二 值逻辑模拟中，状态变量的值限定为o 或者1 。绝大多数的现代逻辑模拟器都 采用多值逻辑来表示额外的信息，在硬件描述语言v h d l 中采用标准的9 值逻 辑”j ，分别为u ( 未定) ，x ( 强未知) ，九0 ( 强0 ) ，i ( 强1 ) ，z ( 高阻) ， w ( 弱未知) ，l ( 弱0 ) ，h ( 弱1 ) 和( 无关) 。 1 25 并行逻辑模拟的研究现状 为了有效地提高模拟速度，国内外专家提出了很多模拟算法。但是，这些算 法基本上都在单机上实现，所得到的效果并不十分明显，速度的提升局限于一个 有限的层次。专用的硬件加速器或并行模拟器能够有效的提高模拟速度，但是它 们价格太过昂贵，而且缺乏通用性。在传统模拟方法无法取得突破的情况下，并 行逻辑模拟作为一个新的研究领域开始受到重视。并行逻辑模拟基于并行离散事 件模拟算法【5 】，通过分散模拟工作量到并行机的多个处理器或者普通工作站网络 减少模拟时间。 在国外，并行逻辑模拟的概念早在八十年代就提出来了。美国的华盛顿大学、 辛辛那提大学、德国的多特蒙德大学以及其它一些研究机构的学者对此进行了研 上海大学硕七学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 究。他们在并行模拟模型构建、逻辑网络单元划分、时钟同步协议等方面取得了 不小的进展；6 。”。这些研究成果为并行逻辑模拟的进步研究奠定了良好的基础。 但是，具有完整功能的并行逻辑模拟系统并不多，目前可见报道的只有美国的辛 辛那提大学和m t l 公司共同开发的并行逻辑模拟器q u e s ti i l 8 j 。值得一提的是， 国外在这领域的研究仍然处于实验阶段，许多影响并行模拟性能的因素还在进 一步探讨中，如电路的划分方法、同步策略、模拟中的动态负载平衡技术等。 在同内，针对并行逻辑模拟的研究相对较少，目前仅有国防科技大学、太原 理工大学、上海大学等高校在并行逻辑模拟划分算法、并行逻辑模拟的同步算法 等方面开展过研究 9 0 ”。总体浣来这方面研究还处于起步阶段，离国外的研究水 平有一定的差距。 1 3 容错在并行逻辑模拟中的研究现状 在国外，虽然容错技术在硬件设计和测试、传统的分布式计算和一些特殊的 应用领域中已经得到了较普遍的应用 1 2 - 1 3 】，但在并行和分布式离散事件模拟中， 尤其是在并行逻辑模拟中，相关的研究工作很不完善，大部分仅在其中运用了部 分容错技术，例如，检查点技术l 】4 。”、对象复制技术b6 、处理拜占庭故障 ( b y z a n t i n ef a i l u r e ) m 】，仅有b e t t i n aw e is 等人对初步构建了一个基于离散 事件模拟、具有容错能力的分布式系统s i m u t ct o o l k jt ”。对于如何在并行 逻辑模拟系统中没计完整的容错机制，目前的工作也只是涉及了对于离散事件模 拟建模，尝试从模型的角度设计容错。以及对整体框架的概念和前景展望方面进 行了探讨。然而，在实际并行逻辑模拟的过程中，特别是在普通的分布式网络上 进行长时间模拟时，容错机制是非常值得重点考虑的一个方面，因为不可能保证 网络工作站在任何情况下都不会出现故障。因此，就目前而言，对于并行逻辑模 拟的研究，特别是其与容错技术的结合，理论上还需要突破。 目前国内容错技术的研究也主要集中在分布式数据库、并行计算、实时系统、 软件可靠性等领域。在并行逻辑模拟的研究领域尚未开展对容错技术的研究。因 此，如何将容错机制引入并行逻辑模拟系统，在国内可以说是一个较新领域，需 要更多的努力去研究探索。 在今后，随着并行和分布式环境的普及，并行逻辑模拟技术会得到更加广泛 的运用，如何针对并行逻辑模拟的特殊性，设计完整有效的容错机制，在技术上 有许多迫切需要解决的问题。而借鉴其它领域如分布式计算中容错技术，如故障 检测、检查点和动态负载重分配等技术，将是设计并行逻辑模拟系统中容错机制 的有效途径。 上海大学硕士学位论文 ! 生! ! ! ! g ! ! ! ! 坐! ! 型! ! ! ! ! ! ! g ! ! ! ! ! ! ! ! ! ! 型 1 4 本文研究内容 本文研究的课题来源于上海应用材料研究与发展基金( 美国a m 基金) 资 助的基于硬件描述语言的并行逻辑模拟系统项目，主要内容为并行逻辑模拟 中的容错技术。本文的主要研究内容将按如下章节进行探讨： 第二章介绍并行逻辑模拟系统的结构和原理，提炼出该系统主要框架和相关 组成部分。此外着重探讨并行逻辑模拟中核心的同步语义规则、局部全局控制 等机制、分析系统自身的特点并给出影响模拟性能的各种因素。 第三章研究分布式系统可靠性及容错的概念，探讨在并行逻辑模拟系统中实 现容错将会涉及的相关技术。对于各种技术的适用环境和存在的主要问题进行了 分析和提炼总结。 第四章设计具有容错功能的并行逻辑模拟系统。结合并行逻辑模拟系统本身 的特点，对该系统中实现容错的各个环节进行分析和比较，提出在该系统中用户 透明的实现容错的方法可恢复时间偏差机制，给出了该机制的具体设计、实 现细节并对其正确性进行了论证。 第五章实现并行逻辑模拟系统容错功能。给出容错实现的具体流程图，并对 该实现所涉及的通讯接口、逻辑进程、虚拟时间管理器等各方而进行定义和描述。 第六章给出测试结果与性能分析。 第七章总结与展望 上海大学硕土学位沦文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 第二章并行逻辑模拟系统 2 1 并行逻辑模拟器的结构 我们研究和建立的并行逻辑模拟系统主要针对采用v h d l 描述的电路。首 先，系统使用前端编译模块将v h d l 转换成一种模拟用的数据格式，这种数据 格式保留了所有元件和信号及其它们之间的互联关系。然后利用划分算法在这种 数据格式的基础上对整个电路模型进行划分，将划分后的结果和数据格式上保存 的所有信息传递给模拟模块，模拟模块在电路元件库的支持卜- ，调用并行模拟核 提供的并行模拟算法，使用用户提供的输入向量对电路进行模拟，最后将模拟结 果输出到文件。图2 1 显示了并行逻辑模拟系统的整体结构。其中，并行模拟核 采用时间偏差协议，使用c + + 及面向对象方法设计开发。 罔2 - 1 并行v h d l 模拟系统的整体结构 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 2 2 前端编译模块 在并行v h d l 模拟系统中，编译模块的功能是对输入的门级v h d l 代码进 行词法、语法和静态语义分析，生成正确源描述的中问格式供模拟和综合子系统 使用。整个编洋模块的结构如图2 2 所示。 劁2 - 2 并行v h d l 模拟系统的前端编译模块结构图 前端编译模块的实现采用了一个语法分析和翻译程序自动生成工具集 - - p c c t s 【i 。前端编译模拟的构造过程如下： ( 1 ) 定义字符串识别规则生成语法分析程序。 ( 2 ) 根据v h d l 的语法定义、语法规则生成语法分析程序，在定义语法规则 的同时对语法树生成规则进行定义。 ( 3 ) 根据语法生成规则生成中间语法树。 ( 4 ) 从根结点开始遍历语法树，根据得到的结点信息构造模拟使用的数据结 构。 2 3 电路划分模块 “划分”就是将各个模拟对象依据某种特定的规则分配到各个处理器上。划分 技术既可以利用模拟算法的并行性，也可以利用被模拟电路本身的并行性。在前 一种技术中，划分算法所确定的并行的数目被模拟算法本身所限制。而后一种技 术试图通过划分电路本身来提高性能，因此，在后种技术中，模拟时不仅均衡 了工作负载，也利用了电路本身的并行性。所以，大多数的电路划分算法都采用 后一种技术。 客观现实中有很多因素会对划分结果的模拟性能产生影响，比如并行度、通 信量和负载的变化口。所以在逃行电路模型划分时，应该主要考虑p 2 t - - 个主要 的因素：并行性、通信量和负载平衡。 ( 1 ) 并行性：并行性由模拟过程中每一个模拟对象的活动所决定。假定在整 个模拟过程中的任何时刻，每个划分块中都有相同数量的模拟对象在活动，那就 上海大学硕士学位论文 ! 生! ! 塑! ! 型! 坠坐堕! ! ! ! g 堕塑兰唑z 能够达到模拟性能并行的最大化。 f 2 1 处理器之间的通信：在不同的划分块之间需要传递各种消息，。包括同步 消息和事件消扈、。消息的滞后到达会引起c p u 的等待，而超前到达可能引起回 退。在一个时间偏差系统中，处理器之间的通信量是非常关键的一个因素。最理 想的划分结果是使得没有跨划分块的信号产生。但由于电路互联的复杂性，在实 际中这是不可能达到的，因此，只能追求跨划分块之间消息传递量的最小化。 f 3 1 处理器的负载平衡：理想的负载平衡是要求在模拟过程中的任何时间段 内，每一个划分块都有相同量的负载分布状态。处于理想的处理器负载平衡状态 下的模拟器能够发挥出最好的模拟性能，避免由f 工作任务分配不均而导致有的 处理器处于空闲状态同时又有处理器因为工作过多而一直处于满负荷运转状态， 从而不能实现并行性的最大化。然而，绝对的负载平衡在实际操作中也是不可能 做到的，因此，我们追求的目标只能是尽可能多的负载平衡。 以上讨论的三个因素之间是一个相互制约、相互依赖的关系。为了说明方便， 将以上的三者关系用一个3 d 坐标来表示，如图2 3 所示。并行性，处理器负载 平衡和处理器之间的通信分别构成了这个3 d 坐标中的三个坐标轴。在这个3 d 坐标中的某一个点p ( x ，y ，z ) 代表了一种特定的逻辑电路划分方案，该划分方 案的并行性，负载平衡和处理器之间的通信分别用x ，y ，z 三个值来表示。假设 模拟过程中划分块的个数是1 ，就是不对电路进行任何划分，那么处理器之间的 通信就降为0 ( 仅有一个划分块，自然不存在跨划分块的消息通信) ，同时由于 模拟过程中工作量负载没有在各个处理器之间进行分配，所有的模拟过程都在一 个处理器ej i 页, 序地进行，因此也使得模拟过程中的并行性降为0 。同理，假如整 个模拟工作进行了分配，且达到每一个模拟对象位于一个划分块的程度，那么就 能够使得模拟过程中的并行性达到最大，同时由于每一个模拟对象都占用一个处 理器，使得不同模拟对象之间的信号传递都可归结为跨划分块的消息通信，处理 器之间的通信量也因此会达到最大。 图2 3 并行性，处理器负载平衡和处理器之间通信的3 d 坐标示意图 上海大学碗士学位论文 ! 生! ! 坐! 型型! ! 堕! ! 堕! ! ! ! g 型! ! 坐堂 一 所以，电路划分的原则应该是使得以上的三个因素能够达到相对的最佳，形 成一个动态的平衡；反之若是对某一方面的性能过度的追求，必然导致其它方面 性能的下降，从而导致整个系统性能的下降。 2 4 并行模拟核 并行模拟核的主要功能是进行并行逻辑模拟中的同步控制。目前，在并行逻 辑模拟中使用的时间同步方法主要有全局时钟同步协议和异步方法。而常用的异 步方法则主要有保守异步协议和乐观异步协议。 保守异步方法【2 1 1 依靠阻塞来避免相关冲突，要求逻辑元件的局部模拟时间的 任一次推进都必须保证不违反事件的因果关系，即在某逻辑元件将局部模拟时间 推进到时间t 之前，它必须确认不会再收到任伺一个带有时间标i l l d , 于t 的消息。 乐观异步方法允许各个局部模拟时间完全独立地向前推进，当发现因果错误 的时候就采用某种机制进行恢复，最流行的一种乐观异步方法就是时问偏差 ( t i m ew a r p ) 协议【2 2 j 。 从国外已有的并行逻辑模拟研究实验得出的数据分析中可以看出，在大部分 情况下，采用乐观异步方法的模拟系统性能要比使用全局时钟同步和保守异步的 系统性能好。本系统的并行模拟核中的同步协议也采用时间偏差协议，它是整个 并行逻辑模拟得以建立的到步基础。 由于时间偏差协议对并行逻辑模拟性能有很大影响，同时与本文研究的容错 技术也紧密相关，因此下面将结合并行逻辑模拟系统对时间偏差沩议进行详细的 介绍。 2 41 时间偏差协议 时间偏差协议以虚拟时间作为其同步的定时标准。虚拟时间是一种适合于分 布式并行模拟的逻辑时间表示方法，它本身是一个加在分布式计算之上的、全局 的、- t 维的时间坐标系统，它是对真实时f 司的一种抽象，但是比真实时间更具有 计算意义，它定义了所有用户可见的同步概念并根据这些同步概念来进行定时。 使用虚拟时间是为了测量计算的进度和定义同步。 通常，虚拟时间的值用一系列的实数值来表示( 用+ i n f 表示正的无限大) ， 且这些实数之间可以用“c ”进行全局排序。从编程者的角度看，全局虚拟时间 总是以一个不可预测的速度向前推进的( 或者至少是不回退的) 。但从执行者的 角度来看，系统中可能存在着许多局部虚拟时钟，它们之间是松散同步的，并且 每一个虚拟时钟都有向前推进的趋势。但在某些时候，一些局部虚拟时钟可能会 跳回到以前的虚拟时间点上。这一点和真实时间是不同的，因为真实时间总是向 k 坶大芊蛾士学位论卫= ! 生! ! ! ! g ! ! ! 堕! ! 堕! ! ! ! ! ! 竺韭! ! ! ! 竖! 型 前推进的。 时问偏差协议可以看成是虚拟时间的一种实现机制，就好像分页和分段机制 实现了虚拟内存一样。一个时间偏差系统是以一个想象的虚拟时钟作为执行同步 的分布式系统。局部虚拟时钟推进的异步性使得时间偏差系统采用的同步策略与 一般的分布式系统有所不同，一般的分布式系统( 包括基于锁、信号量或通常的 流控制机制等) 都使用某种阻塞一继续机制来保持进程之间的同步，而时间偏差 咖议中引入一种称之为回退( r o l l b a c k ) 的策略作为同步的基础，即在时间偏差 协议下，每个逻辑进程异步地向前推进而不管是否与其它的进程发生冲突，当在 随后的时间里检测到冲突之后，违反因果关系的进程就回退到冲突发生之前的最 近一个虚拟时间点【：，然后从该时问点起沿着纠正好的路径重新执行。同步冲突 的检测和解决冲突的回退机制对用户都是透明的。 回退机制广泛地应用于容错技术，但实际可以用于同步目的，虽然分布式系 统是非常复杂的，并且使用时间偏差机制的同步开销看起来要比其它同步机制的 开销大，但事实并非如此，许多理论分析和经验数据表明，使用回退机制和虚拟 时间在并行逻辑模拟中是切实可行的。 242 逻辑进程同步的语义规则 一个采用时间偏差咖议的并行v h d l 模拟系统可看成是一组逻辑进程( l p l o g i c a lp r o c e s s ) 的集合。每个l p 代表模拟过程中的顺序计算单元，用以模拟 v h d l 电路内的某一物理过程。l p 之间异步执行，彼此通过交换带有时间标记 的消息来进行通信。 在时间偏差系统中，我们可以将每一个逻辑进程看成是占有了虚拟空间下的 一个点，并具有一个全局唯一的名字作为它的空间坐标，这样，每一个原子动作 ( 比如改变一个变量，发送一个消息等) 都有一个对应的虚拟时间坐标和虚拟空 间坐标。在相同的虚拟空间x 和相同的虚拟时间t f 发生的所有动作集合称为事 件，记为e v e n t ( x ，t ) 。 逻辑进程之间仅能通过发送消息进行通信，任何一个进程可以在任何一个时 间点上给任何一个它可以找到的进程发送消息( 包括它自身) ，在进程之间没有 隧道的概念，所以不需要打开关闭协议。每一条消息至少包含四个值：发送者 ( s e n d e r ) ，发送时间( s e n d t i m e ) ，接收者( r e c e i v e r ) 和接收时间( r e c e i v e t i m e ) 。 等同的，我们可以说一个消息标有发送事件和接收事件的坐标，因此，消息实质 上是在虚拟时空坐标下一个事件到另一个事件的信息传递。 逻辑进程间的消息发送和事件调度必须遵循下面两条基本语义规则： r u l e l ：每一个消息的虚拟发送时间必须小于它的虚拟接收时间。 r u l e 2 ：在一个进程中，每一个事件的虚拟时问都必须小于该进程中下一个 上拇大学坝士学位论又 ! 塑! ! 韭型! ! 塑堡坐! ! ! ! ! ! g 堕! ! 竖! 型 事件的虚拟时间。 实际上，这两条规则和l a m p o n 的时钟条件在实质上是一致的，它表现了 事件的因果关系以及信息传递的时间方向，它们蕴含了如下的事实，即一个进程 总是以虚拟发送时间的次序来发送消息，而以虚拟接收时间的次序来接收消息。 在( x ，t ) 下的一个事件表示在进程x 中，虚拟时间t 下的一个串行计算序 列，它包含了0 个或多个下列操作： ( 1 ) x 可能接收任意多个标有r e c e i v e r = x 和r e c e i v e t i m e = t 的消息，并读出 这砦消息的内容。 ( 2 ) x 根据得到的消息内容执行t 下的所有操作并更新状态变量。 ( 3 ) 发送任意数量个消息，每个消息都自动标为s e n d e r = x 和s e n d t i m e = t 。 如果事件a 引发了事件b ( 或者a 是b 的一个原因) ，则一定存在一个事件 序列a ，e o ，e l e 。= b ，对其中的每一对e 。和e 。+ i 一定有关系：( a ) e 和e i - i 在 同一个进程中，且e 的虚拟时间小于e h 的虚拟时间。或者( b ) e h 接收了e ，的 一个消息。 从上面的分析可以看出，事件之间的因果关系是影响事件并发执行的关键因 素。具体来说，如果事件a 和b 满足下列两个条件之一，则a 和b 就可以并发 执行而保证结果的正确性： r u l e l ：a 和b 有相同的虚拟时间，且它们之间没有先后调度约束。 r u l e 2 ：不存在事件序列a ，e o ，e l e 。= b 以及b ，e 0 ，e 1 一e 。= a 在第二种情况下，即使a 比b 有更小的虚拟时间，a 也彳i 必要在b 之前调 度，这样，在某些情况下，我们可以将b 先于a 调度从而来取得更好的执行性 能。 243 局音b 控韦0 机韦4 虽然虚拟时间有一个全局的标准，但实际执行过程中并没有全局虚拟时钟的 存在。相反，每一个进程中都有一个局部的虚拟时钟，它标识了局部虚拟时间 ( l v tl o c a lv i r t u a lt i m e ) ，l v t 用于记录局部模拟时间，其值为最近执行的或正 在执行的事件的时间标记值。在一个模拟时间点上，某些进程的l v t 可能超前 于其它进程的l j v t ，但进程本身并不能察觉，因为每个进程对其它进程的虚拟时 钟是不可见的，进程只能通过比较消息的时问标记和l v t 来决定模拟的进度。 在进程的执行阶段，进程不断地接收来自其它l p 的消息并将g l r 插入到输 入队列中，然后取出具有最小时间标记的事件执行，同时更新l v t 。在理想情况 下，没有一个消息的时间标记比l t 小，但因为进程的不同步性，实际的情况 并非如此，进程往往会接收到时间标记比l v t 小的消息，称这样的消息为落后 消息( s t r a g g l e r ) 。一旦进程接收到落后消息，进程就要回退，假定落后消息的时 上海大学硕士学位论文 ! 生! ! ! 堕型! 坐! ! ! ! ! ! 堕! ! ! ! 塑! ! ! 型型生 f h 标记为t ，则进程首先回退到t 之前的最近一个时间点上，即将状态恢复至最 后个正确状态，然后删除t 之后的所有状态，并从t 开始重新执行。 如图24 所示，当l p 2 接收到来自l p 】的落后消息后，l p 2 就回退至处理完 e 时的状态，并撤消由于超前处理e ，而执行的所有操作，然后从事件r 开始重 新执行，一直到l v t 再次推进至1 5 0 。 l p ，一一 l p ，一一 一一+ - 虚拟时间轴 常事件 一一 、耐u 塑型叫 图2 4 进程回退图 在进程的回退时，必须考虑以下两个问题： ( 1 1 内存的回收和对某些不可恢复操作( 比如i o 操作) 的处理。 f 2 1 对己发送出去的消息的处理。 对于问题( 1 ) 将在全局控制机制中加以解决，因为它必须借助全局虚拟时 间才能处理。对于问题( 2 ) ，通常使用发送反消息来解决。如果一个l p 发生回 退，则该l p 就将其输出队列中的反消息发送出去，当正消息和反消息出现在同 一接收进程的输入队列时，正反消息就相互抵消，从而达到取消消息的目的。但 是，已发送出去的消息可能在另外一个进程上已被处理，此时，我们不能仅仪将 正反消息抵消，而必须进行更为复杂的操作。取消消息的几种情况具体如下： 如果原始正消息已经到达但还没有被处理，则它的虚拟接收时间一定大 于接收进程的l v t ，当具有相同虚拟接收时间的反消息到达接收进程之后，只要 简单地将正反消息抵消掉。 如果原始正消息的虚拟接收时间小于接收进程的l t t ，并且原始正消息 已经被完全处理或部分处理，并改变了接收进程的状态且发送了另外的消息到第 三个进程。在这种情况下，当反消息到