2007 年 6 月, 前三名并行计算机, 全是 MPP 排在 top500 (2007/6) 的位于中国的并行机 Figure: 第一, Blue- Gene/L at Lawrence Livermore NL, 万亿次 /s(tflop/s), 65,536 dualprocess

Size: px

Start display at page:

Download "2007 年 6 月, 前三名并行计算机, 全是 MPP 排在 top500 (2007/6) 的位于中国的并行机 Figure: 第一, Blue- Gene/L at Lawrence Livermore NL, 万亿次 /s(tflop/s), 65,536 dualprocess"

矿左
5 years ago
Views:

1 Introduction to Department of Science and

University August 9, 2007 2 3 操作系统通信标准 4 5 6 7 8 9

(massively parallel processing, MPP) 加快求解问题的速度

1 1 Introduction to Department of Science and Engineering School of Mathematics School Peking University August 9, 操作系统通信标准机群 (cluster) 星群 (constellation) 大规模并行计算机系统 (massively parallel processing, MPP) 加快求解问题的速度提高求解问题的规模 Figure: Architecture share for 06/2007 from

2007 年 6 月, 前三名并行计算机, 全是 MPP 排在 top500 (2007/6) 的位于中国的并行机 Figure: 第一, Blue- Gene/L

6 万亿次 /s(tflop/s), 65,536 dualprocessor compute nodes Figure: 第二,Jaguar at Oak Ridge

4 TFlop/s 43 Sinopec ShengLI Oilfield Branch Company,( 公司 ) Geophysical Research

9 (CPU 个数,GFlop/s) 87 China Meteorological Administration China eserver IBM 3200

168-173 Gaming Company (B) 356,428 Digital China Ltd.

2 2007 年 6 月, 前三名并行计算机, 全是 MPP 排在 top500 (2007/6) 的位于中国的并行机 Figure: 第一, Blue- Gene/L at Lawrence Livermore NL, 万亿次 /s(tflop/s), 65,536 dualprocessor compute nodes Figure: 第二,Jaguar at Oak Ridge NL,101.7 TFlop/s Figure: 第三, Red Storm at Sandia NL,101.4 TFlop/s 43 Sinopec ShengLI Oilfield Branch Company,( 公司 ) Geophysical Research Institute China ( 地点 ) IBM (CPU 个数,GFlop/s) 87 China Meteorological Administration China eserver IBM Shanghai Supercomputer Center China Dawning 4000A Dawning Gaming Company (B) 356,428 Digital China Ltd. 473 Chinese Academy of Science China DeepComp 6800 lenovo Unis Digital Co. Ltd. 并行计算机的性能的发展并行计算机的性能的发展外插 Figure: Performance Development. 前 500 总的计算能力, 第一名的计算能力, 平均计算能力 Figure: Projected Performance Development. 前 500 总的计算能力, 第一名的计算能力, 平均计算能力

操作系统通信标准数据并行 :HPF 共享存储 :OpenMP 消息传递 :PVM, MPI 操作系统通信标准 Figure: Operating system family share 06/07 from www.top500.

3 操作系统通信标准数据并行 :HPF 共享存储 :OpenMP 消息传递 :PVM, MPI 操作系统通信标准 Figure: Operating system family share 06/07 from 操作系统通信标准只学习 MPI, 它适用于各种类型的机器, 如 cluster, constellation, MPP 良好的可移植性很好的可扩展性完备的异步通信功能有精确的定义, 从而为并行软件的发展提供了必要的条件 Fortran, Java, Basic, C, C++ Dongarra & Sullivan, Top ten the century, IEEE, in Science & Engineering, Jan./Feb., Why C++? It provides an object-oriented infrastructrue that accommodates a natural break down of the problem into a collection of data structures and operations on those structures. 面向对象的基本结适合把问题自然地分解成数据结构和这些数据结构上的操作 The use of C++ transcends many disciplines beyond engineering where the traditionally FORTRAN has been the prevailing language. C++ 的使用在很多学科都超过了 Fortran C++ is a language naturally compatible with basic algorithmic concepts of C++ 和基本算法概念相一致的一种语言 polymorphism 多态性 recursive function calling 递归 dynamic memory allocating 动态分配内存 encapsulation 封装 The Monte Carlo method 模拟随机现象 The Simplex method 线性优化问题 The Krylov subspace iteration for fast linear solvers and eigensolvers The Householder matrix decomposition to express a matrix as a product of simpler matrices 1957: The FORTRAN compiler that liberated scientists and engineers from programming in assembly : The QR algorithm to compute many eigenvalues 1962: The Quicksort algorithm to put things in numerical or alphabetical order fast 1965: The Fast Fourier Transform to reduce operation count in Fourier series representation 1977: The Integer relation detection algorithm, which is useful for bifurcations and in quantum eld theory 1987: The fast multipole algorithm for N-body problems

4 科学计算数值模拟一些算法的并行实现是显而易见的, 如两个向量相加 c i = a i + b i ; i = 1; 2; ; n 一些算法是需要适当的通信, 如两个向量的内积 d = P n i=1 a ib i 一些算法的并行实现看起来是不可能的如向量要计算 ~x = (1; 2; 3; 4; 5; 6; 7; 8; 9; 10; ) ~y = (1; 3; 6; 10; 15; 21; 28; 37; 40; ) < ++ >, 其中 y i = P i j=1 x j. 使用 MPI_SUM 操作的 MPI_Scan 函数就实现了上面计算的并行算法从 Real world problem 得到数学模型数值求解数学方程偏微分方程数值解有限差分有限元谱方法最优化数值代数线性方程组的求解求矩阵的特征值, 奇异值对方程的解的分析和可视化并行计算显然是一个交叉学科, 涉及的内容很多 C++, 面向对象的编程语言 MPI(MPICH), 并行通信的标准 ( 实现 ) Trilinos C++ 编写的数值代数算法的并行实现 Epetra 提供对 MPI 函数的 C++ 接口提供 BLAS,LAPACK 库的 C++ 接口提供向量矩阵的各种分布存储和操作的并行实现 Teuchos and Triutils: 两个辅助的类 AztecOO: 求解稀疏线性方程组的 Krylov 子空间迭代法 IFPACK: 不完全 LU 分解等预优 ML: 多重网格预优学习方法 google, 寻找可利用的资源读代码, 看文档写程序, 做练习千里之行, 始于足下介绍很简单, 但是能够提供一个脚手架通过这个介绍, 你可以使用 C++ 这个工具 You will understand more about it 任何编程语言 = 数据 + 操作解决实际工程问题是确定什么是相关数据, 做什么操作才得到想要的结果假设我们已经知道数据和操作, 编程就是把这些数据和操作翻译成编程语言

5 Main function 主函数一个简单的 non-trivial C++ 程序 #include<iostream> 计算机开始程序的地方 main() 一个简单的程序 int main(){ std::cout <<``Hello World!''<<std::endl; int main(){ } } main() 就是计算开始计算的起点编译 : fg 内部分就是 main 函数的函数语句这个例子是空就是函数什么都不做 g++ -c -o hello.o hello.cpp 链接 : g++ -o hello.exe hello.o 运行 :./hello.exe C++ 类的例子 :I 函数 : 算法的抽象类 : 数据和数据之上的操作的抽象函数的声明 float func(float x); 函数名字, 输出, 输入 ( 参数 ) 函数体 float func(float x){float y; y =2*x; return y}; 函数在调用之前必须先声明 #include <math.h> class My{ private: int length_; double *data_; public: My(int n){ length_ = n; data_ = new double[n]; }; ~My(){ delete[] data_; }; int length(){return length_; }; const double & operator[] (const int i) const {return data_[i];}; double & operator[](const int i) {return data_[i];};

6 C++ 类的例子 :II C++ 类的例子 :III double norm2(){ double norm = 0.0; for(int i=0;i<length_;i++) norm+=data_[i]*data_[i]; return sqrt(norm); } }; // 这个分号是不可缺少的 #include <iostream> int main(){ My vec(5); for(int i =0; i<vec.length(); i++) vec[i] = i*100.0; std::cout<<"the vector is "<<std::endl; for(int i =0; i<vec.length(); i++) std::cout << vec[i]<< " "; std::cout<<std::endl; std::cout<<"the 2-norm of the vector is " <<vec.norm2()<<std::endl; return 1; } 编译 :g++ -lm -o a.exe a.cpp 运行结果 : tlu:lecture$./a.exe The vector is The 2-norm of the vector is 类定义中的一些概念构造函数 :A constructor is the rst method which is called when an object is instantiated. 析构函数 :A destructor is the method called prior to an object being deleted. Some methods modify the data contained within the oject, while others do not. overloaded operators Getting Past ;, and fg Basic Data Type, int, long, oat, double, char, Basic Operations, +,-,*,/, %, Bool Expressions, a&&b, ajjb, a > b, if 语句,for 语句输出, 输入

7 is much faster than main memory Fortran column-major-order storage C++ row-major-order storage Matrix-Times- Example cache 的使用我们无法控制, 能做得就是尽量使得一次操作装入的数据和 cache 长度大小比较匹配尽量多用 BLAS Level 3 函数, 少用 BLAS Leve 2 or 1. 上面的建议参考 Scientic in C++ and MPI 的第 60 页 = 表示赋值, 不是表示方程. Given ~x0, ~x1,, ~x n 1, nd ~q0, ~q1,, ~q n 1 which are orthogonal to each other and whose norms are unity and they expand the same space as ~x i. ~q 0 = ~x 0 =jjxjj2 将第 i 个向量减去它在前 i P i 1 ~yi = ~xi qi = ~y i jj~y i jj 2 1 个向量 ~q 上的投影 j=0(~q T j ~x i)qj, i = 1; 2; ; n 1 Summarize the algorithm as follows Modied Initialize: Compute r00 = jj~x0jj2. If r00 = 0, STOP, else ~q0 = ~x0=r00. Begin Loop: For i = 1; ; n P 2 ~yi = i 1 ~xi j=0 r ij ~q j 1 Do: 1 Compute rij = ~q T j ~x i ; j = 0; ; i 1 3 ri = jj~yijj2 4 If rii = 0, STOP, else ~qi = ~yi=ri End Loop. Given ~x0, ~x1,, ~x n 1, nd ~q0, ~q1,, ~q n 1 which are orthogonal to each other and whose norms are unity and they expand the same space as ~x i. 差别之处 ~q 0 = ~x 0 =jjxjj2 ~zi = ~xi Begin Loop for j = 0; 1; ; i 1 Do: 数学上 Modied GS 和 GS 是等价的, 因为 qj 之间相互正交, 但数值上这种策略更好 ~yi = ~zi ~zi = ~yi End Loop 差别之处的尾 ~q i = ~y i jj~yijj 2 (~q T j ~z i)qj

8 Algorithm Initialize: Compute r00 = jj~x0. If r00 = 0, STOP, else ~q0 = ~x0=r00. Begin Loop: For i = 1; ; n 1 Do: 1 Classical GS 的头 2 rij = (~qj ; ~xi) P 3 ~yi = i 1 ~xi j=0 r ij ~qj 4 Classical GS 的尾 5 修正 GS 算法和 classic GS 算法差别之处 : ~yi = ~xi Begin Loop: For j = 0; ; i Compute rij = ~q j T ~y i, ~yi = ~yi End Loop. 6 差别之处的尾 7 rjj = jj~yjjj2 rij ~qj 8 If rjj = 0, STOP, else ~qj = ~yj =rjj End Loop. 1 Do: i 阅读课本第一章浏览网站安装 ubuntu 操作系统阅读我博客中的例子 :C++ 程序的一个例子和常见错误以及调试工具 valgrind 的使用运行上面程序中的例子, 比较和 Modied 两种算法输出结果的不同 Use the classical and the modifed Gram- Schmidt algorithms to orthonormalize the vectors x0 = (1; 10 4 ; 0); x1 = (1; 0; 10 4 ): Comparte the two results. What do you observe? 作业要求 : 后三项要写出报告来, 可以上传到我的 ftp 上

1 2 3 操作系统通信标准 Introduction to C++ Learning the Syntax and Other Basic Commands Cache Gram-Schmidt Vector Orthogonalization 9

1 2 3 操作系统通信标准 Introduction to C++ Learning the Syntax and Other Basic Commands Cache Gram-Schmidt Vector Orthogonalization 9 Introduction to Department of Science and Engineering School of Mathematics School Peking University August 9, 2007 1 2 3 操作系统通信标准 4 5 6 7 8 Introduction to C++ Learning the Syntax and Other Basic Commands