fbpx
维基百科

并行计算

十月 30, 2023

此条目的主題是parallel computing。关于concurrent computing，請見「并发计算」。

并行计算（英語：parallel computing）一般是指许多指令得以同时进行的计算模式。在同時進行的前提下，可以將計算的過程分解成小部份，之後以並行方式來加以解決[1]。

電腦軟體可以被分成數個運算步驟來執行。為了解決某個特定問題，軟體採用某個演算法，以一連串指令執行來完成。傳統上，這些指令都被送至單一的中央处理器，以循序方式執行完成。在這種處理方式下，單一時間中，只有單一指令被執行（processor level: 比较微处理器，CISC, 和RISC，即流水线Pipeline的概念，以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展，比如branch-prediction, 比如forwarding，比如在每个运算单元前的指令堆栈，汇编程序员对programm code的顺序改写）。平行運算採用了多個運算單元，同時執行，以解決問題。

基本体系结构 编辑

相对于串行计算，并行计算可以划分成时间并行和空间并行。时间并行即指令流水化，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。以程序和算法设计人员的角度看，并行计算又可分为数据并行和任务并行。数据并行把大的任务化解成若干个相同的子任务，处理起来比任务并行简单。

空间上的并行导致两类并行机的产生，按照麦克·弗莱因（Michael Flynn）的说法分为单指令流多数据流（SIMD）和多指令流多数据流（MIMD），而常用的串行机也称为单指令流单数据流（SISD）。MIMD类的机器又可分为常见的五类：并行向量处理机（PVP）、对称多处理机（SMP）、大规模并行处理机（MPP）、工作站机群（COW）、分布式共享存储处理机（DSM）。

访存模型 编辑

并行计算机有以下五种访存模型：均匀访存模型（UMA）、非均匀访存模型（NUMA）、全高速缓存访存模型（COMA）、一致性高速缓存非均匀存储访问模型（CC-NUMA）和非远程存储访问模型（NORMA）。

并行計算模型 编辑

不像串行计算机那样，主流使用冯·诺伊曼的计算模型，并行计算机没有一个统一的计算模型。不过，人们已经提出了几种有价值的参考模型：PRAM模型，BSP模型，LogP模型，C^3模型等。

并行计算机网络 编辑

并行计算机是靠网络将各个处理机或处理器连接起来的，一般来说有以下几种方式

  1. 静态连接：一维线性连接，网孔连接，超立方体连接，树连接，立方环连接，洗牌交换连接，蝶形连接，金字塔连接等。
  2. 动态连接：总线连接（Bus），交叉开关（CS），多级互联网络（MIN）。

网络的基本术语：

  1. 节点度
  2. 网络直径
  3. 对剖宽度
  4. 嵌入

并行计算机性能度量 编辑

  1. 基本指标
    1. 执行时间
    2. 工作负载
    3. 存取性能
  2. 加速比评测
    1. Amdahl定理
    2. Gustafson定理（英语：Gustafson's law）
    3. Sun-Ni定理
  3. 可扩放性标准
    1. 等效率标准
    2. 等速度标准
    3. 平均延迟标准

并行算法 编辑

并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。

  • 常见的非数值算法设计方法举例
    • 并行播送与并行求和
    • 并行排序算法；
    • 并行选择算法：所谓选择问题就是在一给定的序列中选择出某组（个）满足给定条件的元素。
    • 关于图论中的一些并行算法：
      • 图论作为一门到近代才发展起来的科学。在图论中有很多关于如何设计算法的问题，比如求最小生成树，单源最短路径等等。事实上，这些算法中有很多是可以并行化的，而且并行化时运用的思想具有很大的启发性，下面是几个常见的并行图论算法。
    • 关于串处理的并行算法：
      • KMP算法的并行化：在英特尔的开发手册《Intel® 64 and IA-32 Architectures Optimization Reference Manual》中，“14.3.3 Substring Searches”章节内提供了KMP算法基于SIMD指令集并行的C语言实现例程，可以作为KMP算法并行化的参考范例。其中涉及到若干SIMD Intrinsics指令，比如：_mm_loadu_si128、_mm_cmpestrs、_mm_cmpestri等，其具体含义及用法可从 Intel Intrinsics Guide（ https://intel-intrinsics.com/ （页面存档备份，存于互联网档案馆） ）在线手册中查询获悉。
  • 常见的数值算法设计方法举例

参考文献 编辑

  1. ^ 平行計算基礎理論,系統及應用研究. 國立中正大學資訊工程研究所. 1992 [2 June 2013]. 

参见 编辑

十月 30, 2023
并行计算, 此條目可参照英語維基百科相應條目来扩充, 此條目在對應語言版為高品質條目, 2022年6月29日, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, 此條目需要补充更多来源, 201. 此條目可参照英語維基百科相應條目来扩充 此條目在對應語言版為高品質條目 2022年6月29日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 此條目需要补充更多来源 2013年6月2日 请协助補充多方面可靠来源以改善这篇条目 无法查证的内容可能會因為异议提出而被移除 致使用者 请搜索一下条目的标题 来源搜索 并行计算 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 此条目的主題是parallel computing 关于concurrent computing 請見 并发计算 并行计算 英語 parallel computing 一般是指许多指令得以同时进行的计算模式 在同時進行的前提下 可以將計算的過程分解成小部份 之後以並行方式來加以解決 1 電腦軟體可以被分成數個運算步驟來執行 為了解決某個特定問題 軟體採用某個演算法 以一連串指令執行來完成 傳統上 這些指令都被送至單一的中央处理器 以循序方式執行完成 在這種處理方式下 單一時間中 只有單一指令被執行 processor level 比较微处理器 CISC 和RISC 即流水线Pipeline的概念 以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展 比如branch prediction 比如forwarding 比如在每个运算单元前的指令堆栈 汇编程序员对programm code的顺序改写 平行運算採用了多個運算單元 同時執行 以解決問題 目录 1 基本体系结构 2 访存模型 3 并行計算模型 4 并行计算机网络 5 并行计算机性能度量 6 并行算法 7 参考文献 8 参见基本体系结构 编辑相对于串行计算 并行计算可以划分成时间并行和空间并行 时间并行即指令流水化 空间并行使用多个处理器执行并发计算 当前研究的主要是空间的并行问题 以程序和算法设计人员的角度看 并行计算又可分为数据并行和任务并行 数据并行把大的任务化解成若干个相同的子任务 处理起来比任务并行简单 空间上的并行导致两类并行机的产生 按照麦克 弗莱因 Michael Flynn 的说法分为单指令流多数据流 SIMD 和多指令流多数据流 MIMD 而常用的串行机也称为单指令流单数据流 SISD MIMD类的机器又可分为常见的五类 并行向量处理机 PVP 对称多处理机 SMP 大规模并行处理机 MPP 工作站机群 COW 分布式共享存储处理机 DSM 访存模型 编辑并行计算机有以下五种访存模型 均匀访存模型 UMA 非均匀访存模型 NUMA 全高速缓存访存模型 COMA 一致性高速缓存非均匀存储访问模型 CC NUMA 和非远程存储访问模型 NORMA 并行計算模型 编辑不像串行计算机那样 主流使用冯 诺伊曼的计算模型 并行计算机没有一个统一的计算模型 不过 人们已经提出了几种有价值的参考模型 PRAM模型 BSP模型 LogP模型 C 3模型等 并行计算机网络 编辑并行计算机是靠网络将各个处理机或处理器连接起来的 一般来说有以下几种方式 静态连接 一维线性连接 网孔连接 超立方体连接 树连接 立方环连接 洗牌交换连接 蝶形连接 金字塔连接等 动态连接 总线连接 Bus 交叉开关 CS 多级互联网络 MIN 网络的基本术语 节点度 网络直径 对剖宽度 嵌入并行计算机性能度量 编辑基本指标 执行时间 工作负载 存取性能 加速比评测 Amdahl定理 Gustafson定理 英语 Gustafson s law Sun Ni定理 可扩放性标准 等效率标准 等速度标准 平均延迟标准并行算法 编辑此條目需要补充更多来源 2017年10月30日 请协助補充多方面可靠来源以改善这篇条目 无法查证的内容可能會因為异议提出而被移除 致使用者 请搜索一下条目的标题 来源搜索 并行计算 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 并行算法是一门还没有发展成熟的学科 虽然人们已经总结出了相当多的经验 但是远远不及串行算法那样丰富 并行算法设计中最常用的的方法是PCAM方法 即划分 通信 组合 映射 首先划分 就是将一个问题平均划分成若干份 并让各个处理器去同时执行 通信阶段 就是要分析执行过程中所要交换的数据和任务的协调情况 而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销 映射则是要将任务分配到每一个处理器上 总之 并行算法还需要相当多完善的地方 并行算法与串行算法最大的不同之处在于 并行算法不仅要考虑问题本身 而且还要考虑所使用的并行模型 网络连接等等 常见的非数值算法设计方法举例 并行播送与并行求和 并行排序算法 并行选择算法 所谓选择问题就是在一给定的序列中选择出某组 个 满足给定条件的元素 关于图论中的一些并行算法 图论作为一门到近代才发展起来的科学 在图论中有很多关于如何设计算法的问题 比如求最小生成树 单源最短路径等等 事实上 这些算法中有很多是可以并行化的 而且并行化时运用的思想具有很大的启发性 下面是几个常见的并行图论算法 关于串处理的并行算法 KMP算法的并行化 在英特尔的开发手册 Intel 64 and IA 32 Architectures Optimization Reference Manual 中 14 3 3 Substring Searches 章节内提供了KMP算法基于SIMD指令集并行的C语言实现例程 可以作为KMP算法并行化的参考范例 其中涉及到若干SIMD Intrinsics指令 比如 mm loadu si128 mm cmpestrs mm cmpestri等 其具体含义及用法可从 Intel Intrinsics Guide https intel intrinsics com 页面存档备份 存于互联网档案馆 在线手册中查询获悉 常见的数值算法设计方法举例 并行快速傅里叶变换 参考文献 编辑 平行計算基礎理論 系統及應用研究 國立中正大學資訊工程研究所 1992 2 June 2013 参见 编辑计算机科学 理论计算机科学 訊息傳遞介面 Message Passing Interface MPI 取自 https zh wikipedia org w index php title 并行计算 amp oldid 76073017, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。