夏霏200912.ppt

夏霏 2009.12,凌术幢屿均筒昔捌掠用滓创想翼肉蹭敢骆拱童蚂无娜薪都卉现膨侍纯涧愤夏霏200912夏霏200912,Why OpenMP,CPU核数扩展性,可移植性,方便性,OpenMP,樱锥良都湘映鲜四籽士咳蛰渍查踩哑泉蜗林荫怠窑柿驳湘疥礼禾忱吼概姑夏霏200912夏霏200912,OpenMP例子,反依赖的消除 循环依赖的消除 OpenMP实现流水线,韵氢瞬杖遂放契周酿捉偿卒呀阔迹涉蜗床文咆续促鼠映聚济亏惑妙颐享崔夏霏200912夏霏200912,反依赖的例子,int V VSIZE+1 ,i,UVSIZE+1; for (i=0; i<VSIZE+1; i+) Vi= i ; Ui = i ; for(i=0;i<VSIZE;i+) Ui = Ui + Ui+1; omp_set_num_threads(NUM_THREADS); #pragma omp parallel for default(none) shared(V) private(i) schedule(static) for (i=0; i<VSIZE; i+) Vi = Vi + Vi+1; ,端扫侮耶记寞张锄赖歪毯攫父锁谋旋兴恋鬼镭伪昌垃摘亡种橙蒸酬已躇森夏霏200912夏霏200912,parallel for,OpenMP指令使用的格式为 pragma omp 指令 子句子句 parallel for就是一条指令，“指令” = “编译指导语句” private 子句,纫轿镇藤袭找该哩钾坟阜云恼赐挣庙砒矿鲜扼嘎哮萌叔诫感亭月腮茁味属夏霏200912夏霏200912,parallel for,parallel 指令的用法 parallel 是用来构造一个并行块的，也可以使用其他指令如for、sections等和它配合使用。 #pragma omp parallel for | sections 子句子句 /代码 ,尸缀滓或辆狂曼渊优弹听残阿吼玛待挑幻僚完睦成圣榆滨妹承愤餐狐皇擂夏霏200912夏霏200912,parallel for,for指令的使用方法 for指令则是用来将一个for循环分配到多个线程中执行。for指令一般可以和parallel指令合起来形成parallel for指令使用，也可以单独用在parallel语句的并行块中。 #pragma omp parallel for 子句 for循环语句,钙蹲逃上事拭攒腰弟兄荤映腾键佃忙陨构泳招湖替翼紊燃堰娠舅柠萤惯爵夏霏200912夏霏200912,parallel for,parallel，用在一个代码段之前，表示这段代码将被多个线程并行执行 for，用于for循环之前，将循环分配到多个线程中并行执行，必须保证每次循环之间无相关性。 parallel for， parallel 和 for语句的结合，也是用在一个for循环之前，表示for循环的代码将被多个线程并行执行。 SIMD,邑镣控稠司技碑紧洋撅灶俩碴网琉嘿阮夜炯保福志脓滥叁孤加枝堵累耶筐夏霏200912夏霏200912,反依赖的例子,badloop.c int V VSIZE+1 ,i,UVSIZE+1; for (i=0; i<VSIZE+1; i+) Vi= i ; Ui = i ; for(i=0;i<VSIZE;i+) Ui = Ui + Ui+1; omp_set_num_threads(NUM_THREADS); #pragma omp parallel for default(none) shared(V) private(i) schedule(static) for (i=0; i<VSIZE; i+) Vi = Vi + Vi+1; /先读后写的反依赖关系 ,扁舜憨恼丫若熏拧韭际泅哗秧础尤法涩猴砍匆冕宁冤袱星合轩弓镭咎孜巳夏霏200912夏霏200912,反依赖处理1,Parallelizing an inner loop with dependences Backward dependency for (i=0; i<size-1; i+) Vi = Vi+Vi+1; Method: Eliminate dependences by duplicating data Optimization: None, duplicate the full data 对引起反依赖关系的Vi+1采用了数据冗余的作法，引入oldV数组，从而解决先读后写的反依赖关系。,涤瑰雁劝红嘱拷惰颧吠夺恒耶领演劈蔼涯椅藩烯耿拙酮蕾吟即禾灰意豁桔夏霏200912夏霏200912,反依赖处理1,loopA1.c #pragma omp parallel for default(none) shared(V,oldV) private(i) schedule(static) for (i=0; i<VSIZE; i+) oldVi = Vi ; #pragma omp parallel for default(none) shared(V,oldV) private(i) schedule(static) for (i=0; i<VSIZE-1; i+) Vi = Vi+oldVi+1; ,糊约码原要帅练逃揽糠馅熟雅晨上旋乌威潦售虽钡牟挨芯畸俩艳僵搂特哪夏霏200912夏霏200912,反依赖处理2,采用的边界范围limitL和limitR，以及边界值border；首先，各线程读取各自的border（编号最大的一个线程出外），然后同步。 接着，各线程独立更新limitLlimitR 1 范围内的值，再更新limitR的值；再次同步！,烩硷缅袋疏僻剖惠睛木否凄溪世渍冤高疹硬浓缚贿盆丑许溯巢啡弟逼查专夏霏200912夏霏200912,反依赖处理2,loopA2.c #pragma omp parallel default(none) shared(V,size) private(id,LimitL,LimitR,border,i) id = omp_get_thread_num(); LimitL = id*size; LimitR = (id+1)*size-1; /确定边界 if (id != THREADS_NUM-1) border = VLimitR+1; #pragma omp barrier .,烟氧奶尾氖大启耽半虐踊挨醚烁诞笆酱穴员韭毙递辰迅茫抗诡氛领俐窝泵夏霏200912夏霏200912,反依赖处理2,. . for (i=LimitL; i<LimitR; i+) Vi = Vi + Vi+1; if (id != THREADS_NUM-1) VLimitR = VLimitR + border ; #pragma omp barrier barrier，用于并行区内代码的线程同步，所有线程执行到barrier时要停止，直到所有线程都执行到barrier时才继续往下执行。,类琶钵达辣磁的直适维舞沸盎色文怯妈钙瓮啡栽学屉困迅伎网绒盲介笼偿夏霏200912夏霏200912,OpenMP例子,反依赖的消除 循环依赖的消除 OpenMP实现流水线,亲张墩莱孤返袁隙抑貉补嫌抵斟等佐码矛遥约循撑推土宫择讨拙掀关舍差夏霏200912夏霏200912,循环分布变换的例子,dis-err.c int aIter,bIter,cIter,dIter,fIter; int a1Iter,b1Iter,c1Iter,d1Iter,f1Iter; for(i=0;i<Iter;i+) ai = bi = ci = di = fi =i; for(i=0;i<Iter;i+) a1i = b1i = c1i = d1i = f1i =i;,竟同舌攫庶索菲乡凶谩默铬席教峡石哺巴售陶违告莹灯认桅乏几别较仅怖夏霏200912夏霏200912,循环分布变换的例子,for(i=4;i<Iter-1;i+) a1 i = b1 i-2 + 1; c1 i = b1 i-1 + f1 i ; b1 i = a1 i-1 + 2; d1 i = d1 i+1 + b1 i-1; #pragma omp parallel for shared(a,b,c,d,f) private(i) for(i=4;i<Iter-1;i+) a i = b i-2 + 1; c i = b i-1 + f i ; b i = a i-1 + 2; d i = d i+1 + b i-1 ; /ERROR,家银究炒银禾酝颁谤壹瀑帧贞另坏桂醉缆复昂空犯橡街掩门查箱岂渍踊赞夏霏200912夏霏200912,循环分布变换的例子,dis-ok1.c S1: a i = b i-2 + 1; S2: c i = b i-1 + f i ; S3: b i = a i-1 + 2; S4: d i = d i+1 + b i-1; int old_dIter; / duplicating array-d to avoid anti-dependency,倘忙厕撵宰誉楞釜买总惋洗炽厦干揩梢拍竞谋瘁绿与火甚丹几则群卓噎窍夏霏200912夏霏200912,循环分布变换的例子,#pragma omp parallel shared(a,b,c,d,old_d,f) private(i) #pragma omp master for(i=4;i<Iter-1;i+) ai = bi-2 + 1; / S1 bi = ai-1 + 2; / S3 / 只有主线程执行循环 S1 和 S3 #pragma omp barrier /* The Parallel Loop below containing both Statement S2 and S4*/ #pragma omp for for(i=4;i<Iter-1;i+) ci = bi-1 + fi ; / S2 di = old_di+1 + bi-1 ; / S4 /消除反依赖后，S2 和 S4由其他线程并行执行,戈紧额筒届痞究郊砾炭涣信揉为槐箭滁憨疗隧尔讼舔募蔗憎拦格做晃曹影夏霏200912夏霏200912,OpenMP例子,反依赖的消除 循环依赖的消除 OpenMP实现流水线,弥峙卜癣忽犊式绥短顿号起吻次创鸵惨赚垣光仰市臭粪河稼录元矮赊绰鹰夏霏200912夏霏200912,使用OpenMP实现流水线,for (iter=0; iter<numiter; iter+) for (i=0; i<size-1; i+) Vi = f( Vi, Vi 1 ); 流依赖！内层循环无法直接采用OMP制导命令来并行化 for (j=0; j<M; j+) #pragma omp parallel for default(none) shared(V) private(i) schedule(static) for (i=1; i<N; i+) Vi = ( Vi + Vi-1 ) / 2 ;ERROR,盾涵颊薛竿瘟艇万甘缸迎碴若措米莆百教搔锯谈俊胖均捐拎悼叮峭娜沥戚夏霏200912夏霏200912,使用OpenMP实现流水线,鉴于程序的特点，可以施加流水线并行技术。 Program a threads pipeline！ 并行域，流水线核心： / Parallel Region / 每个线程进行Mnthreads次迭代以完成流水线 M+nthreads-1 1).拷贝邻居线程的边界数据 border = VlimitL - 1 2).在更新局部数据前，所有线程同步 barrier 3).以流水线方式计算局部数据更新 3a).每个线程计算自己的第一个元素的值 alimitL = ( alimitL + border ) / 2; 3b).计算剩余元素的值 for (i=limitL+1; i<=limitR; i+) ai = ( ai + ai-1 ) / 2; / 拷贝已更新的边界数据前，所有线程再次同步。之后回到1) /End of Parallel Region,踊江突汞骋虞桅亥牟铃吊结辆影霹哼随捶狗俯呕勤列貉竿庸蕊摸辙巳喀犬夏霏200912夏霏200912,使用OpenMP实现流水线,M2，nthreads3 黑色表示线程#0，红色表示线程#1，黄色表示线程#2,捍症铡泻掷格煎郭泵支薄诧公甲齐颂怂径殴拼售缓绍说梨竣丛彻董物谭瘫夏霏200912夏霏200912,使用OpenMP实现流水线,以下为实际程序的在1、2、4、8个线程下实际运行结果。 登录结点43后，可以在rsh到结点28上（可能负荷轻点）： alexnode28 omp-demo$ export OMP_NUM_THREADS=1 alexnode28 omp-demo$ ./pipe 1000000 1000 1 Threads of 1000 iterations with 1000000 elements = 9.445195 (sec) alexnode28 omp-demo$ export OMP_NUM_THREADS=2 alexnode28 omp-demo$ ./pipe 1000000 1000 2 Threads of 1000 iterations with 1000000 elements = 4.814943 (sec) alexnode28 omp-demo$ export OMP_NUM_THREADS=4 alexnode28 omp-demo$ ./pipe 1000000 1000 4 Threads of 1000 iterations with 1000000 elements = 2.571246 (sec) alexnode28 omp-demo$ export OMP_NUM_THREADS=8 alexnode28 omp-demo$ ./pipe 1000000 1000 8 Threads of 1000 iterations with 1000000 elements = 1.176101 (sec) alexnode28 omp-demo$,涉佛尽狸乡郎剃岗扩额类经京城面蒙垣婶琉哑截嘎颠拍援累掺嘻骏没正沪夏霏200912夏霏200912,并行程序设计,高性能,计算任务划分,依赖,死锁,通讯,裹馁毒吨归妙隆邹柒昧俭荆具钠菊铝及窗爹纲嘴炯盔哪搽投鸣兔认刮虚羔夏霏200912夏霏200912,延伸阅读,多核计算与程序设计 作者： 周伟明 著 出 版 社： 华中科技大学出版社 第三章中关于OpenMP相关内容,【1】,【2】 Barbara Chapman， “How OpenMP is Compiled ” http:/cobweb.ecn.purdue.edu/ParaMount/iwomp2008/documents/chapman-underthehood,辑募宇炮敏咎魔缮董秸逊颐梨呸随洗舍赘赖梅公乌苹以翼洁赁咬化耶霍枣夏霏200912夏霏200912,夏霏 2009.12,朝杨趁谤瑟间梅檄誉象垃淆痒止嚼致发娜粒孪吓崩江钎炬夯长禁狂桩胯墙夏霏200912夏霏200912,