（计算机软件与理论专业论文）clips在基于知识的并行编程环境中的应用研究.pdf

摘要 摘要 专家系统是人工智能领域中一个非常重要的分支，而新型专家系统需 要具有的一类特征便是并行与分布式处理。因此，在基于知识的并行编程 环境下应用专家系统，把专家系统和并行计算相结合，通过这一方式来提 高专家系统的推理速度是一个新的课题。本文对国内外专家系统和并行计 算的研究现状进行了综合分析，就如何把专家系统与并行计算相结合，以 及并行推理的实现进行了研究。 首先，对目前所普遍采用的并行推理体系结构迸行了分析，设计了一 个改进后的并行推理系统架构。还提出了与之相对应的推理算法，同时研 究了规则细粒度划分的问题，并对两种体系结构进行了比较。 其次，分析c l i p s ( cl a n g u a g ei n t e g r a t e dp r o d u c t i o ns y s t e m ) 自身所具 有的特性，研究了目前实现混合编程的主要方法。通过使用c l i p s 的接口 函数，设计出把c l i p s 嵌入到高级编程语言c + + 中的方案，为实现并行推 理做好了准备。 再次，讨论了并行环境下规则库的分解问题，研究了规则库的动态实 时分解、规则库的构架以及规则库的传输，提出了相应的解决方案。通过 分析c l i p s 在高级程序语言和并行函数间的消息传递方式，设计并实现了 c l i p s 在基于知识并行编程环境中进行推理的算法，接着进一步对算法进 行了分析。然后对推理过程中消息的传递和推理过程中需使用的自定义函 数进行了分析设计。 最后，在并行环境中搭建了一个动物识别专家系统，通过对运行数据 的测试，分析了并行推理的效果。 关键词专家系统；c l i p s ；推理；并行；规则库 燕山大学工学硕士学位论文 a b s t r a c t e x p e r ts y s t e mi sa ni m p o r t a n te m b r a n c h m e n to fa r t i f i c a li n t e l l i g e n c e ，a n d o n eo ft h em o s ti m p o r t a n tc h a r a c t e r so ft h en e we x p e r ts y s t e mi sp a r a l l e la n d d i s t r i b u t e dp r o c e s s i n g s oe x p e r ts y s t e mc o m b i n i n gw i t hp a r a l l e lc o m p m ea n d u s i n gi t i nt h ed o m a i no fk n o w l e d g e - b a s e dp a r a l l e lp r o g r a m m i n gb e c o m e sa n e ws u b j e c t ，i tc a r li m p r o v et h ei n f e r e n c es p e e do fe x p e r ts y s t e m t h i sp a p e r a n a l y z e st h ec u r r e n ts i t u a t i o no ft h ed o m e s t i ca n di n t e r n a t i o n a le x p e r ts y s t e m a n dp a r a l l e lc o m p u t e ，a n dr e s e a r c h e sf o rt h ep r o b l e mo fe x p e r ts y s t e mc o m b i n i n g 诵也p a r a l l e lc o m p u t ea sw e l la sp a r a l l e li n f e r e n c e f i r s t l y , as t r u c t u r eo fp a r a l l e li n f e r e n c ew h i c hw a sa d o p t e da tp r e s e n tw a s a n a l y z e d an e ws t r u c t u r eo fp a r a l l e li n f e r e n c ea n da na l g o r i t h mo f t h ei n f e r e n c ew e r ed e s i g n e d a tt h es a m et i m et h eq u e s t i o na b o u tt h er u l ep a r t i t i o no f f i n e g r a i nw a sr e s e a r c h e d a n dt h e nt w ok i n d so f s t r u c t u r ew e r ec o m p a r e d s e c o n d l y ，t h ec h a r a c t e r i s t i co fc l i p s ( cl a n g u a g ei n t e g r a t e dp r o d u c t i o n s y s t e m ) i t s e l fw a sa n a l y z e d ，a n dt h em a i nm e t h o do fh y b r i dp r o g r a m m i n ga t p r e s e mw a sr e s e a r c h e d b yu s i n gt h ei n t e r f a c ef u n c t i o no fc l i p s ，t h ep r o j e c t o fe m b e d i n gc l i p si nt h ea d v a n c e dp r o g r a m m i n gl a n g u a g ec 十+ w a sd e s i g n e d w h i c hm a d e p r e p a r a t i o nf o rp a r a l l e li n f e r e n c e m o r e o v e r , t h er e s o l v i n go fr u l eb a s eu n d e rt h ep a r a l l e le n v i r o n m e n tw a s d i s c u s s e d t h ed y n a m i cr e a l t i m er e s o l v i n go fr u l eb a s e ，t h ef r a m e w o r ko fr u l e b a s e ，a n dt h et r a n s p o r to fr u l eb a s ew e r er e s e a r c h e d a n dt h er e s o l v e n tw a s d e s i g n e d t h ei n f e r e n c ea l g o r i t h mo fu s i n gc l i p si nt h ed o m a i no fk n o w l e - d g e - b a s e dp a r a l l e lp r o g r a m m i n gw a sd e s i g n e d ，a l s oi tw a sm a d ei n t or e a l i t y , b y a n a l y z i n gt h em e s s a g ep a s s i n gm e t h o do fc l i p sb e t w e e na d v a n c e dp r o g r a - m m i n gl a n g u a g ea n dp a r a l l e lf u n c t i o n ，a n di tw a sd e s c r i b e di nd e t a i l t h e p a s s i n go fm e s s a g ea n dt h eu s e rd e f i n ef u n c t i o nw h i c hc a nb eu s e du n d e rt h e i i a b s t t a c t p r o c e s so fi n f e r e n c ew a sa l s or e s e a r c h e d i nt h ee n d ，a na n i m a lr e c o g n i t i o ne x p e r ts y s t e mh a db e e nc o n s t r u c t e di n t h ep a r a l l e le n v i r o n m e n t t h ee f f e c to fp a r a l l e li n f e r e n c ew a sa n a l y z e db y t e s t i n gt h er u n n i n gd a t a k e y w o r d se x p e r ts y s t e m ；c l i p s ；i n f e r e n c e ；p a r a l l e l ；r u l eb a s e l l i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文( ( c l i p s 在基于知识的并 行编程环境中的应用研究，是本人在导师指导下，在燕山大学攻读硕士学 位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部 分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要 贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完 全由本人承担。 作者签字旒 日期：扣彳年? 月2 2 日 燕山大学硕士学位论文使用授权书 c l i p s 在基于知识的并行编程环境中的应用研究系本人在燕山大 学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成 果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关 人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校 保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。 本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以 公布论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密区 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 日期：2 船衫年弓月2 z 日 日期必彳彰j q 2 2 目 锿铷 第1 章绪论 第1 章绪论 1 1专家系统及其发展 自从2 0 世纪5 0 年代人工智能诞生以来，产生许多分支，包括语音、 视觉、机器人、自然语言理解和学习以及专家系统。在众多人工智能研究 领域中，专家系统是最富代表性、最重要的应用分支。 1 1 1 专家系统 专家系统早期先导者之一，斯坦福大学的e d w a r df d g e r t b a u t m 教授把 专家系统定义为“一种智能的计算程序，它运用知识和推理来解决只有专 家才能解决的复杂问题”。 2 0 世纪5 0 年代后期及6 0 年代初，n e w e l l 和s i m o n 编写了著作人类 问题求解，描述了著名的通用问题求解器，其最重要的结果是证明了大部 分的人类问题求解或认知可以用i f t h e n 类型的产生式规则表达。例如， “如果”汽车油表显示为零，“那么”请给汽车加油。n e w e l l 和s i m o n 把 人类问题求解的模型归纳为：长期记忆( 规则) 、短期记t l ( z 作内存) 和认知 处理机( 推理机) ，这三者是现代基于规则的专家系统的基础。 这里所说的规则是指产生式系统【2 引( p r o d u c t i o ns y s t e m ) 。目前，基于 规则的产生式系统是实现专家系统的一种流行方法。而之所以采用这种基 于规则的系统，主要是因为如下的几点原因。 ( 1 ) 模块化特征规则使得知识容易封装并不断扩充。 ( 2 ) 解释机制通过规则容易建立解释机，这是因为一个规则的前件指 明了激活这个规则的条件。通过追踪已触发的规则，解释机可以得到推出 某个结论的推理链。 ( 3 ) 类似人类认知过程基于n e w e l l 和s i m o n 的工作。规则似乎是模 拟人类怎样解决问题的一个自然方法。规则的简单表示方式“i f t h e n ” 燕山大学工学硕士学位论文 使得容易向获取他们知识的专家解释知识的结构。 这些构成产生式系统的规则称为产生式规则。 专家系统主要有以下几部分构成。 ( 1 ) 用户界面用户和专家系统之间的通信机制。 ( 2 ) 解释机解释系统的推理给用户。 ( 3 ) i 作内存被规则所使用的事实的全局数据库 ( 4 ) 推理机通过决定哪些规则满足事实或目标，并授予规则优先级， 然后执行最高优先级规则来进行推理。 ( 5 ) 议程由推理机创建的一个规则优先级表，这些规则匹配工作内存 中的事实或目标。 ( 6 ) 知识获取机为用户建立的一个知识自动输入方法，以代替知识工 程师去编码知识。 专家系统典型的要素包括：知识库( 规则) 、推理机( 议程) 、工作记忆( 事 实) 。推理机部分还包括解释机、知识获取机和用户界面。一个理想的专家 系统结构如图1 1 所示。 用户 图1 - 1 理想专家系统结构 f i g 】- 1i d e a ls t r i c t u r eo f e x e r ts y s t e m 2 第1 章绪论 由于每个专家系统所需要完成的任务和特点不同，其系统结构也不尽 相同，所以，一般只具有图中部分的模块。在表1 一l 中给出了人类专家与 专家系统的比较。 表1 1 人类专家与专家系统的比较 t a b 1 - 1h u a m a ne x p e r tc o m p a r i s o nw i t he x p e r ts y s t e m 因素人类专家专家系统 可用时间工作日 全天候 地理本地任何可行的地方 安全不可取代可取代 易腐烂的是古 性能变动恒定 度变动恒定( 总是快些) 代价高 偿付得起 1 1 2 专家系统的发展历史 人工智能大多数早期的工作性质都是学术性的，其程序都是用来开发 游戏。在1 9 5 7 年诞生了第一个自动定理证明程序，称作逻辑理论家( l o g i c t h e o r i s t ) 。从1 9 6 5 年开始开发的d e n d r a l 程序为以后的研究者指出了一 个正确的研究方向。斯坦福的研究者们在研究过程中意识到智能行为不仅 依赖于推理方法，更依赖于其推理所用的知识。斯坦福的费根鲍姆声称“i n t h e k n o w l e d g el i e s t h e p o w e r ”，由此研究结果产生了基于知识的专家系统。 诊断感染性血液疾病的m y c i n 专家系统使得人们能更好的理解基于 规则专家系统的构建方法。它证明了人工智能可以应用到实际的现实世界 问题，同时还对许多新概念作出了试验，例如解释机、知识的自动获取和 智能指导等等。另外，它还证实了专家系统外壳的可行性。美国数字设备 公司利用计算机配置专家系统x c o n 每年为公司节省几千万美元的开支。 而在2 0 世纪7 0 年代，还建成了另一个同样非常成功的，用于辅助地质学 家探测矿藏的专家系统p r o s p e c t o r ，它也由于在东华盛顿的m o u n t 燕山大学工学硕士学位论文 t o l m a n 成功钻探开采价值超过l 亿美元的钼矿藏而名声大振。 我国从1 9 7 8 年开始设立人工智能的研究课题，主要在定理证明、汉语 自然语言理解、机器人及专家系统方面取得了一定的成果。智能计算机系 统和智能机器人被列入我国高技术的重点发展主题。根据智能计算机系统 的高技术研究开发计划，我国将研制可扩充大规模并行的、智能化的先进 计算机系统，它们主要用于智能化的可视计算、事务处理、信息管理、信 息分析与服务，它们将具有高速和可视化计算的能力，具有以语言、文字、 图形、图像为界面的人机交互能力，具有智能化的软件开发能力。在表1 2 中给出了专家系统在计算机上的应用。 表】一2 计算机专家系统 t a b 1 2e x p e r ts y s t e mo f c o m p u t e r 名称计算机系统名称 计算机系统 p ，r r a n s给出管理d e c 计算机的预测x s i r e 配置d e c 计算机系统销售订单 b d s 诊断交互网中的损坏部分 s ，m v s 监控i b m m v s 操作系统 x c o n 配置d e c 计算机系统1 1 m m 诊断d e c 计算机 x s e l 配置d e c 计算机系统销售订单 1 2 专家系统的发展趋势 专家系统的近期研究目标是建造专家系统用于代替人类进行智能管理 与决策，其远期的研究目标，是要实现具有更新概念、更好技术性能和更 高智力水平的决策与咨询系统，开发出更高级的智能助手。这需要在现有 的基础上建立更新的理论体系和系统框架，实现更好的信息处理技术与相 关科学技术的集成，开发出更成熟的应用方法。 专家系统具有众多的研究方向，这些方向有着雄厚的理论基础和技术 基础以及广泛的应用前景，主要包括改进和创建专家系统新的知识表示方 法；解决知识获取的“瓶颈”问题( 有效地获取专家知识，充分发挥知识库 4 第1 苹绪论 的作用，研究自动知识获取问题) ；采用机器学习方法来提高系统推理能力； 进一步开发实时专家系统；研制功能更强大的系统开发工具；开发各种新 型专家系统；开发专用专家系统电脑；进一步开展多领域专家交叉合作研 究；实现模块化设计；建立专家系统示范工程，扩大专家系统应用领域； 加强对基于w e b 的专家系统的研究应用；建立与w e b 连接的新型关系数 据库和知识库等等。 当今的时代是一个网络的时代，网络技术逐渐普及，网络给人们带来 愈来愈多的便利。基于网络的专家系统已经出现，并呈现出强劲的趋势。 通过网络可以实现异地协同工作、资源共享和远程咨询。不仅使得专家系 统的应用范围更加广泛便捷，还大大提高了专家系统的使用效率与价值。 发展专家系统不仅要采用各种定性模型，而且要运用人工智能和计算 机技术的新思想新技术。 新型的专家系统需要具有的特征应当是，并行与分布式处理【4 7 ；多专 家系统协同工作；高级语言和知识语言描述；具有自学习功能：引入新的 推理机制；具有自动纠错和自我完善的能力：最后，还需要有先进的人机 接口，便于人机之间的交流。 1 3 并行技术 并行处理技术主要是以算法为核心，并行语言为描述，软硬件作为实 现工具的相互联系而又相互制约的一种结构技术。 1 3 1 并行计算技术 到目前为止，并行计算机具有代表性的应用领域有：天气预报建模、 超大规模集成电路的计算机辅助设计、大型数据库管理、人工智能、犯罪 控制和国防战略研究等，而且它的应用范围还在不断地扩大。 分布式并行计算 8 ，9 j 是利用一组由多种不同结构功能组成的、网络互连 的计算机同时解决一个大型综合问题的计算【l o ，u 1 。因为这种计算环境，分 布式并行计算具有计算成本低，计算性能最佳，满足不断增长的计算需求， 燕山大学工学硕士学位论文 开发方便等一系列的优点。作为计算机研究的又一热点，p v m 、e x p r e s s 等就是在这样的背景下于上世纪八十年代末九十年代初出现的分布式并行 计算环境。 1 3 2 并行计算与专家系统相结合 基于各种并行算法，采用各种并行推理和执行技术，在多处理器的硬 件环境中工作，具有分布处理推理工作的功能，这就是并行分布式专家系 统i l ”j 。其主要目的在于把一个专家系统的功能经分解以后分布到多个处 理器上并行工作，在总体上提高系统的处理效率【l “埽】。它可以在紧耦合的 多处理器环境中工作，也可以工作在松耦合的计算机网络环境里【1 9 1 。因此， 其总体结构在很大程度上依赖于其所在的硬件环境。 专家系统的分布处理特征要求专家系统做到功能合理均衡地分布，以 及知识和数据适当地分布，着眼点主要在于提高系统的处理效率和可靠性 等等。并行技术与专家系统相结合，将使专家系统得到崭新的发展。并行 推理技术将对群决策支持系统、智能决策支持系统、大型m i s 系统提供新 的理论方法和技术，可以解决工程领域中存在的大量不确切信息处理问题， 并行推理技术有着很广阔的应用前景。 国外的许多研究机构也开发过许多并行推理系统，如欧洲工业研究中 心实现的p e p s y s 、美国i l l i n o i s 大学实现的r e d u c e o r 等，但是它们都有 着各自的缺陷，如提供显式的语言级谓词标注手段由程序员指明并行目标， 对程序员要求很高：或者只能开发独立与并行而不能开发相关与并行等等， 因此效果都不十分理想。 1 4 本课题的研究内容 本课题的研究内容主要是设计与实现在基于知识的大型并行程序开发 环境领域里使用c l i p s 语言。 从课题研究对象的实际出发，针对存在问题，遵循并行程序设计的基 本思想，利用目前的开发平台，解决存在的问题，设计出系统框架和主要 第1 章绪论 功能模块，对本领域的基础数据、知识规则和模型等部分进行深入研究， 研究如何有效的在基于知识的并行环境中应用c l i p s 。 要实现在并行程序开发环境中使用c l i p s 语言进行专家系统推理，第 一个需要解决的问题是实现在高级程序语言里使用c l i p s 。也就是要有效 的把c l i p s 嵌入到高级程序开发语言里，使得c l i p s 的各种命令函数都能 自如的在高级程序开发语言里面使用。 其次，需要解决将普通的串行程序并行化。也就是要利用一些并行函 数，把嵌入了c l i p s 的程序修改成可以在并行环境下运行的并行程序，进 而实现c l i p s 的并行推理。 这里面最主要要解决的，一个就是在并行环境中c l i p s 、高级编程语 言、并行函数三者之间的消息传递问题，而另一个则是对数据具体分解规 则确定的问题。 1 5 本文的组织结构 本文的结构安排如下。 第1 章介绍课题的研究背景与研究现状；第2 章作为后续内容的铺垫， 简单介绍相关的基础理论；第3 章至第5 章依次介绍了作者课题研究的主 要内容。 第3 章对当前的并行推理体系结构进行分析，设计了一种新型的并行 推理体系架构，通过比较指出了这个新型体系结构的优势。同时还对其中 细粒度划分的问题进行了研究。 第4 章是对并行推理的详细设计。分析了c l i p s 在高级程序语言和并 行函数间的消息传递方式，研究了需要采用的方法，找出了所要用到的接 口函数，设计实现了把c l i p s 嵌入到c + + 中。给出了实现并行推理的算法， 对不同部分地算法进行了研究。分析了规则库进行分解所需要注意的地方， 及要采取的方法。研究了规则库的分解规则、规则库的构架以及规则库的 传输问题。当采取不同深度的规则库，用不同的方法进行规则库的分解， 以及不同推理系统架构之间所存在的差异，都对并行推理产生不同的影响。 燕山太学工学硕士学位论文 第5 章通过一系列实验验证了并行推理算法的可行性和正确性。比较 了所得各种试验的数据。对这些实验数据进行了深入的分析，通过对实验 数据的研究，表明了并行推理的优势所在。 最后结论部分总结了全文内容，并对未来研究工作进行展望，提出了 在基于知识的大型并行程序开发环境领域里使用c l i p s 语言所存在的一些 不足，以及需要进一步研究和验证的内容。 第2 章相关知识 第2 章相关知识 大型并行性被期待为当今和未来科学应用所需要的计算能力提供下一 次实质性的提高。尽管存在多种可以提供大型并行性的硬件平台，可是一 个使得分布式存储结构程序设计能像单一地址空间系统程序设计一样简单 的合适的程序设计体系环境依然是非常缺少的。并行硬件程序设计师通常 都在面对着常规体系结构中尚未发现的部分，如数据分解，数据和载入分 配，数据通信，进程协调，改变数据存取延迟，以及处理机拓扑学。以前 曾经使用过简化并行程序设计的方法，特别是对于共享存储结构，是对转 换和编译时间进行并行化 2 0 - 2 3 】。然而，这种代码层的并行化对于分布式结 构是极其困难的 2 4 , 2 5 。并且，只有程序并行执行机会中有限的细粒度的部 分可能被检测到，而结果则依赖于程序设计者的编程风格。至于概念上的 检测，在自然科学和工程学的许多应用中被发现的粗粒度并行性对于目前 的并行化技术而言通常都太复杂了。 2 1 并行程序开发环境 一个设计合理的程序开发体系环境是在分布式存储大型并行计算机系 统中进行程序设计的有利工具 2 6 - 2 8 。 理所有由并行硬件所引起的复杂性。 它的主要目的是以用户透明的方法处 为打破当前代码并行化的限制，在早 期的程序发展阶段，以及在规范和设计阶段，可以把并行程序开发同基于 知识的技术相联系，把并行程序开发同用户支持的出发点相联系【2 1 1 。 在设计合理的程序开发体系环境中编程的基本步骤是：使用一种高级 的特定域的形式进行问题规范说明；以交互的方式改进并完成问题规范； 产生对用户透明的程序代码编译 3 2 3 4 。 在一个典型的活动期间，程序员在考虑使用程序辅助接口的情况下给 出程序的初始规范说明。初始问题规范被分解为纯粹的计算特征以及与并 燕山大学工学硕士学位论文 行结构有关的特征。前者被直接传递给程序合成器p s ，后者则传递给程序 设计助手p a 。然后，通过与用户交互的方式，p a 抽取并完成需要确定一 个合适并行框架的信息。p a 是基于a i 重要组成部分的中心，它依赖于各 种不同类型的专家知识。程序合成器则把并行框架扩展到编译、特定硬件、 并行c + + 或者c 程序。依照程序编程过程的三步骤方式，程序开发体系环 境由图2 ，1 所示的三个功能模块组成。 程序设计助手p a 图2 - 1程序开发环境的概念结构 f i g 2 - 1c o n c e p ts m l c n l r eo f p r o g r a md e v e l o p m e n te n v i r o n m e n t 2 2 并行程序设计 对计算系统超过当前可能提供的计算速度的需求总是在不断增长。提 高计算速度的一种方法是用多处理器协同求解一个问题。这种方法中，整 个求解问题被分成若干部分，然后每个部分各由一个处理器并行地计算。 编写这种形式的程序被称为并行编程。计算平台，即一台并行计算机，可 以是专门设计的、含有多个处理器的计算机或是以某种方式互连的若干台 1 0 第2 章相关知识 独立的计算机。一个理想的情况则是，q 台计算机应能提供n 倍的单机运 算速度，不论当前计算机的速度为多少，对于可以期待求解的问题将以1 m 时间完成。1 9 9 3 年由世界各大计算机厂家、应用部门和研究部门共同制定 的高性能f o r t r a n ( h p f ) 语言，象征着并行程序设计语言及其编译的最高水 平，但其仍需由程序员作数据划分。因此，并行化编译仍然是一个等待解 决的严重问题。华中理工大学计算机系，于1 9 9 0 年研制成功了全自动并行 化编译系统h z p a r a ，并正在实现h z p a r a i i ，该研究结果提出的理论方 法是建立在分配相关的理论基础上的，即对迭代空间进行等价分类从而同 时完成数据划分与计算划分。 2 2 1并行计算机的体系结构 并行计算机的体系结构可从不同角度分为，向量机和非向量机；共享 主存并行机和分布式主存并行机；同构并行机和异构并行机；紧耦合系统 和松耦合系统。并行算法则可分为，数值并行算法和非数值并行算法；同 步并行算法和异步并行算法 3 5 - 3 8 。 并行程序设计的模式和技术口9 垅1 也可以分为数据并行以及控制并行 模式；s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 模式和m i m d ( m u l t i p l ei n s t r u c t i o nm u l t i p l ed a t a ) 模式：向量、共享变量、消息传递、面向对象以及函数 和逻辑并行程序设计技术 4 3 - - 4 5 。目前，绝大多数并行计算机的体系结构都 属于多指令流多数据流计算机，即m i m d 计算机。其中，每个处理单元都 是根据不同的控制流程来执行不同的操作、处理不同的数据集合。 下面介绍一些有关程序并行执行的基本概念 4 6 】。 ( 1 ) 任务分布将一个程序划分成若干个可以全部或部分并行执行的 部分。任务划分可以根据控制流进行，也可根据数据流进行。划分任务要 力求并行性最大，任务间的相关性最小，任务的粒度适中。 ( 2 ) 数据分布这是分布式主存并行系统特有的问题，即如何把一个程 序要处理的数据分散存放在系统中各处理机的存储器中。 ( 3 ) 任务调度将各个任务分配到不同的处理机上去执行称之为调度。 在分布式主存系统上，任务调度要和数据分布对准，即把任务分配到它需 燕山大学工学硕士学位论文 要的数据所在的处理机上去执行，以减少机间通讯。 ( 4 1 任务同步同步是协调各并行任务运行的一种方法，它保证互相作 用的各任务所要求的条件得到满足。同步点是相互作用的任务协调各自运 行状态的地方，除事件外，常用的同步方式还有锁、障碍等。 ( 5 ) 任务通讯一个任务将一批数据传送给另一个任务称为通讯。为保 证正确性，通讯必须在同步点进行。 下面介绍一些有关并行程序性能的概念。 4 7 ( 1 1 粒度粒度是一个任务的工作量或执行时间。通常称循环一级的并 行为小粒度的并行，子程序一级的并行为大粒度的并行。若一个系统的任 务调度开销大，则要求大粒度的并行性，反之即可开发小粒度的并行性， 但粒度大不易实现负载平衡，反之则利于负载平衡。 ( 2 ) 负载平衡一个并行程序执行的总时间取决于最后一个完成的任 务。负载平衡就是使各个任务所需时间大致相等，或者说使各个处理机的 工作量大致相等。 ( 3 ) 并行开销并行开销是为了组织一个程序并行执行，由程序员或者 系统引入的开销。开销主要由任务创建、调度和同步通讯引起。 ( 4 ) 确定性若一个程序每次运行时其语句执行次序都不变，则称它是 确定的。在并行程序中要加上适当的同步通讯来保证这些语句的执行次序 正确，也就是去消除影响正确性的不确定性。并行性并不太难，加上适当 的同步通讯以保证正确性才是并行程序编程和调试的难点。 ( 5 ) 加速比并行化是一种优化技术，用来缩短程序运行的墙钟时间， 也称消逝时间。设一个程序串行执行的墙钟时间为r ，并行执行的墙钟时 间为一，则该程序并行执行的加速比为： s p = t 5 l t p ( 6 ) 可伸缩性一个并行程序是可伸缩的，如果随着计算问题的增大和 处理机数目的增多，它能够获得线性增长的加速比。可伸缩性是衡量一个 并行程序优劣的重要指标之一。 一个程序的并行执行以及这个程序在并行执行过程中的性能，都需要 通过这些概念去解决衡量。特别是其中的加速比，是一个很有效衡量并行 第2 章相关知识 程序执行效率数据。 2 2 2 并行计算机的类型 并行计算机可能的内部布置主要有共享存储器多处理机系统，消息传 递多计算机系统，分布式共享存储器系统等等。在并行推理中主要采用的 正是消息传递多计算机系统，其模型如图2 2 所示。 消息 图2 - 2 消息传递多处理机模型 f i g 2 - 2m e s s a g ep a s s i n gm u l t i p r o c e s s o rm o d e l 消息传递即各个并行执行的部分之间，通过传递消息来交换信息、协 调步伐、控制执行。消息传递模型一方面为编程者提供了灵活性，另一方 面，它也将各个并行执行部分之间复杂的信息交换和协调、控制的任务交 给了编程者，目前大量的并行程序设计仍然是消息传递并行编程模式。 消息传递多计算机系统中每台计算机由一个处理器和本地主存储器组 成，其他处理器不可访问该本地的主存储器。在多计算机系统中主存储器 分布在各台计算机中，每台计算机都有自己的地址空间，每个处理器只能 访问自己的本地主存储器中的单元。系统中的互连网络是供处理器间传递 消息用的，这些消息可能含有其他处理器进行计算时所需的数据。消息传 递多计算机中的消息由程序指明将数据从一个处理器传递给另一个处理 器。对消息传递多计算机系统进行编程仍涉及到将问题分解为各个部分， 以使每个部分能同时执行以完成求解。也可使用并行或扩展的顺序语言进 行编程，但一个更通用的方法是使用消息传递库例程，这些库例程与通常 的顺序程序相连接以进行消息传递。 燕山大学工学硕士学位论文 2 3分布式专家系统及并行分布式系统结构 目前所讨论的专家系统并行推理主要是在并行分布式环境下进行的。 分布式专家系统【4 7 ( d i s t r i b u t e de x p e r ts y s t e m ) 是指逻辑上统一而物理上分 布在不同的物理节点上的若干专家系统，是人工智能领域中分布式人工智 能的一个部分。分布式节点上的每个节点上的专家系统与单个的专家系统 不同，它不仅应具有求解特定问题的能力，而且还具有以下性能。 ( 1 ) 每一个节点专家系统仅有有限知识，包括领域有限知识、群体任务 规划调度的有限知识、预测其它节点专家系统能力的有限知识等。 ( 2 ) 要有分解复杂问题为若干子问题，并根据逻辑关系进行优先顺序排 队的能力。 ( 3 ) 要有选择合适的专家系统求解子问题的能力。 ( 4 ) 要有与其它节点专家系统合作与通信的能力。 并行分布式系统结构主要有两种。 一种是m a s t e r - s l a v em o d e l ( 1 v l s m ) t 4 ”，也就是现在主要使用的主一从 模式，由一台独立的主机控制多台从机进行并行运算。 另一种是f a m e r - w o r k e rm o d e l ( f w m ) 1 4 7 1 ，由一个独立的f a m e r 控制多 个w o r k e r 进行并行运算。前者的消息传递主要依靠从机与从机之间进行， 而后者则是f a m e r 与w o r k e r 之间进行数据传递，任何一个单独的w o r k e r 都不依赖于其他w o r k e r 所修改的数据。 2 4 专家系统编程工具c l i p s 基于规则的c l i p s 编程语言的推理和表示能力与o p s 5 很相似，但功 能则更强大。 2 4 1 编程工具c l i p s c l i p s ( cl a n g u a g ei n t e g r a t e dp r o d u c t i o ns y s t e m ) 是美国航空航天局约 翰逊太空中心州a s a j o h n s o ns p a c ec e n t e r ) 于1 9 8 5 年用c 语言设计的一种 1 4 第2 章相关知识 通用专家系统编程工具【4 8 删j 。 在语法方面，c l i p s 规则与a r t 、a r t - i m 、e c l i p s 和c o g n a t e 语言的 规则极为相似。c l i p s 仅支持正向链规则，而不支持反向链规则。 1 9 8 3 年推出的c l i p s 4 3 版是一个基于规则的通用专家系统开发工具， 具有通用性强、适用性好、运行速度快、便于和已有软件集成等特点。该 版本知识表示仅为事实和产生式规则，具有一定的局限性。1 9 9 1 年底n a s a 推出了c l i p s 5 1 版本，该版本较过去有了很大的改进，它除保留了原来的 产生式程序设计方式外，又增加了两种新的程序设计方式：过程式设计和 面向对象程序设计技术。最新版本是c l i p s 6 2 3 ，属第二代专家系统工具。 从编程语言的角度说，c l i p s 是一种多范例编程语言，它支持基于规 则、面向对象和面向过程的编程。c l i p s 中面向过程的编程语言特征类似 于c 和p a s c a l 以及a d a 语言，语法上类似于l i s p 。 c l i p s 具有以下的基本组成。 ( 1 ) 事实列表( f a c tl i s t ) ，包含了推理过程需要的各种数据。 ( 2 ) 知识库( k n o w l e d g eb a s e ) ，包含了所有的规则。 ( 3 ) 推理机( i n f e r e n c ee n g i n e ) ，对运行做整体的控制。 c l i p s 自6 1 和6 2 版以来，其源代码开始能够与c + + 兼容，这使得 其不但能在a n s ic 中编译，也可在v c + + 和c + + b u i l d e r 等这类c + + 编译 器里面进行编译。 因此c l i p s 具有很好的可移植性，很容易实现与其他语言的接口。 c l i p s 平台的基本结构包括事实库、推理机、规则库和待议事件表。 2 4 2 面向对象语言c o o l 在c l i p s 中的面向对象程序设计，是通过其中的c o o l 5 卜h 1 语言来实 现的，c o o l 的全称是c l i p so b j e c t o r i e n t e dl a n g u a g e 。从语言结构上看， 它由结构定义、函数描述、命令和实例集知识库查询操作函数四大部分构 成。c o o l 可以说是许多o o p 系统的综合产物，具有多种特性。例如其封 装的概念就类似于s m a l l t a l k ，而其中多重继承的特性，则是来自于 c l o s ( c o m m o nl i s po b j e c ts y s t e m ) ，而它对信息处理方法的设计则来源于 燕山大学工学硕士学位论文 c l o s 、s m a l l t a l k 和其它一些o o p 系统。 2 5c l i p s 与高级语言相结合 c l i p s 的操作命令是命令行式的，不适于与用户进行良好的交互。但 由于c l i p s 能与c 、c + + 、a d a 、p a s c a l 等语言兼容，所以可将c l i p s 作 为一个子程序嵌入到其他编程工具中，用其他编程工具来构建与用户交互 的可视化w i n d o w s 界面，而用c l i p s 来构建专家系统的核心部分：推理 机和知识库。 2 5 1c l i p s 的基本组成 c l i p s t 5 5 。7 1 的核心由事实库( 工作存储器) 、规则库、推理机三大部分 组成，采用产生式规则作为基本的知识表示方式。 事实由关系名( r e l a t i o nf l a l l l e ，一个符号字段) 、后跟零个或者多个槽 ( s l o t ，也是符号字段) 以及它们的相关值组成，用来表示已知的数据或信息。 整个事实以及每个槽由一对左右括号限定。可以用自定义模板和自定义事 实结构来定义事实。形式如下： ( d e f t e m p l a t e + 、 ( d e f f a c t s + ) 当c l i p s 系统启动推理时，会把所有用d e f f a c t s 定义的事实自动添加 到工作存储器中，并提供下面的一系列命令：a s s e r t 把事实添加到事实库( 工 作存储器) 中；r e t r a c t 删除指定的事实；m o d i f y 修改自定义模板事实的槽值； d u p l i c a t e 复制事实；c l e a r 删除所有事实。 规则用来表示系统推理的有关知识。c l i p s 中的规则可用d e f r u l e 命令 来定义，其格式如下： ( d e f r u l e ) + ；l e f t h a n ds i d e ( l h s ) o f t h er u l e j + ；m g h t - h a n ds i d e ( r h s ) o f t h er u l e 1 6 第2 章相关知识 常用命令：r e s e t 命令会删除事实列表中的所有事实，然后根据现有的 自定义事实语句声明事实；f a c t s 显示事实列表中的事实；a g e n d a 列出指定 模块议程中的活动；w a t c h 监视命令，可多次使用来监视c l i p s 执行的多 个特征；r u n 启动c l i p s 运行等等。 模式( p a t t e r n ) 的一般格式与事实类似，可以包含变量( ? 变量名) 、i 0 函 数( r e a d 等) 、谓词函数( a n d 、e q 等) a n 表达式。 动作( a c t i o n ) ，主要用来添加或者删除工作存储器中的事实，以及控制 运行过程。 c l i p s 推理机不断地扫描规则的模式，并把和事实匹配的规则激活， 放入议程中。议程实际上是一个堆栈，所有激活的规则被按优先级别定义 的次序压入堆栈。若新压入规则的优先级小于栈顶规则的优先级，则它被 压入到栈的下部，直到所有比它优先级高的规则都在此规则的上面。 c l i p s 提供2 种具体的技术来控制规则的执行：优先级( s a l i e n c e ) 和模 块( m o d u l e ) 。可以在定义规则时设置规则的优先级，使议程中的多条规则 按优先级大小顺序执行。对大型的具有复杂规则库的情况，可以定义不同 的模块来划分知识库，通过改变模块的焦点来控制当前被执行的模块。 2 5 2 专家系统的开发语言 目前比较流行的专家系统开发语言主要有以下几种工具。 程序设计语言，包括通用程序设计语言( 如c c 十+ 、p a s c a l ) 和人工智能 语言f 如p r o l o g 和l i s p ) 两种。 专家系统外壳，它是由一些已经成熟的具体专家系统通过抽取其中的 具体知识，而保留它的体系结构和功能演变过来的。利用它可以快速产生 一个专家系统。主要缺点是在于它的灵活性