并行化程序设计方法.ppt

1、第2章 并行化程序设计方法,并发: 并发是指一个进程中的多个线程交替执行。 并发线程在单个处理器上运行。,多线程应用程序中的并发性,Thread 2,Thread 1,引言,并行: 并行是指多个线程同时执行。 并行线程能在多个处理器上执行。,多线程应用程序中的并行性,引言,1.并行化程序开发流程,第一部分,第二部分,第三部分,2.并行化程序设计,2.并行化程序设计,问题的可并行性 是否可以将问题划分为不同的功能模块分别完成 针对需要处理的数据是否可以划分为若干数据块同时操作 是否可以将一个复杂的过程划分为若干个子操作流水执行,2.并行化程序设计,相关性分析 确定必要的通信和同步机制； 分析这些

2、并行化可能会带来的额外的开销 开销是否是必要的？ 是否是有价值的？ 是否是可以承受的？ 额外的开销可能包括程序本身的开销，也可能是经济，资源，人力等方面开销。,2.并行化程序设计,问题1：数据竞争 解决方法：临界区、互斥、同步。 临界区 互斥 同步 问题2：死锁 解决方法：先来先服务 举例说明。,2.并行化程序设计,问题分解 最常用的分解模式有任务分解，数据分解和数据流分解。 任务分解是将问题划分为多个功能模块分别由不同的线程去执行；举例。 数据分解是将待处理数据分成若干不同的数据块交由不同的线程去执行；举例。 数据流分解是将一个复杂的操作划分成若干个简单的子操作，数据在子操作间按照一定的顺序

3、依次计算。举例。,2.并行化程序设计,数据的求和累加; 下列程序如何并行： for(int i=0;i20;i+) for(int i=0;i40;i+) doSomething(); ,2.并行化程序设计,算法设计结构 任务分解采用各任务并行，分而治之的设计结构 数据分解依据对数据的处理过程采用几何分解，递归分解等设计结构 数据流分解采用流水线等设计结构。,3. 并行编程模型选择,显式模型 Win32 API POSIX线程库Pthreads 隐式模型 OpenMP TBB 可选其它编程模型:MPI,PVM 通过例子比较显示模型和隐式模型的区别。,3. 并行编程模型选择,Win32 API

4、线程的创建：createThread() 线程的终止：ExitThread() 线程的挂起与恢复：SuspendThread(), ResumeThread() 线程的等待：WaitForSingleObject() WaitForMultipleObjects() OpenMP 无需开发人员显式处理复杂的线程创建、同步、负载平衡、销毁等技术细节。,4. 性能调优,性能指标 加速比 效率 粒度 负载平衡,调优工具 Intel VTune Intel Thread Checker Intel Thread Profiler,加速比 Speedup = Serial Time / Parallel

5、 Time Amdahls 定律 Speedup = 1 / S+(1-S)/n +H(n) （强调并行比例）,4. 性能调优,Painting a picket fence requires: 30 minutes of preparation (serial). One minute to paint a single picket(300 picket). 30 minutes to clean up (serial). 1、2、10、100 painters,Example: Painting a Picket Fence,4. 性能调优,Consider how speedup is computed for different numbers of painters:,4. 性能调优,效率: (Speedup / Number of Threads) * 100%. Consider how efficiency is computed with different numbers of painters:,4. 性能调优,粒度 粒度表示程序处理数据的规模 两种类型粒度 粗粒度 细粒度,Example: Field and Farmers,4. 性能调优,负载平衡 让每个处理核尽可能处于相同的繁忙程度 有效