计算机工程与设计ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＤｅｓｉｇｎ ２０１１，Ｖｏ１．３２，Ｎ０．１２ ４０５７ 基于任务的Ｃｈｏｌｅｓｋｙ分解多核并行化研究 吴华平， 郑晓薇， 张建强 （辽宁师范大学计算机与信息技术学院，辽宁大连１１６０８１） 摘要：针对Ｃｈｏｌｅｓｋｙ分解算法采用ＯｐｅｎＭＰ并行程序设计时的并行性开销增大和线程负载不平衡的问题，利用并行性能分 析工具对串行程序进行热点分析，提出了一种基于任务的Ｃｈｏｌｅｓｋｙ分解多核并行算法。该算法将大循环问题划分成各个相 互的小任务，并运用任务窃取技术和动态负载均衡算法使多个任务能够并行完成。采用ＰａｒａｌｌｅｌＡｍｐｌｉｉｆｅｒ对并行程序进 行调试和优化，实验结果表明，其性能得到较大幅度的提升。 关键词：Ｃｈｏｌｅｓｋｙ分解；并行化；热点分析；任务窃取技术；动态负载均衡 中图法分类号：ＴＰ３１１ 文献标识码：Ａ 文章编号：１０００．７０２４（２０１１）１２—４０５７．０３ Ｒｅｓｅａｒｃｈ ｏｎ Ｃｈｏｌｅｓｋｙ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｍｕｌｔｉ—ｃｏｒｅ ｐａｒａｌｌｅｌｉｓｍ ｂａｓｅｄ ｏｎ ｔａｓｋ ＷＵ Ｈｕａ・ｐｉｎｇ，ＺＨＥＮＧ Ｘｉａｏ—ｗｅｉ，ＺＨＡＮＧ Ｊｉａｎ—ｑｉａｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｌｉａｏｎｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ １ １ ６０８ １，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｔｈｅ ｃｏｓｔ ｉｎｃｒｅａｓｅｓ ａｎｄ ｔｈｅ ｔｈｒｅａｄ ｌｏａｄ ｉｓ ｉｍｂａｌａｎｃｅ ｗｈｅｎ ｗｅ ａｄｏｐｔ ＯｐｅｎＭＰ ｐａｒａｌｌｅｌ ｐｒｏｇｒａ・ ｍｍｉｎｇ ｆｏｒ Ｃｈｏｌｅｓｋｙ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ａ ｐａｒａｌｌｅｌ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ ｉｓ ａ ｔａｓｋ—ｂａｓｅｄ ｍｕｌｔｉ－ｃｏｒｅ ｏｒ ｆＣｈｏｌｅｓｋｙ ｄｅｃｏｍ— ｐｏｓｉｔｉｏｎ ａｎｄ ａ ｓｅｒｉａｌ ｐｒｏｇｒａｍｓ ａｒｅ ａｎａｌｙｚｅｄ ｕｓｉｎｇ ｔｈｅ ｐａｒａｌｌｅｌ ｓｔｕｄｉｏ ｔｏｏｌｓ．Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｄｉｖｉｄｅｓ ｔｈｅ ｌａｒｇｅ ｃｉｒｃｕｌａｔｉｏｎ ｐｒｏｂｌｅｍｓ ｉｎｔｏ ｅａｃｈ ｉｎｄｅｐｅｎｄｅｎｔ ｓｍａｌｌ ｔａｓｋｓ，ｕｓｉｎｇ ｔｈｅ ｔａｓｋ ｓｔｅａｌｉｎｇ ｔｅｃｈｎｉｑｕｅ ａｎｄ ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｍａｋｅ ｍｕｌｔｉｐｌｅ ｔａｓｋｓ ｔｏ ｂｅ ｐａｒａｌｌｅ１． Ｔｈｅ Ｐａｒａｌｌｅｌ Ａｍｐｌｉｆｉｅｒ ｉｓ ｕｓｅｄ ｔｏ ｄｅｂｕｇ ａｎｄ ｏｐｔｉｍｉｚｅ ｔｈｅ ｐａｒａｌｌｅｌ ｐｒｏｇｒａｍｓ．Ａｎｄ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｉｓ ｉｍｐｒｏｖｅｄ ｓｕｂｓｔａｎｔｉａｌｌｙ． Ｋｅｙ ｗｏｒｄｓ：Ｃｈｏｌｅｓｋｙ ｄｅｃｏｍｐｏｓｉｔｉｏｎ；ｐａｒａｌｌｅｌｉｚａｔｉｏｎ；ｈｏｔｓｐｏｔ ａｎａｌｙｓｉｓ；ｔａｓｋ ｓｔｅａｌｉｎｇ ｔｅｃｈｎｉｑｕｅ；ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ ０引 言 科学计算是计算机发展中的一个重要领域，以Ｃｈｏｌｅｓｋｙ 分解、ＬＵ分解等为代表的线性代数数值计算在现代科学研究 和工程技术中得到广泛应用。许多工程问题、力学问题、动力 系统问题最终都归结为线性方程组的求解问题，其系数矩阵 大多具有对称正定的性质。长期以来，为提高科学计算的速 度，科学计算函数库中积累了大量的库程序。目前市场上多 核处理器已成为主流，但传统的科学计算程序都是针对单处 理器计算架构编写的，在多核平台上由于多核附带的开销造 成性能下降。随着计算机技术的不断发展，并行结构从集中 式机群到分布式ＰＣ，再从多处理器向多核的架构发展；科学计 例如文献［４］提出的ＬＤＬ 分解递归算法具有自动矩阵分块的 功能，可计算满足精度要求的特征值；文献［５】以针对算术单元 设计的有理分数的数据表示形式来实现Ｃｈｏｌｅｓｋｙ并行分解； 还有基于ＦＰＧＡ利用共享存储的多处理器软核实现Ｃｈｏｌｅｓｋｙ 分解和基于ＦＰＧＡ采用细粒度流水线实现Ｃｈｏｌｅｓｋｙ分解并行 算法 等。也有的研究者采用ＭＰＩ和机群系统对线性方程组 的并行求解进行了研究 。针对基于ＭＰＩ的并行算法设计复 杂、消息传递和数据移动开销大问题，本文着重考虑多核计算 机的优势，并结合使用ｌｎｔｅｌ公司的Ｐａｒａｌｌｅｌ Ｓｔｕｄｉｏ并行程序开 发工具套件… ，提出了一种基于任务划分的Ｃｈｏｌｅｓｋｙ分解多核 并行优化算法。该算法提高并优化了基于多核平台的大规模 线性方程组求解速度，对其它科学计算具有重要的推广意义。 实验结果表明，经过并行优化后的并行程序，计算性能得到大 幅提高，多核ＣＰＵ资源的利用率得到提高。 算的发展方向也随着计算机技术的发展经历着相应的变化， 特别是多核并行计算技术及其应用引起了越来越多的重视。 多核技术已广泛地应用于多核嵌入式软件ＶＥＲＴＡＦ，ＭｕｌｔｉＣｏｒｅ （Ⅵ Ｃ）、建模与仿真和傅里叶变换的数字信号处理等领域 。 。 有关线性方程组的求解许多文献都给出了很好的方法。 收稿日期：２０１１－Ｏ１一Ｏｌ；修订日期：２０１１－０３—１０。 基金项目：国家自然科学基金项目（６０６０３０４７）。 １串行Ｃｈｏｌｅｓｋｙ分解算法 Ｃｈｏｌｅｓｋｙ分解用于求解系数矩阵的线性方程组Ａｘ＝ｂ，其 作者简介：吴华平（１９８４－－），男，江西赣州人，硕士研究生，研究方向为并行计算、多核计算机系统； 郑晓薇（１９５７－－），女，辽宁大连人，教 授，ＣＣＦ高级会员，研究方向为并行计算、多核计算机系统； 张建强（１９８１一），男，内蒙古乌兰察布人，硕士研究生，研究方向为并行计算、 多核计算机系统。Ｅ－ｍａｉｌ：ｗｕｈｕａｐｉｎｇ１１０３＠ｙａｈｏｏ．ｃｏｒｎ．ｃｎ ４０５８ ２０１１，Ｖｏ１．３２，Ｎｏ．１２ 计算机工程与设计ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ ａｎｄＤｅｓｉｇｎ 地观察程序的执行，对称矩阵阶数选为２０００，对ＯｐｅｎＭＰ并行 算法程序分析的结果如图１所示。Ｃｏｎｃｕｒｒｅｎｃｙ当中用Ｉｄｌｅ、 Ｐｏｏｒ、Ｏｋ、Ｉｄｅａｌ、Ｏｖｅｒ这５种不同状态来表示并发状态，并采用 不同的颜色显示，例如，红色表示利用率低，即运行的线程数 少于ＣＰＵ的核数；绿色表示理想的并行度，即运行的线程数 等于ＣＰＵ的核数，ＣＰＵ得到充分利用。 Ｃｏｎｃｕｔｒ￣ｒｅｎｃｙ 中，Ａ是一个ｎｘｎ阶的稠密正定对称矩阵，ｂ大小为ｎ向量。求 解该方程组的标准解法是对Ａ先进行Ｃｈｏｌｅｓｋｙ分解Ａ＝ＬＤ ， 得到下三角矩阵Ｌ后，通过前向回代求解下三角方程和后向 回代求解上三角方程：Ｌｙ＝ｂ和Ｌ Ｘ＝Ｙ，最终得到方程组的解 向量ｘ。实数矩阵Ａ的Ｃｈｏｌｅｓｋｙ分解可以通过求解公式，同时 为减少乘法次数，引入辅助量 ：ｌｉｋ ，求得计算 及 的公式 ｆ ＝口 一∑ Ｊ１ ，２，…， （１） 曩墨墨 鸸Ｔ・ ～～ ｔｉｋ＝ａｉｋ一∑ ｆ＝ｋ＋ｌ， ，…， ｕ ｌ ， 由式（１）可以看出，同一行ｔ ，ｌ ，ｄ。的计算存在明显的数据 相关，只能依次顺序进行计算。为消除数据相关，便于实现并 行计算，将式（１）的计算顺序改为按列进行，并且将累￣Ｊｎ，ｎ改为 超前加。由于Ａ为对称阵，故只需给出下三角阵即可。存储 元素共ｎ（ｎ＋１）／２个，用一维数组Ａ存放，顺序为｛ａＩｊｊ ａ 。，ａ２：，…， 。，ａｎｚ，…，ａ ｝，则矩阵元素ａ 对应一维数组元素Ａ（ｉ （ｉ一１）／２＋ ｊ）。为了减少存储空间，又由于矩阵Ａ在经过计算后就不需要 再使用了，因此可以采用原位存储的方法，即用Ｄ覆盖Ａ的对 角线相应位置，Ｔ、Ｌ则覆盖Ａ的对角线以下相应位置。由式 （１）可得到计算Ｃｈｏｌｅｓｋｙ分解的串行算法如下： ｆｏｒ ｋ＝ｌ ｔＯ Ｎ ｏｆｒｍ＝１ ｔｏ ｋ Ａ［ｋ，ｋ］：Ａ［ｋ，ｋ］．Ａ［ｍ，ｋ］？ Ａ［ｋ，ｋ］～一 ； ｅｎｄ ｆｏｒ ｏｆｒｉ＝ｋ＋１ ｔＯＮ ｏｆｒｍ＝ｌ ｔＯ Ｎ Ａ［ｋ，ｉ］＝Ａ［ｋ，ｉ］一Ａ［ｍ，ｉ１ Ａ［ｋ，ｍ】； ｅｎｄ ｆｏｒ Ａ［ｉ，ｋｌ＝Ａ【ｋ，ｉ］／Ａ［ｋ，ｋｌ； ｅｎｄｆｏｒ ｅｎｄｆｏｒ ２ Ｃｈｏｌｅｓｋｙ分解的并行化 ２．１ 串行Ｃｈｏｌｅｓｋｙ分解算法的瓶颈问题 在设计串行算法时定义了多个函数，其中ＬＤＬＴＤＣＭＰ０ 一 函数是Ｃｈｏｌｅｓｋｙ分解的主体部分。运用ＰａｒａｌｌｅｌＡｍｐｌｉｉｆｅｒ中的 Ｈｏｔｓｐｏｔｓ对程序进行热点分析，可收集到不同类型的数据，确 定应用程序运行消耗的时间，以及识别出最耗时的函数。通 一 过热点分析，得出热点函数ＬＤＬＴＤＣＭＰ（）是最耗时的，它是 Ｃｈｏｌｅｓｋｙ分解算法运行的瓶颈。 ２．２ ＯｐｅｎＭＰ方法并行化 为了有效利用多核ＣＰＵ资源，对Ｃｈｏｌｅｓｋｙ分解串行程序 采用ＯｐｅｎＭＰ方法并行化。此处只需要对其热点函数 ＬＤＬＴＤＣＭＰＯ进行并行化。ＯｐｅｎＭＰ是基于共享存储系统并行 编程方法，它具有编程简单、移植性好和可扩展等优点。但由 于ＬＤＬＴＤＣＭＰ（）函数体内的最外层循环存在相关，只能在内 层循环加ＯｐｅｎＭＰ并行编译制导语句。本文的测试平台为： ＣＰＵ Ｉｎｔｅｌ（Ｒ）Ｐｅｎｔｉｕｍ（Ｒ）Ｄｕａｌ １．８６ＧＨｚ、内存１ＧＢ、Ｗｉｎｄｏｗｓ ＸＰ 以及Ｐａｒａｌｌｅｌ Ａｍｐｌｉｉｆｅｒ中的Ｃｏｎｃｕｒｒｅｎｃｙ工具。为了更为直观 “ｖ抽 …ｔｔ ＃５酐￥ｌ 乱 瓠 ０ ｔ瓤ｔ口 瓣 ｉ ｓ ｔ州ｃ 强 ｏ髓“Ｉ ｎｔ札ｌ“ｌ … Ｏ‘∞ ｌ ∞ＬＬ ｘ 图Ｉ ＯｐｅｎＭＰ方法的并行度状态 从图１可知，ＯｐｅｎＭＰ方法的并行度的主导状态是Ｐｏｏｒ， 逻辑ＣＰＵｓ利用率很低。这是因为在ＬＤＬＴＤＣＭＰ ０函数中， ＯｐｅｎＭＰ需要频繁地创建、汇合、销毁以及管理线程，线程负载 不平衡，再加上计算的颗粒度太细，造成并行性开销增大，导 致性能很低。 ３ Ｃｈｏｌｅｓｋｙ分解的任务划分 针对热点函数ＬＤＬＴＤＣＭＰ０采用ＯｐｅｎＭＰ方法并行化性 能低的问题，我们考虑以任务作为计算粒度，增大并行度，以 提高并行加速比和系统效率。将函数ＬＤＬＴＤＣＭＰ（）内部的计 算任务划分成若干个的小计算任务，在考虑各个小任务 负载均衡的问题后，通过适当的任务调度将这些小任务均衡 地分配给多个ＣＰＵ核执行，进而达到任务高效的并行执行。 本算法中任务划分采用依次将计算任务递归地分为两个 子任务的递归划分方式。对划分程度的关键就是粒度， 在程序设计时选择自动地确定恰当的粒度可使并行调度开销 最小。常用的动态任务调度方法有任务窃取法和全局任务排 队法“ 。任务窃取技术是由任务调度器自动地为每一个内核 构建线程，然后将创建的逻辑任务映射到某个工作线程的逻 辑池内，当一个工作线程完成了线程池内的任务时，还可以从 其它任务池取得任务继续执行。本文研究的递归任务划分适 用于任务窃取法，该算法将递归和任务窃取有效地结合起来， 使得Ｃｈｏｌｅｓｋｙ分解并行程序运行速度和ＣＰＵ利用率得到较 大提升。 我们选择的并行工具是线程构建模块（ｔｈｒｅａｄｉｎｇ ｂｕｉｌｄｉｎｇ ｂｌｏｃｋｓ，ＴＢＢ），它是Ｉｎｔｅｌ公司针对多核平台开发的一组开源的 基于运行时的ｃ＋＋线程并行编程模型，可支持可扩展的线程 嵌套和递归并行。ＴＢＢ在多核并行编程上与ＯｐｅｎＭＰ相比有 更好的表现。ＴＢＢ在并行编程方面是基于任务而非线程，具 有适当的抽象、自动负载均衡的不绑定ＣＰＵ数量的优势“ ’川。 ＴＢＢ任务通常是轻量级的组件，在Ｌｉｎｕｘ系统和Ｗｉｎｄｏｗｓ系统 上启动和结束过程更加迅速。同时ＴＢＢ的任务调度器采用任 务自动迁移技术来实现调度，这种调度方式要优于指导调度 吴华平，郑晓薇，张建强：基于任务的Ｃｈｏｌｅｓｋｙ分解多核并行化研究 或动态调度，并且不会带来集中负荷的问题“ 。 本文算法实施步骤如下： （１）循环并行化改造。将热点函数ＬＤＬＴＤＣＭＰ（）内的循环 体转换为在小空间上进行操作的形式，这种形式也称为体对 象（ｂｏｄｙ ｏｂｊｅｃｔ），每个ｏｐｅｒａｔｏｒ（）方法中将处理一个小空间。其 改写的主要代码如下： ｃｌａｓｓ ＰａｒａｌｌｅｌＬＤＬＴＴａｓｋ ２０１１，Ｖｏ１．３２，Ｎｏ．１２ ４０５９ 图２所示。从图２当中可知，Ｐａｒａ１１ｅｌＬＤｕ’函数所划分的小任 务确实由二个ＣＰＵ核均衡并行执行。由图ｌ、图２比较得出， ＴＢＢ方法的并发性能明显好于ＯｐｅｎＭＰ方法，并且主导状态 也由Ｐｏｏｒ变为Ｉｄｅａｌ。与ＯｐｅｎＭＰ方法对比后得到并行性分析 统计对比图３。图３中的ｒ００３ｃｃ和ｒ００１ｃｃ分别是ＯｐｅｎＭＰ方 法和ＴＢＢ方法的分析统计数据，从中可知，ＯｐｅｎＭＰ方法的 ＣＰＵ等待时间和空闲时间比ＴＢＢ方法的要多；ＯｐｅｎＭＰ方法 的逻辑ＣＰＵｓ利用较低，而ＴＢＢ方法的逻辑ＣＰＵｓ利用则达到 ｛ｆｌｏａｔ ｍＪｌａ；ｉｎｔ ＿ｋ； ｐｕｂｌｉｃ：ｖｏｉｄ ｏｐｅｒａｔｏｒ（）（ｃｏｎｓｔ ｂｌｏｃｋｅｄｒａｎｇｅ＜ｉｎｔ＞＆ｒａｎｇｅ） １．９３。这是由于ＴＢＢ任务调度器的任务窃取技术和动态负载 ｃｏｎｓｔ ｛ｆｏｒ（ｉｎｔ ｉ＝ｒａｎｇｅ．ｂｅｇｉｎ（）；ｉ！＝ｒａｎｇｅ．ｅｎｄ（）：＋＋ｉ） ｛ｆ０ｒ（ｉｎｔｍ＝０；ｍ＜ｍ＿ｋ；ｍ＋＋） ｍ＿ｐａ（ｍｋ，ｉ）：ｍ￣ａ（ｍ＿ｋ，ｉ）一ｍ￣ｏａ（ｍ，ｉ） ｍ ｐａ（ｍ＿ ｋ，ｍ）； ｍ￣ａ（ｉ，ｍ＿ｋ）＝ｍ＿ｐａ（ｍｋ，ｉ）／ｍｄｇａ（ｍｋ，ｍ＿ｋ）；｝｝ ＿ＰａｒａＵｅｌＬＤＬＴＴｌａｓｋ（）｛｝ ）； 在ｏｐｅｒａｔｏｒ０方法中ｂｌｏｃｋｅｄｒｎａｇｅ＜Ｔ＞表示类型Ｔ上可递 归划分的一维迭代空间，参数ｒａｎｇｅ明确了方法体的空间。声 明ｏｐｅｒａｔｏｒ（）时使用的ｃｏｎｓｔ是作为一道屏障，用以防止对线程 私有副本的错误修改被积累起来。从类ＰａｒａｌｌｅｌＬＤＬＴＴａｓｋ中 可以看出，并行化改造后的循环体与最初的代码很相似。类 中将访问频率很高的值放入局部变量有助于在编译时更好地 优化循环。 （２）函数定义和任务划分。定义函数来使用改造后的体对 象，并对其需要用到的数据进行初始化，再用ＴＢＢ中的ｐａｒａ１． １ｅｌ ｆｏｒ把热点函数ＬＤＬＴＤＣＭＰ（）内层的循环体划分成若干子 区间（即逻辑任务）并分配到每个处理器。ｐａｒａｌｌｅｌ ｆｏｒ（ｂｌｏｃｋｅｄ ｒｎａｇｅ＜Ｔ＞（ｂｅｇｉｎ，ｅｎｄ），ｔａｓｋ，ｇｒａｉｎｓｉｚｅ））迭代循环体当中的参数ｂｅ— ｇｉｎ、ｅｎｄ为迭代空间的起始索引，ｔａｓｋ是体对象，ｇｒａｉｎｓｉｚｅ用来 指定分配给处理器的合理迭代数量。对迭代区间递归划分程 度取决于任务粒度，粒度过小可能会使循环模板中的调度开 销超过并行性所带来的加速，而粒度过大则并行性。本 文采用的ａｕｔｏ ｐａｒｔｉｔｉｏｎｅ（ｒ）提供一种启发式的方法来选择粒度， 这种启发式方式在努力各种开销的同时，还能尽量实现 负载均衡。 （３）任务调度设计。对于ＴＢＢ来说，最有效的并行是每个 核上只跑一个工作线程。本文的实验平台为双核，设置线程 数为２，在使用算法模版或者任务调度器之前，每个线程必须 初始化线程构建模块，其代码如下： ＴＢＢ：：ｔａｓｋ ｓｃｈｅｄｕｌｅｒ ｉｎｉｔ ｉｎｉｔ（２）；／／Ｏ；ｇ建线程池 ＰａｒａｌｌｅｌＬＤＬＴ（Ａ，Ｎ）； （４）检查错误及优化。对程序并行化后，先用ＰａｒａｌｌｅｌＩｎｓｐｅｃｔｏｒ 检查内存与多线程错误；如果没有错误，对比并行前后的程序， 再用ＰａｒａｌｌｅｌＡｍｐｌｉｉｆｅｒ找到可以再并行的部分，不断优化性能，使 得并行化程度达到最优，提高硬件资源的使用率和算法效率。 ４并行算法的性能分析 使用Ｐａｒａｌｌｅｌ Ａｍｐｌｉｉｆｅｒ中的Ｃｏｎｃｕｒｒｅｎｃｙ对ＴＢＢ方法并行 化后的Ｃｈｏｌｅｓｋｙ分解算法程序进行并发性分析，实验结果如 均衡算法，可调度所有处理器内核全力处理有益工作，既可有 效避免过度使用线程又可）ｒｌ￣Ｕ解决线程用力不足的难题，并 使用启发式方法的ａｕｔｏ ｐａｒｔｉｔｉｏｎｅｒ宏来确定粒度，通过系统努 力各种开销，因而系统性能得到了较大提升。在Ｃｏｎｃｕｒ－ ｒｅｎｃｙ中ＴＢＢ方法执行时间比ＯｐｅｎＭＰ方法多，是由于进行并 发性分析时，需要插入和一些检测代码及统计各种状 态，会产生额外的分析时间。 勰ＣｏＤｃｕｒｒｅｎｃｙ 曩墨墨墨 哪广 … 一 鎏图２ ＴＢＢ方法的并行度状态 一 弱 佛矾～ 釜 ∞１７ ．ａｒ４￣ｔ ｕ 档 Ｔ￣Ｔｅ： 器艘 辫０盆 ・１０，９０１￣ 鲰确 ０＿０｛ｊ 辱９６暑 勰１０，４３４￣ 蕺 ＾舯 ∞ 鼢违镪 § ＬＯｇｉＣａｌ 神峨端 獬 髋 ∞ 钧 １Ｉｌ＿蚺ｄ ａｐＵ舶ｒ憾 ＩＬ６４３Ｓ 奢０绺∞ ｑ缸 嚣 ≤ ＿ 踊圈龃——■圈—鼬一 图３ ＯｐｅｎＭＰ方法和ＴＢＢ方法的并行性分析统计对比 一 为了进一步验证本文并行算法的效果，选用测试矩阵规 模分别为１０００阶和２０００阶，对Ｃｈｏｌｅｓｋｙ分解串行算法、Ｏｐｅｎ— ＭＰ方法并行和ＴＢＢ方法并行算法进行了测试，实际执行时 间的结果如表１所示。从运行时间，加速比和ＣＰＵ利用率分 析得出，Ｃｈｏｌｅｓｋｙ分解采用ＴＢＢ方法并行化比ＯｐｅｎＭＰ方法 更具有优势，ＣＰＵ多核资源得到了充分利用。 表１不同问题规模下３种算法运行时间和结果 １０００阶 ２０００阶 算法 时间ＣＰＵ利 ＣＰＵ利 ／ｓ 加速比 用率 时间／ｓ 加速比 用率 串行算法 ２．４３７ １．０００ ５０．０Ｏ％ ２０ ３５９ １．０００ ５０．００％ ＯｐｅｎＭＰ并行算法 ２．０６２ １．１８２ ５９．１Ｏ％ １５．５Ｏ１ １Ｉ３ｌ３ ６５．６５％ ＴＢＢ并行算法 １．６４０ １．４８６ ７４－３０％ １３．５１５ １．５０６ ７５－３０％ （下转第４２５５页） ，陈婷，王猛：基于频率跟踪插值抽取法的电参量计算 ２０１１，Ｖｏ１．３２，Ｎｏ．１２ ４２５５ （上接第４０５９页） ５结束语 随着多核计算机的普及，相应的软件编程方式和科学计 算方向也在发生着巨变；如何选择一种并行编程技术使得算 法并行化的运行效率最高就显得非常重要。本文把Ｐａｒａｌｌｅｌ Ｓｔｕｄｉｏ工具应用到Ｃｈｏｌｅｓｋｙ分解算法的并行化分析和优化设 ［５】 Ｍａｓｌｅｎｎｉｋｏｗ Ｏ，Ｌｅｐｅｋｈａ、‘Ｓｅｒｇｉｙｅｎｋｏ Ａ，ｅｔ ａ１．Ｐａｒａｌｌｅｌ ｉｍｐｌｅ－ ｍｅｎｔａｔｉｏｎ ｏｆ Ｃｈｏｌｅｓｋｙ ＬＬＴ ａｌｇｏｒｉｔｈｍ ｉｎ ＦＰＧＡ２ ｂａｓｅｄ ｐｒｏ— ｃｅｓｓｏｒ［Ｃ］．Ｐｒｏｃ ｏｆＰＰＡＭ ０７，２００８：１３７—１４７． ［６】Ｈａｒｉｄａｓ Ｓ Ｇ．ＦＰＧＡ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆａ Ｃｈｏｌｅｓｋｙ ａｌｇｏｒｉｔｈｍ ｏｒｆ ａ ｓｈａｒｅｄ ｍｅｍｏｒｙ ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ ａｒｃｈｉｔｅｃｔｕｒｅ［Ｄ］．Ｎｅｗ Ｊｅｒｓｅｙ：Ｉｎ— ｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ，２００３． 计中，通过ＴＢＢ的任务并行化，使得算法的时间效率和多核 资源的利用率大大提高。这种并行算法的设计方法在大规模 数值的科学计算领域具有较好的推广意义。 ［７】 邬贵明．Ｃｈｏｌｅｓｋｙ分解细粒度并行算法［Ｊ】．计算机工程与科学， ２０１０，３２（９）：１０３—１０６． 参考文献： ［Ｉ］ＬＩ Ｎｉ，ＧＯＮＧ Ｇｕａｎｇｈｏｎｇ，ＰＥＮＧ Ｘｉａｏｙｕａｎ，ｅｔ ａ１．Ｓｃｅｎｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｅｖａｌｕａｔｉｏｎ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ－ｃｏｒｅ ｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ ［８］ 付朝江．基于工作站机群并行求解有限元方程组［Ｊ］．计算机工 程与设计，２００８，２９（２４）：６４４１．６４４３． ［９］ＤＵＡＮ Ｚｈｉ－ｊｉａｎ．Ｐａｒａｌｌｅｌ ａｌｔｅｒｎａｔｉｎｇ—ｄｉｒｅｃｔｉｏｎ ｉｔｅｒａｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｏｒｆ ｓｏｌｖｉｎｇ ｂａｎｄｅｄ ｌｉｎｅａｒ ｅｑｕａｔｉｏｎｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００９，４５（２０）：５４—５６． ｔｅｃｈｎｏｌｏｇｙ【Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＷＲＩ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｓｏｆｔ－ ｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２００９：９４—９８． ［１０】刘洋．基于奇偶归约法并行求解三角块线性方程组的研究［Ｊ］ ＿计算机工程与设计，２００９，３０（１３）：３１９３—３１９５． ［１ １］英特尔＠软件网络［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｓｏｆｔｗａｒｅ．ｉｎｔｅ１．ｃｏｍ／ｅｎ—ｕｓ／ｉｎ－ ｔｅｌ—ｐａｒａｌｌｅｌ—ｓｔｕｄｉｏ・ｈｏｍｅ／Ｉｎｔｅｌ Ｐａｒａｌｌｅｌ Ｓｔｕｄｉｏ，２０ １ １． ［２］ Ｍａｒｏｗｋａ Ａ．Ｔｏｗａｒｄｓ ｈｉｇｈ ｌｅｖｅｌ ｐａｒａｌｌｅｌ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌｓ ｆｏｒ ｍｕｌｔｉ－ｃｏｒｅ ｓｙｓｔｅｍｓ【Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ａｄｖａｎｃｅｄ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍ— ｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００８：２２６—２２９． ［１２］周伟明．多核计算与程序设计［Ｍ］．武汉：华中科技大学出版社， ２００８：３２０．３２２． ［３］ ＹＡＮＧ Ｃｈｕａｎ，ＹＡＮＧ Ｂｉｎ．Ｆｏｕｒｉｅｒ ｔｒａｎｓｆｏｒｍ ｍｕｌｔｉ．ｃｏｒｅ ｐａｒａ— ｌｌｅｌｉｚａｔｉｏｎ ｉｍｐｌｅｍｅｎｔ￣ｉｏｎ ｂａｓｅｄ ｏｎ ＴＢＢ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉ— ｎｅｅｒｉｎｇ，２０１０，３６（１６）：２８８—２９０． 【４］ＺＨＡＮＧＫｕｎ，ＺＨＡＮＧＹｏｕ－ｚｈｉ．Ｒｅｃｕｒｓｉｖｅａｌｇｏｒｉｔｈｍｆｏｒ ｃａｌｃｕｌａｔｉｎｇ ｅ ｅｎｖＮｕｅｓ ｏｆｒｅａｌ ｓｙｍｍｅｔｒｉｃ ｍａｔｒｉｘ ｂａｓｅｄ ｏｎ ＬＤＬＴ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ［１３】胡斌，袁道华．ＴＢＢ多核编程及其混合编程模型的研究［Ｊ］．计算 机技术与发展，２００９，１９（２）：９８－１０１． ［１４】郑晓薇．张建强．基于ＴＢＢ任务调度器的Ｎ皇后并行算法［Ｊ］． 计算机工程与设计，２０１０，３１（１５）：３４２３—３４２６． ［１５］Ｒｅｉｎｄｅｒｓ Ｊ，Ｓｔｅｐａｎｏｖ Ａ．Ｉｔｎｅｌ ｔｈｒｅａｄｉｎｇ ｂｕｉｌｄｉｎｇ ｂｌｏｃｋｓ编程指南 【Ｍ】．聂学军，译．北京：机械工业出版社，２００９：２３． ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｉｔｏｎｓ，２００８，４４（３）：７８－８０．
