（计算机应用技术专业论文）基于嵌入式异构多核的信息检索硬件加速实现.pdf

浙江大学硕士：学位论文 摘要 摘要 随着计算机技术和互联网技术的发展，信息检索已经成为一项重要的技术， 在各个领域都有着广泛的应用。因此，对信息检索进行硬件加速以提高计算效率 就成为了一个重要的研究方向。随着集成电路技术的发展，多核处理器尤其是异 构多核处理器逐渐成为计算机发展的主流，为信息检索技术提供了一个很好的平 台 传统的方法采用并行计算对信息检索进行加速，往往通过增加处理器的数目 来提高并行度。另外一类定制方法是设计a s i c 加速器，针对特定应用和特定算 法进行加速。这些方法或者不能把定制核与通用核合成，或者不能灵活的运用于 各种信息检索计算，不能有效地将a s i c 技术与多核技术合成。基于这些研究现 状，本文对使用异构多核体系结构束加速信息检索计算进行了探索和研究。 本文研究了单主核多辅助核的异构多核体系，其中主核使用p o w e r p c4 0 5 ， 而辅助处理核则是针对信息检索计算而定制的。本文针对信息检索计算设计了一 个1 2 8 位并行度专用处理核，以及一套专用、高效的r i s c 指令集。在该指令集 中，还提供了s i m d 指令，在关键字序列小于1 2 8 位时，进一步提高并行度。为 了提高辅助核的吞吐能力，辅助核使用本地存储器进行数据读写，并且针对信息 检索设计了特殊的数掘存储方式，以及灵活的组织形式。 本文还描述了使用自定义的指令集进行信息检索操作的编程模型，以及进行 最基本的信息检索操作时，从数据的分配，l s ( 本地存储器) 的组织，到系统运 行、结果分析的整个计算流程。作为进一步的扩展，本文还给出了多辅助核以及 多系统情况下的设计模型。 本文在x i l i n xv i r t e x 4m l 4 0 3 开发板上实现并验证本系统，并且通过几组不 同应用的信息检索计算进行测试，与通用处理器进行了比较。从测试的结果可以 看出来，在同样不考虑软件算法的情况下，本系统比起通用处理器来说，取得了 7 1 3 倍的性能提升。 由测试结果可以看出，本文所提出的异构多核信息检索加速系统是具有正确 性和先进性的。 关键词信息检索，异构多核，硬件加速，s i m d ，嵌入式系统 浙江大学硕上学位论文 a b s t r a c t a b s t r a c t a l o n gw i t ht h ea m a z i n gd e v e l o p m e n to ft h ec o m p u t e ra n di n t e r n e tt e c h n o l o g y , i n f o r m a t i o nr e t r i e v 0 1 ( i r ) h a sb g c o m eak e yt e c h n o l o g ya l m o s ti no l la s p e c t so fo u r l i r e a c c o r d i n g i xh o wt ob e t t e rt h ep e r f o r m a n c eo ft h e 瓜t h r o u g hi m p r o v i n gt h e e 街c i e n c yo fh a r d w a r eh a sb e e nr o g a r d e da sas i g n i f i c a n tr e s e a r c hd i r e c t i o n i n c o m p a n yw i t ht h ep r o g r e s so ft h ei n t e g r a t ec i r c u i tt e c h n o l o g y , t h ec h i pm u l t i p r o c e s s o r , e s p e c i a l l yt h eh e t e r o g e n e o u sc h i pm u l t i p r o c a s o rw h i c hp r o v i d e sap e r f 鳅p l a t f o r mf o r t h ei rt e c h n o l o g y , h a sg r a d u a l l yb e c o m et h em a i n s t r e a mo f t h ec o m p u t e rd e v e l o p m e n t t h cr e l a t i v e l yt r a d i t i o n a lw a y , w h i c ha d o p t st h ep a r a l l e lc a l c u l a t i o na r i t h m e t i c 。 h s u a l l ya c c e l e r a t e st h es p e e do f i rb vi n c r e a s i n gt h en u m b e ro f p r o c e s s o r m e a n w h i l e , d e s i g n i n gt h ea s i ca c c e l e r a t o rt os u i ts p e c i f i ca p p l i a n c ea n dc a l c u l a t i o na r i t h m e t i c p r o v i d e su sw i t h 柏o t h e ra l t e r n a t i v e h o w e v e r , t h e s em e t h o d se i t h e l f h i lt oc o m b i n e c u s t o m i z e dc o r ea n dg e n e r a lc o r e , o rf a i lt oa p p l yt od i f f e r e n tw a y so fi r b a s e do n t h i s t h i st h e s i st r i e st oe x p l o r et h ep u s s i b i l i t yo fa c c e l e r a t i n gt h es p e e do fmv i at h e h e t e r o g e n c o u sc h i pm u l t i p r o c c s s o rt e c h n o l o g y 1 强st h e s i sm a i n l yf o c u s e so 1t h es y s t e mo fas i n g l em a i nc d w o r k i n gw i t l l s e v e r a ls y n e r g i s t i cp r o c e s s i n ge l e m e n t s ( s p e s ) 1 1 1 cm a i nc o r ei sap o w e r p c4 0 5a n d t h es p e sa r es p e c i a l l yc u s t o m i z e df o rt h ec a l c u l a t i o n0 f 取i no r d e rt oa c h i e v ea l l a c c u r a t er e s e a r c hr e s u l t ，t h ea u t h o rh a sd e s i g n e da1 2 8 - b i tp a r a l l e lc o r ea n dar i s c i n s t r u c t i o ns e tw i t ht h es e v e r a ls i m di n s t r u c t i o n si n s i d e w h i c hc a ng r e a t l ye n h a n c e t h ee f i i e i e n e yo fi i lw h e nt h ek e yw o r d ss e q u e n c ei sl e s st h 锄1 2 8b i t s i fn e c e s s a r y , t h es p e sc a l lm a k eu s eo ft h el o c 0 1s t o r a g e ( l s ) t oi n c r e a s et h e i rc a l c u l a t i o nc a p a c i t y i na d d i t i o nt ot h i s ，as p e c i a lm o d eo fd a t as t o r a g ea n daf l e x i b l eo r g a n i z i n gf o r mh a s a l s ob e e nw o r k e do u t t 1 l i st h e s i sd e s c r i b e sap r o g r a mm o d e lo fr e t r i e v i n gi n f o r m a t i o nb ym e a n so ft h e u s e r - d e f i n e di n s t r u c t i o ns e t 。n 玲t h e s i s0 1 s og i v e st h er e a d e r sad e t a i l e dd e s c r i p t i o no f t h ew h o l ep r o c e s so fi r , i n c l u d i n gt h ed i s t r i b u t i o no fd a t a , t h eo r g a n i z a t i o no ft h el s ， t h es y s t e mo p e r a t i o na n dt h ea n a l y s i so ft h ec a l c u l a t i o nr e s u l t ad e s i g nm o d e lu n d e r t h ec i n 姗s t 柚c eo fm u l t i a s s i s t a n t - c o r ea n dm u l t i - s y s t e mi sa l s oo f f e r e da saf u r t h e r e x t e n s i o n t i l i st h e s i sa t t e m p t st oc a r r yo u ta n dv e i l f yt h eh e t e r o g e n e o u sc h i p m u l t i p r o c e s s o rt e c h n o l o g ys y s t o mb a s e do nt h ex i l i n xv i r t e x 4m l 4 0 3d e v e l o p m e n t p l a t f o r m t h er e s e a r c hf i n d i n g sh a v e b e e nt e s t e di nd i f f e r e n tw a y sa n dc o m p a r e dw i m t h eg e n e r a lp r o c e s s o r a c c o r d i n gt ot h er e s u l to ft e s t , t h i ss y s t e mc a ne n h a n c et h e p e r f o r m a n c eo fp l o o 陷s u rb y7t 0 1 3t i m e sw i t h e u tr e g a r dt o t h ed i f f e r e n c eo f c a l c u l a t i o na r i t h m e t i c i nc o n c l u s i o n ，t h es y s t e mo fh e t e r o g e n e o u sm u l t i - c o r e t e c h n o l o g yi sa l le f f i c i e n tw a y t oi m p r o v et h es p e o da n dq u a l i t yo f 瓜 k e y w o r d s i n f o r m a t i o nr e t r i e v a l ，h e t e r o g e n e o u sc h i pm u l t i p r o c e s s o r , h a r d w a r e a c c e l e r a t i o n ，s i m d ，e m b e d d e ds y s t e m 浙江大学硕上学位论文 图目录 图目录 图2 一l 超标量，多处理器，超线程，超线程的多处理器资源利用率比较l 图2 - 2h y d r ac m p 体系结构l 图2 3i n t e lc o r ed u o 体系结构。1 图2 - 4c e l l 体系结构示意图1 图3 - 1 异构多核信息检索硬件加速系统体系结构示意图l 图3 _ 2 比较指令示意图1 图3 - 3p o w e r p c 指令集操作码示意l 图3 - 4p o w e r p c 指令集寄存器地址示意l 图3 - 5 处理执行单元设计图。 图3 - 6 硬件串行加法器。1 图3 - 7 硬件华莱士树加法器l 图3 - 8l s 的寻址单元1 图3 9 基本匹配算法l 图3 - 1 0 结果处理算法1 图3 一l1 多辅助核扩展l 图3 - 1 2 多辅助核扩展下的任务分配算法1 图3 - 1 3 多系统扩展示意图1 图4 1x i l i n xv i r t e x - 4m l 4 0 3f p g a 开发板外观。l 图4 - 2 使用e d k 的i p 核总线连接图1 图4 3 汇编器框架图1 图5 1 本测试中l s 的组织1 图5 - 2 测试结果示意图l 图5 3 加速比柱状图 v 浙江大学硕十学位论文 表目录 表目录 表3 一l 辅助核寄存器列表。l 表3 2 指令集和操作码规则1 表3 3 指令集中指令的使用频率统计。1 表5 1 测试代码特征。l 表5 2 测试结果 表5 3 加速比1 v l 浙江大学硬上学位论文第1 章绪论 第1 章绪论 1 1 课题榴美背景 1 1 1 处理潞的发展 t 9 4 6 年，第一台全自动墩子数字计算枫e n i a c ( e l e c t r o n i cn u m e r i c a l i n t e g r a t o ra n dc a l c u l a t o r ，繇毫予数字积分器黧谤葵嚣) 瓣整l n ，蠡恚整诗雾撬辩霞 的到来。在以露的4 0 多年囊，诈舞钒技术发展器鬻遂速，在人类秘技史上还没 有一种学科可以与计算机技术的发展速度相比。 1 9 4 7 筇1 2 月，贝尔实验爨的威廉肖克利( w i l l i a ms h o c k l e y ) 、约翰巴丁 ( j o h nb a r d e e n ) 和沃特布拉蜒( w a l t e rb r a t t a i n ) 发明了世界上第一个照体管翻。 1 9 5 8 每趋，圣 算援拜戆采建器体管撵建主要蠡孽逻瓣器佟，产生7 第二我谤舞枫诩。 同年，德髑仪器公司豹杰竞萋容疆：( j a c ks k i l b y ) 淡示7 煎器上蒸一块集成电 路f ，l 。从1 9 6 4 年起的第三代计髯机歼始采用集成电路技术，这使得计算机的体积 大大缩小，性能却更高【i 】。 英特尔公司的创始人之一戈援摩尔( g o r d o nm o o r e ) 于1 9 6 5 馨4 月在 ( e l e c t r o n i c s 杂恚上对未来i o 年中半导体产业的发震做出了如下预测；“微芯 冀上集成豹菇俘管数嚣每1 2 令秀翻一番”残。磊来寨戏毫踌技术滚及徽麓覆器静 发展却很好地骏证了这一说法，教人们称之为摩尔寇律。后来表述为“集成电路的 集成度每1 8 个月或2 4 个月翻褥卯。这些表述并不十分精确，但近几十年来半 导体技术的确是大体按照这样个较高的指数规律麓展的。 当自g 集成电路靛发展已经进入特大规模( 千万个以上元器彳牛) 的阶段，目静 蓬骣主流玺产王艺鼓拳基经弱了粥绣来，班及酷缝张。2 0 0 7 年l 莠癜荚耪笨囱 全球发布了帮将于2 0 0 7 年下半年鬃产1 5 款4 5 缎米徼处理器的清惠。板攘美霉 半导体工业协会( s t a ) 发表的阐际半导体技术路线图( 1 t r s ) 中的预测，到2 0 1 6 年，处理器的线宽将达到2 2 r i m 以下，时钟频率将接近3 0 g h z l 6 。然而，可加工 的器件尺寸将逐渐缩小，最终达剿个物理极刚日。 力了追求受嘉熬性能，处联器瓣设谤越来越复杂。越嚣量( s u p e r s c a l a r ) 、熬 序弧行( o u t - o f - o r d e r ) 、萃指令流多数据滚( s i m d ) 、超长指令字( v l i w ) 、深 流水线等等技术的使用，大大提高了c p u 的主颏和熬体性能，增强了浮点、矢量 运算、多媒体等的处理能力【s 1 。比如i n t d 奔腾4 处理器的流水线已经然剿2 0 多 浙江大学硕士学位论文第1 章绪论 级【9 】。 而晶体管密度的提高以及这些复杂的处理器设计技术虽然使性能有了一定 的提升，但同时也使得芯片的发热量越来越大，晶体管的电流泄漏也越来越严重， 芯片的控制逻辑越来越复杂，已经很难在现有的工艺和技术上再有新的突破【加】。 为了能够进一步提升处理器性能，使摩尔定律继续有效，必须寻找新的体系结构 设计思想和发展方向。在这种背景下，出现了多核技术，并且成为今后计算机发 展的主流趋势。 1 1 2s o c 与f p g a 技术 随着微电子工艺的发展，器件运行速度越来越快。芯片与芯片之间的延迟成 为了限制系统性能的瓶颈之一。而芯片集成度的提升使得人们可以把整个系统集 成在一个芯片上。这就是系统芯片( s y s t e m - o n - c h i p ，又叫片上系统) 技术，简 称s o c 技术。最早的s o c 系统是1 9 9 4 年m o t o r o l a 公司发布的f l e xc o r e t m 系纠l i 】。现在s o c 技术已经成为广泛的应用于各个领域。 s o c 技术可以在一块芯片上集成处理器，存储器以及一些外设控制器，这些 器件通过芯片内部的高速总线进行连接。在s o c 技术的核心是m 核复用技术。玲 核是指知识产权核( i n t e l l e c t u a lp r o p e r t y ) ，是一种预先设计好，已经过验证，具 有某种确定功能的集成电路、器件或部件。使用口核可以大大提高s o c 设计的 效率现在的s o c 的设计多采用软硬件协同设计，先对系统功能进行软硬件划分， 然后对软硬件进行协同设计。软硬件在设计早期就进行结合，相互支持，联合测 试。这种方法能够充分利用现有的软硬件资源，缩短系统开发周期、提高系统性 能、降低成本，避免了传统设计方法中分别设计软硬件，最后再集成的方法所带 来的种种弊端。 s o c 技术的优点在于整个系统都整合在一块芯片上，体积和重量都大幅减小， 并且讯号都采用芯片内部的传输，距离大大缩短，不但速度有了很大提升，而且 功耗也小的多。并且通过口核复用技术可以减少研发成本，缩短研发时间。并且， s o c 技术也为多核处理器的出现提供了物理前提。 f p g a ( f i e l dp r o g r a m m a b l eg a t e a r r a y ，现场可编程门阵列) 是可编程逻辑器 件的一种。可编程逻辑器件是近年来发展比较迅速，应用比较广泛的一种专用集 成电路( a s i c ) 设计新方法。它为用户提供了可编程的功能，用户可根据自己的 需要，通过编程的方式来确定器件的逻辑功能，极大地缩短了设计和制造时间。 比较大的可编程逻辑器件设计厂商有x i l i n x ，a l t e r a 等等。x i l i n x 和a l t e r a 于2 0 2 浙江人学硕上学位论文 第1 章绪论 世纪8 0 年代中期分别推出了c p l d ( c o m p l e xp r o g r a m m a b l el o g i cd e v i c e ，复杂 可编程逻辑器件) 与f p g a 。 f p g a 基于s r a m 技术，通过查找表( l o o k - u pt a b l e ，l u t ) 来实现逻辑功 能。在f p g a 内部有很多可配置逻辑块( c o n f i g u r a b l el o 西c a lb l o c k ，c l b ) ，每 个c l b 中都有若干个l u t 以及寄存器。在c l b 周围有许多布线资源，用户通过 对这些布线资源进行配置来将c l b 连接成不同功能的器件。在芯片的外围，还有 一些输入输出控制块，用来与外界进行交互。 f p g a 技术的发展为硬件设计提供了更为方便的测试和验证平台。使用f p ( a 厂商提供的e d ai 具能够很方便的进行体系结构描述，以及在f p g a 上进行验 证。本文就将通过x i l i n x 公司的v e r t e x - 4m l a 0 3f p g a 开发板对本文所设计的系 统进行验证。 1 1 3 信息检索技术 随着计算机和互联网的普及，人类社会进入了信息时代。互联网数据中心 ( i d c ) 于2 0 0 7 年3 月发布的一份调研报告显示：2 0 0 6 年全球创建的信息总量 为1 6 1 e b ( e x a b y t e ，1 e b = 1 0 亿g b ) ，这相当于迄今为止所有书籍的信息量的 3 0 0 万倍。而到2 0 1 0 年这个数字预计会达到9 8 8 e b 1 2 】。生物技术不断发展。随着 人类基因组计划的启动，生物研究已经进入基因时代。国际基因库( g e n b a n k ) 中的基因中的碱基数目在2 0 0 1 年初就已经达到l l o 亿，并且以大约每1 4 个月翻 一番的速度增长【1 面对如此庞大数据量的电子信息，人们往往要从其中提取出 对自己有用的信息比如，在数以亿计的网页中查找信息，图像识别技术中在大 量的二进制图像数据中查找相似的数据，在生物信息学中从大量的d n a 序列中 查找特征子序列等等。这时候就要用到信息检索的技术，而如何简便高效的进行 信息检索就成了信息时代一个重要的课题 信息检索需要在大量数据中查找有用的信息，计算量非常大。仅仅使用通用 处理器不进行任何优化的检索将耗费大量的时间。以往主要是通过软件算法进行 优化和加速，比如l 【1 4 1 算法等。而对于这样的海量数据处理，采用并行计算 也能够大幅提高运算效率。因此，人们提出了并行信息检索以及分布式信息检索 的方法。使用s i m d 计算机，m i m d 计算机，分布式计算机等来进行信息检索， 从硬件上提高了计算效率【1 5 1 。 不过以上方法都是基于通用处理器进行的并行优化，而信息检索的计算方式 比较单一，而数据量较大，并行度较大，通用处理器并无法针对这些特性进行优 浙江大学硕士学位论文 第l 章绪论 化。因此，可以考虑使用专用的处理器进行计算。随着处理器技术的发展，多核 技术，尤其是异构多核技术渐渐成为处理器发展的趋势。在异构多核体系结构中， 一般拥有一个主控核用来进行控制和一些通用计算，而辅助核则用来高速的完成 某些特定功能。这种体系结构正好适用于对信息检索这样大数据量，计算任务相 对单一的应用进行加速。因此，将多核技术用于信息检索就成为一个很好的解决 方法。 1 2 相关研究 多核处理器目前已经成为处理器发展的主流趋势。在一个芯片上集成多个处 理器核，通过共享高速缓存和片上总线进行通讯，比起以往通过板级总线进行互 联的方式有了很大的性能提升。并且多核技术也节省了芯片面积和成本，比起以 往传统的并行处理器来说有着很大的优势。尤其是异构多核处理器能够根据特定 的功能需求和应用方向来设计专用的辅助处理核，更加能够带来有效的性能提 升，十分适合本研究的应用场景。 本文主要研究使用异构多核技术对信息检索计算进行加速。目前，相近的研 究还很少。不过，在使用并行计算机或者专用的a s i c 加速器来对信息检索计算 进行优化方面，目前已经有了一定的研究。但都还不够成熟和完善，有着种种不 足之处。 传统的并行计算机中，很多s i m d 计算机，m i m d 计算机都可以用来进行信 息检索的加速，但这些计算机都是直接通过简单的增加并行度的方法来提高性 能，其每个处理核仍然还是普通的通用处理器，并不能根据信息检索计算的特点 进行任何优化。而且这类大型计算机一般都是高成本高能耗，很难应用于嵌入式 领域。 另一方面，在目前信息检索的研究中，除了各种各样的软件算法之外，也出 现了一些a s i c 硬件加速器。这些加速器一般多数是针对某一种特殊应用( 比如 字符串匹配) 下的某个特定算法( 比如k m p 算法等) 所定制的，使用特定设计 的专用电路来实现其算法或对算法的一部分进行加速。其缺陷在于只能进行功能 比较固定的计算，至多进行简单的配置操作而无法灵活的运用于各种信息检索 的场景，通用性较差。再者，这一类的加速器也很难进行进一步的扩展，以适应 更高数据量的应用。 4 浙江大学硕士学位论文 第1 章绪论 1 3 主要研究难点 本研究的主要难点在于以下几个方面： 1 信息检索算法的软硬件协同设计。本设计不同于以往的纯软件算法，而是采 用硬件来对信息检索进行加速。因此，必须采用软硬件协同设计的方法，来 完成体系结构以及上层软件的设计。 2 辅助处理核与指令集的设计。辅助处理核是本文最主要的创新，不同于以往 的通用处理核，也不同于一些a s i c 加速器，既需要较高的性能，又要有较 好的灵活性。因此，处理核的设计是一个难点。目l j i 对于特定应用的复制加 速处理核多数是采用m 核的方式，这种方式对于某些具体的固定的应用比较 合适。而信息检索所包含的范围比较广，涉及到的检索方式，检索数据宽度 等等都有所不同。因此，采用指令集的方式能够使该系统更加灵活，应用更 加广泛。而一个系统的性能很大程度上取决于指令集的好坏所以，如何设 计指令集能够既易于实现，又能获得较高的频率和执行效率也成为了本设计 的难点之一。 3 在本系统中，辅助核采用本地存储器( l s ) 来存放需要计算的数据和计算得 到的结果。l s 与高速缓存的工作方式不同，需要主控核组织好后，通知辅助 核，辅助核以d m a 的方式载入l s 。因此，l s 的组织方式对于辅助核的执行 效率来说也是至关重要的。 1 4 本文主要工作 基于以上的背景，本文做了以下一系列工作： 1 设计了一个专用于信息检索的异构多核硬件加速的体系结构以及软件编程模 型、相关的汇编器、应用软件等。该体系结构包括2 个处理核：一个是x i l i n x v e r t e x 4m l 4 0 3 开发板上自带的p o w e r p c 4 0 5 处理核，作为主控核，进行控制 操作，上层软件运行等；另一个是自行设计的专门用来进行信息检索的辅助 处理核。两个处理核之间通过m m 的c o r e c o r m e c t 总线进行连接。主控核通 过总线向辅助核发送控制信息，辅助核则根据控制信息，从主存中读取数据 进行计算，计算结束后将计算结果返回给主控核。在完成了体系结构的设计 之后，为了验证该系统的功能和效率，使用v e r i i o gh d l 语言进行描述，并 在x i l i n xv e r t e x 4m l 4 0 3 开发板上进行了验证。验证结果显示，该系统能够有 效的提高信息检索处理的运算速度，提高执行效率。 2 在这个体系结构中，辅助核的设计是本文的重点。首先，辅助核有自定义的 5 浙江大学硕士学位论文 第l 章绪论 一套专用指令集，这套指令集专门用来进行信息检索的操作。而且，为了进 一步提高匹配的并行度和执行效率，指令集中还包含s i m d 指令。然后，基 于这套特定的指令集，定义了寄存器，设计了辅助核的处理单元。 3 辅助核在运行中使用的数据，以及计算得到的结果都存储在本地存储器( l s ) 中。所以，l s 的组织也是一个重要的问题。本文针对信息检索处理以及处理 单元的特点设计了l s 中1 2 8 宽度的数据寻址方式，并且采用灵活可变组织形 式，让用户能够根据不同的应用场景，通过代码来对l s 进行组织。 1 5 本文组织结构 本文后续章节如下组织： 第二章为相关综述，从处理器和并行计算的发展历史来引出多核技术，并对 多核目前的研究现状进行了分析；另一方面，对信息检索，以及目前的各种信息 检索方法的优缺点进行了分析，从而展示了本文所设计的基于异构多核体系结构 的信息检索系统的优越性。 第三章具体描述基于异构多核体系结构的信息检索硬件加速的设计，首先对 整个系统体系结构和运行方式进行介绍，其次重点介绍辅助核的设计。 第四章描述本系统的具体实现，包括实现方式，硬件环境，系统参数等等方 面。 第五章给出了测试和验证的方法以及得到的结果，证明了本系统对信息检索 运算的效率提升。 最后一章对全文进行了总结，并且指出了本文中存在的不足之处，以及下一 步工作的展望。 6 浙江大学硕l4 学位论文第2 章多核0 信息检索相关研究综述 第2 章多核与信息检索相关研究综述 2 1 多核相关研究 2 1 1 传统并行计算 并行计算是一个历史悠久的话题。当一台计算机的计算能力不足时，使用多 台机器来协作运算就成了一个很好的方法。6 0 年代初期，由于晶体管以及磁芯存 储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术促使 并行计算成为计算机的发展的一个新方向。 最早的4 位微处理器实际上也可以看作是位与位之日j 的并行计算，后来为了 提高运行效率陆续出现了8 位，1 6 位，3 2 位以及“位的微处理器。另一方面， 也出现了更多其他方式的并行技术，比如指令级并行，线程级并行等等【1 6 1 。1 9 8 9 年，a l m a s ia n dg o t t l i e b 对并行计算机进行了如下概括：“并行计算机是一组相互 通信、相互协作以快速求解大型问题的处理单元”p t i 。 对并行计算机的分类有多种方法，其中最著名的是1 9 6 6 年由f l y o n 提出的分 类法，称为f l y n n 分类法。f l y n n 分类法是从计算机的运行机制进行分类的。f l y n n 根掘指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类【l s 】： 1 单指令流单数据流( s i n g l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m , s i s d ) ： 2 单指令流多数据流( s i n g l e i n s t r u c t i o ns t r e a m m u l t i p l e d a t as t r e a m , s i m d ) t 3 多指令流单数据流( m u l t i p l ei n s t m c t i o ns t r e a ms i n g l ed a t as t r e a m , m i s d ) ； 4 多指令流多数据流( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m , m i s d ) 。 s i s d 就是普通的串行处理器，而m i s d 在现实中还无法找到与之匹配的计算 机。s i m d 计算机中有一个控制部件( 又称为控制单元，c o n t r o lu n i t ) 和许多处理 单元( p r o c e s s i n gu n i t ) 。所有的处理单元在控制部件的统一控制下工作。而在 m i m d 计算机中没有统一的控制部件。在m i m d 中，各处理器可以独立地执行不 同的指令 对称多处理器s m p ( s y m m e t r i c a lm u l t i p r o c e s s i n g ) 就是mm d 计算机的一 种。个s m p 系统中汇集了一组处理器，各处理器之问共享内存系统以及板级 总线。系统中的各个处理器是相同的，并且地位也平等。但是从上层用户的角度 来看，s m p 系统就像一台普通的单处理器计算机一样。由操作系统系统将任务队 列对称地分配给每个处理器。所有处理器并行的执行任务，并且通过总线发送消 7 浙江大学硕上学位论文第2 章多核与信息检索相关研究综述 息或者共享变量等方式来进行通信。这样就提高指令序列级的并行度，从而极大 地提高了整个系统的数据处理能力【1 9 】。 此外，还有向量并行处理器( p v p ) 、大规模并行处理器( m p p ) 、工作站机 群( c o w ) 、分布式共享存储器d s m 多处理机等m i m d 计算机。这些基本上都 是使用多个处理器，通过提高空间上的并行度来提升性能的。 另一方面，流水线技术的出现使得指令之间能够在时间上并行执行。在同一 时刻，不同的指令处于不同的执行阶段，使用不同的硬件资源，以此来达到指令 级的并行运行。流水级越多，所获得的加速比也越高。 超标量技术是一种改进了的流水线技术，该技术是在流水线中加入了多个译 码器以及算术逻辑单元a l u 或者浮点处理单元f p u 。在一个时钟周期内c p u 可 以发射多条指令，运行与不同的处理单元上。这样实际上形成了多条并行执行的 流水线，以此来提高指令执行的效率 2 0 1 在流水线技术中，流水缴过多则会增加流水级之间延迟的丌销，并且控制逻 辑会变得更加复杂。而随着流水线的增加，也会出现流水线不能被填满的情况， 也就是说处理器的处理单元并没有被完全利用。在超标量技术中，多个处理单元 在同一时刻并不总是同时运行的，有些处理单元可能处于空闲状态。为了解决这 图2 - i 超标量，多处理器。超线程，超线程的多处理器资源利用率比较 引自用h 呻：一n 耐0 1 1 e d u - j d o n a k l y p e r t h r e a d i n g h y p e r t h r e a d i n g _ i m a g e i ，g i f 8 浙江大学硕上学位论文第2 章多核i 信息检索相关研究综述 个问题，i n t e l 公司提出了超线程技术1 2 1 1 。该技术并不在物理上使用多个计算单元， 而是通过特殊的硬件指令，将一个物理计算单元在逻辑上模拟成两个相同的计算 单元，分别运行两条流水线。这两条流水线前端的指令发射、译码等部件都是分 开的，而后端的运算部件则是共享的。在上层看来就像有两个处理器核在运行， 以此来提高计算单元的利用效率。 以上这些技术的资源利用率如图2 1 所示：小方格表示处理单元，不同的颜 色或灰度表示被不同的线程所占用。可以看出，超标量的资源利用率比较低，而 超线程采用了处理单元共享的方法，提高了资源利用率。而多处理器则是使用完 全分离的两套计算单元进行运算。多处理器系统中的每个处理器又都可以是超线 程的，以进一步提高资源利用率。采用这些技术可以大大提高运算的并行度，提 高效率。这些也为多核技术的出现奠定了基础。 2 1 2 多核技术的出现 多核技术( m u l t i c o r e ) 又称为片上多处理器( c h i p - m u l t i p r o c e s s i n g ) 技术， 简称c m p 。多核体系结构与之前的s m p 等多处理器技术最大的不同之处在于， 多核系统中的多个处理器都集成在一个芯片上，可以看作是s m p 与s o c 技术的 结合，c m p 就相当于片上s m p 。 早在1 9 9 1 年，c m p 技术就被提出来解决视频编解码问题f 埘。斯坦福大学1 9 9 6 年提出的h y d r a 处理器 2 3 1 是一款经典的c m p 体系结构，其拥有4 个同构的处理 器核，集成在一块芯片上，并且通过共享二级缓存的方式进行通讯，如图2 - 2 所 引用虮2 3 】 图2 - 2h y d r ac g p 体系结构 9 浙江人学硕士学位论文第2 章多核与信息检索相关研究综述 示。2 0 0 1 年i b m 推出了的第一款商用多核处理器p o w e r 4 。之后，随着i n t e l 和 a m d 公司推出的多核的桌面处理器的上市，多核技术才逐渐为人们所广泛了解， 并成为今后的主流。 在多核处理器中每个处理核都拥有完整的计算单元以及一级缓存。而二级缓 存可以为每个处理核所私有，也可以被几个处理核所共享。共享的二级缓存可以 用来实现多个处理核之闻的通信。另外一种核间通信的方式是片内总线，通过芯 片内部的高速总线来连接各个处理核，进行数据传输和消息通信。通常用到的总 线包括：i b m 的c o r e c o n n e c t 总线 2 4 1 ，a r m 公司的a m b a 总线( 2 5 】，以及o p c n c o r 姻 的w i s h b o n e 总线啪1 等。 由于多核处理器的多个处理核是集成在一个芯片内，而核问通信也是通过片 内的共享二级缓存或者高速总线来实现的。因此，比起之前的多处理器通过板级 总线的互联，速度和性能都有了很大的提升。 2 1 3 多核体系结构的分类 多核体系根据处理核的类型可以分为两种主要的结构：同构多核体系和异构 多核体系。 同构多核体系结构是指一个处理器中的各个处理核是相同的，每个核的地位 对等，一般来说都是通用处理核。同构多核与s m p 有相似之处，对于上层来说 可以看作是两个c p u ，由操作系统来进行任务分配。同构多核处理器一般设计相 对简单，线程调度，核问通信等都与之前的s m p 等比较相似。 引用甑2 7 】 图2 - 3i n t e lc o r ed u o 体系结构 i o 浙江大学硕l ：学位论文第2 章多核与信息检索相关研究综述 同构多核处理器主要通过提高并行度来提高性能，一般多用于通用计算。比 如，2 0 0 1 年m m 推出的第一款商用多核处理器p o w e r 4 ，以及i n t e l 公司于2 0 0 5 年推出的首款应用与桌面的多核处理器p e n t i u md 以及之后的c o r ed u o ，c o r e2 d u o 等，都是同构的双核处理器【2 7 l ，c o r e d u o 体系结构如图2 3 所示。可以看出 在i n t e lc o r ed u o 体系结构中，两个处理器是完全对称的，并且各自拥有独立的 执行资源( e x e c u t i o nr e s o u r c e s ) 、一级缓存( l ic a c h e s ) 等。而两个处理核则共 用一个能耗管理逻辑( p o w e rm a n a g e m e n tl o g i c ) 和二级缓存( l 2s h a r e dc a c h e ) ， 并且通过同一个总线接口( b u si n t e r f a c e ) 连接到f s b 总线上。 与同构处理器不同，异构多核体系中的各个处理核是不同的，按照功能可以 分为主控核与辅助核。主控核一般为通用处理器，用来进行控制和一些通用运算。 而辅助核一般为专用处理核，执行某类特殊的运算。 图2 4c e l l 体系结构不意图 引用自【2 8 1 异构多核处理器除了提高并行度之外，还依靠面向特定运算的专用处理器来 进行加速，进一步提升性能。例如，m m 公司的c e l l 处理器就是一款典型的异 构多核处理器【2 观c e l l 包括一个作为主控核的p o w e r 处理单元p p e ( p o w e r p r o c e s s i n ge l e m e n t ) 和八个辅助处理单元s p e s ( s y n e r g i s t i cp r o c e s s i n ge l e m e n t s ) 。 浙江大学硕l 学位论文第2 章多核与信息检索相关研究综述 s p e s 专门用来进行浮点运算，并且支持s i m d 技术，能够大幅提高浮点运算的效 率。p p e 和s p e s 以及内存控制器，i o 控制器等都通过高速的元件连接总线e i b ( e l e m e n ti n t e r c o n n e c tb u s ) 进行连接，如图2 - 4 所示。以上这些特性使得c e l l 处理器在大数据量的浮点运算等方面，具有很高的性能，除了主要运用于索尼的 下一代p s 3 游戏主机上之外，还将会运用在3