教学材料请访问北大计算机系课件中心current course website
课程名称： 并行处理（原名“并行程序设计”）
课程编号：
课程类型： 研究生或高年级本科生任选课 (对全校理科专业开放)
所属学科： 计算机科学与技术
领域方向： 计算机系统结构，高性能计算
学时学分： 54学时，3学分
主讲教员： 李晓明
先修要求： 计算引论, 计算机系统结构, 操作系统，程序设计
同修要求： 无
版本号及修订时间：2，（2001年6月）
版本更新历史：1999年10月制定第一版本，80%的内容和并行程序设计技术直接相关。在当前版本中，尽管并行程序设计技术依然占有相当的部分（约50%）,但加强了并行计算机系统结构和并行算法相关的内容。
基本目的：
1. 使学生从系统结构、算法、程序设计三个方面（层次），系统概要地了解并行处理的基本概念和涉及的各种学术和技术问题。
2.
使学生掌握在分布式存储系统环境下的SPMD程序设计模型。
3.
使学生对MPI（Message Passing Interface）有一个较透彻的认识和一定的并行程序设计经验。
学习收获：通过本课程的学习，学生将会有以下收获：
1．
解高性能计算领域人们关心的问题和在系统结构，算法和程序设计技术等方面解决这些问题的途径；对并行计算，尤其是对基于分布存储系统的并行计算技术有一个较全面的理解。这样的理解有助于从事“计算物理”，“计算流体力学”等方向工作的人员做出更大规模、更高水平的工作。
2．
对Message Passing Interface系统有一个较深入的掌握，并通过一定量作业获取进行并行程序设计的实际经验. 这样的经验对于开发数据量大、运行时间长的科学研究与工程应用方面的程序将是很有价值的。
3．
同时，从计算机专业的角度出发，本课程也强调基于一定的抽象（例如某种层次的消息通信接口）实现较高层并行程序设计环境（例如并行库）的要点。
内容提要：
1.
并行计算与并行程序设计的基本概念: 通过4个典型的实际例子，了解并行处理的必要性和可能带来的好处，以及并行处理的适用性和局限性.
掌握：“双机R/C并行处理模型”；程序执行时间和算法复杂性、输入数据量之间的相互关系；Amdahl定律，加速比的不同表示方式，几种不同的可扩展性概念
了解：并行处理发展的历史脉络，Ocean, Barnes-Hut,
Ray Tracing, Data Mining应用问题的基本算法和并行计算的基本特征。
2.
并行计算机系统结构的基本概念，包括“共享存储”，“消息通信”，SMP，DSM，NUMA，UMA, NORMA，高速缓存一致性，存储同一性，等等（6学时）
掌握：从节点配置，互连关系，地址空间的性质，存储访问的特征等方面，区别SMP, MPP, DSM, 和COW的体系结构；高速缓存一致性问题的起源和主要解决思路
了解：存储同一性问题的起源，SC模型的概念和保证条件
3.
典型并行算法设计与分析的模型，包括PRAM, LogP, BSP，Systolic等
掌握：PRAM模型的精神及其局限性，LogP模型，BSP模型
了解：Systolic模型的要点及其适用性
4.
MPI概述: MPI是并行计算研究领域的最重要的成果之一，我们将介绍它的发展背景、过程以及最基本的思想。
掌握：MPI的起源，相关的历史背景
了解：MPI提供的基本设施轮廓
5.
点对点通信：所有消息传递系统的基础与核心
掌握：send/receive的参数设计，操作的“执行”和“完成”的区别，ANY_TAG,
ANY_SOURCE的作用及其对安全性的影响；“缓冲区可重用”和“数据已被接收”的区别
了解：阻塞与非阻塞的区别；标准，缓冲，同步，准备好等四种模式
6.
集体通信，MPI的数据类型，进程拓扑结构
掌握：barrier的用途和实现方式，广播、分发、收集操作；用户自定义数据类型的含义及其步骤；Cart拓扑结构，communicator的概念
了解：scan操作，reduce操作；一般拓扑结构的构造方法；inter communicator
7.
并行IO，并行库的建立技术
掌握：并行I/O的概念，以数据类型的方式定义文件视图的方法，并行I/O的基本操作；并行库中的安全问题，以及communicator概念对构造安全并行库的支持
了解：由并行I/O带来的数据共享问题及其处理方法（Atomicity, Synch），以矩阵相乘为代表的复杂数据移动模式，subarray,
distr_array数据类型
8.
场问题、粒子问题、典型线性代数问题的并行算法
掌握：数据划分的考虑因素，阴影区的使用，数据局部性开发的原理和方法；
了解：附加通信发生的原因和减少的措施；半静态数据划分的场合及原则
进度安排参考意见
第一周 并行处理的意义，它在计算机科学技术，以及科学发展中的地位和作用
第二周 评价并行处理效能的指标，并行处理的适用性和局限性
第三周 现代并行计算机系统结构分类
第四周 高速缓存一致性，存储同一性的概念和要点
第五周 PRAM模型
第六周 LogP和BSP模型
第七周 MPI概览
第八周 点对点通信初步
第九周 点对点通信的不同模式
第十周 集体通信:广播，分发，收集，规约
第十一周 用户自定义的数据类型
第十二周 进程组的拓扑结构
第十三周 并行I/O的概念
第十四周 MPI提供的并行I/O设施
第十五周 建立并行程序库的若干问题，安全，等等
第十六周 典型场问题（Ocean）的并行求解
第十七周 典型粒子问题（n-body,Barnes-Hut算法）的并行求解
第十八周 典型线性代数问题的并行求解
教学方式：
课堂讲授和网络辅助相结合. 每周讲授3学时, 讲义和辅助材料通过网络发布, 作业提交通过网络进行.
教材或参考书：
1.
David E. Culler, Jaswinder Pal Singh, Parallel Computer Architecture. Morgan
Kaufmann, 1999. 第二章、第三章、第五章的一部分。
2.
陈国良, 《并行计算--结构、算法、编程》, 高等教育出版社（面向21世纪课程教材）,1999年10月。
3.
Marc Snir 等，MPI: The Complete Reference. The MIT Press, 1996。
4.
MPIF, MPI-2: Extensions to the Message-Passing Interface, 1997。
学生成绩评定方法: 10次作业, 一次期末考试. 作业占总成绩的20%.
资源需求: （1）本课程通常选修学生在30左右，鉴于有较多作业，希望安排一个助教；（2）由于作业内容涉及到实际的并行程序设计, 要求每个学生有使用MPI并行计算环境的条件，为完成10次作业, 大约需要40小时的机时.
课程建设规划：
目前，本课程已在北大开出三次，积累了一定的经验和素材；争取在十五期间编写一本教材。