【大学课件】基于多核的并行程序设计

1、基于多核的并行程序设计1ppt课件outline参考资料baidu/google课本并行编程模式（清华大学出版社）并行程序设计（机械工业出版社）老师/助教预备知识计算机组成原理操作系统c/c+2022/8/202ppt课件课程安排并行体系与多核体系结构 多核计算机系统的操作系统 基于多核计算机系统的软件开发工具 基于多核的软件设计 基于多核平台的程序调试和优化技术 2022/8/203ppt课件多核发展及其挑战2022/8/204ppt课件拉开多核时代的序幕在CPU快速发展的20年里, CPU一次次地遭遇性能极限，但都又一次次地冲破了这个极限.从奔腾到奔腾2，CPU也突破了1GHZ，从奔腾2到

2、奔腾3，CPU从1GHZ突破了2GHZ，从奔腾3到奔腾4，CPU也终于突破了3GHZ，现在最高的CPU主频已经高达3.8GHZ 单核CPU的极限突破单核CPU好象停止了前进，到3.8G却怎么也超不过4G单核CPU遭遇终极瓶颈英特尔不得不承认奔腾系列已经遭遇最终的主频极限，4G就象一场百年罕见地强降雪，将奔腾系列CPU的性能高速公路永远地封死了。因此，以英特尔为首的CPU军团不得不另外找一条更宽的性能高速公路来继续他们的CPU神话 另寻出路2022/8/205ppt课件多核处理器的基本架构背景：随着芯片制成工艺的不断进步，从体系结构来看，传统的处理器体系结构技术已面临瓶颈，晶体管集成度已经过亿，

3、很难通过提高主频来提升性能；从应用需求来看，日益复杂的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。在这样的背景下，各主流处理器厂商纷纷将产品战略从提高芯片的时钟频率转向多线程、多内核。1.多核芯片发展近况：继双核之后，Intel已经在2006年11月推出了4核产品，AMD也推出了代号为巴塞罗那的4核处理器。目前，多核处理器的推出越演越烈，在推出了代号为Niagara的8核处理器之后，Sun公司还计划推出Niagara2处理器。 Intel近日内声称，明年即将研制推出10核以上的处理器产品。2022/8/206ppt课件Front Side Bus多核处理器简介什么是多核处理

4、器两个或多个独立运行的内核集成于同一个处理器上双核处理器 =一个处理器上包含2个内核Core0Core12022/8/207ppt课件多核处理器简介为什么采用双核双核共享封装和I/O时,总成本下降封装和测试占总成本的20%-50%, I/O通常占晶片面积的15-20%功耗成本性能单核多核主频超过2GHz时功耗超过100W仅靠主频驱动平衡性能与功耗由主频和每时钟周期所执行的指令数来实现2022/8/208ppt课件定义：片上多核处理器（Chip Multi-Processor,CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。多核处理器的基本架构2.片上多核处理器体系结构分类：

5、按计算内核是否对等，CMP可分为同构多核和异构多核。计算内核相同，地位对等的称为“同构多核”，现在Intel和AMD主推的双核处理器就是同构多核的；计算内核不同，地位不对等的称为“异构多核”，异构多核采用“主处理器协处理器”的设计，IBM、SONY等联手推出的Cell处理器就是异构多核处理器的典范。2022/8/209ppt课件硬件结构：由于CMP处理器的各CPU核心执行的程序之间有时需要进行数据共享与同步，故硬件结构必须支持核间通信。多核处理器的基本架构2.片上多核处理器体系结构总线共享cache结构：是指每个CPU内核拥有共享的二级或三级cache，用于保存比较常用的数据，并通过连接核心的

6、总线进行通信。优点：结构简单、通信速度高。缺点：基于总线的结构可扩展性较差。基于片上互连的结构：指每个CPU内核拥有独立的处理单元和cache，各个CPU核心间通过交叉开关或片上网络等方式连接在一起，各个CPU核心间通过消息通信。优点：可扩展性好、数据带宽有保证。缺点：硬件结构复杂，且软件改动较大。2022/8/2010ppt课件多核挑战软件开发多核的影响 传统的科学计算 原有软件大都是并行的多核提供了更高性能的执行平台需要做的是针对多核进行优化,多核应用不存在困难服务器软件 业务特征是并发的,应用具有天然的并发性 多核提供了一个高性能计算平台, 面临挑战不大 原有大部分程序是串行的 需要很好

7、的并行编程模型和开发环境,挑战很大 桌面软件2022/8/2011ppt课件多核挑战软件开发并行程序设计为什么难？其根本原因是因为大多数计算机和编程语言发明之初就是按照冯诺依曼理论进行设计的。根据冯诺依曼的理论，CPU是按照程序指令，一条条取出来并顺序执行的。而在多核或者多CPU的计算机中，同时会有多条指令在执行。 2022/8/2012ppt课件多核挑战软件开发并行程序设计之难首先，运行于不同处理器上的各项任务之间的通信就是个难题。 其次，由于并行系统缺少明确的全局系统状态，不像串行程序容易理解 第三，因为并行程序执行时，每一次的执行路径并不完全一样，这会给并行程序设计的纠错和调优等带来很大

8、困难 。2022/8/2013ppt课件多核带来的挑战毫无疑问，多核给我们提供了更经济的计算能力。但是，这种能力能否善加利用还要取决于软件。 如果不针对多核进行软件开发，不仅多核提供的强大计算能力得不到利用，相反还有可能不如单核CPU好用。 “从某种程度上说，对于软件开发者而言，CPU主频提升就像是免费的午餐，此前所有的程序很自然地会从主频的提升中受益，而如今多核出现了，这种免费的午餐没有了。我们必须针对多核重新进行软件设计。” 2022/8/2014ppt课件认识并行计算2022/8/2015ppt课件What Is Parallel Computing?Attempt to speed s

9、olution of a particular task by1. Dividing task into sub-tasks2. Executing sub-tasks simultaneously on multiple processorsSuccessful attempts require both1. Understanding of where parallelism can be effective2. Knowledge of how to design and implement good solutions2022/8/2016ppt课件Why Parallel Compu

10、ting?“The free lunch is over.” Herb SutterWe want applications to execute fasterClock speeds no longer increasing exponentially10 GHz1 GHz100 MHz10 MHz1 MHz79 87 95 03 112022/8/2017ppt课件Ways of Exploiting ParallelismDomain decomposition(域分解)数据Task decomposition(任务分解)计算Pipelining(流水线)3者的结合2022/8/2018

11、ppt课件Domain Decomposition(域划分)First, decide how data elements should be divided among processors划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据Second, decide which tasks each processor should be doing划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯Example: Vector additionadd two vectors of size 100,000 using two processor

12、s划分方法，最佳是分成前后两部分2022/8/2019ppt课件Domain DecompositionFind the largest element of an array2022/8/2020ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3shared scalar variable that will hold the global maximum2022/8/2021ppt课件Domain DecompositionFind the largest element of

13、an arrayCPU 0CPU 1CPU 2CPU 32022/8/2022ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2023ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2024ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2C

14、PU 32022/8/2025ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2026ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2027ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies

15、 the maximum value it found into the shared memory location.2022/8/2028ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies the maximum value it found into the shared memory location.2022/8/2029ppt课件Domain DecompositionFind the largest element of an a

16、rrayCPU 0CPU 1CPU 2CPU 32022/8/2030ppt课件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3When the last CPU is done, the shared location has the maximum value.2022/8/2031ppt课件Task (Functional) DecompositionFirst, divide tasks among processors划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解S

17、econd, decide which data elements are going to be accessed (read and/or written) by which processors划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着要重新进行域分解和功能分解；Example: Event-handler for GUIOne processor may be watching the keyboard and mouse while another processor performs the activity related

18、 to a previous user action.2022/8/2032ppt课件Task Decompositionf()s()r()q()h()g()In a task decomposition we look for functions that can execute simultaneously.In this drawing the arrows represent the precedence constraints among the functions.2022/8/2033ppt课件Task Decompositionf()s()r()q()h()g()CPU 0CP

19、U 2CPU 1Question: Why is there no point in assigning “f”, “r”, and “s” to different CPUs?2022/8/2034ppt课件Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1Blue circles indicate active CPUs.2022/8/2035ppt课件Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12022/8/2036ppt课件Task Decompositionf()s()r()

20、q()h()g()CPU 0CPU 2CPU 12022/8/2037ppt课件Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12022/8/2038ppt课件PipeliningSpecial kind of task decomposition“Assembly line” parallelismIn a pipelined application, the output of each function is the input to the next function.If we are only interested in pro

21、cessing one data set, there is no parallelism.the throughput is limited by the slowest stage. So if all the stages dont run at the same speed, its inefficient. Example: 3D rendering in computer graphicsRasterizeClipProjectModelInputOutput2022/8/2039ppt课件Processing One Data Set (Step 1)RasterizeClipP

22、rojectModelHere a graphics rendering computation can be divided into four stages.If we want to process only one data set, it takes one step for each stage.2022/8/2040ppt课件Processing One Data Set (Step 2)RasterizeClipProjectModel2022/8/2041ppt课件Processing One Data Set (Step 3)RasterizeClipProjectMode

23、l2022/8/2042ppt课件Processing One Data Set (Step 4)RasterizeClipProjectModelThe pipeline processes 1 data set in 4 stepsHere a graphics rendering computation can be divided into four stages.If we want to process only one data set, it takes one step for each stage.2022/8/2043ppt课件Processing Two Data Se

24、ts (Step 1)RasterizeClipProjectModelCPU0CPU1CPU2CPU3每个CPU完成特定功能2022/8/2044ppt课件Processing Two Data Sets (Time 2)RasterizeClipProjectModel2022/8/2045ppt课件Processing Two Data Sets (Step 3)RasterizeClipProjectModel2022/8/2046ppt课件Processing Two Data Sets (Step 4)RasterizeClipProjectModel2022/8/2047ppt课

25、件Processing Two Data Sets (Step 5)RasterizeClipProjectModelThe pipeline processes 2 data sets in 5 steps2022/8/2048ppt课件Pipelining Five Data Sets (Step 1)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2049ppt课件Pipelining Five Data Sets (Step 2)Data set 0Data set 1Data s

26、et 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2050ppt课件Pipelining Five Data Sets (Step 3)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2051ppt课件Pipelining Five Data Sets (Step 4)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2052ppt课件

27、Pipelining Five Data Sets (Step 5)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2053ppt课件Pipelining Five Data Sets (Step 6)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2054ppt课件Pipelining Five Data Sets (Step 7)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2055ppt课件Pipelining Five Data Sets (Step 8)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3Question: How much faster is the pipelined computat