（计算机软件与理论专业论文）多核系统中的程序性能优化研究.pdf

u n i v e r s i t yo fs c i e n c e a n dt e c h n o l o g yo fc h i n a adi s s e r t a t i o nf o rd o c t o r sd e g r e e s t u d y o np r o gr a mp e r f o r m a n c e o p t i mi z a t ioninmul t i - co r e s y s t e m s a u t h o r sn a m e ： s p e c i a l i t y ： 一 s u p e r v i s o r ： f i n i s h e dt i m e ： q iz h a n g c o m p u t e rs o f t w a r ea n dt h e o r y p r o f y i n l o n gx u a p r i l3 0 ，2 0 1 0 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：签字日期：丝! ! 笙生旦三里 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 导师签名- 碎雌 签字日期：2 翌! ! ：笪： 。1 摘要 摘要 多核处理器在一个处理器芯片上集成多个处理器核心，可同时执行多个线 程。长期以来，处理器芯片上的晶体管数目不断增加，处理器的设计越来越复 杂，但因为功耗和工艺等方面的限制，处理器的时钟频率无法再继续提高。随 着处理器厂商纷纷推出各自的多核处理器，多核系统在我们的工作和生活中迅 速得到普及，并且每个处理器中的核数目还在不断的增加。多核处理器的普及 给应用程序的发展带来了巨大的挑战，多核处理器中每个核的计算能力并没有 增强，它是通过组合多个处理核来提供强大的计算能力。传统的串行应用程序 无法方便的直接借助处理器核数目的增加提升性能，必须通过并行化或者同时 执行多个程序才能充分发挥多核系统的计算能力。 本文从应用程序性能优化和系统整体性能优化两个角度，研究了多核系统 中的程序性能优化方法，并验证其有效性。本文的主要工作和创新点如下： 1 对于多核系统中的应用程序性能优化，本文分别研究了串行程序性能优化方 法，并行程序设计方法和并行程序性能优化方法。通过为程序设计并行算法 并实现，可以使程序同时利用多个核的计算能力。通过对并行程序进行优化， 可以使程序更充分的发挥多个核的计算能力，其方法包括增加任务数量改善 负载均衡，选择最优的线程与处理核之间关联策略，设计无锁机制减少同步 开销，消除线程间高速缓存伪共享等等。 2 本文通过对多个图像特征提取和马尔可夫决策过程求解程序进行性能优化， 使这些应用程序在多核系统中的性能获得了较大提升，并验证了所采用的性 能优化方法能够有效的提高应用程序在多核系统中的性能。 3 对于多核系统整体性能的优化，本文研究了多线程之间对共享缓存空间的竞 争问题，这种竞争会损害整个系统以及各个程序的性能。本文提出了基于工 作集模型分析和预测共享缓存上线程竞争情况的方法，并发现如果同时运行 线程的工作集大小之和超出共享缓存容量，或者同时运行线程的时间局部性 强度差异较大时，线程受到的干扰就会比较剧烈，性能损失比较严重。 4 本文提出了一种基于工作集模型的线程调度方法。本方法通过一组监测单元 以较小的代价获得线程的工作集大小和时间局部性强度属性，并根据一套线 程调度策略，选取合适的线程同时运行，保证线程的工作集数据可以保存在 高速缓存之中。实验结果表明，基于工作集模型的线程调度方法较好的缓解 了共享缓存上线程间的互相竞争，有效提高了整个系统和各个程序的性能。 关键词：程序性能优化多核系统线程调度多线程程序可扩放性性能优化 i a b s t r a c t a b s t r a c t t h em u l t i c o r ep r o c e s s o ri n t e g r a t e sm u l t i p l ep r o c e s s o rc o r e so nas i n g l ec h i p w h i c hc a nr u nm u l t i p l et h r e a d ss i m u l t a n e o u s l y o v e rt h ey e a r s ，t h en u m b e ro f t r a n s i s t o r so nap r o c e s s o rc h i pg r o w sc o n s t a n t l y , a n dt h ed e s i g no fp r o c e s s o r b e c o m e sm o r ea n dm o r ec o m p l e x b u tf o rt h ep o w e ra n ds o m eo t h e ra s p e c t s ，t h e c l o c k f r e q u e n c y c a nn o ti n c r e a s em o r e w i t ht h ep r o c e s s o rm a n u f a c t u r e r s i n t r o d u c i n gt h e i rm u l t i c o r ep r o c e s s o r s ，m u l t i c o r es y s t e m sb e c o m ep o p u l a ri no u r w o r ka n dl i f e a n dt h en u m b e ro fc o r e si nac h i pi si n c r e a s i n gc o n s t a n t l y t h e p o p u l a r i t y o fm u l t i c o r ep r o c e s s o r sb r i n g se n o r m o u sc h a l l e n g e st oa p p l i c a t i o n p r o g r a m i n am u l t i - c o r ep r o c e s s o r , t h ec o m p u t i n gp o w e ro fe a c hc o r ei sn o t e n h a n c e d i tc o m b i n e sm u l t i p l ep r o c e s s o rc o r e st op r o v i d ep o w e r f u lc o m p u t i n g a b i l i t y t h et r a d i t i o n a ls e r i a la p p l i c a t i o n sc a nn o td i r e c t l yi m p r o v ep e r f o r m a n c eb y t h ei n c r e a s i n go fp r o c e s s o rc o r e s t of u l l yu s ec o m p u t i n gp o w e ro fm u l t i 。c o r e p r o c e s s o r , w em u s tr u np a r a l l e lp r o g r a mo rm u l t i p l ep r o g r a m sc o n c u r r e n t l yo nt h e s y s t e m t h i sp a p e rs t u d i e sp r o g r a mp e r f o r m a n c eo p t i m i z a t i o no nm u l t i - c o r es y s t e mb y t w op e r s p e c t i v e s ，a p p l i c a t i o np r o g r a mp e r f o r m a n c eo p t i m i z a t i o na n do v e r a l ls y s t e m p e r f o r m a n c eo p t i m i z a t i o n t h em a j o rw o r ka n di n n o v a t i o no ft h i sp a p e ra r e 嬲 f o l l o w s ： 1 f o ra p p l i c a t i o np r o g r a mp e r f o r m a n c eo p t i m i z a t i o ni nm u l t i 。c o r es y s t e m s ，t h i s p a p e rs t u d i e s s e r i a l p r o g r a mp e r f o r m a n c eo p t i m i z a t i o nm e t h o d s ，p a r a l l e l p r o g r a md e s i g n m e t h o d sa n dp a r a l l e lp r o g r a mp e r f o r m a n c eo p t i m i z a t i o n m e t h o d s t ou s ec o m p u t i n gp o w e ro fm u l t i p l ec o r e s ，w en e e dd e s i g na n d i m p l e m a t i o np a r a l l e la l g o r i t h mf o rp r o g r a m s t o u s ec o m p u t i n gp o w e ro f m u l t i p l ec o r e sm o r ef u l l y , w en e e do p t i m i z ep r a l l e lp r o g r a mp e r f o r m a n c e t h e p a r a l l e lp r o g r a mp e r f o r m a n c eo p t i m i z a t i o nm e t h o d s s t u d i e di nt h i sp a p e ri n c l u d e i m p r o v i n gl o a db a l a n c eb yi n c r e a s i n gt a s k sn u m b e ra n dr e d u c i n g t a s k ss i z e ， c h o o s i n gt h eb e s ta f f i n i t yp o l i c yb e t w e e nt h r e a d sa n dp r o c e s s o rc o r e s ，d e s i g n i n g l o c k f r e es t r u c t u r et or e d u c es y n c h r o n i z a t i o no v e r h e a d ，e l i m i n a t i n gf a l s es h a r i n g o fc a c h eb e t w e e nt h r e a d sa n ds oo n 2 t h i sp a p e ra p p l i e st h e s ep e r f o r m a n c eo p t i m i z a t i o nm e t h o d st os e v e r a li m a g e f u t u r ee x t r a c t i o na n dm a r k o v ed e c i s i o np r o c e s ss o l v i n gp r o g r a m s e x p e r i m e n t i i i a b s t r a c t r e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft h e s ep r o g r a m si si m p r o v e dm u c h ，a n dt h i s v e r i f i e st h ep r o g r a mp e r f o r m a n c eo p t i m i z a t i o nm e t h o d ss t u d i e di nt h i sp a p e rc a n e f f e c t i v e l yi m p r o v et h ep r o g r a mp e r f o r m a n c ei nm u l t i - c o r es y s t e m s 3 f o ro v e r a l ls y s t e mp e r f o r m a n c eo p t i m i z a t i o n ，t h i sp a p e rs t u d i e st h et h r e a d s c o n t e n t i o np r o b l e mo nt h es h a r e dl a s tl e v e lc a c h eo fm u l t i - c o r es y s t e m s ，w h i c h m a yr e d u c ep e r f o r m a n c eo fe a c ht h r e a da n do v e r a l ls y s t e m w ep r o p o s e sa m e t h o db a s e do nw o r k i n gs e tm o d e lt oa n a l y s i sa n de s t i m a t e t h et h r e a d c o n t e n t i o np r o b l e mo nt h em u l t i c o r es y s t e m s w ef i n dt h a to n c et o t a lw o r k i n g s e ts i z eo ft h et h r e a d se x c e e dt h es h a r e dc a c h es p a c eo rt h ed i f f e r e n c eo f t e m p o r a ll o c a l i t y i s g r e a t ，t h e i n t e r f e r e n c et h r e a ds u f f e ri ss e v e r ea n dt h e p e r f o r m a n c ed e g r a d a t i o ni ss e r i o u s 4 t h i sp a p e rp r o p o s e sat h r e a ds c h e d u l i n gm e t h o db a s e do nt h ew o r k i n gs e tm o d e l i nt h i sm e t h o d ，w ed e s i g nas e to fm o n i t o r i n gu n i to ns h a r e dc a c h e ，w h i c hc o l l e c t t h ew o r k i n gs e ts i z ea n dt e m p o r a ll o c a l i t yo ft h r e a d sb yl o wo v e r h e a d w ea l s o p r o p o s ea no p e r a t i n gs y s t e mt h r e a ds c h e d u l i n gp o l i c y , w h i c hs e l e c ta p p r o p r i a t e t h r e a d sr u n n i n gs i m u l t a n e o u s l yt oe n s u r et h ew o r k i n gs e t so ft h r e a d sc a l lb ek e p t i nt h es h a r e dc a c h e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h et h r e a ds c h e d u l i n g m e t h o db a s e do nw o r k i n gs e tm o d e lr e m i t st h et h r e a d sc o n t e n t i o no nt h es h a r e d c a c h e ，e f f e c t i v e l yi m p r o v e st h ep e r f o r m a n c eo f o v e r a l ls y s t e ma n de a c hp r o g r a m k e yw o r d s ：p r o g r a mp e r f o r m a n c eo p t i m i z a t i o n ，m u l t i c o r es y s t e m ，t h r e a d s c h e d u l i n g ， m u l t i t h r e a d p r o g r a ms c a l a b i l i t yp e r f o r m a n c e o p t i m i z a t i o n 目录 目录 第l 章绪论1 1 1 多核处理器1 1 1 1 多核处理器的出现和发展1 1 1 2 典型的多核系统体系结构2 1 2 多核系统对应用程序的影响3 1 3 相关工作4 1 3 1 程序性能优化4 1 3 2 并行算法设计4 1 3 3 并行程序实现4 1 3 4 基于内容的视频信息检索系统及其相关性能优化5 1 3 5 多核系统中的线程调度方法6 1 3 6 多核系统中的缓存分割方法7 1 4 本文的研究内容和主要贡献7 1 4 1 应用程序性能优化方法研究8 1 4 2 多核系统中的线程调度方法研究9 1 5 论文结构1 l 第2 章图像颜色相关图特征提取程序性能优化1 3 2 1 引言 2 2 图像颜色相关图特征提取算法 2 3 图像颜色相关图特征提取串行程序性能优化 2 4 图像颜色相关图特征提取并行算法 2 5 图像颜色相关图特征提取并行程序优化 2 6 实验结果及分析 1 3 1 4 1 5 1 7 1 8 2 0 2 6 1 实验平台2 0 2 6 2 实验输入数据集2 1 2 6 3 可扩放性性能及分析2 1 v 目录 2 7 本章小结2 3 第3 章图像多维白回归纹理特征提取程序性能优化2 5 3 1 引言2 5 3 2 图像多维自回归纹理特征提取算法2 6 3 3 图像多维自回归纹理特征提取串行程序性能优化2 6 3 4 图像多维自回归纹理特征提取并行算法2 8 3 5 图像多维自回归纹理特征提取并行程序性能优化2 9 3 5 1 负载均衡性能优化2 9 3 5 2 关联线程到处理器3 0 3 6 实验结果和分析3 2 3 6 1 可扩放性性能及分析3 2 3 7 本章小结3 5 第4 章图像g a b o r 纹理特征提取程序性能优化3 7 4 1 引言3 7 4 2 图像g a b o r 纹理特征提取算法3 7 4 3 图像g a b o r 纹理特征提取串行程序性能优化3 8 4 3 1 使用英特尔数学核心函数库3 8 4 3 2 充分利用单指令多数据指令3 9 4 3 3 串行优化效果4 0 4 4 图像g a b o r 纹理特征提取并行算法4 0 4 4 1g a b o r 滤波器间任务级并行算法4 0 4 4 2g a b o r 滤波器内数据级并行算法4 l 4 5 实验结果及分析4 2 4 5 1 可扩放性性能及分析4 2 4 5 2 不同线程关联策略对可扩放性性能的影响4 6 4 6 本章小结4 6 第5 章图像尺度不变特征变换程序性能优化4 7 5 1 引言4 7 5 2 图像尺度不变特征变换算法4 8 5 3 图像尺度不变特征变换串行程序性能优化5 0 v l 目录 5 4 图像尺度不变特征变换并行算法5 1 5 4 1 直接并行算法5 1 5 4 2 改进的并行算法5 2 5 5 图像尺度不变特征变换并行程序性能优化5 4 5 5 1 减少线程间同步开销5 4 5 5 2 消除高速缓存伪共享5 5 5 6 实验结果及分析5 6 5 6 1 实验环境5 6 5 6 2 实验输入数据集5 7 5 6 3 程序性能提升实验结果5 7 5 6 4 并行程序可扩放性结果及分析5 9 5 6 5 存储系统性能数据与分析6 1 5 6 6 片上多处理器模拟平台实验结果6 3 5 7 本章小结6 3 第6 章马尔可夫决策过程求解并行算法及性能6 5 6 1 引言6 5 6 2 马尔可夫决策过程模型，6 6 6 2 1 马尔可夫决策问题介绍6 6 6 2 2 马尔可夫决策过程模型6 6 6 2 。3 确定最优行动策略6 7 6 3 动态规划求解马尔可夫决策过程6 8 6 3 1 策略迭代算法及分析6 8 6 3 2 价值迭代算法及分析6 9 6 4 求解马尔可夫决策过程并行算法7 0 6 4 1 并行策略迭代算法7 0 6 4 2 并行价值迭代算法7 1 6 5 马尔可夫决策过程求解并行算法分析7 3 6 5 1 计算复杂度和通信代价分析7 3 6 5 2 可扩放性分析7 5 6 5 3 负载均衡分析7 6 6 6 实验结果及分析7 6 v i i 目录 6 6 1 应用马尔可夫决策过程于实时战略游戏控制7 7 6 6 2 实验平台7 8 6 6 3 并行策略迭代程序性能7 8 6 6 4 并行价值迭代程序性能8 0 6 7 本章小结8 2 第7 章基于工作集模型的多核系统线程调度方法8 3 7 1 引言8 3 7 2 基于工作集模型的线程调度方法框架8 6 7 3 线程局部性曲线及监测器8 7 7 3 1 线程局部性曲线8 7 7 3 2 线程监测器8 9 7 3 3 系统监测器9 0 7 4 线程工作集大小估计9 0 7 5 不公平性问题9 2 7 6 线程调度策略9 4 7 7 实验结果和分析9 5 7 7 1 实验平台9 5 7 7 2 度量标准9 6 7 7 3 工作集模型实验9 6 7 7 4 基于工作集模型线程调度方法的有效性9 8 7 7 5 与相关工作的比较1 0 0 7 8 本章小节1 0 2 第8 章总结与展望1 0 5 8 1 本文的主要工作1 0 5 8 2 本文的主要贡献1 0 6 8 3 未来工作展望1 0 7 参考文献1 0 9 附录l 基于工作集模型的线程调度策略伪代码1 1 7 致谢1 2 1 在读期间发表的学术论文与取得的研究成果1 2 3 v i i i 第1 章绪论 第1 章绪论 本章摘要随着多核处理器的普及，如何在多核系统中优化程序 的性能，以充分发挥多核系统的强大计算能力日益引起人们越来 越多的关注，这也是本文研究工作的重点。本章首先介绍了本文 研究工作的背景和相关工作，接着描述了本文的研究内容以及研 究方法，最后给出了本文的组织结构。 1 1 多核处理器 多核处理器( m u l t i c o r ep r o c e s s o r ) ，也称作片上多处理器( c h i p m u l t i p r o c e s s o r ，c m p ) ，是指在一个处理器芯片上集成多个处理器核心，其中 每个核心都是一个独立的微处理器，这些处理器核心可以并行的执行多个线程 ( h a m m o n de ta l ，2 0 0 0 ) 。多核处理器中的多个核心可以是异构的也可以是同 构的，在本文中我们将主要关注同构多核处理器。而多核系统是指使用多核处 理器的计算机系统，我们期望使用多核系统以最大限度的利用线程级并行为应 用程序提供强大的计算能力。 1 1 1 多核处理器的出现和发展 半导体领域的“摩尔定律”指明，随着晶体管的体积越来越小，速度越来 越快，我们可以在单个芯片上集成的晶体管数目也越来越多。计算机处理器也 正是借助这些增加的晶体管资源来不断提升性能。但日益庞大和复杂的单处理 器结构导致了芯片资源利用率不断降低，且功耗不断增加，处理器芯片的设计 和时钟频率的提高越来越困难( 李辉等，2 0 0 6 ) 。这些困难主要体现在以下两 个方面( 刘必慰等，2 0 0 7 ) ： 一是提高处理器的时钟频率越来越困难。微处理器的性能提升很大一部分 是依靠制造工艺的进步，使元器件尺寸不断缩小，同时器件的延迟也不断减小， 但是器件之间互连线的延迟却无法同步减小，使得进一步提高时钟频率越来越 困难。因此2 0 0 5 年英特尔公司在发布3 8 g 赫兹的处理器后，不得不放弃研发 和推出拥有4 g 赫兹时钟频率的处理器。 二是处理器的功耗越来越大。随着制造工艺的提高，晶体管体积变小，在 一个芯片上集成的晶体管数量不断增多，加上时钟频率的提高，处理器芯片的 第1 章绪论 功耗越来越大。但芯片空间有限，功耗变大时容易导致芯片过热，降低元器件 的稳定性。 因此，自上个世纪末以来，研究者把目光越来越多的投向多核处理器。多 核处理器最早由斯坦福大学计算机系统实验室于1 9 9 6 年提出( o l u k o t t me ta l ， 1 9 9 6 ) ，它在一个处理器芯片上集成多个处理器核心，各个处理器核心并行执行 不同线程，比较类似于传统的对称多处理器并行系统。多核处理器中的每个处 理核都相当于一个独立的微处理器，但结构更加简单，易于设计和扩展，而且 功耗更小。它通过并行的执行多个线程，而不是提高处理器时钟频率，来增加 计算能力，提高性能，有效的使用了芯片资源。 多核处理器最初是在学术界被关注和研究的，包括斯坦福大学的h y d r a c m p 项目( o l u k o t u ne ta l ，1 9 9 6 ；h a m m o n de ta l ，2 0 0 0 ) ，威斯康辛大学的 m u l t i s c a l a r 项目( s o h ic ta l ，1 9 9 5 ；g o p a le ta l ，1 9 9 8 ) ，卡内基一梅隆大学的 s t a m p e d e 项目( s t e f f a ne ta l ，1 9 9 8 ) 和麻省理工学院的m m a c h i n e 项目( k e c l d e r e ta l ，1 9 9 8 ) 。而第一款商用的多核处理器是i b m 公司于2 0 0 1 年发布的p o w e r 4 处理器，每个p o w e r 4 处理器中集成了两个6 4 位i g 赫兹的p o w e r p c 处理核， 随后惠普公司在2 0 0 3 年推出了相似的多核处理器p a r i s c8 8 0 0 ，s u n 公司也推 出了双核架构的u l t r a s p a r c 处理器，它们主要被用于高端的商用服务器上( 刘 必慰等，2 0 0 7 ) 。 随着a m d 和英特尔公司在2 0 0 5 年各自推出商用双核处理器o p t e r o n 和 m o n t e c i t o ，多核处理器在我们的日常工作和生活中迅速普及开来。目前市场上 的计算机中央处理器绝大多数都是多核处理器，而且单个芯片上集成的处理核 数目越来越多，c p u 芯片结构的发展大趋势是由单核( s i g n a l c o r e ) 到多核 ( m u l t i c o r e ) 再到众核( m a n y c o r e ) ，新的摩尔定律预测片上核数每1 8 - 2 4 个 月将增加一倍。 1 1 2 典型的多核系统体系结构 一种典型的多核系统体系结构如图1 1 所示。c o r el 到c o r en 为n 个处理 核，每个处理核拥有私有的一级高速缓存( l 1c a c h e ) ，所有的处理核共享一个 最后一级缓存( s h a r e dl a s tl e v e lc a c h e ) ，缓存通过总线与主存相连。 2 第1 章绪论 l 1c a c h el 1c a c h e s h a r e dl a s tl e v e lc a c h e 介 lib u s m a i nm e m o r y 图1 1 典型的多核系统体系结构示意图 1 2 多核系统对应用程序的影响 在通过提高时钟频率来提升处理器性能的时代，应用程序并不需要做任何 改变，就可以直接在更新更快的处理器上获得更好的性能。但在当今的多核处 理器上，每个核的计算能力并没有增强，它是通过组合多个处理核来提供强大 的计算能力。传统的串行应用程序无法方便的直接通过处理器核数目的增加提 升性能，必须做出改变。 要充分发挥多核系统的计算能力，必须在系统中运行并行程序或者同时运 行多个程序。因此，多核处理器的出现和普及，把并行计算真正引入了个人计 算机，这标志着计算技术的一次重大飞跃。 如何利用多核加速单个应用是目前的一个难题。多核带来了更多的片上计 算和存储资源，更高的片上通信带宽和速度，可以利用更多的并行性( 线程级 和数据级并行性) 来提高性能。要发挥这些优势，要求片上执行的并行计算任 务规模适中，同步和通信的粒度适中，因此利用线程级并行性是一种理想的选 择。而要充分利用多核处理器的计算能力，挖掘应用程序的并行性，需要程序 设计者编写并发的代码，并在多核系统上高效的运行程序。并行编程原本仅是 专业人员面临大规模计算问题时的关注点，但是随着面向桌面应用的多核处理 器的出现，并行编程现已成为所有专业软件开发人员都必须了解和掌握的一项 技术。 另一方面，多核系统中的每个处理核虽然都是一个独立的微处理器，但与 对称多处理器系统不同，它们之间也共享着很多系统资源，比如最后一级缓存 和系统总线等。在多个处理核上同时运行多个线程，势必造成对这些共享资源 一定程度上的竞争，从而线程间彼此互相干扰，影响性能。因此，减少线程间 的干扰，提高多核系统的整体性能也是目前研究领域较关注的一个难题。 多核处理器给计算机系统带来了众多变革，有效的在多核系统中使用多核 3 第1 章绪论 处理器，最大程度的提高应用程序以及整个系统的性能是本文主要关注的问题。 1 3 相关工作 1 3 1 程序性能优化 实现高效的程序主要需要考虑两个方面，一是选择最好的算法和数据结构， 二是编写出编译器能够有效优化以转换成高效可执行程序的代码。通常，编译 器可以帮助我们对程序进行一些优化，但编译器优化程序的能力受到一些因素 的限制，比如它决不能改变程序的行为，对程序的了解有限，而且它需要较快 的完成编译工作。 因此，我们在对程序的性能有更高要求的时候，必须进行一些手工的优化。 一些常用的优化方法包括：移动循环判断内的代码以提高循环效率，减少函数 调用次数，使用寄存器变量减少对存储器的访问次数，通过循环展开( 1 0 0 p u n r o l l i n g ) 降低循环开销，使用指针代替数组减少计算量，使用循环分割( 1 0 0 p s p l i t t i n g ) 以充分利用处理器流水线等等( b r y a n te ta l ，2 0 0 2 ) 。但这些大多只是 针对串行程序和单核处理器系统的优化方法。 1 3 2 并行算法设计 并行算法设计是编写并行程序，以利用多处理器提高程序性能的基础。在 大规模并行系统上，研究者已提出众多的并行算法和并行算法设计方法。设计 并行算法的思路主要有三种：分析现有串行算法中的固有并行性进而直接进行 并行化；借鉴相似问题的并行算法来解决原问题；从问题本身出发设计全新的 并行算法( 陈国良，1 9 9 4 ) 。设计并行算法的方法主要有：平衡树方法( l a d n e r e ta l ，1 9 8 0 ) ，倍增方法( h i r s c h b e r g ，1 9 7 6 ) ，分治法( h o r o w i t ze ta l ，1 9 8 3 ) ， 划分法( v a l i a n t ，1 9 7 5 ) ，流水线技术( t o d d ，1 9 7 8 ) 等等。而且在长期的实践 过程中学术界和工业界已积累了大量的并行算法，但这些并行算法主要集中在 传统的大规模科学计算领域。 1 3 3 并行程序实现 长久以来，并行程序一般只在大规模并行计算机上实现和运行。其实现方 法主要依靠基于消息传递的l c d i 编程和p v m 编程，以及基于数据并行的h p f 编 程( 陈国良等，2 0 0 4 ) 。但在多核系统中，只有对程序进行细粒度的并行化才 能充分发挥多核的计算能力，因此在多核系统上实现并行程序多采用多线程共 享变量的编程模式。 4 第1 章绪论 p t h r e a d s 是一个提供线程级任务并行支持的运行时程序库，几乎被所有的 操作系统( 包括u n i x ，l i n u x ，w i n d o w sn t 等) 支持，其用户编程接口是一些 库例程调用。p t h r e a d s 适合描述任务并行，不便于数据并行，目前普遍被作为 其它并行编程模型的实现基础使用( 周茂成，1 9 9 9 ) 。 o p e n m p 编程模型通过定义编译制导、库例程和环境变量规范，给程序员 提供了支持f o r t r a n 、c c + + 语言的一组功能强大的高层并行方法。o p e n m p 采 用f o r k j o i n 并行执行模式，程序的并行块主要由p a r a l l e l 制导语句来描述，以单 程序多数据的方式用多线程执行。o p e n m p 标准只规定用户定义并行的语义， 它的实现本身并不检查依赖、死锁等导致程序错误的问题，完全由用户保证程 序的正确性( 章隆兵等，2 0 0 4 ) 。o p e n m p 编程模型适用于共享存储对称多处 理器系统以及当前的多核系统。 1 3 4 基于内容的视频信息检索系统及其相关性能优化 随着大容量存储器和数字化图像设备的普及应用，图像、视频、音频等媒 体数据呈现级数的增长，人们对自动化媒体处理软件的需求日益强烈。媒体处 理软件通常涉及到比较大的数据量和计算量，计算机的处理速度严重制约着媒 体处理软件的能力和发展。随着多核处理器的出现和普及，通用处理器的计算 能力大大加强，为进一步提高媒体处理软件的质量和速度提供了可能。 媒体信息检索是指从大量的媒体中找到特定的数据，提取有用的信息，是 媒体处理领域的一个重要问题。图像、视频检索的传统方法是基于文本的，使 用关键字对媒体进行注释是最常用的方法，从而对图像的检索变成了对关键字 的查找。这种方法比较简单，但对目前容量以t b 来计算的媒体集合，要求对每 一幅图像、每一段视频进行注释，显然是不可行的。 为了克服以上方法的局限性，出现了基于内容的视频信息检索 ( c o n t e n t - b a s e dv i d e oi n f o r m a t i o nr e t r i e v a l ，c b v i r ) ( m a r q u e se ta l ，2 0 0 0 ) 方 法，并迅速得到国内外同行的重视和认可。c b v i r 系统能够自动提取视频、图 像的视觉特征( 例如颜色、纹理结构、轮廓、位置关系等特征) ，并以此作为图 像的内容进行匹配、查找等检索工作。这种方法克服了手工注释的低效和二义 性，是自动媒体处理的一个有效途径( 李瑜等，1 9 9 9 ) 。 基于内容的视频信息检索方法提出以后，得到了飞速发展，在国际互联网、 图像数据库、医疗图像处理等领域被普遍应用。但这种方法还存在着不少问题， 其系统的功能和效率都很有限，特别在处理速度方面，国内外的大学和科研机 构正在进行深入的探索和研究。 基于内容的视频检索系统一般包括图像、视频的预处理，图像特征提取， 图像匹配和图像索引几个部分。在预处理阶段，进行视频的关键帧抽取，把视 频转换成一系列的图像，并把这些图像进行标记。图像特征提取是指自动获得 5 第1 章绪论 每幅图像的压缩表示，主要包括图像的颜色特征、纹理特征、轮廓特征和空间 位置特征等等，在不同的应用中可以选用不同的特征，或是使用某些特征的组 合，以提高最终的检索效率和效果。图像匹配是指分析、度量图像间的相似性， 找出需要的图像，主要方法有距离度量方法，神经网络学习相似性方法，以及 近来出现的基于人类视觉的相似性模型。图像索引主要是为了提高查询的效率， 随着特征维数和图像数量的增加，顺序查找的方法已经不能胜任，需要使用高 维索引、多维空间转换、或神经网络和聚类的方法。 视频检索通常涉及到比较大的数据量和计算量，目前的系统无法满足人们 对处理速度的需求。因此，众多研究者都很关注对基于内容的视频检索系统的 性能优化。m i a oe ta l ( 2 0 0 9 ) 介绍了一种基于多核系统的并行c b v i r 系统。还 有一些研究者主要关注如何在图形处理器( g p u ) 上获得图像特征提取程序的 最佳性能。s i n h ae ta l ( 2 0 0 7 ) 在g p u 上实现了图像尺度不变特征变换( s i f t ) 程序，h e y m a n ne ta l ( 2 0 0 7 ) 也报告了一个在g p u 上的s i f t 程序实现与优化。而 我们的工作主要关注在多核系统中优化图像特征提取程序的性能。 1 3 5 多核系统中的线程调度方法 多核系统中的多个线程同时运行，它们彼此之间会互相竞争共享的系统资 源，降低性能。这种线程间