精华内容
下载资源
问答
  • 并行计算与集群技术(1)
    2020-12-24 17:09:56

    并行计算概述

    并行计算是指同时使用多种计算资源解决计算问题的过程,是提高计算机系统计算速度和处理能力的一种有效方法。它的基本思想是,利用多个处理器来协同求解同一问题,即将被求解的问题分解成若干个部分,各部分均由一个独立的处理机来并行计算。在计算机术语中,并行性指的是把一个复杂问题分解成多个能同时处理子问题的能力。
    **并行计算的概念:**并行计算的主要目标是提高求解速度,通过扩大问题求解规模,解决大型而复杂的计算问题。即将需要做大量运算、持续时间长的大型串行任务,根据大任务的内在相关性分解成若干个相对独立的模块并行执行,从而节约运算时间。
    **并行计算:**开行计算是指同时使用多种计算资源解决计算问题的过程,是旨在提高计算机系统计算速度和处理能力的一种有效手段。它是由运行在多个部件上的小任务合作来求解一个规模很大的计算问题的一种方法。它的基本思想是用多个处理器来协同求解同一问题,即将被求解的问
    题拆分成若干个部分,各部分均由一个独立的处理机来进行计算。并行计算系统实际上是一种由多个计算单元组成,运算速度快、存储容量大、可靠性高的计算机系统。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机,也可以是以某种方式互连的若干台的独立计算机构成的集群,通过并行计算集群完成数据的处理,再将处理的结果返回给用户。
    并行计算的内涵包括了并行计算机体系结构、编译系统、并行算法、并行编程、并行软件技术、并行性能优化与评价、并行应用等。此外,并行计算可以定位为连接并行计算机系统和实际应用问题之间的桥梁。它辅助科学、工程及商业应用领域的专家,为在并行计算机上求解本领域问题提供了关键支撑。
    因此,为了成功实施并行计算,须具备3个基本条件:
    (1) 并行计算机。并行计算机至少包含两台或两台以上的处理机,井且这些处理机通计网络能相互连接、相互通信。
    (2)应用具有并行度。应用可以分解为多个子任务,这些子任务可以并行执行。将一个子任务分解为多个子任务的过程,便称为并行算法的设计。(3) 并行编程。在并行计算机提供的并行编程环境上,具体实现并行算法,编制并行程序并运行该程序,从而达到并行求解应用问题的目的。
    并行计算之所以可行,主要在于并发性是物质世界的一种普遍属性,具有实际应用背景的计算问题在多数情况下都可以拆分为能并行计算的多个子任务。

    并行计算的层次

       并行粒度(Granularity) 是两次并行或交互操作之间所执行的计算负载。也就是任务级,即任务量的大小。并行计算的层次按并行粒度可分为:程序级并行、子程序级并行、语句级并行、操作级并行和微操作级并行,后三层大都由硬件和编译器负责处理,开发者通常处理前两层的并行,即程序级并行和子程序级并行,我们通常所说的并行计算也关注的是前两层。
       并行度(Degree of Parallelism, DOP) 是同时执行的分进程数。
    

    并行度与并行粒度大小常互为倒数:增大粒度会减小并行度。增加并
    行度会增加系统(同步)开销。

    并行度(Degree of Parallelism, DOP) 是同时执行的分进程数。并行度与并行粒度大小常互为倒数:增大粒度会减小并行度。增加并行度会增加系统(同步)开销。
    一个数据分析任务能被切分为多个相互之间独立的计算任务并被分配给不同的结点进行处理,这种并行就叫程序级并行。程序级并行是一种粗粒度的并行,一个问题能实现程序级的
    并行意味着这个问题很容易在集群中被执行,并且由于被切分的任务的独立的,子问题之间所需要的通讯代价也是非常小的,不需要在集群结点间进行大量的数据传输。程序级并行中的各个计算任务可以被认为是没有任何计算关联和数据关联的任务,其并行性是天然的、宏观的。
    云计算与大数据关注的正是程序级并行。

    并行计算机的发展

    1.按时间看并行计算机的发展:
    在这里插入图片描述
    2.按应用特点看并行计算机的发展:
    并行计算机的发展历程也可以简单地分为两个时代。
    (1) 专用时代。包括向量机、MPP系统、SGI NUMA 系统、SUN 大型 SMP 系统,也包括我国的神威、银河、曙光1000等。之所以称为“专用”, 并不是说它们只能运行某种应用,是指它们的组成部件是专门设计的,它们的 CPU 板、内存板和 I/O板,甚至操作系统,都是不能在其他系统中使用。
    (2) 普及时代。高性能计算机价格下降,应用门槛降低,应用开始普及。两个技术趋势起
    到重要作用。其一是商品化趋势使得大量生产的商品部件性能接近了高性能计算机专有部件,标准化趋势使得这些部件之间能够集成到一个系统中,其中X86处理器、以太网、内存部件、Linux 操作系统的出现和发展都起到决定性作用。其二是目前高性能计算机的主流体系结
    构之一是集群系统,它的技术基础和工业基础都实现了工业标准化,性价比非常高。
    由于向量机和 MPP 受研制费用高、售价高等因素的影响,其市场受到一定的限制;SMP由于共享结构的限制,系统的规模不可能很大;而集群系统性能价格比较高,具有投资风险小、结构灵活、可扩展性强、通用性好、可继承现有软硬件资源和开发周期短、可编程性好等特点,成为主流并行计算机的发展趋势。
    云计算所需要的最基本的硬件就是大量串联起来的服务器集群。为了解决大量密集的服务器串联会带来主机散热问题,云计算数据中心通常采用“货柜式”摆放法,即将大量的服务器集群规整地摆放在类似集装箱的机柜里。为了实现云计算平台的效用性,对大规模服务器集群必须采用具有大规模、可伸缩性、数据可重复性以及容错和平衡负载等特性的串联技术。例如 Google的Altanta 数据中心与 Oregon Dellas 数据中心都是互为备份的,为了维护服务器之间的负载平衡,将计算工作平均分配到服务器集群中去。

    并行计算与分布式计算

    分布式计算:
    分布式计算主要研究分散系统(Distributed Svstem) 如何进行计算。分散系统是一组计算机通过计算机网络互连后形成的系统。分布式计算可以把程序放在最适合运行它的计算机上运行,实现共享稀有资源和平衡负载,这也是分布
    式计算的核心思想之一。
    并行计算是相对于串行计算来说的,并行计算主要目的是加速求解问题的速度和提高求解问题的规模。并行计算强调时效性和海量数据处理,各任务之间的独立性弱,而且关系密切,每个结点之间的任务时间要同步。即并行程序并行处理的任务包之间有很大的联系,并且并行计算的每一个任务块都是必要的,没有浪费的、分割的,就是每个任务包都要处理,而且计算结果相互影响,这就要求每个计算结果要绝对正确。
    分布式计算是相对于集中式计算来说的。分布式计算的任务包相互之间有独立性,上一个任务包的结果未返回或者是结果处理错误,对下一个任务包的处理几乎没有什么影响。分布式计算的实时性要求不高,并且允许存在计算错误(因为每个计算任务给好几个参与者计算,上传结果到服务器后要比较结果,然后对结果差异大的进行验证。也就是说,分布式计算不强调时效性,各任务之间相互独立,所以结点节可以没有通讯,即无网络信息传输。每个结点之间的任务执行时间没有限制。
    典型的分布式计算,如分析计算蛋白质的内部结构和相关药物的Folding@home 项目,该项目结构庞大,需要惊人的计算量,由一台计算机计算是不可能完成的。因此,该项目通过分布式计算技术把需要进行大量计算的工程数据分区成小块,分配给多台计算机分别计算,在各台计算机上传运算结果后,将结果统一合并得出数据结论。因此,有人认为分布式计算是并行计算的一种特例。
    分布式计算中,很多任务块可以根本不处理,即有大量的无用数据块。因此,分布式计算的速度尽管很快,但真正的“效率”是低之又低的。分布式要处理的问题一般是基于“寻找”模式的。所谓的“寻找”, 就相当于穷举法。为了尝试到每一个可能存在的结果,一般从0~n (某一数值)被一个一个的测试,直到找到所要求的结果。事实上,为了易于一次性探测到正确的结果,可以假设结果是以某个特殊形式开始的。在这种类型的搜索里,也许一开始就找到答案,也许到最后才找到答案,即分布式计算中可能一直在寻找答案,但有可能永远都找不到,也可能一开始就找到了。而并行计算的任务包个数相对有限,在一个有限的时间应该是可能完成的。

    并行计算与云计算

    云计算需要解决:计算资源的透明虚拟化和弹性化、内存储资源的透明虚拟化和弹性化、外存储资源的透明虚拟化和弹性化、数据安全的保障、向开发者提供完善的 API 并实现终端用户向云计算的平滑过渡。云计算将一切隐在云端,普通用户不再关心数据存在哪里,不再关心数据的安全,不再关心应用程序是否需要升级,不再关心计算机病毒的危害,这一切的工作都由云计算负责解决,普通用户要做的就是选择自己喜爱的云计算服务商购买自己需要的
    服务,并为之付费。云计算使普通用户有了享受高性能计算的机会,因为云计算中心几乎可以提供无限制的计算能力,计算的弹性化和存储的弹性化是云计算的重要特征。
    云计算的计算能力的实现是从计算机的并行化开始的,即把多个计算机并联起来,从而获得更快的计算速度,这是一种很简单也很朴系的买现高速计算的方法,也被证明是相当成功的方法。
    由于服务器的大量集中,服务器的失效成为经常的事情,传统的架构对于单点失效是很敏感的,而在云计算架构下单点失效成为系统认可的常态,任何的单点失效都不会影响系统对外提供服务。即云计算在构建系统架构时就将系统结点的失效考虑了进去,实现了基于不可信服务器结点的云计算基础架构。将服务器失效作为云计算系统的服务器集群模型是符合实际情况的,这种情况下单个服务器可以看作是不可信的结点,在系统设计时必须要将不可信服务器结点的失效屏蔽在系统之内,不向开发者和普通用户传递。在将服务器失效作为常态的服务器集群模型下,数据的安全性通过副本策略得到了保证。

    更多相关内容
  • mpi相关的期末考试,某些学校的考试原,可以利用该题目,加深印象
  • 2018年东北大学并行程序设计真题,供大家参考-
  • 并行计算导论第二版

    2017-11-19 11:12:32
    并行计算导论中文版第二版PDF,包含并行算法设计原则,并行平台解析,MPI OPENMP编程等,是学习并行计算的很好的教材,强烈推荐。
  • 覆盖了并行计算领域的传统问题,并且尽可能地采用与底层平台无关的体系结构和针对抽象模型来设计算法。书中选择MPI(Message Passing Interface)、POSIX线程和OpenMP这三个应用最广泛的编写可移植并行程序的标准作为...
  • 并行程序设计

    2018-09-16 11:24:42
    本书系统介绍并行程序设计原理及应用。除介绍常用的一些算法范例,包括分治、流水、同步计算、主从及工作池,还介绍了一些常用的经典数值和非数值算法,如排序、矩阵相乘、线性方程组求解、图像处理中的预处理和相应...
  • 被称为巨大挑战, Great Challenge” , 如人类基因全球气候准确预报海洋环流循 环等等没有万亿次以上的高性能计算机是无法解决的军事上的核爆炸模拟也必须使用 万亿次以上的高性能计算机美国90年代的有关高性能计算...
  •  涵盖从串行计算到并行计算的革命性变革,第6章专门介绍并行处理器,每章中都涉及并行硬件和软件的相关主题。  全书采用Intel Core i7、ARM Cortex-A8和NVIDIA Fermi GPU作为实例。  增加“运行更快”这...
  • 《计算机组成与设计:硬件/软件接口(原书第5版)》是计算机组成与设计的经典畅销教材,第5版经过全面更新,关注后PC时代发生在计算机体系结构领域的革命性变革——从单核处理器到多核微处理器,从串行到并行。...
  • [并行计算] 1. 并行计算简介

    万次阅读 多人点赞 2017-07-20 15:30:07
    这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的先导。因此,它只涵盖了并行计算的基础知识,实用于刚刚开始熟悉该主题的初学者。

    并行计算简介

    (本人刚刚完成这篇长文章的翻译,尚未认真校对。若里面有翻译错误和打字错误敬请谅解,并请参考原贴)

    1 摘要

    最近项目需要实现程序的并行化,刚好借着翻译这篇帖子的机会,了解和熟悉并行计算的基本概念和程序设计。帖子的原文见这里

    这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的先导。因此,它只涵盖了并行计算的基础知识,实用于刚刚开始熟悉该主题的初学者。我们并不会深入讨论并行计算,因为这将花费大量的时间。本教程从对并行计算是什么以及如何使用开始,讨论与其相关的概念和术语,然后解析并行内存架构(parallel memory architecture)以及编程模型(programming models)等。这些主题之后是一系列关于设计和运行并行计算程序的复杂问题的实践讨论。最后,本教程给出了几个并行化简单串行程序的示例。

    2 概述

    2.1 什么是并行计算?

    串行计算: 传统的软件通常被设计成为串行计算模式,具有如下特点:

    • 一个问题被分解成为一系列离散的指令;
    • 这些指令被顺次执行;
    • 所有指令均在一个处理器上被执行;
    • 在任何时刻,最多只有一个指令能够被执行。
      这里写图片描述
      例如,
      这里写图片描述

    并行计算: 简单来讲,并行计算就是同时使用多个计算资源来解决一个计算问题:

    • 一个问题被分解成为一系列可以并发执行的离散部分;
    • 每个部分可以进一步被分解成为一系列离散指令;
    • 来自每个部分的指令可以在不同的处理器上被同时执行;
    • 需要一个总体的控制/协作机制来负责对不同部分的执行情况进行调度。
      这里写图片描述
      例如,
      这里写图片描述

    这里的 计算问题 需要具有如下特点:

    • 能够被分解成为并发执行离散片段;
    • 不同的离散片段能够被在任意时刻执行;
    • 采用多个计算资源的花费时间要小于采用单个计算资源所花费的时间。

    这里的 计算资源 通常包括:

    • 具有多处理器/多核(multiple processors/cores)的计算机;
    • 任意数量的被连接在一起的计算机。

    并行计算机:
    通常来讲,从硬件的角度来讲,当前所有的单机都可以被认为是并行的:

    • 多功能单元(L1缓存,L2缓存,分支,预取,解码,浮点数,图形处理器,整数等)
    • 多执行单元/内核
    • 多硬件线程
      这里写图片描述
      IBM BG/Q Compute Chip with 18 cores (PU) and 16 L2 Cache units (L2)

    通过网络连接起来的多个单机也可以形成更大的并行计算机集群:
    这里写图片描述

    例如,下面的图解就显示了一个典型的LLNL并行计算机集群:

    • 每个计算结点就是一个多处理器的并行计算机;
    • 多个计算结点用无限宽带网络连接起来;
    • 某些特殊的结点(通常也是多处理器单机)被用来执行特定的任务。
      这里写图片描述

    2.2 为什么要并行计算?

    真实世界就是高度并行的:

    • 自然界中的万事万物都在并发的,按照其内在时间序列运行着;
    • 和串行计算相比,并行计算更适用于对现实世界中的复杂现象进行建模,模拟和理解;
    • 例如,可以想象对这些进行顺序建模:
      这里写图片描述
      这里写图片描述
      这里写图片描述

    主要理由:

    • 节约时间和成本:1)理论上来讲,在一个任务上投入更多的资源有利于缩短其完成时间,从而降低成本;2)并行计算机可以由大量廉价的单机构成,从而节约成本。
      这里写图片描述
    • 解决更大规模更复杂的问题:1)很多问题的规模和复杂度使得其难以在一个单机上面完成;2)一个有趣的例子:(Grand Challenge Problems)。3)网页搜索引擎/数据库每秒处理百万级别的吞吐量。
      这里写图片描述
    • 提供并发性:1)单个计算资源某个时间段只能做一件事情,而多计算资源则可以同时做多件事情;2)协同网络可以使得来自世界不同地区的人同时虚拟地沟通。
      这里写图片描述
    • 利用非局部的资源:1)可以利用更广范围中的网络资源;2)SETI@home的例子;以及3)Folding@home的例子。
      这里写图片描述
    • 更好地利用并行硬件:1)现代计算机甚至笔记本电脑在架构上都属于多处理器/多核的;2)并行软件已经适用于多核的并行硬件条件,例如线程等;3)在大多数情况下,运行在现代计算机上的串行程序实际上浪费了大量的计算资源。
    • 这里写图片描述

    并行计算的未来:

    • 在过去的二十多年中,快速发展的网络,分布式系统以及多处理器计算机架构(甚至在桌面机级别上)表明并行化才是计算的未来;
    • 在同一时期,超级计算机的性能已经有了至少50万倍的增加,而且目前还没有达到极限的迹象;
    • 目前的峰值计算速度已经达到了 1018 /秒。
      这里写图片描述

    2.3 谁都在使用并行计算?

    科学界和工程界:

    从历史上来讲,并行计算就被认为是“计算的高端”,许多科学和工程领域的研究团队在对很多领域的问题建模上都采用了并行计算这一模式,包括:大气与地球环境、应用物理、生物科学、遗传学、化学、分子科学、机械工程、电气工程、计算机科学、数学、国防和武器研发等。
    这里写图片描述

    工业界和商业界:

    如今,商业应用为更快速计算机的研发提供了更强劲的动力。这些商业应用程序需要以更复杂的方式处理大量数据,例如:大数据、数据库、数据挖掘、石油勘探、网页搜索引擎、基于web的商业服务、医学成像和诊断、跨国公司管理、高级图形学技术以及虚拟现实、网络视频和多媒体技术、协同工作环境等。
    这里写图片描述

    全球应用:
    并行计算目前在实际上被广泛采用于大量应用中。
    这里写图片描述

    3 概念和术语

    3.1 冯诺依曼体系结构

    以匈牙利数学家约翰·冯诺依曼命名的这一计算机体系结构,出现在他1945年发表的一篇论文中。这也通常被称为“存储程序计算机”——程序指令和数据都被保存在存储器中,这与早期通过“硬接线”编程的计算机不同。从此以后,所有的计算机走遵从这一基本架构:
    这里写图片描述 这里写图片描述
    - 四个组成部分:1)内存;2)控制器;3)处理器;4)输入输出。
    - 读写操作:支持随机存储的内存用来同时保存程序指令和数据:1)程序指令用来指导计算机操作;2)数据是程序用来操作的对象。
    - 控制器:从内存中读取指令或者数据,对这些指令进行解码并且顺序执行这些指令。
    - 处理器:提供基本的算术和逻辑操作。
    - 输入输出设备:是人机交互的接口。

    那么冯诺依曼体系结构和并行计算有什么关系呢?答案是:并行计算机仍然遵从这一基本架构,只是处理单元多于一个而已,其它的基本架构完全保持不变。

    3.2 弗林的经典分类

    有不同的方法对并行计算机进行分类(具体例子可参见并行计算分类)。

    一种被广泛采用的分类被称为弗林经典分类,诞生于1966年。弗林分类法从指令流数据流两个维度区分多处理器计算机体系结构。每个维度有且仅有两个状态:单个或者多个

    下面个矩阵定义了弗林分类的四个可能状态:
    这里写图片描述

    单指令单数据(SISD): SISD是标准意义上的串行机,具有如下特点:1)单指令:在每一个时钟周期内,CPU只能执行一个指令流;2)单数据:在每一个时钟周期内,输入设备只能输入一个数据流;3)执行结果是确定的。这是最古老的一种计算机类型。
    这里写图片描述 这里写图片描述

    单指令多数据(SIMD): SIMD属于一种类型的并行计算机,具有如下特点:1)单指令:所有处理单元在任何一个时钟周期内都执行同一条指令;2)多数据:每个处理单元可以处理不同的数据元素;3)非常适合于处理高度有序的任务,例如图形/图像处理;4)同步(锁步)及确定性执行;5)两个主要类型:处理器阵列和矢量管道。
    这里写图片描述

    这里写图片描述

    这里写图片描述

    **多指令单数据(MISD):**MISD属于一种类型的并行计算机,具有如下特点:1)多指令:不同的处理单元可以独立地执行不同的指令流;2)单数据:不同的处理单元接收的是同一单数据流。这种架构理论上是有的,但是工业实践中这种机型非常少。
    这里写图片描述 这里写图片描述

    多指令多数据(MIMD): MIMD属于最常见的一种类型的并行计算机,具有如下特点:1)多指令:不同的处理器可以在同一时刻处理不同的指令流;2)多数据:不同的处理器可以在同一时刻处理不同的数据;3)执行可以是同步的,也可以是异步的,可以是确定性的,也可以是不确定性的。这是目前主流的计算机架构类型,目前的超级计算机、并行计算机集群系统,网格,多处理器计算机,多核计算机等都属于这种类型。值得注意的是,许多MIMD类型的架构中实际也可能包括SIMD的子架构。
    这里写图片描述 这里写图片描述

    3.3 一些常见的并行计算术语

    和其它一些领域一样,并行计算也有自己的“术语”。下面列出了与并行计算相关联的一些常用术语,其中大部分术语我们在后面还会进行更详细的讨论。

    • 结点(Node): 也就是一个独立的“计算机单元”。通常由多个CPU处理器/处理内核,内存,网络接口等组成。结点联网在一起以构成超级计算机。
    • 中央处理器/套接字/处理器/核(CPU / Socket / Processor / Core): 这些术语也取决于我们讨论的语境。在过去,中央处理器通常是计算机中的一个单个执行单元。之后多处理器被植入到一个结点中。接着处理器又被设计成为多核,每个核成为一个独立的处理单元。具有多核的中央处理器有时候又被称为“套接字”——实际上也没有统一标准。所以目前来讲,我们称一个结点上具有多个中央处理器,每个中央处理器上又具有多个内核。
      这里写图片描述
    • 任务(Task): 任务通常是指一个逻辑上离散的计算工作部分。一个任务通常是一段程序或者一段类似于程序的指令集合,可以由一个处理器进行处理。一个并行程序通常由多个任务构成,并且可以运行在多个处理器上。
    • 流水线(Pipelining): 可以将任务分解成为不同的步骤,并且由不同的处理单元完成,里面有输入流通过。这非常类似于一个装配线,属于一种类型的并行计算。
    • 共享内存(Shared Memory): 从严格的硬件角度来讲,共享内存描述了一种计算机架构,其中所有的处理器都可以对共同的物理内存进行直接存取(通常是通过总线)。从编程的角度来讲,共享内存描述了一种模型,其中所有的并行任务都具有同一内存形态,并且都可以直接对同一内存区域进行直接定位和存取,而无论该物理内存实际上在哪里(也许在千里之外的另外一个计算机上?)。
    • 对称多处理器(Symmetric Multi-Processor (SMP)): 属于一种共享内存的硬件架构,并且不同的处理器对内存以及其它资源都具有同等的访问权限(个人理解,就是不同处理器在角色上没有任何区别)。
    • 分布式内存(Distributed Memory): 在硬件中,表示基于网络的内存存取方式;在编程模型中,表示任务仅仅能够从逻辑上“看到”本机上的内存,但是在其它任务执行的时候,必须通过通讯才能对其它任务所运行的机器上的内存进行存取。
    • 通讯(communications): 并行任务通常需要数据交换。实现数据交换的方式有多种,例如通过共享内存或者通过网络。但是通常意义上,数据交换指的就是通讯,而无论其实现方式。
    • 同步(Synchronization): 指的是并行任务之间的实时协调,通常伴随着通讯(communication)。同步通常由在程序中设立同步点来实现,也就是说,在其它任务没有执行到这一同步点的时候,某一任务不能进一步执行后面的指令。同步通常涉及到需要等待其它任务的完成,因此有时候会增加并行程序的执行时间。
    • 粒度(Granularity): 在并行计算中,粒度定量地描述了计算与通讯的比率。粗粒度表示在通讯过程中需要做大量的计算性工作;细粒度则表示在通讯过程中需要做的计算性工作并不多。
    • 加速比(Observed Speedup): 这是检测并行计算性能的最简单并且最被广泛使用的度量策略,其定义如下:
    • 并行开销(Parallel Overhead): 指的是相对于做实际计算,做协调并行任务所需要花费的时间总数。影响并行开销的因素主要包括:1)任务启动时间;2)同步;3)数据通讯;4)由并行语言,链接库,操作系统等因素而导致的软件开销;5)任务终止时间。
    • 大规模并行(Massive Parallel): 指那些包含并行系统的硬件——拥有很多的处理元件。这里的“很多”可能会随着硬件条件的进步而不断增加,但目前,最大的并行系统所拥有的处理元件高达上百万件。
    • 尴尬并行(Embarrassingly Parallel): 指的是同时解决很多类似而又独立的任务,其中任务之间几乎没有需要协调的地方。
    • 可扩展性(Scalability): 指的是并行系统(包括软件和硬件)通过添加更多资源来成比例增加并行速度的能力。影响可扩展性的因素主要包括:1)硬件,尤其是内存-处理器带宽以及网络通讯的质量和速度;2)应用算法;3)相对并行开销;4)具体应用的特征。

    3.4 并行程序的缺陷和代价

    阿姆达尔定律: 阿姆达尔定律说一个程序的加速比潜力由其可以并行的部分所占的比例而决定,即:
    speedup=11P .
    如果没有代码可以被并行,那么p = 0,所以加速比为1。如果所有的代码都可以被并行,那么 p = 1,加速比为无穷大(当然只是理论上而言)。如果50%的代码可以被并行,那么最大的加速比为2,意味着的运行速度最快可以被加速到2倍。

    如果引入并行程序中的处理器个数,则加速比可以被重新定义为:
    speedup=1PN+S=11P+PN
    其中P仍然是并行代码所占的比例,N是处理器个数,S是串行代码所占比例(S = 1 - P)。
    这里写图片描述 这里写图片描述

    NP = 0.50p = 0.90p = 0.95p = 0.99
    101.825.266.899.17
    1001.989.1716.8050.25
    10001.999.9119.6290.99
    100001.999.9119.9699。02
    1000001.999.9919.9999.90

    之后我们就迅速意识到并行计算的极限所在,例如上表所示。

    “注明引言:”你可以花费一生的时间使得你的代码的95%都可以被并行,然而你如论投入多少处理器,都不会获得20倍的加速比。

    然而,某些问题我们可以通过增加问题的大小来提高其性能。例如:

    类型时间比例
    2D网格计算85秒85%
    串行比例15秒15%

    我们可以增加网格的维度,并且将时间步长减半。其结果是四倍的网格点数量,以及两倍的时间步长。之后的花费时间将变为:

    类型时间比例
    2D网格计算680秒97.84%
    串行比例15秒2.16%

    比起具有固定并行时间百分比的问题,那些可以随着问题规模增大而不断提高并行时间百分比的问题在并行化的意义上更具有可扩展性(复习一下可扩展性的定义^_^)。

    复杂性: 通常而言,并行计算的程序要比相应的串行计算程序更加复杂,也许复杂一个量级。你不仅需要同时执行不同的指令流,而且需要注意他们之间数据的通信。复杂性通常由涉及软件开发周期各个方面的时间来确定,主要包括:1)设计;2)编码;3)调试;4)调参;5)维护。

    遵循良好的软件开发实践对并行应用开发是至关重要的,尤其是在除你之外的其他人还需要和你合作的情况下。

    可移植性: 由于一些API的标准化,例如MPI,POSIX线程以及OpenMP,并行程序的可移植性问题并不像过去那么严重,然而:

    • 所有串行程序中所遇到的可移植性问题都会出现在相应的并行程序中。
    • 尽管一些API已经被标准话,但是在一些细节的实现上任然有差异,有时候这些细节实现会影响到可移植性。
    • 操作系统也会是导致可移植性的关键因素。
    • 硬件架构的不同有时候也会影响到可移植性。

    资源需求:
    并行编程的主要目标就是降低时钟等待时间。然而要做到这一点,需要更多的CPU时间。例如,一个在8个处理器上跑了一个小时的并行程序实际上花费了8小时的CPU时间。

    并行程序所需要的内存开销往往要大于相对应的串行程序,这是因为我们有时候需要复制数据,以满足库和子系统对并行算法的要求。

    对于运行时间较短的并行陈顾,实际性能反而有可能比相对应的串行程序有所降低。这是由于并行环境的建立,任务创建,通讯,任务结束等在这个运行时间中有可能会占有比较大的比例。

    可扩展性:
    基于时间和解决方案的不同,可以将扩展性分为强可扩展性弱可扩展性

    强可扩展性的特点是:1)在更多处理器被加入的时候,问题本身的规模不会增加;2)目标是将同一问题运行的更快;3)理想状态下,相比于对应的串行程序,运行时间为1/P。

    弱可扩展性的特点是:1)随着更多处理器被加入,每个处理上需要处理的问题规模保持一致;2)目标是在相同的时间内解决更多规模的问题;3)理想状态下,在相同时间内,可以解决的问题规模增加为原问题规模的P倍。

    并行程序的性能提高取决于一系列相互依赖的因素,简单地增加更多的处理器并不一定是唯一的方法。

    此外,某些问题可能本身存在扩展性的极限,因此添加更多的资源有时候反而会降低性能。这种情形会出现在很多并行程序中。

    硬件在可扩展性方面也扮演者重要角色,例如:1)内存-CPU之间的带宽;2)通讯网络的带宽;3)某个机器或者某个机器集合中的内存大小;4)时钟处理速度。

    支持并行的库或者子系统同样也会限制并行程序的可扩展性。
    这里写图片描述

    4 并行计算机的内存架构

    4.1 共享内存

    一般特征: 共享内存的并行计算机虽然也分很多种,但是通常而言,它们都可以让所有处理器以全局寻址的方式访问所有的内存空间。多个处理器可以独立地操作,但是它们共享同一片内存。一个处理器对内存地址的改变对其它处理器来说是可见的。根据内存访问时间,可以将已有的共享内存机器分为统一内存存取非统一内存存取两种类型。

    统一内存存取(Uniform Memory Access): 目前更多地被称为对称多处理器机器(Symmetric Multiprocessor (SMP)),每个处理器都是相同的,并且其对内存的存取和存取之间都是无差别的。有时候也会被称为CC-UMA (Cache coherent - UMA)。缓存想干意味着如果一个处理器更新共享内存中的位置,则所有其它处理器都会了解该更新。缓存一致性是在硬件级别上实现的。

    这里写图片描述

    非统一内存存取(Non-Uniform Memory Access): 通常由两个或者多个物理上相连的SMP。一个SMP可以存取其它SMP上的内存。不是所有处理器对所有内存都具有相同的存取或者存取时间。通过连接而进行内存存取速度会更慢一些。如果缓存相缓存想干的特性在这里仍然被保持,那么也可以被称为CC-NUMA。

    这里写图片描述

    优点:全局地址空间提供了一种用户友好的编程方式,并且由于内存与CPU的阶级程度,使得任务之间的数据共享既快速又统一。

    缺点:最大的缺点是内存和CPU之间缺少较好的可扩展性。增加更多的CPU意味着更加共享内存和缓存想干系统上的存取流量,从而几何级别地增加缓存/内存管理的工作量。同时也增加了程序员的责任,因为他需要确保全局内存“正确”的访问以及同步。

    4.2 分布式内存

    一般概念: 分布式内存架构也可以分为很多种,但是它们仍然有一些共同特征。分布式内存结构需要通讯网络,将不同的内存连接起来。一般而言,处理器会有它们所对应的内存。一个处理器所对应的内存地址不会映射到其它处理器上,所以在这种分布式内存架构中,不存在各个处理器所共享的全局内存地址。
    这里写图片描述

    由于每个处理器具有它所对应的局部内存,所以它们可以独立进行操作。一个本地内存上所发生的变化并不会被其它处理器所知晓。因此,缓存想干的概念在分布式内存架构中并不存在。

    如果一个处理器需要对其它处理器上的数据进行存取,那么往往程序员需要明确地定义数据通讯的时间和方式,任务之间的同步因此就成为程序员的职责。尽管分布式内存架构中用于数据传输的网络结构可以像以太网一样简单,但在实践中它们的变化往往也很大。

    优点: 1)内存可以随着处理器的数量而扩展,增加处理器的数量的同时,内存的大小也在成比例地增加;2)每个处理器可以快速地访问自己的内存而不会受到干扰,并且没有维护全局告诉缓存一致性所带来的开销;3)成本效益:可以使用现有的处理器和网络。

    缺点: 1)程序员需要负责处理器之间数据通讯相关的许多细节;2)将基于全局内存的现有数据结构映射到该分布式内存组织可能会存在困难;3)非均匀的内存访问时间——驻留在远程结点上的数据比本地结点上的数据需要长的多的访问时间。

    4.3 混合分布式-共享内存

    一般概念: 目前世界上最大和最快的并行计算机往往同时具有分布式和共享式的内存架构。共享式内存架构可以是共线内存机器或者图形处理单元(GPU)。分布式内存组件可以是由多个共享内存/GPU连接而成的系统。每个结点只知道自己的内存,不知道网络上其它结点的内存。因此,需要在不同的机器上通过网络进行数据通讯。

    从目前的趋势来看,这种混合式的内存架构将长期占有主导地位,并且成为高端计算在可见的未来中的最好选择。

    优缺点: 1)继承了共享式内存和分布式内存的优缺点;2)优点之一是可扩展性;3)缺点之一是编程的复杂性。

    5. 并行计算模型

    5.1 概述

    常见的并行编程模型包括:共享内存模型(无线程),线程模型,分布式内存/消息传递模型,数据并行模型,混合模型,单程序多数据模型,多程序多数据模型。

    并行计算模型是作为硬件和内存架构之上的一种抽象存在。虽然不一定显而易见,但这些模型并不和特定的机器和内存架构有关。事实上,任何一个并行计算模型从理论上来讲都可以实现在任何一种硬件上。下面是两个例子。

    在分布式内存架构上的共享内存模型。 机器内存分布于网络上的不同结点,但是对于用户而言,看到的确实一个具有全局地址空间的共享内存。这种方法通常被称为“虚拟共享存储器”。
    这里写图片描述 这里写图片描述

    在共享内存架构上的分布式内存模型。 最主要的是消息传递接口(MPI)。每个任务都可以直接访问跨所有机器的全局地址空间。然而,它们之间数据交换却是通过消息传递机制实现的,就像在分布式内存网络中所进行的那样。
    这里写图片描述 这里写图片描述

    那么到底使用哪一种呢?这往往取决于现有条件以及用户的偏好。没有最好的模型,但对模型的实现质量却可能存在差别。下面我们将分别描述上面提到的各种并行计算模型,并且讨论它们在实践中的一些实现方式。

    5.2 共享内存模型(无线程)

    在这种并行计算模型中,处理器/任务共享内存空间,并且可以异步地对内存进行读写。很多机制被用来控制对内存的存取,例如锁/信号量等,用来解决访问冲突以及避免死锁。这应该是最简单的并行计算模型了。

    从编程者的角度来看,这种模型的好处之一数据“拥有者”的缺失,所以他们不必明确地指定数据之间的通讯。所有的处理器都可以看到和平等地存取共享内存。程序开发将因此而变得容易。

    性能方面的一个重要缺点是对数据局部性的理解和管理讲变得困难:1)保持数据的局部性将有利于减少内存的存取负担,缓存刷新次数以及总线流量。而当多个处理器使用同一数据时,这些负担将会经常发生;2)不幸的是,保持数据的局部性往往比较难以理解,并且其难度超过一般用户的水平。

    这里写图片描述

    实现: 单机共享内存机器,本地操作系统,编译器及其对应的硬件都支持共享内存编程。在分布式内存机器上,内存在物理上存在于网络上不同的结点上,但是可以通过特殊的硬件和软件,将其变为全局可见。

    5.3 线程模型

    这是共享内存编程的一种模式。在线程模型中,一个单个的“重量级”进程可以拥有多个“轻量级”的并发执行路径。例如下图所示:

    • 主程序 a.out 在本地操作系统上运行。a.out 需要加载所有的系统和用户资源来运行,这是里面的“重量级”进程。
    • a.out 首先执行一些串行工作,然后生成一系列任务(线程),而这些线程可以在操作系统中被并发地执行。
    • 每个线程具有本地数据,但同时也共享 a.out 的所有资源。这节约了所有线程都复制程序资源的的开销。而每个线程同时也从全局内存中获益,因为它可以共享 a.out 的内存空间。
    • 一个线程的工作可以被描述为主程序的一个子程序。任何线程都可以在其它线程运行的同时执行任何子程序。
    • 线程之间的通讯通过全局内存来实现(对全局地址的更新)。这需要建立一种同步机制,以保证在同一时刻,不会有多个线程对同一块地址空间进行更新。
    • 线程可以随时生成和结束,但是 a.out 却一直存在,以提供所需的共享资源,直到整个应用程序结束。

    这里写图片描述

    实现: 从编程的角度来讲,线程的实现通常包括如下两个方面:

    • 库函数或者子程序,这些库函数或者子程序可以在并行源代码中被调用;
    • 嵌入在并行或者串行源代码中的一组编译器指令集合。

    程序员需要同时定义上面的两个方面(尽管有时候编译器可以提供帮助)。

    线程并不是一个新概念。之前硬件供应商就曾经实现过他们自己的线程。由于这些线程的实现各不相同,所以使得程序员很难开发可移植的多线程应用程序。

    而标准化工作却导致了两种完全不同的线程实现方式:POSIX ThreadsOpenMP

    POSIX Threads:由IEEE POSIX 1003.1c standard (1995)定义,仅支持C语言,是Unix/Linux操作系统的一部分,是基于库函数的,也通常被称为“Pthreads”。是非常明确的并行机制,需要程序员注意大量的细节。更多信息可见:POSIX Threads tutorial

    OpenMP:是一个工业标准,有一组主要计算机硬件和软件提供商,组织和个人联合发起和定义,是基于编译器指令的,具有可移植性/跨平台性,目前支持的包括Unix和Windows平台,目前支持C/C++和Fortran语言。非常简单和医用,提供了“增量并行”,可以从串行代码开始。更多信息可见:OpenMP tutorial

    也有一些其它的常见线程实现,但是在这里没有讨论,包括:

    • Microsoft threads
    • Java, Python threads
    • CUDA threads for GPUs

    5.4 分布式内存/消息传递模型

    这种模型具有如下特点:

    • 在计算的过程中,每个任务都仅仅使用它们自身的本地内存。多个任务既可以寄宿在同一个物理机器上,也可以跨越不同的物理机器。
    • 任务之间的数据交换是通过发送和接收消息而实现的。
    • 数据传输通常需要不同进程之间的协同操作才能实现。例如,一个发送操作需要同时对应一个接收操作。

    这里写图片描述

    实现: 从编程的角度来讲,消息传递的实现通常包括子程序库。对这些子程序的调用往往就嵌入在源代码中。编程者负责并行机制的实现。

    自从1980年代以来,出现了多种消息传递库函数。这些实现各不相同,导致编程者很难开发出移植性好的应用程序。自从1992年开始,MPI Forum形成,其主要目标是建立消息传递的标准接口。消息传递接口(Message Passing Interface (MPI))的第一部分在1994年发布,第二部分在1996年发布,第三部分在2012年发布。所有的MPI说明可以参见 http://mpi-forum.org/docs/。MPI成为了事实上的消息传递的工业标准,取代了所有其它消息传递的实现。几乎所有流行的并行计算平台都存在MPI的实现,但并不是所有的实现都包含了MPI-1,MPI-2和MPI-3的所有内容。关于MPI的更多信息可以参见 MPI tutorial

    5.5 数据并行模型

    通常也被称为“全局地址空间分区”(Partitioned Global Address Space (PGAS))模型。具有如下特点:

    • 地址空间被认为是全局的。
    • 大多数的并行工作聚焦于在数据集上的操作。数据集通常被组织成为常用的结构,例如数组,数立方等。
    • 一系列任务在同一块数据结构上操作,但是每个任务却操作在该数据结构的不同分区上。
    • 每个任务在数据结构的不同分区上执行相同的操作,例如,“给每个数组元素加上4”。

    这里写图片描述

    在共享内存的架构下,所有的任务通过全局内存方式来对数据进行存取;在分布式内存架构下,根据任务分配,全局数据结构在物理或者逻辑上被进行分割。

    实现: 目前,基于数据并行/PGAS模型,有如下几个相对有名的实现:

    • Coarray Fortran: 为了支持SPMD并行编程而在Fortran 95上做的一个小的扩展,是编译器相关的,更多信息可以参见:https://en.wikipedia.org/wiki/Coarray_Fortran
    • Unified Parallel C (UPC): 为了支持SPMD并行编程而在C语言基础上做的扩展,也是编译器相关的,更多信息可以参见:http://upc.lbl.gov/

    5.6 混合模型

    混合模型指的是包含了至少两个我们前面提到的并行计算模型的模型。目前,最常见的混合模型的例子是消息传递模型(MPI)和线程模型(OpenMP)的结合:

    • 线程使用本地数据完成计算密集型的任务;
    • 不同的进程则在不同的结点上通过MPI完成数据通讯。

    这种混合模型非常适合目前流行的硬件环境——多核计算机组成的集群系统。

    这里写图片描述

    另外一种类似的,但原来越流行的例子是采用MPI和CPU-GPU的混合编程:

    • 采用MPI的任务运行于CPU上,使用本地内存上的数据,但是通过网络与其它任务进行数据交换;
    • 而计算密集型的核则被加载到GPU上进行计算;
    • 而结点内部的内存和GPU上的数据交换则通过CUDA(或者类似的东西)进行数据交换。

    这里写图片描述

    其它混合模型还包括:

    • MPI和Pthreads的混合;
    • MPI和non-GPU加速器的混合。

    5.7 单程序多数据模型(SPMD)和多程序多数据模型(MPMD)

    单程序多数据模型(Single Program Multiple Data (SPMD)): SPMD事实上是一种可以架构在其它并行编程模型之上的更“高级”的编程模型:

    • 单程序:所有任务都执行同一个程序的拷贝,而这里的程序可以是线程,消息传递,数据并行甚至混合;
    • 多数据:不同的任务操作于不同的数据。

    SMPD通常需要指定任务的执行逻辑,也就是不同的任务可能会根据分支和逻辑关系,去执行整个程序的某个部分,也就是说,不是所有的任务都必须执行整个程序——有可能只是整个程序的某个部分。(译者注:如果不强调这一点,SPMD就退化成了数据并行模型了。)

    而这种采用消息消息传递或者混合编程的SPMD模型,有可能是今天运行在多核集群系统上的最常见的并行计算模型了。

    这里写图片描述

    多程序多数据模型(Multiple Program Multiple Data (MPMD)):

    和SPMD一样,多程序多数据模型实际上也是一种可以架构在其它并行编程模型基础上的“高级”并行编程模型:

    • 多程序:任务可以同时执行不同的程序,这里的程序可以是线程,消息传递,数据并行或者它们的混合。
    • 多数据:所有的任务可以使用不同的数据。

    MPMD应用并不像SPMD应用那么常见,但是它可能更适合于特定类型的程序。

    这里写图片描述

    6 并行程序设计

    6.1 自动 vs. 手动并行化

    设计和实现并行程序是一个非常手动的过程,程序员通常需要负责识别和实现并行化,而通常手动开发并行程序是一个耗时,复杂,易于出错并且迭代的过程。很多年来,很多工具被开发出来,用以协助程序员将串行程序转化为并行程序,而最常见的工具就是可以自动并行化串行程序的并行编译器(parallelizing compiler)或者预处理器 (pre-processor)。

    并行编译器通常以如下两种方式工作:

    • 完全自动: 由编译器分析源代码并且识别可以并行化的部分,这里的分析包括识别出哪些部分满足并行化的条件,以及权衡并行化是否真的可以提高性能。循环(包括do, for)通常是最容易被并行化的部分。
    • 程序员指令: 通过采用“编译器指令”或者编译器标识,程序员明确地告诉编译器如何并行化代码,而这可能会和某些自动化的并行过程结合起来使用。

    最常见的由编译器生成的并行化程序是通过使用结点内部的共享内存和线程实现的(例如OpenMP)。

    如果你已经有了串行的程序,并且有时间和预算方面的限制,那么自动并行化也许是一个好的选择,但是有几个重要的注意事项:1)可能会产生错误的结果;2)性能实际上可能会降低;3)可能不如手动并行那么灵活;4)只局限于代码的某个子集(通常是循环);5)可能实际上无法真正并行化,由于编译器发现里面有依赖或者代码过于复杂。

    接下来的部分仅适用于手动开发并行程序。

    6.2 理解问题和程序

    毫无疑问,开发并行程序的第一步就是理解你将要通过并行化来解决的问题。如果你是从一个已有的串行程序开始的,那么你需要首先理解这个串行程序。

    在开始尝试开发并行解决方案之前,需要确定该问题是否真正可以被并行化。

    • 一个容易被并行化的问题如下。该问题容易被并行化,因为每个分子构象都是独立且确定的。计算最小能量构象也是一个可以被并行化的问题。

    计算数千个独立分子构象中每一个的势能,完成之后,找出能量构象最小的那一个。

    • 一个不太可能被并行化的问题如下。由于F(n)同时依赖于F(n-1)和F(n-2),而后者需要提前被计算出来。

    采用如下公式计算菲波那切数列 (0,1,1,2,3,5,8,13,21,…):F(n) = F(n-1) + F(n-2)。

    识别程序的关键点 (hotspots)

    • 了解哪个部分完成了程序的大多数工作。大多数的科学和技术程序中,大多数的工作都是在某些小片段中完成的。
    • 可以通过剖析器或者性能分析工具来帮助你分析。
    • 专注于程序中这些关键点,忽略那些占用少量CPU的其余部分。

    识别程序中的瓶颈 (bottlenecks)

    • 有没有导致程序不成比例地变慢的,或者导致并行程序停止或者延迟的部分?例如有时候输入输出操作会导致程序变慢。
    • 有时候也可能通过重构程序,或者采用不同的算法来降低或者消除这些执行很慢的区域。

    识别并行化的抑制因素。一个常见的类型是数据依赖性 (data dependence),例如上面提到的菲波那切数列的例子。

    如果可能的话,研究其它算法。这可能是设计并行程序的过程中最重要的一点。

    利用成熟的第三方并行软件,或者高度成熟的数学库(例如IBM的ESSL,Intel的MKL,AMD的AMCL等)。

    这里写图片描述

    6.3 分割 (Partitioning)

    设计并行程序的第一步就是将程序分解成为可以分配到不同任务中去的“块”。这被称为程序的分解 (decomposition) 或者分割 (partitioning)。通常有两种基本方法可以将并行任务进行分解:域分解功能分解

    域分解: 在这种分割方式中,将数根据问题进行分解。每个并行任务操作数据的一部分。

    这里写图片描述

    通常由不同的方式来对数据进行分割:

    这里写图片描述

    功能分解:

    在这种方法中,重点在于要执行的计算,而不是计算所操纵的数据。问题根据要做的工作进行分解,然后每个任务执行整个工作的一部分。

    这里写图片描述

    这种功能分解非常适合于可分为不同任务的问题,例如:

    • 生态系统建模: 每个程序计算给定组的人口,其中每个组的正常取决于其邻居的增长。锁着时间的推移,每个进程计算当前状态,然后与相邻群体交换信息。然后所有任务进行下一步计算。

    这里写图片描述

    • 信号处理: 音频信号数据集通过四个不同的计算滤波器,每个滤波器是一个单独的过程。第一段数据必须通过第一个滤波器,然后才能进入第二个滤波器。当这样做时,第二段数据通过了第一个滤波器。当第四个数据段处于第一个滤波器时(以及之后),四个任务都会变得很忙。

    这里写图片描述

    • 气候建模: 每个模型组件都可以被认为是一个单独的任务。箭头表示计算期间组件之间的数据交换:大气模型需要使用风速数据生成海洋模型;海洋模型使用海面温度数据生成大气模型等。

    这里写图片描述

    在实践中将这两种分解方式结合起来是很自然的,也是很常见的。

    6.4 通讯 (Communications)

    任务之间的通讯需求取决于你的问题:

    不需要通讯的情况: 一些程序可以被分解成为并发执行的任务,而这些任务之间不需要共享数据。这类问题往往被称为“尴尬并行”——任务之间不需要数据通讯。例如如果我们需要对下面一副图片的颜色进行取反(黑色的部分变为白色的,白色的变为黑色的),那么图像数据可以被简单地分解为多个任务,并且每个任务可以被独立地执行。

    这里写图片描述

    需要通讯的情况: 大多数并行程序并不像上一问题这么简单,任务之间确实需要共享数据。例如下面这幅热度扩散图需要一个任务知道其它任务在它的邻居方格中的计算结果。邻居数据的变化将直接影响到该任务的数据。

    这里写图片描述

    设计通讯需要考虑的因素: 在设计程序任务之间的通讯时,有大量的重要因素需要考虑:

    • 通讯开销: 1)任务间通讯几乎总是意味着开销。2)而可以用于计算的机器周期以及资源会转而用于对数据的封装和传输。3)频繁的通讯也需要任务之间的同步,这有可能会导致任务花费时间等待而不是执行。4)竞争通讯流量可能使可用的网络带宽饱和,从而进一步加剧性能问题。

    • 延迟 vs. 带宽: 1)延迟 指的是从A点到B点发送最小量的信息所需要花费的时间,通常以毫秒计。2)带宽 指的是单位时间内可以传输的数据总量,通常以M/S或者G/S来计。3)发送大量的短消息可能会导致延迟成为通讯的主要开销。通常情况下将大量小信息封装成为大消息会更加有效,从而提高通讯带宽的利用效率。

    • 通讯可见性: 1)在消息传递模型中,通讯往往是显式和可见的,并且在编程者的控制之下。2)在数据并行模型中,通讯对编程者来说往往是透明的,尤其是在分布式内存架构中。编程者往往甚至不能明确知道任务之间的通讯是如何完成的。

    • 同步 vs. 异步通讯: 1) 同步通讯需要共享数据的任务之间某种意义上的“握手”。这既可以由编程者显式地指定,也可以在底层被隐式地实现而不为编程者所知。2)同步通讯业常常被称为“阻塞通讯”,因为一些任务必须等待直到它们和其它任务之间的通讯完成。3)异步通讯允许任务之间独立地传输数据。例如任务1可以准备并且发送消息给任务2,然后立即开始做其它工作,它并不关心任务2什么时候真正受到数据。4)异步通讯也常常被称为“非阻塞通讯”,因为在通讯发生的过程中,任务还可以完成其它工作。5)在计算和通讯自由转换是异步通讯的最大优势所在。

    • 通讯的范围: 明确哪些任务之间需要通讯在设计并行代码的过程中是非常关键的。下面两种通讯范围既可以被设计为同步的,也可以被设计为异步的:1)点对点通讯: 涉及到两个任务,其中一个扮演消息发送者/生产者的角色,另外一个扮演消息接受者/消费者的角色。2)广播通讯: 涉及到多于两个任务之间的数据共享。这些任务通常处于一个组或者集合中。

    这里写图片描述

    • 通讯的效率: 通常编程者具有影响通讯性能的选择,这里列举其中一些:1)对于一个给定的模型,究竟应该采用哪一种实现?例如对于消息传递模型而言,一种MPI的实现可能在某个给定的硬件下比其它实现要快。2)什么采用什么类型的通讯操作?正如前面所提到的,异步通讯操作往往可以提高程序的整体性能。3)网络结构(network fabric):某些平台可能会提供多于一个的网络结构。那么究竟哪一个最好?

    • 开销和复杂性:

    这里写图片描述

    最后需要意识到,上面提到的仅仅是需要注意的问题的一部分!

    6.5 同步 (Synchronization)

    管理工作的顺序和执行它的任务是大多数并行程序设计的关键,它也可能是提升程序性能的关键,通常也需要对某些程序进行“串行化”。

    这里写图片描述

    同步的类型:

    • 屏障: 1)这通常意味着会涉及到所有任务;2)每个任务都执行自身的工作,直到它遇到屏障,然后它们就停止,或者“阻塞”;3)当最后一个任务到达屏障时,所有任务得以同步;4)接下来可能发生的事情就有所变化了。通常会执行一段串行代码,或者所有的任务在这里都结束了。

    • 锁/信号量: 1)可以涉及任意多个任务;2)通常用于对全局数据或者某段代码的存取串行化(保护),在任一时刻,只有一个任务可以使用锁/信号量;3)第一个任务会获得一个锁,然后该任务就可以安全地对该保护数据进行存取;4)其它任务可以尝试去获得锁,但必须等到当前拥有该锁的任务释放锁才行;5)可以是阻塞的也可以是非阻塞的。

    • 同步通讯操作: 1)仅仅涉及到执行数据通讯操作的任务;2)当一个任务执行数据通讯操作时,通常需要在参与通讯的任务之间建立某种协调机制。例如,在一个任务发送消息时,它必须收到接受任务的确认,以明确当前是可以发送消息的;3)在消息通讯一节中也已经说明。

    6.6 数据依赖性 (Data Dependencies)

    定义:

    • 依赖: 当语句的执行顺序影响程序的运行结果时,我们称程序语句之间存在依赖关系。
    • 数据依赖: 数据依赖是由不同任务多次存取相同的内存位置而产生的。

    数据依赖也是并行程序设计中的关键,因为它是并行化中一个重要的抑制因素。

    这里写图片描述

    例子:

    • 循环相关的数据依赖:下面这段代码中,A(J-1) 必须在A(J) 之前被计算出来,因此说A(J)A(J-1) 之间存在数据依赖,所以并行化在这里被抑制。如果任务2中有A(J),任务1中有A(J-1),那么要计算出正确的A(J) 则需要:1)分布式内存架构:任务2必须在任务1计算结束之后,从任务1处中获取A(J-1) 的值。2)共享内存架构:任务2在任务1完成对A(J-1) 的更新之后,对A(J-1) 进行读取。
    DO J = MYSTART,MYEND
       A(J) = A(J-1) * 2.0
    END DO
    • 循环无关的数据依赖:在下面的例子中并行化也同样被抑制。Y的值依赖于:1)分布式内存架构: 在任务之间是否需要或者何时需要对X的值的通讯。2)共享内存架构: 哪个任务最后存储X的值。
    task 1        task 2
    ------        ------
    
    X = 2         X = 4
      .             .
      .             .
    Y = X**2      Y = X**3

    尽管在并行程序设计中,对所有数据依赖的识别都是重要的,但循环相关的数据依赖尤其重要,因为循环往往是最常见的可并行化部分。

    处理方法: 1)分布式内存架构:在同步点传输所需数据;2)共享式内存结构:在任务之间同步读写操作。

    6.7 负载均衡 (Load Balancing)

    负载均衡是指在任务之间分配大约相等数量的工作的做法,以便所有任务在所有时间保持繁忙,它也可以被认为是使任务空闲时间最小化。出于性能原因方面的考虑,负载均衡对并行程序很重要。例如如果所有恩物都收到屏障同步点的影响,那么最慢的任务将决定整体性能。

    这里写图片描述

    这里写图片描述

    如何实现负载均衡:

    • 平均分配任务量:

    对于数组/矩阵而言,如果每个任务都执行相同或者类似的工作,那么在任务之间平均分配数据集;2)对于循环迭代而言,如果每个迭代完成的工作量大小类似,则在每个任务中分配相同或者类似的迭代次数;3)如果你的架构是由具有不同性能特征的机器异构组合而成,那么请确保使用某种性能分析工具来简则任何的负载不平衡,并相应调整工作。

    • 采用动态任务分配方法:

    即使数据在任务之间被平均分配,但是某些特定类型的问题也会导致负载不平衡,如下面三个例子所示。


    稀疏矩阵:某些任务会具有真实数据,而大多数任务对应的数据却为0。

    这里写图片描述
    自适应网格:某些方格需要被细分,而其它的不需要。

    这里写图片描述
    N体模拟:粒子可能会跨任务域迁移,因此某些任务会需要承担更多的工作。

    当每个任务的工作量是可变的,或者无法预测的,那么可以采用 调度任务池 (Scheduler-task pool) 方法。每当某个任务完成了它的工作,它就可以从工作队列中领取新的任务。

    这里写图片描述

    最终来看,可能需要设计一种在代码中动态发生和处理负载不平衡的算法。

    6.8 粒度 (Granularity)

    计算通讯比 (computation / Communication Ratio): 在并行计算中,粒度是对计算与通讯的比例的定性度量。计算周期通常通过同步时间与通讯周期分离。

    细粒度并行化 (Fine-grain Parallelism): 1)在通讯事件之外进行相对较少的计算工作;2)计算通讯率较低;3)方便负载均衡;4)意味着较高的通讯开销以及较少的性能提升机会;5)如果粒度过细,任务之间的通讯和同步的开销可能需要比计算更长的时间。

    这里写图片描述

    粗粒度并行化 (Coarse-grain Parallelism): 1)在通讯/同步事件之外需要较大量的计算工作;2)较高的计算/通讯比;3)意味着较大的性能提升机会;4)难以进行较好的负载均衡。

    这里写图片描述

    最佳选择: 最有效的粒度取决于具体算法及其所运行的硬件环境。在大多数情况下,与通讯/同步相关的开销相对于执行速度很高,因此具有粗粒度的问题是相对有利的。而从另外一方面来讲,细粒度则可以帮助减少由负载不均衡所造成的开销。

    6.9 输入输出 (I/O)

    坏消息: 1)I/O操作通常被认为是并行化的抑制剂;2)I/O操作通常比内存操作需要多个数量级的时间;3)并行I/O系统可能不成熟或者不适用于所有平台;4)在所有任务均可以看到相同文件空间的环境中,写操作可能导致文件被覆盖;5)读操作可能受到文件服务器同时处理多个读取请求的能力影响;6)必须通过网络进行的I/O操作(NFS,非本地)可能导致严重的性能瓶颈,甚至导致文件服务器崩溃。

    这里写图片描述

    好消息: 已经具有不少并行文件系统,例如:

    • GPFS:通用并行文件系统 (General Parallel File System)(IBM),现在也被称为IBM Spectrum Scale。
    • Lustre:针对Linux的集群(Intel)。
    • HDFS:Hadoop分布式文件系统(Apache)。
    • PanFS:Panasas ActiveScale File System for Linux clusters (Panasas, Inc.)
    • 更多并行文件系统可以参加这里

    作为MPI-2的一部分,1996年以来MPI的并行I/O编程借口规范已经可用。

    注意事项: 1)尽可能减少整体I/O操作;2)如果你有权访问并行文件系统,请使用它;3)在大块数据上执行少量写操作往往比在小块数据上进行大量写操作有着更明显的效率提升;4)较少的文件比许多小文件更好;5)将I/O操作限制在作业的特定串行部分,然后使用并行通讯将数据分发到并行任务中。例如任务1可以读输入文件,然后将所需数据传送到其它任务。同样,任务2可以再从所有其它任务收到所需数据之后执行写入操作;6)跨任务的I/O整合——相比于很多任务都执行I/O操作,更好地策略是只让一部分任务执行I/O操作。

    6.10 调试 (Debugging)

    调试并行代码可能非常困难,特别是随着代码量的扩展。而好消息是有一些优秀的调试器可以提供帮助:1)Threaded - Pthreads和OpenMP;2)MPI;3)GPU/accelerator;4)Hybrid。

    在LC集群上也安装有一些并行调试工具:1)TotalView (RogueWave Software);2)DDT (Allinea);3)Inspector(Intel);4)Stack Trace Analysis Tool(STAT)(本地开发)。

    更多的信息可以参考:LC web pagesTotalView tutorial

    这里写图片描述

    6.11 性能分析和调优 (Performance Analysis and Tuning)

    对于调试而言,并行程序的性能分析和调优比串行程序更具挑战性。幸运的是,并行程序性能分析和调优有很多优秀的工具。Livemore计算机用户可以访问这种类似工具,其中大部分都在集群系统上。一些安装在LC系统上的工具包括:

    这里写图片描述

    7 并行示例

    7.1 数组处理

    此示例演示了对二维数组元素的操作:将某个函数作用于二维数组中的每个元素,其中对每个数组元素的操作都是独立于其它数组元素的,并且该问题是计算密集型的。对于串行程序而言,我们依次对每个元素进行操作,其代码类似于:

    do j = 1,n
      do i = 1,n
        a(i,j) = fcn(i,j)
      end do
    end do

    这里写图片描述

    问题:

    • 该问题是否可以被并行化?
    • 如果对该问题进行分割?
    • 需要数据通讯吗?
    • 有没有数据依赖?
    • 有没有同步需求?
    • 是否需要考虑负载均衡?

    并行方案1:

    • 由于对元素的计算彼此之间是独立的,所以可以有“尴尬并行”的解决方案。
    • 由于数组元素是均匀分布的,所以每个进程可以拥有阵列的一部分(子阵列)。1)可以选择最佳分配方案以实现高效的内存访问,例如选择步幅为1,或者选择合适的步幅以最大化缓存/内存使用。2)由于可以使单元跨越子阵列,所以分配方案的选择也取决于编程语言,有关选项可以参见第 6.3 节。
    • 由于数组元素的计算是彼此独立的,所以不需要任务之间的通讯和同步。
    • 由于任务之间的工作量是被平均分配的,所以不需要考虑负载均衡。
    • 对数组分割之后,每个任务执行与其拥有的数据相对应的循环部分,其源代码类似于:
    • 请注意只有外部循环变量与串行解决方案不同。
    for i (i = mystart; i < myend; i++) {
      for j (j = 0; j < n; j++) {
        a(i,j) = fcn(i,j);
      }
    }

    这里写图片描述

    一种可能的解决方案: 1)采用单程序多数据 (SPMD) 模型进行实现,每个任务执行相同的程序;2)主进程对数组进行初始化,将信息发送给子任务,并且接收计算结果;3)子进程接收到信息之后,执行计算任务,并且将结果发送给主进程;4)采用Fortran的存储结构,对数组进行块划分;5)伪代码如下所示。6)具体的C代码可以参见MPI Program in C

    find out if I am MASTER or WORKER
    
    if I am MASTER
    
      initialize the array
      send each WORKER info on part of array it owns
      send each WORKER its portion of initial array
    
      receive from each WORKER results 
    
    else if I am WORKER
      receive from MASTER info on part of array I own
      receive from MASTER my portion of initial array
    
      # calculate my portion of array
      do j = my first column,my last column 
        do i = 1,n
          a(i,j) = fcn(i,j)
        end do
      end do
    
      send MASTER results 
    
    endif

    并行方案2:

    上一个并行方案展示了静态负载均衡:1)每个任务执行固定量的工作;2)某些很快或者负载较轻的处理器将会拥有空闲时间,而最慢执行的任务最终决定整体性能。

    如果所有任务在同一台机器上运行相同量的工作,那么静态负载均衡往往并不是一个主要问题。但是如果你确实有负载均衡方面的问题(某些任务比其它任务运行的快),那么你可以采用“任务池”(pool of tasks)模式。

    任务池模式: 里面包含两个进程:

    • 主进程: 1)拥有任务池;2)如果得到请求,给工作进程发送工作任务;3)从工作进程出收集返回结果。
    • 工作进程: 1)从主进程处获取任务;2)执行计算任务;3)向主进程发送结果。

    工作进程在运行之前不知道它将处理数组的哪一部分,以及它将执行多少任务。动态负载均衡发生在运行时:运行最快的任务将完成更多的任务。一段可能的源代码如下:

    find out if I am MASTER or WORKER
    
    if I am MASTER
    
      do until no more jobs
        if request send to WORKER next job
        else receive results from WORKER
      end do
    
    else if I am WORKER
    
      do until no more jobs
        request job from MASTER
        receive from MASTER next job
    
        calculate array element: a(i,j) = fcn(i,j)
    
        send results to MASTER
      end do
    
    endif

    讨论: 1)在上述任务池例子中,每个任务计算数组的某一个元素,计算与通讯比率是细粒度的;2)细粒度的解决方案为了减少任务空闲时间,往往会导致更多的通讯开销;3)更好地解决方案可能是在每个任务中分配更多的工作,“正确”的工作量依然是依赖于具体问题的。

    7.2 圆周率计算

    计算圆周率的方法有多种。我们这里采用蒙特卡洛方法来近似计算圆周率:1)在一个边长为 2r 的正方形中画一个半径为 r 的内接圆;2)内接圆的面积是 πr2,正方形的面积是 4r2 ;3)圆的面积与正方形的面积之比是 πr2/4r2=π/4 ;4)如果你在正方形内随机地产生 N 个点,那么大约会有 Nπ/4 个点( M )会位于内接圆内;5)所以 π 可以被近似为: Nπ/4=M π/4=M/N π=4M/N ;6)注意越多的点产生,则对 π 的近似就越准确。

    这里写图片描述

    该问题的串行代码大约是这样的:

    npoints = 10000
    circle_count = 0
    
    do j = 1,npoints
      generate 2 random numbers between 0 and 1
      xcoordinate = random1
      ycoordinate = random2
      if (xcoordinate, ycoordinate) inside circle
      then circle_count = circle_count + 1
    end do
    
    PI = 4.0*circle_count/npoints

    该问题是计算密集型的——大多数时间将花费在对循环的执行。

    问题:

    • 该问题是否可以被并行化?
    • 如何对该问题进行分割?
    • 任务之间是否需要通讯?
    • 是否存在数据依赖?
    • 任务之间是否有同步需求?
    • 需要考虑负载均衡吗?

    解决方案:

    又一个容易被并行化的问题:1)每个点的计算都是独立的,不存在数据依赖;2)工作可以被平均分配,不需要考虑负载均衡;3)任务之间不需要通讯和同步。

    并行化策略:1)将任务平均划分为相同大小的多个部分,用于在任务池中被执行;2)每个任务独立地完成任务;3)采用单程序多数据(SPMD)模型;4)其中一个任务作为主进程来收集计算结果,并且计算 π 的值。

    这里写图片描述

    下面是并行化之后的伪代码:

    npoints = 10000
    circle_count = 0
    
    p = number of tasks
    num = npoints/p
    
    find out if I am MASTER or WORKER 
    
    do j = 1,num 
      generate 2 random numbers between 0 and 1
      xcoordinate = random1
      ycoordinate = random2
      if (xcoordinate, ycoordinate) inside circle
      then circle_count = circle_count + 1
    end do
    
    if I am MASTER
    
      receive from WORKERS their circle_counts
      compute PI (use MASTER and WORKER calculations)
    
    else if I am WORKER
    
      send to MASTER circle_count
    
    endif

    C语言的示例程序可以参考这里:MPI Program in C

    7.3 简单热方程

    大多数并行计算问题需要任务之间的通讯,其中一大部分问题需要“相邻”任务之间的通讯。

    这里写图片描述

    二维热方程问题描述了在给定初始温度分布以及边界条件的情况下,温度随着时间的变化。有限差分方案可以采用数值方法求解正方形区域内的热扩散方程:

    • 二维数组的元素用来表示正方形区域内的点的温度;
    • 边界处的初始问题是0,中心点的问题最高;
    • 边界处的问题会保持为0;
    • 采用时间步长算法。

    每个元素的文图的计算取决于它的邻居的温度:

    Ux,y=Ux,y+Cx(Ux+1,y+Ux1,y2Ux,y)+Cy(Ux,y1+Ux,y12Ux,y) .

    这里写图片描述

    串行程序的代码可能使这个样子:

    do iy = 2, ny - 1
      do ix = 2, nx - 1
        u2(ix, iy) =  u1(ix, iy)  +
            cx * (u1(ix+1,iy) + u1(ix-1,iy) - 2.*u1(ix,iy)) +
            cy * (u1(ix,iy+1) + u1(ix,iy-1) - 2.*u1(ix,iy))
      end do
    end do

    问题:

    • 该问题是否可以被并行化?
    • 如何对该问题进行分割?
    • 任务之间是否需要通讯?
    • 是否存在数据依赖?
    • 任务之间是否需要同步?
    • 是否需要考虑负载均衡?

    解决方案:

    该问题更具有挑战性。因为存在数据依赖,所以需要任务之间的通讯和同步。整个数组需要被风格成为子数组,并分配给不同任务,每个任务拥有整个数组的一部分。由于任务量是均匀划分的,所以不需要考虑负载均衡。

    这里写图片描述

    确定数据依赖:1)一个任务的 内部元素 和其它任务之间不存在数据依赖;2)一个任务的 边界元素 则和它的邻居任务之间需要产生数据通讯。

    采用单程序多数据模型(SPMD)进行实现:1)主进程向工作进程发送初始信息,然后等待并收集来自工作进程的计算结果;2)工作进程在特定的时间步长内计算结果,并与邻居进程之间进行数据交换。伪代码如下:

    find out if I am MASTER or WORKER
    
    if I am MASTER
      initialize array
      send each WORKER starting info and subarray
      receive results from each WORKER
    
    else if I am WORKER
      receive from MASTER starting info and subarray
    
      # Perform time steps
      do t = 1, nsteps
        update time 
        send neighbors my border info
        receive from neighbors their border info 
        update my portion of solution array
    
      end do
    
      send MASTER results
    
    endif

    示例程序可以参加:MPI Program in C

    7.4 一维波动方程

    在这个例子中,我们计算经过指定时间量之后,一维波动曲线的振幅。其中的计算会涉及到:1)y轴上的振幅;2)x轴上的位置索引i;3)沿着波动曲线的节点;4)以离散时间步长更新振幅。

    这里写图片描述

    这里需要求解的是如下一维波动方程,其中c是常数。

    A(i,t+1) = (2.0 * A(i,t)) - A(i,t-1) + (c * (A(i-1,t) - (2.0 * A(i,t)) + A(i+1,t)))

    我们注意到,t时刻的振幅取决于前一刻的时间步长(t, t-1)以及相邻点(i - 1, i + 1)。

    问题:

    • 该问题是否可以被并行化?
    • 如何对该问题进行分割?
    • 任务之间是否需要通讯?
    • 人物之间是否存在数据依赖?
    • 任务之间是否需要同步?
    • 是否需要考虑负载均衡?

    解决方案:

    这是涉及到数据依赖的另外一个例子,其并行方案将会涉及到任务见的通讯和同步。整个振幅阵列被分割并分配给所有的子任务,每个任务拥有总陈列的相等的部分。由于所有点需要相等的工作,所以我们应该均匀地分配节点。我们可以将工作分成多个块,并且允许每个任务拥有大多数连续的数据点。而通讯只需要在数据边界上进行,块大小越大,则所需的通信越少。

    这里写图片描述

    采用单程序多数据(SPMD)模型的实现:1)主进程向工作进程发送初始信息,并且等到各个工作进程返回计算结果;2)工作进程对特定步长之内的任务进行计算,并且在必要的时候和邻居进程进行数据通讯。其伪代码如下:

    find out number of tasks and task identities
    
    #Identify left and right neighbors
    left_neighbor = mytaskid - 1
    right_neighbor = mytaskid +1
    if mytaskid = first then left_neigbor = last
    if mytaskid = last then right_neighbor = first
    
    find out if I am MASTER or WORKER
    if I am MASTER
      initialize array
      send each WORKER starting info and subarray
    else if I am WORKER`
      receive starting info and subarray from MASTER
    endif
    
    #Perform time steps 
    #In this example the master participates in calculations
    do t = 1, nsteps 
      send left endpoint to left neighbor
      receive left endpoint from right neighbor
      send right endpoint to right neighbor
      receive right endpoint from left neighbor
    
      #Update points along line
      do i = 1, npoints
        newval(i) = (2.0 * values(i)) - oldval(i) 
        + (sqtau * (values(i-1) - (2.0 * values(i)) + values(i+1))) 
      end do
    
    end do
    
    #Collect results and write to file
    if I am MASTER
      receive results from each WORKER
      write results to file
    else if I am WORKER
      send results to MASTER
    endif 

    程序示例可以参见:MPI Program in C

    8 参考文献和更多信息

    • 作者:Blaise Barney,Livermore Computing.
    • 在万维网上搜索“parallel programming”或者“parallel computing”将会获得大量信息。
    • 推荐阅读:
    • 图片/图像由作者以及其它LLNL成员创建,或者从不涉及版权的政府或公领域()获取,或者经所有者同意从其演示文稿或者网页上获取。
    • 历史:该材料有下面的资源演化而来,而这些资源将不再被维护或者不再可用。
      • Tutorials located in the Maui High Performance Computing Center’s “SP Parallel Programming Workshop”.
      • Tutorials located at the Cornell Theory Center’s “Education and Training” web page.
    展开全文
  • 2006并行程序设计期末考试卷
  • 本书系统介绍并行程序设计原理及应用。除介绍常用的一些算法范例,包括分治、流水、同步计算、主从及工作池,还介绍了一些常用的经典数值和非数值算法,如排序、矩阵相乘、线性方程组求解、图像处理中的预处理和相应...
  • 并行计算复习第二篇 并行计算理论基础:并行算法设计Ch5 并行算法与并行计算模型5.1 并行算法的基础知识1.并行算法的表达(1)par-don个节点并行完成for循环(每个节点不同,和i相关):for i = 1 to n par-do ... ...

    并行计算复习

    第二篇 并行计算理论基础:并行算法设计


    Ch5 并行算法与并行计算模型

    5.1 并行算法的基础知识

    1.并行算法的表达

    (1)par-do

    n个节点并行完成for循环(每个节点不同,和i相关):

    for i = 1 to n par-do
        ...
    endfor

    (2)for all

    所有节点都执行相同语句:

    for all Pi, where 0 <= i <= k do
        ...
    endfor
    2.并行算法的复杂度
    • 运行时间t(n):求解问题的时间,包括计算时间和通信时间
    • 处理器数目p(n):求解给定问题所用的处理器数目
    • 成本c(n):c(n) = t(n)*p(n)
    • 成本最优——并行算法的成本在数量级上等于最坏情况下串行求解次问题所需要的执行步数
    • 工作量W(n):并行算法完成的总的操作数量
    • 工作量最优:功耗低、环保

    并行算法的WT表示——Brent定理:

    令W(n)是并行算法A在运行时间T(n)内所执行的运算量,则A使用p台处理器可在t(n) = O(W(n)/p + T(n))时间内执行完毕
    

    5.2 并行计算模型

    1.PRAM模型(SIMD-SM)

    PRAM(Parallel Random Access Machine)并行随机存取机器,是一种抽象并行计算模型,它假设:

    • 存在容量无限大的SM
    • 有限或无限个功能相同的处理器,且均有简单算术运算和逻辑判断功能
    • 任何时刻各处理器可通过SM交换数据

    根据并发访问机制,又分为:

    • 不允许同时读和同时写的PRAM-EREW
    • 允许同时读但不允许同时写的PRAM-CREW
    • 允许同时读和同时写的PRAM-CRCW

    PRAM-CRCW又分为:

    • 只允许同时写相同的数CPRAM-CRCW
    • 只允许优先处理器先写PPRAM-CRCW
    • 允许任意处理器自由写APRAM-CRCW

    PRAM优点:

    • 适合并行算法表达、分析和比较
    • 使用简单,屏蔽了通信、存储管理、进程同步等并行细节
    • 易于修改算法设计以适应不同并行机

    PRAM缺点:

    • PRAM是同步模型,同步锁费时
    • 不适用于MIMD和DM
    • 假设任何处理器可在单位时间内访问任何处理单元而不考虑竞争和带宽,不现实
    2.异步APRAM模型(MIMD-SM)

    异步APRAM模型假设:

    • 每个处理器有LM、局部时钟、局部程序
    • 处理器通信经过SM
    • 无全局时钟,各处理器异步执行各自指令
    • 处理器之间的指令相互依赖关系必须显式加入同步障
    • 一条指令可以在非确定但有界时间内完成

    指令类型有:

    • 全局读:从SM读到LM
    • 局部操作:LM操作存入LM
    • 全局写:LM写入SM
    • 同步:各处理器需等到其他处理器到达后才能继续执行

    APRAM比PRAM更加接近实际并行机

    3.BSP模型(MIMD-DM)

    BSP(Bulk Synchronous Parallel)大同步并行机(APRAM算作轻量)是一个分布式存储的MIMD模型,它的计算由若干全局同步分开的、周期为L的超级步组成,各超级步中处理器做LM操作并通过选路器接收和发送消息;然后做一次全局检查,以确定该超级步是否已经完成(块内异步并行,块间显式同步)

    参数:处理器数p、选路器吞吐率g、全局同步间隔L、一个超级步中一个处理器至多发送或接收h条消息

    4.LogP模型:MIMD-DM,点到点通讯

    LogP模型是分布式存储、点到点通信的MIMD模型

    LogP采取隐式同步,而不显式同步障


    Ch6 并行算法基本设计策略

    6.1 串改并

    发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法

    最常用的设计思路但并不普适,好的串行算法一般无法并行化(数值串行算法可以)

    快速排序的串改并

    SISD上串行执行,最坏情况下O(n^2),理想情况下O(nlogn)

    思路:将O(n)的划分(Partition)并行化是关键,算法:

    • 构造一棵二叉排序树,主元是根
    • 小于等于主元素处于左子树,大于主元素处于右子树
    • 左右子树均是二叉排序树

    在CRCW模型上,用伪代码描述如下:

    //A[1...n]排序用n个处理器,处理器i中存有A[i]
    //f[i]中存有其元素是主元素的处理器号
    //LC[1...n]和RC[1...n]分别记录给定主元素的左儿子和右儿子
    
    for each processor i par-do
        root = i    //所有处理器竞争,只有一个写入root
        f[i] = root //所有处理器都把root写入自己的f[i]
        LC[i] = RC[i] = n + 1   //初始值
    endfor
    
    repeat for each processor i != root do
        if (A[i] < A[f[i]]) || (A[i] == A[f[i]] && i < f[i])
            LC[f[i]] = i    //并发写,所有满足条件的i只有一个写入LC[f[i]]作为左子树的根,也就是下一次循环的主元素
            if i == LC[f[i]] then
                exit        //若当前处理器写入则什么也不做
            else
                f[i] = LC[f[i]] //若当前处理器没有写入,那么它只能当LC[f[i]]的字节点了
            endif
        else
            RC[f[i]] = i    //并发写,所有满足条件的i只有一个写入RC[f[i]]作为右子树的根,也就是下一次循环的主元素
            if i == RC[f[i]] then
                exit        //若当前处理器写入则什么也不做
            else
                f[i] = RC[f[i]] //若当前处理器没有写入,那么它只能当RC[f[i]]的字节点了
            endif
        endif
    endrepeat
    

    每次迭代构造一层排序二叉树花费O(1)时间,在基本平衡的情况下树高O(logn),则算法复杂度为O(logn)

    6.2 全新设计

    从问题本身描述出发,不考虑相应的串行算法,设计 一个全新的并行算法

    有向环K着色算法的并行化设计

    问题:有向环顶点着色,一共K种颜色,相邻顶点不允许同色

    串行算法(3着色):交替2种颜色,若顶点是奇数则需要用到第3种颜色(难以并行化)

    SIMD-EREW上的并行K着色算法:

    //初始随机着色为c[i],每个顶点着色不同
    //输出着色方案为nc[i]
    for i = 1 to n par-do
        k = c[i]和c[i的后继]的最低的不同二进制位
        nc[i] = 2 * k + c[i]的二进制第k位
    endfor

    O(1)时间完成,需要算法正确性证明

    6.2 借用法

    找出求解问题和某个已解决问题之间的联系,改造或利用已知算法应用到求解问题上

    利用矩阵乘法求所有点对间最短路径

    d[k][i][j]表示从vi到vj**至多**经过k-1个中间顶点时的最短路径,d[k][i][j] = min{d[k/2][i][l]+d[k/2][l][j]}

    那么可以用矩阵乘法的改进(乘变加,求和变min)做logn次矩阵乘法即可

    思路是这样,具体伪代码略,需要O(n^3)个节点,时间复杂度为O(log^2(n))


    Ch7 并行算法常用设计技术

    6.1 划分设计技术

    使用划分法把问题求解分成两步:

    1. 把给定问题划分成p个几乎等尺寸的子问题
    2. 用p台处理器并行求解子问题
    (1)均匀划分(PSRS排序)

    长度为n的待处理序列均匀划分给p个处理器,每个处理器处理n/p个元素

    MIMD机器上的PSRS排序算法:

    (1)均匀划分:将n个元素A[1..n]均匀划分成p段,分配给p个处理器
    (2)局部排序:pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序
    (3)选取样本:pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素
    (4)样本排序:用一台处理器对p2个样本元素进行串行排序
    (5)选择主元:用一台处理器从排好序的样本序列中选取p-1个主元,并播送给其他pi 
    (6)主元划分:pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段
    (7)全局交换:各处理器将其有序段按段号交换到对应的处理器中(一定保证均匀划分??)
    (8)归并排序:各处理器对接收到的元素进行归并排序
    (2)方根划分(Valiant归并排序)

    长度为n的待处理序列,取i*sqrt(n)为划分元,将元素划分成若干段交给处理器处理

    SIMD-CREW机器上的Valiant归并排序:

    (1)方根划分:把A和B(长n有序段)的第i*sqrt(n)元素作为划分元,把A和B分成若干段
    (2)段间比较:A中的所有划分元和B中的所有划分元比较,确定A中划分元应插入B中的哪一段
    (3)段内比较:A中的划分元和B中相应段比较并确定插入位置,这些插入位置又将B重新划分成了若干段
    (4)段组合并:插入A划分元后,又得到若干有序段组需要归并,递归直到有一组(A)的长度为0
    

    使用n个处理器可以在O(loglogn)内完成

    (3)对数划分(并行归并排序)

    取i*logn作为划分元划分

    定义位序rank(x,X)为X中小于等于x的元素个数,则有PRAM-CREW上的对数划分:

    //非降有序的A={a[1],...,a[n]}和B={b[1],...,b[m]}归并
    //假设log(m)和k=m/log(m)均为整数
    j[0]=0
    j[k]=n
    
    for i = 1 to k - 1 par-do
        j[i] = rank(b[ilogm], A)
    endfor
    
    for i = 1 to k - 1 par-do
        Bi = {b[ilogm+1], ..., b[(i+1)logm]}
        Ai = {a[j[i]+1], ..., a[j[i+1]]}
    endfor
    
    //将原问题转化为子序列组Bi和Ai的归并,那么同样可以递归调用完成整个序列的归并
    //对数划分保证Bi和Ai中的元素均大于Bi-1和Ai-1中的元素
    
    (4)功能划分( (m,n)-选择)

    功能划分是根据特定问题而把序列分成p个等长组,每组符合问题特性的一种划分方法

    (m,n)-选择问题是将长为n的序列中选取前m个较小的元素,利用功能划分来实现并行化的(m,n)-选择问题求解:

    (1)功能划分:将A划分成g=n/m组,每组含m个元素
    (2)局部排序:使用Batcher排序网络将各组并行排序
    (3)两两比较:将所排序的各组两两比较,从而形成MIN序列
    (4)排序-比较:对各个MIN序列,重复执行第(2)和第(3)步,直至选出m个最小者

    6.2 分治设计技术

    分治将复杂问题划分成较小规模特性相同的子问题,且子问题类型和原问题类型相同,通常用递归完成分治算法

    (1)双调归并网络

    双调序列:若序列x[0],…,x[n-1]是双调序列,则存在一个0<=k<=n-1使得x[0]>=…>=x[k]<=x[k+1]<=…<=x[n-1]或序列循环移动可以得到此关系

    Batcher定理:双调序列对0<=i<=n/2-1,比较所有x[i]和x[i+n/2]得到的小序列MIN和大序列MAX仍然是双调序列

    Batcher双调归并排序算法:

    //输入双调序列X得到非降有序序列Y
    procedure Bitonic-Merge(x) {
        for i = 0 to n/2 - 1 par-do
            s[i] = min(x[i], x[i+n/2])
            l[i] = max(x[i], x[i+n/2])
        endfor
    
        Bitonic-Merge(s)
        Bitonic-Merge(l)
    
        output s followed by l
    }

    6.3 平衡树设计技术

    以树的叶结点为输入,中间结点为处理结点,由叶向根或由根向叶逐层进行并行处理

    (1)求最大值

    SIMD-TC(SM)上O(logn)的树上求最大值算法:

    //带求最大值的n个元素放在A[n, ..., 2n-1]中,最大值放在A[1]中
    //n=2^m
    for k = m-1 to 0 do
        for j = 2^k to 2^(k+1)-1 par-do
            A[j]=max(A[2j],A[2j+1])
        endfor
    endfor

    SIMD-CRCW上常数时间求最大值算法:

    //输入A[1...p]共p个元素
    //B[1..p][1..p],M[1..p]为中间处理用的布尔数组, 如果M[i]=1, 则A[i]为最大值
    
    for i = 1 to p, j = 1 to p par-do   //W(n)=O(p^2)换取时间O(1)
        if A[i] >= A[j] then
            B[i,j] = 1
        else
            B[i,j] = 0
        endif
    endfor
    
    for i = 1 to p par-do
        M[i] = B[i,1]∧ B[i,2]∧... ∧B[i,p] 
        //向量操作保证O(1)完成,则该并行段也是O(1)
        //若M[i]=1,则是A[i]最大值
    endfor
    (2)计算前缀和

    定义二元结合运算*,则n个元素x[1,…,n]的前缀和是如下定义的n个部分和:

    s[i]=x[1]*x[2]*x[i],i=1,…,n

    串行计算n个元素前缀和需要O(n)的时间(利用s[i] = s[i-1] * x[i])

    下面给出SIMD-TC上的求前缀和O(logn)的算法:

    for j = 1 to n par-do
        B[0, j] = A[j]  //平衡树底层是n个元素    
    endfor                                  //O(1)
    
    for h = 1 to logn do                    //正向遍历,父节点存所有字节点之和
        for j = 1 to n/2^h par-do
            B[h,j]=B[h-1,2j-1]*B[h-1,2j]    //父节点存子节点之和
        endfor                              //O(1)
    endfor                                  //共logn层,则总时间O(logn)
    
    for h = logn to 0 do
        for j = 1 to n/2^h par-do
            if j % 2 == 0 then      //该节点是右儿子
                C[h,j]=C[h+1,j/2]   //右儿子等于父节点的值
            else if j == 1 then
                C[h,j]=B[h,1]       //每一层第一个节点等于B树上对应值
            else                    //该节点是左儿子
                C[h,j]=C[h+1,(j-1)/2]*B[h,j]    //叔节点和\*自身和
            endif
        endfor
    endfor

    6.4 倍增设计技术

    递归调用时,所要处理数据之间的距离逐步加倍, 经过k步后即可完成距离为2^k的所有数据的计算

    (1)表序问题

    n个元素的序列L,每个元素分配一个处理器,给定k求出L[k]的rank(k)值,rank(k)等于其到表尾的距离

    每个元素有一个指向下一个元素的指针next(k)

    下面给出SIMD-EREW上求元素表序的算法:

    for k in L par-do
        p(k) = next(k)
        if p(k) != k then
            distance(k)=1
        else
            distance(k)=0
        endif
    endfor                  //O(1)完成distance初始化
    
    repeat t = ceil(logn) times
        for k in L par-do
            if p(k)!=p(p(k)) then //不是到数第2个
                distance(k) += distance(p(k))   //把next的dis加到自己上来
                p(k)=p(p(k))    //next倍增
            endif
        endfor
    
        for k in L par-do
            rank(k)=distance(k)     //为什么每次都去赋值rank不最后赋值一次?
        endfor
    
    endrepeat               //O(logn)
    
    (2)求森林的根

    森林是一组有根有向树,找森林的根就是求出所有节点所在的树的根节点

    可以用倍增技术去修改每个节点的后继(后继即是父节点),下面是SIMD-CREW上的求森林根算法:

    for i = 1 to n par-do
        s[i] = p[i]
        while s[i] != s[s[i]] do    //该节点不是根
            s[i] = s[s[i]]          //指向父节点
        endwhile                    //这个while不需要同步吗?
    endfor                          //O(logn)

    6.5 流水线技术

    将算法路程分成p个前后衔接的任务片段,一个任务片段完成之后其后继任务片段可以立即开始,那么久可以引入流水线的思想来处理多条数据

    (1)五点的DFT计算

    计算DFT时引入Horner法则把任务划分成流水段:
    这里写图片描述

    O(n)的时间即可完成DFT计算

    (2)4流水线编程实例

    老师举出一个可流水化的矩阵赋值的例子,意义不是很大,略

    展开全文
  • 并行算法的设计与分析+第3版+陈国良编著+2009+源代码
  • 由PDG文档转换而成,清晰...本书以并行计算为主题,讨论并行计算的硬件基础,即当代并行计算机系统及其结构模型,并行计算的核心内容并行算法设计与并行数值算法,以及并行计算的软件支持并行程序和设计原理与方法等。
  • 武汉理工大学-并行计算-2020年期末复习指南

    千次阅读 多人点赞 2020-10-31 15:33:53
    武汉理工大学-并行计算-2020年期末复习指南

    并行计算-2020-复习指南

    制作:纪元

    本提纲遵循CC-BY-NC-SA协议

    (署名-非商业性-相同方式共享)

    文章目录

    符号释义

    • ⌊ ⌋ \lfloor \rfloor 向下取整数
    • ⌈ ⌉ \lceil \rceil 向上取整数

    题型设置

    • 选择 20x2
    • 填空 10x2
    • 简答 2x10
    • 编程 2*10

    并行计算机系统及其结构模型

    存储墙

    内存墙,指的是内存性能严重限制CPU性能发挥的现象。

    在过去的20多年中,处理器的性能以每年大约55%速度快速提升,而内存性能的提升速度则只有每年10%左右。长期累积下来,不均衡的发展速度造成了当前内存的存取速度严重滞后于处理器的计算速度,内存瓶颈导致高性能处理器难以发挥出应有的功效,这对日益增长的高性能计算(High Performance Computing,HPC)形成了极大的制约。事实上,早在1994年就有科学家分析和预测了这一问题,并将这种严重阻碍处理器性能发挥的内存瓶颈命名为"内存墙"(Memorya Wall)。

    在这里插入图片描述

    互联网络

    网络性能指标

    • 节点度(Node Degree):射入或射出一个节点的边数。在单向网络中,入射和出射边之和称为节点度。
    • 网络直径(Network Diameter): 网络中任何两个节点之间的最长距离,即最大路径数。
    • 对剖宽度(Bisection Width) :对分网络各半所必须移去的最少边数
    • 对剖带宽( Bisection Bandwidth):每秒钟内,在最小的对剖平面上通过所有连线的最大信息位(或字节)数
    • 对称(Symmetry):从任一节点观看网络都一样

    静态互连网络

    • 静态互连网络:处理单元间有着固定连接的一类网络,在程序执行期间,这种点到点的链接保持不变;典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等。
    • 嵌入(Embedding):指将网络中的各节点映射到另一个网络中去。
    • 膨胀(Dilation):系数来描述嵌入的质量,它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数。如果该系数为1,则称为完美嵌入。
      • 例如,一个环网可完美嵌入到2-D 环绕网中。同样,一个超立方网也可以完美嵌入到2-D环绕网中。并非所有网络之间均可实现完美嵌入。
      • 一般而言,对于高度为 h 的完全二叉树,其膨胀系数为 ⌈ h / 2 ⌉ \lceil{h/2}\rceil h/2
    网络名称网络规模节点度网络直径对剖宽度对称链路数
    线性阵列 N N N 2 2 2 N − 1 N-1 N1 1 1 1 N − 1 N-1 N1
    环形 N N N 2 2 2 N − 1 ( 单 向 ) ⌊ N / 2 ⌋ ( 双 向 ) N-1(单向)\\\lfloor{N}/2\rfloor(双向) N1()N/2() 2 2 2 N N N
    2-D网孔 ( N × N ) (\sqrt{N}\times\sqrt{N}) (N ×N ) 4 4 4 2 ( N − 1 ) 2(\sqrt{N}-1) 2(N 1) N \sqrt{N} N 2 ( N − N ) 2(N-\sqrt{N}) 2(NN )
    Illiac网孔 ( N × N ) (\sqrt{N}\times\sqrt{N}) (N ×N ) 4 4 4 N − 1 \sqrt{N}-1 N 1 2 N 2\sqrt{N} 2N 2 N 2N 2N
    2-D环绕 ( N × N ) (\sqrt{N}\times\sqrt{N}) (N ×N ) 4 4 4 2 ( ⌊ N / 2 ⌋ ) 2(\lfloor\sqrt{N}/2\rfloor) 2(N /2) 2 N 2\sqrt{N} 2N 2 N 2N 2N
    二叉树 N N N 3 3 3 2 ⌈ log ⁡ N ⌉ − 1 2\lceil\log{N}\rceil-1 2logN1 1 1 1 N − 1 N-1 N1
    星形 N N N N − 1 N-1 N1 2 2 2 ⌊ N / 2 ⌋ \lfloor{N/2}\rfloor N/2 N − 1 N-1 N1
    超立方 N = 2 n N=2^n N=2n n n n n n n N / 2 N/2 N/2 n N / 2 nN/2 nN/2
    立方环 N = k × 2 k N=k\times2^k N=k×2k 3 3 3 2 k − 1 + ⌊ k / 2 ⌋ 2k-1+\lfloor{k/2}\rfloor 2k1+k/2 N / ( 2 k ) N/{(2k)} N/(2k) 3 N / 2 3N/2 3N/2

    在这里插入图片描述
    在这里插入图片描述

    完美嵌入(膨胀系数=1)

    在这里插入图片描述

    不完美嵌入(膨胀系数=2)

    在这里插入图片描述

    动态互连网络

    • 动态网络:用交换开关构成的,可按应用程序的要求动态地改变连接组态;典型的动态网络包括总线、交叉开关和多级互连网络等。

    • 总线(Bus)实际上是连接处理器、存储模块和I/O 外围设备等的一组导线和插座。总线系统用以主设备(如处理器)和从设备(如存储器)之间的数据传输。公用总线以分时工作为基础,在多个请求情况下,总线的仲裁是重要的。

    • 局部/本地总线(Local Bus):在印刷电路板上实现的总线

      • 本地总线:CPU板级上的总线(习惯叫法)

      • 存储器总线:存储器板级上的总线

      • 数据总线:I/O 板级和通信板级上的总线。

      • 系统总线:在底板上实现的,它为所有插入板之间的通信提供了通路。

    • 局部/本地总线+存储器总线,将处理器与存储模块相连;

    • I/O总线+系统总线,将I/O设备、网卡等连接起来。

      • I/O总线有时也叫作小型机系统接口SCSI(Small Computer System Interface)总线。
    • 绝大多数标准总线都可低价构造单一处理系统(Unity Processor System)。在构造多处理器系统时,常使用多总线层状总线

    板级、底板级和I/O级总线系统:

    在这里插入图片描述

    • 总线系统造价最低,但易冲突;
    • 交叉开关造价最高,但带宽和选路性能最好;
    • 多级互连网络是总线与交叉开关的折衷
      • 主要优点采用模块结构,可扩展性好
      • 但延迟随网络尺寸对数增长。

    在这里插入图片描述

    并行计算机结构

    定义

    大型并行机系统一般可分为6类机器,SIMD计算机多为专用,其余的5种均属于多指令多数据流MIMD计算机。

    • 单指令多数据流SIMD
    • 并行向量处理机PVP
      • 多为定制,通常不使用高速缓存,而是使用大量的向量寄存器和指令缓冲器
    • 对称多处理机SMP
      • 系统对称,每个处理器可等同的访问共享存储器、I/O设备和操作系统服务。能开拓较高的并行度
      • 是共享存储,限制系统中的处理器不能太多(一般少于64个),同时总线和交叉开关互连一旦作成也难于扩展。
    • 大规模并行处理机MPP
      • 处理节点采用商品微处理器;
      • 系统中有物理上的分布式存储器;
      • 采用高通信带宽和低延迟的互连网络(专门设计和定制的);
      • 能扩放至成百上千乃至上万个处理器;
      • 它是一种异步的MIMD机器,程序系由多个进程组成,每个都有其私有地址空间,进程间采用传递消息相互作用。
    • 工作站机群COW
      • COW的每个节点都是一个完整的工作站(不包括监视器、键盘、鼠标等),也可以是一台PC或SMP;
      • 各节点通过一种低成本的商品(标准)网络(如以太网、FDDI和ATM开关等)互连(有的商用机群也使用定做的网络);
      • 各节点内总是有本地磁盘,而MPP节点内却没有;
      • 节点内的网络接口是松散耦合到I/O 总线上的,而MPP内的网络接口是连到处理节点的存储总线上的,因而可谓是紧耦合式的;
      • 一个完整的操作系统驻留在每个节点中,而MPP中通常只是个微核,COW的操作系统是工作站UNIX,加上一个附加的软件层以支持单一系统映像、并行度、通信和负载平衡等
    • 分布共享存储DSM多处理机。
      • DSM在物理上有分布在各节点中的局部存储,从而形成了一个共享的存储器。对用户而言,系统硬件和软件提供了一个单地址的编程空间。DSM相对于MPP的优越性是编程较容易。
    属性PVPSMPMPPDSMcow
    结构类型MIMDMIMDMIMDMIMDMIMD
    处理器类型专用定制商用商用商用
    互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络(以太ATM)
    通信机制共享变量共享变量消息传递共享变量消息传递
    地址空间单地址空间单地址空间多地址空间单地址空间多地址空间
    系统存储器集中共享集中共享分布非共享分布共享分布非共享
    访存模型UMAUMANORMANUMANORMA

    图示

    • B(Bridge)是存储总线和I/O总线间的接口
    • DIR(CacheDirectory)是 高速缓存目录
    • IOB(I/O Bus)是I/O 总线
    • NIC(InterfaceCircuitry)是网络接口电路(网卡)
    • P/C(MicroprocessorandCache)是微处理器和高速缓存
    • VP(Vector Processor)向量处理器
    • SM(SharedMemory)是共享存储器。
    • LM(Local Memory)本地/局部存储
    • LD(LocalDisk)是 本 地 磁 盘
    • RC(RemoteCatch)远程高速缓存

    在这里插入图片描述

    并行计算机访存模型

    概念

    • UMA(Uniform MemoryAccess)模型是均匀存储访问模型的简称,适于通用或分时应用。

      • 对称多处理机SMP(SymmetricMultiprocessor):所有的处理器都能等同地访问所有I/O设备、能同样地运行执行程序(如操作系统内核和I/O服务程序等)时称为

      • 非对称多处理机:只有一台 或一组处理器(称为主处理器),它能执行操作系统并能操纵I/O,而其余的处理器无I/O 能力(称为从处理器),只在主处理器的监控之下执行用户代码。

      其特点是:

      • 物理存储器被所有处理器均匀共享;
      • 所有处理器访问任何存储单元取相同的时间(此即均匀存储访问名称的由来);
      • 每台处理器可带私有高速缓存;
      • 外围设备也可以一定形式共享。这种系统由于高度共享资源而称为紧耦合系统(TightlyCoupledSystem)。

    在这里插入图片描述

    • NUMA(Nonuniform MemoryAccess)模型是非均匀存储访问模型的简称。特点是:
      • 被共享的存储器在物理上是分布在所有的处理器中的,其所有本地存储器的集合就组成了全局地址空间;
      • 处理器访问存储器的时间是不一样的:访问本地存储器LM 或群内共享存储器CSM较快,而访问外地的存储器或全局共享存储器 GSM较慢(此即非均匀存储访问名称的由来);
      • 每台处理器照例可带私有高速缓存,且外设也可以某种形式共享。

    在这里插入图片描述

    • COMA(Cach-OnlyMemoryAccess)模型是全高速缓存存储访问的简称。是 NUMA 的一种特例。其特点是:
      • 各处理器节点中没有存储层次结构,全部高速缓存组成了全局地址空间;
      • 利用分布的高速缓存目录D进行远程高速缓存的访问;
      • COMA中的高速缓存容量一般都大于2级高速缓存容量;
      • 使用COMA时,数据开始时可任意分配,因为在运行时它最终会被迁移到要用到它的地方。

    在这里插入图片描述

    • CC-NUMA(Coherent-CacheNonuniform MemoryAccess)模型是高速缓存一致性非均匀存储访问模型的简称。它实际上是将一些SMP机器作为一个单节点而彼此连接起来所形成的一个较大的系统。其特点是:
      • 绝大多数商用 CC-NUMA多处理机系统都使用基于目录的高速缓存一致性协议;
      • 它在保留SMP结构易于编程的优点的同时,也改善了常规 SMP 的可扩 放性问题;
      • CC-NUMA 实际上是一个分布共享存 储的DSM多处理机系统;
      • 它最显着的优点是程序员无需明确地在节点上分配数据,系统的硬件和软件开始时自动在各节点分配数据,在运行期间,高速缓存一致性硬件会自动地将数据移至要用到它的地方。

    在这里插入图片描述

    • NORMA(No-RemoteMemoryAccess)模型是非远程存储访问模型的简称。在一个分布存储的多计算机系统中,如果所有的存储器都是私有的、仅能由其处理器所访问时就称为 NORMA。系统由多个计算节点通过消息传递互连网络连接而成,每个节点都是一台由处理器、本地存储器和/或I/O 外设组成的自治计算机。NORMA的特点是:

      • 所有存储器均是私有的;
      • 绝大多数 NUMA都不支持远程存储器的访问;
      • 在DSM中,NORMA 就消失了。

    小结

    物理上分布的存储器从编程的观点看可以是共享的或非共享的

    • 共享存储结构(多处理机)可同时支持共享存储和消息传递编程模型
    • 共享存储的编程模型可同时执行于共享存储结构和分布式存储结构(多计算机)上。

    在这里插入图片描述

    当代并行计算机系统介绍

    共享存储的对称多处理机SMP

    • SMP系统属于UMA(Uniform MemoryAccess)机器
    • NUMA(Nonuniform MemoryAccess)机器是SMP系统的自然推广
    • CC-NUMA (Coherent-CacheNUMA)实际上是将一些SMP作为单节点而彼此连接起来所构成的分布共享存储系统

    结构特性:

    • 对称性:系统中任何处理器均可访问任何存储单元和I/O设备;

    • 单地址空间: 单地址空间有很多好处,例如因为只有一个OS和DB等副本驻留在共享存储器中,所以OS可按工作负载情况在多个处理器上调度进程从而易达到动态负载平衡,又如因为所有数据均驻留在同一共享存储器中,所以用户不必担心数据的分配和再分配;

    • 高速缓存及其一致性:多级高速缓存可支持数据的局部性,而其一致性可由硬件来增强;

    • 低通信延迟:处理器间的通信可用简单的读/写指令来完成(而多计算机系统中处理器间的通信要用多条指令才能完成发送/接收操作)。目前大多数商用SMP系统都是基于总线连接的,占了并行计算机很大的市场

    问题:

    • 欠可靠:总线、存储器或OS失效均会造成系统崩溃,这是SMP系统的最大问题;
    • 可观的延迟:尽管SMP比MPP通信延迟要小,但相对处理器速度而言仍相当可观(竞争会加剧延迟),一般为数百个处理器周期,长者可达数千个指令周期;
    • 慢速增加的带宽:有人估计,主存和磁盘容量每3年增加4倍,而SMP存储器总线带宽每3年只增加2倍,I/O 总线带宽增加速率则更慢,这样存储器带宽的增长跟不上处理器速度或存储容量的步伐;
    • 不可扩放性:总线是不可扩放的,这就限制最大的处理器数一般不能超过10。为了增大系统的规模,可改用交叉开关连接,或改用CC-NUMA或机群结构。

    分布存储的大规模并行处理机 MPP

    MPP公共结构

    所有的 MPP均使用物理上分布的存储器,且使用分布的I/O也渐渐变多。节点间通过高速网络HSN(HighSpeedNetwork)相连。 每个节点包括:

    • 一个或多个处理器和高速缓存(P/C)
    • 一个局部 存储
    • 有或没有磁盘和网络接口电路 NIC(NetworkInterfaceCircuitry),它们均连向本地互连网络(早期多为总线而近期多为交叉开关)

    MPP设计问题

    • 可扩放性:MPP著名特性就是系统能扩展至成千上万个处理器,而存储器和I/O 的容量及带宽亦能按比例的增加。为此,采用物理上分布的存储器结构,它能提供比集中存储器结构更高的总计存储带宽,因此有潜在的高可扩放性;
      • 要平衡处理能力与存储和I/O 的能力,因为存储器和I/O 子系统的速度不可能与处理器成比例地提高;
      • 要平衡计算能力与交互能力,因为进程/线程的管理、通信与同步等都相当费时间。
    • 系统成本:因为 MPP系统中包含大量的元件,为了保证系统的低成本应确保每个元件的低成本。为此,
      • 应采用现有的商用 CMOS微处理器
      • 要采用相对稳定的结构,
      • 要使用物理上分布的存储器结构,它比同规模机器的中央(集中)存储器结构要便宜;
      • 要采用SMP节点方式以削减互连规模。
      • 设计者必须加入专门硬件以扩大物理地址空间规模
    • 通用性和可用性:
      • MPP要支持异步 MIMD模式;
      • 要支持流行的标准编程模式;
      • 诸节点应能按大、小作业要求进行不同的组合以支持交互和批处理模式;
      • 互连拓扑应对用户透明,看到的是一组全连接的节点;
      • MPP应在不同层次上支持单一系统映像SSI(Single-SystemImage)
      • MPP必须使用高可用性的技术。
    • 通信要求:MPP和 COW 的关键差别是节点间的通信,COW 使用标准的LAN,而 MPP使用高速、专用高带宽、低延迟的互连网络,无疑在通信方面优于 COW。
    • 存储器和I/O 能力:因为 MPP是可扩放系统,所以就要求非常大的总计存储器和I/O 设备容量,目前I/O方面的进展仍落后于系统中的其余部分。

    差别

    MPP和 COW 的关键差别是节点间的通信,COW 使用标准的LAN,而 MPP使用高速、专用高带宽、低延迟的互连网络,无疑在通信方面优于 COW。

    工作站机群COW

    定义

    工作站机群COW(ClusterofWorkstations)是实现并行计算的一种新主流技术,是属于分布式存储的 MIMD并行计算机结构,系由工作站和互连网络两部分组成。由于这种结构用于并行计算的主要资源是工作站,所以工作站机群的名称便由此产生。工作站机群COW 这一名称,在早期的研究阶段,也曾被称为工作站网络NOW(NetworkofWorkstations)。

    • 从用户、程序员和系统管理员的角度看,COW 相当于单一并行系统,感觉不到多个工作站的实际存在;
    • 从程序设计模式的角度看,它与 MPP一样可采用面向消息传递的SPMD(SingleProgramMultipleData)编程方式,即各个工作站均运行同一个程序,但分别加载不同的数据,从而可支持粗粒度的并行应用程序。

    优势

    • 投资风险小
    • 编程方便
    • 系统结构灵活
    • 性能/价格比高
    • 能充分利用分散的计算资源
    • 可扩放性好

    并行计算性能评测

    名称符号含意单位
    机器规模 n n n处理器的数目无量纲
    时钟速率 f f f时钟周期长度的倒数 M H z MHz MHz
    工作负载 W W W计算操作的数目 M f l o p Mflop Mflop
    顺序执行时间 T i T_i Ti程序在单处理机上的运行时间 s ( 秒 ) s(秒) s()
    并行执行时间 T n T_n Tn程序在并行机上的运行时间 s ( 秒 ) s(秒) s()
    速度 R n = W / T n R_n=W/T_n Rn=W/Tn每秒百万次浮点运算 M f l o p s Mflops Mflops
    加速 S n = T 1 / T n S_n=T_1/T_n Sn=T1/Tn衡量并行机有多快无量纲
    效率 E n = S n / n En=S_n/n En=Sn/n衡量处理器的利用率无量纲
    峰值速度 R p e a k = n R ’ p e a k R_{peak}=nR’_{peak} Rpeak=nRpeak所有处理器峰值速度之积, R p e a k ′ R'_{peak} Rpeak为一个处理器的峰值速度 M f l o p s Mflops Mflops
    利用率 U = R n / R p e a k U=R_n/R_{peak} U=Rn/Rpeak可达速度与峰值速度之比无量纲
    通信延迟 t 0 t_0 t0传送0一字节或单字的时间 μ s \mu{s} μs
    渐近带宽 r ∞ r_\infty r传送长消息通信速率 M B / s MB/s MB/s

    工作负载

    所谓工作负载(荷),就是计算操作的数目,通常可用执行时间、所执行的指令数目和所完成的浮点运算数三个物理量来度量它。

    • 执行时间:它可定义为在特定的计算机系统上的一个给定的应用所占用的总时间,系指应用程序从开始到结束所掠过时间(ElapsedTime),它不只是CPU时间,还包括了访问存储器、磁盘、I/O 通道的时间和 OS开销等。
    • 浮点运算:对于大型科学与工程计算问题,使用所执行的浮点运算数目来表示工作负载是很自然的。对于程序中的其他类型的运算,可按如下经验规则折算成浮点运算(Flop)数:在运算表达式中的赋值操作、变址计算等均不单独考虑(即它们被折算成0Flop);单独赋值操作、加法、减法、乘法、比较、数据类型转换等运算均各折算成1Flop;除法和开平方运算各折算成4Flop;正(余)弦、指数类运算各折算成8Flop;其他类运算,可按其复杂程度,参照上述经验数据进行折算之。
    • 指令数目:对于任何给定的应用,它所执行的指令条数就可视为工作负载,常以百万条指令为计算单位,与其相应的速度单位就是MIPS(每秒百万条指令)。

    并行执行时间

    在无重叠操作的假定下,并行程序的执行时间 T n T_n Tn为:
    T n = T c o m p u t + T p a r o + T c o m m T_n=T_{comput}+T_{paro}+T_{comm} Tn=Tcomput+Tparo+Tcomm

    • Tcomput为计算时间
    • Tparo为并行开销时间
      • 包括进程管理(如进程生成、结束和切换等)时间,组操作(如进程组的生成与消亡等)时间和进程查寻(如询问进程的标志、等级、组标志和组大小等)时间;
    • Tcomm为相互通信时间。
      • 包括同步(如路障、锁、临界区、事件等)时间,通信(如点到点通信、整体通信、读/写共享变量等)时间和聚合操作(如归约、前缀运算等)时间。

    存储器性能

    存储器的层次结构

    • 容量C:表示各层的物理存储器件能保存多少字节的数据;
    • 延迟L:表示读取各层物理器件中一个字所需的时间;
    • 带宽B:表示在1秒钟内各层的物理器件中能传送多少个字节。

    在这里插入图片描述

    存储器带宽的估算

    公式

    带 宽 = 操 作 的 存 储 长 度 × 时 钟 频 率 带宽=操作的存储长度\times时钟频率 =×

    较快的时钟频率和处理器中较高的并行操作,可获得较宽的带宽

    例:RISC加法指令带宽估算

    条件:字长64位(8字节),时钟频率100MHz,单拍内可完成指令

    指令流程:取2个字a,b,执行操作后送回寄存器,共涉及3个字(24字节)

    三大定律

    简称定义

    • 是并行系统中处理器数;
    • W是问题规模(下文中也常叫作计算负载、工作负载,它定义为给定问题的总计算量),
    • Ws 是应用程序中的串行分量,
    • Wp是W中可并行化部分(显然 Ws+Wp= W);
    • Wo为额外开销
    • f是串行分量比例(f= Ws/W,Ws= W1),
    • 1-f为并行分量比例(显然 f+(1-f)=1);
    • Ts=T1 为串行执行时间,
    • Tp 为并行执行时间;
    • S为加速(比),
    • E为效率。
    • G(p)反映存储容量增加到p倍时工作负载的增加量

    Amdahl定律 - 固定负载的加速公式

    原公式

    S = W s + W p W s + W p p S=\frac{W_s+W_p}{W_s+\frac{W_p}{p}} S=Ws+pWpWs+Wp

    归一化的公式

    W s + W p W_s+W_p Ws+Wp表示为 f + ( 1 − f ) f+(1-f) f+(1f)得:
    S = f + ( 1 − f ) f + 1 − f p = p 1 + f ( p − 1 ) S=\frac{f+(1-f)}{f+\frac{1-f}{p}}=\frac{p}{1+f(p-1)} S=f+p1ff+(1f)=1+f(p1)p

    修正的公式

    上并行加速不仅受限于程序的串行分量,而且也受并行程序运行时的额外开销影响

    极限情况与条件
    • 对于理想情况:当 p → ∞ p\to\infty p时取极限

    S = 1 f S=\frac{1}{f} S=f1

    • 对于实际情况:当 p → ∞ p\to\infty p时取极限

    S = 1 f + W o W S=\frac{1}{f+\frac{W_o}{W}} S=f+WWo1

    出发点
    • 对于很多科学计算,实时性要求很高,即在此类应用中时间是个关键因素,而计算负载是固定不变的。为此在一定的计算负载下,为达到实时性可利用增加处理器数来提高计算速度;
    • 因为固定的计算负载是可分布在多个处理器上的,这样增加了处理器就加快了执行速度,从而达到了加速的目的。
    含义

    它意味着随着处理器数目的无限增大,并行系统所能达到的加速之上限为 1 f \frac{1}{f} f1

    在这里插入图片描述

    Gustafson加速定律

    原公式

    归一化公式

    修正的公式

    极限情况与条件

    当 p充分大时,S′与p几乎成线性关系,其斜率为1-f。

    出发点
    • 对于很多大型计算,精度要求很高,即在此类应用中精度是个关键因素,而计算时间是固定不变的。此时为了提高精度,必须加大计算量,相应地亦必须增多处理器数才能维持时间不变;
    • 除非学术研究,在实际应用中没有必要固定工作负载而使计算程序运行在不同数目的处理器上,增多处理 器必须相应地增大问题规模才有实际意义。
    含义

    意味着随着处理器数目的增加,加速几乎与处理器数成比例的线性增加,串行比例 f不再是程序的瓶颈。

    注意,Wo是p的函数,它可能随 p增大、减小或不变。一般化的 Gustafson 定律欲达到线性加速必须使 Wo随 p减小,但这常常是困难的。

    在这里插入图片描述

    Sun和Ni定律 - 存储受限的加速定律

    原公式

    S ′ ′ = f W + ( 1 − f ) G ( p ) W f W + ( 1 − f ) G ( p ) W p S''=\frac{fW+(1-f)G(p)W}{fW+(1-f)G(p)\frac{W}{p}} S=fW+(1f)G(p)pWfW+(1f)G(p)W

    归一化公式

    S ′ ′ = f + ( 1 − f ) G ( p ) f + ( 1 − f ) G ( p ) p S''=\frac{f+(1-f)G(p)}{f+(1-f)\frac{G(p)}{{p}}} S=f+(1f)pG(p)f+(1f)G(p)

    修正的公式

    极限情况与条件
    • G ( p ) = 1 G(p)=1 G(p)=1时:变为 1 f + ( 1 − f ) p \frac{1}{f+\frac{(1-f)}{p}} f+p(1f)1( Amdahl加速定律)
    • G ( p ) = p G(p)=p G(p)=p时:变为 f + p ( 1 − f ) f+p(1-f) f+p(1f)(Gustafson加速定律;当 G(p)>p时,它相应于计算负载比存储要求增加得快)
    基本思想

    其基本思想是只要存储空间许可,应尽量增大问题规模以产生更好或更精确的解(此时可能使执行时间略有增加)。换句话说,假若有足够的存储容量,并且规模可扩放的问题满足 Gustafson定律规定的时间要求,那么就有可能进一步增大问题规模求得更好或更精确的解。 ,它相应于计算负载比存储要求增加得快,此时Sun和Ni加速均比 Amdahl加速和 Gustafson加速为高。

    在这里插入图片描述

    并行算法的设计基础

    并行算法基本概念

    • 并行算法(ParallelAlgorithm)是一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。
      • 数值计算是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数值计算问题。求解数值计算问题的算法称为数值算法(NumericalAlgorithm)。
      • 非数值计算是指基于比较关系运算的一类诸如排序、选择、搜索、匹配等 符号 处 理 问 题。求 解 非 数 值 计 算 问 题 的 算 法 称 为 非 数 值 算 法(Non_NumericalAlgorithm)。
      • 同步算法(SynchronizedAlgorithm)是指算法的诸进程的执行必须相互等待的一类并行算法。
      • 异步算法(ASynchronizedAlgorithm)是指算法的诸进程的执行不必相互等待的一类并行算法。
      • 分布算法(DistributedAlgorithm)是指由通信链路连接的多个场点(Site)或节点,协同完成问题求解的一类并行算法。
        • 在 局 网 环 境 下 进 行 的 计 算 称 为 分 布 计 算(Distributed Computing)。
        • 把 工 作 站 机 群 COW(ClusterofWorkstations)环境下进行的计算称为网络计算(NetworkComputing)。
        • 把基于Internet的计算则称为元计算(MetaComputing)。
      • 确定算法(DeterministicAlgorithm)是指算法的每一步都能明确地指明下一步应该如何行进的一种算法。
      • 随机算法(RandomizedAlgorithm)是指算法的每一步,随机地从指定范围内选取若干参数,由其来确定算法的下一步走向的一种算法。

    并行计算模型基本概念

    所谓计算模型实际上就是硬件和软件之间的一种桥梁,使用它能够设计分析算法,在其上高级语言能被有效地编译且能够用硬件来实现。

    PRAM(ParallelRandomAccessMachine)模型

    并行随机存取机器,也称之为共享存储的SIMD模型,是一种抽象的并行计算模型。在这种模型中,假定存在着一个容量无限大的共享存储器;有有限或无限个功能相同的处理器,且其均具有简单的算术运算和逻辑判断功能;在任何时刻各处理器均可通过共享存储单元相互交换数据。

    分类

    根据处理器对共享存储单元同时读、同时写的限制,PRAM 模型又可分为:

    • 不允许同时读和同时写(Exclusive_ReadandExclusive_Write)的 PRAM 模 型,简 记之 为 PRAM_EREW;(最弱计算模型)
    • 允许同 时读 不 允 许同 时 写(Concurrent_ReadandExclusive_Write)的 PRAM 模型,简记之为 PRAM_CREW。
    • 允许同时读和同时写(Concurrent_ReadandConcurrent_Write)的PRAM 模型,简记之为PRAM_CRCW。(最强计算模型)
      • 只允许所有的处理器 同时写相同的数,此时称为 公共(Common)的PRAM_CRCW,简记之为CPRAM_CRCW;
      • 只允许最优先的处理器先写,此时称为优先(Priority)的PRAM_CRCW,简记之为PPRAM_CRCW;
      • 允许任意 处 理 器 自 由 写,此 时 称 为 任 意(Arbitrary)的 PRAM_CRCW,简 记 之 为APRAM_CRCW。
    优点
    • 特别适合于并行算法的表达、分析和比较;
    • 使用简单,很多诸如处理器间通信、存储管理和进程同步等并行机的低级细节均隐含于模型中;
    • 易于设计算法和稍加修改便可运行在不同的并行机上;
    • 有可能在 PRAM 模型中加入一些诸如同步和通信等需要考虑的问题。
    缺点
    • PRAM 是一个同步模型,这就意味着所有的指令均按锁步方式操作,用户虽感觉不到同步的存在,但它的确是很费时的;
    • 共享单一存储器的假定,显然不适合于分布存储的异步的 MIMD机器;
    • 假定每个处理器均可在单位时间内访问任何存储单元而略去存取竞争和有限带宽等是不现实的。
    推广
    • 存储竞争模型,它将存储器分成一些模块,每个模块一次均可处理一个访问,从而可在模块级处理存储器的竞争;延迟模型,它考虑了信息的产生和能够使用之间的通信延迟;
    • 局部 PRAM 模型,此模型考虑到了通信带宽,它假定每个处理器均有无限的局存,而访问全局存储器是较昂贵的;
    • 分层存储模型,它将存储器视为分层的存储模块,每个模块由其大小和传送时间表征,多处理机由模块树表示,叶为处理器;
    • 异步PRAM模型

    异步PRAM模型

    分相(Phase)PRAM 模型是一个异步的 PRAM 模型,简记之为APRAM,系由p个处理器组成,其特点是每个处理器都有其局存、局部时钟和局部程序;

    特点
    • 处理器间的通信经过共享全局存储器;无全局时钟,各处理器异步地独立执行各自的指令;
    • 处理器任何时间依赖关系需明确地在各处理器的程序中加入同步(路)障(SynchronizationBarrier);
    • 一条指令可在非确定(无界)但有限的时间内完成。
    指令类型
    • 全局读:将全局存储单元中的内容读入局存单元中;
    • 局部操作:对局存中的数执行操作,其结果存入局存中;
    • 全局写:将局存单元中的内容写入全局存储单元中;
    • 同步:同步是计算中的一个逻辑点,在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序。

    BSP(BulkSynchronousParallel)模型

    性质和特点
    • 将处理器和选路器分开,强调了计算任务和通信任务的分开,而选路器仅施行点到点的消息传递,不提供组合、复制或广播等功能
    • 将处理器和选路器分开,强调了计算任务和通信任务的分开,而选路器仅施行点到点的消息传递,不提供组合、复制或广播等功能
    • 如果能合适地平衡计算和通信,则 BSP模型在可编程性方面具有主要的优点
    • 为PRAM 模型所设计的算法,均可采用在每个BSP处理器上模拟一些PRAM 处理器的方法实现之。

    logP模型(logPModel)

    是一种分布存储的、点到点通信的多处理机模型,其中通信网络由一组参数来描述,但它并不涉及到具体的网络结构,也不假定算法一定要用显式的消息传递操作进行描述。

    参数
    • l(Latency)表示在网络中消息从源到目的地所遭到的延迟;
    • o(Overhead)表示处理器发送或接收一条消息所需的额外开销(包含操作系统核心开销和网络软件开销),在此期间内它不能进行其它的操作;
    • g(Gap)表示处理器可连续进行消息发送或接收的最小时间间隔;
    • P(Processor)表示处理器/存储器模块数。

    并行算法的一般设计策略

    串行算法直接并行化

    • 对于一类具有内在顺序性的串行算法,则恐难于直接并行化。
    • 并非任何优秀的串行算法都可以产生好的并行算法,相反一个不好的串行算法则有可能产生很优秀的并行算法。

    从问题描述开始设计并行算法

    对于有些问题,现有的串行算法恐难直接将其并行化,此时要从问题的描述出发,寻求可能的新途径,设计出一个新的并行算法。但这并不是说完全排除某些串行算法设计的基本思想,而是更着重从并行化的具体实现上开辟新的设计方法。

    借用已有算法求解新问题

    所谓“借用法”是指借用已知的某类问题的求解算法来求解另一类问题。不但要从问题求解方法的相似性方面仔细观察,寻求问题解法的共同点;而且所借来的方法要用得合算,效率要高,从而能达借用的目的。

    并行算法的基本设计技术

    划分时关键在于如何将问题进行分组,使得子问题较容易并行求解,或者子问题的解较容易被组合成原问题的解。

    划分求解的基本步骤

    • 将给定的问题劈成p个独立的几乎等尺寸的子问题;
    • 用p台处理器并行求解诸子问题。

    均匀划分技术

    假定待处理的序列长为n,现有p台处理器,一种最基本的划分方法就是均分划分(UniformPartition),系将n个元素分割成p段,每段含有n/p个元素且分配给一台处理器。

    对数划分技术

    假定待处理的序列长为n,现欲将其分段处理。取每第ilogn(i=1,2,…)个元素作为划分元素,而将序列划分成若干段,然后分段处理之。

    功能划分技术

    欲从长为n的序列中选取前m个最小者,可以将长为n的序列划分成等长的一些组,每组中的元素数应大于或等于m(最后一组除外)。然后各组并行处理。

    并行算法的一般设计过程

    PCAM基本步骤

    • 划分:将整个计算分解成一些小的任务,其目的是尽量开拓并行执行的机会。
    • 通信:确定诸任务执行中所需交换的数据和协调诸任务的执行,由此可检测上述划分的合理性。
    • 组合:按性能要求和实现的代价来考察前两阶段的结果,必要时可将一些小的任务组合成更大的任务以提高性能或减少通信开销。
    • 映射:将每个任务分配到一个处理器上,其目的是最小化全局执行时间和通信成本以及最大化处理器的利用率。

    在这里插入图片描述

    划 分

    所谓划分,就是使用域分解或功能分解的办法将原计算问题分割成一些小的计算任务,以充分揭示并行执行的机会。

    • 目的:充分开拓算法的并发性和可扩放性;
    • 方法:先集中数据的分解(称域分解),然后是计算功能的分解(称功能分解),两者互为补充;
    • 要点:力图避免数据和计算的复制,应使数据集和计算集互不相交。

    通 信

    由划分所产生的诸并行执行的任务,一般而言都不能完全独立执行,一个任务中的计算可能需要用到另一个任务中的数据,从而就产生了通信要求。所谓通信,就是为了进行并行计算,诸任务之间所需进行的数据传输。

    通信模式

    • 局部/全局通信:局部通信时,每个任务只与较少的几个近邻通信;全局通信中,每个任务与很多别的任务通信。
    • 结构化/非结构化通信:结构化通信时,一个任务和其近邻形成规整结构(如树、网格等);非结构化通信中,通信网则可能是任意图。
    • 静态/动态通信:静态通信,通信伙伴的身份不随时间改变,动态通信中,通信伙伴的身份则可能由运行时所计算的数据决定且是可变的。
    • 同步/异步通信:同步通信时,接收方和发送方协同操作;异步通信中,接收方获取数据无需与发送方协同。

    组 合

    从抽象转到具体,即重新考察在划分和通信阶段所作的抉择,力图得到一个在某一类并行机上能有效执行的并行算法。 目的是通过合并小尺寸的任务来减少任务数,但它仍可能多于处理器的数目。

    映 射

    在设计的最后阶段,我们要指定每个任务到哪里去执行,此即映射(Mapping)。开发映射的主要目的是减少算法的总的执行时间。

    基本策略

    • 把那些能够并发执行的任务放在不同的处理器上以增强并行度
    • 把那些需频繁通信的任务置于同一个处理器上以提高局部性。

    算法编写

    矩阵相乘、线性方程组求解(稠密)、快速傅里叶变换

    展开全文
  • 我们来介绍介绍多线程实现矩阵转置的另一种方法,直角划分法。 那么我们就一起来看看如何做到的吧。 首先,我们要知道什么是直角。 Q:什么是直角呢? A:??不是吧阿sir,直角你都不知道,不是吧不是吧。 没错,就是...
  • 并行算法】考试样卷

    千次阅读 2021-01-05 21:49:35
    一、选择(每小2分,共20分) 1、按照结点间连接的性质,互联网络的拓扑结构可以分为___________三类。 ①静态拓扑结构 ②动态拓扑结构 ③混合拓扑结构 ④宽带互联网络 A.①②③ B.①②④ C.②③④ D.①③④ 2、...
  •   本书以并行计算为主题,主要讨论并行计算的硬件基础——当代并行计算机系统及其结构模型,并行计算的核心内容——并行算法设计与并行数值算法以及并行计算的软件支持——并行程序的设计原理与方法。...
  • 1.从并行算法的设计和分析出发,将各种并行计算机(至少是某一类)的基本特征抽象出来,形成一个抽象的模型称为_____并行计算模型_______。 2.BSP模型是以三个参数描述______分布式存储______的多计算模型,在BSP...
  • 并行计算》期末总结

    千次阅读 2016-06-05 20:38:47
    并行计算》总结标签: 并行计算一、并行介绍域分解 针对的分解对象:数据 首先确定数据如何划分到各处理器 然后确定各处理器要做的事情 示例:求最大值 任务(功能)分解 针对的分解对象:任务(功能) 首先将任务划分...
  • 并行计算 就我们程序员而言,一个程序包含了指令和数据,对于一个具体问题,我们会尝试将问题进行拆解形成子问题或者子模块,模块之间可能会存在依赖关系,即一个模块的输出会作为另一个模块的输入,这样的关系只能串行。 ...
  • Python-多线程与并行计算

    千次阅读 2017-11-21 14:44:33
    今天看图像处理cuda的时候看到了并行计算,又恰巧参加第二届CCF举办CCSP比赛的时候,第五是可以并行计算的。。。在赛后分享上,听清华大佬讲得栩栩如生,我听得一愣一愣的。真的是嘴上笑嘻嘻,心理妈卖批。不过...
  • 文章目录0 前言1 java web 平台/业务系统 毕设选题2 java web 管理系统 毕设选题3 游戏设计、动画设计类 毕设选题 (适合数媒的同学)4 算法开发5 数据挖掘 毕设选题6 大数据处理、云计算、区块链 毕设选题7 网络安全 ...
  • 并行与分布式计算复习大纲 华南农业大学

    千次阅读 多人点赞 2021-01-04 18:37:53
    分布和并行计算的区别(重点) 答:并行(如果针对线程进程而言的问题的话,并行就是共享计算机CPU资源)。单机多核,问题并行编程;分布:网络连接,对外以整体提供服务 并行和并发的区别(重点) 答:并发:...
  • 并行程序设计导论 第二章习题

    万次阅读 多人点赞 2015-02-12 15:51:08
    这是一道证明,自己对这块的理解还差很多,这里也就先略过吧。 2.15 a. 假定一个共享内存系统使用监听一致性协议和写回缓存。并假设0号核的缓存里有变量x,并执行赋值命令x=5。1号核的缓存里没有变量x。...
  • 并行与分布式计算期末复习提纲

    千次阅读 2020-01-02 22:33:54
    并行与分布式计算 MPI 初始化 MPI_Init(&argc, &argv) 结束 MPI_Finalize() MPI_COMM_WORLD 一个通信域,包含通信的所有进程 当前进程标识 MPI_Comm_rank(MPI_COMM_WORLD, &node); 通信域包含的进程...
  • 计算机体系结构试题及答案

    热门讨论 2009-11-18 14:15:01
    并行程序的计算/通信比率 7.2 多处理机的存储器体系结构 7.2.1 集中式共享存储器体系结构 7.2.2 分布式共享存储器体系结构 7.3 互连网络 7.3.1 互连网络的性能参数 7.3.2 静态连接网络 7.3.3 动态...
  • 并行程序设计导论 第三章习题

    千次阅读 2015-04-03 01:11:26
    在问候程序中,如果strlen(greeting)代替strlen(greeting)+1来计算进程1、2、…、comm_sz-1发送消息的长度,会发生什么情况?如果用MAX_STRING代替strlen(greeting)+1又会是什么结果?你可以解释这些结果吗? 解答...
  • 并行程序设计导论 第一章习题

    万次阅读 多人点赞 2015-02-08 14:54:11
    这两天也算是找到了这本《并行程序设计导论》,现在准备从最简单的并发的开始。 笔记应该不会做的太多,除非阅读到某些深有感触或有很大疑惑的地方才会写出来。 还有,对于CSDN博客支持markdown格式也是要赞一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,346
精华内容 14,538
关键字:

并行计算题的一般设计方法