（计算机系统结构专业论文）面向体系结构的串匹配算法优化研究.pdf

摘要 串匹配算法广泛应用于生物信息学、信息检索等领域。随着基因数据和网络数据的 爆炸式增长，对串匹配算法的性能也提出更高的要求。 本文从计算机体系结构的角度出发，立足于开发串匹配算法的数掘并行性和提高算 法的c a c h e 性能。本文的主要工作包括： ( 1 ) 基于s i m d 指令集的动态规划算法数据并行性开发与实现研究。 动态规划是模糊串匹配和序列联配中的基本算法一类动态规划算法以 s m i t h - w a t e r m a n 算法为代表，计算复杂度为。妒) ；类是以z u k e r 算法为代表，计算复 杂性为o ( n 3 ) 。本文分析了两类动态规划算法的数据依赖关系及其数据并行性。基于前驱 计算思想，优化设计了s m i t h - w a t e r m a n 算法，充分挖掘了算法的数据并行性，并基于 s 1 m d 指令集实现，数倍提高了该算法性能。通过设计辅助矩阵，有效组织数据，优化 设计了z u k e r 算法，对于较大的数据规模，获得了接近理论值的加速比。 ( 2 ) 基于组合字符集的高性能s h i f t - o r 算法研究 s h i f t - o r 算法广泛应用于内容过滤领域。基本的s h i f t - o r 算法以c h a r 类型的字符集合 作为字符集，因而状态转换单位为8 b i t s 。本文通过组合n f a 的状态，建立。上的n f a ， 状态转换单位提高为s h o r t 型整数，显著降低了自动机状态转换次数，提高了计算效率 ( 3 ) 面向位并行的低内存开销高性能关键词表达式匹配算法研究 关键词表达式匹配算法是一类重要的串匹配算法。本文面向位并行，利用f o u x - m s s i a n 和分治等优化方法设计了新的关键词表达式匹配算法，可提高计算效率、降低内存开锖。 关键词：串匹配算法；s i n g ) ；算法优化；位并行 a b s t r a c t o p t i m i z a t i o no f s t r i n gm a t c h i n ga l g o r i t h mb a s e do nc o m p u t e ra r c h i t e c t u r e d a lz i l 肋g h u a ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yf e n g s h e n g z h o n g s t r i n gm a t c h i n ga l g o r i t h mi saf u n d a m e n t a lp r o b l e mi nb i o i n f o r m a f i c sa n di n f o r m a t i o n r o f i a v a l d e s p i t eo fab i ga m o u n to fe f f o r t ss p e n tb yr e s e a r c h e r so nd e s i g n i n ge f f i c i e n ts t r i n g m a t c h i n ga l g o r i t h n ：l ，i m p r o v i n gt h es t r i n gm a t c h i n ge f f i c i e n c y “x n a i i l so f p r i m a r yi m p o r t a n c e , w h i c hi sd u et ot h ed r a s t i cg r o w t ho f g e n ed a t aa n dw e bc o n t e n ta n d c o n s e q u e n t l yt h em o l ea n d m o r ec r i t i c a ld e m a n do nt h ep e r f o r m a n c e o f s t r i n gm a t c h i n g t h i st h e s i sa i m sa ta d d r e s s i n gt h ep r o b l e mo f h o wt oo p t i m i z es t r i n gm a t c h i n ga l g o r i t h m w i t hr e s p e c tt ot h ed m r a c t c d s t i c so fc o m p u t e ra r c h i t e c t t 鸸w h o s ep r i m a r ya i mi st oe x p l o r e i l pa n di m p r o v et h ep e r f o r m a n c eo f d a t aa c c e s s i n gt h r o u g hc a c h e t h em a i nw o r ki sl i m e da s b e l o w ： ( 1 ) r e s e a r c ho ne x p l o i t i n g a n d i m p l e m e n t i n g d a t a p a r a l l e l i z a t i o n o fd y n a m i c p r o g r a m m i n ga n db a s e do ns i m d i n s t r u c t i o ns e t d y n a m i cp 伊扰呲i i i l gi st h eb a s i so fa p p r o x i m a t es t r i n gm a t c h i n ga n ds i i l e n a l i g n m e n t t w om o s tp o p u l a rk i n d so fs u c ha l g o r i t h m sa r ep r e s e n t e di nt h i st h e s i s ：t h eo n ei s r e p r e s e n t e db ys m i t h - w a t e r m a na l g o r i t h mw h o s ec o m p u t i n gc o m p l e x i t yi so ( 1 1 2 ) ；t h eo t h e r i sr e p r e s e n t e db yz u k e ra l g o r i t h mw h o s ec o m p u t i n g c o m p l e x i t yi so ) w ea n a l y z et h ed a t a d e p e n d e n c ya n dd a t ap a r a l l e l i s mo f t h e s et w ok i n d so f d y n a m i cp r o g r a n m 血g t h e nw ee x p l o i t d a t a p a f a l l e l i z a t i o n o fs m i t h - w a t e r m a n a l g o r i t h m b a s e do nt h e t h i n k i n g o fp r e f i x c o m p u t a t i o n , a n di m p l e m e n ti tw i t hs i m di i 咖c 6 s e t w i t ht h eh e l po f t h ea u x i l i a r ya r m y , w eo r g a n i z et h e w a yo f a c c e s s i n gt h ed a t ao f t h ez u k e ra l g o r i t h m , w h i c hc a ng a i nt h es p e e d u p r a t i on e a rt h et h e o r e t i c a lv a l u ew h e nt h ei n p u ts i z ei sb i g ( 2 ) r e s e a r c ho nh i g hp e r f o m m c es h i f t - o ra l g o r i t h mb a s e do nc o m b i n i n gc h a r a c t e r s e t s h i f t - o ra l g o r i t h mi sw i d e l yu s e di ni n f o r m a t i o nr e t r i e v i n ga n d f i l t e r i n g t h eb a s i cs h i f t - o r a l g o r i t h mt r e a t st h es e to f a s c hc o d ea si t sc h a r a c t e rs e t , s oi tl l a n s f e p 3i t ss t a t ew h e nr e a d i n g a n8 - b i td a t a w i t hr e s p e c tt ot h i sp o i n t ，w ec o m b i n et h es t a t e so f n f a , s e t u pt h en f a o nt h e b a s i ce l e m e n t , w h i c hi sr e a dt ot r a n s f e rt h es t a t eo f n f a , a n d i m p r o v ei t ss i z et ot h a to f s h o r t i n t s ot h ef r e q u e n c yo f s t a t et r a n s f e ri sr e d u c e da n dt h ec o m p u t i n g e f f i c i e n c yi se n h a n c e d ( 3 ) r e s e a r c ho nh i g hp e r f o r m a n c ea n dl o wm e m o r yc o s tk e y - w o r de x p r e s s i o nm a t c h i n g a l g o r i t h mf r o mb i tp a r a l l e l i z a t i o n k e y - w o r de x p r e s s i o nm a t c h i n ga l g o r i t h mi s as i g n i f i c a n ts o r to fs t r i n gm a t c h i n g n i a b s t r a c t a l g o r i t h m i ng r o u n do fb i t - p a r a l l e l ，w ed e s i g nt h i sk e y - w o r de x p r e s s i o nm a t c h i n ga l g o r i t h m w i t hf o u r - r u s s i a nt e c h n o l o g yw h i c hc a nr e d u c et h ec o s to f m e m o r y k e y w o r d s ：s e q u e n c ea l i g n m e n ta l g o r i t h m ，s t r i n gm a t c h i n ga l g o r i t h m , s i m d i v p ? l l ， i f - ，o，0i-i。；，；p，!， 图目录 图1 i t2 0 0 0 年到2 0 0 5 年基因数据增k 趋势图一。l 图i 1 2 2 0 0 0 年到2 0 0 5 年我国国际出口带宽增长趋贽图一2 圈2 2 1s w m m x 算法伪码工 l l 图2 2 2 s w m m x 算法数据| | 列方式一一1 2 图2 3 2 1s w s s e 2 算法的数据择列方式一1 5 图2 3 3 1s w s s e 2 算法计算f 向量得伪码，1 7 图z 2 1 简单动态规划算法得数据依赖关系1 8 图2 a 1 第一种计算方法得数据排列方式一1 9 图3 1 1 1 由。g c a g a g a g 构造的n f a 2 2 图3 1 2 ls h f r - o r 算法匹配过程2 3 图3 1 2 2 r e g i s t e r 各位得含义一。2 4 图3 2 1 由。g c a g a g a g 构造的n f a 2 5 圈3 2 2 由“g c a g a g a g 构造的。上得n f a 一“2 5 囝3 2 2 由。c , - c a g a g a 构造的。上锝n f a 2 5 图4 3 1 1 根据动态规划矩阵构造自动机的两种不同方式一3 5 表2 3 4 1s w s s e 2 算法试验结果 表2 4 2 1 测试环境参数表 表目录 表2 a 2 2 标准指令集与s s e 2 指令集实现的简单动态规划算法执行时h j 表2 3 2 3 标准c 实现的简单动态规划算法在o p t e r o n 系统上的c a c h e 性能 表2 3 2 3 基于s s e 2 指令集的简单动态规划算法在o p t e r o n 系统上的c a c h e 性能 表3 3 is h n 7 r - o r 算法与d s h t - o r 算法执行时间 1 7 2 0 2 0 2 0 表3 3 2 s 岍- o r 算法与d s i - i w t - o r 算法c a c i - i e 性能比较。2 7 i x 声明 我声明奉论文是我本人猩咎鲫指导f 进行的研究工佟及取得酶研究成 聚。塔我所知，除了文巾孛孥舅| j j j u 标淀和墩谢豹地方外，本论文中不包含 矮他人。经发农竣撰鬈过鲍研究成聚与我+ 同工你的同丞慰奉研究所傲 的侄研炙献均也在论文巾你，明确纳滋明_ 挎表示了谢意。 作者镶名；戴正罕翻期；矽口，平辱问，矿目 论文版权使用授权书 本人授权巾豳辩学院汁镎技寒研究所可以保留并内图家有荚都门线机 鞫送受奉论文的笈印件零| l 过4 于文耥。允许零论文放霞阅和借阅，町以褥奉 论文豹令鄙政郯分内容编入有关数镶席边i 亍稔索，可以聚用影e | 】、编印或 扫搦等复制手段保存、汇编本论文。 ( 豫密论文在瓣密后适羽本授投任。) 佟者签名栽亚子 第一章引言 作为一类基本算法，串匹配算法广泛应用在生物信息学、入侵检测、信息过滤、数 据库、中文分词等众多领域。高性能串匹配算法研究具有重要的理论意义和应用价值。 1 1 背景 近年来，随着众多生物基因组测序分析项目的完成，基因和蛋白质数据爆炸式增加， 基因组研究迅速发展，对数据的搜集、管理、处理、分析、释读能力的要求迅速提升。 基因数据的总量每1 4 个月翻一番( 如图1 1 1 ) ，而按m o o r e 定律，计算性能每1 8 2 4 个月增长一倍。因此，基因数据的增长，对于高性能算法设计也提出了挑战。生物信息 学中的问题大部分可以转化成串的问题。 图1 1 12 0 0 0 年到2 0 0 5 年基因数据增长趋势图 同时在网络内容分析中，截止到2 0 0 5 年6 月3 0 日，我国国际出口带宽的总容量为8 2 6 1 7 m ， 与半年前相比增加了8 1 8 8 m ，增蚝率为i l o ，和上年同期相比增加5 3 2 ( 如图1 i 2 所示) 【网 络信息2 0 0 5 1 计算机硬件的性能的提升遵循摩尔定律，即每1 8 个月翻一番，已经无法满足高速增 长的网络数据和基因数据对计算机性能的需求。这就对软件的性能提出了更高的需求 无论是生物信息还是网络信息的处理，核心都是串的匹配问题。 中田科学院硕卜位论文面向体系结构的串匹配算法优化研究 1 2 串匹配算法 历次鹚查我茸强际m 口带宪 图1 1 22 0 0 0 年到2 0 0 5 年我国国际出口带宽增长趋势图 1 2 1 串匹配算法基本概念 约定为给定字符集。例如在生物信息学中，e = f a ，g c ，t l 。 定义1 1 给定字符串s ，如果$ = u v w ，t x , v , w ee ，则称v 为s 的子串。 定义1 2 给定字符串s ，如果s = w ，u , v e ，则称v 为s 的后缀。 定义1 3 给定字符串s e ，如果$ = - - v u ，u , v e e ，则称v 为s 的前缀。 定义2 给定两条序列s = - s 1 o s n 和z 1 t m 。那么我们用嘲来表示s 的长度，踟表 示序列s 的第f 个字符。如果序列s 和r 相同，则必须满足： ( 1 ) 、i s i = i t i ； ( 2 ) 、研1 1 = 妇，( o 0 和m 0 和m n ，并任意给定一个i f 整数k ， o = k 辄，从t 中找出所有子串v 发生的位置使得v 满足条件e d i t ( v 2 ) k 。 定义6 序列的联配( a l i g n m e n t ) 两个或多个符号序列按字母比较，尽可能确切地反 映它们之间的相似或相异，称为序列的联配。 2 第一章q i p , - 定义7 ：如果s 和r 是两个序列，那么s 和r 的全局联配( a l i g n m e n t ) a 可以用序 列i 和，来表示，其中： ( 1 ) 、i s l = l ，i ； ( 2 ) 、将j 和，中的空字符除去后所得到的序列分别为s 和n ( 例s = 么c b c d b ， r = “c 口d 6 扩，那么歹；k c b c d b ，t t = - c a d b d j ，) ； 联配就是把序列，和，上下罗列起来，相应的位置进行一一的比较。联配a 的分值 s c o r e 可以用如下的公式来表示： ， 。 s c o r e = a ( s 吼t 。【f 】) i = l 其中f = j j i = j ，b 定义& 对于两个序列s 和l 它们的全局最优联配a 是指在s 和r 的所有相似性 比较中最高分值s c o r e 所对应的排列。 定义9 所谓局部联配是指：给定两条序列s 和l 其中i s i - n ，i t i = m ，设d 为s 的一个连续的子序列，b 为r 的一个连续的子序列，找出这样的子序列q 和b ，使得d 和b 的相似度是s 和r 中所有的这样的子序列的相似度的最大值。即，a 和b 的相似度 不小于s 中其它的子序列a 和r 中其它的子序列雪的相似度。 定义l o 如果j 和y 是两个任意的字符，那么a ( x , y ) 表示字符工和y 在进行比较时 所得的分值，称为一个记分函数。记分函数包括了当x 为空字符或y 为空字符的情况， 1 在序列中一个所谓的空字符表示序列在此位置可能缺失了一个字符，我们用“一”来表 示这种缺失在不同的算法当中，记分函数可以有不同的记分方法。例如可以这样定义 记分函数：a ( x , x ) - - + 2 ，o r ( x , 力= 盯- ) = 盯( - y ) = - - 1 。 ： 定义1 1 空位处罚空位是指在某一排列的单个序列中，任意连续的尽可能长的空 格空位的引入是为了补偿那些插入或缺失，使序列的排列能更紧密地符合某种所期望 的模型。空位的长度是指在空位中i n d e l 的个数。在序列中空位的数目用拌g a p s 来表示， 所有空位中空格的数目( i n d e l 操作的数目) 用# s p a c e 表示每引入一个空位，联配的分 值都会有所扣除。 对于这些空位有很多罚分的规则，常见的罚分规则主要有两种： 恒定空位权值模型 这是最简单的一种规则，每个空位中的空格的分值设为零，即对任意的x ，s ( 一，x ) - - - - - s 代一) = 0 。这样联配的相似度就为： ， ：e m s p 】，t f 】) + x ( 撑罟q f 峪) 其中s 和t 分别为s 和t 加入空位后的序列，l s i = i t i = l ，w g 为开放一个空位的 罚分。 仿射空位处罚模型( a f f m eg a pm o d e l ) 这是最常用的一种罚分规则。空位处罚函数依赖于空位中空格的数量：用一个附加 3 中国科学院顿l 。学位论文由向体系结构的串匹配算法优化研究 的罚分比例去乘空位的长度，其中有两个参数，w g 表示空位开放处罚，w s 表示空位延 伸处罚。仿射处罚函数可表示为：w g + q x w s ，q 表示某一个空位的长度。这样联配的 相似度就为： ， a ( s 【f 】，t 【哪+ x ( # g a p s ) + 睨x ( # s p a c e ) t = l 1 2 2 串匹配算法 串匹配算法可以分为两大类，精确串匹配算法和模糊串匹配算法。精确串匹配算法 又可分为多模式串匹配算法和单模式串匹配算法。 单模式串匹配算法大致可分为四类：滑动窗口算法，自动机算法，计数算法和h a s h 算法。但这四类划分不是严格的，例如在滑动窗口算法中经常用到后缀自动机来确定窗 口跳跃的距离。 滑动窗口算法的基本思想是根据当| ； 窗口的匹配情况确定下一窗口的位置，这类算 法有叭算法【b o y e r1 9 7 7 】以及b m 算法的各种改进算法 h o r s p o o l1 9 8 0 1 s u n d a y 1 9 9 0 】【s m m i1 9 9 1 】，利用自动机确定跳跃距离的算法b o m 算法、b a w g 算法等。此类 最差时问复杂度为o t m n ) ，最好情况下时间复杂度o ( n m ) ，平均时间复杂度为o ( n m ) 【m i k l i d d e l l1 9 9 7 】。 他们共同的特点是采用自右向左、跳跃滑动的策略。问题的关键在于如何用最短的 时间计算出最长的跳跃距离。如果设t j 为计算跳跃距离所需的时间，s j 为计算出的跳 跃距离，则问题在于如何使得s j t j 的值最大。依此标准可大致判断出该类算法的优劣。 自动机类算法首先根据模式串构造自动机，然后扫描文本串，驱动自动机运行，到 达终态表明发现匹配字符串。此类算法主要有：基于确定性自动机的算法 c r o c h e m o r e1 9 9 7 】、k m p 算法【k m 删1 9 7 7 】基于非确定性自动机的算法 s h i r - o r 算法【、7 i ，ua n dm a n b e r1 9 9 2 】。此类算法时间复杂度为o ( n ) ，空间复杂度为 o ( m l e o 。自动机的存储是困扰该类算法的一个重要问题。 计数算法的时间复杂度与模式串字符的重复率成正比，当模式串中的所有字符均不 同时，时间复杂度为o ( f 1 ) 。当模式串字符重复率较高时，用s i m d 指令集可以加速该算 法此类算法应用面较窄，但是能方便地应用到k 误配串匹配中，这是该算法的一个显 著优点。 h a s h 算法的时间复杂度理论上为o ( n ) ，其关键在于构造好的h a s h 函数，既简单又 能显著降低冲突，从而提高其性能。 多模式串匹配算法可分为三类：跳跃类算法，自动机类算法，h a s h 类算法。在思想 上，各类算法与单模式串匹配算法类似，时埘复杂度也类似。 跳跃类算法【w m l 9 9 4 】( w m 算法) 、s b o m 算法首先截取各个模式串使得得到的 模式串等长，然后根据模式串集合建立跳跃数组。扫描时根据跳跃数组移动窗口。 4 i 。 第一章引言 自动机类算法 a c l 9 7 5 】首先根据模式串集合建立自动机，随后的过程类似于单模 式串匹配算法。 h a s h 类算法一般要经过两次h a s h 才能确定是否有候选匹配项发生。 模糊串匹配算法可分为三类：动态规划算法，自动机算法，过滤算法。 简单的动态规划算法时间复杂度为o ( m n ) ，是模糊串匹配的一类核心算法。动态规 划矩阵各元素之间的数据依赖关系限制了该算法的并行性。 模糊串匹配算法中的自动机与精确串匹配中的自动机有很大不同。模糊串匹配算法 中确定性自动机的状态数目多到严重影响到算法的性能，因此，模糊串匹配算法多采用 非确定自动机。基本的非确定自动机类算法复杂度为o ( h n n ) 。 过滤类算法首先将模式串分解成数个子串，然后按多模式精确匹配算法查找分解得 到的子串，获得候选位置，然后对候选位置执行动态规划算法计算相似度。 1 3 体系结构对算法的影响及算法优化 程序的性能与计算机体系结构密切相关。本文只考虑单机体系结构对程序性能的影 响。直观地看，要想提高程序的性能，需要在两个方面下功夫：尽可能多地执行指令、 尽可能早地执行指令。这就是面向现代体系结构算法优化地两个方面：i l p 优化和存储 优化，这主要涉及计算机系统地两大部分：c p u 和存储系统。 i l p 优化 i l p 优化的出发点是增大程序中可并行执行的操作的数目，尽可能将程序的资源需 求与机器提供的资源弥合，其原则是减少和消除数据与控制相关。具体的方法有：循环 展开、过程嵌入、软件流水、s u p e r b l o c k 、h y p e r b l o c k 、t r a e es c h e d u l i n g 、值预测等。在 对算法进行优化之前，首先要了解计算机系统的体系结构特征。 处理器作为计算机的核心部件一直被给予最大的关注，为了达到单机的高性能，很 多体系结构上的新技术被芯片的设计者广泛采用。其中，最常用的有超标量技术、超长 指令字技术、超流水线技术、乱序执行、同时多线程技术、向量i r a m 技术、单芯片多 处理器技术，超传输技术等等。此外还有一些最新推出的技术，如i n t e l 在x e o n 和p 4 中采用的超线程技术、m m 的双核芯片技术等等。提高应用程序的性能很重要的一点是 如何最大限度的发挥处理器的利用率，充分利用处理器中的各项技术。处理器中不同的 技术对程序性能的影响的幅度和方式有所区别，有些是对程序员透明的，不要程序员做 任何工作；有些虽然透明，但可以通过调节程序以充分利用这些技术；有些则是针对程 序的特点来改变软硬件环境的设置，从而提高性能。 使用s i m d 技术 b o u k n i g h t1 9 7 2 l e e 9 9 5 是现代体系结构的一个重要特征 s i m d 技术通过增加指令中完成的操作数、减少完成一个任务或程序所需的指令条数来 提高处理器的性能。普通指令同时只能执行一次计算，所以虽然处理器是由许多个a l u 构成，但这却并不能加快它的计算速度，因为只有一个a l u 处于工作状态，无法充分 5 中陶科学院颀l ：学位论文面向体系耋 l 构的串匹配算法优化研究 利用处理器中的计算资源。为了改进这种情况，各个处理器生产公司都推出了单指令多 数据( 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 ，s i m d ) 扩展架构的c p u 。如i n t e l 公司引入了 m m x ( m u l t i m e d i ae x t e n s i o n ) 、s s e ( s t r e a m i n gs i m de x t e n s i o n s ) 和s s e 2 指令集l i n t e l v l 】 i n t e l v 2 1 i n t e l v 3 】，a m d 的3 d n o w ! ( 3 d n o w a i t i n g ) 指令集 a m d i 】 a m d 2 a m d 3 】，m m 的a l t i v e c 【a l t i v b c 】，s u n 的图像指令集( v i s u a li n s t r u c t i o ns e t ，v i s ) 等等龙芯也有自己的多媒体指令集 g o d s o n i 。 【c z n 2 0 0 4 】的测试表明，使用s s e 2 指令集的l i n p a c k 测试要比未使用s s e 2 指令 集的l i n p a e k 测试性能提高近9 0 。 s w m m x 算法利用m m x 指令集加速s m i t h - w a t e r m a n 算法，一般情况下能获得6 倍的加速比。 用位并行的方法模拟非确定性自动机，可以获得w 倍的加速比，w 为机器字长。 存储优化 c p u 主频的提升带动了系统性能的改善，但系统性能的提高不仅仅取决于c p u ， 还与系统架构、指令结构、消息在各个部件之间的传送速度及存储部件的存取速度等因 素有关。特别是与c p u 与内存之间的存取速度有关。与飞速发展的c p u 主时钟频率相 比，作为主存储器主要器件的d r a m 已成为高速计算机的主要瓶颈，而且c p u 和主储 器之间的速度差距仍在不断扩大【w i l l f l 9 9 5 】。因此，充分利用存储层次结构的特点i c u r t s e h i m m e l l ，提高数据局部性，是提高应用程序的性能的重要途径。 存储优化的软件方法分为三大类：容忍c a c h e 不命中延迟；优化存储带宽利用；减 少访存或减少c a c h e 不命中数。 容忍c a c h e 延迟的方法有指令调度、软件预取 a n e e s h2 0 0 1 】等。 优化存储带宽利用的存储优化方法的思想是：只将程序使用频繁的数据调入c a c h e 。 其方法有编译时的c l u s t e r i n g 方法和着色方法，部分c a c h e 局部性方法【李明1 9 9 7 】 减少访存的优化方法有：寄存器优化、数组收缩 g e 0 2 0 0 2 、标量替换。 降低c a c h e 缺失率的方法有：优化程序的空间局部性、优化程序的时间局部性和减 少c a t , h e 冲突。按技术手段可分为循环变换、数组变换和数组p a d d i n g 【车永刚2 0 0 4 】。 i n i s h i m u r a2 0 0 1 】通过重新排列a c 自动机状态在内存中的排列顺序，提高了g a c h e 命中率。可以获得一倍左右的加速比。 。 s t e p h e n 通过寄存器优化来优化b f 算法，可以获得一倍以上的加速比。 i n a t h a n 2 0 0 4 通过压缩存储a c 自动机的查询表，降低内存消耗，同时大幅降低 了c a c h e 缺失率，最终可以获得3 倍的加速比。 1 4 面向体系结构串匹配算法优化的主要挑战 优化串匹配算法受串匹配算法本身i l p 的限制。 动态规划算法中，动态规划矩阵每个单元都依赖于它左、上、左上三个元素的值， 6 第一章引等 从而严重限制了该算法的数据并行性，消除或减弱或规避这种数掘依赖关系是提高该算 i l p 的关键。 自动机类算法，当前状态直接依赖于上一个活动状态，导致扫描文本时只能依次读 取一个字符并进行状态转换然后读取下一个字符。算法中数据的依赖关系较强，导致无 法直接并行化。 1 5 本文的贡献 本文的主要贡献如下； ( 1 ) 基于s i m d 指令集的动态规划算法数据并行性开发与实现研究。 本文分析了两类动态规划算法，s m i t h - w a t e r m a n 算法和z u k e r 算法的数据依赖性及 其数据并行性。基于前驱计算思想，优化设计了s m i t h - w a t e r m a n 算法，充分挖掘了算法 的数据并行性，并基于s i m d 指令集实现，数倍提高了该算法性能。通过设计辅助矩阵， 有效组织数据，优化设计了z u k e r 算法，对于较大的数据规模，获得了接近理论值的加 速比 董 ( 2 ) 基于组合字符集的高性能s h i f t - o r 算法研究 ， 本文通过组合n f a 的状态，建立。上的n f a ，状态转换单位提高为s h o r t 型整数， 显著降低了自动机状态转换次数，提高了计算效率。 。 ( 3 ) 面向位并行的低内存开销高性能关键词表达式匹配算法研究 本文面向位并行，利用f o u r - r u s s i a n 和分治等优化方法设计了新的关键词表达式匹配 算法，可提高计算效率、降低内存开销。 ； 1 6 论文的组织 第一章中论述了串匹配算法的应用背景及串匹配算法和算法优化的基础知识，明确 了本文的工作方向。 第二章介绍了基于s i m d 指令集的动态规划算法优化，实现了基于s s e 2 指令集的 s m i t h - w a t e r m a n 算法和z u k c r 算法。 第三章研究介绍了单模式精确串匹配算法s h i f t - o r 的优化。 第四章分析了关键词表达式匹配算法的研究现状，并提出了基于f o u r - r u s s i a n 技术 的算法。 第五章总结本文的研究成果，并提出了进一步工作的展望和设想。 7 第二章基于s i m d 指令集的串匹配算法优化研究 本章主要讨论对串匹配算法中的动态规划算法的优化。动态规划对模糊串匹配算法 有深远的影响，形成串匹配算法的一个基础类别。s m i t h - w a t e r m a n 算法和r n a 二级结 构预测的z u k e r 算法都是动态规划算法，有着不同的特征，同时又都是生物信息学的基 础算法。本章讨论这两类动态规划算法的数据并行性。 2 1s m i t h - w a t e r m a n 算法 最早在序列的联配问题中引入动态规划思想的是n e e d l e m a n 和w u n s c h ，并且利用 这种技术，提出了n e e d l e m a n - w u n s c h 算法 n e e d h x n a na n d w u n s c h1 9 7 0 b 】，解决了序列 全局联配的问题；在此基础上，s m i t h 和w a t e r m a n 提出用于局部联配的s m i t h - w a t e r m a n 算法 s m i t h - w a t e r m a n1 9 8 1 】，g o t o h 【1 9 8 2 和m y e r s 【1 9 8 8 又在这些算法的基础上 进行了时间和空间的改进。 序列联配算法算法主要有两部分组成 m a r t i n2 0 0 0 1 【r o n2 0 0 1 】：( 1 ) 计算所给两个 序列相似分值，得到一个相似度矩阵( s i m i l a r i t y m a u - i x ) ，也称作动态规划矩阵或得分矩 阵；( 2 ) 根据相似度矩阵，回溯寻找最优的联配。我们主要考虑第一步。 给定两个序列s 和t ，其中i s i = n ，i t l = m ，定义矿a 力为子序列s 【1 】s 【i 】和 可l 】t d 】最优联配的分值。v ( i j ) 的计算公式如下： 前提条件： r ( o ，o ) = 0 v ( i ，o ) = v ( i 一1 ，o ) + 盯( s t 妇，- ) ( 2 - 1 ) r ( o ，力= v ( o , j - 1 ) + 仃( _ 研f 】) y ( o ) 表明序列s 中的每一个字符都和t 中的空格相匹配，v ( o ，力与v ( i ，o ) 类似 递归关系： l y o 一1 ，一1 ) + 盯( 研f 】，砸，】) 矿( f ，_ ，) = m a 刈 g ( i - l ，d + 盯( 研f 】- )，l i n ，l j m ( 2 - 2 ) l以- ，一1 ) + 盯( - 刀) 在相似度矩阵中，任意一个元素的分值瞰力依赖于其它的三个元素的分值：、左 上角的元素r ( i 一1 , j - 1 ) ：、左边相邻的元素v ( i , j 1 ) ；上一行相邻的元素v ( i - l , j 3 对全局联配动态规划的基本策略稍作修改可以应用到局部最优联配的算法之中这 种联配的路径不需要到达搜索图的尽头，只需要在内部开始和终结。如果某种联配的分 值不会因为增加或减少联配的数量而增加时，这种联配就是最佳的。这个过程依赖于记 分系统的性质：因为某种路径的记分会在不匹配的序列段减少。当分值降为零时，路径 9 中固科学院顾卜学位论文血向体系结构的串匹配算法优化研究 的延展将会终止，一个新的路径就会产生。这样就会得到许多独立的路径，它们以不匹 配的序列段为界限。在这些路径中拥有分值最高的一个就是最佳的局部联配。 前提条件： v ( i ，0 ) = o ； v ( o ，j ) = 0 ； 递归关系： f o 附舻删 v ( i 矿- ( f 1 , - l j - 卅1 ) + o 仃 ( ( 刚s i , 广t ) j d 【 矿( f ，_ ，一1 ) + 仃( - ，_ ，】) 1 i n ，l 专m( 2 3 ) 找出i t 和r ，使得： 喇，) 2 ，。鼎x 。m ，) 公式( 2 - 3 ) 与前面介绍的全局联配中的递归公式( 2 - 2 ) 的准一不同之处是；在1 l l a x 函数 中添加了一项“0 ”，该公式所表示的四种可能情况是：( 假设最优联配a = ( a ，b ) ，其中a 、 8 分别为序列s 1 】s 【i 】和t 1 】t 圃的后缀。) a = ? 、b = ? ，则此时联配a 的值为0 ； a 、8 = ，且联配a 最后的匹配为( s 【i 1 ，t d 】) ，则此时联配a 的值为 v ( i - i j - l ( s f i 】，t d 】) ； a 九，联配a 最后的匹配为( s 【i 】，一) ，则此时联配a 的值为v 聒l j 灿( s 【i 】，一) t b ，联配a 最后的匹配为( 一，t 【j 】) ，则此时联配a 的值为v ( i j 1 ) _ 怊( 一，t d 】) ； 在m a x 函数中加入“0 ”选项是为了确保在计算中丢弃分值为负的前缀。计算完相 似度矩阵，并且找到最大值( i 宰，j + ) 后，最优联配a 和b 可利用回溯算法从旷，j ) 开始直 到选项( i ，j ) ，其q n i ，j ) = o o 这样局部最优联配a 和b 分别为s 【i 1 s i + 】和t 【j 】t d + 】 2 2 基于指令集的s m i t h - w a t e r m a n 串匹配算法优化现状 基于指令集的优化主要应用在模糊串匹配算法中。主要集中在利用s 巧a _ d 指令集开 发算法的数据并行性。 a l p 咖e ta 1 【1 9 9 5 提出了一种在i n t c lp a r a g o ni 8 6 0 处理器种利用6 4 位指令并行 化s m i t h - w a t e r m a n 的方法，他将6 4 - b i t 的z - b u f f e r 寄存器分成四个不同的部分。利用这 种方法，可以将一条查询序列与四条库序列同时进行比较，他们的试验结果表明同传统 方法相比可以获得5 倍的加速比。 w o z n i a k 【1 9 9 7 】利用v l s i 】l a li n s t r u c t i o ns e t ( v i s ) 技术( s u nu l t r a s p a r c 微处理器) 实现了s m i t h - w a t e r m a n 算法，同使用普通指令集相比可以获得2 倍的加速比。 r o g n e s 【2 0 0 0 】利用i n t e l 的m m x 指令集设计实现的s