(计算机应用技术专业论文)基于cell+be的解线性方程组算法研究.pdf_第1页
(计算机应用技术专业论文)基于cell+be的解线性方程组算法研究.pdf_第2页
(计算机应用技术专业论文)基于cell+be的解线性方程组算法研究.pdf_第3页
(计算机应用技术专业论文)基于cell+be的解线性方程组算法研究.pdf_第4页
(计算机应用技术专业论文)基于cell+be的解线性方程组算法研究.pdf_第5页
已阅读5页,还剩42页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

中文摘要 随着并行计算技术的发展,并行计算成为当今计算机科学中一个重要的研究 领域。c e l lb e 是新型的异构多核处理器,它所拥有的八个协处理器为其提供了 强大的计算能力。因此非常适合进行科学计算,然而对于程序设计人员来说,如 何在其上获得最佳性能还仍然是个挑战。 各种解线性方程组的算法在科学和工程计算中应用十分广泛,并且这些算法 都需要大量的数据和计算。本文在c e l lb e 上并行迁移两种解线性方程组的算法, 高斯消去法和雅可比迭代法,并完成性能的分析与优化。根据c e l lb e 特有的优 化性能的机制,采用主从式结构,对数据进行向量化,并采用双缓冲、d m a 1 i s t 技术对程序进行优化。实验结果显示,向量化、双缓冲、d m a l i s t 技术都可以 对解线性方程组的算法在c e l lb e 上的运行产生优化作用,其中向量化技术对程 序性能的优化效果最为明显,综合应用这三种机制可以得到最好的性能。 本文研究了一些c e l lb e 的特有的体系结构,特别是内存带宽、e i b 和本地 内存。针对内存带宽的实验揭示了c e l l 处理器真实的内存性能。此外本文还提 出一个简单的算法性能模型,帮助程序员更了解程序的运行过程,使算法的有效 评估更加简单。按此模型我们将两种算法的优化结果对比,发现迭代法比直接法 更适合c e l lb e 的体系结构。 关键词: c e l lb e 解线性方程组并行算法优化 a b s t r a c t w i t ht h ei n c r e a s i n gr e q u i r e m e n tf o rt h ec o m p u t i n gc a p a b i l i t ya n ds p e e d , p a r a l l e l c o m p u t i n gh a sb e c o m eo n eo ft h em o s ti m p o r t a n tr e s e a r c ha r e a so fc o m p u t e rs c i e n c e t h ec e l lb r o a d b a n de n g i n ei sah e t e r o g e n e o u sm u l t i p r o c e s s o r - o n - c h i pp r o c e s s o r w h i c hc a np r o v i d ee n o r m o u sc o m p u t i n gp o w e rw i t hi t s e i g h tf u l l ys i m d i z e d c o r e s ( s p e ) i t sa ni d e a lc a n d i d a t ef o rs c i e n t i f i cc o m p u t i n g ,h o w e v e r , m i n i m i z i n gt h e g a pb e t w e e ni t sp e a kp e r f o r m a n c ea n ds u s t a i n e dp e r f o r m a n c ei st h ec h a l l e n g ef o r a l g o r i t h md e s i g n e r s a l g o r i t h m s f o r s o l v i n gl i n e a rs y s t e m s a r ew i d e l yu s e di ns c i e n t i f i ca n d e n g i n e e r i n gc o m p u t i n ga n dt h e ya r ca l s oc o n s i d e r e dm e m o r ya n dc o m p u t a t i o n i n t e n s i v e i nt h i sp a p e r , w ei m p l e m e n tt w op a r a l l e la l g o r i t h m so fs o l v i n gl i n e a r s y s t e m so nc e l lp r o c e s s o r ( g a u s s i a ne l i m i n a t i o na n dj a c o b ii t e r a t i o n ) a n dc o m p l e t e t h ea n a l y s i sa n do p t i m i z a t i o n t h eu n i q u em e c h a n i s m so fc e l l b e ,s u c ha s d o u b l e - - b u f f e r , d m a l i s tt e c h n o l o g yi sa l lu s e dt oo p t i m i z ep e r f o r m a n c eo ft h e p r o g r a m t h ee x p e r i m e n t a lr e s u l t ss h o w e dt h a tv e c t o r i z ed a t a , d o u b l eb u f f e r i n g , d m a - l i s tt e c h n o l o g yt h a tc a nb eu s e do nt h es o l v i n gl i n e a rs y s t e m sa l g o r i t h m s r u n n i n go nt h ec e l lb eh a v ear o l ei no p t i m i z i n g v e c t o r i z ed a t at e c h n o l o g yi so ft h e m o s to b v i o u se f f e c tt oo p t i m i z et h ep e r f o r m a n c e ,a n dt h eu t i l i z a t i o no ft h et h r e e m e c h a n i s m st o g e t h e rc a na c h i v et h eb e s tp e r f o r m a n c e w ea l s op r o v i d ec o m p a r i s o n o u rr e s u l t sd e m o n s t r a t et h a ti t e r a t i o nm e t h o di s m o r es u i t a b l eo nt h ec e l lb r o a d b a n de n g i n ea r c h i t e c t u r et h a nd i r e c tm e t h o d w e d i s c u s sa r c h i t e c t u r ef e a t u r e st h a te f f e c t sa l g o r i t h me f f i c i e n c yo nc e l lb ee s p e c i a l l y t h em e m o r yb a n d w i d t h , e i ba n dl o c a lm e m o r y w ep r e s e n tq u a n t i t a t i v ee x p e r i m e n t s o fm e m o r yb a n d w i d t ht or e v e a lt h er e a lm e m o r y c a p a c i t yo ft h ec e l lp r o c e s s o r w e t h e np r o p o s eas i m p l i f i e dm o d e lw h i c hc a l lh e l pp r o g r a m m e r sr e a s o na b o u th o wa p r o g r a mp e r f o r m st o f a c i l i t a t eo u rd i s c u s s i o no na l g o r i t h me f f i c i e n c ye v a l u a t i o n w e p r o v i d ec o m p a r i s o nb a s e do n0 1 1 1 m o d e l o u rr e s u l t sd e m o n s t r a t et h a ti t e r a t i o n m e t h o di sm o r es u i t a b l eo nt h ec e l lb r o a d b a n de n g i n ea r c h i t e c t u r et h a nd i r e c t m e t h o d k e yw o r d s :c e l l b e ,s o l v i n gl i n e a rs y s t e m s ,p a r a l l e la l g o r i t h m s ,o p t i m i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表 或撰写过的研究成果,也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 。渺沦洲凇杉:甬聃川! i j j :6 j 伞 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘鲎 有关保留、使用学位论文的规定。 特授权墨鲞态堂可以将学位论文的全部或部分内容编入有关数据库进行检 索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学t 涉沦史竹j 存攀耗:p 锈聃 签j ;! lj 甘jj :尹号钎i 6 j j 乎厂 f 佛岬 秽川心。一r y 第一章绪论 1 1 问题的提出 第一章绪论 在自然科学和工程应用领域,许多数学问题的求解最终转化为线性方程组 a x = b 的求解问题,如样条函数插值、解非线性方程组、求解偏微分方程的差 分方法及有限元方法、w i e n e r 滤波器的优化设计、i i r 数字滤波器和f i r 数字滤 波器的优化设计、经济学中的投入产出问题等等。因此,线性方程组的研究与发 展与现实应用息息相关的,近年来,新的应用需求对求解线性方程组技术提出了 新的要求和挑战。 解线性方程算法是一个传统的研究话题,在串行领域的研究已较为成熟,若 想再有显著的突破比较困难,随着多核时代的来临,如何有效地利用多核处理器, 将传统的程序和算法理论移植到新的体系架构当中,以充分利用各处理器的性 能,成为了一个热点的话题与研究方向。 在多核处理器系统中,又分为同构的多核处理器和异构的多核处理器。同构 多核处理器内部的核是结构相同的。异构多核处理器内部的核是结构不同的,每 个核集中力量完成自己擅长的特定任务。两异构多核处理器也是未来多核处理器 的发展方向,因为它更加有效地利用了处理器的性能,使处理器的每个核都达到 了物尽其用。 c e l lb e 是m m 、东芝、索尼及索尼娱乐四家公司共同研制的异构多核处理 器,具有与众不同的特性及超强的计算性能,基于c e l lb e 的刀片服务器于2 0 0 6 年问世。c e l lb e 突破性的多内核架构和超高速通信能力采用了通常用于i b m 最 尖端服务器上的先进多处理技术,大大提高了实时响应速度,能够有效地提供类 似超级计算机的性制。 每个c e l lb e 处理器中拥有九个核心,其中一个为p o w e r 架构( p p e ) ,主要 完成操作系统的运行及应用程序运行期的管理;其余八个协处理单元( s p e ) 为 向量处理器架构,只用于计算l z j 。 由于c e l lb e 是一个较新型的处理器,所以面临着传统的程序和算法向其上 移植的问题,本课题主要是为了给解线性方程组算法向这种新体系结构计算环境 的迁移奠定理论和实践基础,同时也为更多的计算密集型科学计算提供理论和技 术的支持,并对c e l lb e 的适用范围进行探索。 第一章绪论 1 2 本论文的主要工作 由于传统的解线性方程组算法都是基于单核机器的串行结构实现的,所以要 在充分了解传统解线性方程组算法的基础上,筛选具有代表性的算法进行并行 化,本文主要讨论两类算法基于c e l lb e 的特殊结构和性质的优化,探寻解方程 组在c e l lb e 上的最佳解法。 本文选取高斯消元法和雅可比迭代法作为消去法和迭代法两类算法的代表 进行并行化并向c e l lb e 迁移。 对于高斯消元法,应用并行策略解决算法原有的各行之间的依赖关系,然后 将计算分散到各s p e 上,高效传递数据,合理安排使每个p p e 和s p e 的性能得 到充分利用,基于c e l lb e 进行优化。 雅可比迭代法不存在行依赖,所以可将系数分配给s p e 进行计算,在决定 了系数矩阵的分配方式后,需要针对c e l lb e 的特殊结构和功能来对算法进行优 化设计。 在c e l lb e 上的优化主要有: 尝试对系数矩阵进行向量化,以期待能够充分发挥s p e 的性能。 应用多缓冲机制来运行两种算法。 应用d m a 1 i s t 机制来运行两种算法。 在应用单种机制达到优化效果的前提下,综合运用多种机制来运行两种算 法。 对所做的实验数据进行分析总结,以期得出两种算法在c e l lb e 处理器上最 合理的运行方式,分析c e l lb e 的性能。 1 3 论文组织结构 本文从c e l lb e 和解线性方程组算法的背景,解线性方程组算法向c e l lb e 上的移植的设想的提出和本论文的主要工作出发,逐步讨论解线性方程组算法在 c e l lb e 平台上运行的最佳方案。 第二章叙述了相关的背景知识与研究现状,主要介绍了c e l lb e 硬件以及编 程的基础知识和解线性方程组算法的背景知识。 第三章论述了高斯消去法向c e l lb e 上移植的设计方案及相关技术的介绍和 实现效果和数据分析。 第四章讨论了雅可比迭代法向c e l lb e 上移植的各设计方案的实现效果和数 据分析。 第一章绪论 第五章是两种算法加速比的对比分析以及对c e l lb e 本身的性能分析。 第六章是对工作的总结和对未来工作的展望。 第二章背景知识及研究现状 第二章背景知识及研究现状 2 1 解线性方程组算法的背景知识及算法选择 解线性方程组算法是一个传统的研究话题,目前已经存在许多典型的解线性 方程组算法,许多年来,国内外众多学者为此做了大量研究,取得了许多优秀成 果,其中最典型的是众所周知的克莱姆法则和高斯消元法等直接方法。 克莱姆法则适用于线性方程组有唯一解的情况,即系数矩阵a 可逆,但计 算量十分巨大,不适合大线性方程组的求解。高斯消元法的计算量也很大,特别 是当线性方程组的规模较大或系数矩阵是大稀疏的情况时,高斯消元法的计算量 将很大。因为高斯消元法虽然计算量大,但是在非坏情况下,经过有限次的运算 总能得到精确解,所以我们选择它向c e l lb e 迁移。 另一类方法是迭代法,比较常用的有雅可比迭代法、g a u s s s e i d e l 迭代法、 超松弛迭代等和共轭梯度法。用迭代法求解线性方程组,比较适合大稀疏的情况。 一般来说,对线性方程组的系数矩阵有些条件限制。比如:对于对称正定的 系数矩阵a ,g a u s s s e i d e l 迭代法收敛但j a c o b i 迭代法却不一定收敛;同样情况, j a c o b i 迭代法收敛时,g a u s s s e i d e l 迭代法不一定收敛。超松弛迭代法是 g a u s s s e i d e l 迭代法的一种改进方法,只要合理选择松弛因子,其收敛速度明显 加快,但并不是对任意线性方程组,s o r 迭代法都收敛。共轭梯度法对于解大 型稀疏矩阵的线性方程组,是一种有效方法;对于非坏条件问题,其收敛速度很 快,但对于矩阵a 的条件数较大时,其收敛速度很慢。 迭代法总的来说都有一定的局限性,不是在任何时候都能收敛,或者收敛速 度太慢。g a u s s s e i d e l 迭代法、超松弛迭代等和共轭梯度法实际上都是加入了变 量或者一定参数的雅可比迭代法,在一些情况下能够加速收敛。本文选择雅可比 迭代法向c e l lb e 迁移,用参数控制迭代次数避免收敛过慢。 2 2 国内外研究现状 解线性方程组广泛的存在于科学和工程计算领域,如计算机图形学等。现实 生活中的很多问题都可以抽象为解线性方程组问题,所以国内外学者对该算法的 研究一从未间断。这种研究可以分成两大类,第一类是对算法本身的研究,在传 4 第二章背景知识及研究现状 统的算法中加入变量,边界等条件以求得算法复杂性的降低,正是这种研究使得 解线性方程组的方法更加多样化,也产生了如本文2 1 节所列出的各种方法,可 是这种优化的效果毕竟是有限的,当方程组的规模很大时,仍需要较长时间的运 算。第二类是用并行计算的方式解决这类问题。 由于解线性方程组计算密集的特点,在并行计算的发展过程中,国内外工作 者就其进行了大量的研究,在不同的环境中以不同的方法对其实现并行化,包括 共享内存的并行、运用消息传递模型的并行和在p v m 上的并行实现。 在对高斯消元法的研究中,分别实现了多进程和多线程两种方式的并行消 去,研究表明,多线程的方式扩展性较差,对实现平台的依赖性较大【3 】。 在并行化过程中,数据划分有两种策略:面向行的算法并行和面向列的算法 并行。在面向行的算法并行中,在消去时有较大的广播通信量,尤其是当数据规 模很大时。而面向列的并行算法刚好相反【刚。 在面向行的算法中加入流水线操作,可以实现计算和通信的并行化,但是它 本质上是g a u s s j o u r d a n 消去的并行化。s g e 算法对矩阵采用分治策略,简化了 回带求解的过程,回带求解在整个算法中占用的时间较少,但该算法只是部分选 主元【5 】。另一种方案采用循环数据映射、流水化的通信模型,得到好的负载平衡, 但它串行选择主元,在消去时需要较大通信开销【6 j 。本文采用的方法在一定程度 上解决了上述问题。 对于各种迭代法的并行化研究和高斯消元法有很多类似之处,不同的是,因 为迭代法单次迭代之内没有行依赖,所以对数据的划分方法不局限于行和列,还 有分块法等等。 整体来说对于解线性方程组的算法,无论采用哪一种并行模型,在数据量过 小的时候并行计算的时间比串行计算的时间还长,因为通信的开销在程序执行时 间内占的比重较大。随着数据量的增大,并行计算的优势越发突出,但是通信开 销是一个不可忽视的因素。所以,我们研究的重点就是通信问题,如何尽可能跟 少的通信,如何将通信与计算并行化。 计算节点的运算能力也影响着并行计算的性能,参与运算的计算机硬件配置 越好,c p u 主频越高,计算性能越好,但是如果一味追求高性能硬件价格将大 幅增加,需要权衡。在c e l lb e 中,s p e 就是计算节点,这些s p e 都是s i m d 处 理器,如何充分开发利用它的运算能力是我们研究的另一个重点。 c e l lb e 作为一款崭新的异构多核处理器,提供了强大的数据传送和运算能 力。国内外各研究机构针对c e l l 处理器也进行了大量的研究工作,主要包括三 类。 第一类是针对c e l l 处理器本身的性能进行的研究,主要是分析它的特点和 第二章背景知识及研究现状 能力,并将c e l l 处理器与其他的处理器进行对比。第二类是开发针对c e l l 的编 程语言的库函数,如c o r e p y 为c e l l 编程提供p y t h o n 库函数,r a p i d m i n d 是供特 殊类型用以支持数字图像处理和游戏编程等的库函数。基于c e l lb e 的编程往往 需要程序员考虑很多底层的操作,比较复杂,这些库函数以及并行加速模型a l f 将简化基于c e l lb e 的开发过程。第三类就是c e l lb e 的开发,其中很大一部分 是各类算法在c e l l 上迁移实现p j 。本文的工作就属于第三类研究。 解线性方程组算法作为一种常用需要大量的数值计算,而c e l lb e 拥有的强 大计算能力正使它适合解决这类计算密集型问题。 2 3 关于c e l lb e 的基础知识 p o w e r p c 处理器( p p e ) p p e 是主处理器,包含2 个6 4 位p o w e rp c 架构精简指令集的处理核 心,以及一个传统的虚拟内存子系统。p - p e 主要运行操作系统,管理系统资 源,以及进行控制处理。它用时支持还支持v e c t o r s i m d 指令集。p p e 支持 双线程同时执行,可以看作共享数据流的双处理器。 协处理器( s p e ) c e l l 含有八颗协处理器主要用于被优化执行p p e 分配的任务,包含一 个2 5 6 k b 的局部存储器。这个局部存储器主要用来存储指令和数据,并且 是软件可控的。包含1 2 8 个寄存器。s p e 支持一套全新的s i m d 指令集,其 依赖异步d m a 操作完成主存和局部存储器之间的数据和指令传输。s p e 对 主存进行d m a 操作使用的是p o w e r p c 的有效地址空间。s p e 之间d m a 操 作通过将s p e 的本地存储的地址空间映射到p p e 的有效地址空间来完成。 互连总线( e i b ) 将p p e 和八个s p e 通过e i b 紧密地与主存储器和i o 连接到一起。由四 个环形结构的数据总线和一个树形结构的命令总线组成。e i b 由4 个1 6 字 节的数据环组成,每个环可以同时传输1 2 8 字节。每个处理器可以同时发送 和接收数据。这样结构使各s p e 可以按流水线的模型划分作业,而充分地 利用e i b 与处理器之间的连接方式可以达到最好的传输效果。 内存控制器( m i c ) 内存接口控制器提供了e i b 和物理内存之间的接口。主存的每个3 2 位 通道每秒能传输1 2 8 g b 数据。c e l l 处理器支持双通道,即能达到2 5 6 g b s 的带宽。 宽带引擎接口( b e i ) 6 第二章背景知识及研究现状 管理e i b 与i o 设备之间的数据传输,并提供i o 地址翻译和命令处理、 内部中断控制器和总线接口。b e l 支持两路的i o 通道。可以利用e i b 连接 到另外的c e l l 芯片。 图2 - 1c e l l b e 的结构图 如图2 1 所示,c e l lb e 处理器包括一个基于p o w e r p c 架构的控制处理单元 p o w e rp r o c e s s i n ge l e m e n t ( p p e ) 以及8 个s i m d 的协处理器单元一s y n e r g i s t i c p r o c e s s i n ge l e m e n t s ( s p e ) ,以及用以连接p p e ,输入输出单元以及s p e 的高速 环形数据总线- - e l e m e n ti n t e r c o n n e c tb u s ( e i b ) 。c e l lb e 同时还提供了d m a 指 令和控制机制以用于在不同的处理单元之间提供高效的通信。p p e 和s p e 均为 r i s c 结构,指令字长为3 2 位,寻址空间为6 4 位。s p e 提供最高1 2 8 位宽的s i m d 的数据通路。工作在3 2 g h z 主频下,单个s p e 对8 位整型可提供5 1 2b i l l i o n 的峰值计算速度,对单精度浮点可提供2 5 6g f l o p s 的峰值计算速度。 为了提高内存访问速度,c e l lb e 采用r a m b u sx d rd r a m 内存,提供2 个 3 2 位的数据访问通道,每个通道的访问速率为1 2 8 g b s 。为了提高i o 访问速 度,在c e l lb e 中采用了高速、可配置的i o 接口一7 个发射通道和5 个接收通 道的r a m b u sp r a cf l e x l o ,f l e x l o 工作5 g h z 下时,其发送带宽和接收带宽分 别为3 5 g b s 和2 5 g b s 。 p p e 和s p e 都是基于r i s c 架构,双发射的s i m d 处理器。c e l lb e 中所有 的处理单元,i o 控制器,内存控制器都通过高速的e i b ( 4 路1 2 8 位宽的环形总 线) 互联。x l o 接口提供与r a m b u sx d r 内存的高速互连,f l e x l o 提供了高速 i o 通道。p p e 是一个兼容p o w e r p c9 7 0 架构的两路并发多线程处理器,包含一 第二章背景知识及研究现状 个3 2 k b 的l 1c a c h e ( 3 2 k b 的数据c a c h e 和3 2 k b 的指令c a c h e ) 。2 5 6 k b 的l 2 c a c h e 以及一个v m x ( v m x 是p o w e r p c 上的a l t i v e c 多媒体扩展,a p p l e 称为 v e l o c i t ye n g i n e 。v m x 本身就是一个向量处理单元,或者说是类似于i n t e l 的s s e , s s e 2 的s i m d 扩展。) 单元。操作系统运行于p p e 上,p p e 负责对s p e 进行调 度,而s p e 则负责主要的计算工作。s p e 直接访问本地的l o c a ls t o r a g e ( l s ) 。它 通过d m a 方式访问主存,由d m a 负责将指令和数据搬到l s 。这种方式能够有 效的减小内存读写延迟对处理器利用率的影响,因为s p e 的计算和d m a 传输 可以并发地进行。s p e 是一个高度可配置的处理单元,s p e 可以被配置成不同的 运行方式和存储保护模式。在存储保护模式下,p p e 和其他s p e 不能访问该s p e 的l s ,从而在硬件层次上提供了安全机制。 2 3 1c e l lb e 软件开发环境 c e l lb es d k 是专门为在c e l lb e 体系架构上进行软件和系统开发以及性能 分析提供的一个完整的工具包。它运行于l i n u x 系统之上,提供了高效的开发工 具和开发库,仿真环境一i b mf u l l s y s t e ms i m u l a t o rf o rc e l l ,以及大量的技术文 档。 c e l lb es d k 为基于c e l lb e 架构的软件开发,提供了完整的开发环境和运 行环境。 c e l lb es d k 包括以下内容: 1 s p et i m i n gt o o l :用于观察和分析程序在s p e 上执行时,其指令流水线 的状态。 2 i b mx l cc c + + a l p h ae d i t i o nf o rc e l lb r o a d b a n de n g i n e ( c e l lb e ) p r o c e s s o r :i b m 开发的针对c e l lb e 处理器的c c 抖编译器。 3 c e l lb r o a d b a n de n g i n es p em a n a g e m e n tl i b r a r y :为基于c e l lb e 结构编 程模型的应用提供s p e 的线程库支持。 4 c e l lb e 例程:包含了丰富的基于c e l lb e 的例程以及一个详细的手把手 的教程。 5 i b mf u l l s y s t e ms i m u l a t o rf o rc e l lb ep r o c e s s o r :提供对基于c e l lb e 处 理器的系统级的仿真环境,包括c p u ,内存以及外设的仿真。在 s y s t e m s i m 中,可以运行一个完整的l i n u x 操作系统,并且在此基础上 运行和测试基于c e l lb e 的应用程序。s y s t e m s i m 能够对c e l lb e 进行功 能和性能的仿真和分析,并且支持处理器层次的仿真,如中断处理, c a c h e ,总线等。 6 g n ut o o l c h a i nf o rc e l lb e :s p e 和p p e 的交叉编译工具,这是基于g n u g e e 的交叉编译器。前面提到的x l c 在功能上基本兼容这个t o o l c h a i n , 第二章背景知识及研究现状 但是不支持g c c 的某些特殊的编译选项。总的来说,经x l c 编译后的可 执行代码的效率高于g n ut o o l c h a i nf o rc e l lb e ,因为x l c 是专门针对 c e l lb e 所设计的。 同时,i b mf u l l s y s t e ms i m u l a t o rf o rc e l lb e 提供了一个全系统的c e l lb e 仿 真环境,开发者可以在s y s t e m s i m 中运行自己开发的程序,察看结果,并且进行 调试和性能分析。 2 3 2c e l l 编程模型 在c e l l 上开发并行程序需要考虑c e l l 的硬件特性以尽可能利用c e l l 的并发 数据处理能力和极高的总线速度。编成模型即是并行程序和并行系统硬件之间的 桥梁,并在程序的执行效率和编写效率上提供平衡。以下介绍最适合c e l l 上完 成的并行编程任务的几种类型。根据对c e l l 上编程模型的分析可以发现在c e l l 上应用的实现与分布式环境的中m p i 接口应用领域有很多相似之处。而为消息 传递机制设计的m p i 接口在c e l l 上的实现将为各种应用模型的实现带来很大的 便利性。 服务器客户端模型 在这种模型下,p p e 充当任务的分配和仲裁者,起到调度各个任务在s p e 间的调度和负载均衡。从s p e 收集计算结果和将数据发射至各个s p e 的任务。 s p e 为真正的任务负载节点。不断访问p p e 以获取任务和同步数据。p p e 不执 行计算任务,仅承担资源的分配和任务的划分与结果收集。 流水线模型 在流水线模型下,数据在各个s p e 之间以流水线的方式在各个s p e 间传递, 每个s p e 对数据执行的特定的计算任务。各个处理器按一定的顺序从流水线上 前端处理器获得数据并将处理结果发送给后继的处理器。最后,由p p e 获取流 水线处理结果。 o 数据并行模型 c e l l 处理器被设计为p o w e r p c 指令集的处理器。标量数据只有在通过向量 化后才能利用p p e 上的p o w e r p c 向量指令和s p e 上的s 1 m d 向量化指令。在处 理节点完成计算后,由处理器计算完毕再进行宽数据字到正常指令数据字长的转 变 9 第三章高斯消元法的设计和实现 第三章高斯消元法的设计和实现 第二章介绍了c e l l 处理器的基本架构和处理器间的数据交换模式,可以看 到,处理器的提供了丰富的特性非常适合消息传递并行环境的建立。在本章中, 我们将分析如何将传统的高斯消元法并行化迁移到c e l l 处理器上,如何划分数 据,以及并行的策略。 c e l lb e 性能的发挥,很大程度上要依靠对程序的优化,这是由c e l l 的硬件 特性决定的。所以算法迁移后的优化很重要,一方面要是原有的应用合理的并行 化,运用多个s p e 进行运算,并且让各个s p e 及p p e 之间的同步和通信代价保 持在个较低的水平,这个角度可以称之为c e l l 上的并行优化设计,另一方面 对分配到某个s p e 上的计算任务进行优化,让这个任务在单个s p e 上达到较高 的运行速度。 在优化的基础上,分析算法的加速比以及加速优化的瓶颈,更好的深入的理 解c e l lb e 的体系结构。 3 1 算法简介 高斯消去法是一种直接方法,在这种方法中,只包含有限次的四则运算,通 过有限次的计算,能直接得到方程组的精确解。所以它是一种常用的解线性方程 族的算法,具有较高的精度和稳定性,但时间复杂度也较高,并且随着方程阶数 的增长,时间复杂度增长较快,因此,具有很高的优化的价值。 3 1 1 传统串行高斯消元法 高斯消去法的基本思想是利用线性方程组初等变换,即用一个不为零的数乘 一个方程后加至另一个方程,使方程组变成同解的上三角方程组,然后再自下而 上对上三角方程组求解,这样高斯消去法可分成“消元”和“回代”两个过程,为了 保证每次消元结果的正确性,系数矩阵的主对角线元素不能为零,所以在消元之 前还有重要的准备工作,那就是选主元。 将要解的线性方程组表示为a x = b ,a 和b 的元素分别记为a 和b 。 选主元的目的不仅是避免发生除零,更重要的是让计算结果更加精确,所以 我们选择的主元应该是同列当中的绝对值最大的数,找到同列中主元最大的行后 1 0 第三章高斯消元法的设计和实现 和当前行进行行交换。 有了主元最大的保障,就可以开始消元了,消元过程顺序代码如下, f o r ( i - 0 ;i i 一1 ;i + + ) f o r ( j = i + l - j n ;j + + ) m = a d 】 i 】a i 】 i ; f o “k - i ;k n ;k + + ) a j k = a d 】 k 】- a i l k 木m ; b j - b d - b 【i 木m ; 消元的时间复杂度为o ( n 3 ) 。消元结束的时候,整个系数矩阵是一个严格上 三角矩阵。 回代运用如下迭代公式( 3 1 ) ,得到方程的最终解。 誓= 下面是选主元高斯消元法的流程: 图3 1 选主元高斯消元法的流程 l l 公式( 3 1 ) 。包一盱 = k 第三章高斯消元法的设计和实现 3 2 算法设计 3 21 高斯消元法的并行策略 一 已被清零 圉3 - 2 选主元高斯消元法的并行实现 n i + l 元素 包括b 【l 】 待修改行 观察高斯消去法的顺序消元流程可以看出在修改第i + l 行到第n 行数据的部 分有明显的并行空问,修改这n i 行数据时只需要第i 行数据以及待修改行本身, 与其他待修改行没有依赖关系,也没有对共享变量进行写操作或者独占操作,不 会出现资源冲突、读写错误或者死锁等情况,可以并行执行。所以,只要先向待 修改行广播第i 行数据那么消元的过程就可以并行执行。 3 22 数据划分 p p e 将数据划分成数据无关的子数据块,可以将各子数据块分配给各个s p e 分别进行计算,让8 个s p e 充分的调度起来,提高计算的速度。 如果将数据按顺序分成p 块,如图3 - 3 的带状划分,那么在程序运行的过程 中会产生严重的负载不平街现象,在前n p 行完成消元后,s p e 0 就处于闲置状 态,随着程序运行的进程,参与计算的s p e 越来越少,造成大量的资源浪费, 也增加了无谓的等待时间。 第三章高斯消元法的设计和实现 s p e o s p e l s p e 2 图3 - 3 带状划分 p 是s p u 个 数 为了解决上述问题,本文采用循环划分的方法划分数据,如图3 4 ,每个s p e 将在较长的一段时间内工作,使得各个s p e 的工作负载相等。 s p e 0 分到第0 、r e p 、2 n p 、行,即起始行为0 ,步长为r e p 的所有行, 而s p e l 分到的就是起始行为1 步长为r e p 的所有行。所以在计算时每个s p e 只 要得到关于起始行的信息,就可以通过简单计算得到所有数据的地址,简化了 p p e 和s p e 之间的消息传递。 图3 _ 4 循环划分 行 r p 是s p u 个 数 以上的并行化设计都是针对消元过程的,而消元之前的选主元同样可以并行 d p 行。 咖 m 枷 第三章高斯消元法的设计和实现 化。首先,找到对选定主元后,我们可以不进行行交换,而是记住该行的首地址, 以便广播到各个s p e ,即节约了大量交换所用的时间,又为并行化创造了条件。 每个s p e 可以在计算的同时寻找下一次操作的主元,记录这个局部主元的 值和地址,在写回运算结果时一同传给p p e ,这样p p e 就可以在几个局部主元 中快速选出主元并将其广播给各个s p e 进行下一次运算。但是第一次选主元时, 由于还没有进行并行消元,所以由p p e 选主元。 3 2 3 流程设计 c e l lb e 有一个p p e 主处理器和8 个s p e 协同处理器,p p e 用来运行操作系 统和控制代码,s p e 用来运行运算密集型的应用程序,这样能够有效的客服功耗 壁垒。 针对c e l lb e 的特殊体系结构,对p p e 和s p e 设计了不同的流程,它们相 互配合完成了整个程序。 首先,在p p e 端如图3 - 5 ,p p e 从文件中将系数矩阵读入内存,完成初始化 工作和数据划分,寻找第一列的主元,将它的地址广播给所有s p e ,启动s p e 开始计算,等待所有s p e 完成运算并写回结果后,在局部主元中选出主元,继 续广播主元地址,等待计算结果,直到系数矩阵成为上三角矩阵,向回代入求出 方程组的解并将结果写回文件。 否 图3 5p p e 端流程图 1 4 囱 第三章高斯消元法的设计和实现 其次,在s p e 端如图3 - 6 ,每个s p e 将收到广播的主元地址,通过d m a 传 输将这一行读入s p e 的本地内存中,将p p e 划分的属于自己的数据逐行读入本 地内存进行消元计算,将结果写回内存中,直到所有的数据处理完毕后,向p p e 发送消息表示工作已完成。 徐爪 足 泌竺罗 l 否 1r 读取一行 l 写回结果 通知p p e 数据到l s j l 1 r 对这行数据进 r 结束、 行消元计算 图3 - 6 s p e 端流程图 从以上流程中可以看出,p p e 和s p e 间存在大量的数据传输。除了直接应 用d m a 传输外,还可以应用c e l lb e 特有的多种传输机制,比如d m a 1 i s t ,双 缓冲和m a i l b o x 等机制来提高数据的传输效率,从而使程序整体的性能得到提 升。 3 3c e l lb e 的特殊性能的应用讨论 c e l lb e 作为一款新型的处理器,其独特之处不仅仅在于它的一个主处理器 和八个协处理器的构造上,还在于它提供了m a i l b o x 、双缓冲,d m a l i s t 等高效 数据传输机制,以及s p e 强大的向量处理能力。如果能够充分利用这些性能, 将大大的提高程序的执行速度。 第三章高斯消元法的设计和实现 3 3 1 向量化的应用 因为c e l lb e 的s p e 本身是一个向量处理器,s i m d 是s p e 上必不可少的优 化步骤。如果能够将数据以向量的形式进行计算将大大提高性能,具体高斯消去 算法。p p e 是通过v e c t o r s i m d 多美体扩展指令集来进行向量运算的。内存中的 数据是以数组的形式存储的,只要将向量指针指向数据的开始地址就完成了对数 据的向量化,运用c e l l 提供的v e ca d d ( ) 等标准函数可以一次计算多个数据, 提高运算速度。 s p e 上的向量运算是通过s p e 指令集来进行的。与p p e 不同的是,s p e 有 1 2 8 个向量寄存器来进行向量运算,它也可以进行标量计算,但是操作数必须是 1 6 字节对齐的,否则s p e 在执行运算的时候会先对数据进行移位操作,使之1 6 字节对齐,然后进行s i m d 运算,最后再把运算返回的向量转换为标量,这个过 程无疑引入了很多额外的转换开销,所以,为了更好的发挥s p e 的性能,在s p e 上要使用s i m d 代码。数据要以1 6 字节对齐,其上的运算也均采用向量运算, 由于高斯算法的计算密集性,s i 加应该能显著的提高算法的效率。 3 3 2 多缓冲的应用 由于s p e 的局部缓存( l s ) 只有2 5 6 k b 大小,无法一次处理大量的数据, 这就造成了大量的p p e 和s p e 之间的数据传输,降低了系统的性能,为了解决 这一问题,c e l lb e 提供了双缓冲机制。双缓冲机制的原理如图3 7 所示,当一 个s p e 需要从主存读取大量的数据时,则可以遵循以下的步骤完成: 1 初始化从d m a 到l s 的缓存b 0 的传输。 2 初始化从d m a 到l s 的缓存b 1 的传输。 3 等待对缓存b 0 的传输完成。 4 计算缓存b 0 中的数据。 5 初始化从d m a 到l s 的缓存b 0 的传输。 6 等待对缓存b l 的传输完成。 7 计算缓存b 1 中的数据。 8 如果仍有数据传输的话则重复步骤2 到7 。 1 6 第三章高斯消元法的设计和实现 发起d m a 传输到 缓冲区b 0 发起d m a 传输到 缓冲区b l 等待b 0 传输完成 使用b o 数i 1 等待b 1 传输完成 1 卜叫 据进行计ji 图3 7 双缓冲机制原理图 使用b

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论