（计算机软件与理论专业论文）二叉树旋转和dfa化简并行算法的研究.pdf

，f、摘要l u ii l ii i l ii i i iu iiilly 17 3 4 6 7 8由于计算机硬件的元器件、集成度、工艺和体系结构的发展几乎到了极限，因此，并行处理技术成为提高计算机性能的重要手段。并行程序设计和并行编译技术是并行处理技术的关键，所以并行数据结构、并行编译和优化技术成为计算机科学与理论研究领域重要研究课题之一。基于矩阵模型表示的d f a 的极小化和二叉树旋转转换算法是编译系统和数据结构中的关键技术。本课题主要研究基于矩阵模型表示的d f a 的并行化简和二叉树旋转转换算法的并行处理。这些工作对并行计算理论、并行数据结构算法设计研究有一定的理论和实践意义。本文首先叙述了与本课题研究有关的基础理论以及相关并行模型和并行数据结构；重点做了两方面的研究：其一，对p r a m 模型下二叉树旋转转换算法进行较为深入的研究、提出了一种p r a m 模型下二叉树旋转转换算法的并行处理方法。其基本思想是：引入层次矩阵，通过对二叉树和层次矩阵的等价转换，把对二叉树的操作转换成对层次矩阵的操作；由于对矩阵的并行处理技术已经非常成熟，所以借助矩阵这个“桥梁 ，最终实现对二叉树转换的并行处理。其次，对基于矩阵模型表示的d f a 化简、并行处理等问题进行了研究，提出了一种基于矩阵模型表示的d f a 的并行化简方法。该方法主要是借助于并行算法中的行列划分矩阵乘法理论，来实现d f a 的极小化算法的并行化处理。最后，总结全文，并展望了并行数据结构和并行计算的研究前景和方向。关键词：二叉树，层次矩阵，有限自动机，数据结构-a b s t r a c ta st h ec o m p u t e rh a r d w a r ec o m p o n e n t s ，i n t e g r a t i o n ，t e c h n o l o g ya n da r c h i t e c t u r eh a v en o tm u c hr o o mf o rd e v e l o p m e n t ，p a r a l l e lp r o c e s s i n gt e c h n o l o g yh a sb e c o m ea l li m p o r t a n tm e a n st oi m p r o v ec o m p u t e rp e r f o r m a n c e p a r a l l e lt e c h n o l o g yi si m p o r t a n tt oi m p r o v et h ea c t u a ls p e e d t h u s ，p a r a l l e lp r o g r a m m i n ga n dp a r a l l e lc o m p i l e rt e c h n o l o g yh a v eb e c o m et h ei m p o r t a n tr e s e a r c hi s s u e si nc o m p u t e rs o f t w a r e t h em a t r i xm o d e lr e p r e s e n t a t i o no ft h ed f am i n i m i z a t i o na n db i n a r yr o t a t i n ga l g o r i t h ma r er e s p e c t i v e l yt h ek e yt e c h n o l o g i e si nc o m p i l a t i o ns y s t e m ，d a t as t r u c t u r e t h i sr e s e a r c hp r o j e c tm a i n l yf o c u s e so nt h ep a r a l l e lr e d u c t i o no fd f ab a s eo nt h em a t r i xm o d e la n dp a r a l l e lp r o c e s s i n go fb i n a r yr o t a t i o n t h e s ew o r k sh a v es o m et h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c eo nt h et h e o r yo fp a r a l l e lc o m p u t i n ga n dp a r a l l e la l g o r i t h md e s i g no f d a t as t r u c t u r e t h i sp a p e rf i r s t l yd e s c r i b e ss o m eb a s i ct h e o r i e s ，m o d e l sa n dp a r a l l e ld a t as t r u c t u r e sr e l a t e dt ot h i sr e s e a r c h ，w h i c hf o c u so nt h ef o l l o w i n gr e s e a r c ha s p e c t s ：f i r s t ，i tm a i n l ys t u d yp r o b l e mo nb i n a r yr o t a t i n ga l g o r i t h ma n dp r e s e n t saw a yo fb i n a r yo fp a r a l l e lr o t a t i n ga l g o r i t h m t h eb a s i ci d e ao ft h ea l g o r i t h m ：i n t r o d u c t i o no fh i e r a r c h i c a lm a t r i c e s ，t h eb i n a r yt r e ei sc o n v e r t e dt oe q u i v a l e n tl e v e l so fm a t r i xa n do p e r a t i o n so nb i n a r yt r e ea r ea l s ot r a n s f o r mt oe q u i v a l e n to p e r a t i o n so nl e v e l so fm a t r i x b e c a u s ep a r a l l e lp r o c e s s i n gt e c h n o l o g yo nt h em a t r i xi sv e r ym a t u r e ，i ts u c c e s s f u l l yf i n i s h e db i n a r yo fp a r a l l e lr o t a t i n ga l g o r i t h mo nt h eb r i d g e - - m a t r i x s e c o n d , i tm a i n l ys t u d yp r o b l e m0 1 1t h em a t r i xm o d e lr e p r e s e n t a t i o no ft h ed f am i n i m i z a t i o na n dp r e s e n t saw a yo ft h em a t r i xm o d e lr e p r e s e n t a t i o no ft h ed f ap a r a l l e lm i n i m i z a t i o n t h eb a s i ci d e ao ft h ea l g o r i t h m ：s t u d yt h ep r o b l e mo nt h em a t r i xm o d e lr e p r e s e n t a t i o no ft h ed f am i n i m i z a t i o n ，w i t ht h eb r i d g e t h e o r yo nr a n k sd i v i s i o no fm a t r i xm u l t i p l i c a t i o ni np a r a l l e la l g o r i t h m sa n df i n i s ht h em a t r i xm o d e lr e p r e s e n t a t i o no ft h ed f ap a r a l l e lm i n i m i z a t i o nf i n a l l y ,s u m m a r i z e dt h ef u l l t e x t ，a n do u t l o o k e dt h ef u t u r ea n dd i r e c t i o no ft h ep a r a l l e lt e c h n o l o g y k e yw o r d s ：b i n a r yt r e e ，l e v e l so fm a t r i x ，f i n i t ea u t o m a t a ，d a t as t r u c t u r ei i i目录摘要 l i 墨s t r a c t 目录一第一章前言1 1 课题背景与发展现状1 1 1 二叉树和自动机的研究背景1 1 2 国内高端并行计算机发展现状21 1 3 国外高端并行计算机发展现状21 1 4 并行编译及其发展31 2 论文的研究内容41 2 1 本课题研究的目的和意义41 2 2 本文的主要工作51 3 论文的结构安排。5第二章并行方法理论基础72 1 系统设计72 1 1 并行程序开发策略72 1 2 依赖关系分析82 2 应用设计lo2 3 本章小结。1 3第三章基于矩阵模型表示的d f a 的并行极小化1 53 1 问题描述1 53 2 相关定义1 53 3 自动机和矩阵的等价转化1 63 4 行列划分矩阵乘法理论l83 4 1 矩阵相乘串行算法1 83 4 2 矩阵相乘并行分块算法1 9v3 5 串行算法。2 l3 6 并行程序设计2 l3 7 并行计算过程分析2 33 8 小结2 6第四章基于p r a m 模型的二叉树旋转转换并行算法分析一2 74 1 问题描述2 74 2 理论基础2 84 3 二叉树和层次矩阵3 04 4 串行算法3l4 5 并行算法314 5 1l w 序列与r w 序列的并行转换3 24 5 2 四种旋转操作的并行处理3 34 5 3 最短转换路径3 44 6 实例分析。3 54 7 小结3 8第五章全文总结和展望3 95 1 总结。3 95 2 展望3 9参考文献4 1致谢：4 5攻读学位发表的学术论文目录4 7独创性声明4 9关于论文使用授权的说明。4 9第一章前言第一章前言1 1 课题背景与发展现状1 1 1 二叉树和自动机的研究背景( 1 ) 树型结构的概念是克希霍夫( k i r c h o f 0 在1 8 7 4 年为解决电路理论中求解联立方程的问题时首先提出的。树就是不含有回路的连通图，它是以分支关系定义的层次结构。在现实世界中广泛存在着类似于树型结构的客观事物之间的关系，如人类社会的族谱，各种社会组织机构，代数公式的结构，以及化学中的同分异构体问题。随着计算机科学的形成和发展，又极大地促进了树的研究和应用。众所周知，二叉树【1 】作为树型结构的一种特殊形式，以它在查找或检索技术中的时空有效性而被获得广泛的应用。除此之外，一般的广义树还可以在数据库技术中用来表示层次数据模型，在编译程序中用来表示源程序的语法结构，在人工智能中用来表示搜索过程和博奕策略等等。因此，研究二叉树相关算法有其重要的理论和实践意义。( 2 ) 研究自动机t z , 3 的分析与综合问题的数学理论，是控制论的一个重要分支。在自动机理论中，自动机都是指抽象自动机，即能变换和处理信息的离散系统的动态数学模型。因为自动机理论早期的研究工作与数理逻辑有关，所以数学家把它看作是数学的一个分支。因为自动机可作为计算机和计算过程的数学模型，所以计算机专家把它看作是理论计算机科学的一个分支。自动机理论由抽象理论、结构理论和自组织理论三个部分组成。发展简史由文献 4 】可知，1 9 3 6 年英国数学家a m 图灵提出二种抽象自动机，称为图灵机，开创了自动机的抽象理论。1 9 4 3 年美国神经生理学家w s 麦卡洛克和数学家w 皮茨在关于神经活动中思维的逻辑演算一文中，提出自动机的自组织理论。1 9 4 8 年美国数学家n 维纳在控制论一书中对现代自动机作了详细的分析，指出自动机的功能是变换和处理信息，灵敏自动机的理论是一个统计的理论。这就为自动机理论奠定了基础。1 9 5 6 年c e 香农和j 麦卡锡合编的著名论文集自动机研究一书出版。5 0 - - - 6 0 年代自动机理论【6 】得到迅速的发展。7 0 年代后，由于大规模集成电路和并行计算机发展的需要，细胞自动机得到了迅速的发展。随着模式识别、人工智能和大系统自动上的发展以银研制以曙术) ，为继市场装机得一具备2 l 世纪，高端计算技术已成为衡量一个国家经济技术综合实力的重要标志，它对经济、社会、国家安全和国防现代化建设具有重要的意义。由文献【9 】可知，以美、日为代表的发达国家非常重视研制高端计算机系统和开发应用技术。根据全球实用超级计算机5 0 0 强最新排行榜的统计分析，目前国际上已经有2 4 2 台系统的l i n p a c k 实测性能超过l万亿次秒。所有系统分布在世界上3 5 个国家和地区，美、日、德、英等发达国家占了8 0 的计算资源，其中仅美国就占总性能的5 6 ；并且5 0 0 台系统中的9 1 是由美国制造的，所有这些数据均表明美国在高端计算机的使用和生产方面仍然保持着绝对的领先优势。国外高端计算系统今后的开发热点是计算速度为十万亿次秒左右的系统，未来国际高端计算的发展将呈现超级计算机和网格计算2 种形态共存的趋势。2第一章前言1 1 4 并行编译及其发展并行编译系统是并型计算机的系统软件中十分重要的一部分，是充分发挥并行计算机性能、实现超级计算的关键。二十余年来，并行编译系统的理论和技术有了很大发展，并行编译系统在各种并型计算机上得到了成功的应用，国防科技大学计算机学院在银河系列巨型机研制过程中也相继研制成功了向量编译系统、共享存储器并行机并行编译系统和分布存储器并行机并行编译系统，这些系统都具有当时国内领先水平和国际先进水平。并行编译程序( p a r a l l e l i z i n gc o m p i l e r ) 处理并行语言的编译程序或串行语言的程序并行化的编译程序( 自动并行编译程序) 。自动并行编译的实现在常规编译程序的基础上采取两种途径：预处理方式和中间代码优化；预处理方式，在词法语法分析i ； 进行，对数据依赖及循环中的数组下标分析清晰、精确，但并不适用于多种语言而导致重复劳动；中间代码优化，在中间代码的基础上进行，它的优化方法可通用化，但由于各语言实现时的中间代码形式各异且不对外开放，因而仅适用于系统制造者内部实现。自动并行编译的内容主要是并行性的识别。其过程是：首先进行数据依赖分析，即识别各种依赖如数据依赖、控制依赖等；然后进行程序转换，主要是循环的转换；借助于运行系统和操作系统的支撑将源程序转化为并行代码或并行程序。自动并行编译一般进行源到源转换，即将串行源代码转换为并行源代码。并行语言的编译程序通常由词法语法分析、优化和代码生成三个阶段组成。其中优化是主体，它包括依赖关系分析、循环转换及进程分配、调度、同步和通信等。并行编译程序的主要研究内容包括：( 1 ) 依赖关系分析。依赖关系主要涉及四种：流依赖、反依赖、输出依赖及控制依赖。其中只有流依赖是固有依赖，其他依赖如输出依赖和反依赖在一定条件下可通过换名扩张及设置必要的附加语句消去，而控制依赖亦可转化为数据依赖。循环的并行化主要是通过依赖关系分析，改变原串行程序的词法次序，以缩短程序的执行时间而不改变其语义。因此，依赖关系分析提供了保证串行程序语义正确性的条件。编译程序依赖关系的测试方法主要有两种：精确测试法和近似测试法。精确测试法试图求出丢番图方程的通解以适合于方程数目较少且循环具有确定的上下界的情况，如依赖凸边域d c h 方法。近似测试法仅给出一些存在解的必要条件，如b a n e r j e e测试法、g c d 测试法及入测试法等。( 2 ) 循环转换。循环并行化之前应进行预优化工作，这包括循环的规范化( 尽可能线性化以便于依赖关系的分析，使循环的上界和步长均为13二叉树旋转和d f a 化简并行算法的研究等) 。循环的并行化可分为三个阶段：依赖分析( 跨迭代和迭代内依赖) 、循环转换和循环调度。循环的转换技术是对循环变量的集合进行划分或改变循环，主要技术有循环交换、合并、分布、分片和环路收缩等。循环调度则是为了取得更好的负载均衡，可分为静态和动态两类调度方法，这样的技术有：自调度s s 、块调度c s s 、引导调度g s s 和梯形调度t s s 等。( 3 ) 过程分析。过程分析主要包括别名分析、常数分析和引用分析，其目的是为了发掘被过程所隐蔽的信息以利依赖分析。对过程调用的处理，可在程序优化之前，采用内联扩展的办法即将被调用过程通过参数代换嵌入到调用处，最终使整个程序只包含惟一的过程，这种方法简单有效，但极耗内存，是一种消极的方法。2 0 世纪7 0 年代，c r a y - 1 上的向量处理标志着自动并行编译工作的开始，当时只有某些适合于向量化的模式能被识别。7 0 年代末，美国i l l i n o i s 大学研制了p a r a f r a s e ，在向量化和并行化领域进行了开拓性的研究。此后这方面的工作相继展开，到了8 0 年代，随着数据依赖关系的分析技术的成熟、商品化工具( 如k a p 等) 的出现及运用这些产品的系统开始获益，也标志着串行程序的自动并行化技术( 围绕f o r t r a n ) 取得了长足的进步。为向量化及后来的自动并行化工作做出重要贡献，并奠定理论基础的主要是i l l i n o i s 大学的u b a n e r i e e ，m j w o l f e 和r i c e 大学的k k e n n e - d y ，r a l l e n 等对数据依赖的分析和循环转换的研究。目前，完全自动化的并行编译十分困难，因为现有程序中某些算法的固有顺序性成为阻碍其发展的瓶颈。事实上，一个性能良好的并行程序可能需要的不仅仅是并行性识别或代码转换，更重要的是设计合适的并行算法。所以，今后发展的趋势可能是增加并行语言成分和自动并行化的结合。1 2 论文的研究内容1 2 1 本课题研究的目的和意义从1 9 4 6 年世界上第一台计算机e n i a c 诞生至今的5 0 多年时间里，单个c p u 的性能发生了翻天覆地的变化，目前已经达到相当高的水平，但就一些超大规模计算或一些必须实时完成的任务而言，如果不利用并行计算技术是很难满足用户需求的。并行是一种提高计算机性能的有效方法，它能够将原本串行( 线性) 处理的工作改成并行( 多维) 处理，不仅节省了使用的时间，并且减少了所用的存储空间。并行技术是提高实际运行速度的关键。因此，并行程序设计和并行编译技术已成为当代计算机软件的重要研究课题之一。基于矩阵模型表示的d f a 的极小化和二叉树旋转转换算法是编译系统、数据结构4第一章前言中的关键技术，高性能计算和并行处理是当前提高计算机性能的主要手段。因此，基于矩阵模型表示的d f a 的并行化简和二叉树旋转转换算法的并行处理是计算机科学并行计算研究领域的重要分支。本课题主要研究其并行转换技术和其相关算法，对并行计算理论研究和并行算法设计有其理论和实践意义。1 2 。2 本文的主要工作二叉树和自动机识别在数据结构和编译技术中占有重要地位，对基于矩阵模型表示的d f a 的化简和p r a m 模型下二叉树旋转转换算法等问题的并行处理将成为并行方法研究在系统设计和应用设计方面的关键环节。本论文对并行方法的研究主要基于两个方面：应用设计和系统设计。首先，系统设计方面，主要对基于矩阵模型表示的d f a 的化简问题进行研究，提出了一种基于矩阵模型表示的d f a 的并行化简方法，其算法基本思想：通过对基于矩阵模型表示的d f a的化简方法进行分析、研究，借助于并行算法中的行列划分矩阵乘法理论，最终成功实现了d f a 的极小化算法的并行化处理。其次应用设计方面，主要对p r a m 模型下二叉树旋转转换算法进行研究，提出了一种p r a m 模型下二叉树旋转转换算法的并行处理方法，其基本思想：引入层次矩阵，通过对二叉树和层次矩阵的等价转换，把对二叉树的操作转换成对层次矩阵的操作；最终实现对二叉树转换的并行处理。最后，总结全文，并展望了并行技术的研究前景和方向。1 3 论文的结构安排。本论文全文共分5 章，第3 、4 章为重点：第1 章，概要性的论述了有关二叉树和自动机识别的应用前景，研究背景以及发展现状，提出了本文的主要研究内容对基于矩阵模型表示的d f a 的化简和p r a m 模型下二叉树旋转转换算法等问题的并行处理，最后介绍了本文的组织结构。第2 章，为了介绍后文对基于矩阵模型表示的d f a 的化简和p r a m 模型下二叉树旋转转换算法等问题的并行处理，本章对并行方法的研究分别从系统设计和应用设计两个方面，给出了依赖关系分析、并行计算模型p r a m 等相关理论。第3 章，本章主要从系统设计方面，对基于矩阵模型表示的d f a 的化简问题进行研究，详细地描述了对基于矩阵模型表示的d f a 的化简问题的并行化简方法，其算法基本思想：通过对基于矩阵模型表示的d f a 的化简方法进行分析、研究，借助于并行5二义树旋转和d f a 化简并行算法的研究算法中的行列划分矩阵乘法理论，最终成功实现了d f a 的极小化算法的并行化处理。第4 章，本章主要从应用设计方面，对p r a m 模型下二叉树旋转转换算法进行研究，详细描述了p r a m 模型下二叉树旋转转换算法的并行处理方法，其基本思想：引入层次矩阵，通过对二叉树和层次矩阵的等价转换，把对二叉树的操作转换成对层次矩阵的操作；由于对矩阵的并行处理技术已经非常成熟，所以借助矩阵这个“桥梁，最终实现对二叉树转换的并行处理。第5 章，总结全文，并展望了并行计算的研究前景和方向。6第二章并行方法理论基础第二章并行方法理论基础并行计算技术1 0 。1 5 1 的发展已有2 0 多年的历史了。时至今日，高性能并行计算依然缺乏有效的并行程序设计方法和工具，使得编写并行程序、理解并行程序的行为、调试和优化并行程序的性能都很困难，研究并行程序设计方法迫在眉睫。本论文对并行方法睁1 9 1的研究主要基于两个方面：应用设计和系统设计。2 1 系统设计并行方法的系统设计主要是对并行编译的研究。当前，随着计算机的大量使用，编译的重要性日趋显著。进入9 0 年代，并行编译的研究取得了很大的进展，若干并行编译玲2 3 1 的关键技术被发现，如并行程序开发策略、依赖关系分析等。并行编译技术如图2 一l 所示：图2 - 1 并行编译技术2 1 1 并行程序开发策略在多处理机系统中，必须用并行程序设计【砒7 】语言编写程序。或者把已经用串行语言编写的程序转换成并行语言程序之后，才能在多处理机系统上运行。研究大量的现有并行应用程序，可以归纳出几种常用的开发并行应用程序的策略：自动并行化，调用并行库和重新编写并行代码1 2 6 。( 1 ) 、自动并行化策略，主要由以下3 个部分组成：7也是目前开发并行应用程序最流行的方法。( 3 ) 、重新编写并行代码策略，有以下3 个部分：对现有串行代码进行重大修改；编译器支持并行化；生成并行应用程序。分析现有串行源代码的本质结构，对现有串行源代码进行重要甚至时彻底的修改或者从头开始编写全新的并行代码，这样产生的并行程序，质量高，运行快，但是这样一来，程序员的编程负担将是繁重的。2 1 2 依赖关系分析本节讨论以实现程序并行化【2 9 。3 】为目的的依赖关系分析技术。由文献 4 ，3 4 可知，一个串行程序描述了一个“动作 集合，这些动作将按一定的顺序执行。为了完成程序的并行化，并行编译系统将在这些动作中寻找一个新的执行序列，以充分发挥并行体系结构的性能，缩短整个程序运行所需的墙钟时间。这意味着需要将这些动作分组，在一8第二二章并行方法理论基础个组内的动作可以并行地执行。将动作分组的前提是要保证程序的语义不变，而这就要遵循程序内涵中的依赖关系的约束。这种依赖关系是由程序串行执行时存储访问的方式和控制流决定的。所以，依赖关系分析技术是程序并行化技术的基础，也是并行编译的基础。基本的依赖关系分析问题是：给定两个程序变量，判定它们在程序执行中是否会访问相同的存储单元。依赖关系分析技术分为数据依赖和控制依赖，因为影响程序向量化和并行化的主要关系是数据依赖关系，所以本章主要讨论数据依赖关系，并常常将其简写为依赖关系。( 1 ) 数据依赖及其分类嵌套循环l 中的语句t 和语句s ，如果存在s 的一个实例s ( i ) ，t 的一个实例丁( ，) ，以及s 的一个变量，t 的一个变量y ，且满足以下条件，则称语句t 依赖于语句s ：x 和y 至少有一个是它所在语句的输出变量；x 在实例s ( f ) 中和y 在实例t ( j ) 中都表示同一个存储单元m ；在程序串行执行时，s ( i ) 先于t ( j ) 执行；在程序串行执行时，从s ( i ) 执行结束到t ( j ) 开始执行前，没有其它对m 的写操，作。详见参考文献 4 】。由变量x 和y 引起的语句丁关于语句s 的3 种依赖关系是：如果x o u t ( s ) ，y p c ( t ) ，则丁流依赖于s ；如果x i n ( s ) ，y o u t ( t ) ，则丁反依赖于s ；如果x o u t ( s ) ，y o u t ( t ) ，则丁输出依赖于s 。( 2 ) 依赖距离、方向和层次设语句s 和r 是嵌套循环l 中的语句，如果语句r 依赖于s ，则存在实例s ( o 依赖t ( j ) 。令d = 一f ，仃= s i g ( d ) ，= l e v ( d ) ，我们称d 是这个依赖关系的依赖距离向量。其中仃是依赖方向向量，是依赖层次，也称语句r 在第，层上以距离向量d 、方向向量仃依赖于语句s 。依赖距离向量指明了对同一个存储单元的两次访问之间相隔的循环迭代数。依赖方向向量指明了存在依赖关系的两个迭代在每一维上的依赖方向。依赖层次则指明了是由哪一层循环引起的依赖关系。( 3 ) 依赖关系分析o兀组系的的和致1 )2 )下( 2 ) 若i j ，则r 间接依赖s ；( 3 ) 若扛_ ，且s t ，则s 间接依赖r 拿证明详见文献 3 4 ，3 7 】。由文献 3 1 ，3 2 】可知，定理1 和2 是依赖关系分析的基础定理。由这两个定理，可以将嵌套循环l 中关于s 的变量工和t 的变量y 的依赖关系分析问题归结为寻找依赖方程( 1 ) 的所有满足约束( 2 ) 的整数解( f ，_ ，) ，然后根据i _ ，或i = _ ，将解的集合划分成3 个子集。如果某个子集非空，则表明存在相应的依赖关系。2 2 应用设计并行方法的应用设计【3 1 】主要考虑如何将并行技术运用于链表、数组、树或堆结构1 0第二章并行方法理论基础等数据结构中。由于二叉树是计算机科学中最基本的也是最重要的树型数据结构。二叉树旋转算法的研究无论在算法理论上还是在实际应用中都具有重要的意义。基于此，本论文主要涉及二叉树旋转转换的并行处理。为了介绍后文的二叉树旋转转换的并行处理方法，本小节给出了并行计算模型的相关概念。所谓并行计算模型，通常指从并行算法的分析与设计的角度出发，抽象出各种并行计算机( 至少某类并行计算机) 的基本特征，这样一个抽象的计算模型就形成了。从本质来讲，计算模型可以看作是一种桥梁，一种连接计算机软件与硬件的桥梁，通过这个桥梁，能够设计、分析算法，在计算模型上编译高级语言，并通过硬件来实现算法。并行计算模型也可以被看成是便于并行计算的设计及理论分析的抽象机，一种介于程序设计级和体系结构级之间的、能够省略并行处理细节的抽象机。从更广的意义上说，并行计算模型为并行计算起到了提供软件和硬件界面的作用。并行系统软件设计者和硬件设计者在该界面的约定下，开发对并行性的支持机制，从而提高并行系统的性能。需要注意的是，并行计算模型并非并行计算机，它不同于某一具体的并行计算机，某一具体的并行计算机是实现并行算法的物质基础。但对并行算法研制者来说，不能局限于某种并行计算机来研究并行算法，而需借助于抽象的计算模型，它是实现和分析并行算法的基础。计算模型的位置如图所示：用户系统图2 - 2 计算模型在系统4 个层次中的位置图目前，在并行计算机的研究中，存在着一些“通用 的计算模型，其中最有影响的二二叉树旋转和d f a 化简并行算法的研究是p r a m ，b s p 和l 0 9 p 三种。本节主要介绍p r a m 模型。p r a m ( p a r a l l e lr a n d o ma c c e s sm a c h i n e ) 4 2 是一种理想的并行计算模型，也是早期最有影响的理论模型，属于s i m d 共享存储模型。p r a m 模型是顺序的冯诺依曼存储程序模型的自然扩展，每个处理机有自己的局部存储器，多个处理机通过共享存储器进行通讯。p r a m 模型仅有处理机数目这一个参数。在这种模型中，一台并行计算机由若干处理机和一个全局的共享存储器构成，各处理器在任何时刻均可通过共享存储单元相互交换数据；各处理机同步地进行工作，都按读存储器、计算、写存储器的步骤循环运行，如下图所示：图2 3p r a m 模型在p r a m 模型中，假定存在着一个容量无限大的共享存储器，有有限活着无限个功能相同的处理器，且其均具有简单的算术运算和逻辑判断功能，在任何时刻各个处理器均可通过共享存储单元互相交换数据。因此并行计算机被理想化了，它假定并行处理机进行的内存存取和计算都是同步操作，而且忽略了同步的开销。根据存储器是否可并发读写，p r a m 分为并发读写( c r c w ) ，并发读互斥写( c r e w ) ，互斥读写( e r e w ) - - - 种模型。已经提出的几个p r a m 模型的扩展模型，它们主要体现在反映本地存储器和消息传递概念，集中考虑在如下几个方面：( 1 ) 存储器存取。l p r a m ( l o e a l m e m o r y p r a m ) 在c r e w p r a m 模型i - _ y g 每个处理器附加一个无限的局部私有存储器：；q r q w ( q u e u e r e a d ，q u e u e w r i t e ) 把访问同一内存块的请求加入队列，以f i f o 的方式进行访问；( 2 ) 异步。阶段p r a m 模型引入异步执行扩展p r a m 。计算分作若干阶段，每个阶段可以异步执行，阶1 2第二章并行方法理论基础段结束时进行同步。( 3 ) 延迟等待。b p r a m ( b l o e k p r a m ) 是l p r a m 扩展，通过传输连续的数据块以减少通信延迟。它定义了2 个参数，l 表示延迟或启动时间，b 表示块尺寸。本地存取代价为1 个单位时间，全局共享存取花费l + b 个时间单位。( 4 ) 带宽。d r a m ( d i s t r i b u t e dr a m l 以私有分布存储代替全局共享存储器，忽略通信网络拓扑。对非本地存储器的访问，根据数据划分和执行顺序的最可能阻塞的情况，以一个代价函数表示有限带宽，指导调度减少非本地存储的访问。显然，允许同时写是不现实的，于是又对p r a m c r c w 模型做了进一步约定，于是形成了下面几种模型：只允许所有的处理器同时写相同的数，此时称为公共( c o l l l l i l o n ) 的p r a m c r c w ，简称为c p r a m c r c w ；只允许最优先的处理器先写，此时称为优先( p r i o r i t y ) 的p r a m c r c w ，简称为p p r a m c r c w ；允许任意处理器自由写，此时称为任意( a r b i t r a r y ) 的p r a m c r c w ，简称为a p r a m c r c w 。往存储器中写的实际内容是所有处理器写的数的和，此时称为求和( s u m ) 的p r a m c r c e ，将称为s p r a m c r c w 。上面的模型中，p r a m e r e w 是功能最弱的计算模型，而p r a m c r c w 则是最强的计算模型，令t m 表示某一并行算法在并行计算模型m 上的运行时间，则有：其中，p 为处理器的数目，它的含义是，一个具有时间复杂度为t c r e w 或者t c r c w的算法，在p r a m e r e w 模型上要花费l o g p 倍的时间去模拟实现。p r a m 模型的优点：p r a m 模型特别适合于并行算法的表达、分析和比较，使用简单，很多关于并行计算机的底层细节，比如处理器间通信、存储系统管理和进程同步都被隐含在模型中；易于设计算法和稍加修改便可以运行在不同的并行计算机系统上；根据需要，可以在p r a m 模型中加入一些诸如同步和通信等需要考虑的内容。2 3 本章小结为了介绍对基于矩阵模型表示的d f a 的化简和p r a m 模型下二叉树旋转转换算法等问题的并行处理，本章给出了并行方法研究在系统设计和应用设计方面的关键理论，二二叉树旋转和d f a 化简并行算法的研究为后文作了铺垫。1 43 2 相关定义定义1 ：设有限自动机m 为一五元式( j ，0 ，s ，万，名) ，d 和s 分别为m 的输入集、输出集和状态集，万和a 分别为m 的状态转移映射和输出映射。l t l 3 礅 4 2 ，自动机m 可由如下矩阵模型表示： 丢三三 三二耋对任意的x x ，。( 3 3 一- 2 1 ) ，彳( x ) ，b ( x ) 分别为输出映射和状态转换映射，彳( x ) ，b ( x ) 的物理意义：若口 ( 洳) = l ，1 5二叉树旋转和d f a 化简并行算法的研究贝, i j m 对输入勤，当处于状态9 时，将输出z f ；若：b ( x o ) = 1 ，则m 对输入知，将从状态q ，转移到q i ；定义2 ：向量运算o 定义如下( 其中丁代表矩阵的转置，o 为异或加运算)设e 与f 为两个m 维布尔列向量，e = ( 口l ，口2 ，口朋) r ，= ( 6 l ，b 29ojo ) r ，则e 0 。f = ( 口lo 6 l ，口2o 6 2 ，口卅o b m ) r 。定义3 ：m 中的2 个状态s l ，s 2 是等价的：当m 分别处于初态& ，& 时，对任意的输入序列口= a l n 2 口j | i j + ，都有相同的输出响应序列，即a ( s l ，口) = 旯( s 2 ，口) 。k 等价类的判定：g 与七q j 等价营f v x l ，x 2 ，以彳，下列阶矩阵： 彳( 工。) ，i a ( x 。) b ( x 1 ) x b ( x i ) ，h = 2 ，3 ，后；的第i ，例分别做o 运算的结果均为零向量。证明见文献【5 3 】。3 3 自动机和矩阵的等价转化自动机是编译理论中的重要知识点，通过自动机的研究提高编译速度，将成为并行方法在系统设计方面研究的重要内容。本节在文献【4 2 ，4 3 】的基础上分析一般有限自动机的矩阵模型，对有限自动机m 一 ，不依赖于线路的结构函数，而是直接从状态流程表出发，通过引入，( m 的输入集) 、o ( g 的输出集) 和s ( 肘的状态集) 的布尔量表示x ，z ，q ，将万( m的状态转移映射) 和五( m 的输出映射) 换用矩阵形式的映射方程q = b ( x ) xq 和z = 么( 曲q 描述，即得到m 的矩阵模型表示： 丢三三 暑二星，工x 。其中4 ( 功和b ( 功分别是有限自动机m 的状态映射矩阵和输出映射矩阵。( 1 ) 输入集，的布尔量表示设，有，个元素，则有自然数，使：2 卜1 ，2 i ，任取集合x = ( 口l ，口2 ，a ，) ia f = 0 , 1 ；i = 1 , 2 ，) 的r 个元素，设得到的子集为，然后按任意的方式艿将蜀与j 一一对应，这样可用x o 表示，用z = ( 而，x 2 ，而) 表示输入变量：x 0 = ( a l , 口2 ，a ，) 。第三章基丁矩阵模型表示的d f a 的_ 并行极小化如果= ( 口l ，口2 ，a ，) x o 表示艿( ) ，那么很明显，对任何输入= ( 口l ，口2 ，a ，) ，都有z = x o 营矸2 矸= 1( 3 - 3 )其中矽：肛q 一，汪1 ，2 ，工h ，a f = 0( 2 ) 输出集0 、状态集s 的布尔量表示将输出集0 、状态集s 中的元素任意排定一个顺序，分别设为d 。，d ：，d 口和s 。，s 2 ，s 。，那么输出集0 、状态集s 分别可用布尔变量z = z 。，z ：，z 口) 和q = q l ，q 2 ，q ) 来表示，z l = 1 表示0 j ，i = 1 , 2 ，p ，q f = 1 表示墨，i = 1 , 2 ，n 。由于任何时刻，m 所处的状态和输出是唯一确定的，因此要求z i = 1 表示z 集和q集必须满足正交性( 式中+ 和幸为布尔加和乘运算) ，即一z 。2q + a + ：z 。p k ：y ；1 k , y p， g + q q 2 。+ g a + ：q 。= 1f y ；1 y 疗( 3 ) 矩阵模型在前面，输入集，、输出集0 、状态集s 分别都采用了布尔向量表示，那么这里可以用布尔函数矩阵来描述映射万和a ，从而得到m 的矩阵模型表示。详细过程如下：对每个g o ( 1 j o 以) 作布尔函数和式g 。= 矸。2 而a i q一( 3 - 4 )其中每一个单项中的而= ( 口。，a ：，口，) 和q 满足万( q j ，x o ) = q ，o 。由( 1 ) 式可知，对任意的输入= ( 砰，x ：o ，砰) 和任意的状态q i ，m 是否对输入而从状态q f 转移到状态a j o ，关键要看和式( 2 ) 的值在x = 而和q = 1 时是否等于1 ，即q j o = b j o l ( x ) g + 2 ( z ) 幺+ + b y o 。( 工) q( 3 - 5 )的最终值是否为1 ；式子( 3 ) 反映了m 是否对输入而从状态q f 转移到状态q ，。的判定条件，这里的屯o p ( 力( p = 1 , 2 ，刀) 是关于工= ( 五，屯，而) 的布尔函数。当j o = 1 ，2 ，刀时，式子( 3 ) 就变换成n 个布尔方程，其矩阵形式表示为：q = b ( 曲q( 3 6 )1 7二叉树旋转和d f a 化简_ 并行算法的研究在这里，表不：在布尔函数环上按通常的数字矩阵乘法规则相乘，b ( 工) 为布尔函f ，6 l 。( 工) 6 l 。( x ) 、i数矩阵，召( 功= i；i简记为曰( 曲= 【( 功】删。l 色- ( x ) 6 朋( z ) j 同理，可以从输出映射五( 9 ，x ) 出发，推导出描述兄的布尔方程z = 彳( 石) x q( 3 7 )h ( 功( z ) 、i彳( 功= iil简记为彳( 功= 口 f ( 功】朋；h t ( x ) a n n ( x ) p 。上面的( 3 - 6 ) 和( 3 - 7 ) 式组合起来： 丢三：甚；二耋工x 就是有限自动机m 一 的矩阵模型。3 4 行列划分矩阵乘法理论行列划分矩阵乘法理论 5 2 ，5 4 是矩阵运算中的重要理论，是数值计算中最重要的一类运算，特别使在线性代数和数值分析中，他发挥着不可替代的作用。一个m n 阶矩阵a = 【口i 】与一个n x k 阶矩阵b 一【】相乘，就可以得到一个m xk 阶的矩阵c = 【c o 】，它的元素每个元素c 。等于a 的第i 行向量与b 的第j 列向量的内积。矩阵相乘的关键是“对准 ，即相乘的两个元素的下标要满足一定的标准。因此常采用一些矩阵变换的方法，如适当旋转矩阵元素，或适当复制矩阵元素，或采用流水线的方法使元素下标对准。3 4 1 矩阵相乘串行算法1 8算法：单处理器上矩阵相乘串行算法输入：厶。，输出：b e g i nf o ri = ot om 一1d of o r j = o t ok - 1d oc i j = 0f o r r - - o t o n ld 0c i ，j 】= c 【i ，j 】+ 小，r 】幸b r d 】第三章基丁矩阵模礤表示的d f a 的并行极小化e n dt b re n df o re n df o re n d假定一次乘法和加法运算时间为一个单位时间，则显然其时间复杂度为o ( m n k ) 。3 4 2 矩阵相乘并行分块算法矩阵相乘也可以用分块的思想实现并行，即分块矩阵乘法( b l o c km a t r i xm u l t i p l i c a t i o n ) 。分块矩阵乘法的初始化：( 1 ) 、把矩阵a 按行划分成p 块( 这里约定p 为处理器个数) ，设“= f m p ，每个块包含有连续的“个行向量，这些行块依次记为a ，4 ，a p 书分别存放在标号为o ，l ，p l的处理器中；( 2 ) 、对矩阵b 则按列划分为p 块，m v = f k p l ，每块包含有连续的1 ，个列向量，这些列块依次记为岛，置9o 巳p 分别存放在标号为o ，l ，p 一1 的处理器中；( 3 ) 、将结果矩阵c 也相应的同时进行行、列划分，得到p x p 个大小为u ，的子矩阵，第衍亍第，列的子矩阵记为c ：f f ，则有g = 4 岛，其中4y gu n 阶，岛为疗y 阶。表3 1 ：开始时的情况处理器编号ol2p - 1444a v l存储器内容战垦岛以一t图3 - 1 矩阵相乘并行分块算法中的数据交换表3 - 2 ：数据交换后的情况处理器编号ol2p 1a44a v l存储器内容马垦马岛分块矩阵乘法【5 2 】的基本思想：开始，各处理器的内容如表格l 所示。此时各处理1 9f o rs = o t o i l - ld 0c ，z ，j 】= c 1 ，z ，】