第2章 并行化程序设计方法

NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training第2章并行化程序设计方法NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training并发:•并发是指一个进程中的多个线程交替执行。•并发线程在单个处理器上运行。多线程应用程序中的并发性Thread1Thread2Thread2Thread1Thread1Thread1Thread2Thread2Thread2Thread1引言NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training并行:•并行是指多个线程同时执行。•并行线程能在多个处理器上执行。多线程应用程序中的并行性Thread1Thread1Thread1Thread2Thread2Thread2引言NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training1.并行化程序开发流程开始否是1.问题描述3.确定分解模式2.是否具有并行性和并行价值5.选取一种编程模型进行实现6.性能调优结束4.设计并行算法第一部分第二部分第三部分NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计•问题的可并行性–是否可以将问题划分为不同的功能模块分别完成–针对需要处理的数据是否可以划分为若干数据块同时操作–是否可以将一个复杂的过程划分为若干个子操作流水执行NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计•相关性分析–确定必要的通信和同步机制；–分析这些并行化可能会带来的额外的开销•开销是否是必要的？•是否是有价值的？•是否是可以承受的？•额外的开销可能包括程序本身的开销，也可能是经济，资源，人力等方面开销。NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计问题1：数据竞争解决方法：临界区、互斥、同步。–临界区–互斥–同步问题2：死锁解决方法：先来先服务举例说明。NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计•问题分解–最常用的分解模式有任务分解，数据分解和数据流分解。–任务分解是将问题划分为多个功能模块分别由不同的线程去执行；举例。–数据分解是将待处理数据分成若干不同的数据块交由不同的线程去执行；举例。–数据流分解是将一个复杂的操作划分成若干个简单的子操作，数据在子操作间按照一定的顺序依次计算。举例。NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计–数据的求和累加;–下列程序如何并行：for(inti=0;i20;i++){for(inti=0;i40;i++){doSomething();}}NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training2.并行化程序设计•算法设计结构–任务分解采用各任务并行，分而治之的设计结构–数据分解依据对数据的处理过程采用几何分解，递归分解等设计结构–数据流分解采用流水线等设计结构。NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training3.并行编程模型选择•显式模型–Win32API–POSIX线程库Pthreads•隐式模型–OpenMP–TBB•可选其它编程模型:MPI,PVM•通过例子比较显示模型和隐式模型的区别。NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training3.并行编程模型选择Win32API–线程的创建：createThread()–线程的终止：ExitThread()–线程的挂起与恢复：SuspendThread(),ResumeThread()–线程的等待：WaitForSingleObject()WaitForMultipleObjects()OpenMP无需开发人员显式处理复杂的线程创建、同步、负载平衡、销毁等技术细节。NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training4.性能调优•性能指标–加速比–效率–粒度–负载平衡•调优工具–IntelVTune–IntelThreadChecker–IntelThreadProfilerNeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training加速比Speedup=SerialTime/ParallelTimeAmdahl’s定律Speedup=1/[S+(1-S)/n+H(n)]（强调并行比例）4.性能调优NeusoftInstituteofInformation2020年1月17日星期五ITEducation&TrainingPaintingapicketfencerequires:•30minutesofpreparation(serial).•Oneminutetopaintasinglepicket(300picket).•30minutestocleanup(serial).•1、2、10、100paintersExample:PaintingaPicketFence4.性能调优NeusoftInstituteofInformation2020年1月17日星期五ITEducation&TrainingNumberofPaintersTimeSpeedup130+300+30=3601.0X230+150+30=2101.7X1030+30+30=904.0X10030+3+30=635.7XInfinite30+0+30=606.0XConsiderhowspeedupiscomputedfordifferentnumbersofpainters:4.性能调优NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training•效率:–(Speedup/NumberofThreads)*100%.•Considerhowefficiencyiscomputedwithdifferentnumbersofpainters:NumberofPaintersTimeSpeedupEfficiency13601.0X100%230+150+30=2101.7X85%1030+30+30=904.0X40%10030+3+30=635.7X5.7%Infinite30+0+30=606.0Xverylow4.性能调优NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training•粒度–粒度表示程序处理数据的规模•两种类型粒度–粗粒度–细粒度Example:FieldandFarmers4.性能调优NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training•负载平衡–让每个处理核尽可能处于相同的繁忙程度•有效的任务划分方式–线程完成相同的工作量–线程同时完成工作Example:CleaningBanquetTables4.性能调优NeusoftInstituteofInformation2020年1月17日星期五ITEducation&Training本章小结•并行程序开发流程•并行化程序设计综述