精华内容
下载资源
问答
  • 并行算法分析

    千次阅读 2018-05-13 16:47:45
    并行算法分析 基本指标 并行算法分析 VS 串行算法分析 并行程序设计的复杂性 并行算法的额外开销 性能评价标准 效率 代价 可扩展性 并行算法分析 基本指标 并行算法分析 VS 串行算法分析 串行算法...

    并行算法分析

    基本指标

    并行算法分析 VS 串行算法分析

    1. 串行算法评价:算法时间复杂度表示为输入规模的函数
    2. 并行算法评价:除了输入规模之外,还应考虑处理器数目、**处理器相对运算速
      通信速度**
    3. 评价标准
      • 运行时间
      • 加速比:并行算法比串行算法快多少?

    并行程序设计的复杂性

    1. 足够的并发度(Amdahl定律)
    2. 并发粒度
      独立的计算任务的大小
    3. 局部性
      对临近的数据进行计算
    4. 负载均衡
      处理器的工作量相近
    5. 协调和同步
      谁负责?处理频率?

    并行算法的额外开销

    除了串行算法要做的之外的工作
    1. 进程间通信:最大开销,大部分并行算法都需要
    2. 进程空闲:负载不均、同步操作、不能并行 化的部分
    3. 额外计算

    • 最优串行算法难以并行化,将很差的串行算法并行化,并行算法计算量>最优串行算法

    • 最优串行算法并行化也会产生额外计算:并行快 速傅立叶变换,旋转因子的重复计算

    性能评价标准

    1. 运行时间
      串行算法:TS,算法开始到结束的时间流逝
      并行算法:TP,并行算法开始到最后一个进 程结束所经历时间

    2. 并行算法总额外开销
      To=pTP – TS

    3. 加速比
      S=TS/TP

    效率

    • 理想并行算法,S=p
    • 难实现,不是100%时间都用于有效计算
    • 求和例子,部分时间处理器处于空闲
    • 效率(Efficiency):度量有效计算时间
    • 理想情况=1,正常0~1
    • E=S/p
    • 求和例子
      E= Q(n/logn)/n= Q(1/logn)

    代价

    • cost,并行算法运行时间×处理器数量
    • 所有处理器用来求解问题的时间总和
    • E=TS/cost,p=1时,cost=TS
    • 代价最优,cost-optimal:代价与最优串 行算法运行时间渐进相等——E= Q(1)
    • 代价也称为工作量(work),处理器时 间积(processor-time product)

    可扩展性

    可扩展性是高性能并行机和并行算法追求的主要目标,其主要作用:
    ❑ 度量并行系统性能的方法之一
    ❑ 度量并行体系结构在不同系统规模下的并行
    处理能力
    ❑ 度量并行算法内在的并行性
    ❑ 利用系统规模和问题规模已知的并行系统性 能来预测规模增大后的性能:scale down,
    适合开发、调试,不适合性能预测

    展开全文
  • 研一开设的并行算法设计与分析,教材使用的是《并行算法设计与分析 陈国良》,考试前进行总结如下: sdd

    研一开设的并行算法设计与分析,教材使用的是《并行算法的设计与分析 陈国良》,考试前进行总结如下:

    思维导图文件可以私信我要,有PDF版本;
    考试内容如下:
    在这里插入图片描述

    展开全文
  • 并行算法设计与分析

    千次阅读 2019-04-13 10:58:12
    并行算法设计 任务并行 数据并行 任务并行不同,前者是划分操作和计算任务,核心对于数据进行不同的运算;后者是划分数据,而核心对于数据进行相同的运算。...并行算法分析 性能评价标准 运行时间 TpT_pTp​并...

    并行算法设计

    任务并行

    数据并行

    与任务并行不同,前者是划分操作和计算任务,核心对于数据进行不同的运算;后者是划分数据,而核心对于数据进行相同的运算。

    其他任务划分方法

    搜索分解

    将搜索树的每个子树划分成一个任务,与数据分解的区别在于,前者的所有计算工作都是有用的,对于后者一旦找到解,其他搜索工作也停止
    工作量可能大于也可能小于串行算法。

    并行算法分析

    性能评价标准

    运行时间

    TpT_p并行算法开始到最后一个进程结束所需要的时间。

    并行算法额外总开销

    To=pTpTsT_o=pT_p-T_s
    其中TsT_s指的是最优串行算法运行时间,pp指的是并行进程数目。

    加速比

    并行算法比串行算法快的倍数。

    S=TsTpS=\frac{T_s}{T_p}

    一般情况下1Sp1 \leq S \leq p,这是因为并行算法一般比串行算法要快,但是会有一些额外开销。
    但是SpS \geq{p}也是可能出现的,可能原因是硬件条件不利于串行算法。

    效率

    度量有效计算时间。
    E=Sp=TscostE=\frac{S}{p}=\frac{T_s}{cost}
    理想情况下是1。

    代价cost

    cost=pTpcost=pT_p
    代价也称作工作量,处理器时间积。
    代价最优,即最优串行算法运算时间与代价近似相等,即p趋近于1,即E=O(1)E=O(1)

    可扩展性

    • 算法的强可扩展性定义:算法的效率恒定,或效率不随着线程数的增大而降低,那
      么称程序是可扩展的。
      算法的弱可扩展性定义:问题规模以一定速率增大,效率不随着线程数的增大而
      降低,则认为程序是可扩展的。
    • 度量并行体系结构在不同系统规模下的并行处理能力,利用系统规模和问题规模已知的并行系统性能来预测规模增大后的性能
      1. 在并行线程数pp一定的情况下,随着nn的增大,SES、E逐渐增大并且趋向于饱和。
        这可能是因为随着nn的增大,额外开销相对减小。
      2. nn(问题规模)一定的情况下,随着pp的增大,额外开销增大,SS趋向于饱和,EE减小。
        证明:E=Sp=TspTp=TsTo+Ts=1ToTs+1E=\frac{S}{p}=\frac{T_s}{pT_p}=\frac{T_s}{T_o+T_s}=\frac{1}{\frac{T_o}{T_s}+1}
    • 为了保持效率不变,问题规模与处理器数量的增长比率度量了系统的可扩展性,越慢,越好。
    • 问题规模:最佳串行算法在单处理单元求解问题所需基本运算步骤数目。如果设定一个基本操作需要一个单位时间,那么Ts=WT_s=W
    • 因此,效率可以表示为问题规模和线程数的函数。推导过程如下:
      Tp=To+Tsp=To(W,p)+WpT_p=\frac{T_o+T_s}{p}=\frac{T_o(W, p)+W}{p}
      S=TsTp=WpTo(W,p)+WS=\frac{T_s}{T_p}=\frac{Wp}{T_o(W,p)+W}
      E=Sp=WTo(W,p)+W=1To(W,p)/W+1E=\frac{S}{p}=\frac{W}{T_o(W,p)+W}=\frac{1}{T_o(W,p)/W+1}
      分析:
      WW不变,pp增加,ToT_o增加,因此EE减少。
      pp不变,WW增加,ToT_o增加比WW要慢,因此EE增加。
      可以通过同时增加WpW、p,使得效率保持不变。
    • 等效率函数:W=KTo(W,p)W=KT_o(W,p)
      较小——较小的问题规模即可充分利用较多的处理器的计算能力,强/高可扩展性
      较大——弱/低可扩展性
    展开全文
  • 并行算法设计

    2018-05-13 16:10:17
    并行算法设计 并行算法设计 任务分解、数据依赖、竞争条件 设计一个并行算法 竞争条件数据依赖 n 个数求和的例子 1.串行算法 2. 并行算法 版本1:计算任务划分 版本2:加锁 版本3:粗粒度 版本4:消除锁 同步方法...

    并行算法设计

    并行算法设计

    假定已有求解问题的串行算法,我们将 其改为并行版本

    • 并不一定是最好的策略——有些情况下,最 优并行算法与最优串行算法完全没有关系
    • 但很有用,我们很熟悉串行算法,很多时候 是切实可行的方法

    并行算法与体系结构紧密相关!

    任务分解、数据依赖、竞争条件

    设计一个并行算法

    1. 计算任务的分解
      ❑ 如何将并行计算工作分解,交由众多进程/线程并发执行
    2. 保持依赖关系
      ❑ 计算结果与串行算法保持一致
    3. 额外开销
      ❑ 有多种类型的开销,要尽量降低

    竞争条件与数据依赖

    1. 执行结果依赖于两个或更多事件的时序, 则存在竞争条件(race condition)
    2. 数据依赖(data dependence)就是两个内 存操作的序,为了保证结果的正确性,
      必须保持这个序
    3. 同步(synchronization)用来将多个线程 的执行串行化,或是将并发数据访问串
      行化

    n 个数求和的例子

    1.串行算法
    sum = 0;
    for (i = 0; i < n; i++) {
    x = Compute next value(. . .);
    sum += x; }
    2. 并行算法
    版本1:计算任务划分

    假定每个核心计算连续n/t个元素的部分和(t为线程数或处理器数)

    int block_length_per_thread = n/t;
    int start = id * block_length_per_thread;
    for (i=start; i<start+block_length_per_thread; i++) {
    x = Compute_next_value(...);
    sum += x; }

    分析
    1. 循环步之间的求和运算存在依赖→ 线程间依赖
    ❑ 但可以重排顺序,因为加法运算满足结合律
    2. 取数-加法-存结果必须是原子操作,以保持结果与串行执行一致
    3. 定义
    原子性(atomicity):一组操作要么全部执行要么全不执行,则称其是原子的。即不会得到部分执行的结果。
    互斥(mutual exclusion):任何时刻都只有一个线程在执行.

    版本2:加锁

    插入互斥(mutex),保证任何时刻只有一个线程读数-加法-存结果——原子操作

    int block_length_per_thread = n/t;
    mutex m;
    int start = id * block_length_per_thread;
    for (i=start; i<start+block_length_per_thread; i++) {
    my_x = Compute_next_value(...); mutex_lock(m);
    sum += my_x;
    mutex_unlock(m);
    }
    版本3:粗粒度

    在将局部和加到全局和时才加锁

    int block_length_per_thread = n/t;
    mutex m;
    int my_sum;
    int start = id * block_length_per_thread;
    for (i=start; i<start+block_length_per_thread; i++) 
    {
        my_x = Compute_next_value(...);
        my_sum += my_x; 
    }
    mutex_lock(m); 
    sum += my_sum; 
    mutex_unlock(m);
    版本4:消除锁

    “主“线程完成部分和相加

    int block_length_per_thread = n/t;
    mutex m;
    shared my_sum[t];
    int start = id * block_length_per_thread;
    for (i=start; i<start+block_length_per_thread; i++) {
    my_x = Compute_next_value(...);
    my_sum[id] += my_x; }
    if (id == 0) { // 主线程
    sum = my_sum[0];
    for (i=1; i<t; i++) sum += my_sum[i];
    }
    同步方法:障碍
    1. 如果主线程开始计算全局和的时候其他线程还未完成计算,就会得到不正确的结果
    2. 如何强制主线程等待其他线程完成之后再进行全局和计算呢?
    3. 定义
      障碍(barrier)阻塞线程继续执行,在此程序点等待,直到所有参与线程都到达障碍点才继续执行
    版本5:消除锁,但增加障碍
    int block_length_per_thread = n/t;
    mutex m;
    shared my_sum[t];
    int start = id * block_length_per_thread;
    for (i=start; i<start+block_length_per_thread; i++) {
    my_x = Compute_next_value(...);
    my_sum[t] += x; }
    Synchronize_cores(); // 所有参与线程都设置障碍 
    if (id == 0) { // 主线程
    sum = my_sum[0];
    for (i=1; i<t; i++) 
        sum += my_sum[t];
    }
    版本6:多核并行求全局和

    这里写图片描述

    求和例子总结
    • 求和计算有竞争条件和数据依赖
    • 使用mutex和障碍进行同步保证正确结果
    • 更多地进行本地运算,以提高线程间并行计算的粒度

    • 在这个例子中看到了哪些额外开销?
      ❑ 分配计算任务的额外代码
      ❑ 锁开销:加锁/解锁操作本身开销和线程间 竞争导致的空闲等待
      ❑ 负载不均

    数据并行

    如何设计并行算法

    1. 任务并行
      将求解问题的计算分解为任务,分配给多个核心
    2. 数据并行
      • 将求解问题涉及的数据划分给多个核心
      • 每个核心对不同数据进行相似的计算

    其他任务划分方法

    展开全文
  • 并行算法设计与分析 第3版 陈国良编著 2009年8月出版 高清扫描pdf版,值得大家收藏~~ 另外:并行计算——结构·算法·编程(修订版)—陈国良编著 2003,请参看我的上传列表
  • 并行算法设计与性能优化总结

    千次阅读 2016-03-28 10:18:29
    1.并行和并发的区别在于并发是在单核上执行多线程,即为满足用户应用需求,并行才是为了加速。 2.一般来说,并行相对串行的加速比,不会超过核数。Amdal定律告诉我们,在计算规模一定的前提下,只要代码中有不能并行...
  • 并行算法设计基础

    2019-07-05 22:31:56
    并行算法的定义和分类 并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。 并行算法分类 数值计算非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法 ...
  • 并行算法

    千次阅读 2019-04-23 19:22:44
    并行算法设计包括划分法、分治法、平衡树法、倍增法、指针跳跃法、流水线法、破对称法等,根据问题的特性来选择适合的设计方法。 并行编程的模型主要有数据并行、消息传递和共享存储器。并行语言发展迅速,并行语言...
  • 并行算法是并行计算的基础,实现技术相结合,为高效率使用并行计算机提供解决方案。其基本原则简述如下: 1 体系相结合 常见的并行计算的硬件载体有FPGA、GPU、多核CPU(ARM、x86)、DSP等。FPGA硬件加速的...
  • 并行计算复习第二篇 并行计算理论基础:并行算法设计Ch5 并行算法与并行计算模型5.1 并行算法的基础知识1.并行算法的表达(1)par-don个节点并行完成for循环(每个节点不同,和i相关):for i = 1 to n par-do ... ...
  • 算法分析与设计总结

    千次阅读 2017-11-04 10:54:00
    算法分析与设计总结 回顾这八周以来关于这课程的学习情况,我体会最深的是:不论是从深度还是从广度上,现在所习的算法比以前学习的算法难度增加了很多。但是费老师极富经验的教学和课件,为我的学习提供了很大的...
  • 算法分析与设计基础 (清华版)

    千次阅读 2019-05-02 21:28:40
    算法分析与设计基础 (清华版)
  • 并行算法设计--Foster的设计方法论

    千次阅读 2017-07-31 20:56:48
    a 原始任务数至少比目标并行计算机上的处理器数高一个数量级(如果该条件不能满足的话,则后面的设计将受到很大限制) b 冗余计算和冗余数据结构存储最小化(如果该条件不能满足的话,则该设计 在问题规模增加的...
  • 基于MapReduce的并行算法设计

    千次阅读 2014-11-03 19:46:21
    这是中国大学MOOC中的大数据算法课程笔记
  • 并行计算及并行算法

    万次阅读 多人点赞 2018-06-13 22:27:31
    一、并行计算  简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算、超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关...
  • 排序算法并行分析

    万次阅读 多人点赞 2016-05-05 00:52:11
    我之前刚好在写排序,于是我就将常用的排序写了一遍并且用OpenMP进行并行,计算加速比等数据进行分析。在这篇文章中我主要介绍八大基本排序的实现原理及代码,以及对这些算法进行改进从而让它们可以并行,并且对他们...
  • 算法分析与设计 作者: (美)古德里奇,(美)塔玛西亚 著,霍红卫 译 出版社: 人民邮电出版社 出版日期: 2006-10 印次: 1 定价: 55.00 内容提要:  本书系统地阐述了算法设计...
  • 算法分析与设计课程资料:蚂蚁算法的初步研究计算机模拟 整理:Ackarlix 近年来在人工智能界引出的新的研究小热点----蚂蚁算法,以及我们对蚂蚁算法的一些研究成果。我们从完全不同的观点来研究蚂蚁等昆虫群体...
  • 并行算法的基本原理

    千次阅读 2015-09-05 16:30:02
    并行算法的基本原理 并行算法就是用多...并行算法的研究应该确立一个“理论-设计-实现-应用”的系统方法,形成一个完善的 “架构—算法—编程” 方法论,这样才能保证并行算法不断发展并变得更加实用。 简单的说,算
  • 算法---->并行算法

    千次阅读 2013-05-20 16:32:53
    并行算法 一、并行算法 什么是并行算法? 它可理解为: 适合于在某类并行计算机上求解问题和处理数据的算法, 是一些可同时执行的诸进程的集合, 这些进程相互作用和协调作用, 从而达到对给定问题的求解。 二、并行...
  • FFT并行算法与应用-基于MPI(三)

    千次阅读 2018-01-25 18:26:45
    给出针对一维FFT的并行计算方法,并针对其加以分析推广到二维FFT的计算中。 并行FFT算法: (1)计算长度为p和n/p2的按位倒置序列; (2)进行处理机内部的数据交换和外部的数据交换; (3)在每个处理机中计算...
  • MATLAB之并行算法学习

    千次阅读 2016-05-26 10:39:38
    1.在占用时间较长的代码上进行算法的优化 2.打开MATLAB并行池使用parfor等运算 3.将循环转化为矩阵0526更新本来在做CUDA的矩阵乘法,在设计参数的时候突然想到matlab这边可以把一个循环转化成矩阵。也就是3的思想...
  • 并行程序的编程模型、运行环境、调试环境等都要比串行程序复杂...并行算法研究要以硬件,即并行计算机为依托,并行计算机性能的发挥要依靠优秀并行算法设计的实现。所以本文,并行算法研究现状及其相关问题的综述,将
  • 算法设计与分析基础

    千次阅读 2016-12-21 11:59:15
    To All Of You:一个人在接受科技教育时能得到的最珍贵的收获是能够终身受用的通用智能工具。在讨论算法的书籍中,一般会采用两种...其缺点在于,由于过于强调问题的类型,它忽略了对算法设计技术的讨论。2.第二种方
  • 求解定积分的并行算法——基于MPI

    千次阅读 2017-05-23 11:17:01
    求解定积分的并行算法——用MPI求解 1.算法思路 可以用四个基本步骤去设计一个并行程序: 1)将问题的解决方案划分成多个任务。 2)在任务间识别出需要的通信信道。 3)将任务聚合成复合任务。 4)在核上...
  • 假期突然延长,为了不荒废人生,决定趁这两天补一下课,把之前没有修过的并行与分布式计算补习一下。 这门课主要教了MPI, Pthread, OpenMP和CUDA,内容围绕着并行计算和高性能计算展开,比较繁杂,知识点很琐碎,但...
  • 数组的前缀和(Prefix Sum)问题及其并行算法

    万次阅读 多人点赞 2009-10-29 17:01:00
    前缀和(Prefix Sum)问题是在讨论并行优化算法时常常被用来作为示例的一个典型问题。对于一个输入的数组,我们所得之结果是一个等长的数组,而结果数组中的每个元素(假设是第x个元素)都是原数组中对应位置的前x项和...
  • 矩阵乘法的并行算法讨论

    万次阅读 多人点赞 2015-09-26 13:28:14
    另一方面,矩阵乘法同时也是并行计算领域常常被用来作为范例的一个话题。它的特点是首先计算量可能相当大,适合利用并行实现来提高效率。其次,它所使用的各种数据之间(矩阵中的元素)没有相互依赖性,可以充分使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,943
精华内容 38,377
关键字:

并行算法分析与设计