没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记245(2009)51-67www.elsevier.com/locate/entcs基于Petri网的去冗余Sohini Dasgupta苏希尼·达斯古普塔1,2曼彻斯特大学英国曼彻斯特亚历克斯·雅科夫列夫3纽卡斯尔大学英国纽卡斯尔摘要在本文中,我们考虑的问题,descrisising模块化同步规格实现GALS架构,并获得简单的包装器,是有效地综合使用现有的合成工具。该系统采用Petri网(PN)建模,并基于PN局部性理论对系统进行去冗余化。全局同步系统的触发语义的特征在于输入和输出转换的最大触发。 同步系统的划分通过将输入转换拆分并允许输出转换以最大步长触发来实现,以便在分布式环境中实现异步通信。我们的模型满足两个基本的正确性属性,即语义保持和死锁预防,从最大触发语义,其次是同步系统,到输入转换的标准交织语义和输出转换的最大步长触发语义,其次是GALS架构。通过添加内部信号来支持局部的形成,所述内部信号对于在将生成局部时钟使能的局部中构建包装器是必要的。这些包装可以随后使用基于PN的合成工具进行合成。关键词:Petri网,去冗余化,局部性,持久性,GALS。1引言本文介绍了一种新的同步系统去同步化成全局异步和局部同步(GALS)体系结构的方法在过去的十年里,已经提出了不同的形式化技术用于GALS例如[1,2]。在文献[3]中,为了对同步系统进行去同步化,人们用变迁系统(TS)作为描述同步系统1 感谢所有应该感谢2 电子邮件地址:sohinid@cs.man.ac.uk3电子邮件:Alex. ncl.ac.uk1571-0661 © 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2009.07.02852S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51一CeBDF系统时钟(kHz)区块4Block3Block2Block1一BCeFDclk1CLK2Loc2Loc1同步系统GALS结构图1.一、同步系统向分布式体系结构的转换GALS架构。每个同步模块获得的模型可以是非常大的和复杂的,由于薄弱的并发处理所造成的desynchronisation方法使用。并发性是为GALS部署指定处理异步通信的同步系统的先决条件。此外,这些模型被翻译成Petri网,以使用现有的异步工具的逻辑综合。因此,从以前的方法获得的过渡系统的复杂性,以及这些模型的PN合成的计算复杂性形成了这项工作的主要动机。新技术使用PN作为规范模型,其高效的并发处理技术使其成为描述系统去规范化的最可行模型之一PN提供了一个高级系统描述模型,其中转换被映射到信道或符号上的动作该技术使用标记PN作为指定这些动作与系统及其组成块的I/O事件之间的逻辑依赖关系的方式。在我们的框架中,通过转换执行的语义,同步/同步的概念。 网络的执行受某些规则的约束,这些规则是由逻辑上启用的转换根据位置上的某些条件被这些条件是由语义施加的,以满足系统的时钟要求。假设在真正的同步执行中,所有逻辑上启用的转换的触发都是根据最大步长策略(参见定义1)完成的。在真正的异步执行中,我们使用步骤语义和所有可能的交错。新技术背后的理论使用了受[5]启发的局部性概念,由于其与GALS架构的强结构和功能对应性,该概念有助于描述同步系统在异步架构同步系统由与一组输入和输出信号相关联的部件组成。图1中描绘了这样的系统。这些组件中的每一个都由诸如发送和接收控制信号以及在不同组件之间交换数据信号之类的所有组件执行的操作由单个全局时钟控制在这项工作中,我们假设时钟生成的机制可以以已知的方式之一构建• 使用独立的全局时钟和同步器(例如,基于双通道S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5153结构)与每个输入相关联,• 由输入产生的内部时钟(事件或数据驱动时钟)局部性的概念[5],在应用于生物膜系统时,引入了将这些上述组件局部化的想法,因此将它们的相关作用局部化到各个块中。这些模块在其输入和输出信号上结合了一些额外的排序约束这些限制使这些地方的行为像独立的同步系统。因此,可以消除全局时钟,并且每个局部可以与控制分配给它们的动作的局部时钟一起使用。这种情况下提请平行的系统之间获得的建议desychronisation计划和Endoprosthesis系统,其中同步程序可以重建其时间从其内部的行动,并不需要使用环境作为外部刺激它。如图1所示,一个以上的组件可以映射到每个地方取决于一些规则和优化标准,稍后讨论。由于去除了全局时钟并应用了本地时钟,因此在这些地点之间没有时钟信号,因此创建的这些地点将彼此异步通信从全局同步系统获得分布式体系结构的技术必须满足两个基本的正确性属性,即,• 原始同步系统的语义保持:在每个同步序列的执行期间,同步系统的组件基于内部信号和输入信号的值来计算输出信号的事件。在每个时间单位内,系统通过输入和输出信号的最大并发执行来变换将这样的系统部署到GALS架构中需要对输入信号进行拆分,以帮助在异步环境中无序接收这些信号。因此,这种形成分布式体系结构的转换应该保留原始系统的语义。• 防止死锁:当同步系统转换为GALS架构时,如前所述,在原始系统中绑定的输入转换被解除绑定。这种无序的信号接收不应导致系统进入死锁状态。因此,在转换后的模型中应该有额外的约束以避免发生此类情况。这两种性质已分别在第6节和第7节中讨论我们试图在本文中提出一些初步的想法,该方法使用PN的建模语言和它们的“同步范式”的步骤和最大并行性的语义表示的系统进行deskenisation该方法定义了正确解系统Petri网模型的重要条件这些条件在上下文中讨论Petri网执行语义的应用。该方法有可能允许设计者在设计空间中移动各种不同的选项,以在完全同步和完全异步之间进行去同步化。特定的解决方案可以通过去杂质化的标准来确定,例如54S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51作为性能优化。为了说明在这个频谱中搜索设计解的一个特殊情况,本文最后给出了一个算法的草图,该算法采用完全同步系统的Petri网模型,并产生一个系统模型,该系统模型具有一组由非捆绑输入(整个系统的主要输入和单个块的输入,由系统的细化形成并与无限延迟相关联)和最大可能的输出组的条件确定的位置。2预赛本文采用Petri网模型来描述同步系统。这是因为同步系统执行的所有组件和动作都可以直接映射到Petri网的不同元素例如,同步事件在转换上表示,触发条件在位置上表示。为了显示触发条件为真,该场所配备有令牌。使一个同步组件从一种配置转换到另一种配置是通过触发转换来表示的。因此,PN模型在描述同步系统时具有充分的表达能力。这些模型的详细描述见第4节。2.1Petri网及其在系统去规范化背景下的解释Petri网(PN)是一种用来表示具有并发性的系统的模型。它是一个四元组PN={P,T,F,μ0},其中P是一个位置集合,T是一个变迁集合,F是一个弧,表示一个关系F<${(P×T)<$(T×P)},μ0是初始标记。给定一个Petri网N,变迁t∈T的前、后多重集分别是多重集preN(t)和多重集postN(t),使得对所有p∈P,|preN(t)= F(p,t),|p|post N(t)= F(t,p),其中|p|表示令牌数|denotes the number of tokens在P的地方。在PN理论中有许多语义方面和属性,但对我们的目的来说最重要的是以下内容:步骤的语义概念和持久性的行为属性前者对于表达将一组动作同步为一个束的想法是必要的(在我们的解释中,通过将公共时钟应用于相应的硬件单元来实现)。需要后者来表达事件束的稳定性的概念(即,如果一个时钟信号被应用到一组提交的动作中,这组动作不能被“立即”改变,否则时钟信号可能会遇到危险)。定义2.1步骤一个步骤是一个多重转换集U:T→N,其中N是一组自然数。在最大步长语义中,如果相关的外部条件为真,则PN模型通过并发触发过渡集来演化S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5155定义2.2持久性一个Petri网(N,μ0)是持久的,如果对于N的任意两个不同的变迁t1,t2和任意可达标记μ,如果t1和t2在μ处被使能,则其中一个变迁的出现不能使另一个变迁失效.持久性的概念可以推广到步骤。在本文中,我们将考虑作为主要执行语义的语义称为交错步骤语义[5],它要求在每个标记中执行所有可能的启用转换子集,如果它们不冲突。例如,对于图2(b)所示的网,在使能In1和In2的标记有三个可能的步骤可以执行:{In1}、{In2}和{In1;In 2}。每个步骤通常与可达状态图中的单独弧相关联。在下文中,为了避免符号混乱,如果相应的交织是可能的,我们通常将不示出瞬态步骤。因此,如图所示在图3中,In1和In2以交错步骤语义执行,我们因此,我们将仅显示其重要性由最大步骤执行确定的步骤。本文使用PN来模拟与I/O端口和内部通道的激活相关联的动作的系统我们将不关注系统的计算因此,可以方便地假设,对于这样的PN,输入I和输出O的集合以及将Petrint的转换映射到SetIO{tint}的函数l,其中int∈IO是不受环境影响的简单的整数。考虑一个具有I/O端口的系统的简单示例,如图2(a)。设输入I1和I2彼此并发。图2(b)表示图2(a)所示系统的输入输出依赖关系的Petri网表示。在下一节中,我们将考虑如何添加局部性的附加(结构)概念,可以帮助我们将一个方便的建模框架放在一起,用于分析在PN转换的上述解释下使用Petri网模型与系统去冗余化相关的问题3基于地区的去荒漠化方法的动机上述对过渡步骤的定义有助于对它们的结合效果进行即使用时钟的同步。根据转换步骤执行的语义,我们可以制定不同级别的同步性,从全局(即完全同步)到完全异步。然而,我们还需要一些标准,将一个特定形式的执行政策的Petri网模型的系统。例如,从性能的角度来看,我们可能想要改变(全局)最大步触发并行性的策略,因为这样的语义假设时钟信号仅在前一步中的所有事件都被执行之后才被激活。这导致了最坏情况下的操作56S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51In1 In2S1氧气,S2O3、In2In1In2In1O1O2O3O4O3,O4O1,O2(一)O1O4(b)第(1)款(c)第(1)款图二. 同步系统图3.第三章。非捆绑无序输入系统模型延迟从系统我们将全局同步范式与最大触发语义相关联。在图2(c)中呈现了描绘上述PN示例的这种语义的状态图。假设我们想要将系统解压缩成GALS版本,例如由于In1和In2之间以及O1和O3之间的延迟变化等较大并且全局时钟是时间依赖性的事实。为了融入随机性的思想,必须允许输入以任何顺序和在任何时刻到达。这导致了如图3所示的输入的分拆。但是输出信号是以束或最大输出步长(或Max-O步长语义,见第4节)的形式发出的由于输入信号不能被调度为在已知时刻到达,因此不能保证持久性。这导致输入之间的未知延迟。 因此,从图中可以看出,模型在状态s1和s2处具有非持久性步骤。也就是说,让首先到达,这使得以最大步长执行。但是在最大步骤的执行完成之前,如果In2到达,则系统尝试执行最大步骤。因此,的到来禁用了导致违规的步骤 在s1处In2>和O1, O2>之间的持久性。<<状态s2的非持久性步骤可以用类似的方式轻松显示因此,如果一个bundle在持久性上被改变,例如上面的例子中的{O1,O 2,O3,O 4}到{O1,O 2},它会导致bundle的持久性违反。换句话说,事件不能由于某些并发行动,因为它会产生不稳定的束。In1O1O2氧化铟O4In1In2O2O3S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5157为了避免这种情况,系统不会全局遵循最大输出语义。如果有可能以这样的方式划分系统,即在每个分区中没有输入转换和输出步骤是非持久的,则Max-O语义可以被限制到每个分区,从而导致并发系统的正确实现。 这为使用地点提供了动力,因此,也提供了一种满足持久计时属性的去同步化方法。为了从同步规范中获得GALS系统的正确实现,需要将同步系统划分为类似于分区块的局部。因此,将全局同步系统划分为多个局部并在每个局部应用Max-O语义,通过保证不存在死锁和实现正确的输入输出依赖关系来帮助去除全局时钟。3.1使用进程的Max-O语义和有效性准则上一节介绍了用于描述分布式体系结构的Max-O语义。PN的标准交织语义不关联任何最大触发的概念,通过该概念,一组转换总是并发地触发。因此,引入了最大输出语义,它绑定了输出转换的集合,以便并发地触发它们。在本节中,我们得出了PN模型与最大输出语义和标准(交错步骤)语义之间的一些等价关系。获得这种等价性的原因因此,用于表示我们的系统的模型是那些在标准和Max-O语义下等价的模型。在这里,我们需要定义支持上述等价的限制。这可以借助文献[6]中介绍的过程理论来完成。为了避免形式化,我们在这里只提出这种行为等价的直观想法。设P={P,T,F,μ}是一个Petri网模型。令PNSTD是标准语义下的解折叠的前缀,并且PNmax是解折叠的前缀。在Max-O语义下,标准语义具有交错输出步骤,Max-O语义具有最大输出步骤。因此,与Max-O语义相比,交织语义将具有更多的许可步骤。因此,我们可以直观地说,标准语义的过程比Max-O语义的过程更丰富为了防止Max-O语义包含标准语义不允许的额外事件,PNmax语义的每个进程必须是PNSTD的某个进程的前缀。4同步模型描述现在考虑一个更复杂的例子,以突出我们的非对称化方法的主要方面。这将是一个运行的例子,58S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51In1In2系统时钟O1O2O3O4O5O6O7(一)In1In2O1,...O7(b)第(1)款(c)第(1)款见图4。 同步块PN和SG模型用于去噪O1O2O3O4O5O6O7图五.同步系统GALSi fication.图. 图4(a)示出了同步系统。 有两个输入In1和In2到块和七个输出,即O1,O 2,O 3,O 4,O 5,O 6和O7从块。系统时钟用于为整个系统提供全局时钟。 这种系统的PN模型规范如图4(b)所示(为了简单起见,我们稍微滥用了标记Petri网的标记约定,并将一组并发启用的输出分配给一个转换,而不是使用七个单独的转换)。全局同步环境中最大触发语义的状态表示如图4(c)所示假设同步系统被进一步细分为更小的计算块。这些模块具有来自其他类似内部模块的输入信号和去往其他类似内部模块的输出。当从单个同步块的顶层看时,这些信号这些较小的块有自己的内部信号集。这种系统如图5所示。信号a、b、c和d形成整个同步块的内部信号。这种系统的PN表示如图6(a)所示。这种系统的状态图如图6(b)所示为了形成的地方,并帮助异步通信的地方之间的一些转换应用在PN模型的水平。在组成同步系统的各个块的并行性上,这些内部信号形成到内部块的输入和来自内部块的输出,即,作为块1的输出,但作为块4的输入由于内部信号现在被解释为从一个块输出并输入到下一个块,因此在网络上应用变换以将该通信合并到通道上一块Block1b4In1块2C块5In2d座36系统时钟S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5159In1In2O1O2O4O6a_Ob_Oc_Od_Oa_In b _Inc_Ind_InO3O5O7(一)(b)第(1)款见图6。 同步块见图7。 修正模型以将输出与输入信号区分开,从而进行解扰。这是必要的,以纳入地方的想法,有一套输入和输出转移分配给每个地方。因此,一个地方的输出形成了另一个地方的输入。为此,我们将信号划分为输出信号和输入信号。例如,信号a被细化为一个O和一个In。要做到这一点,需要通过插入新的内部信号来转换模型,为此使用第4.1这种改进导致原始系统的修改后的PN模型,如图所示。第七章阴影框表示在原始系统中插入信号4.1网络变换和有效性概念为了获得系统的分布式PN模型,需要对模型进行一些变换以辅助划分过程。 一个这样的变换是信号插入。在本节中,通过转换划分的信号插入被正式定义。插入的类型被限制为顺序后插入,因为插入是为了帮助将信号划分为其输出和输入对应部分,因此消除了并发插入。定义3. 过渡分裂给定一个标记Petri网,其中I =(P,T,F,μ0),I是一组输入,O是一组输出,使得I<$O= 0,l是映射In1In2O1O2O4O6a BCDO3O5O760S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51将Petrint的位置转移到S etin ti ntiJ J J J J J J的转移t∈T产生一个LPN =(,I,O,l),带 =(P,T,F,μ0),S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5161不不u不u不(a)(b)第(1)款(c)第(1)款(d)其他事项见图8。 过渡分裂其中,JT=T<${u},其中u∈/P<$T是一个新的位置JP=P{p},其中p∈/PT是一个新的平面JF= F <$({t,p}<${p,u}<${(u,q)|q ∈ t·})\{(t,q)|q ∈ t·}信号插入的有效性的概念是直接的,并且可以根据弱互模拟来调整变换,这已经得到了很好的研究。这样的概念在[[4],命题5.3]中提出。有效变换在插入信号时需要遵守一些限制。• 新插入的地方形成了不同地方之间的因此,这些地方不能有令牌被盗的另一个过渡冲突。为了避免转移窃取令牌并导致一个局部运行陷入死锁,图中描述了这种情况。第8章不应该被允许因此,接口场所不可能是选择场所。• 如果信号具有扇出,则缓冲器应在扇出之前插入,而不是在每个分支中插入一个缓冲器。后者可能导致由于大量信号插入而形成不必要的局部。这在图中举例说明。8(b).因此,图8(c)和图8(d)分别显示了扇入后和扇出前信号插入的允许示例。过渡期重新标签转换t(被分割的转换)和u(新插入的转换)通过添加后缀来标记O到t的标签,在标签中的美国这样做是为了将意义与表示信道通信的插入信号相关联。因此,对于图6所示的示例,标记为a的被分割成表示来自块1的输出的O和表示到块4的输入的In。新插入的位置t·i可以被视为存储单元,例如缓冲器。 此缓冲器在将数据传输到下一个街区。···62S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51图9中描绘的每个单独的隔室现在可以被视为具有其自己的输入和输出信号的模块化同步块S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5163O1O2a_Ob_Oa_Inb_InO3O4In1c_Oc_InO5O6In2d_Od_InO7系统时钟见图9。 具有存储单元的将必须遵循同步行为。因此,原始同步系统现在可以定义为这些COM的集合,通过PN的并集的标准操作在PN级别建模,在位置上合并[10]:=(P1,T1,F1,μ1)(Pn,Tn,Fn,μn)由于这些隔室中的每一个都被视为同步块,因此来自这些块的输入和输出转换也遵循如上所述的相同执行规则。4.2一个Petri网类对于我们的初始工作,我们使用PN的一个子类,遵循一定的假设,以帮助我们的去同步过程。因此,我们的PN模型应该满足以下性质:性质1(安全):PN是1-安全的,如果对于每个可达标记和每个位置,我们有μ(p)≤1。在这项工作中使用的PN模型是1-安全的,以帮助使用现有的合成工具合成模型,以及能够使用理论来自[5]的局部,其使用基本网络结构(已知1-安全网络可以很容易地由基本网络建模属性2(选择):只有当输入信号受环境控制时,才允许在输入信号之间进行非确定性选择。5局部Petri网为了从同步系统模型建模分布式体系结构,我们应用了最初在[5]中引入的局部Petri网理论。在以前的工作中,最大限度地执行同位转换。我们通过区分输入和输出转换并允许输入转换在它们到达时执行,并限制输出转换最大限度地执行并仅在持久步骤中执行来扩展这一点。 此扩展 与前面部分中讨论的同步行为直接相关。从允许多个信号的角度来看,可以在我们提出的概念和[11,12]中提出的突发模式电路的概念之间进行类比。64S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51每次转换时的变化并考虑I/O因果关系。另一方面,前者可以被看作是突发模式电路的概括。这是因为它使用PN作为计算模型,其允许基于捆绑在突发和独立突发中的事件的子集以可伸缩的方式引入突发/捆绑,从而保持它们之间的真实并发性水平PN中的跃迁属于固定的唯一局部性。通过使用局部映射函数γ划分PT网来实现对转移的局部分配。这意味着如果两个跃迁返回相同的γ值,它们将位于同一位置。具有位置的PN是由NL=(P,T,F,μ0,γ)表示的元组,其中底层PN由UND(NL)=(P,T,F,μ0)表示,并且γ:T→N是过渡集T的位置映射。γ(t)返回一个整数值,表示转换t的位置。最初,对于所有t∈T,γ(t)被设置为0,这表示转换未分配。一般来说,一个网可以被划分,从而形成构成原始图的较小的网。设P ={P,T,F,μ0}为PN。然后,划分可以导致将网划分为n个较小的网,其可以表示为,i=(Pi,Ti,F对于i= 1到n,其中n是一组整数,每个Ti<$T使得(T1<$T2<$.................... Tn)/=并且每个Pi∈ P,使得(P1∈ P2∈.... Pn)=,PiD μ0定义如下:如果μ0:P→{0,1},则μp∈Pi,μ0 i:Pi→ {0,1}|μ0 i(p)= μ0(p)。根据应用于划分过程的规则,可以改变上述一般定义以满足给定方法的要求。在我们提出的分区方法中应用的规则在6中给出。6划分正确性如上所述,同步系统可以通过拆分输入并形成位置来分解为这些局部的形成应满足某些正确性性质,以确保正确的设计同步。同步系统的GALS部署的划分是正确的w.r.t.如果GALS系统和初始同步规范之间存在行为等价,则初始同步系统。这在形式上定义如下:设P ={P,T,F,μ0}为PN。分区2n,每个分区都属于到L1L2... Ln分别在标记μ i处对于所有的转变步骤U1→T1,. 其中,U1,. Un分别在U1、.......................................................................................................... Un中启用,合并后的步骤U1和U2... Un已启用。 这表示为,(μ D P1)[U1>1(μ D P2)[U2>2. (μD Pn)[Un>n<$μ[U1<$U2<$.........Un>,对于所有的U1<$T1,U2<$T2,Un<$Tn.S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5165位置=2英寸2位置=1In1位置=1位置=2In1In2(一)(b)第(1)款见图10。转换之间的连接冲突解决为了遵守上述准则,局部性分配应该满足冲突解决的正确性性质。例如,图10(a)中显示了一个不正确的分区。将净T1划分为分别属于地点L1和L2的T1和T2,使得转移t1被分配给地点L1并且t2被分配给L2,因此,T1=t1并且T2=t2。现在,代入p对于μ,在局部性的局部性中,leadstamarkings{p}[{t1}>1和d{p}[{t2}>2{p}[{t1,t2}>不规则。 Hence,thepartitingisincorrectt. 对于图10(b),可以类似地示出导致不正确的分区的这种这一概念要求把冲突中的过渡放在同一地点。局部优化技术可能导致这种情况的发生。因此,在分区中插入输入/输出桥时必须小心因此,如果以下条件成立,则可以保证正确性:设n ={P,T,F,μ0}是已划分的基本网系统转换成101,102,...,你好 如果来自分区的转换不共享前提条件,后置条件,或·T1型·T2型... ·Tn= T1·T2·... Tn·=那么分割是正确的。因此,如果输出可以相互禁用,即它们处于冲突状态,则它们不能在不同的地方。这些产出必须在同一地点,这种冲突应被解释为发生在该地点内的选择注意如果在标记s下存在启用的步骤{I1,I 2,O 1,O 2,},则允许其中的每个操作,如果它不与其中的另一个操作相冲突如果一些被启用的如果转换是冲突的,在全局时钟系统中,没有非持久性步骤,因为没有真正的并发性(同步同时动作)。在这样的系统中的冲突可以静态地解决,在一个确定的方式,通过调度它们使用一些机制,如优先级或成本函数。一旦我们开始去殖民化,即。拆分后,我们进入了一个并发可能会由于动态冲突66S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51解决或动态S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5167In1In2O1O2O4O6a_Ob_Oc_Od_O(一)(b)第(1)款见图11。 持久性检查重新安排步骤。这可以不使用具有某些最小延迟(即,某些分辨率限制)的逻辑块来物理地实现。步骤持久性分区块必须满足的另一个正确性属性是步长持久性。识别和处理非持久性的原因已在第3节中介绍。非持久转换可以通过使用以下过程来识别和持久化:1)对于网络中的每个输出转换,识别依赖于多个输入转换的输出转换集Out。2)对于Out中的每个输出转换,返回输出所依赖的输入转换集In。3)对于In中的每个输入,检查它是否导致一个以上的输出转换。4)返回(3)为真的输入信号的集合。5)返回输出转换O1,使得O1∈Out,并且导致它属于集合的输入保持不变。6)将(5)中获得的输出与集合中的每个输入信号通过输出-输入转换对连接,如图11(b)中的阴影区域所示。插入的信号是输出-输入转换对的集合,用Ox和Ix表示,它们表现为整个系统的内部事件或静默事件。这些信号满足第2节中讨论的信号插入有效性的概念。因此,在模型级别,图7中描绘的系统被转换成图11(b)中描绘的系统。7地点分配为了获得跃迁的划分集,需要关于PN的每个输入和输出跃迁的位置的信息。我们从输入-输出依赖关系中推导出同步电路的每个输入和输出转换的本地化。例如,如果在位置L中计算输出转换y,则执行y所需的输入信号(在这种情况下为x)也是如此。因此,输入x也必须位于L中。这种定位将直接影响内部信号的定位遵守此属性可以防止由于输入信号In1In2O1O2Ox2 Ox3O6a_Ob_OiX3d_OIX2a_InO4b_Inc_OO3c_Ind_InO5O768S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51iX3In1In2O1O2Ox2OX3O6a_Ob_OIX2iX3d_Oa_Inb_InO4O3c_Oc_Ind_InO5 O7见图12。 分块模型在某些地方,因为输入信号不被不同的地方共享。这种局部性分配方法将我们引向由以下定义表示的分区块。设φ ={P,T,F,μ0}是一个基本网系.然后,划分导致将网络划分为n个较小的网络,表示为i=(Pi,Ti,F对于i= 1到n,其中n是一组整数,每个Ti<$T使得(T1<$T2<$Tn)=并且每个Pi<$P使得(P1<$P2<$Pn)/=.这项工作没有解决的问题,找到最佳的本地化的计算w.r.t所产生的分布式系统的性能。同步系统的所有动作的局部化直接从输入和输出信号的局部化导出。本节还提出了一个优化的局部性分配方法,通过重新分布的地方,以避免局部过载所产生的大输入扇出。为了给一个系统的变迁分配局部性,我们需要定义一些方法,这些方法在[8,9]中作为算法给出该算法采用了一个双向的子网遍历,以分配地方的过渡访问。它以一个同步系统的Petri网模型作为输入,用Petri网表示.该算法的输出是同步系统的Petri网模型,局部性信息添加到模型中的每个转移。为了保证第6节中讨论的划分正确性,在应用局部性分配算法之前,要检查网络的步长持久性如果存在任何持续违规,则插入相关信号。[ 8 ]中提出的划分算法也满足正确性标准,即冲突解决。这是因为该算法将所有信号一致地放置在同一位置。将[8]中提出的算法应用于图1所示的系统11(a),导致图中所示的分区模型12个。如上所述形成的每个位置可以完全异步地实现,或者具有其内部时钟以控制所有内部计算S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)5169和输出信号的产生。为此,可以构建将生成本地时钟使能的适当包装器。这些包装可以使用现有的PN为基础的合成工具进行合成。关于包装合成的更多细节可以在[3,8]中找到。8结论本文讨论了用PN作为抽象模型的描述方法综合GALS系统的问题因此,使用PN构造的去离散化系统的粒度小于从先前的方法[3]获得的GALS系统可以通过将局部理论应用于保持输入输出信号的同步特性的同步系统模型来获得。这项工作提出了一个despersonisation的方法与一个相对清晰的路线自动化合成,同时保留的IO行为的同步系统。今后工作建议的方法需要自动化,以减少设计时间和设计人员的干预。可以进一步优化位置分配以满足各种标准,例如,最小化位置之间的互连并提高组件速度。也可以应用其他方式的非捆绑转换(例如,不一定考虑所有输入都被解捆绑),从而获得持久步骤的不同条件。确认我们感谢匿名推荐人提供的有益意见。这项工作得到了EPSRC的支持。引用[1] C. Carloni,K.McMillan和A.桑吉瓦尼-文森泰利延迟不敏感设计理论IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems,20(9):1059-1076,9 2001.[2] D.Potop-Butucaru , B. Caillaud 和 A. 祝 你 好 运 同 步 系 统 中 的 并 发 。 InProc. of ACSD 2004 ,Hamilton,Canada,2004.[3] S.达斯古普塔湾波托普-布图卡鲁湾Caillaud,A. Yakovlev[4] A. Madalinski,“基于偏序语义的异步系统交互式合成”。纽卡斯尔大学博士论文,2006年。[5] M. Koutny,M. Pietkiewicz-koutny,“具有局部性的初等网系统的变迁系统”。InProc. CONCUR,Bonn,Germany,2006,pp 173-187.[6] V. Khomenko,A. Madalinski,A. Yakovlev,“基于STG展开的单次插入和并发减少的编码冲突解决方案”。见Proc.ACSD,芬兰图尔库,2006年,第57-66页。[7] J. Desel,J. Esparza,“自由选择Petri网”。剑桥大学出版社,2005年9月。70S. Dasgupta,A.Yakovlev/Electronic Notes in Theoretical Computer Science 245(2009)51[8] S. Dasgupta,A. Yakovlev,“使用Petri网的去冗余技术”。Tech.报告系列NCL- EECE-MSD-TR-2007-124,MSD Group,纽卡斯尔大学EECE学院,2007年11[9] S. Dasgupta,纽卡斯尔大学博士论文,2008年。[10] G. Berthelot,1985年,《Advances in Petri Nets》LNCS,第222卷。施普林格出版社,柏林,1940年。[11]Steven M. Nowick,“突发模式异步控制器的自动合成”。 斯坦福大学计算机科学系博士论文,1993年。[12] Steven M.作者声明:David L. Dill,“使用本地时钟合成异步状态机”。在Proc.International Conf.ComputerDesign(ICCD),第192- 197页,IEEE计算机协会出版社,1991年10月。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功