2016/6/27
《并行算法》 8 / Ch0
0.3 课程考核和评分要求

Examination and Grading
-Lessons & Answer: 5% -Paper: 25%
-Final written exam: 70%
2016/6/27
《并行算法》 9 / Ch0
主要内容
0.1 任课教师和课程主页 0.2 课程内容介绍 课程内容、特点和授课方式 教材和主要参考书目 课程在并行计算技术中的地位 0.3 课程考核和评分要求 0.4 并行计算介绍 什么是并行计算? 为什么需要并行计算? 几种实现方案 并行计算的粒度 并行计算的研究领域 TOP500和China TOP100 问题示例
large database and data mining, speech recognition, biology, image and signal processing, etc Computing-intensive applications: numerical simulation(e.g. forecasting, manufacturing, chemistry, aerodynamics) Network-intensive application Multicore and manycore and cloud computing
//综合：并发、分布、流水
//流水线 //分布

2016/6/27
《并行算法》 11 / Ch0
0.4 并行计算介绍: 为什么需要并行计算？(1)

Interest in parallelism since the very ancient era of computers(e.g. ILLIAC IV of 1967 had 64 processors) Parallel Processing is an effective answer for the tremendous future computing requirements. applications impulses: Data-intensive applications: videoconferencing, virtual reality,

Distributed memory multicomputers ($200,000400,000) Intel iPSC/860, NCUBE/2, Meiko Massively parallel processors ($5,000,000) Intel Paragon, TMC CM-5, CRAY T3D, IBM SP-2
并行图论算法
分布式算法
面向计算机专业
并行算法的设计与分析
并行算法类 课程实践
算法实现
并行算法实践
并行计算机 体系结构
算法应用基础
并行计算： 结构.算法.编程
面向计算机专 或计算科学的研
高性能计算导论
2016/6/27 《并行算法》 7 / Ch0
主要内容
0.1 任课教师和课程主页 0.2 课程介绍 课程内容、特点和授课方式 教材和主要参考书目 课程在并行计算技术中的地位 0.3 课程考核和评分要求 0.4 并行计算介绍 什么是并行计算? 为什么需要并行计算? 几种实现方案 并行计算的粒度 并行计算的研究领域 TOP500和China TOP100 问题示例
Parallel Algorithms
Chapter 0
Introduction
Spring, 2016
2016/6/27
《并行算法》 1 / Ch0
主要内容
0.1 任课教师和课程主页 0.2 课程介绍 课程内容、特点和授课方式 教材和主要参考书目 课程在并行计算技术中的地位


2016/6/27
《并行算法》 4 / Ch0
0.2 课程介绍: 内容、特点和学习方式
课程内容： 并行机结构模型、并行计算模型、并行算法基本知识； 非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等； 数值并行算法：矩阵运算、线性方程组求解、FFT算法等； 并行计算理论。 新增内容：多核计算和GPU上的并行算法 课程特点： 追求算法上界最优(并行计算时间、并行成本、加速比)； 强调严密的理论分析； 展现优秀的算法思想； 学习方式： 课程讲授、大作业和课堂讨论相结合

2016/6/27 《并行算法》 5 / Ch0
0.2 课程简介: 教材和主要参考书目
教材： 陈ຫໍສະໝຸດ 良, 并行算法的设计与分析（第3版）, 高等教育出版社,
2009.8

主要参考书目：
Kai Hwang,Zhiwei Xu”,Scalable Parallel
Computing”,McGraw-Hill,1998
课程主页 /~xuyun/pa.htm
《并行算法》 3 / Ch0


2016/6/27
主要内容
0.1 任课教师和课程主页 0.2 课程介绍 课程内容、特点和授课方式 教材和主要参考书目 课程在并行计算技术中的地位 0.3 课程考核和评分要求 0.4 并行计算介绍 什么是并行计算? 为什么需要并行计算? 几种实现方案 并行计算的粒度 并行计算的研究领域 TOP500和China TOP50 问题示例


2016/6/27
《并行算法》 12 / Ch0
0.4 并行计算介绍: 为什么需要并行计算？(2)

Grand challenges: Science today: experimentation, theory, simulation (or
computation)
Simulation relies heavily on parallel processing
Multi-Core PC, GPU (lowest cost) Cluster of workstations (lower cost) Multiprocessor workstations ($60,000) DEC Firefly, Apollo DN 10000, SUN SPARCstation 20 Shared memory multiprocessors ($200,000-400,000) Sequent Symmetry, Encore Multimax, SGI Challenge, SUN
2016/6/27
《并行算法》 15 / Ch0
0.4 并行计算介绍: 并行计算无处不在

并行计算时代已到来，将普惠天下大众 多核PC 国家高性能计算中心 我校和中国惠普联手共建高性能计算实验室 2003-07-11 / 并行计算无处不在 天气预报 电影电视制作 搜索引擎： 大型数据库 医药食品 汽车、飞机设计制造 大坝桥梁建造，防汛抗灾

处理器及加速器: Per node：16-core AMD Opteron 6274 processor

2016/6/27
《并行算法》 17 / Ch0
0.4 并行计算介绍: TOP500
2016/6/27
《并行算法》 18 / Ch0
0.4 并行计算介绍: TOP500
Titan: ORNL Supercomputer
陈国良, “并行计算：结构· 算法· 编程” 北京：高等教育出版社，
《并行算法》 6 / Ch0
0.2 课程简介 : 课程在并行计算技术中的地位 算法理论
可计算性与 计算复杂性 算法研究的 数学基础
专业博士生 面向计算机
算法设计与分析并行排序和 选择算法
并行算法类课 程教学网站
VLSI计算理论 与并行算法
0.3 课程考核和评分要求
0.4 并行计算介绍 什么是并行计算? 为什么需要并行计算? 几种实现方案 并行计算的粒度 并行计算的研究领域 TOP500和China TOP100 问题示例
2016/6/27
《并行算法》 2 / Ch0
0.1 任课教师和课程主页

任课教师 徐 云 xuyun@ 我的研究方向 大数据挖掘和生物信息学算法 并行编程模型及性能优化

2016/6/27
《并行算法》 10 / Ch0
0.4 并行计算介绍: 什么是并行计算？

A parallel computer is a “collection of processing elements that communicate and cooperate to solve large problem fast”. –-David E. Culler Or all processors cooperate to solve a single problem Daily life examples: House construction Car manufacturing Grocery store operation
J.JaJa,”Introduction to Parallel Algorithms”, Addison
Wesley,1992
A.Gramma et al, ”Introduction to Parallel
2011
2016/6/27
Computing”(Second Edition), 北京：机械工业出版社, 2003

Multicore and Manycore

In one words: Parallel processing promises increase of Performance(e.g. large, fast, cost) Reliability Large set of computational problems are inherently parallel in