1、并行处理与体系结构哈尔滨工业大学计算机科学与技术学院第一章 并行计算机模型n 1 计算技术的现状n 2 多处理机和多计算机n 3 多向量机和 SIMD计算机n4 并行计算机的抽象模型n 5 可扩展的范围和设计哈尔滨工业大学计算机科学与技术学院4 并行计算机的抽象模型n 并行计算机的理论模型是从物理模型抽象的；n 为开发并行算法提供了一种方便的框架； n 用这些模型可求得并行计算机的理论性能界限；n 可在芯片制作前估算芯片区的 VLSI复杂性和执行时间。哈尔滨工业大学计算机科学与技术学院n一、时间与空间复杂性n计算机求解一个规模为 s的问题的算法复杂性取决于：q执行时间q存储空间哈尔滨工业大学计
2、算机科学与技术学院n 时间复杂性：n时间复杂性 g(s)为 O(f(s)，可读作 “ 数量级为 f(s)” ，如存在正的常量 c和 s0，则对所有 ss0的非负值就有 g(s) cf(s) 。 哈尔滨工业大学计算机科学与技术学院n 空间复杂性n 为问题规模 s的函数。q 渐近空间复杂性 (asymptotic spacecomplexity)主要与大问题的数据存储有关，而程序 (代码 )存储的需求和输入数据的存储不考虑在内。n 串行算法的时间复杂性简称为串行复杂性 ;n 并行算法的时间复杂性就称为并行复杂性 ;n 并行复杂性应比串行复杂性低，至少是相近。n 只考虑确定性算法。哈尔滨工业大学计算
3、机科学与技术学院n P类 (即多项式类 )：q 指确定型图灵机上的具有多项式算法的问题集合 q 具有多项式复杂性算法的问题集，如果存在一多项式 p(s)，对任何问题规模 s的时间复杂性为 O(p(s)，则某算法即具有多项式复杂性。n NP类 (即不确定性多项式类 )：q 非确定型图灵机上具有多项式算法的问题集合。q 脱离图灵机的概念， NP问题则是指那些其肯定解，能够在给定正确信息下在多项式时间内验证的判定问题。 哈尔滨工业大学计算机科学与技术学院n PNP： 确定性算法是不确定算法的特殊情况。n 现在不知道是否 P NP或 P NP。n 难解的 NP类问题又称为具有指数时间复杂性的问题。n NP完全（ NPC）q 一个判定问题 A称为是 NP完全的，如果对于NP中的每个问题 B， B多项式时间归约到 A，并且 A在 NP类中。哈尔滨工业大学计算机科学与技术学院n例题：多项式复杂性和指数复杂性算法：n将几个数排序的多项式时间复杂性分别为 O(nlogn)，属于 P类n对两个 n n矩阵相乘算法的多项式时间复杂性分别为 O(n3)，属于 P类。哈尔滨工业大学计算机科学与技术学院n旅行推销员问题复杂性为 O(n22n)和背包问题的复杂性为 O(2n/2 )n指数复杂性问题是属 NP类的：q到目前为止还未发现这类问题的确定性多项式算法。哈尔滨工业大学计算机科学与技术学院
