没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记128(2005)231-246www.elsevier.com/locate/entcs异步硬件分层验证的统一CSP方法X. 王明夸特科夫斯卡湾狄奥多罗普洛斯张1伯明翰大学计算机科学学院Edgbaston,BirminghamB15 2TT,UK摘要形式验证在异步电路设计中越来越重要,因为缺乏全局同步时钟会由于并发性而产生错误(例如, 死锁)实际上不可能通过诸如仿真的常规方法检测到。提出了一种基于CSP及其模型检测器FDR的异步系统分级验证方法。该方法反映了异步硬件综合框架的分层性质,例如Balsa系统,并允许在不同的抽象级别上对系统进行验证,以防止死锁,延迟不敏感性,一致性和细化等属性。我们通过自动检测延迟敏感性和死锁引起的错误来证明我们方法的可行性简单的异步硬件组件。关键词:异步硬件,层次验证,CSP,模型检测,抽象层次。1介绍异步和GALS(全局异步局部同步)[17,9]设计技术是同步的重要替代方案,基于全局时钟的设计技术,通过通信子系统之间的局部握手同步协议实现同步移除全局时钟可能会导致高度并发、不确定的1{X.Wang,M.Z.Kwiatkowska,G.K.Theodoropoulos,Q.Zhang}@ cs.bham.ac.uk1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.04.014232X. Wang等人/理论计算机科学电子笔记128(2005)231IST系统2,其使得单独的模拟不足以作为测试方法。在本文中,我们提出了一种使用Balsa的异步硬件系统的形式化验证方法,Balsa是由曼彻斯特大学AMULET小组[17,7]开发的基于CSP[10Balsa被赋予模拟,但不是验证,工具。我们演示了如何巴尔萨程序,握手网络(又名。握手电路)和异步门电路可以转换为CSP [15],这反过来又使FDR [15](CSP的成熟模型检查器)能够用作后端验证工具。数据独立性可以用来解决数据路径缩减问题。所提出的方法可以实现作为一个附加到现有的巴尔萨设计和合成过程。本文件的结构如下。我们首先概述了异步硬件设计的VLSI编译框架。然后,我们提出了一个分层验证方法,作为框架的扩展,基于使用CSP作为统一的形式主义。接下来,我们说明了一个Balsa程序片段,握手网络,异步逻辑电路及其综合过程的帮助下的方法。对于每个级别(共三个),我们给出了CSP中Balsa组件的翻译语义,并描述了验证实验的结果最后,对本文的工作进行了总结,并对今后的工作进行了展望.2高级异步电路编译在已经使用的各种基于CSP的方法中(例如,[18,14,11]),一个特别有前途的方法是采用硅编译来自动生成来自高级规范的门级实现;最著名的例子包括Brunvand在这个异步逻辑综合框架内(参见图1),基于CSP的并行编程语言通常用于给出设计的高级算法描述。根据这样的描述,语法指导的编译创建握手组件的网络(组合),其中程序中的每个语言构造被映射到对应的握手实现。握手组件通常是预先设计的,并以门级电路片段的形式存储在库[2]请注意,高度并发的非确定性系统可能具有顺序的和确定性的黑盒行为,并且异步系统和同步系统中的确定性定义是不同的。X. Wang等人/理论计算机科学电子笔记128(2005)2312333分层方法基于硅编译框架,我们提出了一个层次化的方法来验证异步硬件设计,它利用FDR,CSP的模型检查器。这种方法围绕着硅编译中的两个层次结构:抽象层次结构(c.f.图1)和组件组成的层次结构。关键的观察是CSP适合描述所有三个级别的系统描述。 顶层描述了一个类似于标准CSP的同步系统;它利用了细粒度的并行性(顺序组合中的并行运算符),这是其他模型检查器很少支持的。两个较低的层次描述异步系统,这对标准CSP的表达能力提出了挑战基于我们新颖的调度器思想,我们发现异步系统不仅可以直接直观地在CSP中建模,而且可以简化为只使用跟踪模型。在某种意义上,我们的工作类似于Dill在所有三个级别上,系统都是高度并发的;过去的经验表明,FDR在高度并行的情况下工作得很好[16]。另一个重要的见解是,在所有三个级别上,都可以减少跨组件组合层次结构的验证问题。在同步级别,我们采用传统的基于规范的细化检查。在异步水平,我们采用了一种新的协议为基础的闭路测试。3.1跨抽象级别的抽象层次结构是管理异步电路设计复杂性的重要工具,无论是对于人类设计师还是对于验证工具。在编程语言层面,我们使用抽象的结构,如同步广播通信,共享变量,顺序和并行组合,描述了一个高层次的算法视图和硬件系统的结构设计。在握手级别,简单的异步握手信号和一组基本的握手组件(Fork、Split、Variable、Loop、Accuur、BinaryFunc等),实现同步广播、交错变量访问、控制顺序性和并行性。 在基本门级,握手信号被映射到线路上的转换。基本握手组件的功能由基本逻辑门综合而成。给定一个大型异步硬件设计,在最底层验证整个设计通常是不可行的通过利用抽象层次,整个验证问题可以分解为更小,更易于处理的问题。234X. Wang等人/理论计算机科学电子笔记128(2005)231不同层次的问题。由于我们在抽象的所有层次上都使用CSP,因此我们可以基于各种技术(如行为细化,动作细化,抽象解释(RAI)等)在层次之间建立正式的语义链接。RAI refine,CSP中的Balsa规范,在CSP中分为几个不同的握手协议。在一个系统的方法,我们希望利用这个链接在未来验证巴尔萨的编译功能和合成算法,并证明适当的正确性的建设结果的系统3.2跨组分粒度的在一个抽象层中,小的组件通常被组合成更复杂的组件。将组合层次结构扁平化来执行验证是不可取的。在同步的情况下,众所周知,CSP精化支持组合验证,也就是说,将组件的规范与其实现分开。在检查细化之后,在组成组件时可以使用规范而不是实现。异步硬件系统,在较低的层次上,是一个输入/输出系统,它由一系列由通道连接的异步组件组成。通道与延迟相关联。组件通过发送/接收具有非阻塞语义的信号进行虽然CSP通常将同一通道上的输入和输出同步到单个事件中,但我们选择分别对这两个操作进行建模,并使用调度程序来显式地调度输入和输出的延迟。调度程序将首先非确定性地选择发送组件的已启用输出(CSP进程的初始值),然后将其强制到接收组件的相应输入上。调度器的这种不确定性可以模拟系统的所有可能的延迟场景。如果系统使用调度程序正确运行,这意味着系统在所有延迟场景中都正确运行。也就是说,系统是延迟不敏感的。如果存在关于信道延迟的假设,例如等时分叉,则可以修改调度器以反映该假设。异步输入/输出系统可以是开路系统或闭路系统。开路系统是一个组件的模型,通常与一个协议相关联,在其接口上规定了输入和输出事件的所有合法序列。在验证闭路系统时,我们将系统与调度器并行运行。 如果调度程序将输出强制到输入时它死锁(也称为我们说这个系统是不正确的,在这个意义上说,X. Wang等人/理论计算机科学电子笔记128(2005)231235Balsa程序及其行为规范翻译CSP计划CSP规格语法制导翻译Rai握手网络及其协议翻译CSP网络&CSP协议异步逻辑综合Rai门级电路及其协议翻译电路CSP协议系统不构成一个良好的环境,其中所有的协议的子组件都遵守。由于调度程序参与每个事件的发生,因此调度程序的任何死锁都是全局的,因此很容易在FDR中检查。在验证一个开路系统之前,我们需要使用它的协议作为系统的环境来闭合它。开路验证的完整示例将在第7节中显示4巴尔沙Balsa既是一个异步硬件合成框架,也是一种类似CSP的语言,用于描述此类系统。Balsa生成的纯异步宏模块电路类似于Philips (One主要的不同之处在于Balsa扩展了七巧板,增加了更多的握手包[6,7]。) Balsa与技术无关(例如,通道连接可以可以使用速度无关或延迟不敏感的方案来实现),并且它针对用于产生门级网表的标准单元和FPGA技术。支持三个级别的仿真:Balsa级别的行为仿真,以及基本浇口和布局级别的功能和时序仿真(使用支持的商业CAD工具的本地仿真器)(图2)。 无验证工具服务器租用-美国服务租用图2中较弱的线条表示手动过程。从图中可以明显看出,Balsa中的大多数验证工作都是手动完成的图1.抽象的层次结构图2. 巴尔萨系统5异步 硬件编程硬件编程使系统设计人员能够在高抽象层次上设计复杂的异步VLSI电路236X. Wang等人/理论计算机科学电子笔记128(2005)2319ǁ||--|||ǁ|||5.1CSP中Balsa的翻译语义Balsa没有正式的语义,尽管Tangram有一个基于握手过程的语义[1]。但是握手过程是异步的,语义本质上是在握手级别。它比顶层抽象得多。在本文中,我们给出了一个CSP的翻译语义的Balsa程序直接在顶层。我们使用的CSP语言的变体类似于[14]和[8]中的CSP语言,它们具有命令式语法,但可以给出异步电路的简洁描述3:CSP生产线CMD::= c?x:b|c!e|Skip|CMDQCMDJ|CMDHCMDJ| CMD|[ chans]|CMDj|CMD\chans|CMD \chans| l(e1,..., en)|if b then CMD else CMD J|{l(z1,., zn)= CMD,. }其中x、y和z是变量4,chans是一组频道名称(例如,c1,. ,cn),b是b值表达式,e是值表达式。 c?x:b是一个选择性输入命令;如果c上的输入x满足b,则接受该输入。[chans]是一个接口并行操作符;它只在chans中的事件上执行它的两个子进程。有时候,和运算符也被使用:是一个交织运算符,而当字母表从上下文中是不言自明的时候,是一个缩写的平行。顺序组合比选择更强,而选择比平行组合更强作为一个运行示例,我们将使用Balsa代码片段作为仲裁器:import[type]--导入某些类型和库过程过程Arb--过程定义组件(input NTarget 1,NTarget 2:InsAdd;--组件的输入output NTarget 2: InsAdd)--组件的输出是局部变量C:bit--内部变量begin looparbitrate-- arbitrate 是 双 向 选 择 NTarget 1 then-- 如 果NTarget1.c= C,则第一个等待NTarget 1then NTarget-NTarget1 end|NTarget2然后--第二个等待NTarget 2C:=NTarget2.c||NTarget-NTarget2#[32:->||DW(>CLR|n目标[32:=->@1SFV->X. Wang等人/理论计算机科学电子笔记128(2005)23124199996.3CSP中握手网络的验证让我们假设一个Balsa程序B,它在CSP中的规范是P,被编译成一个握手网络N,n是N中的一个握手组件,它在CSP中的协议是p。为了验证N正确地实现了B,我们需要首先握手扩展(RAI refine)P,以获得网络的握手级协议PRT。然后,对于N中的每个n,其协议p被用作其行为规范。组成这些ps(因为它们在N中连接)给我们一个网络的CSP转换,通过调度器并行地放置NRM和PRT,我们可以检查FDR中的死锁,以证明NRM符合PRT,即N是B的正确实现。在上面的指令提取示例中,仲裁器单元arb的CSP规范是:spec(c)=(ntarget 2?x?cJo ntarget!x的!cJont2endospec(cJ))9 9 9Q(ntarget 1?x?如果c = cJ,则ntarget!x的!celseSkipont1endospec(c))9 9 9由于NTarge1和NTarge2都是被动端口,而NTarge2是主动端口,因此上述协议可以握手扩展为:prot(c)= serialize(NT 2. r?x?cJo NT。r!x的!cJo NT。a. NT 2. ao prot(cJ)|||NT1. r?x?cJo 如果c = cJ,则NT。r!x的!cJo NT。aelse跳过o NT 1. aoprot(c))9 9 9 9序列化=NT。r?x?cJo(NT 1. 2. a)o连载9 9其中,在上文中,prot是用于图5的(仲裁)握手网络的协议,而protJ是用于当对选择激活没有干扰时的优化(选择)握手网络由于篇幅限制,我们将不展示握手级别的验证相反,一个完整的例子,使用基于协议的闭路测试将显示在门级。7基本门电路在识别和定义了握手组件的基本集合(Balsa为40+)之后,每个组件都可以基于某种编码方案手动或自动合成为门级电路。编码方案决定如何使用门级电路中导线的电压转换来实现握手级的抽象请求/确认和数据信号。7.1异步逻辑综合给定一个握手组件,合成过程的初始输入应该是它的握手协议。然后,合成过程具体化(RAI重新,242X. Wang等人/理论计算机科学电子笔记128(2005)231WDr0Ir不Ia或Sr瓦萨土地1OandANDnIandN2WDaIC1OcCO1'fork我IC2O2'O1WDrI叉O2In1读取端口输出RDIn2−根据编码方案对协议进行改进,产生新的门级协议。这是一个设计过程;新协议必须考虑它对合成电路的速度、成本、安全性等例如,FV组件最近由曼彻斯特AMULET集团重新设计,用于双轨电平信号方案。 新的细化协议如图6(a)所示(a)(b)第(1)款图6.FV和T元件的门级协议由于电平信号,有用的转换通常是向上的(+ )。向下的过渡(),只是为了将电压恢复到零 以便为下一轮向上过渡做准备。一图7. FV实现图8. 抽象FV实现基于新协议,他们提出的实现如图7所示(详细信息可在[23]中找到)。T元件的行为由图6(b)8的协议指定。8输入/输出接线定义见图8。X. Wang等人/理论计算机科学电子笔记128(2005)2312439999999999999999999在图6(a)中,WDr0+表示传入总线上的第一个比特的到达,而WDr[1,n−1]+表示所有比特的到达。所有位到达的检测由图7中的CD7.2CSP验证假设握手组件H在门级电路G中实现,其协议由CSP中的PRT捕获。设g是G中的门级元素,设其在CSP中的协议为p。 然后,对于G中的每个g,其协议p用作行为规范。组合这些ps(因为它们在G中连接)会产生网络的CSP转换,把并行的调度器,我们证明了并行符合PRT通过检查FDR中的死锁自由。有时,元件g本身可以由电路中甚至更基本的元件来实现。t(例如,FV电路中的T元件)。 那么g的协议就是t的协议。通过将t转换为CSP,我们可以类似地证明t实现了g。对于FV的例子,抽象后的数据总线和完成检测,tection,门级电路实现如图8所示转换图6(a)中的STG,我们获得电路的CSP协议为:protocolFV=(writer_reader)o WDa。下载协议FVwriter=(WDr. 上一页向下)。上WDr。下来reader=(WDr 0. 上,上至RDr。上一页向上)o RDa。上萨。上,降到RDr。降到0 RDa。下奥萨。下来9 9 9 9 9 9类似地,我们可以得到T元素的行为规范:protocolT= Ir. 上或下。去奥阿。上O(或。去奥阿岛。在阿格拉。向上,向上。向下)9 9 9 9 9或Ia。下载协议9 9电路中有两个分叉;它们的行为规范是:fork0 = I. 向上O(O 1. 升到1000向上)o叉1fork1 = I. 向下O(O 1. 降低二氧化碳浓度。向下)o叉0Muller-C元素具有以下行为:protocolC=(Ic1. 2. 上)O O. upoprotocolCJprotocolCJ=(Ic1. 2. 向下)O O. 下载协议C在数据总线抽象之后,READPORT元件的功能类似于与门:readport=(In1. 2. 上)O输出。向上读端口J读取端口J=(In1. downo(Out)2. 向下)2. downo(Out)1. down))oreadport244X. Wang等人/理论计算机科学电子笔记128(2005)23199单输入否定与门的行为可以类似地规范。但是,由于它是在这个特定的电路中使用的有限的方式,它的协议是相当不同的,从上述。这是一个使用协议而不是元素的完整规范进行并且N= I和N 2. 上0(1和1)。上一页2. 下)O O和。向上o和NJ9 9 9且NJ= I且1. 在奥兰德。向下O和N9 9我们可以从上述具体化中得到的一个重要的观察结果是,没有任何元素共享任何事件。这是由于我们的原则,分离输入这样我们就可以使用调度器来链接和同步它们。 调度器的规格如下:signalling(x,y)= x?zo y!z调度程序=(信令(WDr0,Ir)Q信令(Oc,WDa)Q信令(WDr,I)Q信令(O1,Ic 2)Q信令(O2,In 2)Q信令(O1J,IandN 2)Q信令(O2J,In 1)Q信令(O and,Ic1)Q信令(Ia,I and1)Q信令(Or,Sr)Q信令(Sa,Ia)Q信令(RDr,IJ)Q信令(Out,RDa))其中信令(x,y)将一个元件的输出通道x连接到另一个元件的输入通道y。每当在x上产生输出9时,调度器将强制它到y上。将所有元素与调度程序和协议并行protocolFV,我们最终获得了下面的测试系统测试系统=调度程序||protocolFV ||protocolC||叉0||读取端口||叉0J||和N 0||协议用FDR检查测试系统,我们发现它死锁了。其中一个死锁跟踪是:(WDr. 上,我。up)(O 2. 上,2. up)(WDr 0. 起来,先生。上)(或。上,先生。向上)(RDr. 起来,我J。up)(O 2 J. 上,在1。up)(Out. 上,RDA。up)(Sa. 起来,欧阿。上)Ia. 起来然而,通过向fork j添加等时fork约束,RDr的到达。在ANDn上将超过Ia。上,所以封锁了Oand。提前上去这是由FDR证实的。实际上,由于时间上的另一个小限制,我们用FDR证明上述实现是正确的10.8结论和今后的工作我们已经提出了一个分层框架的综合方法,以允许设计,仿真和验证异步硬件中,9对于这个例子,它是向上转换或向下转换。10CSPm中的详细信息和完整脚本可以在[23]中找到X. Wang等人/理论计算机科学电子笔记128(2005)231245巴尔萨体系。我们的方法的主要优点是,它自然地利用了电路设计人员用来管理复杂性的不同抽象层次,将所有三个抽象层次纳入统一的CSP形式主义中,使我们有机会在语义上将它们联系起来,并使用成熟的CSP模型检查器FDR作为后端验证工具,以证明或反驳重要的异步电路属性,如死锁、延迟不敏感性、等价性和细化。我们已经证明了我们的方法的可行性,通过翻译和验证的异步处理器的组件,发现一个真正的未知的错误在FalseVariable电路设计引起的延迟敏感性。与相关工作相比,我们在较低级别的调度方法不仅可以检查异步电路的安全条件[5],还可以检查进程条件[8]。显式引入调度器的优点是它使我们能够使用标准CSP理论,而不是专门的异步理论[5,12]。它使“匿名”更容易理解和验证。正式的语义联系和严格的异步理论的比较,但是,目前正在调查的主题。当然,需要做更多的工作,以充分实现我们的做法。目前,我们已经为Balsa系统中的所有主要35个握手组件开发了CSP规范(或者更准确地说,协议)[20]。基于这些规范,一方面,我们可以验证它们在门级的实现,如第7节所示;另一方面,我们可以验证将Balsa程序转换为握手组件网络的编译函数。以前,我们的研究伙伴在将握手组件组成握手网络时遇到了一些不兼容性问题。与此同时,我们也在进行一个更大的案例研究,如[2]中的案例。它基于与曼彻斯特AMULET小组合作完成的异步MIPS处理器核心设计[21]。其他未来的工作包括在不同级别上自动化翻译,并完成我们在标准CSP中建模异步硬件的理论确认我们要感谢Doug Edwards、Andrew Bardsley和Luis Plana的宝贵建议和帮助。该研究由EPSRC项目GR/S11091/01 GR/S11084/01资助。246X. Wang等人/理论计算机科学电子笔记128(2005)231引用[1] K.范·伯克尔。握手电路-一种用于超大规模集成电路编程的异步结构。剑桥大学出版社,1993年。[2] G.伯特威斯尔异步微流水线中的控制状态。AINT 2000,第45-55页,代尔夫特理工大学,2000年。[3] E. Brunvand和M.斯塔基 一个集成的设计与仿真环境自定时系统。在IFIP VLSI[4] T. A.楚从图论规范综合自定时VLSI电路。麻省理工学院博士论文,1987年。[5] D. L. 迪尔速度无关电路自动分级验证的迹理论。ACM杰出论文。MIT Press,1993.[6] D. Edwards和A.巴兹利Balsa:一个异步硬件系统。异步电路设计原理,第二部分,2001年12月,编辑:J。Sparso,S.费伯[7] D. Edwards和A.巴兹利Balsa:一种异步硬件综合语言。计算机杂志,第45卷,第1期,第12-18页,2002年1月[8] J. C.埃伯根将程序转换为延迟不敏感电路。埃因霍温科技大学计算机科学系一九八七年十月[9] S. Hassoun和D.马库列斯库面向GALS设计方法。在FMGALS2003年。[10] C. A. R.霍尔通信顺序进程。Communications of ACM 21(8):666- 677(1978)[11] H. Hulgaard和S. M.伯恩斯一类有选择CSP程序的有界延迟时间分析。在ASYNC[12] M. B.约瑟夫和J. T.乌丁 延迟不敏感电路的代数。 在90年的CAV 531,第343-352页。Springer-Verlag,1990.[13] R. 拉兹岛。数据隐含的语义研究及其在建模中的应用。博士论文,牛津大学计算实验室,1999年。[14] A. J·马丁异步超大规模集成电路的综合。王志文,大规模积体电路设计之形式化方法,台北,1990。[15] A.罗斯科 并发的理论与实践。 Prentice-Hall,1998年。[16] A. 罗 斯 科 将 共 享 变 量 程 序 编 译 成 CSP 。 PROGRESS 2001 研 讨 会 论 文 集 。http://web.comlab.ox.ac.uk/oucl/research/areas/concurrency,2000年。[17] J. Sparso和S.费伯异步电路设计原理:系统观点。Kluwer Academic Publishers,2001.[18] G. Theodoropoulos和J.V. Woods。Occam:异步硬件描述语言?在IEEE Euromicro[19] G. Theodoropoulos和Q.张某异步流水线中控制冒险的分布式着色算法。Proceedings of I-SPAN[20] X.王. Balsa握手组件的CSP翻译。Tech.报告(CSR-04-11),伯明翰大学计算机科学学院,2004年。[21] Q. Zhang和G.狄奥多罗普洛斯异步MIPS R3000处理器ACSAC'03会议记录,LNCS 2823,第137-150页,Springer,2003年[22] 异步硬件分布式仿真和形式验证的集成框架。http://www.cs.bham.ac.uk/research/parlard网站。[23] 巴尔沙 验证 示例 页. http://www.cs.bham.ac.uk/research/parlard/examples网站。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功