Seminar课程

并行算法 / 计算机与软件学院 / 廖好

计算机科学从诞生至今七十年来,经历从电子管到大规模集成电路的若干研究发展阶段,高性能计算机系统一直是各国各行业发展的重要项目,成为衡量一个国家科技实力、民族智慧和行业硬实力的标志之一。受限于元器件的物理因素限制,计算机单机速度尽管仍在提高,但是已经逐步接近速度极限,因此单纯依靠提高硬器件速度已不可能达到所期望的高性能。各方学者和技术人员纷纷将高性能计算机的研究热点集中在并行计算上。

“并行计算”是21世纪由我校计算机与软件学院陈国良院士为首的团队提出的“并行算法类教学体系”中的核心内容之一,它是处于并行算法类教学体系中的算法应用基础层次,是面向计算机专业高年级学生或者从事计算科学的研究生的,是为了适应高性能计算机迅速发展的形势,满足我校培养21世纪高科技人才之需要。并行算法对降低问题的计算复杂性,改善其高效性和可维护性,提高服务的生产率,有着十分重要的意义。课程力求使学生理解并行算法设计思想,培养学生的并行算法分析和设计能力,为学生毕业后从事本专业范围内各项工作奠定坚实的理论和实践基础。

课程主要教材:

[1]     陈国良,并行算法的设计与分析(修订版),高等教育出版社,2002

[2]     陈国良等,并行计算机体系结构,高等教育出版社,2002

[3]     陈国良等,并行算法实践,高等教育出版社,2004

[4]     林闯. 随机Petri网和系统性能评价. 清华大学出版社. 2005

[5]     Ananth Grama. 并行计算导论. 机械工业出版社. 2003

[6]     C.Xavier, S.Iyengar, Introduction to Parallel Algorithms, 机械工业出版社, 2004

[7]     V.Kumar etal, Introduction to Parallel Computing, Benjamin/Cummings,1994 (影印本:2003

[8]     J.JaJa,"Introduction to Parallel Algorithms",Addison Wesley,1992

[9]     Kai Hwang,Zhiwei Xu",Scalable Parallel Computing",McGraw-Hill,1998

 

参考文献:

[1]     陈国良,并行算法类课程教学与基地建设,教育与现代化,19994)。

[2]     陈国良编著,并行算法——排序和选择,中国科学技术大学出版社,1990和台湾儒林图书公司,1992

[3]     陈国良,陈崚编著,VLSI计算理论与并行算法。中国科学技术大学出版社,1991和台湾儒林图书公司,1994

[4]     陈国良,唐策善,梁继发编著,并行图论算法。中国科学技术大学出版社,1991

[5]     陈国良,吴俊敏,章锋,章隆兵编著,并行计算机体系结构,高等教育出版社,2002

[6]     陈国良,安虹,陈崚,郑启龙,单久龙编著,并行算法实践,高等教育出版社,2004

[7]     陈国良编著,并行计算——结构·算法·编程(第二版),高等教育出版社,2003

[8]     陈国良编著,并行算法的设计与分析(第二版),高等教育出版社,2002

[9]     陈国良,安虹,计永昶,并行算法类实验教学建设与研究,高等理科教育,19995)。

[10]   陈国良 等编著,并行算法实践,高等教育出版社,2003

[11]   Andrews G R. Foundations of multithreaded parallel, and distributed programming, Pearson Education, 2002.

[12]   Blelloch, Guy E.; Maggs, Bruce M. "Parallel Algorithms" . USA: School of Computer Science, Carnegie Mellon University. 2015.

[13]   陈国良,陆克中,毛睿,廖好,周明洋,刘刚,李廉。大数据计算理论基础,高等出版社,In press.


(1) 并行计算模型 并行算法作为一门学科,首先研究的问题是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁,是并行算法设计和分析的基础。它屏蔽了并行机之间的差异,从并行机中抽取若干个能反映计算特性的可计算或可测量的参数,并按照模型所定义的计算行为构造成本函数,以此进行算法的复杂度分析。

并行计算模型的第一代是共享存储模型,如SIMD-SMMIMD-SM的一些计算模型,模型参数主要是CPU的单位计算时间,这样科学家可以忽略一些细节,集中精力设计算法。第二代是分布存储模型。在这个阶段,人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU,还有通信。因此如何把不同的通信性能抽象成模型参数,是这个阶段的研究重点。第三代是分布共享存储模型,也是我们目前研究所处的阶段。随着网络技术的发展,通信延迟固然还有影响,但对并行带来的影响不再像当年那样重要,注重计算系统的多层次存储特性的影响。

(2) 设计技术并行算法研究的第二个问题是并行算法的设计技术。虽然并行算法研究还不是太成熟,但并行算法的设计依然是有章可循的,例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。

3)最后并行算法分为多机并行和多线程并行两个实际实现的问题研究。多机并行,如MPI技术;多线程并行,如OpenMP技术。


本课程在内容体系上力求有所创新,在遵循课程自身学科性、系统性和完整性的同时,充分考虑不同应用领域在并行计算机上求解大型科学工程问题的需求,将并行机体系结构、并行数值计算、并行算法和并行编程等课程的内容有机的整合在一起,形成一门有思想有深度有认识的新型“并行计算”课程。本课程在教学内容和形式上力求有所改进,采用“结构-算法-编程”一体化的并行计算研究方法,带领学生仔多个学术专题和两三个前沿问题领域组织探讨,指导学生分组选题,课后资料查阅文献分析,课上组间讨论师生交流,老师指引学生有方向有目的的辩证思考,动手实践,交叉应用,将学生的创新意识和自学能力从根本激发,形成“有问题的学习,找问题的学习,发现问题的学习”的主动性和积极性

分析与论证

一.课堂教学

  采用ppt教学课件加案例代码演示的课堂教学方式。

  ppt教学课件(部分):

UNIX多线程环境.ppt

linziyu-BigData-PPT-Chapter4-MapReduce.pdf

mapreduce计算模型.pptx

并行模型.ppt

计算性分析.ppt

绪言计算机网络和计算.ppt


二.实验分析

  在课堂教学中,我们提出多种简单基本的算法实现,并要求同学在课后收集资料,进行复杂情况下的编程实验,并对其进行分析思考。

 

三.讨论辩证

  经过课后的实验操作,同学们积累了大量的疑惑和期待分享自己获取的大量相关知识,老师迎合同学的需求,多次开展讨论课,并与同学们一起就多个前沿问题进行自己的观点阐述和辩论。大家都收获许多。


        综上,通过本次seminar课程教学,我们有信心将“并行算法”课程做成开放互动、互学互助的新型研究生课程,并较好地达到预期的教学效果。

本课程贯彻教育部《关于深化研究生教育改革的意见》文件精神,以促进研究生在课程中学习和科学中研究的有机结合为目标,增强学生对学术界新型知识的获取和对前沿问题的关注性,以期通过高质量的课程学习来强化研究生的科学方法的训练和学生素养的培养,来提高研究生在数年的学术生涯中的创新能力和完善学术学位的培养模式。

         在任课老师授课过程中,每一到三次课程做一个学术专题,引导学生课后收集资料,查阅文献,课上进行思考和辩论。并鼓励学生不惧错误,开放思维,充分的发挥和表达自己的观点,引导学生间的讨论和师生间的互动学习。


hello world

本课程采用陈国良院士提出的“结构-算法-编程”一体化的并行计算研究方法,并紧随“算法理论-算法设计-算法实现-算法应用”一套完整的并行算法学科体系,采取了以下课程研讨方案:

1.        并行处理(计算)概述:并行性与并行计算概念,并行性等级,并行计算研究的内容,并行计算模型,计算机系统中并行性的发展,当代并行系统概述,并行处理技术的应用。

2.        流水线(并行)技术:流水技术的基本概念,流水线的分类,流水线处理机性能的定量分析方法,相关问题及其处理方法,线性流水线控制方式的基本原理以及非线性流水线的调度策略,向量流水处理技术和向量流水处理机。

3.        并行计算机的互连网络:互连函数及其表示方法,几种基本的互连函数,互连网络的结构参数和传输性能参数,静态互连网络及其拓扑结构,动态互连网络的基本结构。

4.        并行计算性能评测:计算机性能的评测,并行系统的加速比,Amdahl定律,Gustafson可扩展加速比定律,可扩放性评测标准,基准测试程序。

5.        并行算法的分析:数据结构与算法概述,算法的时间复杂性分析,并行算法的定义和分类,并行算法的性能分析,研究并行算法的几种途径,并行算法举例。

6.        并行算法的设计:并行算法的一般设计方法,并行算法的基本设计技术,并行算法的一般设计过程,设计并行算法应注意的问题。

7.        并行程序设计:并行程序设计概念,并行编程模型,并行程序设计环境与工具,MPI并行环境介绍与使用。

实验方案:

1.        熟悉MPI并行程序设计:熟悉MPI并行环境,使用MPI编写一个greeting程序,使用编号为0的进程接受其它各进程的“问候”,并在计算机屏幕上显示问候情况。用MPI编写一个多进程求积分的程序,并通过积分的方法求π的值,结果与π的25位精确值比较。

2.        多线程程序设计:用Pthreads或OpenMP编写通过积分的方法求π的程序。把该程序与相应的MPI程序比较。用Pthreads或OpenMP编写矩阵相乘的程序,观察矩阵增大以及线程个数增减时的情形。

3.        Java多线程编程:掌握多线程编程的特点,了解线程的调动和执行过程,使用Java实现资源共享访问的实现方法,编写龟兔赛跑程序以及选号程序。


本课程采取“随堂学习、随堂提问、随堂思考、随堂讨论”的教学思路,让研究生在任课老师的指导下,围绕“UNIX多线程环境”、“并行模型”、“计算性分析”、“MapReduce计算模型”以及“PETRI网”等多个学术专题及“异构处理器的并行化”和“基于并行化的框架研究”等并行计算的前沿问题组织教学,让同学们(20人)分成5组进行组内实验、课后调研以及文献资料分析,课中组间交流、师生讨论、教师原理讲解,形成一套合理合适并著有成效的教学研讨理念。

老师上课教学

好哥 (1).jpg

第一次讨论课:并行模型在产业界的实际应用----胡梓良同学

微信图片_20170920194909.jpg

第二次讨论:mapreduce计算模型的基础知识----吴兴桐同学

微信图片_20170920194922.jpg

教学期间也很荣幸邀请到清华大学计算机网络技术研究所所长林闯教授为学生传授“PETRI网络性能分析”主题课程,细述了petri网中并行模型思想的应用以及petri网的广泛应用场景,使学生受益匪浅,收获良多。

林闯教授传授petri网的相关知识以及与同学老师进行讨论

林闯教授.jpg

image.png


本课程是为计算机科学与技术专业和软件工程专业的学术研究生开设的专业课,参考的书籍对研究生的要求相对较高,首先能够阅读英文文献,对算法导论里的问题有一个比较清楚的基础。CC ++Fortran中的编程能力,以及重新思考问题如何解决的意愿。而并不要求以前对并行计算或超级计算有较多的经验积累。通过本课程能够对并行算法的思想进行理解,为将来研究当中运用并行算法的思想解决大规模计算和分析的问题。

学生评论:

1、敖威:一开始会觉得并行算法这门课有点难度,但廖老师能根据本课程知识结构的特点,重点突出,层次分明,通俗易懂;同时理论和实际相结合,通过例题使知识更条理化,让我获益匪浅。

2、胡梓良:廖老师在授课时语言幽默风趣,善于调动课堂气氛,能激发我们对并行算法这门课的兴趣,让我们在快乐中学习知识。

3、李俊:课堂内容充实,简单明了,使学生能够轻轻松松掌握知识;教学内容丰富有效,教学过程中尊重学生,有时还有些幽默,很受同学欢迎。

4、宋琪:廖老师对待教学认真负责,语言生动,条理清晰,举例充分恰当;对待学生严格要求,能够鼓励学生踊跃发言,使课堂气氛比较积极热烈,很喜欢这样的课堂。

5、吴远诗:并行算法课程老师治学严谨,要求严格,对同学的提问,能耐心讲解,不厌其烦。

6、吴兴桐:廖老师平易近人,能循循善诱,很注意启发和调动学生的积极性,能够鼓励学生踊跃发言,课堂气氛较为活跃,很喜欢这样的教学。

7、杨海泉:老师教学认真,课堂效率高,授课内容详细,我们学生大部分都能跟着老师思路学习,气氛活跃,整节课学下来有收获、欣喜,使人对并行算法课程兴趣浓厚。

8、颜果开:并行算法这门课程兼顾理论和应用,廖老师不仅在课堂上传授我们基础理论和前沿算法,并且还注重我们的代码实现能力,这对我们今后的工作和学习都有很大的帮助。

9、杨海良:在上课时,廖老师都会给我们充分的时间来讨论自己的想法和见解,大家都能够畅所欲言,课堂氛围很活跃;师生之间就像朋友一样,很喜欢这样有活力的课堂。

10、孙旭东:很喜欢并行算法这门课,廖老师授课也比较生动形象,主要从以下几个方面体现:第一,教学目标明确,善于抓住重点难点和关键点;第二,教学内容充实,理论与实际结合,把书本内容和生活相结合;第三,教学方法适当,廖老师对我们循循善诱,善启善导,很能够调动同学们的积极性;第四,上课组织的好,具有教学机智,廖老师教学观点严谨,语言表达清晰,具有感染力,同时也幽默风趣;第五,师生积极性高,配合默契,廖老师非常注重与同学们沟通,能广泛听取我们的意见和反馈信息。总的来说,廖老师的课是一门很有意思的课。

11、朱艺:廖老师上课准备很充分,每次都给我们精心准备了几篇前沿的论文,供我们自由学习;讲课深入浅出,讲的内容很容易让我们记住。

12、袁国文:廖老师的课堂非常生动,几乎每堂课会给我们一些很有趣的问题供大家讨论,在和大家的沟通讨论中,我的思考问题的方式和角度得到很好的延伸和推展!通过廖老师并行算法课程的教学,不仅能够领略到廖老师风趣幽默的人格魅力,还能够系统全面的学习到国内外先进的算法和技术,受益匪浅,感谢廖老师!