规则编译论文-牛当当

规则编译论文-牛当当

导读:本文包含了规则编译论文开题报告文献综述及选题提纲参考文献,主要关键词:知识编译,扩展规则,超扩展规则,启发式

规则编译论文文献综述

牛当当[1](2018)在《基于扩展规则的知识编译方法研究》一文中研究指出知识编译能够提高重复性任务的求解效率,并且已经成功被应用到模型检测、逻辑综合、诊断、产品配置、系统设计、自动规划等多个领域。知识编译的主要思想是将问题的求解分为两个基本阶段:离线编译和在线推理。提高知识编译方法的编译效率能够减少离线编译所消耗的时间,而提高知识编译方法的编译质量则能够减少每次在线推理所消耗的时间。在扩展规则的基础上,Lin等人提出了一种基于扩展规则的知识编译方法KCER,可以将子句集编译为EPCCL理论。随后,许多学者针对EPCCL理论的编译展开了深入地研究。本文基于扩展规则和超扩展规则从启发式选择、新型编译框架、并行编译、互补知识编译等方面研究了EPCCL理论的编译方法,旨在进一步提高扩展规则知识编译方法的编译效率和编译质量。本文的主要研究内容和创新成果如下:1、提出了相关性矩阵的概念,并定义了相关集。通过分析相关集的性质,利用扩展规则在相关性矩阵和KCER算法之间建立了联系。基于相关集的基本信息以及相关性矩阵与KCER算法的联系,本文设计了MNE启发式和M2S启发式,用于选择满足“相关集所不能扩展出的极大项集对应EPCCL理论规模较小”的子句。不同于现有启发式策略,MNE启发式和M2S启发式主要考虑不同子句长度实例中的启发式信息。最后,设计并实现了MNE_KCER算法和M2S_KCER算法。实验结果表明:对于随机子句长度的实例,MNE_KCER算法和M2S_KCER算法相比于KCER算法能够大幅度降低编译结果的规模,并且具有更高的编译效率。2、提出了一种新的EPCCL理论编译算法:求交知识编译算法IKCHER,适合难解类SAT问题的知识编译,同时是一种可并行的知识编译算法。基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集、差集和并集,并将所得结果以EPCCL理论的形式保存。IKCHER算法基于超扩展规则,通过计算所有子句所不能扩展出极大项集的交集得出输入子句集所不能扩展出的极大项集,并将结果保存为EPCCL理论,然后再用相同方法求得上述计算结果所不能扩展出极大项集对应的EPCCL理论,进而得出与输入子句集等价的EPCCL理论。实验结果表明:IKCHER算法具有较高的编译效率和编译质量,是目前为止最优秀的EPCCL理论编译算法之一。3、提出了UKCHER算法和IKCHER算法的并行化策略,并实现了相关并行算法。并行推理是提高推理方法效率的有效策略。基于超扩展规则研究了多个EPCCL理论的并行求并合并和并行求交合并,分别提出了PUAE算法和PIAE算法。结合并行求并编译和并行求交编译以及上述合并策略,提出了P-UKCHER算法和P-IKCHER算法。基于对输入EPCCL理论对应普通子句集的利用,设计了高效的并行求并算法imp-PUAE和并行求交算法imp-PIAE,以及相应的并行编译算法impP-IKCHER和impP-UKCHER。实验结果表明:P-UKCHER算法虽然没有提升UKCHER算法的效率,但能够提升UKCHER算法编译结果的质量,最好情况下可提升4倍;impP-UKCHER算法能够提高UKCHER算法的效率,同时也能够提升编译结果的质量,同样最好情况下可提升4倍;P-IKCHER算法所使用的合并策略并没有起到加速的效果,反而使得编译效率和编译质量有所下降;impP-IKCHER算法提高了IKCHER算法的编译效率,四核并行下最高可提高两倍。4、提出了互补知识编译方法,是一种新的非等价的知识编译方法。提出了互补公式(COMF)的概念,并基于超扩展规则提出了C2C编译算法。C2C能够将任意子句集编译为相应的c-FCCD公式。c-FCCD是一种互补公式,同时也是一种EPCCL理论。通过理论分析,证明了COMF和c-FCCD多项式时间内所能支持的知识编译图谱中的查询操作,以及COMF、c-FCCD和EPCCL理论多项式时间内所能支持的知识编译图谱中的转化操作。其中,c-FCCD能够在多项式时间内支持知识编译图谱中的全部八种查询操作以及两种转化操作。不同于现有知识编译方法,互补知识编译以互补公式为编译目标进行编译,然后在互补公式上完成在线推理任务。实验结果表明:相比于现有基于扩展规则或超扩展规则的知识编译算法,C2C具有最优的编译效率和编译质量。综上,本文从启发式选择、新型编译框架、并行编译、互补知识编译等方面进一步提高了EPCCL理论编译方法的编译效率和编译质量,同时本文工作能够为其它目标编译语言编译方法的优化提供借鉴。(本文来源于《吉林大学》期刊2018-06-01)

王琦[2](2018)在《面向非规则应用的SIMD自动向量化编译技术研究》一文中研究指出SIMD扩展部件是一种广泛存在于主流处理器芯片中的向量加速器件,是构建当代计算机系统的重要组成,能有效提升各种应用的处理效能。自动向量化编译作为一种构造向量程序的主要手段,已得到广泛的研究并在各种主流编译系统中予以实现。然而,当前自动向量化编译仅能处理规则访存模式的应用,对含有复杂非规则访存模式的各种新型应用,尚缺乏有效的处理能力。针对自动向量化编译面临的挑战,本文依循自动向量化的向量挖掘、优化与代码生成过程,开展面向非规则应用的自动向量化编译优化技术研究,对非规则应用的向量化挖掘、访存优化以及非规则数据访问的向量指令生成深入研究,主要工作和贡献如下:(1)非规则应用的向量化挖掘。现有编译器的自动向量化能够对规则应用给出精准的数据分析,从而指导程序进行向量代码的转换。非规则应用中同样蕴含着向量并行执行的机会,但由于其访存不连续或者依赖于输入数据,使得编译器在编译阶段无法建立准确的数据引用关系,因而放弃其向量化的机会。因此本文以Inspector/Executor模型为基础,提出基于Inspector的非规则数据访存模式识别,在计算之前对非规则应用的访存模式进行预分析,并且针对不规则规约操作存在向量写冲突的问题,提出非规则数据的向量打包策略,将不同的迭代打包成向量,解决非规则应用的向量挖掘的问题。(2)非规则应用的访存优化技术研究。非规则应用中,访存不连续性和随机性使得程序数据局部性较差,访存效率较低。因此为了提高非规则应用的访存效率,本文提出分层分块算法,提高数据局部性。其次提出基于访存记录的数据预取算法,以隐藏内存访问的延迟。最后提出基于最大匹配度的向量寄存器重用,以减少程序访存次数,提升程序执行效率。(3)非规则数据访问的向量指令生成。SIMD扩展指令可以将内存中连续的数据一次性的加载到向量寄存器中。但是对于非规则应用的数据访问随机性,可能使向量包内同构语句的数量小于向量化因子,并且一次向量加载指令不能将非规则数据加载到向量寄存器中去,所以需要对向量寄存器的部分使用以及非规则数据访问的向量代码生成展开研究。因此本文提出不充分向量化以及非规则向量访存的实现方案。最后提出代价模型的计算,以选择最优方案对程序进行向量变换。为验证本文提出方法的正确性和有效性,以GCC5.3.0编译器为基础实现了本文提出的算法。通过对选择的程序进行测试,本文的研究能提升SIMD扩展部件的加速效能,对于编译系统的研制以及应用程序的优化存在一定的指导意义。(本文来源于《战略支援部队信息工程大学》期刊2018-04-15)

张庆花,赵荣彩,张素平,丁丽丽,王鹏翔[3](2018)在《面向非规则Doacross循环的反馈式编译框架》一文中研究指出非规则Doacross循环包含复杂数据流以及控制流引起的不确定依赖关系,传统并行化技术对其采取保守处理,错失不少并行机会。文章提出一种面向非规则Doacross循环的反馈式编译方法,利用程序运行时的剖面信息指导自动并行化工具进行并行化。通过插桩和试运行的方式得到程序的上下文信息,反馈给并行化工具,利用反馈信息构建程序依赖图,进而对程序进行并行化。实验结果表明该方法对测试用例有明显的性能提升。(本文来源于《信息工程大学学报》期刊2018年01期)

杜铁[4](2017)在《基于规则库的编译时代码安全检测方法研究》一文中研究指出程序安全漏洞对用户隐私和安全构成了巨大威胁。传统研究侧重于安全漏洞的检测,在运行时防御、动态检测和静态检测等方面做了大量工作。这些检测工作虽然发现了一大批未分类的安全漏洞,但较少为开发人员解决漏洞问题提供充分的调试信息。与之前的工作不同,检测系统致力于安全漏洞的自动分类,并为开发人员解决漏洞问题提供清晰的调试信息。现有的安全漏洞可以被描述为一系列的规则,进一步简化为数学断言问题。基于规则库的编译时代码安全检测系统,可以自动的把安全漏洞分为叁类,包括确定性漏洞,内部不确定性漏洞以及外部不确定性漏洞。实现上述分类目标的核心技术主要包括:根据不同类型的安全漏洞的特点建立规则库(缓冲区溢出,空指针引用,除零);结合控制流分析以及指针分析,通过抽象语法树来获取规则中出现的必要信息;验证规则是否成立。如果成立,则判定为一个确定性漏洞;否则,运用一种新的逆向污点分析去区分剩下的两种漏洞为内部不确定性漏洞或外部不确定性漏洞。在LLVM(3.5.0)的基础上实现了基于规则库的编译时代码安全检测系统,与标准的编译器处理流程完全并行,编译时的额外开销几乎可以忽略不计。基于微基准程序和14个真实程序的实验结果,证明了基于规则库的编译时代码安全检测系统在漏洞检测率和误报率上的显着提升,同时也证明了安全漏洞分类机制的准确性。(本文来源于《华中科技大学》期刊2017-05-01)

刘磊,牛当当,吕帅[5](2016)在《基于超扩展规则的知识编译方法》一文中研究指出超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集与差集,并将所得结果以EPCCL理论的形式保存.该文首次提出了扩展反驳方法,是一种新型推理方法,并在该推理方法与知识编译之间建立了联系.基于超扩展规则的性质,该文还提出了两种知识编译算法:求并知识编译算法UKCHER和求差知识编译算法DKCHER,是两种新的知识编译算法.算法UKCHER是目前为止唯一一个可并行的EPCCL理论编译算法,算法DKCHER对于相变点附近的难解问题具有较高的编译效率和编译质量.实验结果表明:UKCHER算法的编译效率和编译质量均优于Lin等人提出的KCER算法;当子句数和变量数的比值较大时,DKCHER算法的编译效率和编译质量是最优的,相比于现有EPCCL理论编译算法,该算法具有较强的竞争力.(本文来源于《计算机学报》期刊2016年08期)

牛当当[6](2015)在《基于超扩展规则的高效知识编译方法研究》一文中研究指出扩展规则推理方法是2003年提出的一种新型推理方法,得到了国内外学者的认可。基于扩展规则能够实现命题逻辑中的推理问题求解及知识编译算法设计。本文旨在提高基于扩展规则的知识编译算法的编译效率和编译质量,其中编译质量用编译结果的规模来衡量。本文首先提出了一种新的推理规则,超扩展规则(SER),并证明了超扩展规则与扩展负超归结的关联关系;利用超扩展规则,能将一个SAT问题编译为EPCCL理论,因此重写了殷明浩等人提出的KCER算法;并提出了基于超扩展规则的动态在线推理算法IKCCER,采用离线编译和在线推理过程交互执行的方式,在保持推理效率不改变的同时,极大地降低了空间复杂性。动态在线推理进一步扩展了基于扩展规则的知识编译方法的应用范围。超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集与差集,并将所得结果以EPCCL理论的形式保存。本文首次提出了扩展反驳方法,是一种新型推理方法,并在该推理方法与知识编译之间建立了联系。基于超扩展规则的性质,本文还提出了两种知识编译算法:求并知识编译算法UKCHER和求差知识编译算法DKCHER,是两种新的知识编译算法。算法UKCHER是目前为止唯一一个可并行的EPCCL理论编译算法,算法DKCHER对于相变点附近的难解问题具有较高的编译效率和编译质量。实验结果表明:UKCHER算法的编译效率和编译质量均优于Lin等人提出的KCER算法;当子句数和变量数的比值较大时,DKCHER算法的编译效率和编译质量是最优的,相比于现有EPCCL理论编译算法,该算法具有较强的竞争力。本文提出的叁种知识编译算法从不同角度提升了扩展规则知识编译算法的性能。IKCCER算法改善了KCER算法的内存消耗,从而使得原本KCER算法因内存溢出而解决不了的SAT实例得以解决。DKCHER算法和UKCHER算法是基于超扩展规则的两种新型结构的算法。不同于KCER算法的桶删除理论,上述两种算法采用了新的架构,因此与KCER算法具有明显不同的特性。DKCHER算法更适合于相变点附近的SAT实例,而UKCHER算法能够通过动态在线推理提前判断出输入子句集的可满足性。(本文来源于《吉林大学》期刊2015-04-01)

谷文祥,王金艳,殷明浩[7](2011)在《基于MCN和MO启发式策略的扩展规则知识编译方法》一文中研究指出在基于扩展规则的知识编译算法的基础上提出了2种启发式策略:MCN策略和MO策略.MCN策略和MO策略利用子句集的信息分别选择相应子句和变量,减少扩展规则的使用次数,进而降低知识编译后目标子句集的规模.在此基础上,设计并实现了MCN_KCER,MO_KCER和MCN_MO_KCER算法.实验结果表明:2种启发式策略都可以大幅度减小编译后的子句集规模,同时使用它们的效果更为明显,经过编译后得到的子句集规模是原算法的1/3~1/39,从而大幅度提高之后的在线推理阶段的效率.(本文来源于《计算机研究与发展》期刊2011年11期)

殷明浩,孙吉贵,林海,吴瑕[8](2010)在《可能性扩展规则的推理和知识编译》一文中研究指出在扩展规则的基础上提出了可能性扩展规则.给出了基于可能性扩展规则的可能性逻辑推理方法,利用互补因子的概念来估价推理问题的复杂度.扩展了经典逻辑的蕴含可控制类和可满足可控制类的定义,提出了可能性蕴含可控制类、不一致性程度计算可控制类的概念.在可能性扩展规则的基础上提出了EPPCCCL(each pair of possibilistic clauses contains complementary literals)理论,并证明了该理论是在最优化形式蕴含可控制类和不一致性程度计算可控制类中的,可以作为可能性知识编译的目标语言.(本文来源于《软件学报》期刊2010年11期)

杨海涛[9](2010)在《规则引擎中规则描述语言及编译系统的研究与实现》一文中研究指出在全球化、社会化商品经济的浪潮中,企业所身处商业环境的变化也日益加快。为了保持竞争优势,提高自身核心竞争力,企业需要不断调整其商业策略、优化业务流程,提高运营效率以应对商业环境的变化。相应地,企业内部的IT支撑系统也必须紧跟变化需求,对企业业务流程的快速变化做出支持。为了使得系统能够灵活地实现对业务流程快速变化的适应,可以通过应用规则引擎实现业务规则和代码的分离与集中管理。商业策略制定者与业务人员可以通过运用规则描述语言设计、更新规则,直接参与规则的生命周期管理;系统开发人员则可以将更多的注意力集中于IT系统的设计与实施之上。将规则引擎应用于IT系统,可以有效改善软件系统的开发流程并使系统在可重用性方面受益。目前主流规则引擎在企业应用中,主要存在规则描述语言过于专业化,给许多非技术背景的使用者的学习、使用、分析带来了一定程度的困难。另外,大部分开源规则引擎的规则描述语言仅在规则中支持Java语言实现的外部系统接口函数,限制了规则描述语言的表达能力并增加:了规则引擎与非Java接口的外部系统进行集成的成本。针对规则引擎使用过程中易用性、功能完备性和兼容性方面需求,本文在对当前主要规则引擎研究及分析的基础上设计了一种规则描述语言。该语言基于产生式规则设计,包括4层语法结构的规则条件部分和全面支持C语言语法的规则推论部分,增强了规则描述语言的易用性和规则引擎与外部系统间的兼容性。围绕文中设计的规则描述语言,本课题设计并实现了一个支持该规则描述语言的规则引擎TSEGRULEENGINE。在规则引擎的设计过程中提出了嵌套编译技术流程的概念,实现了对规则描述语言中两种不同语法的编译处理工作,设计了一个开放接口支持不同算法的规则推理流程并应用编译结果对事实和规则进行推理。论文中设计实现的规则引擎被应用于某电信计费系统在包月订购关系计费场景中进行了相应的测试,验证了系统的可用性。(本文来源于《北京邮电大学》期刊2010-01-13)

杨四才[10](2009)在《面向非规则计算的帮助线程预编译技术研究》一文中研究指出随着微处理器与存储器之间速度差异的日益增长,制约系统整体性能的存储墙问题也越来越严峻。现在,非规则计算出现在许多重要的科学计算应用中,由于访存模式的非规则性,使得非规则计算程序往往造成大量的缓存缺失。延迟容忍技术是克服存储墙问题的一种有效方法,已成为数据预取领域的研究热点。基于帮助线程的数据预取利用空闲的硬件上下文、投机性地预取主线程需要的数据,达到延迟隐藏的目的。由于人工书写帮助线程实现数据预取是一件非常繁琐而且耗时的工作,因此深入研究帮助线程的预编译技术,具有重要的理论意义和实用价值。本文是在共享高速缓存的多核处理器平台下,进行的面向非规则计算的帮助线程预编译技术研究。针对现有的基于帮助线程的数据预取方法,提出了一种预编译框架,自动化的完成线程的创建、数据的预取以及线程间的通信和同步工作。本文首先总结了前期研究成果中的五种数据推送框架,通过分析它们的优点和局限,提出了一种新的数据推送方法——交织同步推送方法,该方法不仅能解决不同计算量下的数据推送问题,而且具备较低的通信和同步开销的优点。实验重点是面向非规则计算的帮助线程预编译技术研究。本文在交织同步推送方法的基础上,设计了一套适用于静态帮助线程技术的预编译框架,真正实现由编译器自动生成帮助线程;最后在该框架下对多个基准测试程序进行了实验分析并获得20%以上的加速效果。(本文来源于《北京理工大学》期刊2009-06-22)

规则编译论文开题报告

(1)论文研究背景及目的

此处内容要求:

首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。

写法范例:

SIMD扩展部件是一种广泛存在于主流处理器芯片中的向量加速器件,是构建当代计算机系统的重要组成,能有效提升各种应用的处理效能。自动向量化编译作为一种构造向量程序的主要手段,已得到广泛的研究并在各种主流编译系统中予以实现。然而,当前自动向量化编译仅能处理规则访存模式的应用,对含有复杂非规则访存模式的各种新型应用,尚缺乏有效的处理能力。针对自动向量化编译面临的挑战,本文依循自动向量化的向量挖掘、优化与代码生成过程,开展面向非规则应用的自动向量化编译优化技术研究,对非规则应用的向量化挖掘、访存优化以及非规则数据访问的向量指令生成深入研究,主要工作和贡献如下:(1)非规则应用的向量化挖掘。现有编译器的自动向量化能够对规则应用给出精准的数据分析,从而指导程序进行向量代码的转换。非规则应用中同样蕴含着向量并行执行的机会,但由于其访存不连续或者依赖于输入数据,使得编译器在编译阶段无法建立准确的数据引用关系,因而放弃其向量化的机会。因此本文以Inspector/Executor模型为基础,提出基于Inspector的非规则数据访存模式识别,在计算之前对非规则应用的访存模式进行预分析,并且针对不规则规约操作存在向量写冲突的问题,提出非规则数据的向量打包策略,将不同的迭代打包成向量,解决非规则应用的向量挖掘的问题。(2)非规则应用的访存优化技术研究。非规则应用中,访存不连续性和随机性使得程序数据局部性较差,访存效率较低。因此为了提高非规则应用的访存效率,本文提出分层分块算法,提高数据局部性。其次提出基于访存记录的数据预取算法,以隐藏内存访问的延迟。最后提出基于最大匹配度的向量寄存器重用,以减少程序访存次数,提升程序执行效率。(3)非规则数据访问的向量指令生成。SIMD扩展指令可以将内存中连续的数据一次性的加载到向量寄存器中。但是对于非规则应用的数据访问随机性,可能使向量包内同构语句的数量小于向量化因子,并且一次向量加载指令不能将非规则数据加载到向量寄存器中去,所以需要对向量寄存器的部分使用以及非规则数据访问的向量代码生成展开研究。因此本文提出不充分向量化以及非规则向量访存的实现方案。最后提出代价模型的计算,以选择最优方案对程序进行向量变换。为验证本文提出方法的正确性和有效性,以GCC5.3.0编译器为基础实现了本文提出的算法。通过对选择的程序进行测试,本文的研究能提升SIMD扩展部件的加速效能,对于编译系统的研制以及应用程序的优化存在一定的指导意义。

(2)本文研究方法

调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。

实证研究法:依据现有的科学理论和实践的需要提出设计。

定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。

定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。

跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。

模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

规则编译论文参考文献

[1].牛当当.基于扩展规则的知识编译方法研究[D].吉林大学.2018

[2].王琦.面向非规则应用的SIMD自动向量化编译技术研究[D].战略支援部队信息工程大学.2018

[3].张庆花,赵荣彩,张素平,丁丽丽,王鹏翔.面向非规则Doacross循环的反馈式编译框架[J].信息工程大学学报.2018

[4].杜铁.基于规则库的编译时代码安全检测方法研究[D].华中科技大学.2017

[5].刘磊,牛当当,吕帅.基于超扩展规则的知识编译方法[J].计算机学报.2016

[6].牛当当.基于超扩展规则的高效知识编译方法研究[D].吉林大学.2015

[7].谷文祥,王金艳,殷明浩.基于MCN和MO启发式策略的扩展规则知识编译方法[J].计算机研究与发展.2011

[8].殷明浩,孙吉贵,林海,吴瑕.可能性扩展规则的推理和知识编译[J].软件学报.2010

[9].杨海涛.规则引擎中规则描述语言及编译系统的研究与实现[D].北京邮电大学.2010

[10].杨四才.面向非规则计算的帮助线程预编译技术研究[D].北京理工大学.2009

标签:;  ;  ;  ;  

规则编译论文-牛当当
下载Doc文档

猜你喜欢