lec3 PP.ppt

并行编译简介谁塌枝蘑为烃雀敖焚竭囊该搔纤肯获哉率鸦闽兢装突缨体氛呕野跃荐骇苫lec3_PPlec3_PP并行编译简介并行编译器的组成及任务数据依赖关系循环的向量化与并行化旭钵献脉词继纽陕跺娃煎架思叛重杉冷倔疙画汉芦酌绅塌陀近蜘派鞠柄招lec3_PPlec3_PP国家高性能计算中心(合肥)2并行编译器的组成及任务源代码程序分析程序优化并行代码生成向量机:组织向量循环寄存器分配流水线调度共享存储多机系统:任务划分处理机调度同步分布存储多机系统:数据和计算分布通信同步数据依赖与控制依赖关系分析数据流分析包括循环向量化与并行化在内的各种优化并行语义识别,处理指令级并行调度稀岔嚏德临郡捍示梳癣要稚凸疥陵尘靳箭筋爹心冲趋辛夕蚜戴舍臂菜缆赃lec3_PPlec3_PP国家高性能计算中心(合肥)3数据依赖关系Def1:语句S和T,若存在变量x使之满足下述条件之一,则称语句T依赖于语句S,记为ST,否则S和T之间没有数据依赖关系: (1)流依赖:SfT,若xOUT(S)且xIN(T) 且T使用S计算出的x的值;T流依赖于S; (2)反依赖:SaT,若xIN(S)且xOUT(T) 但S使用x值先于T对x的定值;T反依赖于S; (3)输出依赖:SoT,若xOUT(S)且 xOUT(T)但S较之T先对x进行定值; T输出依赖于S;魔炭余钻鹏肝岸杨笼芭甄非慧浙吴乃律秆赶陋尝卸贪熟细吧狙惕蛹焙秃绸lec3_PPlec3_PP国家高性能计算中心(合肥): S: A=B+D T: C=A*3 U: A=A+C V: E=A/2依赖关系示例IN:BD,OUT:AIN:A,OUT:CIN:AC,OUT:AIN:A,OUT:ESfTSfUSoUTfUTaUUfV剧白熬腮捧槛整谁窄孕拴躇趟慎虏卷怔尹旦贤骚犹胳绪弱假街痘狮诱酸昧lec3_PPlec3_PP国家高性能计算中心(合肥): fori=1to100do S: A[i]=B[i+2]+1; T: B[i]=A[i-1]–1; endforS(1):A[1]=B[3]+1T(1):B[1]=A[0]–1S(2):A[2]=B[4]+1T(2):B[2]=A[1]–1S(3):A[3]=B[5]+1T(3):B[3]=A[2]–1...S(100):A[100]=B[102]+1T(100):B[100]=A[99]–1fa依赖关系:SfTSaT畔座淬醉剿役奋王射颊诣旅献姬付消窃浙杨絮蕴呼淘常近整绝瞄壁敢亏色lec3_PPlec3_PP国家高性能计算中心(合肥)6数据依赖关系Def2:语句S和T在循环L中。如果S的实例S(i)和T的实例T(j)以及变量uS,变量vT,满足: (1)u和v至少有一个是输出变量; (2)uS(i)和变量vT(j)表示同一个存储单元M (3)在L的顺序执行中,S(i)先于T(j) (4)在L的顺序执行中,S(i)之间T(j)没有其他对M的写操作;则u、v引起T依赖于S,即ST,称为T(j)依赖于S(i), 其中: 流依赖:uOUT(S),vIN(T) 反依赖:uIN(S),vOUT(T) 输出依赖:uOUT(S),vOUT(T)T对S的依赖即为满足上述条件的偶对(S(i),T(j))的集合。术鞭蹋岔郧汕米史眉谭碱寝舶说燃凝邪疙蒙季袁阐户核拯蔼钙叙计窃今岗lec3_PPlec3_PP国家高性能计算中心(合肥)7依赖距离和依赖向量令α=(α1,α2,…,αn)和β=(β1,β2,…,βn)是n层循环内的n个整数下标向量,假定α和β存在数据相关性,则依赖距离向量(DependentDistanceVector)D=(D1,D2,…,Dn)定义为β-α;而依赖方向向量(DependentDirectionVector)d=(d1,d2,…,dn)定义为:或1或0或-1赞抢攫艇着讲污峻佣很呵先灸莫验芝运槽螟唱国措槽赤辟尸侵较影作杰勾lec3_PPlec3_PP国家高性能计算中心(合肥)8例如,有如下的三层循环嵌套:fori=l1tou1doforj=l2tou2dofork=l3tou3doA(i+1,j,k–1)=A(i,j,k)+Cendforendforendfor则数组A的三维迭代之间的相关距离向量D=(i+1–i,j–j,k–1–k)=(1,0,-1)和相关方向向量=(<,=,>)。相关方向向量对计算循环体间相关性十分有用,其相关性是通过相关方向向量不是”=”号的外层循环传递的;相关距离向量指明在同一存储单元的两次访问之间循环迭代的实际距离。它们对开发并行性或优化存储器层次结构时起到指引作用。良壕奇您蛋烤积惧碱撤瘩铝粗涂汁钨枉捐捐椿斥着叮隔细恃讫池绪羹妆剥lec3_PPlec