（计算机科学与技术专业论文）多核环境下矩阵库设计与优化.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意。 签名：毯伞蟹日期：递丝血垒 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：獬锯导师( 签名) ：朝疵 日期：扣，厶，d 摘要 自1 9 4 6 年计算机问世以来，数值计算一直是计算机应用的主要领域之一， 它已经广泛应用到人类生产与生活的各个方面，矩阵运算是数值计算最基本和 经常使用的运算之一，它是数值计算的一个基础，提高矩阵运算的性能则显得 更为重要。本文把矩阵运算与多核、并行联系起来，并分别从矩阵库的设计， 矩阵库的并行化以及多核环境下矩阵库运算的优化三个方面阐述了矩阵库的实 现，具体内容如下： ( 1 ) 矩阵库的设计先在完成功能、运算需求、可维护性、面向对象、并 行化等方面确定了矩阵库的设计原则；然后结合矩阵的数学定义、c + + 的特点和 以后程序扩充的需要的基础上，给出了矩阵库的组织结构，并在m i c r o s o f tv i s u a l c + + 2 0 0 8e x p r e s se d i t i o n 平台上完成矩阵库的设计方案，最后在文中给出矩阵行 列式求值的示例。 ( 2 ) 矩阵库的并行研究在分析现有的消息传递模型、数据并行模型、共 享存储并行编程模型三种并行模型之后，通过比较重点介绍了一种面向共享内 存的多处理器多线程并行程序语言o p e n m p ，并对o p e n m p 指令、库函数和并 行化的循环选取原则作了介绍。然后在m i c r o s o f tv i s u a lc + + 2 0 0 8e x p r e s se d i t i o n 平台上用o p e n m p 并行机制对设计好的矩阵库串行程序实施并行化。同时，给 出了矩阵行列式求值的并行化处理示例。 ( 3 ) 利用i n t e lv t u n e 进行优化在介绍现有的一些优化工具之后，重点介 绍了英特尔公司针对英特尔多核处理器开发的i n t e lv t u n e 优化工具，然后在上 述平台下用i n t e lv t u n e 优化工具对并行处理后的矩阵库进行程序分析，采集大 量分析数据，以得到各种因素对运算效率的影响，并对算法进一步分析和改进。 ( 4 ) 根据本文给出的矩阵库的中的矩阵的构造、矩阵的加减乘除运算、矩阵 相等、矩阵转置、判断矩阵对称、判断矩阵对称正定、一般矩阵的秩、求逆矩 阵、求对称正定矩阵逆、求托伯利兹矩阵逆等运算，在现有的软硬件平台上完 成了串行、并行、优化后不同方面的对比实验。 通过对矩阵各种基本操作的应用和对输出结果的分析，计算结果准确，程 序基本达到矩阵基本运算的初衷；通过实例的运算比较，结果表明并行优化后 的程序的性能有改善。 关键字：多核，矩阵运算，并行计算，共享内存，o p e n m f a b s t r a c t s i n c et h ea d v e n to fc o m p u t e ri n1 9 4 6 , n u m e r i c a lc o m p u t a t i o nh a sb e e no n eo f t h em a i nf i e l d so fc o m p u t e ra p p l i c a t i o n , w h i c hh a sb e e nw i d e i yu s e di nt h eh u m a n s p r o d u c t i o na n da l la s p e c t so fl i f e i nt h en u m e r i c a lc o m p u t a t i o n , t h em a t r i xi so n eo f t h em o s tb a s i ca n do f t e nu s eo p e r a t i o n i nas e n s e , t h em a t r i xi sac o m m o ni n n u m e r i c a lc o m p u t a t i o n ，t h ep o p u l a r i t yo f w h i c hi sv e r yi m p o r t a n t t h i sp a p e rr e l a t e d m a t r i xt om u l t i c o r ea n dp a r a l l e lc o m p u t i n g , a n de x p o u n d e dt h er e a l i z a t i o no fm a t r i x l i b r a r ys e p a r a t e l yf r o mt h ed e s i g no fm a t r i xl i b r a r y , m a t r i xl i b r a r yp a r a u e l i z a t i o na n d m u l t i - c o r ee n v i r o n m e n tm a t r i xo p t i m i z a t i o n n ed e t a i l sa 托a sf o l l o w i n g ： ( 1 ) t h ed e s i g no fm a t r i xl i b r a r yf i r s t l y , c o n f i r m st h em a t r i xl i b r a r y d e s i g n p r i n c i p l 自d mf u n c t i o n , c o m p u t i n gr e q u i r e m e n t s ，m a i n t a i n a b i l i t y , o b j e c t - o r i e n t e d a n dp a r a l l e l i z a t i o n ；a n dt h e ng a v et h eo r g a n i z a t i o n a ls t r u c r t r eo fm a t r i xl i b r a r yw h e n c o m b i n e dw i t hm a t r i x m a t h e m a t i c a ld e f i n i t i o n , 酣斗c h a r a c t e r i s t i c sa n dt h en e e do f p r o g r a ml a t e re x p a n s i o n a f t e rm a k i n gc l e a rb a s i co p e r a t i o n so f m a t r i xl i b r a r y , b a s e d o nt h ep l a t f o r mm i c r o s o f tv i s u a lc + + 2 0 0 8e x p r e s se d i t i o np r o p o s es o l u t i o n so f p a r a l l e lm a t r i xl i b r a r y , a n dt h ep a p e rg a v et h ee x a m p l eo fc a l c u l a t i n g d e t e r m i n a n t e v a l u a t i o n ( 2 ) t h ep a r a l l e lr e s e a r c ho fm a t r i xl i b r a r y a f t e r a n a l y z i n gm e s s a g et r a n s f e r m o d e l ，d a t ap a r a l l e lm o d e la n ds h a r i n gs t o r a g ep a r a l l e lp r o g r a m m i n gm o d e lt h r e e p a r a l l dm o d e l ，t h r o u g hc o m p a r i n ga n da n a l y s i se m p h a t i c a l l y i n t r o d u c e s o p e n m pw h i c h i sa l la p p l i c a t i o n p r o g r a m m i n gi n t e r f a c e ( a p i ) t h a ts u p p o r t s m u l t i - p l a t f o r ms h a r e dm e m o r y m u l t i p r o c e s s i n gp r o g r a m m i n g i nc ，c + + ， a n df o r t r a no nm a n ya r c h i t e c t u r e s ，a n di n t r o d u c e si t sc o m m a n d ，l i b r a r yf u n c t i o na n d t h ec y c l es e l e c t i n gp r i n c i p l e so fp a r a l l e l i z a t i o n , t h e ni m p l e m e n t sp a r a l l e l i s mo ft h e m a t r i xl i b r a r yw h i c hh a sd e s i g n e do nt h ep l a t f o r mo fm i c r o s o f tv i s u a lc + + 2 0 0 8 e x p r e s se d i t i o n m e a n w h i l e , t h ep a p e rg a v ep a r a l l e lc a l c u l a t i n gd e t e r m i n a n t e v a l u a t i o n ( 3 ) o p t i m i z i n g 、) l r i t l li n t e lv t u n eh t r o d u c e i n gs o m ee x i s t i n go p t i m i z a t i o n t o o l s , t h ep a p e re m p h a t i c a l l yi n t r o d u c e si n t e l 矿触w h i c hw a sd e v e l o p e df o ri n t e l e p uf r o mi n t e lc o m p a n y , t h e nu s i n gi n t e lv t u n et oa n a l y s et h ep r o g r a ma n dc o l l e c t n i n f o r m a t i o n s a f t e rk n o wt h ea d 腑w h i c ha f f e c tt h ee f f i c i e n c y , w ei m p r o v et h e p r o g r a m ( 4 ) a c c o r d i n gt oa l l t h eo p e r a t i o n so fm a t r i xs u c ha sc o n s t r u c t i o n , a d d i t i o n a l ， s u b s t r a c t , m u l t i p l i c a t i o n , d i v i s i o n , e q u a l ，t r a n s p o s i t i o n , j u d g es y m m e t r i c a l a n d p o s i t i v ed e f i n i t e m a t r i x a ss e q u e n c e , i n v e r s em a t r i x ，e t c 。，a tt h ee n d ，d oc o m p a r a t i v e e x p e r i m e n t so ne x i s t i n gp l a t f o r m b a s e do nt h ea p p l i c a t i o no ft h eb a s i co p e r a t i o no fm a t r i xa n dt h ea n a l y s i so ft h e o u t p u t ，t h ec a l c u l a t i o nr e s u l t sa c c u r a t e , p r o c e d u r e sa c h i e v et ot h eo r i g i n a li n t e n t i o n a n dt h r o u g ht h ec o n t r a s tc a ns e et h ep r o g r a ma f t e ro p t i m i z a t i o no fp a r a l l e l p e r f o r m a n c eh a si m p r o v e ds i g n i f i c a n t l y k e yw o r d s ： m u l t i - c o r ep r o c e s s o rc h i p s ，o p e n m p , p a r a l l e lc o m p u t i n g , m a t r i x o p e r a t i o n , s h a r e d - m e m o r y i 目录 摘! 要i a b s t r a c t i i 第1 章绪论l 1 1 课题研究背景及意义1 1 1 1 课题背景l 1 1 2 研究意义一1 1 2 国内外研究现状2 1 2 1 矩阵计算研究现状2 1 2 2 多核处理器与并行计算简述3 1 3 本文主要研究工作与结构。6 第2 章矩阵库的串行设计8 2 1 矩阵的介绍8 2 1 1 矩阵概念8 2 1 2 矩阵的基本运算9 2 2 矩阵库的设计原则l l 2 3 矩阵库的准备1 l 2 3 1 命名ll 2 3 2 模板。1 2 2 3 3 重载13 2 3 4 浮点数1 3 2 3 5 构造函数1 4 2 4 矩阵库的结构1 4 2 5 矩阵库的实现示例l5 2 6 本章小结2 l 第3 章矩阵库并行化2 2 3 1 并行编程模型和编程环境。2 2 3 1 1 消息传递模型2 2 3 1 2 数据并行模型2 3 3 1 3 共享存储2 4 3 1 4 模型比较。2 4 3 2o p e n m p 编程介绍2 6 3 2 1o p e n m p 编程模型与简例2 6 3 2 2o p e n m p 指令和库函数介绍2 9 3 2 3o p e n m p 编程并行化的循环选取原则3 l 3 2 4 0 p e n m p 在矩阵库并行计算中的应用实例3 2 3 3 本章小结3 3 第4 章矩阵库的优化3 4 4 1 优化3 4 4 1 1 优化工具介绍3 5 4 1 2 优化工具i n t e lv t u n e 介绍3 5 4 2 矩阵库的优化3 7 4 3 本章小结一3 9 第5 章实验与结果分析4 0 5 1 实验环境介绍：4 0 5 2 试验结果4 0 5 2 1 示例结果4 0 5 2 2 对比分析4 8 5 3 试验结果分析4 9 5 4 本章小结。4 9 第6 章总结与展望5 l 6 1 研究工作总结5 1 6 2 研究工作展望j 。5 l 参考文献5 3 致谢。5 7 攻读学位期间的主要研究成果5 8 武汉理工大学硕士学位论文 第l 章绪论 1 1 课题研究背景及意义 1 1 1 课题背景 从计算机的产生到现在，数值计算【1 3 l 一直是人们研讨的一个主题，并广泛 应用于社会生活的各个方面。在数值计算里，矩阵运算【4 】是最基本的和经常使用 的运算之一。用矩阵形式来解方程组在我国古代数学著作 九章算术【5 】中已相 当成熟，但这部著作并没有建立起它独立的矩阵理论，而仅仅是把矩阵看作一 种排列形式来解决现实问题。从1 8 世纪末到1 9 世纪中期，用这种排列形式来 求解线性方程组和计算行列式等数学问题的应用日益广泛，矩阵思想在此得到 进一步的的孕育与形成。在这之后，数学家们并没有停止对矩阵的研究，在1 9 世纪下半叶，许多数学家在数学的不同领域进一步研究和发展着矩阵理论。当 今，矩阵运算在信号处理、石油勘探、固态物理、理论物理、编码理论、密码 学、数字图像处理、线性预测、自回归滤波器设计和计算机时序分析等领域都 有着相当广泛的应用。 所以，矩阵运算一直是数值计算中人们关注的热点，其性能直接影响着数 值计算性能；许多工程问题如数字图像处理、微分方程求解、最小二乘法、力 学分析等最终都涉及到矩阵运算，从某种意义上说矩阵运算是数值计算操作的 一个共同基础。 1 1 2 研究意义 目前矩阵运算大多是借助一些数值计算软件和数值计算库来完成的，它们 的可读性、稳定性、兼容性、计算效率、扩展性、准确性和可移植性不能得到 很好的保证。例如：使用m a t l a b 强大的矩阵运算功能可以方便地解决一些工程 技术计算问题，然而，在有些情况下，我们需要在c 抖环境如v i s u a ls t u d i o 下 做矩阵的相关操作，但是c + + 语言没有对矩阵操作定义专门的类，这样势必增 加了在c h 下作数值计算的难度。尽管可以用c + + 调用m a t l a b 数学库中的资源， 但必须在运行环境中安装m a t l a b 软件，这样程序员很难设计出脱离m a t l a b 的独 武汉理工大学硕士学位论文 立的应用程序。再者，m a t l a b 和c - h 是两种不同的编程语言、有着不同的运行 环境，当二者进行混合编程时，数据的传递带来的大开销降低了程序的运行效 率。 同时，随着硬件技术的快速发展，c p u 、高速缓存、内存、外存等计算机组 件为人们的程序开发提供了更好的资源，尤其多核处理器的出现为人们带来了 更低的系统开销、更高的系统性能和更低的功耗，为了充分利用好多核处理器 带来的性能提升和资源优势，就需要程序员设计适应并行模型的更高效的应用 程序。因此开展基于多核环境下的并行矩阵运算库的研究，对科学研究、工程 计算、推动数值计算的快速发展具有一定的经济价值和社会意义。 矩阵运算是数值计算中的一个重要组成部分，加速矩阵运算有着较大的理 论意义和现实意义。所以本文在分析工程数学里面矩阵运算的基础上，给出了 一种基于多核的矩阵库方案，并对其进行了优化。 1 2 国内外研究现状 1 2 1 矩阵计算研究现状 作为数值计算的一个重要组成部分的矩阵运算，通过查阅和研究，下面对 几个能够提供矩阵运算的数值计算软件或软件包进行简单介绍。 ( 1 ) m a t l a b ，m a t l a b 4 8 】数学软件是矩阵实验室( m a t r i xl a b o r a t o r y ) 研 发的商业数学软件，用于程序开发、数据分析以及数值计算。它界面友 好，易于操作，丰富的库函数做数学计算比较方便，但是使用m a t l a b 运行效率较低，执行相同功能的代码它的时间开销比c + + 大得多，程序 里面循环越多速度越慢；而且m a t l a b 的矩阵的大小取决于电脑内存 容量的大小。 ( 2 ) m e s c h a c h 6 】库，用于向量和矩阵的运算。它具有能在l i n u x 和w i n d o w s 操作系统下编译的优点。m e s c h a c h 可以解稠密或稀疏线性方程组、计 算矩阵的特征值和特征向量以及解最小平方问题。它为复数和双精度数 计算提供了接近4 0 0 个函数，效率也比较高，但是m e s c h a c h 库使用复 杂，操作不是很友好。 ( 3 ) b l i t z 【7 】库，b l i t z 是一个高性能的支持矩阵计算的c + + 类库，它支持k a i 、 i n t e l 、g e e 、m e t r o w o r k s 和v c 7 1 + + 以上等多个编译器，它还提供多维 2 武汉理工大学硕士学位论文 数组类，这些类可以是整数、复数、浮点数或者是用户定义的一些类型。 它的构造函数复杂，而且对c + + 模板的支持程度不够。对大矩阵的运算 处理也不够理想，两个最简单1 0 0 阶的矩阵相乘就可能导致编译死机。 ( 4 ) m t l 引，m t l 是一个高效的数值计算c - h 模板程序库，并对v c 6 、v c 7 、 v i s u a ls t u d i o 、g c c 等多种工具提供支持，它专注于线性代数相关的数 值处理，如各种形式矩阵( 转置，共轭，稀疏，对称等) 的生成，计算， 变换，以及与一维向量间的运算。m t l 参考文档不友好，好多具体的使 用方法都没有介绍。所以往往必须阅读其源代码后来使用这个程序库。 ( 5 ) f o r t r a n 9 1 ，f o r t r a n 是接近数学公式自然描述的高效计算机语言。语法严 谨简单易学，可以对复数和矩阵直接进行相关操作，从产生到现在，它 积累了大量可靠且高效的源代码。现在，f o r t r a n 在高性能计算和并行计 算领域广泛地应用。 ( 6 ) o s l 加】数学库，g s l ( g n us c i e n t i f i cl i b r a r y ) 为c + + c 提供了大量科 学数值运算库，使用起来比较方便，但是它对大型的数值计算不能提供 较好的操作，源码可读性较差。 数值计算软件和计算包对科学计算有着非常重要的作用，在数值计算领域 里，重多繁杂的集数学、算法和程序编制的各种数值软件包，可以跨平台移植， 与自己的开发平台集成，供科学家与工程师广泛的应用在各个数值领域，解决 工程和科研上遇到的一些计算问题。 1 2 2 多核处理器与并行计算简述 随着芯片制造工艺的不断革新，个人电脑c p u 从奔腾达到了现在的3 8 g h z 主频，但单个芯片的集成度达到了物理极限，仅仅通过提高主频来提升处理器 性能已面临技术瓶颈；而多媒体、科学计算、虚拟化、数据处理等多个应用领 域都提出了对处理器的更高性能需求，于是，各主流处理器厂商将产品战略纷 纷从提高芯片的时钟频率转向了多内核的研发。多核处理器的出现是应用需求 和科技发展的产物。 多核处理器又称作片上多处理器( c m p 【i l 】，c h i pm u l t i p r o c e s s o o ，或单芯片 多处理器，是指在一枚处理器上集成两个或两个以上完整的计算内核。1 9 9 6 年 自美国斯坦福大学首次提出片上多处理器思想和多核结构原型；2 0 0 1 年m m 公 司推出第一个商用多核处理器p o w e r 4 ；2 0 0 5 年a m d 和i n t e l 多核处理器的大 3 武汉理工大学硕士学位论文 规模生产应用；现在多核成为市场的主流，并广泛应用在多媒体计算、嵌入式 设备、个人计算机、商用服务器和高性能计算机等众多领域，多核程序设计f 3 9 】 技术及其相关研究也得到了迅速发展。 多核处理器是利用在一个芯片上将多个完整功能的核心集成，对外提供统 一服务并提高程序的并行性它具有如下优点： ( 1 ) 多核处理器通过集成多个处理核心，成倍地提高了整个处理器同时执行 的线程数或任务数，提升了处理器的并行性能，可以更有效地执行各项 计算任务，使计算性能得到了提高。 ( 2 ) 多个核集成在一个片内，极大地缩短了核间的互连线，核问通信延迟也 变低，不仅提高了通信效率，数据传输带宽也得到提高。 ( 3 ) 多核结构有效共享片上资源，动态调整频率、电压，资源的利用率得到 了提高，随着器件的减少功耗也得到了降低。 ( 4 ) 多核处理器结构较简单，采用成熟的单核处理器作为处理核心，设计和 验证周期短，易优化，扩展性强，节省研发成本，这些优势最终推动了 多核处理器的发展并逐渐取代单处理器的主流地位。 现在，随着处理器和存储器等计算机器件性能的提高和成本的下降，多处 理器系统的应用越来越受到企业界的重视，但是，在硬件迅速发展的情况下， 如果不针对多核处理器来进行软件开发，不仅多核提供的强大计算能力不能得 到利用，反而还有可能不如单核处理器好用。因为多核处理器采用的c p u 其每 个内核的主频比主流的单核通常要低一些，如果我们的程序只能发挥一个内核 的效用的话，应用程序的开发还是停留在单线程的开发模式下。那样还不如单 核c p u 好。所以在多核处理器出现后，迫使软件开发朝着并行化的方向发展。 并行计算【1 2 】是指使用多种计算资源同时进行问题求解，能有效提高计算机 系统计算速度和性能。它通过多个处理器的协同来求解同一问题，也就是把被 求解的问题分解成若干个子问题，各子问题均由独立的处理器同时计算。 并行计算处理是在串行计算概念的基础上演变过来的，具有巨大的数据处 理算和数值计能力。随着科学计算在科研和应用中发挥的作用越来越大，并行 计算被广泛地应用在科技发展、国防建设和国民经济等很多领域。 几十年的发展，并行计算的应用现在已达到了前所未有的广度和深度。这 是因为：( 1 ) 提高计算速度，即在相同的时间内解决更多或更复杂的处理问题或 在更短的时间内解决相同的计算问题。特别是对一些新出现的更细致或更大规 模的计算问题，不使用并行计算是根本无法得到解决的。( 2 ) 节省投资，用并行 4 武汉理工大学硕士学位论文 计算可以以相对串行计算较低的投入成本完成计算任务。( 3 ) 物理极限的束缚， 晶体管的集成度几乎达到了物理极限，设备和材料的制造也不可能做得无限小， 只有通过并行才能够不断提高计算速度。 当然，在数值计算方面并行处理技术还面对着许多尚待研究的问题，这此 问题主要包括以下几方面： ( 1 ) 任务分配较困难因为并不是所有问题都能够划分成足够多的并行过 程，许多问题在划分时相当困难，而且在衡量一个算法的好坏时，除了 要考虑时间的复杂性和空间的复杂性之外，还要考虑各模块之间的通信 量和处理机同步开销等，这几个因素都会对算法的性能产生影响。 ( 2 ) 很难摆脱原先串行处理方式的思维约束在原来的应用领域里面开发 应用并行算法，必然要参考或继承原来的大量串行算法，如何摆脱旧的 约束来创造并设计并行算法成为程序员颇具挑战性的任务。 ( 3 ) 现有的编程语言对并行编程的限制较大从计算机的出现到现在，计算 机语言得到了迅速的发展，从f o r t r a n 、a l g o l 、b a s i c 到p a s c a l 、 c 、c + + 等，但它们都是以串行计算机为基础设计的，因此其执行效率仍 然非常有限，得不到提高。 ( 4 ) 核之间的通信开销往往使并行处理技术效果不明显或者更差。核间的通 信问题非常重要，因此高带宽、灵活、快速的通信通道对获得高性能并 行计算十分重要。 ( 5 ) 软件是并行处理中的难题，如操作系统、编译工具、算法实现软件等等， 软件的支持对并行处理提供操作可能。并行硬件发展迅速，而并行软件 的研制却远远落后于硬件的发展速度，它已成为高性能并行计算的一个 瓶颈问题。 目前，面向大规模数据处理和科学计算的并行软件研究与开发在国际上成 为一个热点。这一方面主要是由于多核处理器经过十多年来的探索研究，已逐 渐趋于稳定了，为并行应用程序的开发提供了稳定的硬件平台；另一方面是产 业部门和学术界迫切的需要。世界各国为适应信息社会的高速发展要求都非常 重视信息技术领域的基础设施建设。美国提出了加速战略计算创新( a s c i 【1 3 1 ) 和 高性能通讯与计算( h p c c 吲) 等计划，明确提出了要发展更加高性能的计算机， 来适应太空科学、核武器设计等新技术的计算研究需求。为此，不仅许多重要 的部门而且很多科研机构和大学都建立了超级计算机中心。超级计算机中心不 仅给用户提供了高性能的计算服务和资源，为科研工作者进行重大挑战性课题 s 武汉理工大学硕士学位论文 的研究、重大科学问题的解决及重点学科的建设提供了操作平台和新的研究方 式。在美国，以四大国家实验室和美国国家航空航天局及一些知名大学联合研 制适合不同机器结构的可移植、可扩展的数值计算基础软件。欧盟以英、法、 德的工业界与研究单位合作为主也正在开发适合于各种结构的数值软件，目前 已取得了不少成果。我国在高性能计算方面也取得了一定成就，如现有“曙光一、 “神威 和“银河 三大系列的高性能计算机。 然而，面向并行处理机的大规模并行应用软件的研制却大大滞后。高性能 并行软件的研发的匮乏严重地限制着多核处理器的高效与广泛使用。当前，并 行计算发展的基本状况是： ( 1 ) 并行软件的研制发展远远落后于计算机硬件体系结构的发展。 ( 2 ) 并行计算的应用发展远远落后于并行计算技术的发展。 ( 3 ) 大规模并行处理系统的研究不再是主要的研究领域。 ( 4 ) 由高速网联成的各种类型的、规模可伸缩计算机群，将可能进一步促使 并行计算应用较大的发展。 ( 5 ) 计算系统的规模可编程性和可伸缩性已成为了并行计算机系统发展的 一对主要矛盾。 1 3 本文主要研究工作与结构 本文主要完成以下几个方面的研究工作： ( 1 ) 在深入分析、探讨国内外数值计算库和并行程序设计的研究现状基础 上，基于m i c r o s o f tv i s u a lc + + 2 0 0 8e x p r e s se d i t i o n 平台，结合数学定义 组织并实现了矩阵库 ( 2 ) 矩阵库并行化。在分析现有的并行算法之后，重点介绍了一种面向共享 内存的多处理器多线程并行程序语言山e n m p ，并在m i c r o s o f tv i s u a l c + + 2 0 0 8e x p r e s se d i t i o n 平台上结合具体例子对矩阵库实施并行化。 ( 3 ) 最后，在所开发的软硬件平台上完成大量实验，结合优化工具采集运算 数据，分析得到所设计的并行矩阵库的运算瓶颈，并对算法作进一步分 析和改进。 本文共分5 章，主要内容如下： 第l 章，绪论。本章首先介绍了多核环境下矩阵库的设计与优化研究的背 景和意义；其次简要的介绍数值计算的相关研究现状；接着介绍了国内外多核 6 武汉理工大学硕士学位论文 处理器以及并行处理技术的研究现状；最后给出了论文的主要研究内容和组织 结构。 第2 章，矩阵库实现解决方案。本章首先从数学角度下简要介绍了矩阵以 及基于m i c r o s o rv i s u a lc + + 2 0 0 8e x p r e s se d i t i o n 的矩阵库的结构。然后实现了 建立在m i c r o s o rv i s u a lc h2 0 0 8e x p r e s se d i t i o n 平台之上的矩阵库解决方案。 第3 章，矩阵库的并行化。本章围绕矩阵库的并行化展开，首先论述了并 行计算发展的基本现状；接着讨论了o p e n m p ，包括简介和基本语句两个部分； 最后讨论了基于o p e n m p 的矩阵库并行化。 第4 章，并行矩阵库的优化。本章在第3 章并行矩阵库基础之上，采集并 记录相关数据，对矩阵库进一步分析和优化。 第5 章，总结与展望。主要是对多核环境下矩阵库的设计与优化的工作进 行总结和未来工作的展望。 7 武汉理工大学硕士学位论文 2 1 矩阵的介绍 第2 章矩阵库的串行设计 “矩阵【1 5 , 1 6 】( m a t r i x ) 是由数学家西尔维斯特创用并由凯莱首先创立其概 念的。1 9 世纪5 0 年代，西尔维斯特引入“矩阵 一词来表示“一项由x 行y 列 元素组成的矩形阵列，作为矩阵理论的创立者，凯莱首先为了简化记法引进矩 阵，然后系统地阐述了矩阵的理论体系。他们为矩阵理论的初期发展做出了重 要的贡献。随后，弗罗伯纽斯等人发展并完善了矩阵的理论，形成了矩阵的现 代理论体系，使矩阵从零散的知识发展为系统的理论体系。2 0 世纪，矩阵理论 进一步得到发展，并在物理学、地理学、生物学、经济学等学科中有大量的应 用分支。 矩阵是线性代数中一个重要的内容，它可以使复杂的代数方法得到简化， 利用矩阵可以使某些散乱的计算过程变为得齐有序，运用矩阵可以使线性代数 中许多抽象的研究问题变得较为具体。矩阵是解决众多实际问题的有力工具， 矩阵及其理论现已广泛地应用于现代科技的很多领域，如自然科学、工程技术、 经济理论和管理科学，同时矩阵也是高等代数中最重要的内容之一，矩阵论已 作为高等数学的一门很重要的课程。由此看出，矩阵理论在科技发展以及教育 教学中有着相当重要的地位。 2 1 1 矩阵概念 ( 1 ) 定义 数域f 上的m 刀个数嘶( i _ l ，2 ，册, j - - 1 ，2 ，刀) 按特定的位置排列成矩阵阵 列，成为坍以矩阵，记作： a = 降 ka 其中横的一排叫做行，竖的一排叫做列，元素吩称为矩阵的第i 行第j 列的 元素。矩阵彳简记为( a g ) 或( l ，数域f 为实数域或者复数域，则称a 为1 1 1 p i 、一，、，m 8 武汉理工大学硕士学位论文 一一一 实( 矩) 阵或复( 矩) 阵。 ( 2 ) 几种特殊类型的矩阵 方阵：当矩阵( ) 中i - = - m 时，称矩阵彳为以阶方阵 行矩阵： 列矩阵： 当缸= 当如，= 巨 称为列矩阵c 也称为m 维列向量儿 零矩阵：若矩阵么的全部元素都是零，则称彳矩阵为零矩阵，记为0 或0 矩阵。 三角矩阵：当矩阵主对角线的左下方的元素全部为零的一阶矩阵称之为上 三角阵。相反，当矩阵主对角线的右上方的元素全部为零的刀阶矩阵称之为下三 角阵。 对称正定阵：若4 是方阵，q ，篁( i ，j = l 2 ，n ，i j ) ，即元素关于对角 元对称相等，则矩阵彳称为“对称阵一。若彳为方阵，且对称，则其所有顺序主 子式都大于0 ，则称彳为“对称正定阵 。 2 1 2 矩阵的基本运算 、” 矩阵相等：若同型矩阵彳= 吩0 耐和曰= 岛0 删在对应位置上的元素都相 等，即q ，= 岛j ，i = l ，i i l ；j = l ， i i 则称彳= 召 矩阵的加法：设矩阵彳= q 0 和b = 6 ：f 是掰刀阶的矩阵，么与b 的 加法( 或称和) ，记为a + b ，定义一个聊疗的矩阵 c - q ，) = 口1 2 + 包2 口2 2 + 也2 口m 2 4 - 吒2 q 厅 口2 一 口m 一 矩阵的减法：彳一b = 彳+ ( 一b ) 矩阵的数乘：一个数名与矩阵彳= q 蜊。的乘积，称为数乘，记s b , t 彳或者 么a ，表达式如下： c = q ，) = 力彳= 么a 9 、l、i，j 钆锄 山 十 + + l ，_ 月 加助 协 + + 斗 b m 砒 +反口； 口 4 r、，l 武汉理工大学硕士学位论文 矩阵的乘法：定义假设彳= ) 是一个m s 的矩阵，口= 岛， 是一个s 靠的 矩阵，那么a 与b 的乘法，记为仰，定义为一个埘n 的矩阵c = 彳占= q ，) ， 其中： q ，a j l l 5 1 ，+ 岛2 6 2 ，+ + = a t k b 村( i ：l ，2 m ；j = i ，2 ，以) t i i 矩阵的转詈： 设a = 口l ia 1 2 a 2 1 a m la m 2 口i 。 呸。 ： 。 将a 的行和列对应互换后得到的n m 的矩阵，则定义为a 的转置矩阵，记 作彳r 。 f a i - 口2 - - 1 n ，2 ：a 2 2 ：，2 k 乏。：。a mj 矩阵的行列式：它是指矩阵彳= q j 的元素按原来的相对位置构成的行列 式，记为d e t 彳或记为h ， i a i = ( 一1 ) 口l 屯q 如 公式件1 ) 在公式( 4 - 1 ) 中，墨，乞，t 是将序列l ，2 ，力的元素次序交换k 次所得到 的一个序列，号表示对式中七l ，乞，吒取遍l ，2 ，刀的一切排列求和。 伴随矩阵：假设矩阵彳= q ， ，则由行列式h 的代数余子式4 j 构成的矩阵 a = 口i ia 2 i a t 2a 2 2 口l 。口2 。 ，称为矩阵彳的伴随矩阵。需要注意，伴随矩阵 a 奉在( i ，j ) 上的元素是矩阵彳的位置( j ，i ) 上的代数余子式。 逆矩阵：假设矩阵彳是n 阶方阵，如果存在n 阶矩阵曰，它满足 a b = b a = e ，则称矩阵彳可逆，并且称为矩阵彳的逆矩阵，记作a - 1 ，也就是 b = a 一。 矩阵的秩：若矩阵的彳的1 1 个列向量中r 个线性无关，而所有个数大于r 的 列向量都线性相关。则称数r 为矩阵彳的列秩。类似可以定义矩阵彳的行秩。矩 阵彳的列秩和行秩一定相等，它也称为矩阵a 的秩，记作r a n k a = r 。 1 0 i 2 t； 武汉理工大学硕士学位论文 2 2 矩阵库的设计原则 设计矩阵库的原则如下： ( 1 ) 完成功能：矩阵库能够完成对一般矩阵的各种基本操作，如矩阵的构造、 矩阵的+ - 等运算、矩阵相等、输出矩阵、矩阵转置、判断矩阵对称、判断矩 阵对称正定、一般矩阵的秩、求逆矩阵、求对称正定矩阵逆、求托伯利兹矩阵 逆等。 ( 2 ) 运算需求：程序能够不作任何改动在单核、多核平台下运行，根据核心 数目分配线程个数，自由度高，满足不同环境的计算任务。 ( 3 ) 采用面向对象方法：随着面向对象思想与概念对计算机程序开发的影响 越来越大，c + + 语言作为程序设计语言方面的代表被广泛接受与采用，为此， 本课题充分