节200411月18日讲义课件.ppt

《节200411月18日讲义课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行处理与体系结构哈尔滨工业大学计算机科学与技术学院第一章并行计算机模型1计算技术的现状2多处理机和多计算机3多向量机和SIMD计算机4并行计算机的抽象模型5可扩展的范围和设计哈尔滨工业大学计算机科学与技术学院4并行计算机的抽象模型并行计算机的理论模型是从物理模型抽象的；为开发并行算法提供了一种方便的框架；用这些模型可求得并行计算机的理论性能界限；可在芯片制作前估算芯片区的VLSI复杂性和执行时间。哈尔滨工业大学计算机科学与技术学院一、时间与空间复杂性计算机求解一个规模为s的问题的算法复杂性取决于：执行

2、时间存储空间哈尔滨工业大学计算机科学与技术学院时间复杂性：时间复杂性g(s)为O(f(s))，可读作“数量级为f(s)”，如存在正的常量c和s0，则对所有s>s0的非负值就有g(s)≤cf(s)。哈尔滨工业大学计算机科学与技术学院空间复杂性为问题规模s的函数。渐近空间复杂性(asymptoticspacecom—plexity)主要与大问题的数据存储有关，而程序(代码)存储的需求和输入数据的存储不考虑在内。串行算法的时间复杂性简称为串行复杂性;并行算法的时间复杂性就称为并行复杂性;并行复杂性应比串行复杂性低，至少是

3、相近。只考虑确定性算法。哈尔滨工业大学计算机科学与技术学院NP完全性：P类(即多项式类)：具有多项式复杂性算法的问题集，如果存在一多项式p(s)，对任何问题规模s的时间复杂性为O(p(s))，则某算法即具有多项式复杂性。NP类(即不确定性多项式类)：能以多项式时间，用不确定性算法求解的问题集。PNP确定性算法是不确定算法的特殊情况。P类问题是计算易解的，而NP-P类问题是难解的。哈尔滨工业大学计算机科学与技术学院现在不知道是否P＝NP或P≠NP。难解的NP类问题又称为具有指数时间复杂性的问题。哈尔滨工业大学计算机

4、科学与技术学院例题：多项式复杂性和指数复杂性算法：将几个数排序的多项式时间复杂性分别为O(nlogn)，属于P类对两个n×n矩阵相乘算法的多项式时间复杂性分别为O(n3)，属于P类。哈尔滨工业大学计算机科学与技术学院旅行推销员问题复杂性为O(n22n)和背包问题的复杂性为O(2n/2)指数复杂性问题是属NP类的：到目前为止还未发现这类问题的确定性多项式算法。哈尔滨工业大学计算机科学与技术学院P、NP和NPC（NP完全问题）哈尔滨工业大学计算机科学与技术学院二、并行随机存取机模型(ParallelRandom—Acc

5、essMachine，PRAM)目的：可用来开发并行算法和分析可扩展性及复杂性。哈尔滨工业大学计算机科学与技术学院MIMD细粒度严格同步零开销共享变量哈尔滨工业大学计算机科学与技术学院在PRAM上的一个并行程序由n个进程组成，其中第i个进程留驻在第i个处理器上，且由一串指令所组成。在每个基本时间步(称为周期)，每个处理器执行一条指令。这些指令包括数据传送、算/逻、控制流以及I/O指令，在典型的顺序计算机中均有这些指令。哈尔滨工业大学计算机科学与技术学院1.同构性规模为1的PRAM退化为传统的RAM。这种机器为SIS

6、D。当处理器多于1个时，一个PRAM将访问多个数据流，且通常可执行多个指令流。因此PRAM是一个MIMD机器。哈尔滨工业大学计算机科学与技术学院MIMD的特例:如果在每一周期，所有处理器必须执行相同指令，即只有一个指令流时，则PRAM就成为单指令(流)、多数据(流)(SIMD)机器。(SPMD)计算：单程序、多数据，所有进程执行同一程序，而由进程指标加以参数化。SIMD和SPMD间的差别是，在SPMD计算中，同一周期可以执行不同指令。哈尔滨工业大学计算机科学与技术学院2.同步性进程同步是严格的。PRAM是在指令级同

7、步的。哈尔滨工业大学计算机科学与技术学院3.交互机制这一属性描述了并行进程间如何相互影响行为的特性。在PRAM模型中，进程间通过共享变量(或共享存储器)进行交互。哈尔滨工业大学计算机科学与技术学院4.地址空间理论PRAM模型的一个重要特征是所有进程对所有存储单元均有相等的访问时间。这种机器为均匀存储器访问(UMA)。在多计算机中，每个处理机有它自己的分离地址空间。这些机器被称为具有多地址空间。多计算机的处理机间通信不是通过共享变量，而是借助消息传递。哈尔滨工业大学计算机科学与技术学院5.存储器模型各种方案的主要区别

8、在于如何协调CW的冲突。四种PRAM模型方案都与存储器读写如何处理有关。(1)EREW-PRAM模型——这种模型禁止一台以上处理机同时读、写同一存储单元(Snir，1982；Karp和Ramachandran，1988)。这是限制最大的PRAM模型。(2)CREW-PRAM模型——用互斥使写冲突避免。可以并行读同一存储单元。哈尔滨工业大学计算机科学与技术学院