（检测技术与自动化装置专业论文）基于二维网格noc的矩阵求逆加速实现.pdf

基于二维网格n o c 的矩阵求逆加速实现 摘要 超级计算机的发展给了人们许多启示，依据“p c 参考系准则”提出了多 核研究的“超级计算机参考系准则”，即参考超级计算机的组织架构和发展历 史进行多核系统研究。超级计算机理念中，程序的并行化是核心问题，而并行 程序的核心是算法的并行。 高密度计算问题的本质是矩阵运算，本文在研究软件和硬件多核之间关系 的基础上，初步探索了大矩阵运算在多核系统优化实现技术，具体以大维度的 复杂矩阵计算( 分块、求逆、转置、三角化等) 为对象，研究矩阵运算的并行算 法，以及在同构多核结构下高密度计算的并行算法分解、再组合和任务分配过 程。通过均衡多核系统的核间负载，寻找最小路由路径，优化资源分配，实现 在高密度计算任务驱动下，充分挖掘多核系统并行能力，提高多核系统计算速 度的目标。 论文的主要内容如下： 1 参考设计了基于二维网格结构的n o c 同构多核系统。 2 根据并行算法的理论，比较多种已有的矩阵求逆算法，选出一种并行 度较高的基于块l u 分解的矩阵求逆方法，挖掘其并行能力。 3 遵循均衡多核系统的核间负载，减少同步开销、优化资源分配等原则， 将矩阵求逆并行算法映射到二维网格n o c 多核架构中，充分发挥多核系统的并 行能力，提高矩阵求逆的计算速度。 4 使用f p g a 原型验证最终得到矩阵求逆并行算法在同构多核中的映射所 得的加速效果。结果表明这种任务分配的方法是可行的，加速效果明显。 关键词：二维网格n o c ，同构多核，矩阵求逆，并行算法，f p g a 原型验证 t h ea c c e i e r a t i o no fm a t r i xi n v e r s i o nb a s e do n t w o d i m e n s i o n a lm e s hn o c a b s t r a c t t h ed e v e l o p m e n to fs u p e r c o m p u t e r si n s p i r e sp e o p l eal o t a c c o r d i n gt ot h e “p cf r a m e o f r e f e r e n c es t a n d a r d s ”“s u p e r c o m p u t e rf r a m eo fr e f e r e n c es t a n d a r d s a i m i n g a t m u l t i c o r er e s e a r c hi sp r o p o s e d ，n a m e l y ，r e f e r r i n gt oo r g a n i z a t i o ns t r u c t u r ea n d d e v e l o p i n gh i s t o r yo fs u p e r c o m p u t e rt oe x p l o r e o nm u l t i - c o r es y s t e m i nt h e s u p e r c o m p u t e rt h e o r y ，t h ep a r a l l e l - o p e r a t i o no fp r o g r a mi st h ec o r ep r o b l e mw h i l e t h ec o r eo fp a r a l l e lp r o g r a mi st h ep a r a l l e lo fa l g o r i t h m t h ee s s e n t i a lo fh i g h d e n s i t yc o m p u t i n gp r o b l e mi sm a t r i xo p e r a t i o n s b a s e do n r e s e a r c h i n gt h er e l a t i o n s h i p b e t w e e ns o f t w a r ea n dh a r d w a r e ，t h i sp a p e rf i r s t i n v e s t i g a t e sr e a l i z i n gt e c h n i q u eo fb i g m a t r i xo p e r a t i o nw h i c hc o u l db eo p t i m i z e d i nm u l t i c o r es y s t e m s i nd e t a i l ，u t i l i z i n gt h el a r g e d i m e n s i o nc o m p l e xm a t r i x o p e r a t i o n ( b l o c k ，i n v e r s i o n ，t r a n s p o s e ，t r i a n g u l a t i o ne t c ) a st h eo b je c t ，t h er e s e a r c h i sf o c u s i n go np a r a l l e la l g o r i t h mo fm a t r i xo p e r a t i o n ，a sw e l la sp a r a l l e la l g o r i t h m f a c t o r i z a t i o n ，r e c o m b i n a t i o na n dt a s kd i s t r i b u t i o n c o u r s eo fh i g h - d e n s i t y c o m p u t i n gi nt h ei s o m o r p h i s mm u l t i - c o r es t r u c t u r e b yb a l a n c i n gc o r e - t o 。c o r e l o a d so ft h em u l t i c o r es y s t e m ，t h em i n i m u mr o u t i n gp a t hc o u l db ef o u n di no r d e r t o o p t i m i z e r e s o u r c ed i s t r i b u t i o n ，s u c c e e d i n gi nf u l l ye x p l o r i n gt h ep a r a l l e l c a p a b i l i t ya n di n c r e a s ec o m p u t i n gs p e e do ft h em u l t i - c o r es y s t e mw i t ht h ed r i v eo f h i g h - d e n s i t yo p e r a t i o nt a s k t h em a i nc o n t e n t sa r ea sf o l l o w s ： 1 n o ci s o m o r p h i s mm u l t i c o r es y s t e mi s g r i ds t r u c t u r e 2 3 d e s i g n e db a s e do nt h et w o d i m e n s i o n a l a c c o r d i n gt op a r a l l e la l g o r i t h mt h e o r y ，t h ee x i s t i n gm a t r i xi n v e r s i o na l g o r i t h m i sc o m p a r e d a tt h es a m et i m e ，b a s e do nb l o c kl uf a c t o r i z a t i o n ，am a t r i x i n v e r s i o na l g o r i t h mw i t hah i g hp a r a l l e l i s mi ss e l e c t e d ，a sw e l la se x p l o r i n gi t s p a r a l l e la l g o r i t h m c o m p l y i n gw i t ht h er u l e s ，s u c ha sk e e p i n g t h eb a l a n c eo fc o r e - t o - c o r el o a d si n m u l t i c o r es y s t e m ，d e c r e a s i n gt h es y n c h r o n o u sc o s t ，a n do p t i m i z i n gr e s o u r c e d i s t r i b u t i o n ， m a t r i xi n v e r s i o n p a r a l l e la l g o r i t h m i s m a p p e d i n t o t w o d i m e n s i o n a lg r i dn o cm u l t i c o r es t r u c t u r e t h i sc o u l df u l l yp l a yt h e p a r a l l e lc a p a b i l i t yo fm u l t i - c o r es y s t e ma n di m p r o v et h ec o m p u t i n gs p e e do f m a t r i xi n v e r s i o no p e r a t i o n 2 4 t h ef p g ap r o t o t y p eo na c c e l e r a t i o ne f f e c to fm a t r i xi n v e r s i o np a r a l l e l a l g o r i t h mi s a c h i e v e di nt h em a p p i n go fi s o m o r p h i s mm u l t i c o r e t h er e s u l t s i n d i c a t et h a tt h em e t h o do ft a s kd i s t r i b u t i o ni sf e a s i b l ea n dt h ea c c e l e r a t i o n e f f e c ti se v i d e n t k e y w o r d s ：t w o d i m e n s i o n a lm e s hn o c ，i s o m o r p h i s mm u l t i c o r e ，m a t r i xi n v e r s i o n ，p a r a l l e l a l g o r i t h m ，f p g ap r o t o t y p e 插图清单 图3 1基于二维网格n o c 的系统结构图1 3 图3 2通讯流程图1 4 图3 。3计算节点结构示意图1 5 图3 - 4处理器发起通讯过程流程图1 8 图3 5接收数据过程流程图1 9 图3 - 6监视器2 0 图4 1基于块l u 分解的矩阵求逆m a t l a b 建模2 9 图4 2单核硬件平台结构示意图3 0 图4 3四核二维网格n o c 系统结构示意图3 0 图4 4l u 分解c + + 建模3 2 图4 5数据写入r a m 实现一3 2 图4 - 6单核时钟周期图3 3 图4 7数据输出3 5 图4 8数据接收3 6 图4 - 9块l u 分解计算顺序示意图3 7 图4 1 0数据接收3 8 图4 1 1四核三角矩阵分块求逆3 8 图4 1 2四核矩阵分块乘法3 8 图4 1 3数据传输方法一一3 9 图4 1 4数据传输方法二3 9 图4 15四核分部加速比4 0 图4 1 6四核加速比4 1 图4 1 7四核二维网格n o c 原型实验结果4 2 图4 1 8八核块l u 分解4 2 图4 1 9八核三角矩阵分块求逆4 2 图4 2 0八核矩阵分块乘法4 3 图4 2 1八核分配图4 3 图4 2 2八核加速比4 4 图4 2 3八核二维网格n o c 原型实验结果4 5 图4 2 4结果验证流程图4 6 图4 2 5任意维矩阵求逆任务划分图4 7 7 表格清单 表3 1报文格式定义。1 l 表4 。1单核时钟周期表3 3 表4 2四核、八核加速比4 4 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金目坠兰些盘堂或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者酶够晦字吼叫。年毕月弘日 学位论文版权使用授权书 本学位论文作者完全了解 金胆王业太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金日巴王些叁堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 吻恕慈 签字日期叫。年午月；o 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期：年月日 电话： 邮编： 致谢 在论文完成之际，我要对所有在工作学习期间给过我帮助与支持的老师和 同学表示感谢。 首先感谢我的导师高明伦教授，感谢他的悉心指导和一贯的鼓励支持。高 老师渊博的学识、对学科的深刻认识以及对i c 产业的深入理解使我获益良多。 他实事求是的治学态度和平易近人的工作作风对我有着潜移默化的影响，他全 面迅捷把握工作的能力和严谨的治学精神值得我一生学习。 感谢宋宇鲲老师、张多利老师、杜高明老师、耿罗峰博士和侯宁博士在项 目设计中严谨而细致的工作，感谢他们在论文选题、结构安排直至最终定稿的 过程中所给予的指导和帮助。感谢他们给我学习锻炼的机会，也给了我设计思 路和工作方法上的诸多启迪，他们对工作认真负责的态度深深的感染着我。在 此，我向他们表示由衷地感谢。 本论文的研究工作受到以下项目的资助：( 1 ) 教育部博士点基金资助项目 “集成电路n o c 体系结构中o c n 关键技术研究 ( 项目编号：2 0 0 5 0 3 5 9 0 0 3 ) ； ( 2 ) 安徽省自然科学基金资助项目“嵌入式多核s o c 基础研究( 项目编号： 0 7 0 4 1 2 0 3 1 ) 。在此表示感谢。 感谢与我一起并肩工作的项目组成员：肖福明、温海华和陈迎春等同学， 他们表现出的谦逊的学习态度和刻苦的钻研精神永远值得我认真学习。 感谢尹勇生老师、邓红辉老师、王晓蕾老师在课程上的指导。感谢毕业的 师兄师姐以及2 0 0 7 级的全体同学在学习中的帮助。感谢林微老师、贾靖华老师、 范月红、胡剑和木子一在生活上的帮助。 最后要特别感谢我最敬爱的父母，感谢我亲爱的姐姐姐夫，感谢他们用最 大的鼓励支持我顺利地完成学业，他们无微不至的关怀和激励使我有勇气和信 心面对任何困难和挑战。 4 作者：何莹莹 2 0 1 0 年3 月 第一章绪论 1 1n o c 系统简介 多核( m u l t i c o r e ) 是当代集成电路设计的战略性技术。与传统c p u 只提高时 钟速度的办法不同，多核芯片依靠多处理器并行工作提高效率。这一创造性的 理念宣告了后m o o r e 定律时代的到来，多核技术也成为后m o o r e 时代人们对集成 电路性能新的追求，“成为业界的重要里程碑 ( i n t e l 总裁语) 。 现在，人们已经意识到多核技术是提高s o c 性能的必由之路，而关键在于 芯片内部的通讯效率。目前，性能最好的计算机仍然是基于n e t w o r k 的分布式 计算机系统f 2 2 1 ，因此，人们将n e t w o r k 移植到集成电路体系结构中，提出了 n o c 的概念以提高片上通讯效率。 m p s o c 的出现有两个重要前提：首先，随着工艺的发展，在单个芯片中能 够集成多个处理器，；其次，提高芯片频率的方法已经走到了尽头，必须改变 传统依靠频率提升性能的设计思想，转向用面积换性能的发展道路。 本节首先介绍几个相关的概念： m p s o c ( m u l t i p r o c e s s o rs o c ) ：指在单一芯片上集成多个处理器的复杂 s o c ，由计算资源和通讯资源组成。计算资源完成广义的计算任务，它们可以 是微处理器或s o c ，也可以是单一功能的i p ；通讯资源负责计算资源之间的数 据通讯，可以是总线，也可以是网络或任何其他通讯方式。 n o c ( n e t w o r ko nc h i p ) ：片上网络，是使用路由器技术完成片上通讯任务 的硬件结构【2 。 比较它们的定义可以看出1 3 j ： ( 1 ) 关注重点不同。n o c 关注更多的是通讯方式，而m p s o c 贝, 0 更强调多核。 这种关注重点从通讯方式到处理方式的转变，体现了处理器结构和s o c 结构的 进化趋势。 ( 2 ) m p s o c 的通讯架构范围更广泛。m p s o c 涵盖了各种可能的通讯方式， 如点对点、总线、n e t w o r k 等。n o c 虽然只是m p s o c 的一个分支，但却n o c 代表着未来发展的方向。 1 2n o c 的优势 n o c 技术的出现，顺应了集成电路技术的发展趋势。它的优势主要体现在 以下几个方面： 首先，更高的集成度。随着半导体技术的进步，在单块芯片中已经可以集 成数千万计乃至更多的晶体管，这使得设计者在系统芯片中集成多个处理器核 成为可能。复杂的系统能更好地满足电子产品对功能、体积和处理速度越来越 高的要求引。 l 其次，更高的通讯效率。相对于总线通讯架构的多核系统n o c 使用类似网 络的通讯方式，可以支持多对处理器同时通讯，极大提高通讯效率，而且具备 更优秀的系统可扩展性能【5 1 。 最后，低功耗和更强的可控性。网络与处理器间使用异步通讯，避免了庞 大时钟树所带来的面积和功耗问题；n o c 的处理核与网络的通讯通过简单的握 手协议完成，网络与各个处理器的电气参数、时钟信号都可以相对独立处理， 容易控制【6 j ，避免了总线结构采用全局同步的时钟策略，导致的时钟和功耗不 可控制。 由于n o c 所具有的上述优势，必然成为未来复杂系统芯片的主要形式。 1 3 同构多核及优点 多核处理器按照不同的标准有不同种分类方法，其中按照其内部处理核的 组合类型，可以分为同构多核体系结构和异构多核体系结构。同构多核体系是 指处理器芯片内包含有多个相同的处理核；异构多核体系是指处理器芯片内包 含有多个不同的处理核【7 】。 多核处理器本身没有规定核之间的结构是否需要相同，通常来说，同构多 核处理器的设计比较简单，不像异构多核处理器一样每种不同的核都需要分别 设计。设计的重点在于核的互联和通讯方式( 内部互联总线、共享c a c h e 等) 、共 享资源的调度策略与方法等。 目前，已经出现了一系列同构多核处理器。2 0 0 1 年，美国i b m 公司推出了 其第一款用于服务器的通用同构多核处理器p o w e r 4 8 1 。2 0 0 4 年，i b m 又推出了 p o w e r 5 处理器一j ，p o w e r 5 处理器是一款拥有双处理核芯片。2 0 0 6 年，i n t e l 在2 0 0 6 年度的春季i d f 大会( i n t e ld e v e l o p e rf o r u m ) 上宣布将在下一代处理器上使用 c o r e2 微架构【1 0 j 。其他的多核产品还有美国s u n 公司出品i 均n i a g a r a t l l 】和 u l t r a s p a r c i v + 【1 2 j ，a m d 的x 2 a t h l o n 6 4 t 1 3 】等。 一般来说，同构多核处理器由于不需要像异构多核处理器一样考虑各个不 同处理核的特性和需求，因而其整体结构、片上通信架构、软件执行模型、用 户编程模型等都相对比较简单。同时，由于同构多核处理器中各个处理核完全 相同，这就要求每个核都能支持整个软件系统，即每个核的指令集与设计实现 都必须能够运行包括控制软件、操作系统、应用软件等整体软件系统。 考虑上述需求，一般地同构处理器中的处理核都是通用处理单元，其设计 原则就是优化各种程序的平均执行性能。同构多核处理器相对于异构多核处理 器的最大不足在于：由于其内部各个核不存在差异，操作系统或控制程序在分 配任务时，将只能根据任务量进行各个核之间的负载平衡。 本文的设计中将使用同构多核系统来实现矩阵求逆。 2 1 4 本文课题来源 本论文的研究内容来源于： ( 1 ) 教育部博士点基金资助项目“集成电路n o c 中o c n 关键技术研究”( 项且 编号：2 0 0 5 0 3 5 9 0 0 3 ) ( 2 ) 安徽省自然科学基金资助项目“嵌入式多核s o c 基础研究”( 项目编号： 0 7 0 4 1 2 0 31 1 1 5 本文工作及论文结构安排 本文针对矩阵求逆计算在科学计算中的广泛应用，且其计算复杂度较高， 难以实现求逆运算的加速，提出了一种较为简单的加速方法。随着n o c 技术的 发展，且经过比较，本文选用基于n i o s 的二维网格型n o c 多核系统，再将求 逆任务映射到多核系统中。矩阵求逆算法也经过比较选择并行度较高，适合发 挥多核优势的基于块l u 分解的算法。本文以2 0 * 2 0 维矩阵为例，设计的关键 除了n o c 多核系统，还有通过均衡多核系统的核间负载，寻找最小路由路径， 优化资源分配，既使任务均衡分配至各核，又不占用太多的通讯时间，达到加 速的效果。最后对结果进行验证及分析，与单核系统中的计算时间比较，得到 加速比，直观看出加速效果。 论文结构安排分为以下几部分： 第一章绪论。给出n o c 的概念，阐述其优势。在n o c 的基础上，介绍同 构多核，分析其优点，以及在本文中被选用的原因。 第二章同构多核与并行计算概述。简述高密度计算与并行计算，同构多 核在并行计算中的应用。然后引进高密度计算的核心一一矩阵运算及矩阵求逆。 最后对求逆算法进行简述。 第三章二维网格n o c 多核系统设计。定义n o c 多核系统通讯协议和拓扑 结构，介绍各功能模块，简述设计过程。介绍硬件平台搭建环境。 第四章基于二维网格n o c 的矩阵求逆实现。简述求逆算法，介绍任务分 配实现过程。验证及分析结果。 第五章总结与展望。总结论文所做工作，对于进步的工作给出了展望。 第二章同构多核在并行计算中应用概述 本章首先引出高密度计算的核心一矩阵计算，以矩阵求逆为例，研究矩 阵计算一些共性问题。然后介绍了并行算法的概念、发展、分类、设计并行算 法的方法以及实现并行算法的方法。再次使用第一章提出的同构多核概念，研 究同构多核在并行算法中的应用问题，进而引出本文研究重点，将矩阵求逆计 算映射到同构多核系统。 2 1 矩阵计算 随着科学技术的进步和计算机技术的发展，科学与工程计算( 简称科学计 算) 的研究受到科学技术人员的极大重视，其应用己渗透到许多学科领域。 矩阵计算是科学计算领域中的一个重要方面。用矩阵的理论和方法来处理 科学研究和工程技术上的各种问题已越来越普遍。引入矩阵理论不仅使理论的 表达更为简捷，而且对理论实质的刻画也更为深刻。这点也被越来越多的科技 工作者所认识。 计算机和计算方法的发现、普及和发展，为矩阵理论开辟了广阔的研究空 间，同时也为科学、工程技术的研究开拓了崭新的途径。矩阵理论与方法已成 为众多学科领域的重要数学工具。它不仅在最优化方法、数学模型、数值分析 等数学分支上有重要应用，更在信号处理、图像处理、无线电技术和卫星通信 等尖端科学领域中有极其重要的用途【l4 。 大矩阵是典型的高密度计算核心算法模块，解决大矩阵的快速计算具有重 要的工程应用价值。数值计算及其实现手段是近代数学和信息技术永恒的命题， 而高密度计算依然是许多重大工程项目的瓶颈。譬如：雷达系统必须具备每秒 数百亿次的运算速度才能在复杂环境中实时检测出目标【l 引。进入纳米电子以 后，晶体管级s p i c e 仿真尤其必要，但由于目前e d a 软件仿真速度太慢而难以实 现，所以加速技术的研究具有特别的意义【m 1 。 许多工程问题的数学模型都使用矩阵运算求解，求解电路参数实际上就是 解多维线性方程或矩阵求逆，s p i c e 算法的数学模型就是矩阵模块它们大多运算 量惊人。而本文研究的重点矩阵求逆的计算也是随着矩阵维度的增加计算复杂 度呈指数增长。因此，如何对大规模计算进行加速实现是一个具有重大意义的 研究课题。解决海量计算的方法是在简化算法的基础上，选择合适的硬件平台。 2 2 并行算法 本小节首先给出并行算法的定义，并行算法是一些可同时执行的诸进程的 集合，这些进程相互作用、协调动作，从而达到对给定f 1 题求解【17 1 。通俗来说， 4 并行算法也可描述为在各种并行机上解决问题和处理数据的算法。它把多维问 题映射到多处理机上执行，或者把多个任务映射到多处理机中解决。 根据计算复杂度的不同，算法的复杂性一般可以表示为时间复杂性和空间 复杂性。一般情况下，串行算法本质上是为解决一维问题而设计的，所以“深 且窄 。大型的串行计算靠增加算法树的深度来实现。并行算法通常通过增加 空间的维数以及或者增加处理器的个数，增加空间复杂性，从而减少时间复杂 性。也就是说，并行算法是与串行算法截然想法的“浅而宽 的结构。同一时 刻可容纳的计算量增加，而算法的步数尽量减少，最终把时间复杂性转化为空 间复杂性，提高计算速度，达到计算加速的效果【1 8 】。 并行算法是传统的计算数学与新一代计算机相结合而产生的，它是大规模 科学计算必不可少的理论基础和支持工具。只要是超级计算和高性能计算都不 可避免的要使用到并行技术。为了在尽可能短的时间内完成海量计算，只依靠 并行机远远不够。即使是使用类似本文中的具有功能完善的并行机( 二维网格型 n o c 同构多核系统) ，也会因为串行算法的制约而不能完全发挥其优势。因此， 除了并行机，还要有一套并行算法，要求能够在并行机上实现、能充分发挥并 行机功能、设计合理优化。 并行算法，即适合在向量计算机和并行计算机上求解问题的数值方法。 k u n g1 9 8 0 年在并行算法结构一文中将并行算法定义为“多个并发进程的 集合，这些进程同时并相互协作地进行运行处理，从而达到对给定问题的求解 并行算法技术作为计算数学的分支，尽管是一个较新的理论体系且发展不长， 但在多个传统数学领域与应用领域都取得了引人瞩目的进展。目前已经开发出 了很多切实可行的并行算法l l9 1 。 尽管如此，对于目前体系结构的发展速度而言，国内外并行算法的研究应 用仍然相对落后。许多方面仍处于初级阶段，理论以及技术都相对很不成熟。 原因很多，最主要的是任务的合理分配，以及配套软件的欠缺，通信和同步问 题。实际的应用程序中存在并行度才导致了并行机的出现，因此，应用程序中 的并行度是否存在，是否可以挖掘以及如何挖掘是并行机应用的关键。而并行 算法是应用程序的基础，因此在整个过程中具有重要作用，也一直是研究人员 研究的重点之一i z 。 2 2 1 并行算法的分类 并行算法根据不同的标准可以有不同的分类，其中根据不同处理器核承担 的计算任务粒度的不同，可分为： ( 1 ) 细粒度并行算法，通常指基于向量和循环级并行的算法。 ( 2 ) 中粒度并行算法，通常指基于较大的循环级并行，且并行的好处足以弥 补并行带来的额外开销的算法。 ( 3 ) 大粒度并行算法，通常指基于子任务级并行的算法，例如基于区域分解 5 的阶的表示并行算法，是当前并行算法设计的主流。本文主要选用的即为大粒 度并行算法。 并行算法根据并行进程间相互执行顺序关系的不同可分为： ( 1 ) 同步并行算法，进程间由于运算顺序必须相互等待的并行算法，如通常 的s i m d 算法、向量算法等。 ( 2 ) 异步并行算法，进程间不需相互等待的一种算法。 ( 3 ) 独立并行算法，进程间完全独立，整个计算过程不需要任何通信。 根据运算基本对象的不同可分为： ( 1 ) 非数值并行算法，主要为符号运算而设计的并行算法，如遗传算法、 神经网络算法等。 ( 2 ) 数值并行算法，主要为数值计算方法而设计的并行算法。 此外，还存在根据应用问题的不同、不同的通信方式等进行分类的方式。 2 2 2 并行算法的发展 并行算法和并行计算机互相影响，它们的发展相辅相成、缺一不可。 并行算法的发展经历了几个重要阶段： ( 1 ) 基于向量运算的并行算法设计阶段； ( 2 ) 基于多向量处理机的并行算法设计阶段； ( 3 ) s i m d 类并行机上的并行算法设计阶段； ( 4 ) m i m d 类并行机上的并行算法设计阶段； ( 2 ) 现代并行算法设计。 当代，m i m d 类仍然是并行算法的设计主流，且对可扩展性和可移植性要 求越来越高。随着互联网络和微处理器的高速发展，可扩展可移植高性能的获 取要求并行算法设计兼顾两个发展方向：首先，可移植、可扩展的大粒度任务 级并行；其次，每个进程中，应包括通信方式、合理数据结构和程序设计，以 便于发挥单机性能。 要想真正发挥由高性能微处理器和互联网络构成的并行计算机的高性能， 只有兼顾这两个方面才可能实现。 2 2 3 设计并行算法方法 设计并行算法的基本方法分为以下三类： ( 1 ) 检测和开拓现有串行算法中的固有并行性而直接将其并行化； ( 2 ) 修改已有的并行算法使其可求解另一类相似问题； ( 3 ) 从问题本身的描述出发，从头开始设计一个全新的并行算法。 对具有内在顺序性的串行算法难于并行化：修改已有的并行算法有赖于特 定的一类问题；设计全新的并行算法，尽管技术上尚不成熟且要求有些技巧， 但也不是无章可循。本文中的矩阵求逆算法即属于这类具有内在顺序性的串行 算法，设计过程中检测比较多种求逆算法的并行性，择优将其并行化，也就是 6 主要采用第一类设计并行算法的方法。 常用的并行算法设计技术包括倍增技术、平衡树方法、流水线技术、分治 策略以及加速级连策略等。 2 2 4 并行算法的基本实现方法 并行算法的实现不仅依赖于并行机的硬件结构也依赖于它们的软件环境， 它们协同合作。算法实现过程中，需要考虑的因素有很多，主要有：整体修正、 粒度调整、负载平衡、超级步的划分、通信模式、数据依赖、同步开销、并行 调试、循环展开、调换次序和软件开销等。以下只对几个重要因素作简要介绍： ( 一) 整体修正 实际问题中，当只考虑“分而治之 已经不够时，还应该做“整体修正”， 即找出计算关键部位，在这些关键部位进行必要的结点间通信。此部分只需要 很小的工作量很小，却是决定并行算法效率的关键。 ( - - ) 负载平衡 并行算法中，分派给各个结点的任务大小一般都是不同的，而且很难估计， 在异构并行处理系统中尤为突出。而并行程序的整体效率通常由负载最多的结 点决定，因此，设计过程中应尽最大可能平衡各结点的计算负载，才能最终提 高整体效率。 ( 三) 超级步的划分 实际问题中，通常解决问题时需要分成若干个步骤，且上一步骤的计算结 果作为下一步骤的初始数据，影响并行操作。因此，可将并向程序划分为若干 超级步，每一个步骤内部并行化，在该步骤结束时各结点统一进度，然后同时 整理结果进行下一部计算。 ( 四) 数据依赖 对同一存储区域进行重复使用时会产生数据依赖性，这种依赖性通常会抑 制并行执行，应尽量避免。 ( 五) 同步开销 同步开销通常源自两个因素，其一，某些处理机在等待继续执行计算的间 隙中会变得很空闲，有时甚至所有处理机都会空闲。其二，同步化所花时间， 一般需要对处理机进行一定的检验。同步开销严重影响整个算法的性能，所以 并行算法应该尽量使同步开销。 后面的章节中，针对矩阵求逆并行算法，将对这些考虑因素具体分析。 2 2 5 并行计算性能评测 如果对于一个问题设计出新的并行算法，该如何评价其性能? 因此就需要提 出性能度量准则，对并行算法进行性能评测。常用的若干评测标准包括： 并行算法的运行时间、问题的规模与分类、并行机规模、并行度与粒度、 加速比与效率、成本、计算步与通讯步、同步障碍因子和可扩展性等。 7 其中本文关注的主要是并行算法的运行时间，并行机规模，加速比与效率， 可扩展性等。 2 3 矩阵计算与并行算法关系 常见的矩阵计算的并行化矩阵的计算包括矩阵的乘法、矩阵的特征值计算、 矩阵分解、矩阵求逆等。不同的矩阵运算，他们的并行算法也有很大不同，例 如矩阵乘法的并行计算最容易实现，且并行度最高，是理想的算法之一。矩阵 求逆的数据相关性最大，并行度不高，因此实现起来困难最大，具有重大的意 义。 2 4 同构多核在矩阵计算中的应用 矩阵计算的并行化矩阵的计算包括矩阵的乘法、矩阵的特征值计算、矩阵 分解、矩阵求逆等。 传统计算机在计算矩阵乘法时采用串行算法，需要占用较多的工作单元和 较大的存储单元，浪费计算时间和资源。矩阵乘法的时间复杂度为o ( n 3 ) ，1 1 为 矩阵的阶。随着n 的增大，计算效率也会快速降低。其他更复杂的矩阵计算随着 r l 的增加，时间复杂度增加更快，效率也更低。随着并行计算机的出现，通过使 用并行算法，矩阵运算特别是n 值很大的矩阵运算的运算速度可以得到大规模的 提高。并行计算机利用多个处理器同时解决某一个问题，以空间复杂性换取时 间复杂性，是当前提高计算速度的主要途径。 由于单核c p u 的串行工作机制限制了计算的速度，而对于大规模矩阵运算 的限制更大，且单核c p u 处理能力的提升受到m o o r e 定律的制约，处理能力 十分有限。多核技术保留了单核c p u 的可编程性，其“空间并行 的特性提高 了处理速度。多核系统不仅具有硬件处理速度快的优点、也具有软件灵活性高 的优点，这些优点预示着多核技术具备天然的高密度计算优势。挖掘多核系统 的时空并行性可以提高计算速度，发挥多核系统的可编程可以提高计算灵活性， 因此采用多核技术来进行硬件加速是一个理想的选择。 由1 2 和1 3 节介绍的同构多核系统及其优点，经分析比较发现，这种系统 实现起来较为简单，也易于将矩阵运算的并行算法映射其中。 2 5 逆矩阵及求逆方法简述 线性代数中，逆矩阵的定义为：对于n 阶方阵a ，如果存在n 阶方阵b ， 使a b = b a = e ( e 为单位矩阵) ，则称方阵a 是可逆的，并把b 称为a 的逆矩 阵。如果方阵a 可逆，则其逆矩阵是唯一的2 1 1 。 判断矩阵是否可逆的一般方法是看它是否为奇异矩阵，也就是它的行列式 是否为零。一线性变换或正方矩阵a ，若它只对零输入产生零输出，或者说a 的行列式值( 记为i a l ) 不为零，则称为非奇异的，也即可逆，存在逆矩阵，否则 是奇异的，即不可逆，不存在逆矩阵。矩阵奇异性的另外一种表示方式是行列 式，一个n * n 矩阵的行列式用( n - 1 ) 幸( n 1 ) 矩阵的行列式定义，如公式( 2 5 1 ) ，即 f a t - - ( 一1 ) p 1 口1 f 4 一 ( 2 5 1 ) j z l 其中4 ，是除去a 的第1 行和第j 列后得到f 1 0 ( n 1 ) 幸( n 一1 ) 矩阵。判断关系如 下： h 0 彳是非奇异的彳可逆 ( 2 5 2 ) 矩阵求逆的方法有很多，包括伴随矩阵法、初等变换法、分块矩阵法、 g a u s s j o r d a n 消去法、矩阵分解法等等。 上述各种矩阵求逆的方法中，伴随矩阵法中需要求大量的行列式，每个行 列式都几乎要计算到所有的矩阵元素，计算量大，对存储空间的需求也较大， 不利于在多核中实现。 矩阵分解( d e c o m p o s i t i o n ，f a c t o r i z a t i o n ) 是将矩阵分解为一些较简单矩阵的 乘积，如三角矩阵或酉矩阵，他们都具有某种特性，较容易得到逆矩阵【2 2 1 。对 分解得到的矩阵求逆后相乘，得到原矩阵的逆矩阵。矩阵分解可分为l u 分解、 q r 分解、满秩分解、j o r d a n 分解和s v d ( 奇异值) 分解等【2 3 1 ，常见的有三种： 1 ) l u 分解法( l uf a c t o r i z a t i o n ) ，2 ) q r 分解法( q rf a c t o r i z a t i o n ) ，3 ) 奇异值分 解法( s i n g u l a rv a l u ed e e o m p o s t i o n ，s v d ) 。 ( 1 ) l u 分解法 l u 分解法是将原正方( s q u a r e ) 矩阵分解成一个上三角形矩阵或是排列 ( p e r m u t e d ) 的上三角形矩阵和一个下三角形矩阵，这样的分解法又称为三角分 解法。 ( 2 ) q r 分解法 q r 分解法是将矩阵分解成一个正规正交矩阵与上三角形矩阵，正规正交 矩阵的通用符号为q ，所以称为q r 分解法。 ( 3 ) 奇异值分解法 奇异值分解是另一种正交矩阵分解法；s v d 是最可靠的分解法，但是它比 q r 分解法要花上近十倍的计算时间。【u ，s ，v = s v d ( a ) ，其中u 和v 代表二 个相互正交矩阵，而s 代表一对角矩阵。原矩阵a 不必为正方矩阵，这和q r 分解法相同。 例如若将矩阵a 作l u 分解成两个三角矩阵，即a = l u ，则a 1 = u q l 。 其中三角矩阵的几乎一半数据都为0 ，所以求逆简单，正交矩阵的逆为它 的转置矩阵，更为简单。将分解得到的特殊矩阵分别求逆后再相乘，即最终得 9 到原矩阵的逆。比较三种分解方法， 后面提出一种分块l u 分解的方法， 解、分块l u 分解、三角矩阵求逆、 可发现并行度最高的为l u 分解法，且在 并行度更高，本文即选用这种算法。l u 分 矩阵乘法的具体算法将在第四章介绍。 2 6 本章小结 本章概述了矩阵运算、并行算法以及并行算法与同构多核的关系。接下来 将设计一个二维网格型n o c 多核系统，并将矩阵求逆的并行算法映射其中，最 终达到矩阵求逆的加速效果。 1 0 第三章二维网格n o c 多核系统设计 本章根据工作需要，重点设计出一个基于a v a l o n 总线和n i o s 核的二维网 格型n o c 的硬件平台。搭建n o c 系统平台，对各个功能模块简单介绍，简述 设计要点。最后对本文中简要介绍本文的硬件设计环境。 3 1n o c 系统设计简介 n o c 系统的设计关键在于通讯模式和拓扑结构。本文借鉴文献 2 4 】，主要 提出以下设计方案： n o c 系统架构主要分为物理层、系统链路层、网络层和网络拓扑结构。 1 物理层定义了机械的、电气的和时序的接口，本文只关注时序接口。选 用同步握手协议，它的优点是实现简单，且完全可以满足研究通讯架构问题的 需要； 2 数据链路层定义了报文的数据格式，向网络层提供定义良好的服务接口； 3 网络层解决如何将报文从网络源端发送到网络目的端，就需要路由器实 现数据的接收存储转发，以及设定路由算法； 4 片上网络的拓扑结构体现了n o c 中通讯节点是如何在芯片中分布和连接 的，且根据系统需求、节点模块的尺寸和不同的位置，需要不同类型的拓扑结 构。 以下将对于报文格式、路由算法以及网络拓扑结构分别介绍： 3 1 1 报文结构 表3 - 1报文格式定义 b o p 3 2 b i t s e o p 6 b i t s1 0 b i t s8 b i t s8 b i t s 头帧 l 保留帧长度源计算节点目的计算节点 o 网络地址网络地址 实体帧 o 有效数据 o 尾帧 0 有效数据 1 在参考文献 2 4 】的基础上，本文使用如表3 1 所示的报文结构。报文包含 有三种类型的数据帧：头帧、实体帧和尾帧，且一个完整的数据报文一定会有 头帧和尾帧，可能会含有实体帧。中间3 2 位为帧的负