C2E:一个高性能的EPCCL编译器

提出一个新的基于DPLL的编译算法KCDP,从而成功地将EPCCL理论和SAT求解联系起来,使得目前很多应用在基于DPLL的SAT求解器中先进的技术都能被引入到EPCCL理论的编译中以提高编译效率;提出规约规则,并基于该规则,提出能在多项式时间内终止的REDUCE算法对EPCCL理论进行规约;结合KCDP和REDUCE算法,实现了编译器C2E,并在随机问题和国际通用的测试用例上测试了C2E的编译效率和编译质量,实验结果表明,无论从编译效率还是编译质量来说,C2E都是一个高性能的EPCCL编译器.     

知识编译

精确地讲,什么是知识编译?它是否具有多种含义?什么是深层知识和表层知识?几位专家对此及其它问题作了探讨。     

可能性扩展规则的推理和知识编译

在扩展规则的基础上提出了可能性扩展规则。给出了基于可能性扩展规则的可能性逻辑推理方法,利用互补因子的概念来估价推理问题的复杂度。扩展了经典逻辑的蕴含可控制类和可满足可控制类的定义,提出了可能性蕴含可控制类、不一致性程度计算可控制类的概念。在可能性扩展规则的基础上提出了EPPCCCL(each pair of possibilistic clauses contains complementary literals)理论,并证明了该理论是在最优化形式蕴含可控制类和不一致性程度计算可控制类中的,可以作为可能性     

基于MCN和MO启发式策略的扩展规则知识编译方法

在基于扩展规则的知识编译算法的基础上提出了2种启发式策略:MCN策略和MO策略.MCN策略和MO策略利用子句集的信息分别选择相应子句和变量,减少扩展规则的使用次数,进而降低知识编译后目标子句集的规模.在此基础上,设计并实现了MCN_KCER,MO_KCER和MCN_MO_KCER算法.实验结果表明:2种启发式策略都可以大幅度减小编译后的子句集规模,同时使用它们的效果更为明显,经过编译后得到的子句集规模是原算法的1/3～1/39,从而大幅度提高之后的在线推理阶段的效率.     

知识编译研究

知识编译是处理命题逻辑知识库常用的一种新技术,知识编译的过程就是把知识转换成易于推理的表示形式.作为一种有效的推理机制,这种技术已经被广泛地应用到各种各样的人工智能领域中.对目前知识编译的研究与应用进行了综述性的介绍,并且从简洁性、多项式时间内支持的查询操作以及多项式时间内支持的转换操作3个方面对各种知识编译目标语言做了系统的阐述.     

一个简单的知识编译模型

“知识编译”这一术语是指:给出某知识K 和一个知识编译函数 C,将 C 作用于 K 得出编译知识 K';即:C(K)=K'。假设对完成某一信息处理任务 f,K'比 K 有效,即:f 是期望实现的某种功能,而且利用 K'实现 f 的某功能(以 f_k,表示)要优于利用 K 完成 f 的任何功能(以 f_k 表示)。由 f_k 与 f_k 实现的功能也许不同于 f 的功能。例如:f 是诊断某一设备的任务,K 是关于此设备的一个定性物理模型,C 的功能是将 K 转化为诊断知识 K'。换言之:K'比 K 更直接地将观察与故障相联系。只利用 K 得到一个诊断系统的实现过程为 f_k,而利用 K'的诊断系统实现过程为 f_k'。     

SIMD自动向量化编译优化概述

SIMD扩展部件是集成到通用处理器中的加速部件,旨在发掘多媒体程序和科学计算程序的数据级并行.首先介绍SIMD扩展部件的背景和研究现状,然后从发掘方法、数据布局、多平台向量化这3个角度介绍了SIMD自动向量化的研究问题、困难和最新研究成果,最后展望了SIMD编译优化未来的研究方向.     

高速并行RS编译码系统实现系统

给出了一种高速并行RS编译码系统的实现方法,并就其中的几个关键技术进行了分析。采用该技术实现的纠错系统,可以使误码率在10^-3的情况下仍保证数据的高可靠,高速率传输。     

面向多核体系结构的并行迭代编译技术研究

迭代编译技术是一种编译优化技术,目前学术研究已经证明将迭代编译技术运用于程序优化能够显著提高程序性能。但是,因为迭代编译需要多次编译运行程序,整个迭代过程耗时巨大。为了运用当前普遍存在的多核计算资源,加快迭代编译过程,对当前新提出的迭代编译框架OpenTuner进行修改,将迭代编译过程中的评估阶段改为并行执行。同时,探索迭代编译评估阶段并行化对优化效果的影响,并对此做出分析。     

基于LSF集群技术的网格并行编译服务模型

针对目前单机编译环境中编译资源局限、编译作业执行时间过长等问题,通过对网格集群技术的研究,提出了一种基于集群技术的网格并行编译服务模型。该模型中首先对编译作业进行分解,并依据作业调度算法,把分解后的元编译作业分发至集群中的编译服务器进行并行编译。实际应用表明,该模型充分利用了编译服务网格资源,提高了编译效率,具有很高的实用价值。     

Knowledge Compilation Using the Extension Rule

In this paper, we define a new class of tractable theories: EPCCL theories. Using EPCCL theories as a target language, we propose a new method for knowledge compilation. It is different from existing approaches in that both the compilation and the querying are based on the extension rule, a newly introduced inference rule. With our compilation method, arbitrary queries about the compiled knowledge base can be answered in linear time in the size of the compiled knowledge base. For some theories, the compilation can be done very efficiently, and the size of the compiled theory is small. Furthermore, our method suggests a new family of knowledge compilation methods.     

一种基于扩展规则的#SAT 求解系统

#SAT 问题是SAT 问题的扩展,需要计算出给定命题公式集合的模型个数.通过将问题求解沿着归结的反方向进行,并利用容斥原理解决由此带来的空间复杂性问题,提出了一种基于扩展规则的模型计数和加权模型计数问题求解框架,可以看作是目前所有模型计数问题求解方法的一种补方法.证明了该方法的完备性和有效性,设计了基于扩展规则的#SAT 求解系统:JLU-ERWMC.实验结果表明,JLU-ERWMC 在有些问题中优于目前最为高效的#SAT 问题求解系统.     

面向全分布式智能建筑系统应用程序的并行化编译方法

群体智能系统通过邻居个体的信息交互实现群体级别的应用任务,具有良好的鲁棒性和灵活性.与此同时,大多数开发人员难以对分布式、并行的个体交互机制进行描述.一些高级语言允许用户以串行思维方式、从系统全局角度来编程并行的群体智能计算任务,而无需考虑通信协议、数据分布等底层交互细节.但面向用户、全局声明式的群体智能系统应用程序与个体并行执行逻辑存在的巨大语义差距,使得编译过程复杂进而导致应用程序开发效率不高.提出一个编译系统及其支撑工具,支持将高级的群体智能系统应用程序转换为安全、高效的分布式实现.所提编译系统通过并行信息识别,计算划分,交互信息生成技术,将面向系统全局、串行编程的群体智能应用程序编译为面向个体独立执行的并行目标代码,从而使用户不必了解个体间的复杂交互机制.设计一种标准化中间表示,将复杂群体智能计算任务转换为群体智能算子和输入输出变量组合而成的标准化语义模块序列,其以独立于平台的形式表示源程序信息,屏蔽目标硬件平台的异构性.在一个群体智能系统案例平台中部署和测试所提编译系统,结果表明该系统能够有效将群体智能应用程序编译为平台可执行的目标代码并提升应用程序开发效率,其生成的代码在一系列基准测试中具有比现有编译器更好的性能.     

Redundancy checking algorithms based on parallel novel extension rule

Abstract

Redundancy checking (RC) is a key knowledge reduction technology. Extension rule (ER) is a new reasoning method, first presented in 2003 and well received by experts at home and abroad. Novel extension rule (NER) is an improved ER-based reasoning method, presented in 2009. In this paper, we first analyse the characteristics of the extension rule, and then present a simple algorithm for redundancy checking based on extension rule (RCER). In addition, we introduce MIMF, a type of heuristic strategy. Using the aforementioned rule and strategy, we design and implement RCHER algorithm, which relies on MIMF. Next we design and implement an RCNER (redundancy checking based on NER) algorithm based on NER. Parallel computing greatly accelerates the NER algorithm, which has weak dependence among tasks when executed. Considering this, we present PNER (parallel NER) and apply it to redundancy checking and necessity checking. Furthermore, we design and implement the RCPNER (redundancy checking based on PNER) and NCPPNER (necessary clause partition based on PNER) algorithms as well. The experimental results show that MIMF significantly influences the acceleration of algorithm RCER in formulae on a large scale and high redundancy. Comparing PNER with NER and RCPNER with RCNER, the average speedup can reach up to the number of task decompositions when executed. Comparing NCPNER with the RCNER-based algorithm on separating redundant formulae, speedup increases steadily as the scale of the formulae is incrementing. Finally, we describe the challenges that the extension rule will be faced with and suggest possible solutions.     

基于局部搜索的并行扩展规则推理方法

扩展规则推理方法在经典的可满足性问题求解中已得到广泛应用,若干个基于扩展规则的推理方法已被提出,皆得到国内外的认可,例如完备的NER,IMOMH_IER,PPSER算法以及基于局部搜索的不完备算法ERACC等,都具有良好的求解效果.其中,ERACC算法是当前扩展规则求解器中求解效率最高、能力最强的算法.但是,串行的ER...     

A Framework for Method-Specific Knowledge Compilation from Databases

Generality and scale are important but difficult issues in knowledge engineering. At the root of the difficulty lie two challenging issues: how to accumulate huge volumes of knowledge and how to support heterogeneous knowledge and processing. One approach to the first issue is to reuse legacy knowledge systems, integrate knowledge systems with legacy databases, and enable sharing of the databases by multiple knowledge systems. We present an architecture called HIPED for realizing this approach. HIPED converts the second issue above into a new form: how to convert data accessed from a legacy database into a form appropriate to the processing method used in a legacy knowledge system. One approach to this reformed issue is to use method-specific compilation of data into knowledge. We describe an experiment in which a legacy knowledge system called INTERACTIVE KRITIK is integrated with an ORACLE database. The experiment indicates the computational feasibility of method-specific data-to-knowledge compilation.     

基于规范划分集的并行循环计算划分

计算划分问题是并行编译中最为重要的问题之一.针对并行循环,在数据分布确定的情况下,提出了基于规范集的计算划分算法,具体讨论了规范集的获取方法及综合通信与负载均衡的最优方案选取算法.实验表明,在并行循环处理方面,这一算法与以前几种算法相比更加简单、有效;采用这一算法的p_HPF编译器对数据并行应用问题可以获得良好的加速比和效率.该编译器已在石油领域得到应用.