1、高性能科学计算理论和方法高性能科学计算理论和方法全册配套课件全册配套课件高性能科学计算理论和方法高性能科学计算理论和方法教材n主要教材：并行程序设计导论帕切克 美国旧金山大学教授参考教材陈国良,中国科学技术大学教授课程考核n平时表现：包括出勤情况、课堂表现、课堂练习，占20n分组报告：课堂将有几次分组讨论作业，要求学生分组并完成相应的课后作业或者编程作业，并在课堂上进行演示，占40%。n期末考试：课程报告，可以是理论课程报告，也可以是实践课程报告，占40%第一章 为什么要并行计算n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序时代变迁n从1986年到
2、2002年，微处理器的性能以平均每年50%的速度不断提升n从2002年开始，单处理器的性能提升速度降低到每年大约20%一个聪明的解决方案n不再继续开发速度更快的单处理器芯片单处理器芯片，而是开始将多个完整的单处理器放到一个集成集成电路芯片上。对程序员的影响n大多数串行程序串行程序是在单个单个处理器上运行的，不会因为简单地增加更多的处理器就获得极大的性能提高n串行程序不会意识到多个多个处理器的存在，它们在一个多处理器系统上运行的性能，往往与在多处理器系统的一个处理器上运行的性能相同相同。为什么需要不断提升的性能n不断提升的计算能力已经成为许多飞速发展领域（如科学、互联网、娱乐等）的核心力量。n随
3、着计算能力的提升，我们要考虑解决的问题也在增加，下面举些例子气候模拟蛋白质折叠药物发现能源研究数据分析并行程序设计n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序为什么需要构建并行系统n到目前为止，单处理器性能大幅度提升的主要原因之一，是日益增加的集成电路晶体管密度（晶体管是电子开关）n但也有内在的问题一点物理常识n更小的晶体管=速度更快的处理器n更快的处理器=增大的耗电量n增大的耗电量=增加的热量n增加的热量=不可靠的处理器解决方案n与其构建更快、更复杂的单处理器，不如在单个芯片上放置多个相对简单的处理器。n核（ “core” ）已经成为中央处理器
4、或者CPU的代名词。 n 答案是并行！并行程序设计n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序为什么需要编写并行程序n大多数为传统单核系统编写的程序无法利用多核处理器n虽然可以在多核系统上运行一个程序的多个实例，但这样意义不大。例如，在多个处理器上运行一个喜爱的游戏程序的多个实例并不是我们需要的。n运行得快！串行问题的处理方法n将串行程序改写为并行程序n编写一个翻译程序来自动地将串行程序翻译成并行程序n非常困难n鲜有突破更多的问题n尽管我们可以编写一些程序，让这些程序辨识串行程序的常见结构，并自动将这些结构转换成并行程序的结构，但转化后的并行程序
5、在实际运行时可能很低效n一个串行程序的高效并行实现可能不是通过发掘其中每一个步骤的高效并行实现来获得，相反，最好的并行化实现可能是通过一步步回溯，然后发现一个全新的算法来获得的例子n假设我们需要计算n个数的值再累加求和n串行代码：例子（续）n现在我们假设有p个核，且p远小于nn每个核能够计算大约n/p个数的值并累加求和，以得到部分和此处的前缀my_代表每个核都使用自己的私有变量，并且每个核能够独立于其他核来执行该代码块例子（续）n每个核都执行完代码后，变量my_sum中就会存储调用Compute_next_value获得的值的和n例如，假如有8个核，n=24，24次调用Compute_next
6、_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核将收到的部分和累加而得到全局总和：例子（续）Core01234567my_sum8197157131214Global sum8 + 19 + 7 + 15 + 7 + 13 + 12 + 14 = 95Core01234567my_sum95197157131214n别急！还有一个更好的方法来计算全局总和更好的并行算法n不要由mast
7、er核计算所有部分和的累加工作n将各个核两两结对，0号核将自己的部分和与1号核的部分和做加法，2号核将自己的部分和与3号核的部分和做加法，4号核将自己的部分和与5号核的部分和做加法，以次类推。多个处理器求全局总和分析比较n在8个核的情况下，第一种方法中，master核需要执行7次接收操作和7次加法n第二种方法中，master核仅需要执行3次接收操和3次加法n第二种方法比第一种方法快2倍！分析比较（续）n当有更多的核时，两者的差异更大。n在1000个核的情况下，第一种方法需要999次接收和加法操作，而第二种方法只需要10次，提高了100倍。n非常明显，第一种计算全局总和的方法是对串行求和程序的一
8、般化：将求和的工作在核之间平分，等到每个核都计算出部分和之后，master简单地重复串行程序中基本的串行求和。而第二种计算全局总和的方法与原来的串行程序没有多大关系。并行程序设计n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序怎么编写并行程序n任务并行n将待解决问题所需要执行的各个任务分配到各个核上执行.n数据并行n将待解决问题所需要处理的数据分配给各个核.n每个核在分配到的数据集上执行大致相似的操作.例子15 个问题300 份试卷3个助教数据并行TA#1TA#2TA#3100 exams100 exams100 exams任务并行TA#1TA#2T
9、A#3Questions 1 - 5Questions 6 - 10Questions 11 - 15求和例子的第一部分数据并行n数据是通过Compute_next_value计算得到的值，每个核在所赋予的数据集上执行大致相同的操作：通过调用Compute_next_value获取所需的数据，再将数据累加求部分和。求和例子的第二部分任务并行n总共有两个任务：一个任务由master核执行，负责接收从其他核传来的部分和，并累加部分和； 另一个任务由其他核执行， 负责将自己计算得到的部分和传递给master核。第一章的课堂练习n练习1. 为求全局总和例子中的my_first_i和my_last_i推
10、导一个公式。需要注意的是：在循环中，应该给各个核分配数目大致相同的计算元素。quotient = n / p;remainder = n % p;if (my_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;练习2n尝试写出树形结构求全局总和的伪代码。假设核的数目
11、是2的幂（1、2、4、8等）。提示：使用变量divisor来决定一个核应该是发送部分和还是接收部分和，divisor的初始值为2，并且每次迭代后增倍。使用变量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_v
12、alue;while ( divisor = number of cores ) if ( my_rank % divisor = 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;练习3n作为前面问题的另一种解法，可以使用C语言的位操作位操作来
13、实现树形结构树形结构的求全局总和。为了了解它是如何工作的，写下核的二进制数编号二进制数编号是非常有帮助的，注意每个阶段相互合作的成对的核。n从表中我们可以看到在第一阶段，每个核与其二进制编号的最右位最右位不同编号的核配对，在第二阶段与其二进制编号的最右第二位最右第二位不同编号的核配对，第三阶段与其二进制编号的最右第三位最右第三位不同编号的核配对。因此，如果在第一阶段有二进制掩码（bitmask）0012、第二阶段有0102、第三阶段有1002，那么可以通过将编号中对应掩码掩码中非零位置的二进制数取反来获得配对核的编号，也即通过异或操作或者操作。n使用位异或位异或操作或者左移左移操作编写伪代码来
14、实现上述算法。bitmask = 1;divisor = 2;sum = my_value;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. 最初的求全局总和的伪代码。
15、 b. 树形结构求全局总和。制作一张表来比较这两种算法在总核数是2、4、8、1024时，0号核执行的接收与加法操作的次数。n(a)接收次数为p-1，加法次数为p-1n(b)接收次数为log2(p)，加法次数为log2(p)练习5n全局总和例子中的第一部分（每个核对分配给它的计算值求和），通常认为是数据并行的例子； 而第一个求全局总和例子的第二个部分（各个核将它们计算出的部分和发送给master核，master核将这些部分和再累加求和），认为是任务并行。第二个全局和例子中的第二部分（各个核使用树形结构累加它们的部分和），是数据并行的例子还是任务并行的例子？为什么？第二章第二章 并行硬件和并行软件
16、53背景知识54串行硬件和软件输入输出程序一次只执行单个任务55“经典”的冯诺依曼结构56主存（Main memory）n主存中有许多区域，每个区域都可以存储指令和数据。n每个区域都有一个地址，可以通过这个地址来访问相应的区域及区域中存储的数据和指令。57中央处理单元(CPU)n中央处理单元中央处理单元分为控制单元和算术逻辑单元（Arithmetic Logic Unit，ALU）。n控制单元控制单元负责决定应该执行程序中的哪些指令。nALU负责执行指令。add 2+258关键术语n寄存器CPU中的数据和程序执行时的状态信息存储在特殊的快速存储介质中n程序计数器控制单元中一个特殊的寄存器，用来
17、存放下一条指令的地址。n总线指令和数据通过CPU和主存之间的互连结构进行传输。这种互连结构通常是总线，总线中包括一组并行的线以及控制这些线的硬件。59memoryCPUfetch/read当数据或指令从主存传送到CPU时，我们称数据或指令从内存中取出或者读出。60memoryCPUwrite/store当数据或指令从CPU传送到主存中时，我们称数据或指令写入或者存入内存中。61冯诺依曼瓶颈主存和CPU之间的分离称为冯诺依曼瓶颈。这是因为互连结构限定了指令和数据访问的速率。程序运行所需要的大部分数据和指令被有效地与CPU隔离开。62一个操作系统“进程”n进程是运行着的程序的一个实例。n一个进程包
18、括如下实体:n可执行的机器语言程序.n一块内存空间.n操作系统分配给进程的资源描述符.n安全信息.n进程状态信息.63多任务n大多数现代操作系统都是多任务的。 这意味着操作系统提供对同时运行多个程序的支持。n这对于单核系统也是可行的，因为每个进程只运行一小段时间（几毫秒），亦即一个时间片。在一个程序执行了一个时间片的时间后，操作系统就切换执行其他程序64多任务n在一个多任务操作系统中，如果一个进程需要等待某个资源，例如需要从外部的存储器读数据，它会阻塞。这意味着，该进程会停止运行，操作系统可以运行其他进程。例如：航班预定系统在一个用户因为等待座位图而阻塞时，可为另一个用户提供可用的航线查询。6
19、5线程n线程包含在进程中。n线程为程序员提供了一种机制，将程序划分为多个大致独立的任务，当某个任务阻塞时能执行其他任务。n此外，在大多数系统中，线程间的切换比进程间的切换更快。66一个进程和两个线程the “master” thread（主线程）starting a threadIs called forking（派生）（派生）terminating a threadIs called joining（合并）（合并）67对冯诺依曼模型的改进68缓存 (Cache)nCPU Cache 是一组相比于主存，CPU能更快速地访问的内存区域。nCPU Cache位于与CPU同一块的芯片或者位于其他芯片
20、上，但比普通的内存芯片能更快地访问。69局部性原理n程序访问完一个存储区域往往会访问接下来的区域，这个原理称为局部性。n空间局部性访问附近的位置n时间局部性访问在不久的将来70局部性原理float z1000;sum = 0.0;for (i = 0; i 1000; i+) sum += zi;71缓存的分层（level）L1L2L3最小 & 最快最大 & 最慢72Cache命中（hit）L1L2L3x sumy z totalA radius r1 centerfetch x73Cache缺失（miss）L1L2L3y sumr1 z totalA radius centerfetch x
21、x主存74与缓存有关的问题n当CPU向Cache中写数据时，Cache中的值与主存中的值就会不同或者不一致(inconsistent)。n有两种方法来解决这个不一致性问题：写直达(write-through) 和写回(write-back) 75与缓存有关的问题n在写直达(write-through) Cache中，当CPU向Cache写数据时，高速缓存行会立即写入主存中。n在写回(write-back) Cache中，数据不是立即更新到主存中，而是将发生数据更新的高速缓存行标记成脏（dirty）。当发生高速缓存行替换时，标记为脏的高速缓存行被写入主存中。76缓存映射n全相联(fully as
22、sociative) Cache每个高速缓存行能够放置在Cache中的任意位置。n直接映射(directed mapped) Cache每个高速缓存行在Cache中有唯一的位置。nn路组相联(n-way set associated)每个高速缓存行都能放置到Cache中n个不同区域位置中的一个。77n路组相联n当内存中的行（多于一行）能被映射到Cache中的多个不同位置（全相联和n路组相联）时，需要决定替换或者驱逐Cache中的哪一行。x78例子假设主存有16行，分别用015标记，Cache有4行，用03标记。在全相联映射中，主存中的0号行能够映射到Cache中的0、1、2、3任意一行。在直接
23、映射Cache中，可以根据主存中高速缓存行的标记值除以4求余，获得在Cache中的索引。因此主存中0、4、8号行会映射到Cache的0号行，主存中的1、5、9号行映射到Cache的1号行，以此类推。79虚拟内存(1)n如果运行一个大型的程序，或者程序需要访问大型数据集，那么所有的指令或者数据可能在主存中放不下。n利用虚拟存储器（或虚拟内存），使得主存可以作为辅存的缓存。80虚拟内存(2)n虚拟内存通过在主存中存放当前执行程序所需要用到的部分，来利用时间和空间局部性.81虚拟内存(3)n交换空间（swap space）那些暂时用不到的部分存储在辅存的块中，称为交换空间。n页(page) 数据块和
24、指令块.n页通常比较大.n大多数系统采用固定大小的页，从416kB不等.82虚拟内存(4)program Aprogram Bprogram Cmain memory83虚拟页号n在编译程序时，给程序的页赋予虚拟页号。n当程序运行时，创建一张将虚拟页号映射成物理地址的表。n程序运行时使用到虚拟地址，这个页表就用来将虚拟地址转换成物理地址。假如页表的创建由操作系统管理，那么就能保证程序使用的内存不会与其他程序使用的内存重叠84页表n假如虚拟地址有32位，页大小是4KB = 4096字节，那么可以用12位来标识页中的每个字节。因此，可以用虚拟地址的低12位来定位页内字节，而剩下的位用来定位页。表2
25、-285思考题n在表2-2中，虚拟地址由12位字节偏移量和20位的虚拟页号组成。如果一个程序运行的系统上拥有这样的页大小和虚拟地址空间，这个程序有多少页？86转译后备缓冲区（ TLB ）n尽管多个程序可以同时使用主存了，但使用页表会增加程序总体的运行时间。n为了解决这个问题，处理器有一种专门用于地址转换的缓存，叫做转译后备缓冲区（TranslationLookaside Buffer，TLB）。87转译后备缓冲区(2)nTLB在快速存储介质中缓存了一些页表的条目（通常为16512条）。n页面失效假如想要访问的页不在内存中，即页表中该页没有合法的物理地址，该页只存储在磁盘上，那么这次访问称为页面
26、失效（page fault）。88指令级并行(ILP)n指令级并行(InstructionLevel parallelism，ILP)通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。89指令级并行(2)n有两种主要方法来实现指令级并行：流水线和多发射。n流水线指将功能单元分阶段安排。n多发射指让多条指令同时启动。90流水线91流水线例子(1)n举一个关于计算的例子，假如我们想要将浮点数9.87104和6.54103相加，我们可以使用如下步骤：92流水线例子(2)n如果每次操作花费1纳秒,那么加法操作需要花费7纳秒nfor循环需要花费7000纳秒.93流水线例子(3)另一个方案n
27、将浮点数加法器划分成7个独立的硬件或者功能单元。n第一个单元取两个操作数，第二个比较指数，以此类推。n假设一个功能单元的输出是下面一个功能单元的输入，那么加法功能单元的输出是规格化结果功能单元的输入。94流水线例子(4)另一个方案95流水线例子(5)另一个方案n在时间5后，流水循环每1纳秒产生一个结果，而不再是每7纳秒一次。所以，执行for循环的总时间从7000纳秒降低到1006纳秒，提高了近7倍。96思考题2n当讨论浮点数加法时，我们简单地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都耗费2纳秒，其余的每个操作耗费1纳秒。 a. 在上述假设下，每个浮点数加法要耗费多少时间？ b.
28、非流水线1000对浮点数的加法要耗费多少时间？ c.流水线1000对浮点数加法要耗费多少时间？97思考题2nd. 如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别非常大。假设从一级缓存上取数据/指令要耗费2纳秒，从二级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执行某条指令，取其中一个操作数时，发生了一次一级缓存失效，那么流水线会发生什么情况？如果又发生二级缓存失效，又会怎样？98思考题2的答案na. nb. 9 1000 = 9000 nanoseconds99思考题2的答案nc. 9 + 999 2 = 2007ns100思考题2
29、的答案nd. 101多发射(1)n多发射处理器通过复制功能单元来同时执行程序中的不同指令。adder #1adder #2z0z2z1z3for (i = 0; i 0) w = x ;e l s e w = y ;Z 应该是正数如果系统预测错误，需要回退机制，然后执行w=y.105硬件多线程n指令级并行是很难利用的，因为程序中有许多部分之间存在依赖关系。n硬件多线程(hardware multithreading)为系统提供了一种机制，使得当前执行的任务被阻塞时，系统能够继续其他有用的工作。n例如，如果当前任务需要等待数据从内存中读出，那么它可以通过执行其他线程而不是继续当前线程来发掘并行性
30、.106硬件多线程(2)n细粒度(fine-grained)在细粒度多线程中，处理器在每条指令执行完后切换线程，从而跳过被阻塞的线程。n优点: 能够避免因为阻塞而导致机器时间的浪费.n缺点: 执行很长一段指令的线程在执行每条指令的时候都需要等待.107硬件多线程(3)n粗粒度(coarse grained)只切换那些需要等待较长时间才能完成操作（如从主存中加载）而被阻塞的线程。n优点: 不需要线程间的立即切换.n缺点: 处理器还是可能在短阻塞时空闲，线程间的切换也还是会导致延迟.108硬件多线程(4)n同步多线程(Simultaneous Multithreading，SMT)是细粒度多线程的
31、变种。n它通过允许多个线程同时使用多个功能单元来利用超标量处理器的性能。如果我们指定“优先”线程，那么能够在一定程度上减轻线程减速的问题。109并行硬件并行硬件110并行硬件n因为有多个复制的功能单元，所以多发射和流水线可以认为是并行硬件。但是，这种并行性通常对程序员是不可见的，所以我们仍把它们当成基本的冯诺依曼结构的扩展。n我们的原则是，并行硬件应该是仅限于对程序员可见的硬件。换句话说，如果能够通过修改源代码而开发并行性或者必须修改源代码来开发并行性，那么我们认为这种硬件是并行硬件111Flynn分类法SISDSingle instruction streamSingle data stre
32、am(SIMD)Single instruction streamMultiple data streamMISDMultiple instruction streamSingle data stream(MIMD)Multiple instruction streamMultiple data streamclassic von Neumannnot covered112SIMDn单指令多数据流(Single Instruction，Multiple Data，SIMD)系统是并行系统。n顾名思义，SIMD系统通过对多个数据执行相同的指令从而实现在多个数据流上的操作。113SIMD例子con
33、trol unitALU1ALU2ALUnfor (i = 0; i n; i+) xi += yi;x1x2xnn data itemsn ALUs114SIMDn如果ALU的数目小于数据的个数，怎么办？n将数据分组，然后迭代计算n例如， m = 4 ALUs，n = 15 个数据RoundALU1ALU2ALU3ALU41X0X1X2X32X4X5X6X73X8X9X10X114X12X13X14115SIMD的缺点n所有的ALU要么执行相同的指令，要么同时处于空闲状态的要求会严重地降低SIMD系统的整体性能。n在“经典”的SIMD系统中，ALU必须同步操作，即在下一条指令开始执行之前，每
34、个ALU必须等待广播。n此外，ALU没有指令存储器，所以ALU不能通过存储指令来延迟执行指令。nSIMD并行性在大型数据并行问题上非常有用，但是在处理其他并行问题时并不优秀。116向量处理器n向量处理器的重要特点是能够对数组或者数据向量进行操作，而传统的CPU是对单独的数据元素或者标量进行操作。n向量寄存器.n能够存储由多个操作数组成的向量，并且能够同时对其内容进行操作。向量的长度由系统决定，从4到128个64位元素不等。117向量处理器(2)n向量化和流水化的功能单元.n对向量中的每个元素需要做同样的操作，或者某些类似于加法的操作，这些操作需要应用到两个向量中相应的元素对上。因此，向量操作是
35、SIMD.n向量指令.n在向量上操作而不是在标量上操作的指令.118向量处理器(3)n交叉存储器.n内存系统由多个内存“体”组成，每个内存体能够独立访问.n在访问完一个内存体之后，再次访问它之前需要有一个时间延迟，但如果接下来的内存访问是访问另一个内存体，那么它很快就能访问到。所以，如果向量中的各个元素分布在不同的内存体中，那么在装入/存储连续数据时能够几乎无延迟地访问。119向量处理器(4)n步长式存储器访问和硬件散射/聚集.n在步长式存储器访问中，程序能够访问向量中固定间隔的元素，例如能够以跨度4访问第一个元素、第五个元素、第九个元素等。120向量处理器优点n速度快而且容易使用；n向量编译
36、器擅长于识别向量化的代码；n它们能识别出不能向量化的循环而且能提供循环为什么不能向量化的原因；因此，用户能对是否重写代码以支持向量化做出明智的决定；n向量系统有很高的内存带宽；n每个加载的数据都会使用，不像基于Cache的系统不能完全利用高速缓存行中的每个元素。121向量处理器缺点n不能处理不规则的数据结构和其他的并行结构n可扩展性差。可扩展性是指能够处理更大问题的能力。122图形处理单元（ GPU ）n实时图形应用编程接口使用点、线、三角形来表示物体的表面。123GPUsn使用图形处理流水线(graphics processing pipeline)将物体表面的内部表示转换为一个像素的数组。
37、 这个像素数组能够在计算机屏幕上显示出来。n流水线的许多阶段是可编程的。可编程阶段的行为可以通过着色函数（shader function）来说明。n典型的着色函数一般比较短，通常只有几行C代码.124GPUsn因为着色函数能够应用到图形流中的多种元素（例如顶点）上， 所以一般是隐式并行的。nGPU可以通过使用SIMD并行来优化性能。 现在所有的GPU都使用SIMD并行。n需要强调的是，GPU不是纯粹的SIMD系统。 尽管在一个给定核上的ALU使用了SIMD并行，但现代的GPU有几十个核，每个核都能独立地执行指令流。125MIMD系统n多指令多数据流（Multiple Instruction，M
38、ultiple Data，MIMD）系统支持同时多个指令流在多个数据流上操作。nMIMD系统通常包括一组完全独立的处理单元或者核，每个处理单元或者核都有自己的控制单元和ALU。126共享内存系统n在共享内存系统中，一组自治的处理器通过互连网络（internection network）与内存系统相互连接。n每个处理器能够访问每个内存区域。n处理器通过访问共享的数据结构来隐式地通信。127共享内存系统(2)n最广泛使用的共享内存系统使用一个或者多个多核处理器.n(一个多核处理器在一块芯片上有多个CPU或者核)128共享内存系统(3)Figure 2.3129一致内存访问(UMA)多核系统Figu
39、re 2.5每个核访问内存中任何一个区域的时间都相同.130非一致内存访问(NUMA)多核系统Figure 2.6访问与核直接连接的那块内存区域比访问其他内存区域要快很多，因为访问其他内存区域需要通过另一块芯片.131分布式内存系统n集群(clusters)n由一组商品化系统组成（例如PC），通过商品化网络连接（例如以太网）。n实际上，集群系统中的节点是通过通信网络相互连接的独立计算单元.132分布式内存系统Figure 2.4133互连网络n互连网络（interconnection network）在分布式内存系统和共享内存系统中都扮演了一个决定性的角色，即使处理器和内存无比强大，但一个缓慢
40、的互连网络会严重降低除简单并行程序外所有程序的整体性能。n分两类：共享内存互连网络和分布式内存互连网络134共享内存互连网络n总线（bus）互联n总线是由一组并行通信线和控制对总线访问的硬件组成的.n总线的核心特征是连接到总线上的设备共享通信线.n因为通信线是共享的，因此随着连接到总线设备的增多，争夺总线的概率增大，总线的预期性能会下降.135共享内存互连网络n交换互连网络n使用交换器（switch）来控制相互连接设备之间的数据传递.n交叉开关矩阵（crossbar） n交叉开关矩阵允许在不同设备之间同时进行通信，所以比总线速度快.n但是，交换器和链路带来的开销也相对高。一个小型的基于总线系统
41、比相等规模的基于交叉开关矩阵系统便宜. 136Figure 2.7(a)图2-7a是一个交叉开关矩阵（crossbar），线表示双向通信链路，方块表示核或者内存模块，圆圈表示交换器(b)图2-7b表示单个交换器有两种不同的设置(c)图2-7c显示了，当P1向M4写数据，P2从M3中读数据，P3从M1中读数据，P4向M2中写数据时，各个交换器的配置情况137分布式内存互连网络n两种n直接互连n在直接互连中，每个交换器与一个处理器-内存对直接相连，交换器之间也相互连接.n间接互连n在间接互连网络中，交换器不一定与处理器直接连接.138直接互连网络139Figure 2.8环(ring)二维环面网格
42、(toroidal mesh)二维环面网格的交换器需要能够支持5个链路而不只是3个等分宽度(bisection width)n衡量“同时通信的链路数目”或者“连接性”的一个标准是等分宽度(bisection width)。n为了理解这个标准，想象并行系统被分成两部分，每部分都有一半的处理器或者节点。在这两部份之间能同时发生多少通信呢？140环的等分宽度141Figure 2.9一个二维环面网格的等分142Figure 2.10定义(Definitions)n带宽 n链路的带宽(bandwidth)是指它传输数据的速度。通常用兆位每秒或者兆字节每秒来表示.n等分带宽n等分带宽(bisection
43、 bandwidth)通常用来衡量网络的质量。它与等分宽度类似。但是，等分带宽不是计算连接两个等分之间的链路数，而是计算链路的带宽。143全相连网络n理想的直接互连网络是全相连网络，即每个交换器与每一个其他的交换器直接连接。但是，为节点数目较多的系统构建这样的互连网络是不切实际的144Figure 2.11bisection width = p2/4impractical超立方体n超立方体是一种已经用于实际系统中的高度互连的直接互连网络。n递归构建:n一维超立方体是有两个处理器的全互连系. n二维超立方体是由两个一维超立方体组成，并通过“相应”的交换器互连. n相似地，三维超立方体由两个二维超
44、立方体构建145超立方体146Figure 2.12one-three-dimensionaltwo-超立方体n维度为d的超立方体有p=2d个节点，并且在d维超立方体中，每个交换器与一个处理器和d个交换器直接连接。这样的超立方体的等分宽度是p/2，所以它比环或者环面网格连接性更高，但需要更强大的交换器，因为每个交换器必须支持1+d=1+log2(p)条连线，而二维环面网格的交换器只需要5条连线。 所以构建一个p个节点的超立方体互连网络比构建一个二维环面网格更昂贵。147间接互连网络n间接互连为直接互连提供了一个替代的选择。在间接互连网络中，交换器不一定与处理器直接连接。它们通常由一些单向连接和
45、一组处理器组成，每个处理器有一个输入链路和一个输出链路，这些链路通过一个交换网络连接。n交叉开关矩阵和omega网络是间接网络中相对简单的例子。148一个通用的间接网络149Figure 2.13交叉开关互连网络150Figure 2.14交叉开关矩阵通过单向链路共享分布式内存omega网络nomega网络比交叉开关矩阵便宜。omega网络使用了1/2plog2（p）个交换器， 每个交换器是一个22交叉开关矩阵交换器，所以总共使用了2plog2(p)个交换器，而交叉开关矩阵使用p2个交换器n一个pp大小的交叉开关矩阵的等分宽度是p，而一个omega网络的等分宽度是p/2。151思考题n请写出不
46、同的分布式内存互连形式的总链路数的表达式。152互连网络互连网络节点数节点数链路数链路数环P二维环面网格p=q2全互连网络p超立方体p=2d交叉开关矩阵pomega网络p=2d153思考题na.除了没有循环链接（“wraparound” link）， 平面网格（planar mesh）和二维环面网格(toroidal mesh)是相似的。请问一个平面网格的等分宽度是多少？nb.三维网格与平面网格是相似的，除了三维网格拥有深度这个特性外。请问一个三维网格的等分宽度是多少？154na. 假设节点数p = q q ，则等分宽度是qnb.假设节点数p = q q q ，则等分宽度是q q155思考题n
47、a. 请画出一个四维超立方体结构。nb. 请用超立方体的归纳定义来解释为何超立方体的等分宽度为p/2。156157 由于d维的超立方体有2d个节点，我们需要剪掉2d个链路. 而 (d + 1)-维的超立方体有p=2d+1个节点, 则2d= p/2更多的定义n当传送数据时，我们关心数据到达目的地需要花多少时间.n延迟（latency）n延迟是指从发送源开始传送数据到目的地开始接收数据之间的时间.n带宽(bandwidth)n带宽是指目的地在开始接收数据后接收数据的速度.158159消息传送的时间= l + n / b延时 (秒)带宽 (字节每秒)消息的长度(字节)Cache 一致性160nCPU
48、 Cache是由系统硬件来管理的，程序员对它不能进行直接的控制.Figure 2.17假如共享内存系统中有两个核，每个核有各自私有的数据Cache，见图2-17Cache 一致性161y0的内存区域会最终得到值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的Cache，然后再重新加载到核1的Cache中；若没有上述情况，通
49、常还是会使用原来的值x=2，而z1也会得到42=8。n有两种主要的方法来保证Cache的一致性：监听Cache一致性协议和基于目录的Cache一致性协议162监听Cache一致性协议n监听协议的想法来自于基于总线的系统：当多个核共享总线时，总线上传递的信号都能被连接到总线的所有核“看”到n当核0更新它Cache中x的副本时，如果它也将这个更新信息在总线上广播，并且假如核1正在监听总线，那么它会知道x已经更新了，并将自己Cache中的x的副本标记为非法的。 这就是监听Cache一致性协议大致的工作原理163基于目录的Cache一致性协议n目录存储每个内存行的状态。一般地，这个数据结构是分布式的，
50、在我们的例子中，每个核/内存对负责存储一部分的目录。这部分目录标识局部内存对应高速缓存行的状态。n当一个高速缓存行被读入时，如核0的Cache，与这个高速缓存行相对应的目录项就会更新，表示核0有这个行的副本。 当一个变量需要更新时，就会查询目录，并将所有包含该变量高速缓存行置为非法。164并行软件n通常，在运行共享内存系统时，会启动一个单独的进程，然后派生（folk）出多个线程。所以当我们谈论共享内存程序时，我们指的是正在执行任务的线程。n另一方面，当我们运行分布式内存程序时，我们使用的是多个处理器，所以我们指的是正在执行任务的进程。165单程序多数据流(SPMD)nSPMD程序不是在每个核上
