2020《并行算法》期末考试重点：路由传输与矩阵计算

"该资源是2020年期末考试的大纲，主要涵盖并行算法相关的知识，包括路由传输时间计算、矩阵计算、并行计算模型、并行算法设计技术等内容。考试题型包括填空、简答和设计并行算法。" 详细知识点： 1. **信包传输性能参数**： - 了解不同选路模式，如X-Y 选路、E-立方选路，以及它们的传输时间公式。 - 单一信包在不同传输模式下的时间计算，如SF (Store-and-Forward) 和 CT (Cut-through) 在一维环形网络中的传输时间。 2. **并行计算模型**： - 掌握并行计算机的分类，例如SISD、SIMD、MISD、MIMD等。 - 学习并行计算机的互连方式，包括静态互连（如LA、MC等）和动态互连（如Bus、Crossbar Switcher等）。 - 理解PRAM模型（SIMD-SM）、SIMD-IN模型、异步APRAM模型以及BSP模型等并行计算模型。 3. **并行算法性能分析**： - 理解并行算法的定义、表示方法（如par-do、forall）以及复杂度概念。 - 掌握运行时间t、处理器数目p、成本c、加速比s和并行效率E的计算。 - 学习工作量W的概念，并理解工作量最优和成本最优的重要性。 - 熟悉Brent定理在并行算法中的应用。 4. **并行算法设计技术**： - 了解并行算法的三种基本设计方法及其应用，如平衡树、倍增技术和分治策略。 - 掌握基本设计技术，如表序问题、森林根的计算、归并排序（包括均匀划分、对数划分、方根划分）以及流水线技术的应用。 5. **特定章节内容**： - Chap8涉及路由传输时间的计算，要求设计并行算法，分析其复杂度。 - Chap12关注矩阵计算，可能涉及并行化的矩阵运算。 - Chap13介绍Gauss-Seidel迭代法的并行实现，特别是红黑着色算法。 - Chap14涵盖串行FFT的蝶式递归计算和串行计算流图，以及SIMD-BF上的FFT算法和时间分析。 - Chap15讨论了p深度优先等算法在生成树和连通矩阵中的应用。 - Chap18讲解低度顶点部分独立集的问题，涉及到破对称技术。 - 补充内容涉及GPU计算，但仅限于概念，不涉及具体算法。 这些知识点构成了一个综合性的并行算法复习大纲，旨在帮助学生理解和掌握并行计算的关键概念、模型和设计技术。考试将测试学生对这些概念的理解和应用能力。