多核结构与程序设计 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系.

Presentation on theme: "多核结构与程序设计 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系."— Presentation transcript:

1 多核结构与程序设计 杨全胜 东南大学成贤学院计算机系

2 并行计算基础 内容 什么是并行计算 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法

3 什么是并行计算 传统的软件是为串行计算机而编写的: 在只有一个处理器的单台计算机上运行 把一个问题分解成离散的指令序列
指令被一条条的顺序执行 任何时候只有一条指令在执行

4 什么是并行计算 并行计算是同时使用多个计算资源来解决计算问题 使用多个CPU或核来运行 把一个问题分解成几个离散的部分，从而能够同时解决
每个部分更进一步地分解成离散的指令序列 每个部分的指令在不同的CPU或核上同时执行

5 什么是并行计算 组成并行计算机的各个部分： 节点（node） 互联网络（interconnect network） 内存 （memory）
内存模块位于节点内部 内存模块与节点分离

6 并行计算基础 内容 什么是并行计算 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法

7 弗林经典分类 弗林根据指令和数据这两个独立维度的情况，对多处理器计算机结构进行了如下分类 SISD 单指令流单数据流 SIMD
单指令流多数据流 MISD 多指令流单数据流 MIMD 多指令流多数据流

8 弗林经典分类 单指令流单数据流(SISD) 一个串行(非并行)计算机 单指令流: 在任何一个时钟周期，CPU中只有一个指令流在活动。
单数据流: 在任何一个时钟周期，只有一个数据流作为输入在被使用。 执行结果是确定的 从很早一直到现在，这都是计算机的最主要的形式。

9 弗林经典分类 单指令流多数据流(SIMD) 并行计算机的一种 单指令流: 在任何一个时钟周期，CPU中只有一个指令流在活动。
多数据流: 每个处理单元能在不同的数据元素上进行操作。 最适合具有高度规律性的特殊的问题，比如图像处理。 同步（步调一致）和确定的执行 两种类型: 处理器阵列和向量流水线

10 弗林经典分类 多指令流单数据流 (MISD) 单一的数据流流入多个处理器单元去处理 每个处理器单元通过独立的指令流对数据进行处理
这种类型的并行计算机很少有存在的例子，有一个实验室的产品是卡内基梅陇大学的C.mmp计算机 (1971)。 一些想象中的可能应用： 多种频率的滤波器处理同一个信号流 用多个密码算法尝试解开一个编码信息。

11 弗林经典分类 多指令流多数据流 (MIMD) 目前最常用的并行计算机。大多数现代计算机属于这一类 多指令流: 每个处理器可以执行不同的指令流
多数据流: 每个处理器可以工作在不同的数据流上 执行可以是同步的或者异步的，确定的或者不确定的 举例: 很多目前的巨型计算机、网络并行计算机“网格”、多处理器SMP计算机以及多核处理器。

12 并行计算基础 内容 什么是并行计算 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法

13 并行计算机存储结构 多级存储体系结构 为了解决存储墙（memory wall）性能瓶颈问题。
在节点内部的cache称为二级cache（L2 cache）。 在处理器内部更小的cache成为一级cache(L1 cache) L1 cache连接CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中。

14 并行计算机存储结构 多级存储体系结构 Cache的映射策略指的是内存块和cache行之间如何建立相互映射关系。
直接映射策略（direct mapping strategy） 每个内存块只能被唯一的映射到一条cache行中 K－路组相联映射策略 （K-way set association mapping strategy） Cache被分解为V个组，每个组由K个cache行组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一个cache行。 全相联映射策略 （full association mapping strategy） 内存块可以被映射到cache中的任意一个cache行。

15 并行计算机存储结构 分布式存储 MEMORY NODE MEMORY NODE MEMORY NODE MEMORY NODE
network MEMORY NODE MEMORY NODE NODE（节点） = 单处理器或多处理器

16 并行计算机存储结构 分布式存储-NORMA (No-Remote Memory Access)
节点有它们自己的局部存储器。一个节点内的存储器地址不会映射到其他节点上，所以在全部节点中没有全局地址空间的概念。 因为每一个节点有它自己局部存储器它们独立地操作。因此Cache一致性的概念不存在。 当一个节点需要存取另一个节点的数据（很少见），通常要程序员明确提供如何以及何时数据被传送的信息。

17 并行计算机存储结构 分布式存储 优点 缺点 增加节点数，就自然成比例地增加了存储容量.
每个节点能快速地存取它自己的存储器而无需干涉也没有试图保持Cache一致性的开销。 成本效率: 可以用商业化的，现成的处理器和网络。 缺点 如果数据在两个节点间传送，就要求程序员提供很多有关数据传送的细节。 很难将现在基于全局存储的已有数据结构映射到这种存储组织中。 非均匀内存访问(NUMA) 时间 off-the-shelf :现货供应;不用定制的，成品

18 并行计算机存储结构 共享存储 NODE MEMORY NODE NODE NODE NODE（节点） = 单处理器或多处理器

19 并行计算机存储结构 共享存储 共享存储的并行计算机千差万别，但都能够使所有的节点以全局地址空间的形式访问全部的存储器空间。
多个节点可以独立操作但又可共享相同的存储资源。 在一个节点上改变一个存储位置的值对其他节点来说也是可见和可用的。

20 并行计算机存储结构 共享存储 均匀存储访问(UMA): 存储器和节点分离 物理存储器能够通过互联网络被所有节点共享。
发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等； 外围I/O设备也可以共享，且每个节点有平等的访问权利。 最常见的代表是当前的对称多处理器机器 (SMP)

21 并行计算机存储结构 共享存储 均匀存储访问(UMA): 所有节点访问任意存储单元的时间相同； 各节点的CPU可带有局部私有高速缓存；
互联网络可以是单总线、多总线或者交叉开关。 有时候称为CC-UMA – Cache一致性UMA. Cache一致性意味着如果一个处理器修改了共享存储器中的某个位置的数，其他的所有处理器都知道这个改变。Cache的一致性在硬件一级完成。

22 并行计算机存储结构 分布式共享存储器(DSM) NODE NODE MEMORY MEMORY network NODE NODE

23 并行计算机存储结构 分布式共享存储器(DSM)
共享存储器部分通常是一个Cache一致性的SMP机器。在给定的SMP中的处理器，能够以全局方式寻址这个机器的存储器。 分布式存储部分是多个SMP联网。SMP只知道它们自己的存储器-不是在其他SMP上的存储器。因此，需要网络通信来将数据从一个SMP移动到另一个。 目前的趋势似乎表明这种类型的存储结构将继续盛行，并将在高端计算机上得到增强。

24 并行计算机存储结构 分布式共享存储器(DSM) 非均匀存储访问(NUMA) 每个节点都有共享存储的一部分（局部存储器）
存储器只有一个地址空间 任何节点都可以实际地址直接访问任何存储器 每个节点都可以有局部Cache 不是所有的节点能够以相同的时间访问所有的存储器，访问时间与该存储器到该节点的距离有关。 跨链接的存储访问比较慢 如果保持Cache一致性，它也可以称为CC-NUMA – Cache一致性NUMA 分布式共享结构

25 并行计算机存储结构 分布式共享存储器 全高速缓存存储访问 (COMA):
每个节点拥有共享存储的一部分。然而，这次共享存储器是由Cache组成的。 没有层次性存储，地址空间是针对Cache的。 有一个Cache目录来帮助远程Cache访问。 需要将数据转移到需要它的节点上。

26 并行计算机存储结构 分布式共享存储器 优点 缺点 全局地址空间提供一个用户友好的访存编程方式。 由于节点与内存接近，任务间的数据共享快速统一
增加一些节点会使得存储器到节点的路径的拥挤程度成几何增大。 对于cache一致性系统，增加更多的节点会使得与cache/存储器管理相关联的冲突成几何增长。 程序员的责任就是能确保全局存储的正确访问的同步结构。

27 并行计算基础 内容 什么是并行计算机 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法

28 并行编程模型 共享存储模型 在共享存储编程模型里，任务共享一个共用的地址空间，它们在这个共享空间进行异步的读写。
像“锁/信号量”这样不同的机制将会用来控制对共享存储的访问。 从程序员的观点，这种模式的好处是没有数据所有权的概念，因此没必要在任务之间明确地规定数据通信。程序开发通常会比较简单。 一个重要的性能上的缺点是理解和管理局部的数据变得更加困难。

29 并行编程模型 共享存储模型 实现 在共享存储平台，本地编译程序将用户程序变量翻译成全局存储空间中实际的存储地址。
目前没有公共的分布式存储平台的实现。然而，KSR ALLCACHE近似地提供了一个数据的共享存储，尽管数据在物理上是分布的。

30 并行编程模型 线程模型 在并行编程的线程模型中，一个单独的进程，可以有多个并发的执行路径。 线程一般和共享存储结构与操作系统有关
Perhaps the most simple analogy that can be used to describe threads is the concept of a single program that includes a number of subroutines: The main program a.out is scheduled to run by the native operating system. a.out loads and acquires all of the necessary system and user resources to run. a.out performs some serial work, and then creates a number of tasks (threads) that can be scheduled and run by the operating system concurrently. Each thread has local data, but also, shares the entire resources of a.out. This saves the overhead associated with replicating a program's resources for each thread. Each thread also benefits from a global memory view because it shares the memory space of a.out. A thread's work may best be described as a subroutine within the main program. Any thread can execute any subroutine at the same time as other threads. Threads communicate with each other through global memory (updating address locations). This requires synchronization constructs to insure that more than one thread is not updating the same global address at any time. Threads can come and go, but a.out remains present to provide the necessary shared resources until the application has completed.

31 并行编程模型 线程模型 从程序的观点，线程的实现通常包括： 这两种情况下，程序员都要负责决定所有的并行操作。
在并行程序中被调用的一个子程序库 嵌入到串行或并行代码中的一组编译指导语句。 这两种情况下，程序员都要负责决定所有的并行操作。 有两个完全不同的线程实现：POSIX Threads 和 OpenMP.

32 并行编程模型 线程模型 POSIX Threads 基于库的; 需要并行程序代码
遵循IEEE POSIX c 标准 (1995). 只支持C语言 通常使用Pthreads. 现在大多数硬件供应商除了他们自己的线程实现外，还提供Pthreads的支持 非常明显的并行；需要程序员注意细节。

33 并行编程模型 线程模型 OpenMP 基于编译器指导 用串行代码写程序，然后指导OpenMP将其并行化
由一帮主要的软件和硬件厂商共同定义和支持。 OpenMP Fortran API 1997年10月28日发布。 C/C++ API 在1998年后期发布。 便携式/多平台。包括Unix和Windows NT平台 提供C/C++和Fortran实现 能够非常容易和简单地被使用——提供“增量并行”

34 并行编程模型 消息传递模型 一组任务在计算的时候使用它们自己的局部存储器。多个任务可以驻留在同一台机器，或者跨任意数量的机器。
任务之间通过发送和接受消息的数据通信来交换数据。 数据传送通常需要每个进程协同操作来完成。比如一个发送操作必须有一个对应的接收操作。

35 并行编程模型 消息传递模型 实现: 1992年, MPI（消息传递接口）论坛成行，其主要目标是制定消息传递实现的标准接口
MPI现在是实际上的消息传递的工业标准，实际上替代了所有其它的用于生产工作的消息传递实现。大多数并行平台会提供至少一个MPI的实现。少数还提供完整的MPI-2的实现。 对于共享存储结构，MPI通常实现的时候不用网络进行任务通信。它通常处于性能的考虑，用共享存储（存储器拷贝）来实现。

36 并行编程模型 数据并行模型 大多数并行工作都是在一个数据集中去完成。数据集通常组织成一个共同的结构，比如数组或者多维数组。
一组任务共同地工作在相同的数据结构，然而每个任务工作在这个数据结构的不同部分。 任务用相同的操作执行它那部分工作，比如“给每个数组元素加4。”

37 并行编程模型 数据并行模型 在共享存储结构，所有的任务可以通过全局存储器来访问数据结构。
在分布式存储结构中，数据结构是分散的，并以“组块”的方式存在于每个任务的局部存储器中。

38 并行编程模型 数据并行模型 实现 高性能Fortran (HPF): 将Fortran 90扩展，支持数据并行的程序设计
增加了指导编译器如何分布数据的功能 增加了能够改进生成代码优化的功能 增加了数据并行的结构(现在是Fortran 95的一部分) 编译器指导语句: 允许程序员指定数据的分布和对齐。Fortran 实现是最常见的并行平台。 这种模式的分布式存储实现通常由编译器转换程序到标准代码来调用消息传递库（通常是MPI）去分布数据到所有处理器。所有的消息传递对程序员是透明的。

39 并行计算基础 内容 什么是并行计算 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法

40 并行程序设计相关问题 人工并行化 程序员通常要负责识别和实际地实现并行。 很多时候，手工开发并行代码是费时、复杂、易错和反复的过程.

41 并行程序设计相关问题 自动并行化 全自动 程序员指导 编译器分析源代码并标识并行的时机
分析包括:识别不能并行的部分;是否用并行来实际地提高性能;并行带来的可能的成本代价。 循环(do, for)是自动并行化最常见的目标。 程序员指导 使用“编译器指导语句”或者可能地编译器标志，程序员明确地告诉编译器如何并行化代码。 也许能和一定程度的自动并行化一起使用。

42 并行程序设计相关问题 自动并行化 问题 可能会产生错误的结果 性能实际上可能会降低 比人工并行化的灵活性差 受限于代码的子集（主要是循环）
如果分析的结果建议不能并行化，或者代码太复杂，就有可能不对代码进行并行化 很多自动并行的工具是为Fortran开发的

43 并行程序设计相关问题 开发并行软件的步骤 首先，理解你想用并行来解决的目标问题 确定这个问题是不是真的可以并行化
问题是否足够大，充分理解问题中的关键特征 确定这个问题是不是真的可以并行化 任务是否可以划分为不同的功能模块 多个不同文件的同时上传和下载。 需要处理的数据是否可以被划分为若干数据子集 计算上千个独立的分子构造的势能 一个大文件的下载 一个复杂的过程是否可以被划分为若干个子操作流水执行 成批图像输入、处理、输出的问题 使用公式F(k + 2) = F(k + 1) + F(k)计算斐波拉契数列(1,1,2,3,5,8,13,21,...) (可否并行化？)

44 并行程序设计相关问题 开发并行软件的步骤 标识程序的热点
知道哪才是真正在做的实际的工作。大多数科学和技术的程序中通常只有很少的一部分是在完成它们的大部分工作。 关注那些热点地方的并行化，而忽略那些很少使用CPU的程序段。 Profilers（剖析工具）和性能分析工具可以有所帮助

45 并行程序设计相关问题 开发并行软件的步骤 标识程序中的瓶颈 标识不可并行化的部分。一个常见的不可并行化的类型是数据依赖。
是不是有什么地方显得出奇的慢，或者引起并行化工作停止或延迟？ 也许可以重构造程序或者使用不同的算法来减少或避免不必要的执行又慢的区域 标识不可并行化的部分。一个常见的不可并行化的类型是数据依赖。 如果可能的话，研究其他的算法。当设计一个并行应用程序的时候，这可能是最重要的一个考虑因素。

46 并行程序设计相关问题 分解的方法 将问题分解成能分布到多个任务中的离散的“块组” 有两个在并行任务间划分计算工作的方法
功能分解（任务分解）：问题根据必须完成的工作被分解。每个任务完成全部工作的一部分。 数据分解（域分解）：与问题相关的数据被分解。每个并行任务工作在分配给它的部分数据上。 数据流分解：将一个复杂的过程划分成多个任务，这些任务按照某种顺序执行。 生产者-消费者问题

47 并行程序设计相关问题 同步的类型: 栅障(Barrier) 通常涉及到所有的任务，在它们的执行路径上有一个统一的“暂停点”称为栅障
每个任务完成它的工作直到到达栅障的位置就停下来或者被阻塞。 当最后一个任务到达栅障时，所有的任务被同步。 从栅障开始会发生什么是不同的。通常任务串行的部分必须被执行。其他情况下，任务自动地放开继续他们的工作。 栅栏（Barrier栅障） :一组线程可以使用栅栏来进行共同的相互同步。组中的每个线程各自执行，直到到达栅栏，就阻塞在那里。在所有相关线程到达栅栏后，它们就全部继续它们的执行。就是说，它们一个接一个地阻塞，等待其他的线程到达栅栏；一旦所有线程都到达了它们的执行路径中的“栅栏点”，它们就一起重新启动。

48 并行程序设计相关问题 同步的类型: 锁/信号量 可能涉及任意数量的任务
通常用于串行地（保护地）访问全局数据或者代码 段。在每个时刻只有一个任务能使用锁/信号量/标 志 第一个任务请求锁并“set”锁，之后该任务就能 安全地访问被保护的数据和代码。 其他任务也能请求锁，但是必须等到获得锁的任务 释放锁以后才能去获得锁。 可以是阻塞或者非阻塞

49 并行程序设计相关问题 同步的类型: 同步通信操作 只涉及那些执行通信操作的任务
当一个任务执行一个通信操作，需要与其他参加通信的任务进行某种形式的协调。比如，在一个任务能执行发送操作之前，它必须收到一个来自接收任务的回应信号说它已经准备好。

50 并行程序设计相关问题 时间依赖和数据依赖 当语句的执行顺序影响到程序的结果的时候，我们说程序的语句之间存在时间依赖（时间相关）。
数据依赖 产生于不同任务对存储中相同位置数据的多个使用。也称为数据相关。 依赖对于并行程序设计是很重要的，因为它们是最基本的阻止并行的因素之一。

51 并行程序设计相关问题 数据依赖 循环引起的数据依赖 for (i = 1;i<100;i++) a[i] = a[i-1]*32
循环独立但数据是依赖的 task task X = X = Y = X^2 Y = X^3 Loop carried data dependence The value of A(J-1) must be computed before the value of A(J), therefore A(J) exhibits a data dependency on A(J-1). Parallelism is inhibited. If Task 2 has A(J) and task 1 has A(J-1), computing the correct value of A(J) necessitates: Distributed memory architecture - task 2 must obtain the value of A(J-1) from task 1 after task 1 finishes its computation Shared memory architecture - task 2 must read A(J-1) after task 1 updates it Loop independent data dependence As with the previous example, parallelism is inhibited. The value of Y is dependent on: Distributed memory architecture - if or when the value of X is communicated between the tasks. Shared memory architecture - which task last stores the value of X.

52 并行程序设计相关问题 数据依赖 如何处理数据依赖: 分布式存储结构- 通信要求数据在同步点上。 共享存储结构-在任务间采用同步“读/写”操作

53 并行程序设计相关问题 负载均衡 负载均衡 是指在任务之间分发工作的方法，该方法要所有的任务在所有的时候保持忙
负载均衡对于并行程序的性能是很重要的。 Load balancing is important to parallel programs for performance reasons. For example, if all tasks are subject to a barrier synchronization point, the slowest task will determine the overall performance.

54 并行程序设计相关问题 如何获得负载平衡 相等地划分每个任务所接受的工作 对于数组和矩阵操作每个任务完成相似的工作，在任务间均衡地分布数据集。
对于循环迭代，让每次迭代的工作相似，在任务间均衡地分布迭代。 如果使用不同性能特性的不同机制的混合，确定使用一些性能分析工具来发现任何负载的不均衡，并相应调整工作。

55 并行程序设计相关问题 如何获得负载平衡 使用动态工作指派 即使数据在任务间均衡分布，有些类型的问题依然会引起负载不均衡
当任务要执行的工作量是变化的，或者是不可预测的时候，使用一个诸如任务池的调度器是有帮助的。每个任务完成自己的工作后，从队列中获得新的工作 可能有必要设计一个算法来检测和处理在代码中动态发生的负载不均衡问题。 Certain classes of problems result in load imbalances even if data is evenly distributed among tasks: Sparse arrays - some tasks will have actual data to work on while others have mostly "zeros". Adaptive grid methods - some tasks may need to refine their mesh while others don't. N-body simulations - where some particles may migrate to/from their original task domain to another task's; where the particles owned by some tasks require more work than those owned by other tasks.

56 并行计算基础 内容 什么是并行计算 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法

57 程序性能优化方法 性能评估 Amdahl定律

58 程序性能优化方法 性能评估 Amdahl定律
程序潜在的加速(speedup)是用的可并行的那部分code(P)来定义的 Sspeedup = 1/(1-P) 如果代码没有任何部分可并行，P = 0 并且 speedup = 1 (没有加速). 如果所有的代码都可以并行，P = 1 并且speedup是无穷 (理论上). 如果一半的代码可以并行化，则最大的speedup = 2, 意味着代码会以2倍的速度执行。

59 程序性能优化方法 性能评估 Amdahl定律
引入执行并行部分工作的处理器的个数，这时P = 并行部分, N = 处理器个数并且 T = 串行部分=1-P, 上述公式可以改成:

60 … 程序性能优化方法 串行程序性能优化 调用高性能的库函数，比如BLAS，FFTW等. 是用合适的编译器优化选项。 合理定义数组维数
int a[m][n]; for(i=0,i<M,i++) a[i][j]=… //n和S是什么关系比较好？ C语言中的数组是行主序的 教材P54 合理定义数组维数 现代计算机的存储结构多为多体交叉的并行存储结构（包括组相联的Cache），数据会在统一编址的情况下以字为单位交替分布在不同存储体中，因此进行连续数据访问的时候应该使得地址增量与内存体数的最大公约数尽量小，要避免地址增量刚好是存储体数的整数倍，这样会刚好集中在一个存储体中。比如，假设内存访问的字长为4个字节，内存体数为S，则对于2维数组 int a[M][N]来说，当我们对数组第一维进行顺序访问时（C语言是按行存放）， for(i=0,i<M,i++) a[i][j]=… 数据的增量是第二维的维数N，如果N是S的整数倍时，则所访问的数据会集中在一个存储体中。如果N和S不是这种关系，则数据会分布在不同存储体中。通常，万一N是S 倍数，则可以采用为数组增加一个边的方法，即定义数组为a[M][N+1]

61 程序性能优化方法 哪个好？ 嵌套循环的顺序对于数据访问的局部性是很重要的 int a[128][40960];
int b[128][40960]; for(int i=0;i<128;i++) { for(int j=0;j<40960;j++) a[i][j] = b[i][j]; } for(int i=0;i<40960;i++) for(int j=0;j<128;j++) a[j][i] = b[j][i]; 哪个好？ 嵌套循环的顺序对于数据访问的局部性是很重要的 嵌套循环的顺序对于数据访问的局部性是很重要的. int a[128][40960]; int b[128][40960]; for(int i=0;i<128;i++) { for(int j=0;j<40960;j++) a[i][j] = b[i][j]; } for(int i=0;i<40960;i++) for(int j=0;j<128;j++) a[j][i] = b[j][i]; 哪个好，为什么？ C语言中的数组是行主序的，即a[r][c]在内存中是这样放的，a[0][0]a[0][1]...a[0][c-1]a[1][0]a[1][1]...a[c-1] 所以1比2好

62 程序性能优化方法 哪个好？ 嵌套循环的顺序对于数据访问的局部性是很重要的 int a=0;
for(int i=0;i< ;i++) { for(int j=0;j<5;j++) a ++; } for(int i=0;i<5;i++) for(int j=0;j< ;j++) 哪个好？ 嵌套循环的顺序对于数据访问的局部性是很重要的 嵌套循环的顺序对于数据访问的局部性是很重要的. int a[128][40960]; int a=0; for(int i=0;i< ;i++) { for(int j=0;j<5;j++) a ++; } for(int i=0;i<5;i++) for(int j=0;j< ;j++) 哪个好，为什么？长循环作为内循环，减少cpu条件分支预测失败的概率。 所以2比1好

63 程序性能优化方法 哪个好？ 数据分块 for(i=0;i<n;i++) for(j=0;j<n;j++) a[i]+=b[j];
for(j=0;j<n;j+=s) for(i=0;i<n;i++) for(jj=j;jj<min(j+s-1,n);jj++) a[i]+=b[jj] 数据分块 数据分块 如 for(i=0;i<n;i++) for(j=0;j<n;j++) a[i]=a[i]+b[j]; 改成 for(j=0;j<n;j+=s) for(jj=j;jj<min(j+s-1,n);jj++) a[i]+=b[jj] 此处s为分块大小，根据cache大小选择适当的S,使得b[jj,jj+s-1]刚好放在一个cache行下，则i的一次循环，都不会切换该cache行，改善了对数组b访问的时间局部性，从而提高效率

64 程序性能优化方法 哪个好？ 循环展开 for(i=0;i<n;i++) d+=a[i];
for(i=((n%4)+1);i<n;i+4) d+=a[i]+a[i+1]+a[i+2]+a[i+3]; 循环展开 循环展开 将 for(i=0;i<n;i++) d+=a[i]; 变成 for(i=0;i<(n%4),i++) d+=a[i]; for(i=((n%4)+1);i<n;i+4) d+=a[i]+a[i+1]+a[i+2]+a[i+3];

65 程序性能优化方法 并行程序性能优化 减少通信量，提高通信粒度
在全局集合通信如广播，规约、数据散发与收集等时候尽量调用MPI标准库的函数，他们专门为此目的优化 挖掘算法的并行度，减少CPU空闲时间 保持负载平衡（线程池、算法设计） 计算与通信的重叠，利用计算时间屏蔽通信时间 用重复计算减少通信，比如公共量的计算与其让一个处理器算完发给其他处理器，不如大家自己算