逻辑推理机及其并行性的开发

逻辑推理机的研制是第五代计算机发展的主要方向之一.其目标是设计高性能的并行逻辑推理机.本文介绍了这一崭新的非冯·诺依曼型计算机系统的主要特点.以PSI机为例讨论了串行推理机的结构,并对逻辑推理机中固有的"与"并行性、"或"并行性、"合一"并行性、"流"并行性及搜索并行性进行了分析,通过DADO PROLOG机器、Conery-Kibler PROLOG并行解释程序、并发PROLOG和PARLOG语言的典型实例分析了如何从逻辑程序设计语言、逻辑推理机体系结构及机器硬件实现三个层次来开发上述并行性.     

第五代计算机核心语言的发展

日本第五代计算机将逻辑程序设计语言作为系统的核心语言(KL).核心语言有两层意思,一是作为顺序推理机或并行推理机的机器语言,二是作为系统编程或应用编程的的核心(基础).选择逻辑程序设计语言的主要原因是这类语言具有一些特有的优点(例如低过程性,非确定性/并行性,符号     

并行PROLOG语言与并行PROLOG机器

一、引言举世瞩目的日本第五代计算机(以下简称5G)工程的第一阶段业已结束,其主要结果是:直接用微程序解释执行核心语言第0版KL0(一种顺序PROLOG)的个人顺序推理机PSI和在PSI上用系统程序语言ESP(一种扩展PROLOG)实现的操作系统和编程系统SIMPOS(PSI+SIMPOS=顺序推理机SIM),以及一种作为知识库机基础的关系数据库机Delta。这一阶段的工作主要是为了建立后期研究的测试台和硬软环境。 5G工程第二阶段(现阶段)的核心工作是研制并行推理的多处理机体系结构,     

并行推理机设计的主要论题

基于谓词逻辑的逻辑程序设计语言将逻辑推理对应计算,它丰富的表达能力特别适合于知识信息处理。Warren提出的编译技术大大提高了顺序执行Prolog的时空效率。但是,为了满足知识信息处理应用的要求,需要研究并行推理机以并行执行逻辑程序。本文论述了并行推理机设计中涉及到的一些问题,从逻辑语言,执行模型和体系结构等方面探讨了并行推理机中并行性开发方法和需考虑的问题。     

基于Horn子句逻辑的并行推理机

顺序推理中遵循先左后右——子句在前者先选择(即由上到下)的原则,而人们发现 Horn 子句逻辑具有下列基本的并行性:1)AND 并行性,即并行计算规则,指一个目标中的各个子句可并行约化;2)OR 并行性,即并行搜索规则,指一个子目标可同时与多个可能匹配的子句进行匹配;3)搜索并行性,指同时搜索库中所有子句;4)合一并行性,指同时匹配单一目标中的各个项;5)流并行性,指具有共享变量的子目     

PROLOG并行处理技术

我们把用多处理机系统来并行解释(传统顺序)PROLOG程序称做 PROLOG并行处理。本文讨论PROLOG并行处理的有关问题,如PROLOG并行处理的背景,PROLOG解释的并行模型及相应的处理方式(包括子句分布,并行解释控制策略,处理机/进程的分配/调度,PROLOG过程语义维护,通讯复杂性控制,以及支撑多处理机体系结构等)。最后介绍我们提出并准备实现的PROLOG的A并行处理方式,这一种包纳了多种并行模式的逆向递归式断言并行解释方式。     

PROLOG并行解释系统中AND/OR并行成份选择策略

作者认为变量共享以及 ADDCL、DELCL和KILL等数据库操作内部谓词的副作用是影响顺序 PROLOG并行解释的并行度的主要因素。寻求一种识别、选择AND/OR并行成份的有效算法,获得PROLOG子句和子目标的最大可并行计算类,是PROLOG 并行解释的重要步骤。本文对这一问题进行详细讨论,得出了若干实用的结论。     

逻辑程序设计语言的并行性分析

逻辑程序设计语言的并行性是研究和开发并行推理机的重要内容之一。本文介绍了逻辑型语言的一般概念和特点,比较和分析了被 ICOT 确定为五代机核心语言的 Prolog、CP、GHC以及东京大学新提出的语言方案 SPL 的并行性。最后强调了并行基本处理单位的粒度与计算模型、体系结构的关系。     

基于可重构处理器的并行优化算法

为挖掘可重构处理器的内在并行性,需要编译器通过分析程序的并行性来决定可重构处理器硬件最好的执行模式。为此,提出一种基于可重构处理器的并行优化算法。将有向无环图的并行计算部分映射到可重构处理器上,对任务实现3个不同层次的并行性(指令级并行、循环级并行、线程级并行)。测试结果表明,该算法使得可重构处理器在处理任务时比未用并行优化算法的性能提升1.2倍左右。     

数据流计算机结构性能的初步分析

引言第五代计算机的主要目标之一是实现知识信息处理系统(KIPS)。KIPS主要包括推理机和知识库系统。进行高速推理操作需要高度并行的执行机构,数据流机器能有效地实现并行操作和推理功能。传统的冯·诺依曼计算机是单指令流、单数据流结构,它的一个最重要的概念是指令流。由指令流来控制整个机器的运行,在传统的计算机结构中,并行的概念受到限制,只能是一个处理机上不同进程的切换,或由程序员将程序分解成并行的指令或数据流,由各个处理机处理。为了提高计算能力,增强计算并行性,有各种多处理机的结构,但编制程序时,必须适合这些计算机的特殊结构,如对多机系统,程序员必须将任务划分成多个进程使其在多个处理机上执     

网络处理器同步问题的编译优化方法

网络处理器具有并行体系结构,而其高级语言往往具有串行语义。对串行程序进行并行化编译要求引入同步,而同步的优劣又影响生成代码的执行效率。针对网络处理器上的程序,提出一个对同步进行优化的程序划分算法以增加程序的并行性。实验数据表明,在一些有代表性的网络应用上,该算法可提高程序的并行性,并提升性能。     

基于编译的逻辑程序的“与”并行

本文描述了采用静态数据分析实现逻辑程序“与”并行的方法。通过编译将逻辑程序的子句转换成执行图表达式。执行时,只需简单的测试即可进行“与”并行求解。该方法有时得不到最佳“与”并行。     

基于区域平均执行时间和数据依赖信息的可能并行区域识别

随着多核处理器逐渐成为处理器发展的新趋势,为了持续提高程序性能,必须并行执行应用程序.传统的自动并行技术能够很好地并行科学计算应用中的规则循环,但对于含有大量函数调用和指针引用的不规则程序,目前还不能有效地对其实施并行.针对这一现状,文中提出了基于区域平均执行时间和数据依赖信息的可能并行区域识别方法来对一些不规则程序实施高效并行,主要贡献如下:(1)自动识别程序中的多种并行性,不仅包括传统并行性分析中的循环迭代间的细粒度并行性,而且也包括传统并行性分析尚不能有效处理的循环体和函数调用点间的粗粒度并行性.对于程序中蕴含的众多并行性,文中基于区域平均执行时间实施收益分析来选择合适的并行区域实施并行;(2)自动识别可能并行区域间数据依赖关系的数量、类型以及导致数据依赖关系的程序变量.基于文中的分析结果,作者使用面向行为的投机并行系统(behavior oriented parallelism)对SPEC2006中的4个测试用例实现了并行化.并行化后的程序在Intel和AMD多核处理器上分别得到了300%和260%的平均性能加速.     

并发函数式语言CM的设计及实现

使用函数式语言书写的程序包含了稳式的并行性。由于表达式可以以任意次序计值，因此无需显式的并行结构来管理并行性，且可以非常方便地在并行计算机体系结构上实现，程序正确性的证明也相对简单。但一般说来在函数式语言并行实现过程中所开发的是细颗粒度的并行性，它的管理开销较大。本文在纯函数式语言Ｍｉｒａｎｄａ中引入两个并行进程构造子，它们的使用使得在粗颗粒度上管理并发进程的产生、执行、通讯、同步成为可能，从而提高了程序的执行效率。     

并行性挖掘的图文法方法

并行性分析技术一般通过对程序的控制与数据流图或相关依赖图的分析来实现,因而需要从程序中抽取出相应依赖图的算法的支持.本文基于上下文相关图文法RGG形式框架,定义了一种任务级的并行编程图语言GPPL来直接描述顺序或并行程序的控制与数据流图,而且设计了相应的并行性分析算法以挖掘GPPL图程序的并行性特征.GPPL图语言可视为并行程序设计与程序代码生成之间的协同语言,从而使并行性挖掘避免了从程序中抽取出相应依赖图的过程.与已有的描述顺序或并行程序的图语言及其分析算法相比,GPPL图程序形式更为简洁和直观,易于设计,描述能力也更强;基于GPPL图的并行性分析算法的分析能力更强,而且具有可扩展性.     

PROLOG的一种并行解释方式及其实现

文中我们概略地描述了PROLOG的A-并行解释思想。本文主要描述PROLOG的A-并行解释方式的实现及有关的模拟和分析结果。我们首先概述PROLOG 的A-并行解释思想,然后给出A-并行的系统结构和解释模型,以及子句分布和分布式解释器的实现和模拟,最后分析和讨论有关的功能和性能问题。     

并行推理机编译技术的研究

自动模式识别,数据相关性分析、AND并行性的开发、副作用处理、并行性的粒度分析、并发语言的处理和WAM指令集的扩充是并行推理机编译中所面临的一些课题。本文对这些课题及我们所做的工作逐一作了论述,并展示了并行推理机编译技术研究的前景。     

GKD-PROLOG/VAX 780 V1.0系统

<正> 一、概述 PROLOG语言是一种准逻辑型语言。它能以接近自然语言的形式。告诉计算机做什幺,而不必象传统的程序设计语言那样告诉计算机怎么做。这种“智能型”语言诞生以来。特别是日本以PROLOG为基础研制第五代计算机的计划宣布以后,PROLOG已经引起计算机界的广泛重视。PROLOG在小型关系数据库,数字逻辑,自然语言的理解,结构设计,CAD,符号方程求解,专家系统,定理证明等许多领域均获得了应用。GKD-PROLOG/VAX780V1.0解释系统的研制,对改进软件设计环境,人工智能和第五代计算机的研究具有重要的理论和实践意义。     

对推理机体系结构的研究及层次型包驱动结构HPDM的设计

本文对推理机的结构进行了全面的探讨,并指出了并行模型及核心语言对体系结构所施加的影响。文中作者给出了一个基于包驱动执行机制的推理机概念性的方案HPDM,该方案的硬件构成是层次型网状多处理机系统,本文最后对该结构进行了性能评价。     

程序的结构

一个程序由下列几部份组成:程序员写的“具体程序”,由系统提供的标准序部,标准尾部,程序库序部和程序库尾部。从语法角度看,程序是一个“闭子句”,即用括号括起来的“顺序子句”。 我们首先讨论“区域”,这基本上就是作为ALGOL60中分程序概念的推广的顺序子句;其次我们讨论顺序短语和并行短语,把它们看作是由初等动作组成的复合动作。应当说明,一个子句是ALGOL60意义上的一条指令或一个表达式,而一个短语则是一个子句或一个说明。 2.1.分程序和范围的结构 区域和ALGOL60分程序一样,它决定了界限,一个标识符(在ALGOL68中还包括: