（计算机应用技术专业论文）基于多核处理器串行程序并行化改造和性能优化.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 早期并行程序的开发基本应用在超级计算、高端服务器等特殊应用领 域。随着i n t e l 和a m d 多核处理器市场占有率的上升，通过提高c p u 频率 来提升程序性能的时代即宣告结束。但是重新开发适应多核平台的应用程序 不仅浪费以往的大量串行程序资源，同时也无法在短期内满足用户需求。因 此多核开发从早期的专用领域开发延伸到多核通用领域并行改造。这里的多 核通用平台的并行改造是指基于通用p c 机开发环境即w m d o w s 操作系统 + i n t e l 多核处理器，将以往的大量的普通串行程序进行并行改造，实现正确、 高性能和可扩展的多核程序开发。多核通用平台开发不同于传统的并行开发 在于其平台的通用性、开发周期的快速性和系统级配套辅助工具的使用等方 面。 为此，本文针对多核通用开发，基于w i n d o w s + i n t e l 开发平台，运用并 行编程模型和方法，结合使用i n t e lv t u n ep e r f o r m a n c ea n a l y z e r ( 性能分析器) 对一串行程序进行并行化分析，提出对串行程序进行并行改造的解决方案； 接着运用i n t e l 并行时库t b b ( i n t e lt h r e a db u i l d i n gb l o c k s 线程构建模块) 对多核平台下的串行应用程序进行流程机制、循环并行化、粒度划分、内存 分配和任务调度等方面的并行改造；最后运用i n t e lt h r e a dc h e c k e r ( 线程检 查器) 、i n t e lt h r e a dp r o f i l e r ( 线程直方统计器) 对改造后的并行程序进行调 试和优化；通过对改造后的程序评测，其性能得到一定程度的提高，具有负 载均衡和正确性。 关键词：多核处理器；多线程；串行程序并行化；t b b 西南交通大学硕士研究生学位论文第页 a b s t r a c t e a r l i e rp a r a l l e lp r o g r a m m i n gw a sm a i n l yu s e di ns p e c i a la p p l i c a t i o n ss u c h a s s u p e rc o m p u t i n g ，h i g h - e n ds e r v e re t c w i t ht h ei n c r e a s i n go c c u p a n c yo f m u l t i c o r ep r o c e s s o rf o rd a i l yu s e ，t h ed a y so fi m p r o v i n gp e r f o r m a n c et h r o u g h i n c r e a s i n gc p uf r e q u e n c yi so v e r h o w e v e r , c h a n g i n ga l lt h et r a d i t i o n a ls e r i a l p r o g r a m si n t op a r a l l e lo n e si saw a s t eo f m o n e ya n da l s oc a n tb er e a l i z e di ns h o r t t i m e t h e r e f o r et h em u l t i c o r ed e v e l o p m e n th a sc h a n g e dt ot h en e x ts t a g e ：g e n e r a l p a r a l l e lr e c o n s t r u c t i o n g e n e r a lp a r a l l e lr e c o n s t r u c t i o ni sap r o c e s so fc h a n g i n ga s e r i a l p r o g r a mi n t oap a r a l l e lo n e 丽廿1c o r r e c t n e s s ，g o o dp e r f o r m a n c ea n d s c a l a b i l i t yu s i n gp a r a l l e lr u n t i m el i b r a r yb a s e do nw i n d o w sa st h eo p e r a t i o n s y s t e ma n di n t e lm u l t i c o r ea st h ep r o c e s s o r i t sm a i n l yd e v e l o p e df o rd a i l yu s e a n dt h u sr e q u i r e sq u i c kd e v e l o p m e n tt i m ea n ds p e c i a lt o o l sa st h ea s s i s t a n t ，w h i c h i st h em a i nd i f f e r e n c ef r o mt r a d i t i o n a lp a r a l l e ld e v e l o p m e n t i ti ss u i t a b l ef o rt h e p o p u l a r i z a t i o no fm u l i t c o r ed e v e l o p m e n t d e p e n d i n go nt h ec o n c e p t sa n dt h ed e v e l o p m e n tm e t h o d sm e n t i o n e da b o v e ， b a s e do nw i n d o w s 十i n t e ld e v e l o p m e n tp l a t f o r m ，t h i sp a p e ra i m e da td e v e l o p i n g g e n e r a lm u l t i c o r ep r o g r a m b ya n a l y z i n gt h es e q u e n t i a lp r o g r a mw i t ht h eh e l po f 1 1 1 t e lv t u n ep e r f o r m a n c e ，w h i c ht r i e dt of i n dt h ep o t e n t i a l p a r a l l e lp a r t t h e s o l u t i o no fp a r a l l e lr e c o n s t r u c t i o nu s i n gt b b ( t h r e a db u i l d i n gb l o c k s ) w a s p r o p o s e di nt h ef i r s tp a r t s e c o n d l y , t h ed e s i g nr e c o n s t r u c t e dt h ep r o c e s sf l o w , c y c l e ，m e m o r ya l l o c a t i o na n dt a s ks c h e d u l e ro ft h es e r i a lp r o g r a m f i n a l l y , t h e p a p e ru s e di n t e lt h r e a dc h e c k e rt od e b u ga n di n t e lt h r e a dp r o f i l e rt oo p t i m i z e t h er e c o n s t r u c t e do n e a c c o r d i n gt ot h e e v a l u a t i o n ，t h ep e r f o r m a n c eo ft h e r e c o n s t r u c t e dp r o g r a mw a sg r e a t l ye n h a n c e da n da l s ot h el o a dw a sb a l a n c e d t h i s p a p e rh a sr e a l i z e dt h er e c o n s t r u c t i o no fas e r i a lp r o g r a mm a k i n gf u l lu s eo f m u l t i c o r er e s o u r c e s i th a sc e r t a i np r a c t i c a lm e a n i n g s k e y w o r d s ：m u l t i c o r ep r o c e s s o r ；m u l t i t h r e a d ；p a r a l l e l i z a t i o no fs e q u e t i o n a l p r o g r a m ；t b b 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密中使用本授权书。 ( 请在以上方框内打“4 ”) 学位论文作者签名：嗽手哥 日期： 。7 - 6 罗 指导老师签名： 卞匆方式 日期： 口尹7 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 在p c 机上尝试将多核化改造方法应用于典型图像处理程序的并行化 改造，探讨对传统串行程序进行可并行化的分析方法； 2 针对不同的串行图像处理程序，创建t b b ( 线程构建模块) 并行化处 理模型，构建并行化改造方案； 3 将i n t e l 并行化工具引入经t b b ( 线程构建模块) 并行化后的图像处 理程序系统调试和性能优化中。 学位论文作者签名： 日期： 苇畸鸯 训牛6 刁 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 引言 多核是目前整个i t 产业较为关注的一个技术关键词。根据i d c ( 网络 媒体平台) 新近发布的预测，2 0 0 8 年度在全球市场上发售的p c 、p c 服务器 和笔记本电脑中，有8 0 的机型将配备多核处理器。而2 0 0 9 年预测几乎所 有服务器、p c 和笔记本电脑产品将全面实现多核化【14 1 。随着这些硬件产品 在多核技术上的逐渐就绪，如今整个i t 业界面临的最大挑战就是如何将原 先仅用于高端应用开发的并行编程方式推广到所有软件开发的过程中，以打 造出更多支持多线程并行化运行的应用软件，全面释放多核处理器的性能潜 力。多核是软件业发展的一种趋势。 然而将原有的串行程序全部重写实现并行化可实施性小，很难短期实 现，同时也浪费了大量资源。一个更优的解决方案就是将串行程序进行并行 化改造，从而使其适应多核平台，更好的利用多核平台资源。这样不仅可以 尽快解决多核硬件和软件之间发展的差距，同时可以带来经济效益。 1 2 本课题的研究背景 1 2 1 多核的研究现状和发展 实现并行改造有两个方案，分别是传统的并行化程序设计和针对p c 平 台通用多核并行化改造。在多c p u 处理器和集群机出现之后，并行化模型 和算法就一直在不断的发展，特别是在高性能计算、服务器和特殊应用领域， 比如医学图像、数据挖掘等。但是当越来越多的多核应用扩展到通用领域， 软件并行化开发推广到所有应用软件则存在一定的局限。 比较传统并行开发和通用平台的多核开发不同主要有几下一点：第一， 开发环境不同。传统的并行开发，硬件提供的性能满足特殊需求。而通用多 核开发针对的是i n t e l 和a m d 的双核通用平台，硬件没有提供特殊的性能； 第二，开发模型不同。通用p c 开发需要采用一个高层次抽象模型，将过多 的底层细节屏蔽起来，从而方便程序员开发。而传统的并行开发则需要对硬 西南交通大学硕士研究生学位论文第2 页 件平台有比较深的理解；第三，开发工具不同。传统的并行开发需要人工或 半人工的分析、调试或优化程序。实现多线程的负载均衡，检查多线程的数 据错误等都需要程序员设计。而针对p c 平台的多核应用开发则拥有一套从 分析、设计、调试到优化测试的配套工具辅助设计，从而提高并行程序的正 确性和可扩展性；第四，对开发人员的要求不同。传统的并行开发需要专业 的并行开发人员配备系统的专业学习和训练，掌握并行编程的各项知识和技 术，经过长期的并行编程实践。而针对p c 平台通用多核开发，则可以通过 掌握并行开发语言和工具配合使用就可以完成并行开发过程；第五，对原有 串行程序的改造程度不同。传统并行开发，比如w i n d o w sa p i 多线程开发并 行程序，对原有串行程序结构需要进行全面的改造。而针对p c 平台的通用 多核开发则仅需要对原有串行程序进行局部改造就可以实现并行化。 总之，针对通用p c 平台的多核开发提供了抽象层的开发语言，屏蔽了 底层硬件架构，通过使用系统级配套开发工具加速了多核开发进程，缩短了 开发周期，实现了低成本从传统顺序串行应用程序到多核p c 平台下并行应 用程序的改造。针对p c 平台下的通用多核开发是目前多核发展的方向。 分析工具调试优化工具 并行模型 抽象层并行时库 分析解决方案 实现程序流程、内存分配、任务调 度等并行化设计 完成对程序 并行分析 纠错和优化 通过对程序的局部改造实现并行化 + i p c 客户机传统串行软件改造平台 t上 l 传统串行程序 “用多核处理卜 _ 一 多核并行程序l 图1 1p c 客户机通用串行程序软什改造平台框图 西南交通大学硕士研究生学位论文第3 页 1 2 2 多核的应用领域 虽然多核是未来软件发展的趋势，但是从目前的情况来看，并不是每个 应用领域都要进行多核多线程并行处理。因为多核多线程就意味着增加了多 线程的创建、通信和销毁等开销。如果程序规模小或者程序串行部分占据过 多比例，这样的牺牲就是不值得的。从目前的应用看，多核程序设计主要集 中在以下三个领域 1 5 】。首先就是高性能计算机领域，如数据挖掘【1 6 】。如果计 算机的子函数查找数据可以被分解为多个线程并行查找，则可以大大减少查 找的时间，从而提高查找速度。第二个领域就是图形处理领域【1 7 】。在图像渲 染和图像压缩方面，通过对程序并行执行可以在保证图像质量的情况下提高 处理速度和效率，从而为图像应用提供更好的拓展。最后一个领域就是游戏 领域【1 引。游戏设计是典型的多任务设计，对游戏环境的显示、人物的设定、 对动作、声音、视频的多种协调，体现了多线程并行执行的特点，因此游戏 领域是最早利用多核技术的领域【1 9 】。 目前多核的应用领域随着多核处理器在市场占有率的上升而逐步进入 通用和商用领域，在数字化家庭、数字化企业和移动用户方面进行多核化处 理。 1 2 3 课题的研究现状 多核处理器很重要的一个研究领域就是图像处理。特别是当多核进入到 通用领域的并行化进程后，游戏开发和多媒体视频对图像并行化处理的性能 需求也不断加大。因此本文的传统串行程序选择图像处理领域。因为图像处 理数据量大，在嵌入式和多媒体网络等对实时性要求高的领域，计算处理需 要具有高度可并行性。因此研究图像领域的并行化具有现实意义。图像处理 的并行化分为硬件和软件两个方面。硬件方面的并行化主要通过d s p 、g p u ( 图形处理器) 、i b mc e l l ( 细胞处理器) 和i n t e l 多核平台进行加速；软 件方面的并行化主要通过对图像算法的优化设计和使用并行化库对串行程 序改造来实现性能提升。其中并行化库和编译指令主要有o p e n m p ( 共享存 储并行设计的库) 和m p i ( 消息传递并行编程环境) 。o p e n m p 和m p i 进入 商业领域仍然进展缓慢，究其原因在于其对多核扩展和多核应用仍然没有满 西南交通大学硕士研究生学位论文第4 页 足。本设计的并行化处理方式就是软件设计里对并行化库的使用这一个层面 的改造，不过本文使用的是i n t e l 多核运行时库t b b 。 1 2 4 课题的研究意义 课题的研究意义主要体现在以下三个方面： 第一：多核满足需求。多核化的时代已经到来，今年的多核处理器市场 占有率已经接近9 0 ，单核正在市场上消失。这意味着今后无论是服务器还 是台式机电脑都将采用多核处理器作为开发平台。而目前程序的开发仍然基 于单核处理器架构采用串行处理方式。软件和硬件发展的不平衡，软件性能 的亟待提升都使多核的开发变得迫切且实际。多核程序设计不同于多线程开 发。多线程机制是在单个核心上的时间片轮转的并发，而多核机制实现了在 多个处理器核心上的真正意义并行。面对变化的处理器架构，多核程序设计 的出现成为了解决软件并行问题的解决方案，因而具有社会价值和经济价 值。 第二：多核改造而不是多核开发，缩短了开发时间。多核多线程并行化 设计如果按照基于传统并行模型开发新版本并行程序，是不适用的。因为这 个开发周期太长，而且多线程的开发和调试本身就是技术难题，让对串行开 发熟悉的程序员掌握传统并行开发的知识并应用，是一个漫长的过程。因此 对现有的串行程序进行多核并行化改造，在不改变串行程序基础架构和算法 的基础上，对其局部并行化部分进行并行化设计，利用多核性能调试和优化 工具辅助改造，可以加速多核程序设计的开发时间，提高并行化效率。本文 提出的解决方案就是基于上述的并行模型思想，因此具有实用价值。 第三：本设计通过研究国内外通用的并行化设计方式，总结并行改造流 程，综合分析了并行化改造需要考虑的因素，提出的多核并行化改造的设计 模型和解决方案。 1 3 本课题的并行化模型工具 本课题设计用到的并行化模型工具主要有t b b ( i n t e lt h r e a db u i l d i n g b l o c k s 并行库) 和i n t e l 辅助并行化工具i n t e lc + + c o m p i l e r ( i n t e l 编译器) 、 i n t e lv t u n ep e r f o r m a n c ea n a l y z e r ( 性能分析器) 、i n t e lt h r e a dc h e c k e r ( 线程 西南交通大学硕士研究生学位论文第5 页 检查器) 和i n t e lt h r e a dp r o f i l e r ( 直方图优化器) 。 1 3 1 并行模型t b b t b b 是2 0 0 7 年8 月推出的c + + 运行时库，并行化级别在更高的抽象层。 其主要是基于任务的编程，而不是基于线程。它的主要关注点在性能和可扩 展，是多核处理器并行化开发的最佳选择。 与o p e n m p 和m p i 等传统并行化技术相比【2 7 1 ，线程构建模块( t b b ) 主要有以下特点【2 8 】： 1 面向任务的编程。任务是比线程更高级的并行抽象，任务和线程的 关系就好比高级语言与汇编语言的关系。在使用线程构建模块时，需要的是 任务而不是线程。这就使开发者无须关心一些具体的线程细节技术，例如负 载均衡，优化调度等，线程构建模块的底层组建已经帮助实现了这些工作， 它将通过高效的方式将任务映射到线程，并通过任务窃取( w o r ks t e a l i n g ) 来实现自动调度。这正如在用c + + 编程时无需编写p u s h p o p 指令一样，c + + 编译器将自动实现这些工作； 2 可移植编程。任何支持i s oc + + 的编译器都可以直接编译t b b 程序； 3 丰富的辅助开发工具。与t b b 结合使用的有许多辅助开发工具，例 如下面将要介绍的i n t e l 工具。这些辅助工具的配合使用将极大地的提高并行 程序的开发效率和调试效率； 线程库a p i 可在l i n u x 、w i n d o w s 或m a co s 平台间移植。 1 3 2 并行支持工具in t el 工具 对多线程调试存在很多技术难点而且调试效率低下。i n t e l 提供了多线程 调试调优的工具可以解决问题并提供优化 2 9 】。 i n t e l 提供并行支持的工具主要有： 1 i n t e lc + + 编译器：可以直接通过编译实现初步并行化程序； 2 i n t e lv t u n ep e r f o r m a n c ea n a l y z e r ：用来分析串行程序瓶颈； 3 i n t e lt h r e a dc h e c k e r ：用来检查线程的死锁和数据竞争，调试并行程 序： 西南交通大学硕士研究生学位论文第6 页 4 i n t e lt h r e a dp r o f i l e r ：用来检查线程的潜在性能问题，优化并行程序。 英特尔开发工具已经与微软v i s u a ls t u d i o 系列紧密结合，安装时可以在 v i s u a ls t u d i o 中安装插件，方便使用。 i 蔷j 毒：j 毫。苦名孝i i l i 泰，3 “咛” ：奠。；yq 呈i ! ! ! ! _ = ) “磐0 n - t 。t m f ”一r u t r im “l l e 一2 i 一 一” v o 口己 一 。? 二一 篇黑：，竺。：黯；：。悉：! 。w 。o 。：。 图1 - 2 i n t e l 工具在v i s u a l s t u d i o 中的插件示意图 1 4 本设计的预期目标和主要工作内容 14 1 预期目标 本论文的预期目标为： 1 分析出串行程序需要并行的部分，用并行编程模式和泛型编程的思 想分解程序，提出并行化解决方案； 2 用t b b 运行时库对程序进行并行化改造。用t b bp a r a l l e lf o r 并行化 l o o p 循环：用t b b改造程序流程；并行化任务调度；_ p i p e l i n e t b bt a s ki n i t t b b _ b l o e k e d _ r a n g e 设计可扩展的多线程粒度；t b b _ w o r k _ s t e a l i n g 技术实现多 处理器的负载均衡；t b ba t m o i c 实现多线程问的互斥和同步： 3 将并行程序移植到实验室双核验证机器，用i n t e lc 十十c o m p l i e r 、i n t e l t h r e a dc h e c k e r 、i n t e lt h r e a dp r o f i l e r 调试和优化并行程序，解决线程问的死 锁和处理器的过载开销等问题： 4 将调试优化后的程序在实验室双核处理器服务器上验证，对比串行 程序进行性能评测，并对评测结果进行分析。 14 2 主要工作内容 根据并行开发的特点、工作的重点和难度，本论文的主要工作分为串行 程序并行化分析、并行化程序设计、调试优化和性能评测四个方面。 串行程序并行化分析方面的主要工作内容为： 西南交通大学硕士研究生学位论文第7 页 1 、用v t u n e 分析器分析找到程序中的热点( h o t s p o t ) ，分析并行可行 性； 2 、用并行编程模型和泛型模型思想对程序的数据流、任务流进行分解； 3 、综合两种分析方法，提出完整的并行化解决方案；。 并行化程序改造方面的主要工作内容为： 1 、用t b bp a r a l l e lf o r 并行设计程序中的遍历搜索； 2 、用t b b _ b l o c k e d _ r a n g e 设计可扩展的多线程粒度； 3 、用t b bp i p e l i n e 改造程序流程： 4 、用t b bt a s ki n i t 设计并行程序的任务调度： 5 、用t b bs c a l a b l ea l l o c a t o r 并行化内存分配； 6 、用t b ba t o m i c 原子操作解决多线程间对共享存储的访问； 7 、对并行改造程序进行初步评测，并对结果进行分析。 调试和优化方面的主要工作内容为： l 、搭建并行开发环境，将程序移植到双核服务器； 2 、用i n t e lc h e c k e r 检查程序中潜在的死锁和竞争，定位目标程序，提 出解决问题的方案； 3 、用i n t e lc + + 编译器对程序进行编译，比较串行、并行的运行效率； 4 、用i n t e lp r o f i l e r 检查程序中的负载不均衡和系统开销，提出问题的解 决方案； 调试和优化方面的主要工作内容为： 1 、在双核验证机上，改变不同的评测参数，对串行程序和并行程序进 行对比评测； 2 、对评测结果进行分析。 1 4 3 课题的难点 1 、并行化程序设计的思想的构建【3 0 】； 2 、操作系统任务调度相关知识的引入； 3 、并行化方法的分析； 4 、并行化模型的建立； 西南交通大学硕士研究生学位论文第8 页 5 、多线程编程、调试和优化问题； 6 、多核工具的使用； 1 4 4 课题的创新点 本文的创新点主要体现在： 1 在p c 机上尝试将多核化改造方法应用于典型图像处理程序的并行化 改造，探讨对传统串行程序进行可并行化的分析方法； 2 针对不同的串行图像处理程序，创建t b b 并行化处理模型，构建并 行化改造方案； 3 将i n t e l 并行化工具引入经t b b 并行化后的图像处理程序性能分析、 系统调试和性能优化。 1 5 本章小结 本章介绍了多核通用领域并行开发的研究现状，本课题的研究背景和意 义。并且详细介绍了本课题的研究目标、开发模型和开发工具，同时提出了 本文设计的创新点。 西南交通大学硕士研究生学位论文第9 页 第2 章系统总体设计 2 1 多核开发平台 2 1 1 硬件开发平台一多核处理器 开发串行程序是不需要考虑底层的处理器结构等相关方面内容的，但是 多核应用程序的开发就需要首先了解硬件开发平台即多核处理器的架构。因 为只有在了解硬件结构变化的前提下，并行程序的编写才能充分利用多核的 资源。程序的运行速度和底层的c p u 处理能力是相关的。 多核处理器在同一个芯片中植入了多个处理器引擎，这样就可以提供更 高的c p u 性能、功能特性和分区能力。一般说来，多核有两种实现形式。 第一，s m p ( s y m m e t r i cm u l t i p r o c e s s i n g ，对称多处理) 。在这种情况下，开发 人员面对的是单一的抽象化硬件平台，由s m p 操作系统来决定具体由哪一 个内核来运行哪个任务，其中每个内核都是相同的，而且在同一个操作系统 的管理控制之下，共享同一个内存；第二，a m p ( a s y m m e t r i cm u l t i p r o c e s s i n g ， 非对称多处理) 。在这种情况下，各个处理器内核都运行着各自独立的操作系 统。这种独立性意味着，其中各个处理器内核既可以是同构的，并且运行同 样的操作系统，也可以是异构的并运行各自不同的操作系统【3 l 】。 同构多核s m p异构多核a m p 图2 1 同构多核s m p 和异构多核a m p 示意图 本文设计基于的i n t e l 多核处理器结构就是s m p 对称的结构，即两个核 的功能和操作是相同的。一个芯片集成两个c p u 核，具有四个物理线程。 一个芯片如果集成四个c p u 核，就具有八个物理线程【3 2 】。 西南交通大学硕士研究生学位论文第1 0 页 2 1 2 软件开发平台 软件开发可以在单核机器开发也可以在双核机器上开发，但是必须移植 到多核机器上生成执行程序和进行调试、优化。 本设计的开发平台： 系统：m i c r o s o f tw i n d o w sx pp r o f e s s i o n a ls e r v i c ep a c k2 处理器：i n t e lc e l e r o n 2 4 g 内存：5 1 2 m 开发环境：v i s u a ls t u d i o2 0 0 8 2 1 3 系统验证平台 操作系统：m i c r o s o f tw i n d o w sx pp r o f e s s i o n a l5 1 2 6 0 0 处理器：d u a l c o r ei n t e lc o r e2d u oe 4 3 0 0 ，18 0 0m h z 酷睿2 将两枚独立的处理器内核集成在一起，具有强大的双核处理能力。 所有处理器以相同频率运行，并共用6 m b 二级高速缓存和高达1 3 3 3 m h z 的前端总线，从而实现真正的并行计算。 中央处理器速度： c p u 核心频率：11 9 9 9m h z ( 原始频率： t r i a lv e r s i o n m h z ) 内存：5 1 2m bd d r 2 6 6 7d d r 2s d r a m 验证环境：v i s u a ls t u d i o2 0 0 8 选择本开发平台的原因在于：一，双核处理器为大众平台常用处理器， 因此在双核上进行验证有代表性；二，四核及八核平台可以作为今后的扩展 平台，但是因为其对操作系统和开发环境存在局限性。综上作为通用开发验 证平台，本设计选用双核处理器。 2 2 总体设计 在本质上，多核开发也就是利用多线程进行程序开发，让不同功能的进 程在不同的核上运行，或者让同一进程中不同功能的线程在不同的核上运 行。以往的算法都是面向单线程的，而多核开发要将这些算法改造成支持多 核多线程的算法。系统运行时会将多线程分配到多核处理器的多个核上，以 西南交通大学硕士研究生学位论文第1 1 页 实现性能的加速。不过和传统的多线程编程方式有所不同，多核开发对于同 步锁定等问题处理较简单，但是需要仔细分析出可并行计算的代码块来，让 多线程能够在一个任务中并行。 2 2 1 系统分析 本文需要改造一个传统串行程序，使其适合在多核处理器上多线程并行 执行。为了实现这个目标，需要首先对目标模型进行分析，找到需要并行的 代码段。然后用i n t e l 最新提出的运行时库t b b 改造串行程序，改造包括对 程序循环部分、任务调度、多线程设置、多线程同步访问和处理器负载均衡 等并行化改造。将并行的程序移植到i n t e l 双核目标机进行验证，初步检验并 行程序性能。然后用i n t e l 的编译器和工具对并行后的程序进行分析调试，优 化程序设计，进一步解决程序中潜在的死锁和竞争以及处理器开销等问题。 最后将优化后的程序再次在实验室机器上验证，比较并行程序和串行程序设 计性能，总结分析并行程序性能提高结果。 2 2 2 并行化开发运行时库的选择 并行化开发运行时库有多种选择，每个库有其各自的缺点和优点，将他 们的适用范围和特性列表【6 1 1 2 1 所示。 表格2 1 不同并行开发运行时库表格 i n t e l o1 1 强 0 p e i l 肝 n l r e a d s 任务级并行 + 数据分解支持 + 复杂的并行模式( 非l o o p ) + 并行编程模型 + 可扩展的嵌套并行支持 + 嵌入的负载均衡 十+ 亲和力支持 + 静态调度 靠 并行数据结构 + 可扩展内存分配 + 西南交通大学硕士研究生学位论文第1 2 页 i 0 为主的任务 + 用户级同步原语 + 没有编译器 + + 跨操作系统支持 + + 从表2 1 可以看出t b b 库无论是在任务级抽象并行，对数据分解的支持， 嵌套并行，支持并行模式，并行数据结构，内存分配和跨操作系统方面都是 领先于其他方式，如o p e n m p 和w i n d o w s 多线程a p i 。这也是本设计采用 t b b 作为开发运行时库的原因。 2 2 3 并行化开发工具的选择 并行程序在开发后都需要基于多核处理器的多线程调试和并行程序的 性能分析。传统并行程序的调试技术：全局断点、渐增检查点、事件分析、 静态分析。具体内容包括【6 2 】： 1 断点调试包括控制流断点、自陷断点和谓词断点； 2 事态分析法记录运行中事件轨迹信息而事后加以分析，轨迹信息主 要用于阅览和重放； 3 重放控制程序再现同步通信次序就可以重放程序运行结果。 传统并行程序的性能优化【6 3 】： 1 静态分析：采用模拟或分析方法获取源程序中有关性能参数报告给 用户，是在源程序一级进行的，其优点是可以用较小的时间代价，针对重要 的程序结构做出多种可能的性能选择，缺点是准确性较差； 2 动态分析：采用测量的方法收集程序运行中的各种性能参数，即时 或事后报告给用户；性能参数的获取可由硬件和软件提供；其优点是所提供 的数据较准确，缺点是灵活性较差； 3 性能分析方法：统计程序各部分执行时间；分析大计算量的程序段 是计算部分还是通信部分或i o 部分，从而找出性能瓶颈；根据加速的理论 值和实测值，分析计算粒度大小，负载平衡情况，通信开销和存储访问冲突 以及c a c h e 命中率等；根据效率和可扩放性分析结构与算法的组合最佳情 况等【删。 西南交通大学硕士研究生学位论文第1 3 页 传统并行调试和优化方案的开发周期不仅漫长而且需要测试的内容也 很庞杂，因而考虑采用多核开发工具缩短调试和优化周期。i n t e l 多核工具不 仅实现了上述调试和优化的功能，而且提供直观的图像参考，可以显示开发 者关心的各种参数。i n t e l 多核工具提供从串行程序分析到并行程序的线程检 错、性能分析、负载分析等全部的多线程调试优化内容，体现了它的系统性 指导和实用性的支持。本设计在比较传统并行化调试优化方法和i n t e l 多核配 套工具后，选择i n t e l 多核工具作为辅助开发。 2 2 4 系统开发模型的建立 综合分析本系统的具体实现，将开发模型显示如图2 - 2 3 3 】所示。 一分析 方法： 用泛型编程和并行编程模式 数据分解( 划分像素) 任务分解( 划分功能函数) 流水线分解( 机制) 工具 i n t e lv t u n ep e r f o r m a n c ea n a l y z e r ( 寻找热点) f 程序改造和程序重写结合( 提出解决方案) i 设计l i n t e lt h r e a db u il d i n gb l o c k s2 0 ( 基于任务的并行) ( p a r a ll e l f o r ；p a r a ll e l _ b l o c k e d r a n g e ：t b b t a s k _ i n i t ： i7 初步对性能进行评测并分析结果 v 叫调试 i n t e lt h r e a dc h e c k e r ( 检查死锁和竞争) 分析并解决 i h 优化 i n t e lc + + 编译器优化并行改造后的程序 i n t e lt h r e a dp r 。f i l e r ( 检查性能和负载) 分析并解决l _ 图2 2 系统开发模型 如果在程序并行化改造后的调试和优化阶段，发现诸如并行化粒度，数 西南交通大学硕士研究生学位论文第1 4 页 据竞争，死锁和负载均衡等问题，随时返回到并行设计阶段，用t b b 解决 i n t e l 工具分析出的错误。 2 2 5 系统开发步骤 并行步骤： 第一步：理解处理器体系，了解软件并行部分涉及到处理器的改变； 第二步：并行化可能性分析。用v t u n e 性能分析器找到热点； 第三步：并行化。用t b b 并行改造第二步分析的并行化部分； 第四步：线程调试。用c h e c k e r 找到并行程序中的错误，改正错误； 第五步：性能优化。用p r o f i l e r 优化性能。重新回到第一步，调整性能 和体系不一致的地方； 第六步：对并行改造后的程序进行评测。 2 3 本章小结 本章首先介绍了多核开发的硬件、软件和系统验证平台，接着详细介绍 了本设计的总体设计，包括并行开发运行时库的选择，开发工具的选择和系 统开发的步骤。 西南交通大学硕士研究生学位论文第1 5 页 第3 章串行程序可并行化分析 串行程序的主要功能是实现图形处理的三个主要功能函数，它们分别是 模糊化、灰度转换和c a n n y 边缘检测。通过对串行程序的并行化可能性分析， 提出串行程序并行化改造的解决方案。 3 1 串行程序的结构特征 3 1 1 串行程序总体架构 引入这个串行程序主要有四个原因：一是因为多核并行化的主要领域就 是高性能计算和图形处理，因此引入图形处理程序可以更好的发挥多核效应 1 3 4 j ；二是选择这三个函数体现了图像处理的三个层次，他们对c p u 的消耗 不同，可以从不同的角度来评测并行改造的结果；第三个原因是在嵌入式系 统中，图像的处理和传输占有十分重要的地位【3 5 1 ，同时也意味着图像处理性 能的好坏，将会成为制约整个系统的性能瓶颈。因此在处理器升级为多核处 理器后，对图像处理程序的并行化改造，具有现实意义；第四个原因是这个 串行程序是典型的传统串行程序，通过对它的并行改造，构建一个对典型程 序并行化改造的普遍解决方案。即通过对串行程序的并行化分析，并行化改 造和程序的调试优化，为其他程序的并行化提出可借鉴的并行化模型。 串行程序主要包括三个基本的图像处理功能，分别是图像模糊，图像彩 色- 灰度转换和c a n n y 边缘检测，对应着子函数b l u r c l a p 、g r e y c p p 和 c a n n y c p p 。输入图像为t i f 格式。程序框架如图3 1 所示。 西南交通大学硕士研究生学位论文第1 6 页 图3 1 串行程序系统功能模型图 串行程序流程如图3 2 所示。 图3 2 串行程序流程图 西南交通大学硕士研究生学位论文第1 7 页 3 1 2 串行程序的功能 a 图像模糊功能：通过设置模糊半径，对图像每个元素进行模糊操作。 模糊操作分为垂直方向的模糊和水平方向的模糊，由v e r t 0 矛nh o f i z o 两个函 数实现。 模糊实现框图如图3 3 所示。 模糊实现框图 f o r ( 行循环) f o r ( 列循环) k _ y = m a x ( r o w - r a d i u s ，0 ) ； k x2m a x ( c o l r a d i u s ，o ) ； 初始化像素的r g b a = 0 ) f o r ( 行循环) f o r ( i n tx2k x ；x g e t w i d t h 0 ) ；x + + ) p = i m g - g e t p i x e l ( x ，r o w ) ；获得像素 值 r + 2 p r ；g + 2p g ；r g b a 赋值 b + 2 p b ；a + 2 p a ； n p i x e l s + + ； p r = r n p i x e l s ；垂直模糊运算 p 9 2g | n p i x e l s ； p b 2 b n p i x e l s ； p a 2an p i x e l s ； o u t - s e t p i x e l ( c o l ，r o w ，p ) ；输出像素 图3 3 模糊操作实现图 b 灰度转换功能：将彩色图像转换为灰度图像 灰度函数： f l o a ti m a g e ：l u m i n a n c e ( p i x e l & p i ) 【e 1 ) r e t u r np i x e l r 宰0 3 f + p i x e l g 宰0 5 9 f + p i x e l b 幸0 1i f ， 西南交通大学硕士研究生学位论文第1 8 页 图3 _ 4 灰度操作实现图 c c a n n y 边缘检测的框图 一 c a n n y 边缘检测实现框图 、 二维循环像素 f o r ( i n tr o w = r a n g e r o w s ( ) b e g i n 0 ；r o w r a n g e r o w s ( ) 饥d ( ) ；r o w 抖) f o r ( i n tc o l 。r a n g e c o l s 0 b e g i n ( ) ；c o l s e t p i x e l ( c o l ，r o w ，p ) ； ) j l， 图3 - 5c a n n y 边缘检测实现图 三种功能函数的时间复杂度对比： g r e y s c a l e - t ( n ) = - n c a n n y e d g e ：t ( n ) = 9 n 西南交通大学硕士研究生学位论文第1 9 页 b l u r ：t ( n ) = 2 ( 2 r + i ) n r = 模糊半径 测试前，如图3 _ 6 所示。 l r l l 髑c p i r 髑记录 i 1 i ”使用辜页面文件健用记录 图3 - 6 串行运行前的c p u 情况 测试后，如图3 7 所示。 如果运行单入单出的串行程序，仅仅运行在一个c p u 上。如果多个串 行程序同时运行，则c p u 的使用是5 0 ，但是两个核的负载是不均衡的