《LecNote_2》由会员分享，可在线阅读，更多相关《LecNote_2（58页珍藏版）》请在金锄头文库上搜索。
1、第二讲 概述(2),概念：并行计算机、并行计算机模型 并行程序开发考虑 并行程序开发环境 问题的并行性 计算任务的划分 计算任务的通行、同步 数据相关性、负载均衡问题 我们能从并行计算技术期待什么？,并行计算机,通常，一个计算系统的组成包括两部分硬件资源和软件资源 A parallel computer is a set of processors that are able to work cooperatively to solve a computational problem,硬件资源,第一层软件，例如OS内核,第二层软件，例如system functions,第三层软件，例如编译和运
2、行库,高层软件，例如用户程序,并行计算机两方面的含义,从硬件的拓扑结构的角度看 共享存储体系结构：UMA、NUMA 分布存储体系结构：CLUSTER (UP) 分布-共享存储体系结构：CLUSTER (SMP/multi-core) 从硬件的行为特征的角度看 MISD SIMD MIMD,并行计算机的分类：Flynn分类法(行为特征),SIMD,处理器阵列机、向量机: CELL、GPU 适用于非常规则的计算，例如：视频、音频处理的MPEG算法；密集矩阵的运算,MISD,很少见,MIMD,最常见的并行计算机,常见的并行机存储体系结构,共享存储体系结构 UMA(当前主要是SMP) NUMA(通常多
3、个SMP互联),分布存储体系结构,分布-共享的混合存储体系结构 当前、以及今后一段时间里的并行机主流结构 北大科学工程中心的两台超级计算机均采用该体系结构 IBM RS/6000 SP3：4节点，每个节点16颗CPU HP Cluster：128节点，每个节点2颗CPU 基于Cache的multi-core 一个CPU中有多个执行核(execution core) 每个执行核有自己独立的一级cache,FP Unit,FP Unit,Exe Core,Exe Core,L1 Cache,L1 Cache,L2 Cache,System Bus,Intel Core微架构,基于DMA的multi
4、-core,并行计算与分布式计算的差异,分布式计算: 多台计算机利用网络通信进行协作, 共同完成某一项任务. 这些机器可以是同时做不同的子任务, 也可以是按工作流方式依次做不同的子任务. 运行平台在地理上的分布特征. P2P: 完成文件数据的共享 WEB: 完成信息检索 并行计算: 多个处理器执行部件(执行核)协作, 共同完成某一项任务. 各个执行部件同时工作, 分别做不同的子任务. 这些执行部件可以在相同的计算机上 (MPP/SMP/多核处理器), 也可以在不同的计算机上(此时是一种形式的分布式计算). 子任务的执行顺序特征,并行计算,分布式计算,硬件的行为取决于软件,A parallel
5、machine model is an abstract parallel computer from the programmers viewpoint, analogous to the von Neumann model for sequential computing,硬件资源：共享/分布/分布-共享存储体系结构,第一层软件，例如OS内核,第二层软件，例如system functions,第三层软件，例如编译和运行库,高层软件，例如用户程序,程序员看到的计算机：编程模型(编程语言、函数包的API),编程模型：编程语言、函数包API,可执行程序：SIMD/MIMD/MISD,常见的并行编
6、程模型,站在程序开发的角度，把并行计算机划分成两类 多处理器multi-processor：程序运行时，只有一个进程，其中可以包括多个并发运行的线程 进程：OS的资源分配单位。一个进程有一个存储空间，进程的所有操作都是在这个存储空间上进行的 线程：处理器资源的调度单位 多计算机multi-computer ：程序运行时，有多个进程 每个进程存储程序的一部分数据、执行一部分计算任务 进程之间有协作：同步、交换数据 Multi-processor 并发threads pthreads：POSIX并发线程模型 OpenMP CELL BE线程模型 PRAM (Parallel Random Acce
7、ss Machine：理论模型),Multi-computer Message passing Data parallel BSP (Bulk Synchronous Parallelism：理论模型；同时定义了一个函数包，可以用于并行程序开发) 并行程序的代码结构 SPMD：Single Program Multiple Data。编写一个程序，求解不同的子任务。不同的子任务，执行的控制流不同 控制转移、分支pthread、OpenMP、 Data parallel、 Message passing(通常用SPMD并行程序) MPMD： Multiple Program Multiple D
8、ata。编写多个程序，分别求解不同的子任务 CELL BE线程模型、 Message passing(支持MPMD并行程序) 理论模型：分析算法的复杂性，指导并行算法设计和程序性能优化,Disk,Network interface circuitry,A custom-designed circuitry that interfaces a commodity microprocessor to C, M, D, NIC,程序员眼中的Multi-processor,有一个全局的存储空间 每个处理器都可以直接访问任何存储地址 用“锁”/“信号”的办法解决对共享变量的竞争,Shared Memor
9、y,Shared Disks,NIC,Interconnection network,C,NIC,C,C,Cache,M,Memory,D,P,Processor,NIC,shell,Threads model,a single process can have multiple, concurrent execution paths Master thread ( the main program ) performs: serial work; fork/join slave threads,每个线程分别由OS调度到不同的CPU上运行 从存储空间的角度，看线程之间的关系(与C程序对比) M
10、aster thread: main function Slave threads: subroutines called in the main function Master thread与slave threads共享存储空间 main function and the called subroutines share global variables Master thread与slave threads都可以有自己的私有数据 Both the main function and called subroutines can declare local variables,从程序运行行
11、为的角度，看线程之间的关系(与C程序对比) main function call一个subroutine后，停止自己的工作，直到 subroutine 执行完，再继续自己的工作 subroutine 在运行过程中独占global memory space的访问权 subroutine在运行结束后，可以通过返回参数将结果传递给main function的local memory space Master thread fork 一个slave thread后，继续做自己的工作，将与slave thread并发执行 slave thread只能将自己的结果写到global memory space
12、 每个thread访问global memory space时，需要考虑与其它thread的同步(“锁”、“信号量”),例子：计算小于N的全部素数,判断K是素数的算法：K不能被2，x之间的素数整数 x2 K (x+1) 2 K从3开始 并行程序 primes5000;/存储找到的素数 totalPrimes; /找到的素数总数 pthreads=0; /fork的线程总数 K = 3; main()k=3;primes0 = 2;primes1 = 3;totalPrimes = 1； 创建一组线程；searchPrimes();等待所创建的线程结束，此时pthreads=0； ,每个线程执行
13、 pthreads+; searchPrimes(); pthreads-; searchPrimes(): 从剩下的数据中取一个最小的数K，判断它是否为素数，直到小于等于N的全部数都判断完为止。算法的实现并不复杂，但需要使用 “锁”lock1：确保每个k只被取一次 “锁”lock2 ：确保每次只有一个线程在对pthread执行自增、自减运算 “锁”lock3 ：确保每次只有一个线程在对primes执行write操作 “信号量”signal：确保素数在primes中从小到大顺序存储 找到一个素数prime后，查看期待的下一个素数是否是prime，即：primestotalPrimes+1=pr
14、ime? 如果不是，等到primestotalPrimes+1被改变的信号出现 每个数字k在判断完成后，无论k是否是素数，都将期待的下一个素数的值置为K+1,Pthreads,定义了一个函数包，用来实现“锁”、“信号量”机制 支持用C开发并行程序,OpenMP,基于编译制导语句 为C/C+和Fortran分别提供了不同的接口 由并行编译器根据指导语句提供的信息，生成可执行的并行程序 有兴趣的同学可以继续读课程网站提供的资料,PRAM,在串行程序设计中，采用von Neumann computer刻画影响程序运行性能的关键因素。 串行程序的复杂性度量：程序中循环的迭代空间与问题规模N的关系，例如
15、O(N)、 O(NlogN)、 O(N2)、。 每个循环体运行一次的时间取决于 问题的特征：循环体需要的运算量 CPU的速度 MEMORY的数据存取速度 对于multi-processor 如何在算法设计和程序开发中解决存储一致性问题？ 如何衡量并行程序的性能？,PRAM试图对multi-processor进行抽象，刻画其中对性能其本质作用的特征 N个处理器 一个全局的内存空间，由N个处理器共享 每个处理器都可以通过系统总线直接访问共享内存中的任何元素 对存储空间中的任何元素，每个处理器的访问开销是相同的,时间t,PRAM上的并行程序,一个并行程序由N个process(进程?我觉得线程更合适)
16、组成，第I个进程位于第I个处理器上 每个进程是一组指令的线性序列 在每个时间步(basic time step/cycle)上，每个进程分别执行一条指令 数据传输指令 数学/逻辑运算指令 控制转移指令 I/O指令 NULL指令等 进程之间通过共享变量进行交互,共享内存的访问冲突问题一致性原则(consistency rule) EREW(exclusive read exclusive write)：每个CYCLE上，一个内存单元最多只能被一个进程访问 CREW(concurrent read exclusive write)：每个CYCLE上，一个内存单元可以被多个进程读，但最多只能被一个进程写 CRCW(concurrent read concurrent write)：每个CYCLE上，多个进程可以读、写同一个内存单元的数据，而当发生写冲突时，则采用预先确定的访问策略解决冲突问题 common: 所有进程写的数据相同 priority:由最优先的那个进程写数据 arbitrary: 允许任意处理器自由写,
