（计算机应用技术专业论文）并行序列模式挖掘关键问题研究.pdf

并行序列模式挖掘关键问题研究 摘要 序列模式挖掘主要研究如何从大规模数据库中寻找具有时空序列特征的频繁模 式。由于在海量数据库中进行序列模式挖掘是项耗时的工作，因此利用并行计算技术 来加快挖掘速度是一个有效的解决方法。对并行序列模式挖掘算法的研究表明，诸如 多计算单元之间的负载均衡问题、通信问题、空间搜索策略问题等，是研制高效并行 序列模式挖掘算法的关键。本文针对这些关键问题展开研究，主要研究工作如下： ( 1 ) 详细分析了现有并行序列模式挖掘算法的设计思想，指出影响并行序列模式 挖掘算法效率的关键问题在于提供有效的负载均衡策略、通讯策略和空间搜索策略 等，分析了现有算法在解决这些问题上存在的不足。 ( 2 ) 针对共享存储的并行计算环境，建议利用动态任务分配机制来解决负载均衡 问题，基于局部并行剪枝技术来设计空间搜索策略，基于任务并行的计算模型来设计 序列模式挖掘算法，据此设计了一种基于s m p 系统的并行序列模式挖掘算法p f s p a n 。 理论分析和实验结果表明，p f s p a n 算法能够有效地进行序列模式挖掘。 ( 3 ) 针对分布存储的机群并行计算环境，提出利用任务并行和数据并行相结合的 方式来设计并行序列模式挖掘算法，采用基于前缀树传送的通讯方法，静态与动态任 务分配机制相结合的负载均衡方法，基于先全局剪枝后项序扩展剪枝的两步剪枝空间 搜索方法，据此设计了一种基于机群系统的并行分布式序列模式挖掘算法f p m s p ，并 对算法作理论分析和实验验证。 关键词：序列模式并行算法负载均衡空间搜索策略通讯 r e s e a r c ho i lk e yp r o b l e m sf o rp a r a l l e l s e q u e n t i a lp a t t e r n sm i n i n g a b s t r a c t a so n eo ft h et h ep r i m a r yr e s e a r c hf i e l di nd a t am i n i n g ，s e q u e n t i a lpa t t e r nm i n i n g w h i c he n u m e r a t e sf r e q u e n ts p a t i o - t e m p o r a lc h a r a c t e r i s t i cp a t t e r n si nl a r g ed a t a b a s ei sa t i m e c o n s u m i n gt a s ka n di ts e e m st h a ti ti sag o o di d e at os p e e d u pt h em i n i n gp r o c e s s b yu s i n go fp a r a l l e lc o m p u t et e c h n o l o g y t h er e s e a r c ho np a r a l l e ls e q u e n t i a lp a t t e r n m i n i n ga l g o r i t h ms h o w st h a ts o m ek e yp r o b l e m ss u c ha sw o r k l o a db a l a n c i n g ， c o m m u n i c a t i o na n ds e a r c h i n gs t r a t e g yi ns o l u t i o ns p a c ea m o n g c o m p u t i n g - u n i t sa r et h ek e y p r o b l e m si nd e v e l o p i n ge f f i c i e n tp a r a l l e lm i n i n ga l g o r i t h m t h e s ek e yp r o b l e m sa r e s t u d i e dd e t a i l yi n t h i sd i s s e r t a t i o na n dt h em a i nc o n t e n to ft h i sd i s s e r t a t i o ni sa s f o l l o w ： ( 1 ) t h ei d e a so fs e v e r a lk n o w np a r a l l e ls e q u e n t i a lp a t t e r n sm i n i n ga l g o r i t h ma r e d i s c u s s e di nd e t a i l t h ea n a l y s i si n d i c a t e st h a tt h ek e yp r o b l e m st h a ta f f e c te f f i c i e n c yo f p a r a l l e la l g o r i t h mf o rm i n i n gs e q u e n t i a lp a a e m sa r ee f f e c t i v es t r a t e g i e sf o rl o a d i n g b a l a n c i n g ，c o m m u n i c a t i o na n ds e a r c h i n gi ns o l u t i o ns p a c e ，a l s ot h ed e f i c i e n c yo ft h e s o l u t i o nt ot h e s ek e y p r o b l e m su s e di nt h e s ea l g o r i t h m si sp r e s e n t e d ( 2 ) a i m i n gt o t h ep a r a l l e lc o m p u t e rs y s t e mw i t hs h a r e dm e m o r y , d y n a m i ct a s k s d i s t r i b u t i o nm e t h o dt ot h ew o r k l o a db a l a n c i n gp r o b l e m ，l o c a lp a r a l l e lp r u n i n gt e c h n o l o g y f o rt h es e a r c i n gs t r a t e g yi ns o l u t i o ns p a c ea n dt a s kp a r a l l e l i s mm o d e lb a s e ds e q u e n t i a l p a t t e r n sm i n i n ga l g o r i t h ma l eu s e d ap a r a l l e la l g o r i t h mf o rm i n i n gs e q u e n t i a lp a t t e r n s u s i n gt h e s em e t h o d sb a s e do ns m pc o m p u t e rs y s t e m ，a b b r e v i a t e db yp f s p a n ，i sd e s i g n e d i nt h i sd i s s e r t a t i o n b o t ht h e o r e t i c a la n a l y s i sa n dp r a c t i c a le x p e r i m e n t ss h o wt h a tp f s p a n c a nm i n es e q u e n t i a lp a t t e r n se f f e c t i v e l y ( 3 ) a i m i n gt op a r a l l e lc o m p u t e re n v i r o n m e n t 丽t l ld i s t r i b u t e dm e m o r y , ap a r a l l e l a l g o r i t h mm o d e lc o m b i n i n gd a t ap a r a l l e l i s ma n dt a s kp a r a l l e l i s m ，t h ec o m m u n i c a t i o n m e t h o dw h i c hb a s e so nt r a n s m i s s i o no fp r e f i xt r e e s ，t h el o a d i n gb a l a n c i n gm e t h o di n c l u d e s t a t i ca n dd y n a m i ct a s kd i s t r i b u t i o n , a n dt h et w o - s t e ps e a r c h i n gm e t h o di ns o l u t i o ns p a c e w h i c hb a s e so ng l o b a lp r u n i n ga n di t e m - e x t e n d i n gp r u n i n ga c c o r d i n gt ot h eo r d e ro fi t e m s a r ea l s ou s e d o nt h eb a s i so ft h e s em e t h o d s ，a l g o r i t h mf p m s p ，a p a r a l l e la n dd i s t r i b u t e d a l g o r i t h mf o rm i n i n gs e q u e n t i a lp a t t e r n so nc l u s t e rh a sb e e nd e s i g n e di nt h i sd i s s e r t a t i o n ， t o o t h r o u g ht h e o r e t i c a la n a l y s i sa n de x p e r i m e n t s ，t h ep e r f o r m a n c eo ff p m s p i sp r o v e d k e yw o r d s ：s e q u e n t i a lp a t t e r n ；p a r a l l e la l g o r i t h m ；w o r k l o a db a l a n c i n g ；s e a r c h i n gs t r a t e g y i ns o l u t i o ns p a c e ；c o m m u n i c a t i o n 表格清单 表2 1 一个顾客事物数据库1 2 表2 2 与表2 1 事务数据库对应的顾客序列数据库1 2 表2 3 频繁项集及映射1 4 表2 4 转换后的数据库1 4 表2 5 投影数据库和序列模式1 9 表3 1i b m 数据生成器的主要参数及说明3 5 表3 2 不同规模数据集下的实验结果3 6 i v 插图清单 图1 。1 五类m i m d 并行计算机体系结构6 图3 1频繁序列格3 0 图3 2三个处理器并行生成f s 树3 1 图3 3并行挖掘时的动态任务分配3 2 图3 4两个处理器进行并行局部剪枝。3 3 图3 5p f s p a n 与t p f b p 算法运行时间及加速比比较3 6 图3 6不同支持度下p f s p a n 与t p f 。b p 算法运行时间比较3 7 图4 1三棵局部f s 树。4 3 图4 2合并序列树4 3 图4 3f p m s p 与t p f b p 算法运行时间及加速比比较4 8 图4 4不同数据规模下f p m s p 与t p f b p 算法运行时间比较4 8 i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金月巴王些太堂 或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：萎锋彳 签字日期：矽口7 年午月j7 日 学位论文版权使用授权书 本学位论文作者完全了解金月巴王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金月垦王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 珈坪 签字日期：z 驴乍午月，7 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日 邮编： 电话： 归9 日 致谢 值此论文完成之际，谨此向我的导师田卫东副教授致以衷心的感谢和崇高的敬 意! 在近三年的硕士研究生阶段，我自始至终都得到了田老师悉心的指导，所取得的 点滴进步，无不浸透着田老师的心血。田老师渊博的知识、严谨的治学态度、精 益求精的工作作风给我留下了刻骨铭心的印象，他是我学习的榜样。没有田 老师的指导和帮助，没有他对我论文反复修改和精心提炼，我是不可能顺利完成我的 毕业论文的。田老师不仅在学术上给我指明了方向，同时在思想上、人生态 度和意志品质方面给予了我谆谆教诲，这些教益必将激励着我在今后的人生 道路上奋勇向前。 同时在这里，我要十分感谢计算机与信息学院的胡学钢教授，在我攻读硕士期间， 他给了我大量的指导、关怀和帮助，并提出了许多宝贵的意见，令我受益匪浅。 除此之外，我还要感谢吴共庆、张玉红、张晶等老师，与他们一起对数据挖 掘课题进行的讨论拓宽了我的思路；感谢我的师兄王丹阳，他为我提供了宝贵的研 究资料，并常与我交流相关课题的研究心得；感谢合肥工业大学人工智能与数据挖 掘研究室所有老师和同学对我的关怀和帮助。 特别感谢合肥工业大学可视化与协同计算研究室( v c c ) 提供了并行计算环 境，并给予了大量的相关资料。 感谢计算机与信息学院的王浩教授、曹航老师为我所付出的辛勤工作。 最后，衷心地感谢我的父母和其他亲朋好友对我的关心、支持和理解，没有他们 对我的鼓励，我是无法完成现在的硕士学业的。 作者：姜海辉 2 0 0 9 年4 月 第1 章绪论 1 1 研究背景和意义 近十几年来，随着数据库技术的成熟和数据应用的普及，人类积累的数据 量正在以指数速度迅速增长。然而，目前人们收集和存储数据的能力已经大大 超过了对其分析和综合处理的能力，从如此大量的数据中，获取有用的知识变 得越来越困难了，这就是被j o h nn a i s b e t t 称之为“信息丰富而知识贫乏 ( d r o w n i n gi ni n f o r m a t i o nb u ts t a r v i n gf o rk n o w l e d g e ) 的窘境j 。 为了对大量的数据进行有效地分析、利用和处理，数据库知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 1 j ，【2 j 酝酿而生。知识发现可以简单地 描述为从数据中发现有用知识的整个过程，而通常把其中使用专门算法从数据 中提取模式，然后再通过解释和评价模块转化成用户可以理解的知识的过程称 为数据挖掘( d a t am i n i n g 引。近年来，国内外已有许多学者进入到数据挖掘研 究领域，在知识模式、算法研究、数据挖掘应用等方面均取得了很好的成果。 在数据挖掘的实践中人们发现，现实世界的真实数据多数都带有时间特征， 例如超市内顾客在购买商品的序列、商品价格数据、天气数据和生产数据等。 这类被称为时态数据( t e m p o r a ld a t a 4 】数据中带有的时间特征通常表达了数据 或行为的先后次序，蕴含有很重要的序列信息。对这类数据的挖掘是数据挖掘 的一个重要内容。 序列模式挖掘( s e q u e n t i a lp a t t e r nm i n i n g ) 或称序列挖掘【5 l ，主要研究如何在 带有时间特征的数据库中挖掘频繁发生的序列，从而实现对未来行为的预期。 一个典型的序列模式的例子是“9 个月以前购买奔腾p c 的顾客很可能在1 个月内 订购新的c p u 芯片 。序列模式挖掘在现实生活中具有广泛的应用，包括顾客 购物模式分析和互连网访问模式分析，以及序列分析或者其他与时间相关的处 理过程分析，例如科学实验、自然灾难事件、疾病防治，d n a 序列、股票序列 的分析等【6 1 。 然而，序列模式挖掘在发展道路上也不可避免地会遇到种种问题，其中之 一就是挖掘所涉及的数据集的规模较大，造成巨大的运算量以及繁重的i o 操 作。虽然许多专家和学者就提高算法的效率做了大量的工作，不断地对算法进 行优化，但是随着序列模式挖掘数据规模的不断增大和挖掘模式的不断加长， 传统的单机系统在功能和性能上已难以达到预期效果。其主要原因一方面是单 处理机的c p u 和内存资源都非常有限，尽管对传统算法进行了许多改进工作， 但大规模和多维问题所需的单纯计算工作在单处理机上的运行时间仍然太长； 另一方面，许多事务数据库来源于分布式数据库或者这些数据分布于不同的站 点f 刀，而将它们搬到同一站点或同一计算机中以便于使用串行算法所带来的开 销是巨大的。所以，开发并行和分布式序列模式挖掘算法是十分必要的i s 】。 近年来，越来越多的研究人员开始关注并行序列模式挖掘课题，他们针对 不同并行计算机体系结构提出的并行算法在很大程度上提高了大规模序列模式 挖掘的效率。但是随着并行计算的规模越来越大、参与计算的处理器数目越来 越多，并行序列模式挖掘算法的并行效率提高得越来越有限，其原因归根结底 是不能很好地解决如下的几个问题： ( 1 ) 计算负载均衡 并行序列模式挖掘过程主要是将挖掘的工作量进行划分，然后交给不同的 处理器处理。由于整体工作量在挖掘前是未知的，因此如何进行平均地分配是 非常棘手的问题，往往会由于工作量分配不均造成某些处理器在工作时其他一 些处理器处于空闲状态，浪费了系统资源。 ( 2 ) 通讯开销 并行计算需要各计算单元之间的信息交互，因此通讯开销是必须要考虑的 问题，过大的通讯开销会降低整体的挖掘效率。如何减小通讯量和通讯次数是 并行序列模式挖掘面临的一大难题。 ( 3 ) 并行空间搜索策略 针对串行序列模式挖掘，已有大量简化搜索空间的策略被提出。这些策略 可以有效地降低挖掘的工作量，大大提高挖掘的效率。然而，由于受通讯、同 步等多方面因素的限制，这些策略并不能直接应用于并行序列模式挖掘。虽然 现有的并行序列模式挖掘算法提出了一些优化策略，但并没有很好地解决效率 提高的问题。 ( 4 ) 同步次数 并行序列模式的挖掘过程中，当计算进行到某个阶段，每个计算单元可能 需要其他计算单元提供的信息才能继续完成后面的计算，此时所有计算单元停 止计算，同时进行信息交互，这就是同步。同步次数的增多很大程度上会降低 并行序列模式挖掘的效率，在某些基于a p r i o r i 特性的算法中这种现象尤为突出。 ( 5 ) i 0 开销 序列模式挖掘涉及大规模数据库的多次扫描，受内存限制等条件的影响， 并行计算时必然会花费不小的i 0 开销。 ( 6 ) 数据偏移 在分布存储的并行计算机体系结构下挖掘序列模式，往往全局序列数据库 会被划分为大小相等的分块提交给各计算节点并行处理。各计算单元的本地数 据库里蕴含的信息量可能有较大差异，这样会造成计算单元之间的负载不均， 这就是数据偏移问题。 此外，针对特定的计算机体系结构，并行序列模式挖掘还面临着其他一些 关键问题，如共享存储环境下数据库互斥访问等。如何针对不同的体系结构设 计这些问题的解决方案已经成为并行序列模式挖掘的重要内容。 2 1 2 并行序列模式挖掘研究概况 1 2 1 序列模式挖掘问题 序列模式挖掘的概念是r a g r a w a l 等人在1 9 9 5 年首先提出的”】，其问题描述 如下。正式的形式化描述参见第二章。 给定一个由多个交易组成的交易数据库d ，每个交易描述某个顾客在某时 间购买的物品的集合。物品的集合称为项集。序列是来自相同顾客的多个交易 包含的项集的子集按时间先后关系的一个排列，每个子集称为一个元素 ( e l e m e n t ) ，然后给定由用户确定的最小支持度阈值( r a i n s u p p o r tt h r e s h o l d ) ，序 列模式挖掘就是去发现所有的频繁子序列( 即：这些子序列的出现频率不小于给 定的最小支持度) 。 1 2 2 序列模式挖掘研究概况 序列模式挖掘的问题被提出以后，人们不断地研究和改进在时间序列数据 库中挖掘序列模式和其他频繁模式的算法。现有的序列模式挖掘算法主要可以 分为两类：第一类是基于r a g r a w a l 和r s r i k a n t 在1 9 9 4 年提出的a p r i o r i 特性p 的 算法。a p r i o r i 特性首先应用在关联规则挖掘中，其基本思想是频繁模式的子序 列也一定是频繁模式。基于a p r i o r i 特性，人们提出了一系列类a p r i o r i 的序列模 式挖掘算法，这些算法中有采用水平数据格式( h o r i z o n t a ld a t af o r m a t ) 的算法， 如a p r i o r i a l l 算法【5 1 、g s p 算法【10 1 、p s p 算法【1 1 1 等；有采取垂直数据格式( v e r t i c a l d a t af o r m a t ) 的算法，如s p a d e 算法【1 2 】、s p a m 算法【1 3 】等。第二类是j h a n 等人提 出的基于模式增长( p a t t e r n g r o w t h ) 策略的算法，f r e e s p a n 算法【l 引、p r e f i x s p a n 算法【1 5 】1 1 6 】等。 另外，c a n t u n e s 等人提出了s p a r s e 算法【45 1 ，该算法的主要思想是将候选 序列的产生和在投影数据库空间搜索结合起来，每一步在产生出频繁元素后， 通过增长长度寻找模式。该算法应用在密集型数据库中能获得较好的性能。 以上算法都是在序列数据库中挖掘所有的序列模式，而且除了g s p 算法之 外，它们挖掘的都是普通的序列模式。每一个序列模式包含了组合数级的频繁 子序列，若序列模式的长度很长，则频繁子序列的数量往往大得惊人。 在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序 列模式，而是加入一定的约束，找出用户感兴趣的序列模式【4 6 】，【4 7 1 ，a g r a w a l 等 人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口( s l i d i n gt i m e w i n d o w ) 和分类约束，并提出了g s p 算法。g s p 算法是基于a p r i o r i 特性的算法， 同样具有类a p r i o r i 算法的缺点。 上述序列模式挖掘算法都是在一维信息中挖掘序列模式。若能在序列模式 中融合感兴趣的多维信息，在考虑与时间相关属性的同时，挖掘多维信息中感 兴趣的模式，则将得到能提供给用户更丰富信息的多维序列模式。h p i n t 等人 提出的u n i s e q 算法【4 8 1 能有效地挖掘多维序列模式，但在维度较高时其挖掘性能 会有所下降。 此外，当前国内外学者广泛关注的研究方向还包括增量式( i n c e r m e n t a l ) 序 列模式挖掘【4 9 1 、闭合( c l o s e d ) 序列模式挖掘5 0 1 、周期性( p e i r o d i c ) 模式挖掘 5 1 1 、 结构( s t r u c t u r e ) 模式挖掘【5 2 1 、近似( a p p r o x i m a t e ) 序列模式挖掘5 3 1 等。 1 2 3 并行序列模式挖掘研究概况 并行数据挖掘领域中，关于并行关联规则挖掘方面的研究起步较早，产生 了许多优秀的算法【3 9 卜【4 4 1 。由于序列模式是关联规则的扩展，因此序列模式的 并行挖掘很快得到了人们的重视。 当前大多数并行序列模式挖掘算法都是对相应串行算法并行化的结果， g s p 算法是序列模式挖掘的经典算法，它的思想自然会扩展到并行序列模式挖 掘中。s h i n t a n i 等人提出了基于g s p 算法的三种并行策略n p s p m 、s p s p m 、 h p s p m t l 7 】。在算法n p s p m 中，候选序列被复制到所有处理器中，每个处理器 利用本地数据库为其计算本地支持度，为了得到其全局支持度，在每次迭代之 后执行一个归约操作。由于n p s p m 在每个节点上复制完整的候选集，这样，对 于大型数据库可能会带来内存溢出问题。s p s p m 将候选集划分成大小相等的块 后分别置于各处理器中。由于s p s p m 利用了系统的聚合内存，这样会导致额 外的通信开销，因为每个处理器的本地数据库不得不被广播到其他所有的处理 器上以得到序列的全局支持度。h p s p m 采用了一个更加智能的策略，一方面 基于h a s h 机制对候选序列进行划分；另一方面，它还减少了所需的通信时间。 因此，相比前面两个算法h p s p m 的性能最好。 g u r a l n i k 等人提出了一类基于树投影技术的并行序列模式算法l l 驯“1 9 】。根据 并行策略，算法可被分为两种，一种是数据并行模式d p f 。在这种机制下，原 始数据库被划分成p 个大小相等的块存于p 个处理器上，每个处理器拥有一个相 同的字典树。各处理器计算本地支持度然后通过通信和归约操作得到各候选序 列的支持度，然后将全局支持度发送到各处理器，并求出第k 层的频繁序列。另 外一种形式是任务并行模式t p f 。首先利用数据并行算法扩展树直到某一层 斛1 ( 胗0 ) ；然后第k 层不同节点被划分到各处理器上一旦初始分配完成，每个处理 器继续产生子树( 子森林) ，其获得了l 匕d p f 更好的扩展性。 z a k i 等人提出了算：去p s p a d e 2 0 】处理共享内存计算机上的序列模式挖掘问 题。该算法采用了如下技术：( 1 ) 使用垂直数据库的数据格式，通过简单时态连 接列举出所有频繁序列；( 2 ) 利用格理论，将原始搜索空间分解成基于后缀的类， 这些类可在主存中被单独处理。这种分解过程在下一层被递归地应用到各个父 类上以产生更小的类；( 3 ) 提出了异步机制，使得处理器工作在不同的类上，处 理器之间无须共享或同步；( 4 ) 为了保证各处理器上的负载均衡，提出了动态负 4 载均衡机制，即任何一个空闲处理器将加入到一个忙碌的处理器上以处理在更 高层形成的类。通过这些技术，算法在减t j 、i o 开销和实现负载均衡方面取得了 较好的效果。 近年来，科研人员开始把并行化技术引入到闭合序列模式挖掘中去，如韩 家炜等人提出的算法p a r c s p t 2 1 】，通过将伪投影分配给不同的处理器以实现并 行化。同时在我国，越来越多的学者也已经涉足并行序列模式挖掘邻域，邹翔 等人提出了分布式序列模式挖掘算法f d m s p t 2 2 1 ，其采用一种异步的方式进行计 算，指定站点统计不同序列的全局支持计数。马传香等人提出了并行序列模式挖 掘算法p m s p l 2 3 】，该算法基于改进的d s g 图，通过剪枝候选集及数据的合理分 布，有效地解决了i o 代价问题。此外文献 2 4 】， 2 5 】， 2 6 也都提出了一系列有 效的并行挖掘序列模式的算法。 1 3 并行计算理论 1 3 1 并行计算机体系结构 并行计算机是由多个处理单元( 以下也称处理器，简称为c p u ) 组成的计算 机系统，这些处理单元相互通信和协作，能快速、高效地求解大型复杂问题【2 。 并行计算机主要可分为两大类：单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o n m u l t i p l ed a t a ) 和多指令流多数据流m i m d ( m u l u t i p l e i n s t r u c t i o nm u l t i p l ed a t a ) 。 ( 1 ) 单指令流多数据流s i m d 对于s i m d 并行机，多处理机在同一时刻执行相同的指令，但数据不同。对 于数据并行类问题，这种计算机能够达到很高的处理速度。s i m d 计算机的主要 代表是阵列处理机1 2 引。 ( 2 ) 多指令流多数据流m i m d 对于m i m d 并行机，多处理机在同一时刻可执行不同的指令，处理的数据 也可以不同。m i m d 多处理机又可以分为：并行向量处理机p v p ( p a r a l l e lv e c t o r p r o c e s s o r ) ；对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 大规模并行处理机 m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) ；分布式共享存储d s m ( d i s t r i b u t e ds h a r e d m e m o r y ) 多处理机和工作站机群c o w ( c l u s t e ro f w o r k s t a t i o n ) 。其中对称多处理 机s m p 和工作站机群c o w 是两类使用比较广泛的并行计算机，本文第三章和 第四章所设计的算法就是分别针对这两类并行计算机的。如图1 1 所示是五种 m i m d 并行机的体系结构，具体介绍如下： 并行向量处理机( p v p ) 典型的并行向量处理机的结构如图1 1 ( a ) 所示。c r a yc - 9 0 、c r a yt - 9 0 、n e c s x 4 和我国的银河1 号等都是p v p 。这样的系统中包含了少量的高性能专门设 计定制的向量处理器v p ，每个至少具有1g f l o p s 的处理能力。系统中使用了 专门设计的高带宽的交叉开关网络将v p 连向共享存储模块，存储器可以每秒 兆字节的速度向处理器提供数据。这样的机器通常不使用高速缓存，而是使用 大量的向量寄存器和指令缓冲器。 i 总线或交叉开关 ( a ) p v p( b ) s 怍 c o ；) m 母 莺簪臻臻 蔺 - | 睡ii 野 - - | 器 ：l 忭网：l 俪司：；一而司：；一而司： 二蛋墅堕二刍口匝杰受因五曲 6 分布式共享存储多处理机的结构如图1 1 ( d ) 所示。s t a n f o r dd a s h 、c r a yt 3 d 和s g i c r a yo r i g i n2 0 0 0 等属于此类结构。d s m 系统就是在物理上分布存储的 系统上逻辑地实现共享存储模型。d s m 和s m p 的主要差别是，d s m 在物理上 有分布在各节点中的局部存储，通过高速缓存目录d i r 支持分布高速缓存的一 致性，从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一 个单地址的编程空间。d s m 相对于m p p 的优越性是编程较容易。 工作站机群( c o w ) 工作站机群的结构如图1 1 ( e ) 所示。b e r k e l e yn o w 、a l p h af a r m 、d i g i t a l t r u c l u s t e r 等都是c o w 结构。在有些情况下，机群往往是低成本的变形的m p p 。 c o w 的重要界限和特征是：1 ) c o w 的每个节点都是一个完整的工作站( 不包括 监视器、键盘、鼠标等) ，这样的节点有时叫做“无头工作站”，一个节点也可以 是一台p c 或s m p ：2 ) 各节点通过一种低成本的商品网络( 如以太网、f d d i 和 a t m 开关等) 互连，有的商用机群也使用定做的网络；3 ) 各节点内总是有本地 磁盘，而m p p 节点内却没有；4 ) 节点内的网络接口是松耦合到i o 总线上的， 而m p p 内的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式 的：5 ) 一个完整的操作系统驻留在每个节点中，而m p p 中通常只是个微核， c o w 的操作系统通常是工作站u n i x ，加上一个附加的软件层以支持单一系统 映像、并行度、通信和负载平衡等。 1 3 2 并行算法基础 ( 1 ) 基本概念 定义1 1 并行算法 2 9 1 ( p a r a l l e la l g o r i t h m ) 是一些可同时执行的诸进程的集 合，这些进程相互作用和协调，以完成对给定问题的求解。 定义1 2 同步并行算法( s y n c h r o n o u sp a r a l l e la l g o r i t h m ) 是指在某一特定时 刻需要与其他的处理机进行数据交换，然后才能继续执行的一类算法。 定义1 3 异步并行算法( a s y n c h r o n o u sp a r a l l e la l g o r i t h m ) 在进行数据交换 不需要严格确定在某一时刻，每个处理机按照预定的计算任务持续执行，但通 常需要在一定的时候必须进行一次数据交换，以保证算法的正确性。 ( 2 ) 并行算法的性能 下面主要介绍度量并行算法性能的一些基本概念及定理。 定义1 4 粒度：是各个处理机可独立并行执行的任务大小的度量。大粒度 反映可并行执行的运算量大，亦称为粗粒度。指令级并行等则是小粒度并行， 亦称为细粒度。 定义1 5 加速比：串行执行时间为瓦，使用拿个处理器并行执行的时间为 昂( 口) ，则并行加速比为昂( g ) = 瓦乃( g ) 。 定义1 6 效率：设g 个处理器的加速比为昂( g ) ，则并行算法的效率昂( g ) = 7 s p ( q ) q 。 定义1 7 性能：求解一个问题的计算量为矽，执行时间为丁，则性o 邑( f l o p s ) 为p e r f = w t 。 在8 0 年代，使用f l o p s 为单位，9 0 年代，使用m f l o p s 和g f l o p s ， 2 1 世纪普遍使用g f l o p s 和t f l o p s ，目前也逐渐开始使用p f l o p s 。 定理1 1a m d a h l 定律：对己给定的一个计算问题，假设串行所占的百分比 为口，则使用q 个处理机的并行加速比为 1 s ，( g ) 2 再若丽 ( 卜1 ) 口+ ij 一口) 口 a m d a h l 定律表明，当g 增大时，昂( g ) 也增大。但是，它是有上界的。也 就是说，无论使用多少处理机，加速的倍数不是能超过1 口。 定理1 2g u s t a f s o n 公式：假设在每个处理机中，串行部分的百分比为口， 则使用q 个处理机的并行加速比为 $ ( g ) = 口+ q ( 1 一口) ( 1 2 ) ( 3 ) 并行算法设计原则【3 0 】 与体系结构相结合 一个好的并行算法应该具备充分发挥并行计算机潜在性能的能力。所以， 要结合具体的并行环境设计有针对性的并行算法。 具有可扩展性 并行算法是否是随处理机个数增加而能够线性或近似线性的加速，这是评 价一个并行算法是否有效的重要标志之一。也就是说，如果一个并行算法的加 速比是s p ( q ) = o ( q ) 或者昂( g ) = d ( q ( 1 + l o g ( q ) ) ) ，则可以称为具有可扩展性的并 行算法。 粗粒度 通常情况下，粒度越大越好。这是因为在每个处理机中有很多需要计算的 工作任务，如此可以充分发挥多处理机的作用。并行加速比对细粒度问题一般 情况下是不会很高的，这也是为什么并行计算需要求解大规模问题的原因所在。 减少通信开销 一个高效率的并行算法，通信是至关重要的。提高性能的关键是减少通信 量和通信次数，其中通信次数通常情况下是决定因素。 优化性能 一个算法是否有效，不仅依赖于理论分析的结果，也和在实现的过程中采 用的技术息息相关。性能主要看单处理机能够发挥计算能力的百分比，然后是 并行效率。 1 3 3 并行程序的实现技术 从编程的角度，可以将所有的计算机系统分成共享内存的计算机( 如s m p ) 和分布式内存的计算机( 如c l u s t e r ) ，相应地可以采用不同的并行编程方式【3 。 目前主要的并行编程模式有：数据并行模式( 如d a t ap a r a l l e l ) ，消息传递模式( 如 m p i ，p v m ) ，共享内存模式( 如o p e n m p ) 以及后两种模式同时使用的混合模式 【32 1 。下面介绍本文在第三章和第四章用到的并行编程接1 2 1o p e n m p t 3 3 】， 3 4 】，【3 5 】，【3 6 】 和m p i l 3 3 ，【3 4 】，f 3 7 j ，【38 1 。 ( 1 ) o p e n m p o p e n m p ( o p e nm u l t i p r o c e s s o r ) 是一套开放的应用编程接口标准，它定义了 如何通过编译器指令( c o m p i l e rd i r e c t i v e s ) ，函数库( 1 i b r a r yr o u t i n e s ) 和环境变量 来为多处理器系统编程，尤其是对称多处理器系统，属于共享内存编程模式。 共享内存并行编程模式的使用相对较为简单，程序员不需要考虑数据在内存中 的位置，进程管理及同步操作均有由系统自动完成。 o p e n m p 通过对f o r t r a n 和c 等传统的串行语言中加入编译制导以指示 程序并行的执行，是基于线程的并行编程模型。一个共享存储的进程由多个线 程组成，o p e n m p 就是基于已有线程的共享编程范例：其次，o p e n m p 是一个 外部编程模型，而不是自动编程模型，它能够使程序员完全控制并行化。对程 序添加制导，使得用户可以逐步的( 逐个循环) 地对串行程序进行分析，将串行 程序增量并行化。 o p e n m p 使用f o r k j o i n 并行执行模型。所有的o p e n m p 程序开始于一个 单独的主线程。主线程会一直串行地执行，直到遇见第一个并行域才开始并行 地执行。接下来的过程如下：1 ) f o r k - 主线程创建一队并行的线程，然后，并 行域中的代码在不同的线程队中并行执行；2 ) j o i n ：当诸线程在并行域中执行 完之后，它们或被同步或被中断，最后只有主线程在执行。 ( 2 ) m p i m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是1 9 9 4 年5 月发布的一种消息传递接1 2 1 。 它实际上是一个消息传递函数库的标准说明，吸取了众多消息传递系统的优点， 是目前国际上最流行的并行编程环境之一，尤其是分布式存储的可缩放并行计 算机和工作站网络以及机群的一种编程范例。m p i 具有许多优点：具有可移植 性和易用性；有完备的异步通信功能：有正式和详细的精确定义。因此，m p i 为并行软件产业的增长提供了必要的条件。 在基于m p i 编程模型中，计算是由一个或多个彼此通过调用库函数进行消 息收、发通信的进程所组成。在绝大部分m p i 实现中，一组固定的进程在程序 初始化时生成，一般情况下，一个处理器只生成一个进程。这些进程可以执行 相同或不同的程序( 相应地称为单程序多数据s p m d 或多程序多数据m p m d 模 式) 。进程间的通信可以是点到点的，也可以是集合的。 m p l 只是为程序员提供一个并行环境库，程序员通过调用m p i 的库程序来 9 达到程序员所要达到的并行目的，m p i 提供c 语言和f o r t r a n 语言接口。 m p i 是个复杂的系统，它包含了1 2 9 个函数( 根据1 9 9 4 年发布的m p i 标准) 。 事实上，1 9 9 7 年修订的标准，称之为m p i 2 ，已超过2 0 0 个，目前最常用的也 有约3 0 个。然而我们可以只使用其中的6 个最基本的函数就能编写一个完整的 m p i 程序去求解很多问题。 1 4 本文研究内容 本文在对以往并行序列模式挖掘算法分析的基础上，针对在两类并行计算 机体系结构下并行挖掘序列模式时遇到的负载、通讯等几个关键问题进行研究， 意在找出有效的解决方案，设计高效的并行序列模式挖掘算法。 ( 1 ) 针对现有算法在共享存储环境下存在的