《高性能计算机系统导论》教学大纲

一、课程的性质、目的与任务

本课程是为计算机科学与技术专业、网络工程和软件工程的高年级本科生开设的专业课，也可作为面向科学和工程计算的非计算机专业的高年级本科生和研究生的选修课程。通过此课程的学习，可使学生了解和掌握计算机学科中以及大型科学与工程问题中的基本的并行与分布计算方法及其软硬基础。

二、课程教学基本内容

第一篇 并行计算硬件基础

第一章 并行计算机系统及其结构模型

1.1 并行计算

1.1.1 并行计算与计算科学

1.1.2 当代科学与工程问题的计算需求

1.2 并行计算机系统互连

1.2.1 系统互连

1.2.2 静态互连网络

1.2.3 动态互连网络

1.2.4 标准互连网络

1.3 并行计算机系统结构

1.3.1 并行计算机结构模型

1.3.2 并行计算机访存模型

1.3.3 并行计算机存储组织

第二章 当代并行计算机系统介绍

2.1 共享存储多处理机系统

2.1.1 对称多处理机SMP结构特性

2.1.2 CC-NUMA Origin 2000超级服务器

2.2 分布存储多计算机系统

2.2.1 大规模并行处理机MPP结构特性

2.2.2 ASCI Option Red MPP系统

2.3 机群系统

2.3.1 大规模并行处理系统MPP机群SP2

2.3.2 工作站机群COW

2.3.3 Berkeley的NOW计划

第三章 并行计算性能评测

3.1 并行计算机的一些基本性能指标

3.1.1 CPU和存储器的某些基本性能指标

3.1.2 通信开销

3.1.3 机器的成本、价格与性能/价格比

3.2 加速比性能定律

3.2.1 Amdahl定律

3.2.2 Gustafson定律

3.2.3 Sun和Ni定律

3.2.4 有关加速的讨论

3.3 可扩放性评测标准

3.3.1 并行计算的可扩放性

3.3.2 等效率度量标准

3.3.3 等速度度量标准

3.3.4 平均延迟度量标准

3.3.5 有关可扩放性标准的讨论

3.4 基准测试程序

3.4.1 基本的测试程序

3.4.2 数学库测试程序

3.4.3 并行测试程序

第二篇 并行算法的设计

第四章 并行算法的设计基础

4.1 并行算法的基础知识

4.1.1 并行算法的定义和分类

4.1.2 并行算法的表达

4.1.3 并行算法的复杂性度量

4.1.4 并行算法中的同步与通信

4.2 并行计算模型

4.2.1 PRAM模型

4.2.2 异步PRAM模型

4.2.3 BSP模型

4.2.4 logP模型

4.2.5 对BSP和logP的评注

第五章 并行算法的一般设计策略

5.1 串行算法的直接并行化

5.1.1 设计策略描述

5.1.2 快排序算法的并行化

5.2 从问题描述开始设计并行算法

5.2.1 串匹配算法

5.2.2 KMP串行串匹配算法

5.2.3 并行串匹配算法的设计思路

5.3 借用已有算法求解新问题

5.3.1 设计策略描述

5.3.2 利用矩阵乘法求所有点对间最短路径

第六章 并行算法的基本设计技术

6.1 划分设计技术

6.1.1 均匀划分技术

6.1.2 方根划分技术

6.1.3 对数划分技术

6.1.4 功能划分技术

6.2 分治设计技术

6.2.1 双调归并网络

6.2.2 凸壳问题

6.3 平衡树设计技术

6.3.1 求取最大值

6.3.2 计算前缀和

6.4 倍增设计技术

6.4.1 表序问题的计算

6.4.2 求森林的根

6.5 流水线设计技术

6.5.1 一维心动阵列上的DFT计算

6.5.2 一维心动阵列上的卷积计算

第七章 并行算法的一般设计过程

7.1 PCAM设计方法学

7.2 划分

7.2.1 域分解

7.2.2 功能分解

7.2.3 划分判据

7.3 通信

7.3.1 局部通信

7.3.2 全局通信

7.3.3 非结构化、动态和异步通信

7.3.4 通信判据

7.4 组合

7.4.1 增加粒度

7.4.2 保持灵活性和减少软件工程成本

7.4.3 组合判据

7.5 映射

7.5.1 负载平衡算法

7.5.2 任务调度算法

7.5.3 映射判据

第三篇 并行数值算法

第八章 基本通信操作

8.1 选路方法与开关技术

8.1.1 选路方法

8.1.2 开关技术

8.2 单一信包一到一传输

8.3 一到多播送

8.3.1 使用SF进行一到多播送

8.3.2 使用CT进行一到多播送

8.4 多到多播送

8.4.1 使用SF进行多到多播送

8.4.2 使用CT进行多到多播送

第九章 稠密矩阵运算

9.1 矩阵的划分

9.1.1 带状划分

9.1.2 棋盘划分

9.2 矩阵转置

9.2.1 棋盘划分的矩阵转置

9.2.2 带状划分的矩阵转置

9.3 矩阵-向量乘法

9.3.1 带状划分的矩阵-向量乘法

9.3.2 棋盘划分的矩阵-向量乘法

9.4 矩阵乘法

9.4.1 简单并行分块乘法

9.4.2 Cannon乘法

9.4.3 Fox乘法

9.4.4 DNS乘法

第十章 线性方程组的求解

10.1 三角形方程组的求解

10.1.1 基本术语

10.1.2 上三角方程组的求解

10.2 三对角方程组的求解

10.2.1 三对角方程组直接求解法

10.2.2 三对角方程组奇偶归约求解法

10.3 稠密线性方程组的求解

10.3.1 有回代的高斯消去法

10.3.2 无回代的高斯-约旦法

10.3.3 迭代求解的高斯-赛德尔法

10.4 稀疏线性方程组的求解

10.4.1 稀疏矩阵的存储方式

10.4.2 雅可比迭代法

10.4.3 高斯-赛德尔迭代法

10.4.4 超松弛迭代法

10.4.5 多重网格法

10.4.6 共轭梯度法

第十一章 快速傅里叶变换

11.1 离散傅氏变换

11.1.1 预备知识

11.1.2 离散傅里叶变换

11.1.3 离散傅里叶逆变换

11.1.4 离散傅氏变换的蝶式计算

11.2 快速傅氏变换串行算法

11.2.1 串行FFT迭代算法

11.2.2 串行FFT递归算法

11.3 并行FFT算法

11.3.1 SIMD-MC2上FFT算法

11.3.2 SIMD-BF上FFT算法

11.3.3 SIMD-CC上FFT算法

11.3.4 MIMD-DM上FFT算法

第四篇 并行程序设计

第十二章 并行程序设计基础

12.1 并行程序设计概述

12.1.1 串行程序设计与并行程序设计

12.1.2 并行程序设计环境与工具

12.1.3 并行程序设计方法

12.1.4 并行编程风范

12.2 进程

12.2.1 进程的基本概念

12.2.2 进程的并行执行

12.2.3 进程的相互作用

12.3 线程

12.3.1 线程的基本概念

12.3.2 线程的管理

12.3.3 线程的同步

12.4 同步

12.4.1 原子与互斥

12.4.2 高级同步结构

12.4.3 低级同步原语

12.5 通信

12.5.1 影响通信系统性能的因素

12.5.2 低级通信支持

12.5.3 TCP / IP通信协议组简介

12.6 并行程序设计模型

12.6.1 计算π样本程序

12.6.2 隐式并行模型

12.6.3 数据并行模型

12.6.4 消息传递模型

12.6.5 共享变量模型

12.6.6 并行程序设计模型比较

第十三章 共享存储系统并行编程

13.1 基于共享变量的共享存储并行编程

13.1.1 共享存储并行编程的基本问题

13.1.2 共享存储编程环境

13.2 早期共享存储并行编程模型

13.2.1 ANSI X3H5共享存储模型

13.2.2 POSIX线程模型

13.3 OpenMP编程简介

13.3.1 OpenMP概述

13.3.2 OpenMP编程风格

13.3.3 OpenMP编程要素

13.3.4 OpenMP计算实例

13.3.5 运行库例程与环境变量

第十四章 分布存储系统并行编程

14.1 基于消息传递的并行编程

14.1.1 SPMD并行程序

14.1.2 MPMD并行程序

14.2 MPI并行编程

14.2.1 最基本的MPI

14.2.2 群体通信

14.2.3 通信体

14.2.4 导出数据类型

14.2.5 点到点通信

14.3 PVM并行编程

14.3.1 PVM概貌

14.3.2 PVM消息传递库

14.4 基于数据并行的并行编程

14.4.1 数据并行模型的特点

14.4.2 数据并行编程的基本问题

14.5 HPF并行编程

14.5.1 HPF的语言特点

14.5.2 HPF的数据并行机制

14.5.3 HPF使用中的若干问题

第十五章 并行程序设计环境与工具

15.1 软件工具与环境

15.1.1 编码工具

15.1.2 软件工程工具

15.1.3 集成工具

15.1.4 将来的工具与环境

15.2 并行编译器

15.2.1 编译及其并行化

15.2.2 相关分析

15.2.3 代码优化

15.2.4 代码生成

15.3 并行程序调试

15.3.1 并行程序调试的方法与步骤

15.3.2 并行程序的调试技术

15.3.3 并行程序的性能调试

15.4 并行程序性能分析

15.4.1 并行程序的性能预测

15.4.2 并行程序的性能监控

15.4.3 并行程序的性能可视化

15.5 图形化并行程序集成开发环境

15.5.1 并行程序的可视化设计环境与工具

15.5.2 图形应用开发环境GRADE的组成

15.5.3 GRADE中开发并行程序过程

三、课程各章节学时分配

四、本课程课外学习与修学指导

由于该课程涉及高性能计算机系统中各种软硬件资源的管理，内容复杂，难度较大，且具有很强的实践性，所以要学好本课程，必须做到理论与实践紧密结合，才能达到较好的学习效果。要求学生多参阅相关书籍，多做练习，多上机实验，掌握高性能计算机系统的基本原理、主要算法及其实现过程。

五、本课程考核方式及成绩评定标准

考核方式：闭卷考试

成绩评定方法：本课程的考核是平时成绩、实验成绩和期终考试成绩相结合。具体比例为：上课出勤、作业占20%，实验占20%，期末考试成绩占60%。

其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：选择题、填空题、简答题、计算题、算法题、分析题、综合应用题等。

六、教材及参考书

教材：陈国良，《并行计算：结构，算法，编程》，北京：高教出版社，1999(初版)，2003(修订版)

主要参考书：

[1]陈国良等，《并行计算机体系结构》，北京：高教出版社，2002

[2]陈国良，《并行算法的设计与分析》，北京：高教出版社，2002 (修订版)

[3]陈国良等，《并行算法实践》，北京：高教出版社，2003

大纲撰写人：彭东海

大纲审阅人：袁辉勇

教学副主任：易叶青

编写日期：2012.6