精华内容
下载资源
问答
  • 当2011年我从中科院毕业的时候,虽然当时已经成为了GPU并行计算领域小有名气的人物,但是我当时的心境非常不安,因为无论是在51job,还是在智联招聘上都搜索不到GPU并行计算相关的职位,甚至连并行计算相关的职位也...

    当2011年我从中科院毕业的时候,虽然当时已经成为了GPU并行计算领域小有名气的人物,但是我当时的心境非常不安,因为无论是在51job,还是在智联招聘上都搜索不到GPU并行计算相关的职位,甚至连并行计算相关的职位也查找不到,“毕业即失业”成为隐忧。而在写作本文时,我在51job和智联招聘上搜索“GPU”或CUDA时,弹出来的职位数量和内容已经非常丰富了,一些企业也开始招聘X86或ARM代码优化人员。而招聘的公司不但有百度、腾讯等一线公司,也有一些民营企业,而更多的是一些初创企业在寻找相关方向的人才。

    我想我的经历是异构并行计算在中国乃至世界发展的一个缩影:异构并行计算已经从实验室里教授们的研究对象变成了真正提高企业生产力的重要工具。

    作为一个异构并行计算这一浪潮的重度参与者,我想我有必要和大家分享我的异构并行计算算法设计方法:希望更多的读者从我的方法中借鉴与掌握应该如何设计异构并行计算算法,更希望我的方法能够促进异构并行计算在中国的进一步发展。

    1. 异构并行计算平台的差异

    在不同的应用场景下,需要满足不同要求的处理器,才能够获得最高的计算性能。在2008年以前,Intel希望通过其X86处理器架构一统天下,把其在桌面和服务器领域的成功复制到移动和嵌入式,以及图形处理。事实证明其策略是失败的:在移动处理器上,Intel出过几款处理器,也被联想等企业应用到手机中,但是市场并不买账,而今天移动处理器市场上基本上没有Intel的足迹;在嵌入式上面,Intel最近推出了爱迪生芯片,虽然爱迪生基于Intel X86架构,但是依据嵌入式应用的需求做了许多改进,但是市场依旧在观望;在图形处理器方面,Intel分别针对图形图像处理和通用计算推出了GEN架构和MIC架构,而无论是GEN架构和MIC架构都和传统的X86架构有本质区别,更明确地说:GEN和MIC已经不是X86处理器了,而是纯正的GPU。Intel的这些行为充分证明了Intel一直不愿意承认的异构并行计算的核心理念:不同的架构设计的处理器具有不同的特点,而不同的应用也具有不同的特点,应当为不同特点的应用使用不同的处理器,使用一种处理器架构满足各个不同市场的需求是痴心妄想。

    为了提高系统的性能,则必须要把应用的特点和处理器的特性相互配合,这就是协同设计。从应用的特点来看,不同的应用具有不同的需求:有的应用需要大量的访问数据;有的应用局部性很好,而有的应用局部性又很差。从不同的处理器的特点来看,不同的处理器适合做不同的事情:如X86 处理器为进行延迟优化,以减少指令的执行延迟为主要设计考量(当然今天的X86 处理器设计中也有许多以吞吐量作为设计考量的影子),编程相对简单,使用了大量的缓存,因此应用易于达到硬件的峰值性能;如NVIDIA GPU和AMD GPU则以以提高整个硬件的吞吐量为主要设计目标,在编程理念和方法上与X86体系具有许多不同。

    异构并行计算的理论和实践涉及到许多不同的内容,本节只是简介了其中比较本质内容。笔者所著的《并行算法设计与性能优化》关注并行优化和并行计算相关的基础理论、算法设计与高层次的实践经验。这本书是笔者多年经验的积累,填补了国内代码性能优化和并行计算的空白,希望对广大想要了解代码性能优化和并行化背后的理论基础的读者有所帮助。

    2. 异构并行算法的设计方面

    同一算法在不同的处理器上具有不同的性能瓶颈,这主要是因为不同的处理器的设计理念不同,应用场景也有区别,因此将不同比例的晶体管用在了不同的单元上。比如下图展示了Intel X86处理器和NVIDIA GPU的设计理念差异。

    7a996c1fdc00b2707a11f8c203c774a6.png

    Intel X86处理器将大量的晶体管用于缓存和逻辑控制,因此真正用于计算的晶体管数量反而偏少。而NVIDIA GPU只将很少的晶体管用于逻辑控制,用于缓存的比例则更少,因此能够用于计算的比例就比较高。这两种设计使得在同样数量的晶体管规模下,NVIDIA GPU所能够获得的峰值计算能力远大于X86。由于大量的晶体管用于缓存和控制逻辑,在X86上编程相对容易,简单的代码往往也能获得比较好的性能,降低了为了获得更高性能所需要的编程难度。由于不同处理器擅长做不同的事情,因此对于某个固定的算法也需要选择合适的硬件和合适的编程模型以将算法很好地映射到硬件上执行。

    对于某个具体算法的异构并行化过程,可以分成以下几个环节:

    q 为算法选择合适的硬件和编程模型,如前面所述:硬件具有不同的特性,而应用的各个部分也有不同的特点,如何选择合适的异构并行平台和编程模型以将算法的各个部分和硬件平台相匹配。

    q 将算法的不同部分划分给异构并行平台上多个处理器计算,异构平台上通常具有多种不同的处理器,每个处理器擅长的任务通常也不相同,如CPU+GPU的异构平台上,CPU适合处理逻辑复杂的计算,而GPU适合处理数据并行的计算密集型运算,如何将算法的各个部分分配给不同的处理器以获得更好的性能使我们需要考虑的一个问题。

    q 将分配给某个处理器的计算高效地映射到处理器硬件上,对于异构平台上每个处理器来说,要发挥其峰值性能需要的编程方法可能并不相同,要尽量将算法和硬件的架构细节相协调,以充分发挥硬件的性能。

    q 对算法的实现进行性能分析,如果性能不如预期,分析性能瓶颈产生在什么地方,然后依据性能瓶颈优化算法或实现,返回1,2,3修改算法设计细节,进一步提升性能,周而复始,直到算法性能达到极致。

    (1)如何选择合适的硬件和编程模型

    目前市场上的主流处理器厂商有Intel、AMD、NVIDIA和ARM等,其中Intel和AMD生产服务器和桌面使用的CPU,而AMD和NVIDIA生产桌面和服务器使用的GPU,至于ARM则主要是授权移动CPU和GPU知识产权。从硬件架构上说,Intel和AMD的X86处理器以及ARM的CPU具有许多共同点,一些性能优化思想和方法也基本类似,但是如果为了发挥硬件的峰值性能,在这几种处理器上编程还是有非常巨大的区别,比如Intel X86处理器在寄存器重命名机制和乱序执行能力上就比AMD X86处理器和ARM CPU要强很多。对NVIDIA GPU和AMD GCN(Generation Core Next)GPU来说,大多数优化方式都通用,在NVIDIA GPU上的优化在AMD GPU上也能够获得高性能。

    目前可以用于异构并行计算的编程环境主要是CUDA、OpenCL和OpenMP,其中CUDA由NVIDIA开发,经过多年发展已经比较稳定,是在NVIDIA硬件平台上进行异构计算的首选。OpenCL是一个开放的标准,已经获得了包括NVIDIA、AMD、Intel和ARM在内的许多硬件巨头的支持。为了支持更广泛的处理器,OpenCL编程相比CUDA要繁琐一些。OpenCL和CUDA的许多概念非常类似,一些完全可以互换使用,因此在两者之间转换并不难,一些公司也开发了源到源的编译器以支持将CUDA代码转化成OpenCL代码。最新的OpenMP 4标准已经加入了异构并行计算的支持,一些编译器厂商正在试图使得其编译器满足OpenMP 4标准,相信不久之后,GCC等开源的编译器都会加入OpenMP 4的支持,这样一份异构并行计算代码就可以同时在Intel、AMD和NVIDIA的处理器上编译运行,虽然OpenMP可能不能在某些异构处理器获得高性能,但是OpenCL和OpenMP混合使用能够解决这个问题。

    为了商业利益,不同的硬件厂商的库和编程工具之间并不兼容,市场上也很少有相关的参考著作。笔者所著的《并行编程方法与优化实践》关注于C程序设计语言的向量化和并行化扩展及算法到硬件的映射。此书介绍了常见的SSE/AVX/NEON SIMD指令集编程,用于GPU的异构并行编程语言CUDA、OpenCL和OpenACC,以及常见的用于多核编程的OpenMP标准。并且以稠密矩阵运算和图像处理为例,介绍了如何使用这些工具优化程序性能。想要学习这些工具的朋友,或因为项目需要学习这些工具尽快上手的同学可以参考此书。

    (2)如何在异构平台上进行任务分配

    对于一个算法的不同部分,需要选择使用最优的处理器来处理。如果算法的一部分包含有许多逻辑处理,那么最好将这部分运算交给X86处理;如果一部分包含许多数据并行处理,那么最好将这部分运算交给GPU处理;如果一部分代码对实时性要求非常高,使用FPGA处理可能是更好的选择。

    在异构平台上进行任务分配的主要难度在于:除了要考虑各个处理器的计算性能、特点外,还需要考虑多个不同的处理器之间的交互对性能的影响。在CPU+GPU的平台上,通常GPU是通过PCI-e总线连接到主板上的,因此CPU和GPU之间的通信需要通过PCI-e总线进行,这就引入了一项额外的消耗,由于PCI-e总线的带宽远小于内存带宽(PCI-e 3的实际带宽大约12 GB/s,而内存带宽以达近100 GB/s),这个消耗有的时候会成为算法性能的瓶颈。在一些情况下,将一些不太适合GPU的运算转移到GPU上可能会获得更好的性能,因为这样潜在地降低了在CPU和GPU之间进行数据传输的需求。

    在异构平台上进行任务分配是一个比较复杂的问题,这更多的是一个知识、技术和经验相互结合的难题。

    (3)任务映射

    如何将算法中的计算映射到硬件上,以便获得更好的性能,这有许多方面需要考虑,在不同的硬件中,这些考虑有相同点也有不同点,笔者以在大GPU集群中计算某个变量(这个变量可以是某个运算,比如计算矩阵乘法、从数据流中过滤一些数据等)为例,展示这些考虑。

    ① 在节点间,不同的节点需要通过网络来传输数据,通常网络带宽要比计算慢很多,故减少网络传输的损耗非常重要。常见的方法有:

    q 把算法映射到节点上,以减少数据传输的次数和总传输的数据量;

    q 数据传输的本地化:利用节点内的数据传输,减少节点间的数据传输;

    q 合并小的数据传输为大的数据传输,以减少总的数据传输次数;

    q 在数据传输的同时进行计算以掩盖节点间数据传输的消耗;

    q 提高节点间的数据传输带宽,比如使用性能更高的Infiniband网卡和交换机。

    ② 在节点内,多个GPU计算时可能需要相互传输数据,这需要通过PCI-e总线进行数据传输,NVIDIA GPU支持GPUDirect P2P技术,通过这种技术在两个GPU之间传输数据时,CPU无须参与,GPU之间的数据交换也无须通过内存中转。GPUDirect P2P技术需要主板硬件的支持,因此各个GPU如何连接到主板上也非常重要。在多个GPU间进行计算的同时,通过PCI-e总线进行数据传输,如果数据传输时间小于计算时间,数据传输时间就可以被掩盖。

    ③ 单个GPU内,如何合理地安排计算和存储器访问,以最大程度地发挥计算单元和存储器访问单元的效率。比如如何满足全局存储器的合并访问要求;如何使用共享存储器访问减少全局存储器访问次数;如何合理安排指令顺序,以减少寄存器延迟的影响。在单个GPU内,也需要在计算前通过PCI-e总线将数据传到GPU上,在计算完成后将数据传回CPU,一些GPU具备多个数据拷贝引擎,能够同时进行从CPU到GPU的数据传输和从GPU到CPU的数据传输。

    在GPU内的单个流多处理器内,如何使得流多处理器上具有足够的线程同时在执行,重叠访存和计算,以计算掩盖访存的延迟,这更考验软件开发人员的智慧、经验和知识。

    从流多处理器到集群中的多个GPU,这是一个从小到大的层次,在实际工作中,笔者通常进行从小到大的设计,在小的层次上解决问题,再将算法扩展到大的,解决问题后再向更大的层次扩展。

    (4)性能分析

    在某个具体的硬件上实现算法后,需要评估其性能,找到其性能瓶颈,找到其性能瓶颈后,再重新审视算法的设计,以确定是否需要更改算法以更好地映射到硬件上,以去除性能瓶颈,周而复始以使得算法的性能达到最优。在一些情况下,评估性能后可能发现算法并不适合在当前的异构平台上执行,此时可能需要换一种异构平台配置。

    无论是Intel、AMD,还是NVIDIA,它们都提供了丰富的软件来分析运行在其硬件上的程序性能,比如Intel的Vtune工具,AMD的CodeXL工具和NVIDIA的Nsight工具,关于这些工具笔者就不介绍了,感兴趣的读者可以参考官方介绍或手册。

    3. 异构并行计算的应用场景

    异构并行已经走出实验室,正在产业界得到越来越广泛的应用,除了超算中心的传统科学计算之外,异构并行计算还在油气勘探、图像处理、大数据处理和深度学习领域获得重视,并且还在越来越多的领域生根发芽。

    图像处理是GPU的传统优势领域,由于大多数图像处理算法具有数据并行的特征,因此非常适合向量处理器进行向量处理。目前X86、ARM和GPU都已经广泛应用在图像处理领域。

    在油气勘探领域,超级计算机被大量用来模拟地下物理结构,以推测是否有石油或天然气。油气勘探领域的主要计算是偏微分方程求解和傅立叶变换。对于偏微分方程求解,通过差分方法可转化成两类问题:一类是递推迭代;一类是线性方程求解。由于需要模拟大区域的情况和差分方法的运用,通常这两类问题都具有非常好的并行性,非常适合CPU+GPU的异构平台。

    在深度学习应用领域,现在开源的深度学习平台(如caffe, theano)都支持GPU的训练,如Google、Facebook、百度、腾讯、阿里都在开发各自的深度学习平台。可以毫不讳言地说:GPU硬件已经是深度学习训练平台的标准配置。

    大数据处理中需要从海量数据中寻找特殊的模式,这也是异构并行计算的用武之地。许多大数据创业公司使用GPU来分析数据,从中找出有用的信息。

    笔者所著的《科学计算与企业级应用的并行优化》介绍了如何将线性代数、偏微分方程求解、分子动力学和机器学习领域的常见算法良好地在X86和GPU平台上实现出来,希望能够帮助从事这些领域的朋友提高职业技能。

    展开全文
  • 并行计算模型及其算法设计,并行计算模型及其算法设计
  • 并行计算复习第二篇 并行计算理论基础:并行算法设计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流水线编程实例

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

    展开全文
  • 第一部分 并行计算的基础 第1章 并行计算的研究目标 第2章 并行计算机系统及其结构模型 第3章 当代并行机系统:SMP、MPP和Cluster 第4章 并行计算性能评测 第二部分 并行算法设计 第5章 并行算法设计基础 第6...
  • 通过对电网通讯结构的分析,确定了并行程序的设计方法,基于Matlab对并行计算机算法下的电网暂态过程进行数值模拟,结果表明,电网系统的电压、功率及转子角速度的变化幅度较小而且平稳,系统稳定性较高。
  • 并行算法设计

    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版)》是并行计算系列丛书之开篇,它以并行计算为主题,围绕并行计算机、并行算法和并行程序设计展开讨论,强调融并行计算机体系结构、数值与非数值并行算法设计以及并行程序...
  • Y.Xu Copyright USTC Parallel algorithms * / Ch6 Parallel Algorithms * / Ch6 Y.Xu Copyright USTC Parallel algorithms * / Ch6 Y.Xu Copyright USTC * Parallel Algorithms Chapter 6 Parallel Search * Y.Xu C
  • Y.Xu Copyright USTC Parallel Algorithms * / Ch13 Parallel Algorithms * / Ch13 Y.Xu Copyright USTC Parallel Algorithms * / Ch13 Y.Xu Copyright USTC * Parallel Algorithms Chapter 13 Numerical Algorithms
  • 并行计算机组成与设计 内容简介《并行计算机组成与设计》以简单易懂的方式讲解错综复杂的并行体系结构,引导读者了解并行计算机的工作原理,同时鼓励读者创新并实现自己的设计。全书共9章,内容涵盖底层电子工艺、微...

    并行计算机组成与设计 内容简介

    《并行计算机组成与设计》以简单易懂的方式讲解错综复杂的并行体系结构,引导读者了解并行计算机的工作原理,同时鼓励读者创新并实现自己的设计。全书共9章,内容涵盖底层电子工艺、微体系结构、存储结构、互连网络、多处理器、片上多处理器以及量化评估模型等。每一章都独立且完备,既包含全面的基本概念,也涵盖一些前沿研究点。本书适合作为高等院校计算机相关专业的教材,教师可根据课程及学生的层次选取不同的主题。同时,对于工程师和研究者,本书也是不可多得的有益参考。

    并行计算机组成与设计 目录

    第1章 总述

    1.1 什么是计算机体系结构

    1.2 并行体系结构的基本组成

    1.2.1 处理器

    1.2.2 存储

    1.2.3 互连

    1.3 并行体系结构

    1.3.1 指令级并行

    1.3.2 线程级并行

    1.3.3 向量和阵列处理器

    1.4 性能

    1.4.1 基准测试集

    1.4.2 Amdahl定律

    1.5 技术挑战

    1.5.1 功耗和能量

    1.5.2 可靠性

    1.5.3 连线延迟

    1.5.4 设计复杂度

    1.5.5 尺寸缩小极限和CMOS终点

    习题

    第2章 工艺及其影响

    2.1 概述

    2.2 电学基本定律

    2.2.1 欧姆定律

    2.2.2 电阻

    2.2.3 电容

    2.3 MOSFET晶体管和CMOS反相器

    2.4 工艺变更

    2.5 功耗和能耗

    2.5.1 动态功耗

    2.5.2 静态功耗

    2.5.3 功耗和能量指标

    2.6 可靠性

    2.6.1 故障和错误

    2.6.2 可靠性指标

    2.6.3 故障率和老化

    2.6.4 瞬时故障

    2.6.5 间歇性故障

    2.6.6 永久性故障

    2.6.7 工艺偏差及其对故障的影响

    习题

    第3章 处理器微结构

    3.1 概述

    3.2 指令集架构

    3.2.1 指令类型和操作码

    3.2.2 指令混合

    3.2.3 指令操作数

    3.2.4 异常、陷阱和中断

    3.2.5 存储一致性模型

    3.2.6 本书的核心ISA

    3.2.7 CISC和RISC

    3.3 静态调度流水线

    3.3.1 经典五级流水线

    3.3.2 指令乱序完成

    3.3.3 超流水和超标量CPU

    3.3.4 分支预测

    3.3.5 静态指令调度

    3.3.6 静态流水线的优缺点

    3.4 动态调度流水线

    3.4.1 解决数据相关:Tomasulo算法

    3.4.2 推测执行

    3.4.3 动态分支预测

    3.4.4 支持推测的Tomasulo算法

    3.4.5 动态内存歧义消除

    3.4.6 显式寄存器重命名

    3.4.7 指令发射后的寄存器读取

    3.4.8 推测指令调度

    3.4.9 打破数据流限制:值预测

    3.4.10 单周期多指令

    3.4.11 处理复杂ISA

    3.5 超长指令字微结构

    3.5.1 动态和静态技术

    3.5.2 VLIW体系结构

    3.5.3 循环展开

    3.5.4 软件流水

    3.5.5 非循环VLIW调度

    3.5.6 谓词指令

    3.5.7 推测内存歧义消除

    3.5.8 异常

    3.6 EPIC微结构

    3.7 向量微结构

    3.7.1 算术/逻辑向量指令

    3.7.2 内存向量指令

    3.7.3 向量分段开采和链接

    3.7.4 条件语句

    3.7.5 scatter和gather操作

    习题

    第4章 存储层次

    4.1 概述

    4.2 金字塔形存储层次

    4.2.1 访存局部性

    4.2.2 存储层次中的一致性

    4.2.3 存储包含

    4.3 cache层次

    4.3.1 cache映射及组织方式

    4.3.2 替换策略

    4.3.3 写策略

    4.3.4 cache层次的性能

    4.3.5 cache失效的分类

    4.3.6 非阻塞cache

    4.3.7 cache预取和预加载

    4.4 虚拟存储

    4.4.1 引入虚存的动机

    4.4.2 从操作系统视角看到的虚拟存储

    4.4.3 虚地址转换

    4.4.4 访存控制

    4.4.5 多级页表

    4.4.6 反向页表

    4.4.7 旁路转换缓冲

    4.4.8 带物理标识的虚地址cache

    4.4.9 带虚标识的虚地址cache

    习题

    第5章 多处理器系统

    5.1 概述

    5.2 并行编程模型

    5.2.1 共享内存系统

    5.2.2 消息传递系统

    5.3 基于消息传递的多处理器系统

    5.3.1 消息传递原语

    5.3.2 消息传递协议

    5.3.3 消息传递协议的硬件支持

    5.4 基于总线的共享内存系统

    5.4.1 多处理器cache组织

    5.4.2 一个简单的侦听cache协议

    5.4.3 侦听cache协议的设计空间

    5.4.4 协议变种

    5.4.5 多阶段侦听cache协议的设计问题

    5.4.6 通信事件的分类

    5.4.7 TLB一致性

    5.5 可扩展共享内存系统

    5.5.1 目录协议的基本概念和术语

    5.5.2 目录协议实现方法

    5.5.3 目录协议的扩展性

    5.5.4 层次化系统

    5.5.5 页面迁移和复制

    5.6 全cache共享内存系统

    5.6.1 基本概念、硬件结构和协议

    5.6.2 平坦COMA

    习题

    第6章 互连网络

    6.1 概述

    6.2 互连网络的设计空间

    6.2.1 设计概念综述

    6.2.2 延迟和带宽模型

    6.3 交换策略

    6.4 拓扑结构

    6.4.1 间接网络

    6.4.2 直接网络

    6.5 路由技术

    6.5.1 路由算法

    6.5.2 死锁避免和确定性路由

    6.5.3 放松路由限制:虚通道和转弯模型

    6.5.4 进一步放松的路由算法:自适应路由

    6.6 交换架构

    习题

    第7章 一致性、同步与存储一致性

    7.1 概述

    7.2 背景

    7.2.1 共享内存通信模型

    7.2.2 硬件组件

    7.3 一致性和store原子性

    7.3.1 多处理器一致性的实现困难

    7.3.2 cache协议

    7.3.3 store原子性

    7.3.4 纯一致性

    7.3.5 store原子性和访存交错

    7.4 顺序一致性

    7.4.1 顺序一致性的形式化模型

    7.4.2 顺序一致性的访存顺序规则

    7.4.3 入站消息管理

    7.4.4 store同步性

    7.5 同步

    7.5.1 基本同步原语

    7.5.2 基于硬件的同步

    7.5.3 基于软件的同步

    7.6 放松的存储一致性模型

    7.6.1 不依赖于同步的放松模型

    7.6.2 依赖同步的放松模型

    7.7 推测执行中的存储序违反

    7.7.1 乱序执行处理器中的保守存储模型

    7.7.2 推测执行中的存储序违反

    习题

    第8章 片上多处理器

    8.1 概述

    8.2 CMP的基本原理

    8.2.1 技术趋势

    8.2.2 机遇

    8.3 核内多线程

    8.3.1 软件支持的多线程

    8.3.2 硬件支持的多线程

    8.3.3 块式(粗粒度)多线程

    8.3.4 交错(细粒度)多线程

    8.3.5 乱序执行处理器上的同时多线程

    8.4 片上多处理器架构

    8.4.1 同构CMP架构

    8.4.2 基于异构处理器核的CMP系统

    8.4.3 连体处理器核

    8.5 编程模型

    8.5.1 独立进程

    8.5.2 显式线程并行

    8.5.3 事务内存

    8.5.4 线程级推测执行

    8.5.5 帮助线程

    8.5.6 通过冗余执行提高可靠性

    习题

    第9章 量化评估

    9.1 概述

    9.2 模拟器分类

    9.2.1 用户级模拟器和全系统模拟器

    9.2.2 功能模拟器和时钟精确模拟器

    9.2.3 trace驱动模拟器、执行驱动模拟器和直接执行模拟器

    9.3 模拟器的集成

    9.3.1 功能优先模拟器的集成

    9.3.2 时序优先模拟器的集成

    9.4 多处理器模拟器

    9.4.1 串行多处理器模拟器

    9.4.2 并行多处理器模拟器

    9.5 功耗和热量模拟

    9.6 工作负载采样

    9.6.1 基于采样的微架构模拟

    9.6.2 SimPoint

    9.7 工作负载特征刻画

    9.7.1 理解性能瓶颈

    9.7.2 合成基准测试程序

    9.7.3 预测工作负载行为

    习题

    附录

    并行计算机组成与设计 精彩文摘

    1.1 什么是计算机体系结构

    计算机体系结构是一门工程或应用科学学科,它主要研究如何在给定的工艺限制和软件要求下设计更好的计算机。过去计算机体系结构是指令集设计的代名词,然而随着时间的推移,该术语已经涵盖了计算机的硬件组成、微处理器乃至硬件组件级别的整个系统的设计。本书中,我们采用了默认的“计算机体系结构”的现代定义,即“计算机硬件组成和计算机设计”,在提到指令集时,我们将明确地使用术语“指令集架构”(简称ISA)。从指令集的设汁发展历史可以看出,指令集是非常稳定的,现在只有少数忉为工业界所支持,虽然目前的指令集可能会不断扩展,但从头开始设计新的指令集是几乎不可能的,因为开发一个全新的指令集并进行实现的成本无疑非常巨大。本书中,我们将粗略地介绍指令集架构,因为这不是我们的主要目标,我们的主要目标是在给定成本和工艺限制下快速、正确地实现指令集架构的并行计算机体系结构。

    c2a685211f6de3a7a80b36cce15d73bb.png

    展开全文
  • 冯-诺依曼计算机是一个理想的通用串行计算机模型,但是对并行计算来说,到...并行计算模型:从并行算法设计和分析出发,将各种并行计算机(至少是某一类)的基本特征抽象出来,形成一个抽象的并行计算模型。 并行...
  • 并行算法设计基础

    2019-07-05 22:31:56
    并行算法的定义和分类 并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。 并行算法分类 数值计算与非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法 ...
  • 全书共分二十章,主要内容包括:并行算法基础,并行算法的基本设计技术,各种计算模型上的计算机领域中诸多常用计算问题的并行算法设计和分析方法,最后还讨论了各种并行计算模型的能力、限制、等价性以及与并行...
  • 并行算法设计与性能优化,刘文志等著,影印版本,搞并行计算的小伙伴必备

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,282
精华内容 512
关键字:

并行计算算法设计