1、高性能科学计算理论和方法高性能科学计算理论和方法教材n主要教材：并行程序设计导论帕切克 美国旧金山大学教授参考教材陈国良,中国科学技术大学教授课程考核n平时表现：包括出勤情况、课堂表现、课堂练习，占20n分组报告：课堂将有几次分组讨论作业，要求学生分组并完成相应的课后作业或者编程作业，并在课堂上进行演示，占40%。n期末考试：课程报告，可以是理论课程报告，也可以是实践课程报告，占40%第一章 为什么要并行计算n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序时代变迁n从1986年到2002年，微处理器的性能以平均每年50%的速度不断提升n从2002年开
2、始，单处理器的性能提升速度降低到每年大约20%一个聪明的解决方案n不再继续开发速度更快的单处理器芯片单处理器芯片，而是开始将多个完整的单处理器放到一个集成集成电路芯片上。对程序员的影响n大多数串行程序串行程序是在单个单个处理器上运行的，不会因为简单地增加更多的处理器就获得极大的性能提高n串行程序不会意识到多个多个处理器的存在，它们在一个多处理器系统上运行的性能，往往与在多处理器系统的一个处理器上运行的性能相同相同。为什么需要不断提升的性能n不断提升的计算能力已经成为许多飞速发展领域（如科学、互联网、娱乐等）的核心力量。n随着计算能力的提升，我们要考虑解决的问题也在增加，下面举些例子气候模拟蛋白
3、质折叠药物发现能源研究数据分析并行程序设计n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序为什么需要构建并行系统n到目前为止，单处理器性能大幅度提升的主要原因之一，是日益增加的集成电路晶体管密度（晶体管是电子开关）n但也有内在的问题一点物理常识n更小的晶体管=速度更快的处理器n更快的处理器=增大的耗电量n增大的耗电量=增加的热量n增加的热量=不可靠的处理器解决方案n与其构建更快、更复杂的单处理器，不如在单个芯片上放置多个相对简单的处理器。n核（ “core” ）已经成为中央处理器或者CPU的代名词。 n 答案是并行！并行程序设计n为什么需要不断提升的
4、性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序为什么需要编写并行程序n大多数为传统单核系统编写的程序无法利用多核处理器n虽然可以在多核系统上运行一个程序的多个实例，但这样意义不大。例如，在多个处理器上运行一个喜爱的游戏程序的多个实例并不是我们需要的。n运行得快！串行问题的处理方法n将串行程序改写为并行程序n编写一个翻译程序来自动地将串行程序翻译成并行程序n非常困难n鲜有突破更多的问题n尽管我们可以编写一些程序，让这些程序辨识串行程序的常见结构，并自动将这些结构转换成并行程序的结构，但转化后的并行程序在实际运行时可能很低效n一个串行程序的高效并行实现可能不是通过发掘其中每
5、一个步骤的高效并行实现来获得，相反，最好的并行化实现可能是通过一步步回溯，然后发现一个全新的算法来获得的例子n假设我们需要计算n个数的值再累加求和n串行代码：例子（续）n现在我们假设有p个核，且p远小于nn每个核能够计算大约n/p个数的值并累加求和，以得到部分和此处的前缀my_代表每个核都使用自己的私有变量，并且每个核能够独立于其他核来执行该代码块例子（续）n每个核都执行完代码后，变量my_sum中就会存储调用Compute_next_value获得的值的和n例如，假如有8个核，n=24，24次调用Compute_next_value获得如下的值：1,4,3, 9,2,8, 5,1,1, 5,
6、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不要由master核计算所有部分和的累加工作n将各个核两两结对，0号核将自己的部分和与
7、1号核的部分和做加法，2号核将自己的部分和与3号核的部分和做加法，4号核将自己的部分和与5号核的部分和做加法，以次类推。多个处理器求全局总和分析比较n在8个核的情况下，第一种方法中，master核需要执行7次接收操作和7次加法n第二种方法中，master核仅需要执行3次接收操和3次加法n第二种方法比第一种方法快2倍！分析比较（续）n当有更多的核时，两者的差异更大。n在1000个核的情况下，第一种方法需要999次接收和加法操作，而第二种方法只需要10次，提高了100倍。n非常明显，第一种计算全局总和的方法是对串行求和程序的一般化：将求和的工作在核之间平分，等到每个核都计算出部分和之后，maste
8、r简单地重复串行程序中基本的串行求和。而第二种计算全局总和的方法与原来的串行程序没有多大关系。并行程序设计n为什么需要不断提升的性能n为什么需要构建并行系统n为什么需要编写并行程序n怎样编写并行程序怎么编写并行程序n任务并行n将待解决问题所需要执行的各个任务分配到各个核上执行.n数据并行n将待解决问题所需要处理的数据分配给各个核.n每个核在分配到的数据集上执行大致相似的操作.例子15 个问题300 份试卷3个助教数据并行TA#1TA#2TA#3100 exams100 exams100 exams任务并行TA#1TA#2TA#3Questions 1 - 5Questions 6 - 10Qu
9、estions 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尝试写出树形结构求全局总和的伪代码。假设核的数目是2的幂（1、2、4、8等）。提示：使用变量divisor来决定一个核应
11、该是发送部分和还是接收部分和，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_value;while ( divisor = number of cor
12、es ) 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使用位异或位异或操作或者左移左移操作编写伪代码来实现上述算法。bitmask = 1;divisor = 2;sum =
14、 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. 最初的求全局总和的伪代码。 b. 树形结构求全局总和。制作一张表来比较这两种算法在总核数是2、4、8、1024时，0号核执行的接收与加法操作的次数。n(a)接收次数为p-1，加法次数为p-1n(b)接收次数为log2(p)，加法次数为log2(p)练习5n全局总和例子中的第一部分（每个核对分配给它的计算值求和），通常认为是数据并行的例子； 而第一个求全局总和例子的第二个部分（各个核将它们计算出的部分和发送给master核，master核将这些部分和再累加求和），认为是任务并行。第二个全局和例子中的第二部分（各个核使用树形结构累加它们的部分和），是数据并行的例子还是任务并行的例子？为什么？
