并行计算的算法与应用

第３４卷第１期　西安科技　大　学　学　报　

２０１４年０１月　ＪＯＵＲＮＡＬ　ＯＦ　ＸＩ’ＡＮ　ＵＮＩＶＥＲＳＩＴＹ　ＯＦ　ＳＣＩＥＮＣＥ　ＡＮＤ　ＴＥＣＨＮＯＬＯＧＹ　Ｖｏ１．３４　Ｎｏ．１　Ｊａｎ．２０１４　

文章编号：１６７２—９３１５（２０１４）０１—００７１—０４　

基于线程并行计算的Ａｐｒｉｏｒｉ算法　

阴爱英　

（１．福州大学数学与计算机科学学院，福建福州３５０１０８；２．福州大学至诚学院，福建福州３５０１０８）　

摘　要：针对数据挖掘中经典的Ａｐｒｉｏｒｉ算法在计算频繁项目集时需消耗大量的时间缺点，文中　

利用多线程并行计算的特点，提出了基于线程并行计算的Ａｐｒｉｏｒｉ算法，该算法是将统计候选项目　

个数的任务交给多线程来执行，从而达到减少Ａｐｒｉｏｒｉ算法的运行时间。通过实验数据分析，该算　法对减少Ａｐｒｉｏｒｉ算法的运行时间有很大的提高。　

关键词：线程；并行计算；Ａｐｒｉｏｒｉ算法　

中图分类号：ＴＰ　３１】．１３　文献标志码：Ａ　

Ａｐｒｉｏｒｉ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｒｅａｄ　ｐａｒａｌｌｅｌ　ｃｏｍｐｕｔｉｎｇ　

ＹＩＮ　Ａｉ—ｙｉｎｇ　’　

．　（１．Ｃｏｌｌｅｇｅ　ｏｆＭａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｆｕｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ　３５０１０８，Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＣｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｚｈｉｃｈｅｎｇ　Ｃｏｌｌｅｇｅ　ｏｆＦｕｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ　３５０１０８，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｃｏｎｓｉｄｅｒｉｎｇ　ｔｈｅ　Ａｐｒｉｏｒｉ　ｄａｔａ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｈｅ　ｃｌａｓｓｉｃ　ｃａｌｃｕｌａｔｉｏｎ　ｏｆ￣ｅｑｕｅｎｔ　ｉｔｅｍｓｅｔｓ　

ｒｅｑｕｉｒｅｓ　ａ　ｌｏｔ　ｏｆ　ｔｉｍｅ，ｕｓｉｎｇ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｍｕｌｔｉ—ｔｈｒｅａｄｅｄ　ｐａｒａｌｌｅｌ　ｃｏｍｐｕｔｉｎｇ，ｔｈｒｅａｄ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｂａｓｅｄ　

计算机时代２０１７年第９期　・　３３　・　

ＤＯＩ：１０．１６６４４／ｊ．ｃｎｋｉ．ｃｎ３３・１０９４／ｔｐ．２０１７．０９．０１１　

并行计算在矩阵中的应用　

王涛，赵映诚，刘鑫源　

（中国石油大学（华东）理学院，山东青岛２６６５８０）　

摘要：在解决许多实际问题时，经常需要计算一些高阶矩阵。然而传统的串行计算方法往往效率比较低。因此，需将　

串行程序并行化来提高计算效率。文章分别研究了Ｗｉｎｄｏｗｓ　ＡＰＩ、ＯｐｅｎＭＰ、ＭＰＩ、ＰＰＬ这四种并行计算方法在矩阵乘法　并行化中的应用。通过测试不同规模的矩阵，根据加速比衡量并行化的加速效果，对这四种并行化方法的加速效果进行　

了对比。结果表明，这四种方法都可以提高计算效率，其中ＭＰＩ的加速效果最好。　关键词：计算效率；串行计算；并行化；加速比　

中图分类号：ＴＰ３３８．６　文献标志码：Ａ　文章编号：１００６—８２２８（２０１７）０９—３３—０４　

Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｐａｒａｌｌｅｌ　ｃｏｍｐｕｔｉｎｇ　ｉｎ　ｍａｔｒｉｃｅｓ　

Ｗａｎｇ　Ｔａｏ，Ｚｈａｏ　Ｙｉｎｇｃｈｅｎｇ，Ｌｉｕ　Ｘｉｎｙｕａｎ　

（Ｃｈｉｎａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｐｅｔｒｏｌｅｕｍ（Ｅａｓｔ　Ｃｈｉｎａ）Ｓｃｉｅｎｃｅ　Ｃｏｌｌｅｇｅ，Ｑｉｎｇｄａｏ，Ｓｈａｎｄｏｎｇ　２６６５８０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｓｏｌｖｉｎｇ　ｍａｎｙ　ｐｒａｃｔｉｃａｌ　ｐｒｏｂｌｅｍｓ，ｓｏｍｅ　ｈｉｇｈ—ｏｒｄｅｒ　ｍａｔｒｉｃｅｓ　ｏｆｔｅｎ　ｎｅｅｄ　ｔｏ　ｂｅ　ｃａｌｃｕｌａｔｅｄ．Ｈｏｗｅｖｅｒ，ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｓｅｒｉａｌ　ｃｏｍｐｕｔｉｎｇ　ｍｅｔｈｏｄｓ　ａｒｅ　ｏｆｔｅｎ　ｉｎｅｆｆｉｃｉｅｍ．Ｔｈｅｒｅｆｏｒｅ，ｓｅｒｉａｌ　ｐｒｏｇｒａｍｓ　ｎｅｅｄ　ｔｏ　ｂｅ　ｐａｒａｌｌｅｌｉｚｅｄ　ｔｏ　ｉｍｐｒｏｖｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｅｆｆｉｃｉｅｎｃｙ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｆｏｕｒ　ｐａｒａｌｌｅｌ　ｃｏｍｐｕｔｉｎｇ　ｍｅｔｈｏｄｓ，Ｗｉｎｄｏｗｓ，ＡＰＩ，ＯｐｅｎＭＰ，ＭＰＩ　ａｎｄ　ＰＰＬ，ａｒｅ　ｓｔｕｄｉｅｄ　ｏｎ　ｔｈｅｉｒ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｍａｔｒｉｘ　ｍｕｌｔｉｐｌｉｃａｔｉｏｎ．Ｂｙ　ｔｅｓｔｉｎｇ　ｔｈｅ　ｍａｔｒｉｃｅｓ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｓｉｚｅ，ａｎｄ　ｍｅａｓｕｒｉｎｇ　ｔｈｅ　ａｃｃｅｌｅｒａｔｉｏｎ　ｅｆｆｅｃｔ　ｏｆ　ｐａｒａｌｌｅｌｉｚａｔｉｏｎ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ａｃｃｅｌｅｒａｔｉｏｎ　ｒａｔｉｏ．ｔｈｅ　ａｃｃｅｌｅｒａｔｉｏｎ　ｅ岱。ｃｔ　ｉｓ　ｃｏｍｐａｒｅｄ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ａｌｌ　ｔｈｅ　ｆｏｕｒ　ｍｅｔｈｏｄｓ　ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｅｆｆｉｃｉｅｎｃｙ，ａｎｄ　ｔｈｅ　ａｃｃｅｌｅｒａｔｉｏｎ　ｅｆｒｅｃｔ　ｏｆ　ＭＰＩ　ｉｓ　ｔｈｅ　ｂｅｓｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｍｐｕｔａｔｉｏｎａｌ　ｅｆｆｉｃｉｅｎｃｙ；ｓｅｒｉａｌ　ｃｏｍｐｕｔｉｎｇ；ｐａｒａｌｌｅｌｉｚａｔｉｏｎ；ａｃｃｅｌｅｒａｔｉｏｎ　ｒａｔｉｏ　

并⾏计算与分布式计算区别与联系

并⾏计算、分布式计算以及⽹格计算和云计算都是属于⾼性能计算（HPC）的范畴，主要⽬的在于对⼤数据的分析与处理，但它们却存在很多差异。我们需要了解两者的原理、特点和运⽤的场合，对云计算的了解⼤有裨益。

之所以将两种计算技术放在⼀起，是因为这两种计算具有共同的特点，都是运⽤并⾏来获得更⾼性能计算，把⼤任务分为N个⼩任务。但两者还是有区别的，关于两者的区别在后⾯有介绍。

并⾏计算

1、并⾏计算概念

并⾏计算（Parallel Computing）⼜称平⾏计算是指⼀种能够让多条指令同时进⾏的计算模式，可分为时间并⾏和空间并⾏。时间并⾏即利⽤多条流⽔线同时作业，空间并⾏是指使⽤多个处理器执⾏并发计算，以降低解决复杂问题所需要的时间。

并⾏计算同时使⽤多种计算资源解决计算问题的过程。为执⾏并⾏计算，计算资源应包括⼀台配有多处理机（并⾏处理）的计算机、⼀个与⽹络相连的计算机专有编号，或者两者结合使⽤。并⾏计算主要⽬的在于两个⽅⾯：

(1) 加速求解问题的速度。

(2) 提⾼求解问题的规模。

2、并⾏计算的原理

并⾏计算能快速解决⼤型且复杂的计算问题。此外还能利⽤⾮本地资源，节约成本 ― 使⽤多个“廉价”计算资源取代⼤型计算机，同时克服单个计算机上存在的存储器限制。

为提⾼计算效率，并⾏计算处理问题⼀般分为以下三步：

（1）将⼯作分离成离散独⽴部分，有助于同时解决；

（2）同时并及时地执⾏多个程序指令；

（3）将处理完的结果返回主机经⼀定处理后显⽰输出。

从上图可以看出，串⾏计算必须按步骤⼀步⼀步计算才能出来最终结果。⽽并⾏计算则要将问题分成N多个⼦任务，每个⼦任务并⾏执⾏计算。⽽每个⼦任务是⾮独⽴的，每个⼦任务的计算结果决定最终的结果。这个和分布式计算不同。

3、并⾏计算需满⾜的基本条件

（1）并⾏计算机。并⾏计算机⾄少包含两台或两台以上处理机，这此处理机通过互联⽹络相互连接，相互通信。 （2）应⽤问题必须具有并⾏度。也就是说，应⽤可以分解为多个⼦任务，这些⼦任务可以并⾏地执⾏。将⼀个应⽤分解为多个⼦任务的过程，称为并⾏算法的设计。

一 种 保持 二 叉 搜 索 树 平 衡 的最 佳 方 法 ( 1980 。 E i l s l 对 于 组 合 判定

与组 合 优 化 等类 型 组 合搜 索 问 题 设 计并 行 处 理 算 法 无 疑 要 复 杂 一

些 , 。 提 出 了 一 组针 对 A V L 树结 构 的 搜索 。 与 插 入 等 操 作 处 理 的并 行

算 法 目前 比 较 成 熟 的 解 决 办 法 主 要有 状 态 空 间 图 S , 组 合搜 索 则 是 寻

找 定 义 在 对 象 集 中 方 法 搜 索 问题 可 以 表 示 成 一 种 由 与 丫 或 及 与或 等关 系 构 成 的 状 态 空 间 树 如 图 。 , “ ’ ` ” 一 个 或 多个 最 优 ( 或 次 优 解 的 寻

求 过 程 即 “ ” , 8 从集合 S 中找 出 所 有 的 ( 可 能 不 止 一 个 满 。 所 示 树 的 根节 点 代 表 待 求 解 的原始 问 题 内 节 点 代 表 求 解 的子 问 题 叶 节点 代 表 向

题 的 ; 解 状 态 两 分 支 之 间 ( 或 多 分 支之 间 有 弧 “ , , 足 条 件 的对 象 的 过 程

组 合 搜索 又 可 进 一 步 。 分 为 组 合 判 定和 组 合 优 化 , 前 者 是 寻 求 所有 、

满 足 约 束 条 件 的 可 行解 后 者 则 是 寻 求 满 足 U 标 志 的 为 与 节 点 而 无 弧

标志 的 则 为 ” “ ” , 条件 的最 优 解 。 一 或 节点 ” 。 a 纵 以 八八 爪 八 与树 ; 了 b

八 爪 八八 C 一 从 八 八 或树 ; 与 或树 图 8 状 态 空 间树 3 w “ ” a h e t , e t . a l

( 1955 , 描 绘 了组 合 搜 索 问 D I M 题 与 树 多步 处 理 方 法 指 出 在 S “ 模型 并