第一章并行计算机模型 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)主要与大问题的数据存储有关，而程 序(代码)存储的需求和输入数据的存储不考虑 在内。 ◼ 串行算法的时间复杂性简称为串行复杂性; ◼ 并行算法的时间复杂性就称为并行复杂性; ◼ 并行复杂性应比串行复杂性低，至少是相 近。 ◼ 只考虑确定性算法