第一章并行计算机模型 1计算技术的现状 2多处理机和多计算机 23多向量机和SMD计算机 (4并行计算机的抽象模型 (5可扩展的范围和设计 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 第一章 并行计算机模型 ◼ 1 计算技术的现状 ◼ 2 多处理机和多计算机 ◼ 3 多向量机和SIMD计算机 ◼ 4 并行计算机的抽象模型 ◼ 5 可扩展的范围和设计
4并行计算机的抽象模型 并行计算机的理论模型是从物理模型 抽象的; 为开发并行算法提供了一种方便的框 架 ■用这些模型可求得并行计算机的理论 性能界限; 可在芯片制作前估算芯片区的ⅥS|复 杂性和执行时间。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 4 并行计算机的抽象模型 ◼ 并行计算机的理论模型是从物理模型 抽象的； ◼ 为开发并行算法提供了一种方便的框 架； ◼ 用这些模型可求得并行计算机的理论 性能界限； ◼ 可在芯片制作前估算芯片区的VLSI复 杂性和执行时间
时间与空间复杂性 计算机求解一个规模为s的问题 的算法复杂性取决于: 执行时间 口存储空间 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼一、时间与空间复杂性 ◼计算机求解一个规模为s的问题 的算法复杂性取决于： ❑执行时间 ❑存储空间
时间复杂性: 时间复杂性g(s)为0(f(s),可读 作“数量级为f(s)”,如存在正的 常量c和s0,则对所有s>s0的非负 值就有g(s)≤cf(s)。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 时间复杂性： ◼ 时间复杂性g(s)为O(f(s))，可读 作“数量级为f(s)”，如存在正的 常量c和s0，则对所有s>s0的非负 值就有g(s)≤ cf(s)
空间复杂性 为问题规模s的函数。 a渐近空间复杂性( asymptotic spacecom plexity)主要与大问题的数据存储有关,而程 序(代码)存储的需求和输入数据的存储不考虑 在内。 串行算法的时间复杂性简称为串行复杂性; 并行算法的时间复杂性就称为并行复杂性; 并行复杂性应比串行复杂性低,至少是相 近 只考虑确定性算法。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 空间复杂性 ◼ 为问题规模s的函数。 ❑ 渐近空间复杂性(asymptotic spacecom— plexity)主要与大问题的数据存储有关，而程 序(代码)存储的需求和输入数据的存储不考虑 在内。 ◼ 串行算法的时间复杂性简称为串行复杂性; ◼ 并行算法的时间复杂性就称为并行复杂性; ◼ 并行复杂性应比串行复杂性低，至少是相 近。 ◼ 只考虑确定性算法
NP完全性: P类(即多项式类): 具有多项式复杂性算法的问题集,如果存在 多项式p(s),对任何问题规模s的时间复杂性为 0(p(s),则某算法即具有多项式复杂性 NP类(即不确定性多项式类):能以多项式时 间,用不确定性算法求解的问题集。 PCNP 口确定性算法是不确定算法的特殊情况。 P类问题是计算易解的,而NPP类问题是难 解的。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ NP完全性： ◼ P类(即多项式类)： ❑ 具有多项式复杂性算法的问题集，如果存在一 多项式p(s)，对任何问题规模s的时间复杂性为 O(p(s))，则某算法即具有多项式复杂性。 ◼ NP类(即不确定性多项式类)：能以多项式时 间，用不确定性算法求解的问题集。 ◼ PNP ❑ 确定性算法是不确定算法的特殊情况。 ◼ P类问题是计算易解的，而NP-P类问题是难 解的
现在不知道是否P=NP或P≠NP。 难解的NP类问题又称为具有指数时间 复杂性的问题。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 现在不知道是否P＝NP或P≠NP。 ◼ 难解的NP类问题又称为具有指数时间 复杂性的问题
例题:多项式复杂性和指数复杂性 算法 将几个数排序的多项式时间复杂性 分别为0( nlogn),属于P类 对两个n×n矩阵相乘算法的多项式 时间复杂性分别为0(n3),属于P类。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 例题：多项式复杂性和指数复杂性 算法： ◼ 将几个数排序的多项式时间复杂性 分别为O(nlogn)，属于P类 ◼ 对两个n×n矩阵相乘算法的多项式 时间复杂性分别为O(n3)，属于P类
旅行推销员问题复杂性为0(n22)和 背包问题的复杂性为0(2n2) 指数复杂性问题是属NP类的: 口到目前为止还未发现这类问题的确定 性多项式算法。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 旅行推销员问题复杂性为O(n22 n)和 背包问题的复杂性为O(2n/2 ) ◼ 指数复杂性问题是属NP类的： ❑ 到目前为止还未发现这类问题的确定 性多项式算法
P、NP和NPC(N完全问题) NP NP:不确定多项式时间类 NPC))P:多项式时间类 NPG:NP完全问题 推测NP,P和NPC类计算问题之间的关系 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 P、NP和NPC（ NP完全问题）