多核技术导论

多核程序设计多核处理器，独立缓存！通过并行方式改进处理器的性能！软件要如何做？教学内容多核技术基础Windows多线程编程OpenMP多线程编程周伟明，华中科技大学出版社第一章多核技术基础内容进程、线程多核编程方式加速比并行程序设计模式多线程的同步1.进程、线程应用程序：可执行文件。应用程序包括指令和数据。存储在磁盘上的应用程序1.进程、线程进程：正在执行的应用程序。进程包括指令、数据和状态。（状态保存在寄存器中）进程运行时，进程的状态会发生变化。加载到内存的单线程应用程序1.进程、线程线程：是进程中的一个实体，是系统调度的基本单位。每个进程至少包含一个线程，主线程。线程拥有很少的系统资源：程序计数器、一组寄存器和栈同一进程中的各线程共享进程的全部资源。同一进程中的多个线程可以并发执行，提高了资源利用率。加载到内存的多线程应用程序1.进程、线程线程的标识通常用一个整数来标识一个线程，线程ID。线程的创建主线程从main函数开始用线程库函数创建一个新的线程线程的终止函数执行完毕调用线程库的终止函数主线程退出1.进程、线程线程的生命周期：线程从创建到消亡的过程。终止运行阻塞就绪调度条件满足等待资源切换被创建完成2多核编程方式通过并行的方式，充分利用cpu核心。目的：降低单个问题求解的时间；增加问题规模、提高问题求解精度。2多核编程方式多线程线程的创建、切换代价相对小共享内存，共享数据OpenMP隐式并行、线程库函数显式并行影响加速比的因素：锁竞争、同步多进程进程的创建、切换代价相对大独立内存，通过消息传递数据MPI影响加速比的因素：消息传递的开销3加速比加速比：用于衡量同一问题并行化后的执行时间与串行执行时间的比。并行执行时间包括：计算时间，并行开销，通信时间

加速比

3加速比例,粉刷栅栏:前期准备工作30分钟(串行)一分钟粉刷一个栅栏(共计300根)

收尾工作30分钟(串行)3加速比粉刷人数时间加速比130

+

300

+

30

=

3601.0X230

+

150

+

30

=

2101.7X1030

+

30

+

30

=

904.0X10030

+

3

+

30

=

635.7XInfinite30

+

0

+

30

=

606.0X3加速比并行效率：衡量并行计算时，CPU利用率。

(加速比/

线程数量)

*

100%考虑“粉刷栅栏”例子的并行效率:粉刷人数时间加速比并行效率130

+

300

+

30

=

3601.0X100%230

+

150

+

30

=

2101.7X85%1030

+

30

+

30

=

904.0X40%10030

+

3

+

30

=

635.7X5.7%Infinite30

+

0

+

30

=

606.0Xvery

low3.1Amdahl定律（1）加速比与哪些因素有关？加速比是否可以随着处理器个数的增加而线性增加呢？3.1Amdahl定律（2）

串行时间并行时间加速比

3.2Amdahl定律（3）加速比与处理器个数关系

3.2Gustafson定律（1）问题规模增加后，串行部分的规模是固定的，即串行部分执行时间固定的。程序在多处理器上执行的总时间是常数。3.2Gustafson定律（2）串行时间并行时间加速比

设串行部分执行时间为K

3.2Gustafson定律（3）加速比与处理器个数关系

3.3锁竞争对加速比的影响有锁保护下的，线程内的计算分类线程粒度因子，反映线程的计算量大小

线程粒度因子与分解的线程数量有关3.3锁竞争对加速比的影响锁粒度因子，反映一个线程内锁操作的粒度关系

将粒度非常小的锁称为细粒度锁。细粒度锁，可使加速比性能得到提升。减少锁粒度因子方法：将非共享资源操作从锁内移到锁外。将大的共享资源操作设计成小的共享资源操作，减少非共享资源操作时间。3.4负载均衡对加速比的影响影响负载均衡的主要因素线程划分不均线程执行时间不确定CPU核数负载均衡的评价指标

3.4负载均衡对加速比的影响有效的分配

线程执行相同的工作量各线程尽可能同时结束动态调度线程4.并行程序设计模式数据分解模式分治模式流水线模式任务并行模式关键路径4.1数据分解模式将数据分解成若干独立的数据子集。每个线程处理其中的一个或多个数据子集。当数据量很大时，多用数据分解模式并行化。4.1数据分解模式数据分解（例）两个园丁对一个花园进行除草、翻地。如果需要修剪草坪的地块非常小，怎么分解？假设有另外两个园丁加入了工作，怎么分解？4.1数据分解模式编程模式ParallelRegionsMasterThreadForkandJoinProgrammingModelisthemostcommonapproachfordataparallelism4.1数据分解模式编程模式for(inti=0;i<1000000;i++)sum+=a[i]*b[i]for(inti=0;i<500000;i++)sum+=a[i]*b[i]for(inti=500000;i<1000000;i++)sum+=a[i]*b[i]数据分解注意事项：负载均衡数据在Cache中的位置4.2分治模式分治模式：将一个原问题的求解分解为多个子问题的求解，然后将多个子问题的解通过一定的计算方法合并为原问题的解。例如：整数求和问题排序问题4.2分治模式子问题求解时负载平衡问题通常解决办法是将子问题数量增大，然后通过一定的任务调度方法使之负载均衡。子问题的解的合并可能引起的串行化问题解的合并时间少，不会对加速比产生大的影响。解的合并时间长，最好将解的合并时间过程进行并行化计算。4.3流水线模式Laundry（洗衣）ExampleAnn,Brian,Cathy,Dave

eachhaveoneloadofclothes

towash,dry,andfoldWashertakes30minutesDryertakes40minutesFoldertakes20minutesABCDSequentiallaundrytakes6hoursfor4loadsIftheylearnedpipelining,howlongwouldlaundrytake?ABCD3040203040203040203040206PM7891011MidnightTaskOrderTimePipelinedlaundrytakes3.5hoursfor4loadsABCD6PM7891011MidnightTaskOrderTime3040404040204.3流水线模式将一个计算过程分解成多个阶段，不同阶段之间的数据有依赖浏览器，浏览一个网页文件过程生成一组线程，每个线程执行不同的阶段任务，这些线程同时工作。数据在各线程间流动。获取网页文件数据处理网页文件数据显示网页文件数据获取网页文件数据处理网页文件数据显示网页文件数据获取数据线程处理数据线程显示数据线程4.4任务并行将一个大的计算任务按功能分解成若干独立的小计算任务。生成一组线程，每个线程执行一个独立的任务。例：盖房子4.4任务并行例：文字处理软件，打开一个文档进行编辑。分页和文档输入两个任务文档输入分页串行文档输入分页并行Cpu核1Cpu核2任务并行S1:a=page(a1,a2);S2:b=input(b1,b2);4.4任务并行任务并行引起数据竞争通常要移除任务间的依赖性或使用复制来分离依赖性。任务并行引起负载均衡问题通过任务调度解决4.5关键路径关键路径是确定任务可在最短时间内完成的一组步骤。例：一个串行程序要完成任务A、B、C、DB依赖于AD依赖于B和C5.多线程的同步同步：指两个或多个任务之间协调其行为的过程，保证各个线程可以在一起适当地协调工作，称为线程之间的同步。5.1为什么需要线程同步？5.2数据竞争5.3常用的线程同步方法5.4死锁5.5活锁5.1为什么需要线程同步？多个线程同时访问共享数据如果没有正确的数据保护，导致计算结果的错误。线程1线程2i=8i++i=9i--MOV[i],8MOVEAX,[i]INCEAXMOV[i],EAXMOV[i],9MOVEAX,[i]DECEAXMOV[i],EAX5.2数据竞争数据竞争内存冲突发生于：当多个线程同时访问同一内存空间至少有一个线程对该内存进行更新操作两种可能的冲突读写冲突写写冲突5.2数据竞争IntinSet(doubleix,doubleiy){intiterations=0;doublex=ix,y=iy,x2=x*x,y2=y*y;while((x2+y2)<4)&&(iterations<1000)){y=2*x*y+iy;x=x2-y2+ix;x2=x*x;y2=y*y;iterations++;}}由于数据竞争而无法直接并行化5.2数据竞争通过复制避免数据竞争voidanti-dependency()读写竞争{ result1=calculation(data1);

data1=result2+1;}voidanti-dependency(){ data1_prime=data1; result1=calculation(data1_prime); data1=result2+1;}5.2数据竞争通过复制避免数据竞争voidout-dependency()写写竞争{

data1=result1+2;

data1=result2+2;}voidout-dependency(){ data1_prime=result1+2; data1=result2+2;}5.2数据竞争voiddowork(intx,inty){ intvalue=longCalculation(x,y); if(value>threshold) { returnvalue+secondLongCalculation(x,y); } else{ returnvalue; }}推测执行voiddowork(intx,inty){ intvalue1,value2;

#pragmastartparallelregion { #pragmaperformparalleltask {value1=longCalculation(x,y);} #pragmaperformparalleltask {value2=secondLongCalculation(x,y);} }#pragmawaitforparalleltaskstocomplete if(value1>threshold) {returnvalue1+value2; } else {returnvalue1; }}5.2数据竞争5.2数据竞争voiddowork(intx,inty){ intvalue=longCalculation(x,y); returnsecondLongCalculation(value);}值推测voiddowork(intx,inty){ intvalue1,value2;

staticintlast_value; #pragmastartparallelregion { #pragmaperformparalleltask {value1=longCalculation(x,y);} #pragmaperformparalleltask {value2=secondLongCalculation(lastvalue);} }#pragmawaitforparalleltaskstocomplete if(value1==lastvalue) { returnvalue2; } else { lastvalue=value1; returnsecondLongCalculation(value1); }}5.3常用的线程同步方法临界区（Critical_Section）互斥量（Mutex）信号量（Semaphore）事件（Event）1、临界区临界区：当多个线程访问共享数据时，共享数据需要被保护，以保证数据的完整性。临界区包括：进入区和退出区当一个线程进入某个临界区域，其它想访问这个临界区域的线程就必须等待。临界区的优点：速度快，适合控制数据访问。进入区退出区临界区2、互斥量互斥量：采用互斥对象机制拥有互斥对象的线程才能访问公共资源，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥对象用于：多线程、多进程。互斥量可以命名，可以跨进程使用。创建互斥量需要的资源更多临界区只能在同一个进程内使用。临界区速度相对快，资源占用少。互斥量临界区2、互斥量ThreadAVoidsomeMethod(){print(“AHelloone”);print(“AHellotwo”);}ThreadBVoidsomeMethod(){print(“BHelloone”);print(“BHellotwo”);}不使用同步原语AHellooneBHellooneBHellotwoAHellotwo2、互斥量ThreadAVoidsomeMethod(){mutex.lock();print(“AHelloone”);print(“AHellotwo”);mutex.unlock();}ThreadBVoidsomeMethod(){mutex.lock();print(“BHelloone”);print(“BHellotwo”);mutex.unlock();}加上同步原语Mutexmutex;3、信号量12个停车位，空3个位置，来了5辆车。3、信号量信号量允许多个线程同时访问共享资源，但限制同时访问此资源的最大线程数目。信号量的特性如下：信号量是一个非负整数（车位数）要访问共享资源的线程/进程（车辆）必须获取一个信号量，则信号量减一。当信号量为零时，试图访问共享资源的线程/进程将处于等待状态。离开共享资源的线程/进程（车辆）释