7.13图150319

7.12图1302197.12元素视图I0型算法全过程例7.12.1FOR(i=K;i<=L;i++){D(i)=F(i)+E(i)IF(E(i).EQ.0)(7.10){F(i)=E(i-1)E(i)=D(i)}}一、构造闭体：FOR(i=K;i<=L;i++){D(i)=F(i)+E(i)………S1#LE(i)=E(i).EQ.0……...S2F(i)=E(i-1)………S3(7.11)E(i)=D(i)……....S4}图7.20是它的一个时序层次片断。辈份msmsmsms0F(1)——E(1)——E(1)E(0)F(2)——E(2)——E(2)F(3)——E(3)——E(3)F(4)——E(4)——E(4)｜r｜｜｜｜｜｜｜｜｜p｜p｜p｜p｜p｜p｜p｜p｜p｜｜｜｜｜｜｜｜｜1D(1)1#LE(1)2F(1)3D(2)1#LE(2)2D(3)1#LE(3)2D(4)1#LE(4)2｜r｜r｜r｜r｜p｜p｜p｜p｜｜｜｜2E(1)4E(2)4E(3)4E(4)4｜r｜r｜r｜p｜p｜p｜｜｜3F(2)3F(3)3F(4)3图7.20闭体(7.11)的一个时序层次片断二、识别闭体：等价变换时序层次达到标准形。图7.20是它的一个时序层次片段，其原始状态非标准形式，须对它实施等价变换。首先，第四语句的结点全部在第二辈上连片。其次，F(1)3可下拉至第三辈，使得第三语句的结点全部在第三辈上连片。剩下第一辈，第一语句与第二语句的结点犬牙交错。尽管其中含有p-r对，不过，无论令第一语句的结点靠左，第二语句的结点靠右连片，抑或第二语句的结点靠左，第一语句的结点靠右连片，皆不产生任何r-p逆对。这样的标准形，使得闭体无须暂存地可并行。再识别：确定闭体的目标语序。按照年长顺序遍历达到标准形的时序层次，即可排列出目标语序：目标语序<1,2,4,3>或<2,1,4,3>均可。S2是逻辑数据暂存语句，它管辖S3和S4。在闭体的两种目标语序<1,2,4,3>或<2,1,4,3>里，S2都领先于它所管辖的S3和S4。再识别成功。改写闭体。对于目标语序<1,2,4,3>，闭体的目标程序：D(K:L)=F(K:L)+E(K:L);………PS1#LE(K:L)=E(K:L).EQ.0;……...PS2E(K:L)=D(K:L);..…....PS4F(K:L)=E(K-1:L-1);………PS3对于目标语序<2,1,4,3>，闭体的目标程序：#LE(K:L)=E(K:L).EQ.0;……...PS2D(K:L)=F(K:L)+E(K:L);………PS1E(K:L)=D(K:L);..…....PS4F(K:L)=E(K-1:L-1);………PS3再改写。对于目标语序<1,2,4,3>，原体的目标程序：D(K:L)=F(K:L)+E(K:L);………PS1#LE(K:L)=E(K:L).EQ.0;……...PS2IF(#LE(K:L))E(K:L)=D(K:L);..…....PS4IF(#LE(K:L))F(K:L)=E(K-1:L-1);………PS3对于目标语序<2,1,4,3>，原体的目标程序：#LE(K:L)=E(K:L).EQ.0;……...PS2D(K:L)=F(K:L)+E(K:L);………PS1IF(#LE(K:L))E(K:L)=D(K:L);..…....PS4IF(#LE(K:L))F(K:L)=E(K-1:L-1);………PS3优化。两种目标语序，所达到最终的目标程序均为：D(K:L)=F(K:L)+E(K:L);………PS1IF(E(K:L).EQ.0){E(K:L)=D(K:L);..…....PS4(7.12)F(K:L)=E(K-1:L-1);………PS3}模拟运行。设K＝1，L＝3。重新排列(7.10)的赋值语句，及其在(7.12)里相应的赋值语句序号如下：FOR(i=1;i<=3;i++){D(i)=F(i)+E(i)………..S1IF(E(i).EQ.0){(7.13)F(i)=E(i-1)………..S2E(i)=D(i)………..S3}}D(1:3)=F(1:3)+E(1:3);………PS1IF(E(1:3).EQ.0){(7.14)E(1:3)=D(1:3);..…....PS3F(1:3)=E(0:2);………PS2}二者模拟串行与模拟并行的结果，列于表(7.5)中。表7.5(7.13)式的模拟串行与(7.14)式的模拟并行表7.5.1逻辑条件<真，真，真>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口真真真QrStuvwxyz<1,1>X+u<1,2>t<1,3>X+u<2,1>Y+v<2,2>X+u<2,3>Y+v<3,1>Z+w<3,2>Y+v<3,3>Z+w串行出口真真真X+uy+vZ+wtX+uY+vZ+wtX+uY+v并行入口真真真QrstuvwxYzPS1X+uY+vZ+wPS3X+uY+vZ+wPS2tX+uY+v并行出口真真真X+uy+vZ+wtX+uY+vZ+wtX+uY+v表7.5.2逻辑条件<真，真，假>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口真真假QrStuvwxYz<1,1>X+u<1,2>t<1,3>X+u<2,1>Y+v<2,2>X+u<2,3>Y+v<3,1>Z+w<3,2><3,3>串行出口真真假X+uy+vZ+wtX+uY+vwtX+uZ并行入口真真假QrstuvwxYZPS1X+uY+vZ+wPS3X+uY+vPS2tX+u并行出口真真假X+uy+vZ+wtX+uY+vwtX+uz表7.5.3逻辑条件<真，假，真>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口真假真QrStuvwxYz<1,1>X+u<1,2>t<1,3>X+u<2,1>Y+v<2,2><2,3><3,1>Z+w<3,2>v<3,3>Z+w串行出口真假真X+uy+vZ+wtX+uvZ+wtYv并行入口真假真QrstuvwxYzPS1X+uY+vZ+wPS3X+uZ+wPS2tv并行出口真假真X+uY+vZ+wtX+uvZ+wtYv表7.5.4逻辑条件<真，假，假>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口真假假QrStuvwxYz<1,1>X+u<1,2>t<1,3>X+u<2,1>Y+v<2,2><2,3><3,1>Z+w<3,2><3,3>串行出口真假假X+uy+vZ+wtX+uvwtYZ并行入口真假假QrstuvwxYZPS1X+uY+vZ+wPS3X+uPS2t并行出口真假假X+uy+vZ+wtX+uvwtYz表7.5.5逻辑条件<假，真，真>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口假真真QrStuvwxYz<1,1>X+u<1,2><1,3><2,1>Y+v<2,2>X+u<2,3>Y+v<3,1>Z+w<3,2>Y+v<3,3>Z+w串行出口假真真X+uy+vZ+wtuY+vZ+wxX+uY+v并行入口假真真QrstuvwxYzPS1X+uY+vZ+wPS3Y+vZ+wPS2X+uY+v并行出口假真真X+uy+vZ+wtuY+vZ+wxX+uY+v表7.5.6逻辑条件<假，真，假>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口假真假QrStuvwxyz<1,1>X+u<1,2><1,3><2,1>Y+v<2,2>X+u<2,3>Y+v<3,1>Z+w<3,2><3,3>串行出口假真假X+uy+vZ+wtuY+vwxX+uZ并行入口假真假QrstuvwxYZPS1X+uY+vZ+wPS3Y+vPS2X+u并行出口假真假X+uy+vZ+wtuY+vwxX+uz表7.4.7逻辑条件<假，假，真>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口假假真QrStuvwxYz<1,1>X+u<1,2><1,3><2,1>Y+v<2,2><2,3><3,1>Z+w<3,2>v<3,3>Z+w串行出口假假真X+uy+vZ+wtuvZ+wXYv并行入口假假真QrstuvwxYzPS1X+uY+vZ+wPS3Z+wPS2v并行出口假假真X+uY+vZ+wtuvZ+wxYv表7.5.8逻辑条件<假，假，假>数组元素E(1)=0E(2)=0E(3)=0D(1)D(2)D(3)E(0)E(1)E(2)E(3)F(1)F(2)F(3)串行入口假假假QrStuvwxYz<1,1>X+u<1,2><1,3><2,1>Y+v<2,2><2,3><3,1>Z+w<3,2><3,3>串行出口假假假X+uy+vZ+wtuvwXYZ并行入口假假假QrstuvwXYZPS1X+uY+vZ+wPS3PS2并行出口假假假X+uy+vZ+wtuvwXYz从表7.5可知，遍历三个逻辑条件所有可能的八种运行组合，串行与并行的结果全部相符。@再纳入运算数据的暂存，我们有更加完整，当然也更加复杂的全过程如下。例7.12.2FOR(j=M;j<=L;j++){X(j)=Z(j)*Y(j)IF(W.GT.X(j))去掉这里的(7.14){Z(j)=Y(j)Y(j)=Z(j+1)}}一、构造闭体：FOR(j=M;j<=L;j++){X(j)=Z(j)*Y(j)………S1#LX(j)=W.GT.X(j).……...S2(7.15)Z(j)=Y(j)………S3Y(j)=Z(j+1)……....S4}图7.21是它的一个时序层次片断。辈份mssmssms0Z(1)——Y(1)——Y(1)Z(2)——Z(2)——Y(2)——Y(2)Z(3)——Z(3)——Y(3)——Y(3)Z(4)｜r｜r｜｜r｜r｜｜r｜r｜｜p|p｜p｜p｜p｜p｜p｜p｜p｜｜｜｜｜｜｜｜｜1X(1)1Z(1)3Y(1)4X(2)1Z(2)3Y(2)4X(3)1Z(3)3Y(3)4｜｜｜｜p｜p｜p｜｜｜2#LX(1)2#LX(2)2#LX(3)2图7.21闭体(7.15)的一个时序层次片断二、识别闭体：2.1等价变换时序层次达到标准形。图7.21是它的一个时序层次片段，其原始状态非标准形式，须对它实施等价变换。首先，第二语句的结点全部在第二辈上连片。其次，X(2)1可越过Z(1)3和Y(1)4左移至X(1)1身旁，X(3)1可越过Z(2)3和Y(2)4、Z(1)3和Y(1)4左移至X(2)1身旁，使得第一语句的结点全部在第一辈左方连片，并且无需调动任何p-r对。剩下，第三语句与第四语句的结点犬牙交错于第一辈的右方。其中含有p-r对、、、和。若令第三语句居左、第四语句居右，则须调动和两个p-r对。这里采用6.17节的图解法，推导它的序号仨。图7.22，是从图7.21截取出来的和p-r对。1、r链所指结点的语句序号，就是α=3；2、p链始结点的语句序号，就是β=4；3、n=0（不含m链），其父母序号γ=n+1=1。求得它的序号仨<3,4,1>。对于p-r对，重复此过程，结果一样。0Z(2)Z(3)｜｜｜pr|pr｜｜1Y(1)4Z(2)3Y(2)4Z(3)3图7.22p-r对和至于第三语句居右、第四语句居左，完全类似；限于篇幅，不再赘述。三、再识别：3.1闭体业已达到标准形，而且在此标准形中，#LX(1)2、#LX(2)2和#LX(3)2，跟Z(1)3、Y(1)4、Z(2)3、Y(2)4、Z(3)3和Y(3)4，均无影响执行次序的约束关系。所以，闭体相应的目标语序是<1,<3,4>||<2>>，表示<1,3,4,2>、<1,3,2,4>、<1,2,3,4>皆可。由于S2是逻辑数据暂存语句，它管辖S3和S4，使得闭体的三种目标语序里，只有<1,2,3,4>满足S2领先于S3和S4的条件。取<1,2,3,4>，再识别成功。四、改写闭体。4.1无暂存地中间改写。对于目标语序<1,2,3,4>，闭体的目标程序：X(M:L)=Z(M:L)*Y(M:L)………PS1#LX(M:L)=W.GT.X(M:L).……...PS2Z(M:L)=Y(M:L)………PS3Y(M:L)=Z(M+1:L+1)……....PS44.2构造暂存语句。把序号仨<α,β,γ>＝<3,4,1>代入：#Aα,0(Iβ,γ(I0):Iβ,γ(I1):cβ,γ*s)=Aα,0(Iβ,γ(I0):Iβ,γ(I1):cβ,γ*s)我们得到：#A3,0(I4,1(I0):I4,1(I1):c4,1*s)=A3,0(I4,1(I0):I4,1(I1):c4,1*s)亦即：#Z(M+1:L+1)=Z(M+1:L+1)。4.3把暂存语句插入中间程序。位置是在目标语句PSα即PS3的前面：X(M:L)=Z(M:L)*Y(M:L)………PS1#LX(M:L)=W.GT.X(M:L).……...PS2#Z(M+1:L+1)=Z(M+1:L+1)Z(M:L)=Y(M:L)………PS3Y(M:L)=Z(M+1:L+1)……....PS4其中包含了两个暂存语句：逻辑数据暂存语句和运算数据暂存语句，各一。4.4把临时数组替换进去获得最终的目标程序。对于目标语序<1,2,3,4>，从序号仨<α,β,γ>＝<3,4,1>，得知β＝4，γ＝1。于是，该替换的对象是A4,1＝Z，从而获得闭体最终的目标程序：X(M:L)=Z(M:L)*Y(M:L)#LX(M:L)=W.GT.X(M:L)#Z(M+1:L+1)=Z(M+1:L+1)Z(M:L)=Y(M:L)Y(M:L)=#Z(M+1:L+1)五、再改写。对于闭体的目标语序<1,2,3,4>，原体的目标程序：X(M:L)=Z(M:L)*Y(M:L)#LX(M:L)=W.GT.X(M:L)IF(#LX(M:L))#Z(M+1:L+1)=Z(M+1:L+1)IF(#LX(M:L))Z(M:L)=Y(M:L)IF(#LX(M:L))Y(M:L)=#Z(M+1:L+1)其中，运算数据暂存语句的执行条件可省略，亦即改有条件为无条件。六、优化。由于影响逻辑数据#LX(M:L)取值的X(M:L)，在后续的三个句子里皆无变化，可省略为：X(M:L)=Z(M:L)*Y(M:L)IF(W.GT.X(M:L))#Z(M+1:L+1)=Z(M+1:L+1)IF(W.GT.X(M:L))Z(M:L)=Y(M:L)IF(W.GT.X(M:L))Y(M:L)=#Z(M+1:L+1)又由于三个被控语句连片，可合并。所达到最终的目标程序为：X(M:L)=Z(M:L)*Y(M:L)IF(W.GT.X(M:L)){#Z(M+1:L+1)=Z(M+1:L+1)Z(M:L)=Y(M:L)Y(M:L)=#Z(M+1:L+1)}@