主权项 |
一种程序数据与代码局部性的量化方法,其特征在于包括以下步骤:a)使用剖析工具对程序的指令特征及数据特征进行剖析;b)获取剖析结果:指令访问数据信息、指令及数据的组织信息、运行时热度信息;c)将步骤b)中获取的结果用作原始程序特征信息来进行后续计算;d)使用右手坐标系建立空间坐标系OXYZ;e)在步骤d)中建立的空间坐标系OXYZ基础上,进一步构造可视化程序特征空间坐标图,使用步骤c)中获取的基础信息向步骤d)中所建立的空间坐标系映射,具体包括:ⅰ)将数据项映射为X轴即数据维度,将指令项映射为Y轴即指令维度,将热度项映射为Z轴即热度维度;ⅱ)将指令及数据的组织信息映射为轴内的摆放方式;ⅲ)将指令使用数据映射为空间坐标中的单位立方体;单位立方体体积V为1,赋予密度属性ρ并置初始值为1,得其初始质量M = ρV = 1;f)在建立的空间坐标系中放置立方体,具体包括:ⅰ)从原点开始,X轴、Y轴和Z轴分别向其正方向依次使用单位为1的立方空间;ⅱ)当Y轴指令项第一次访问X轴数据项,在XY相应立方空间坐标处放置立方体,当Y轴指令项再次访问X轴数据项时,在XY相应立方空间坐标处向上叠加单位立方体;g)将步骤e)中的热度维度(Z轴)投射为立方体密度,具体包括:ⅰ)定义Zmax为存在立方体的空间坐标的Z分量的最大值;ⅱ)使用Z=Zmax处的XY平面向Z轴负方向挤压,停止于Z=1处的XY平面;ⅲ)将各XY坐标处存在的立方体密度ρ设为其投射之前立方柱高度;使用投射后的程序空间坐标图计算局部性程度,具体包括:ⅰ)定义Xmax为存在立方体的空间坐标的X分量的最大值,Ymax为存在立方体的空间坐标的Y分量的最大值;ⅱ)定义局部性程度计算的输入为[Ys,Ye];Ys为目标局部的Y轴坐标的开始处,Ye为目标局部的Y轴坐标结束处,0 <= Ys < Ye <= Ymax;ⅲ)计算[Xs,Xe]:使用X = 0处的YZ平面向X轴正向移动,当其受到[Ys,Ye]范围的立方体表面阻止时停止,令Xs等于停止位置处的X坐标;使用X = Xmax处的YZ平面向X轴负向移动,当其受到[Ys,Ye]范围内的立方体表面阻止时停止,令Xe等于停止位置处的X坐标;ⅳ)当前程序空间坐标图中的平面X‑ Xs = 0,X–Xe = 0,Y–Ys = 0, Y–Ye = 0, Z = 0,Z–1 = 0确定了目标局部的长方体表示;j)设局部性程度为L(Ys,Ye),使用步骤h)中ⅳ)确定的目标局部的长方体表示及其相关属性包括密度、边沿,计算目标局部的局部性程度,具体包括:ⅰ)当局部内部无跳转跳出长方体范围时,有L(Ys,Ye) = M(Xs,Xe,Ys,Ye,0,1)/V(Xs,Xe,Ys,Ye,0,1)= (∑(ρXiYj * V(Xi,Xi+1,Yj,Yj+1,0,1))) /((Xe‑Xs) * (Ye‑Ys)) 其中,M(Xs,Xe,Ys,Ye,0,1)指长方体的质量,V(Xs,Xe,Ys,Ye,0,1)为长方体的体积,ρXiYi为平面X–Xi = 0,X–(Xi + 1) = 0,Y–Yj = 0,Y–(Yj + 1) = 0,Z = 0,Z–1 = 0所围的立方体的投射密度,Xi和Yi均为整数且Xi∈[X1,X2‑1]、Yj∈[Y1,Y2‑1];ⅱ)当局部内部有跳转跳出立方体范围时,使用跳转位置的XZ平面切分当前长方体;设当前长方体被切分成的子长方体数为n,切分位置Y分量坐标分别为(Y1,Y2,Y3…Yn‑1),其跳转方向对应为(D1,D2,…Dn‑1),对任意的Di(1<=i<=n‑1)有Di = Ys或Di = Ye;Di = Ys表示跳转方向为Y轴负向,Di = Ye表示跳转方向为Y轴正向;对每一个子长方体,分别计算其局部性程度:L(Ys,Y1) = M(Xs,Xe,Ys,Y1,0,1)/(V(Xs,Xe,Ys,Y1,0,1) + V(X1,X2,Y1,D1,0,1))L(Y1,Y2) = M(Xs,Xe,Y1,Y2,0,1)/(V(Xs,Xe,Y1,Y2,0,1) + V(X1,X2,Y1,D2,0,1))…L(Yn‑1,Ye) = M(Xs,Xe,Yn‑1,Ye,0,1)/(V(Xs,Xe,Yn‑1,Ye) + V(X1,X2,Yn‑1,Ye,0,1))使用上述计算的局部性程度结果作为子长方体修正密度,用此修正密度计算子长方体的质量:M(Ys,Y1) = L(Ys,Y1) * V(Xs,Xe,Ys,Y1,0,1)M(Y1,Y2) = L(Y1,Y2) * V(Xs,Xe,Y1,Y2,0,1)…M(Yn‑2,Yn‑1) = L(Yn‑2,Yn‑1) * V(Xs,Xe,Yn‑2,Yn‑1,0,1)M(Yn‑1,Ye) = L(Yn‑1,Ye) * V(Xs,Xe,Yn‑1,Ye,0,1)使用上述计算结果再次计算局部性程度:L(Ys,Ye) = (M(Ys,Y1) + M (Y1,Y2) … + M(Yn‑1,Ye))/V(Xs,Xe,Ys,Ye,0,1);其中:所述剖析工具为编译器及运行时统计分析工具。 |