高性能科学计算理论和方法全册配套完整精品课件.ppt

1、高性能科学计算理论和方法高性能科学计算理论和方法 全册配套完整精品课件全册配套完整精品课件 高性能科学计算理论和方法高性能科学计算理论和方法 教材 n主要教材：并行程序设计导论 帕切克 美国旧金山大学教授 参考教材 陈国良,中国科学技术大学教授 课程考核 n平时表现：包括出勤情况、课堂表现、 课堂练习，占20 n分组报告：课堂将有几次分组讨论作业 ，要求学生分组并完成相应的课后作业 或者编程作业，并在课堂上进行演示， 占40%。 n期末考试：课程报告，可以是理论课程 报告，也可以是实践课程报告，占40% 第一章 为什么要并行计算 n为什么需要不断提升的性能 n为什么需要构建并行系统 n为什么需

2、要编写并行程序 n怎样编写并行程序 时代变迁 n从1986年到2002年，微处理器的性能以 平均每年50%的速度不断提升 n从2002年开始，单处理器的性能提升速 度降低到每年大约20% 一个聪明的解决方案 n不再继续开发速度更快的单处理器芯片单处理器芯片 ，而是开始将多个完整的单处理器放到 一个集成集成电路芯片上。 对程序员的影响 n大多数串行程序串行程序是在单个单个处理器上运行 的，不会因为简单地增加更多的处理器 就获得极大的性能提高 n串行程序不会意识到多个多个处理器的存在 ，它们在一个多处理器系统上运行的性 能，往往与在多处理器系统的一个处理 器上运行的性能相同相同。 为什么需要不断提

3、升的性能 n不断提升的计算能力已经成为许多飞速 发展领域（如科学、互联网、娱乐等） 的核心力量。 n随着计算能力的提升，我们要考虑解决 的问题也在增加，下面举些例子 气候模拟 蛋白质折叠 药物发现 能源研究 数据分析 并行程序设计 n为什么需要不断提升的性能 n为什么需要构建并行系统 n为什么需要编写并行程序 n怎样编写并行程序 为什么需要构建并行系统 n到目前为止，单处理器性能大幅度提升 的主要原因之一，是日益增加的集成电 路晶体管密度（晶体管是电子开关） n但也有内在的问题 一点物理常识 n更小的晶体管=速度更快的处理器 n更快的处理器=增大的耗电量 n增大的耗电量=增加的热量 n增加的热

4、量=不可靠的处理器 解决方案 n与其构建更快、更复杂的单处理器，不如在单 个芯片上放置多个相对简单的处理器。 n核（ “core” ）已经成为中央处理器或者CPU的 代名词。 n 答案是并行！ 并行程序设计 n为什么需要不断提升的性能 n为什么需要构建并行系统 n为什么需要编写并行程序 n怎样编写并行程序 为什么需要编写并行程序 n大多数为传统单核系统编写的程序无法 利用多核处理器 n虽然可以在多核系统上运行一个程序的 多个实例，但这样意义不大。例如，在 多个处理器上运行一个喜爱的游戏程序 的多个实例并不是我们需要的。 n运行得快！ 串行问题的处理方法 n将串行程序改写为并行程序 n编写一个翻

5、译程序来自动地将串行程序 翻译成并行程序 n非常困难 n鲜有突破 更多的问题 n尽管我们可以编写一些程序，让这些程序辨识 串行程序的常见结构，并自动将这些结构转换 成并行程序的结构，但转化后的并行程序在实 际运行时可能很低效 n一个串行程序的高效并行实现可能不是通过发 掘其中每一个步骤的高效并行实现来获得，相 反，最好的并行化实现可能是通过一步步回溯 ，然后发现一个全新的算法来获得的 例子 n假设我们需要计算n个数的值再累加求和 n串行代码： 例子（续） n现在我们假设有p个核，且p远小于n n每个核能够计算大约n/p个数的值并累加 求和，以得到部分和 此处的前缀my_代表每个核都使用自己的私

6、 有变量，并且每个核能够独立于其他核来执 行该代码块 例子（续） n每个核都执行完代码后，变量my_sum中 就会存储调用Compute_next_value获得 的值的和 n例如，假如有8个核，n=24，24次调用 Compute_next_value获得如下的值： 1,4,3, 9,2,8, 5,1,1, 5,2,7, 2,5,0, 4,1,8, 6,5,1, 2,3,9 例子（续） n当各个核都计算 完各自的 my_sum值后， 将自己的结果值 发送给一个指定 为“master”的 核（主核）， master核将收到 的部分和累加而 得到全局总和 ： 例子（续） Core01234567

7、 my_sum8197157131214 Global sum 8 + 19 + 7 + 15 + 7 + 13 + 12 + 14 = 95 Core01234567 my_sum95197157131214 n别急！ 还有一个更好 的方法来计算 全局总和 更好的并行算法 n不要由master核计算所有部分和的累加 工作 n将各个核两两结对，0号核将自己的部分 和与1号核的部分和做加法，2号核将自 己的部分和与3号核的部分和做加法，4 号核将自己的部分和与5号核的部分和做 加法，以次类推。 多个处理器求全局总和 分析比较 n在8个核的情况下，第一种方法中， master核需要执行7次接收操作

8、和7次加 法 n第二种方法中，master核仅需要执行3次 接收操和3次加法 n第二种方法比第一种方法快2倍！ 分析比较（续） n当有更多的核时，两者的差异更大。 n在1000个核的情况下，第一种方法需要 999次接收和加法操作，而第二种方法只 需要10次，提高了100倍。 n非常明显，第一种计算全局总和的方法是对串行求和程序的一般化：将 求和的工作在核之间平分，等到每个核都计算出部分和之后，master简 单地重复串行程序中基本的串行求和。而第二种计算全局总和的方法与 原来的串行程序没有多大关系。 并行程序设计 n为什么需要不断提升的性能 n为什么需要构建并行系统 n为什么需要编写并行程序

9、n怎样编写并行程序 怎么编写并行程序 n任务并行 n将待解决问题所需要执行的各个任务分配到 各个核上执行. n数据并行 n将待解决问题所需要处理的数据分配给各个 核. n每个核在分配到的数据集上执行大致相似的 操作. 例子 15 个问题 300 份试卷 3个助教 数据并行 TA#1 TA#2 TA#3 100 exams 100 exams 100 exams 任务并行 TA#1 TA#2 TA#3 Questions 1 - 5 Questions 6 - 10 Questions 11 - 15 求和例子的第一部分数据 并行 n数据是通过Compute_next_value计算得 到的值，

10、每个核在所赋予的数据集上执 行大致相同的操作：通过调用 Compute_next_value获取所需的数据， 再将数据累加求部分和。 求和例子的第二部分任务 并行 n总共有两个任务：一个任务由master核执行，负责接收从其他核传来的 部分和，并累加部分和； 另一个任务由其他核执行， 负责将自己计算得 到的部分和传递给master核。 第一章的课堂练习 n练习1. 为求全局总和例子中的 my_first_i和my_last_i推导一个公式 。需要注意的是：在循环中，应该 给各个核分配数目大致相同的计算 元素。 quotient = n / p; remainder = n % p; if (m

11、y_rank remainder) my_n_count = quotient + 1; my_first_i = my_rank * my_n_count; else my_n_count = quotient; my_first_i = my_rank * my_n_count + remainder; my_last_i = my_first_i + my_n_count - 1; 练习2 n尝试写出树形结构求全局总和的伪代码。假设核的数 目是2的幂（1、2、4、8等）。提示：使用变量divisor 来决定一个核应该是发送部分和还是接收部分和， divisor的初始值为2，并且每次迭代后

12、增倍。使用变量 core_difference来决定哪个核与当前核合作，它的初 始值为1，并且每次迭代后增倍。例如，在第一次迭代 中0 % divisor = 0，1 % divisor = 1，所以0号核负责 接收和，1号核负责发送。在第一次迭代中0 + core_difference = 1，1-core_difference = 0，所以0 号核与1号核在第一次迭代中合作。 divisor = 2; core_difference = 1; sum = my_value; while ( divisor = number of cores ) if ( my_rank % divisor

13、 = 0 ) partner = my_rank + core_difference; receive value from partner core; sum += received value; else partner = my_rank - core_difference; send my sum to partner core; divisor *= 2; core_difference *=2; 练习3 n作为前面问题的另一种解法，可以使用C 语言的位操作位操作来实现树形结构树形结构的求全局 总和。为了了解它是如何工作的，写下 核的二进制数编号二进制数编号是非常有帮助的，注 意每个

14、阶段相互合作的成对的核。 n从表中我们可以看到在第一阶段，每个核与其二进制 编号的最右位最右位不同编号的核配对，在第二阶段与其二 进制编号的最右第二位最右第二位不同编号的核配对，第三阶段 与其二进制编号的最右第三位最右第三位不同编号的核配对。因 此，如果在第一阶段有二进制掩码（bitmask）0012、 第二阶段有0102、第三阶段有1002，那么可以通过将 编号中对应掩码掩码中非零位置的二进制数取反来获得配 对核的编号，也即通过异或操作或者操作。 n使用位异或位异或操作或者左移左移操作编写伪代码来实现上述 算法。 bitmask = 1; divisor = 2; sum = my_valu

15、e; while ( bitmask number of cores ) partner = my_rank bitmask; if ( my_rank % divisor = 0 ) receive value from partner core; sum += received value; else send my_sum to partner core; bitmask = 1; divisor *= 2; 练习4 在下列情况中，推导公式求出0号核执行接 收与加法操作的次数。 a. 最初的求全局总和的伪代码。 b. 树形结构求全局总和。 制作一张表来比较这两种算法在总核数是2 、4、8

16、、1024时，0号核执行的接收与 加法操作的次数。 n(a)接收次数为p-1，加法次数为p-1 n(b)接收次数为log2(p)，加法次数为log2(p) 练习5 n全局总和例子中的第一部分（每个核对分配给 它的计算值求和），通常认为是数据并行的例 子； 而第一个求全局总和例子的第二个部分（ 各个核将它们计算出的部分和发送给master核 ，master核将这些部分和再累加求和），认为 是任务并行。第二个全局和例子中的第二部分 （各个核使用树形结构累加它们的部分和）， 是数据并行的例子还是任务并行的例子？为什 么？ 第二章第二章 并行硬件和并行软件 53 背景知识 54 串行硬件和软件 输入

17、输出 程序 一次只执行单个任务 55 “经典”的冯诺依曼结构 56 主存（Main memory） n主存中有许多区域，每个区域都可以存 储指令和数据。 n每个区域都有一个地址，可以通过这个 地址来访问相应的区域及区域中存储的 数据和指令。 57 中央处理单元(CPU) n中央处理单元中央处理单元分为控制单 元和算术逻辑单元（ Arithmetic Logic Unit， ALU）。 n控制单元控制单元负责决定应该执 行程序中的哪些指令。 nALU负责执行指令。 add 2+2 58 关键术语 n寄存器CPU中的数据和程序执行时的 状态信息存储在特殊的快速存储介质中 n程序计数器控制单元中一个

18、特殊的寄 存器，用来存放下一条指令的地址。 n总线指令和数据通过CPU和主存之间 的互连结构进行传输。这种互连结构通 常是总线，总线中包括一组并行的线以 及控制这些线的硬件。 59 memory CPU fetch/read 当数据或指令从主存传送到CPU 时，我们称数据或指令从内存中 取出或者读出。 60 memory CPU write/store 当数据或指令从CPU传送到主存 中时，我们称数据或指令写入或 者存入内存中。 61 冯诺依曼瓶颈 主存和CPU之间的分离称为冯诺 依曼瓶颈。这是因为互连结构限 定了指令和数据访问的速率。程 序运行所需要的大部分数据和指 令被有效地与CPU隔离开

19、。 62 一个操作系统“进程” n进程是运行着的程序的一个实例。 n一个进程包括如下实体: n可执行的机器语言程序. n一块内存空间. n操作系统分配给进程的资源描述符. n安全信息. n进程状态信息. 63 多任务 n大多数现代操作系统都是多任务的。 这 意味着操作系统提供对同时运行多个程 序的支持。 n这对于单核系统也是可行的，因为每个 进程只运行一小段时间（几毫秒），亦 即一个时间片。在一个程序执行了一个 时间片的时间后，操作系统就切换执行 其他程序 64 多任务 n在一个多任务操作系统中，如果一个进 程需要等待某个资源，例如需要从外部 的存储器读数据，它会阻塞。这意味着 ，该进程会停止

20、运行，操作系统可以运 行其他进程。例如：航班预定系统在一 个用户因为等待座位图而阻塞时，可为 另一个用户提供可用的航线查询。 65 线程 n线程包含在进程中。 n线程为程序员提供了一种机制，将程序 划分为多个大致独立的任务，当某个任 务阻塞时能执行其他任务。 n此外，在大多数系统中，线程间的切换 比进程间的切换更快。 66 一个进程和两个线程 the “master” thread（主线程） starting a thread Is called forking（派生）（派生） terminating a thread Is called joining（合并）（合并） 67 对冯诺依曼模型的

21、改进 68 缓存 (Cache) nCPU Cache 是一组相比于主存，CPU能 更快速地访问的内存区域。 nCPU Cache位于与CPU同一块的芯片或者 位于其他芯片上，但比普通的内存芯片 能更快地访问。 69 局部性原理 n程序访问完一个存储区域往往会访问接 下来的区域，这个原理称为局部性。 n空间局部性访问附近的位置 n时间局部性访问在不久的将来 70 局部性原理 float z1000; sum = 0.0; for (i = 0; i 1000; i+) sum += zi; 71 缓存的分层（level） L1 L2 L3 最小 i 0) w = x ; e l s e w =

22、 y ; Z 应该是 正数 如果系统预测错误，需要回退机制， 然后执行w=y. 105 硬件多线程 n指令级并行是很难利用的，因为程序中有许多部分之 间存在依赖关系。 n硬件多线程(hardware multithreading)为系统提供了一 种机制，使得当前执行的任务被阻塞时，系统能够继 续其他有用的工作。 n例如，如果当前任务需要等待数据从内存中读出， 那么它可以通过执行其他线程而不是继续当前线程 来发掘并行性. 106 硬件多线程(2) n细粒度(fine-grained)在细粒度多线 程中，处理器在每条指令执行完后切换 线程，从而跳过被阻塞的线程。 n优点: 能够避免因为阻塞而导致机

23、器时间的 浪费. n缺点: 执行很长一段指令的线程在执行每条 指令的时候都需要等待. 107 硬件多线程(3) n粗粒度(coarse grained)只切换那些 需要等待较长时间才能完成操作（如从 主存中加载）而被阻塞的线程。 n优点: 不需要线程间的立即切换. n缺点: 处理器还是可能在短阻塞时空闲，线 程间的切换也还是会导致延迟. 108 硬件多线程(4) n同步多线程(Simultaneous Multithreading，SMT)是细粒度多线 程的变种。 n它通过允许多个线程同时使用多个功能 单元来利用超标量处理器的性能。如果 我们指定“优先”线程，那么能够在一 定程度上减轻线程减速

24、的问题。 109 并行硬件 并行硬件 110 并行硬件 n因为有多个复制的功能单元，所以多发射和流 水线可以认为是并行硬件。但是，这种并行性 通常对程序员是不可见的，所以我们仍把它们 当成基本的冯诺依曼结构的扩展。 n我们的原则是，并行硬件应该是仅限于对程序 员可见的硬件。换句话说，如果能够通过修改 源代码而开发并行性或者必须修改源代码来开 发并行性，那么我们认为这种硬件是并行硬件 111 Flynn分类法 SISD Single instruction stream Single data stream (SIMD) Single instruction stream Multiple da

25、ta stream MISD Multiple instruction stream Single data stream (MIMD) Multiple instruction stream Multiple data stream classic von Neumann not covered 112 SIMD n单指令多数据流(Single Instruction， Multiple Data，SIMD)系统是并行系统。 n顾名思义，SIMD系统通过对多个数据执 行相同的指令从而实现在多个数据流上 的操作。 113 SIMD例子 control unit ALU1ALU2ALUn for

26、 (i = 0; i n; i+) xi += yi; x1x2xn n data items n ALUs 114 SIMD n如果ALU的数目小于数据的个数，怎么办 ？ n将数据分组，然后迭代计算 n例如， m = 4 ALUs，n = 15 个数据 RoundALU1ALU2ALU3ALU4 1X0X1X2X3 2X4X5X6X7 3X8X9X10X11 4X12X13X14 115 SIMD的缺点 n所有的ALU要么执行相同的指令，要么同时处于空闲状 态的要求会严重地降低SIMD系统的整体性能。 n在“经典”的SIMD系统中，ALU必须同步操作，即在 下一条指令开始执行之前，每个ALU

27、必须等待广播。 n此外，ALU没有指令存储器，所以ALU不能通过存储指 令来延迟执行指令。 nSIMD并行性在大型数据并行问题上非常有用，但是在 处理其他并行问题时并不优秀。 116 向量处理器 n向量处理器的重要特点是能够对数组或 者数据向量进行操作，而传统的CPU是对 单独的数据元素或者标量进行操作。 n向量寄存器. n能够存储由多个操作数组成的向量，并且能 够同时对其内容进行操作。向量的长度由系 统决定，从4到128个64位元素不等。 117 向量处理器(2) n向量化和流水化的功能单元. n对向量中的每个元素需要做同样的操作，或 者某些类似于加法的操作，这些操作需要应 用到两个向量中相

28、应的元素对上。因此，向 量操作是SIMD. n向量指令. n在向量上操作而不是在标量上操作的指令. 118 向量处理器(3) n交叉存储器. n内存系统由多个内存“体”组成，每个内存 体能够独立访问. n在访问完一个内存体之后，再次访问它之前 需要有一个时间延迟，但如果接下来的内存 访问是访问另一个内存体，那么它很快就能 访问到。所以，如果向量中的各个元素分布 在不同的内存体中，那么在装入/存储连续 数据时能够几乎无延迟地访问。 119 向量处理器(4) n步长式存储器访问和硬件散射/聚集. n在步长式存储器访问中，程序能够访问向量 中固定间隔的元素，例如能够以跨度4访问 第一个元素、第五个元

29、素、第九个元素等。 120 向量处理器优点 n速度快而且容易使用； n向量编译器擅长于识别向量化的代码； n它们能识别出不能向量化的循环而且能提供循 环为什么不能向量化的原因；因此，用户能对 是否重写代码以支持向量化做出明智的决定； n向量系统有很高的内存带宽； n每个加载的数据都会使用，不像基于Cache的 系统不能完全利用高速缓存行中的每个元素。 121 向量处理器缺点 n不能处理不规则的数据结构和其他的并 行结构 n可扩展性差。可扩展性是指能够处理更 大问题的能力。 122 图形处理单元（ GPU ） n实时图形应用编程接口使用点、线、三 角形来表示物体的表面。 123 GPUs n使用

30、图形处理流水线(graphics processing pipeline)将 物体表面的内部表示转换为一个像素的数组。 这个像 素数组能够在计算机屏幕上显示出来。 n流水线的许多阶段是可编程的。可编程阶段的行为可 以通过着色函数（shader function）来说明。 n典型的着色函数一般比较短，通常只有几行C代码. 124 GPUs n因为着色函数能够应用到图形流中的多种元素 （例如顶点）上， 所以一般是隐式并行的。 nGPU可以通过使用SIMD并行来优化性能。 现 在所有的GPU都使用SIMD并行。 n需要强调的是，GPU不是纯粹的SIMD系统。 尽管在一个给定核上的ALU使用了SIMD

31、并行， 但现代的GPU有几十个核，每个核都能独立地 执行指令流。 125 MIMD系统 n多指令多数据流（Multiple Instruction， Multiple Data，MIMD）系统支持同时多 个指令流在多个数据流上操作。 nMIMD系统通常包括一组完全独立的处理 单元或者核，每个处理单元或者核都有 自己的控制单元和ALU。 126 共享内存系统 n在共享内存系统中，一组自治的处理器 通过互连网络（internection network） 与内存系统相互连接。 n每个处理器能够访问每个内存区域。 n处理器通过访问共享的数据结构来隐式 地通信。 127 共享内存系统(2) n最广泛使

32、用的共享内存系统使用一个或 者多个多核处理器. n(一个多核处理器在一块芯片上有多个CPU或 者核) 128 共享内存系统(3) Figure 2.3 129 一致内存访问(UMA)多核系统 Figure 2.5 每个核访问内存中 任何一个区域的时 间都相同. 130 非一致内存访问(NUMA)多核系统 Figure 2.6 访问与核直接连接的那块内存区 域比访问其他内存区域要快很多， 因为访问其他内存区域需要通过 另一块芯片. 131 分布式内存系统 n集群(clusters) n由一组商品化系统组成（例如PC），通过商 品化网络连接（例如以太网）。 n实际上，集群系统中的节点是通过通信 网

33、络相互连接的独立计算单元. 132 分布式内存系统 Figure 2.4 133 互连网络 n互连网络（interconnection network）在 分布式内存系统和共享内存系统中都扮 演了一个决定性的角色，即使处理器和 内存无比强大，但一个缓慢的互连网络 会严重降低除简单并行程序外所有程序 的整体性能。 n分两类：共享内存互连网络和分布式内 存互连网络 134 共享内存互连网络 n总线（bus）互联 n总线是由一组并行通信线和控制对总线访问 的硬件组成的. n总线的核心特征是连接到总线上的设备共享 通信线. n因为通信线是共享的，因此随着连接到总线 设备的增多，争夺总线的概率增大，总线

34、的 预期性能会下降. 135 共享内存互连网络 n交换互连网络 n使用交换器（switch）来控制相互连接设备 之间的数据传递. n交叉开关矩阵（crossbar） n交叉开关矩阵允许在不同设备之间同时进行通信 ，所以比总线速度快. n但是，交换器和链路带来的开销也相对高。一个 小型的基于总线系统比相等规模的基于交叉开关 矩阵系统便宜. 136 Figure 2.7 (a)图2-7a是一个交叉开关矩阵 （crossbar），线表示双向通信 链路，方块表示核或者内存模块， 圆圈表示交换器 (b)图2-7b表示单个交换器有两种不 同的设置 (c)图2-7c显示了，当P1向M4写 数据，P2从M3中

35、读数据，P3从 M1中读数据，P4向M2中写数据 时，各个交换器的配置情况 137 分布式内存互连网络 n两种 n直接互连 n在直接互连中，每个交换器与一个处理器-内存 对直接相连，交换器之间也相互连接. n间接互连 n在间接互连网络中，交换器不一定与处理器直接 连接. 138 直接互连网络 139 Figure 2.8 环(ring)二维环面网格(toroidal mesh) 二维环面网格的交换 器需要能够支持5个链 路而不只是3个 等分宽度(bisection width) n衡量“同时通信的链路数目”或者“连接性” 的一个标准是等分宽度(bisection width)。 n为了理解这个

36、标准，想象并行系统被分成两部 分，每部分都有一半的处理器或者节点。在这 两部份之间能同时发生多少通信呢？ 140 环的等分宽度 141 Figure 2.9 一个二维环面网格的等分 142 Figure 2.10 定义(Definitions) n带宽 n链路的带宽(bandwidth)是指它传输数据的速度。通 常用兆位每秒或者兆字节每秒来表示. n等分带宽 n等分带宽(bisection bandwidth)通常用来衡量网络 的质量。它与等分宽度类似。但是，等分带宽不是 计算连接两个等分之间的链路数，而是计算链路的 带宽。 143 全相连网络 n理想的直接互连网络是全相连网络，即每个交换器与

37、 每一个其他的交换器直接连接。但是，为节点数目较 多的系统构建这样的互连网络是不切实际的 144 Figure 2.11 bisection width = p2/4 impractical 超立方体 n超立方体是一种已经用于实际系统中的 高度互连的直接互连网络。 n递归构建: n一维超立方体是有两个处理器的全互连系. n二维超立方体是由两个一维超立方体组成， 并通过“相应”的交换器互连. n相似地，三维超立方体由两个二维超立方体 构建 145 超立方体 146 Figure 2.12 one-three-dimensionaltwo- 超立方体 n维度为d的超立方体有p=2d个节点，并且在d

38、 维超立方体中，每个交换器与一个处理器和d 个交换器直接连接。这样的超立方体的等分宽 度是p/2，所以它比环或者环面网格连接性更 高，但需要更强大的交换器，因为每个交换器 必须支持1+d=1+log2(p)条连线，而二维环面 网格的交换器只需要5条连线。 所以构建一个 p个节点的超立方体互连网络比构建一个二维 环面网格更昂贵。 147 间接互连网络 n间接互连为直接互连提供了一个替代的选择。 在间接互连网络中，交换器不一定与处理器直 接连接。它们通常由一些单向连接和一组处理 器组成，每个处理器有一个输入链路和一个输 出链路，这些链路通过一个交换网络连接。 n交叉开关矩阵和omega网络是间接网

39、络中相对 简单的例子。 148 一个通用的间接网络 149 Figure 2.13 交叉开关互连网络 150 Figure 2.14 交叉开关矩阵通过单向 链路共享分布式内存 omega网络 nomega网络比交叉开关矩阵 便宜。omega网络使用了 1/2plog2（p）个交换器， 每个交换器是一个22交叉 开关矩阵交换器，所以总共 使用了2plog2(p)个交换器， 而交叉开关矩阵使用p2个交 换器 n一个pp大小的交叉开关矩 阵的等分宽度是p，而一个 omega网络的等分宽度是 p/2。 151 思考题 n请写出不同的分布式内存互连形式的总 链路数的表达式。 152 互连网络互连网络节点

40、数节点数链路数链路数 环P 二维环面网格p=q2 全互连网络p 超立方体p=2d 交叉开关矩阵p omega网络p=2d 153 思考题 na.除了没有循环链接（“wraparound” link）， 平面网格（planar mesh）和二 维环面网格(toroidal mesh)是相似的。请 问一个平面网格的等分宽度是多少？ nb.三维网格与平面网格是相似的，除了 三维网格拥有深度这个特性外。请问一 个三维网格的等分宽度是多少？ 154 na. 假设节点数p = q q ，则等分宽度 是q nb.假设节点数p = q q q ，则等分 宽度是q q 155 思考题 na. 请画出一个四维超立

41、方体结构。 nb. 请用超立方体的归纳定义来解释为何 超立方体的等分宽度为p/2。 156 157 由于d维的超立方体有2d 个节点，我们需要剪掉2d 个链路. 而 (d + 1)-维的 超立方体有p=2d+1个节点, 则2d= p/2 更多的定义 n当传送数据时，我们关心数据到达目的 地需要花多少时间. n延迟（latency） n延迟是指从发送源开始传送数据到目的地开 始接收数据之间的时间. n带宽(bandwidth) n带宽是指目的地在开始接收数据后接收数据 的速度. 158 159 消息传送的时间= l + n / b 延时 (秒) 带宽 (字节每秒) 消息的长度(字节) Cache

42、 一致性 160 nCPU Cache是由系统 硬件来管理的，程序 员对它不能进行直接 的控制. Figure 2.17 假如共享内存系统中有两个核，每个核 有各自私有的数据Cache，见图2-17 Cache 一致性 161 y0的内存区域会最终得到值2，y1的内存区域会得到值6， z1 = ? x是一个共享变量并初始化为2， y0是核0私有的，y1和z1是核1私有 的 Cache 一致性 nz1会获得什么值就不是很清楚了。 n第一感觉可能是，既然核0在z1赋值前将x更新为7，所 以z1可以得到47=28。 n但是，在时间0时，x已经在核1的Cache中。除非出于 某些原因，x清除出核0的C

43、ache，然后再重新加载到核 1的Cache中；若没有上述情况，通常还是会使用原来 的值x=2，而z1也会得到42=8。 n有两种主要的方法来保证Cache的一致性：监听Cache 一致性协议和基于目录的Cache一致性协议 162 监听Cache一致性协议 n监听协议的想法来自于基于总线的系统：当多 个核共享总线时，总线上传递的信号都能被连 接到总线的所有核“看”到 n当核0更新它Cache中x的副本时，如果它也将 这个更新信息在总线上广播，并且假如核1正 在监听总线，那么它会知道x已经更新了，并 将自己Cache中的x的副本标记为非法的。 这 就是监听Cache一致性协议大致的工作原理 1

44、63 基于目录的Cache一致性协议 n目录存储每个内存行的状态。一般地，这个数据结构 是分布式的，在我们的例子中，每个核/内存对负责存 储一部分的目录。这部分目录标识局部内存对应高速 缓存行的状态。 n当一个高速缓存行被读入时，如核0的Cache，与这个 高速缓存行相对应的目录项就会更新，表示核0有这个 行的副本。 当一个变量需要更新时，就会查询目录， 并将所有包含该变量高速缓存行置为非法。 164 并行软件 n通常，在运行共享内存系统时，会启动一个单独的进 程，然后派生（folk）出多个线程。所以当我们谈论共 享内存程序时，我们指的是正在执行任务的线程。 n另一方面，当我们运行分布式内存程

45、序时，我们使用 的是多个处理器，所以我们指的是正在执行任务的进 程。 165 单程序多数据流(SPMD) nSPMD程序不是在每个核上运行不同的程序，相反， SPMD程序仅包含一段可执行代码，通过使用条件转移 语句，可以让这一段代码在执行时表现得像是在不同 处理器上执行不同的程序。 166 if (Im thread/process i) do this; else do that; SPMD nSPMD程序能够实现任务并行，也能够实 现数据并行，比如 167 进程或线程的协调 n只有在极少数的情况下，获取好的并行 性能是容易的。例如，假设有两个数组 ，我们想要将它们相加 168 double

46、 xn, yn; for (i = 0; i my_val = %dn , my_rank , my_x ) ; . . . Thread 0 my_val = 7 Thread 1 my_val = 19 Thread 1 my_val = 19 Thread 0 my_val = 7 因为线程独立执行并且独立地与操作系统交 互，执行一个线程完成一段语句所花的时间 在不同次的执行也是不同，所以语句执行的 顺序是不能预测的。 非确定性 n当线程或者进程尝试同时访问一个资源时，这 种访问会引发错误，我们经常说程序有竞争条 件（race condition），因为线程或者进程处于 竞争状态下。 n

47、举个例子。假设每个线程计算一个int型整数， 这个int型整数存储在私有变量my_val中。假设 想要将my_val的值加到共享内存的x位置中，x 初始化为0。两个线程都要执行下面的代码： 175 非确定性 176 my_val = Compute_val ( my_rank ) ; x += my_val ; 在这个例子中，线程竞争执行x+=my_val。在这种情况下， 除非一个线程在另一个线程开始前，计算完成x+=my_val， 结果才是正确的。 非确定性 n一次只能被一个线程执行的代码块称为临界区 (critical section)，通常是程序员的责任来保证 互斥地访问临界区。换句话说

48、，我们需要保证 如果一个线程在临界区中执行代码，其他线程 需要被排除在临界区外。 n保证互斥执行的最常用机制是互斥锁（mutual exclusion clock），或者互斥量(mutex)，或者 锁(lock)。因此，为了保证代码正常运行，我 们必须修改代码为 177 非确定性 n这保证了每次只有一个线程执行语句x+=my_val。 这段代码在线程上没有施加任何预定的顺序。或者 线程0或者线程1能够先执行x+=my_val。 178 my_val = Compute_val ( my_rank ) ; Lock( x += my_val ; Unlock( 忙等待 n可以用忙等待来替代互斥量

49、的方式 n在忙等待（busywaiting）时，一个线 程进入一个循环，这个循环的目的只是 测试一个条件。在我们的例子中，假设 共享变量ok_for_1初始化为false，下面 的代码能够保证只有在线程0将ok_for_1 置为ture 后，线程1才能更新x： 179 忙等待 180 my_val = Compute_val ( my_rank ) ; i f ( my_rank = 1) while ( ! ok_for_1 ) ; /* Busywait loop */ x += my_val ; /* Critical section */ i f ( my_rank = 0) ok_f

50、or_1 = true ; /* Let thread 1 update x */ 分布式内存程序 n在分布式内存程序中，各个核能够直接访问自己的私 有内存。目前已经有了许多可以使用的分布式内存编 程API。但是，最广泛使用的是消息传递。 n分布式内存程序通常执行多个进程而不是多个线程。 这是因为在分布式内存系统中，典型的“执行的线程 ”是在独立的CPU中独立的操作系统上运行的，目前 还没有软件架构可以启动一个简单的“分布式”进程 ，使该进程能在系统中的各个节点上再派生出更多的 线程来。 181 消息传递(message-passing) n消息传递的API（至少）要提供一个发送和一 个接收函