基于图论方法的SHA-1差分路径的精准概率计算

针对SHA-1算法,Stevens提出了以联合概率为基础的高精度差分路径概率模型.它是一个理论值的求解方案,并将理论值分割成三个部分,但对差分路径的概率计算停留在理论层面,未能给出具体的计算方法.本文对第三部分概率进行深入分析,结合图论的方法证明了在由两类最优扰动向量得到的差分路径中,该部分的连通分支中只存在1个或2个布尔函数比特位的结构特性,并给出了两类连通分支的概率特征,利用这些结论可以简化求取差分路径成立概率的过程.最后通过一个差分路径实例展示了概率的具体计算过程,实例证明,本文的差分路径概率模型较原始计算方法(独立地计数充分条件的个数)得到的概率值更贴近真实值,表明了本文的改进概率模型可以对差分路径的概率进行更精准的刻画与计算.

一种针对线性循环结构的非线性静态调度策略

现有OpenMP调度策略通常采用动态策略处理程序中的线性循环结构,存在负载不均衡和调度开销大的问题。提出一种针对线性递增或线性递减循环结构的非线性静态调度策略Nonlinear;tatic。将线性循环负载均匀变化参数与总负载、负载峰值、线程数相结合构建调度模型,计算循环迭代在线程上的映射,使迭代块大小呈非线性递增或递减趋势。将线性循环的负载平均地分配在每个线程上,并在开源OMPi编译器中进行编码。在Adjoint Convolution、Compute Pots、Matrix Multiplication、Mandelbrot Set应用程序上进行多线程调度,实验结果表明,相比静态调度、动态调度、指导调度等策略,Nonlinear;tatic调度策略在处理线性循环结构时执行时间缩短了5%~10%,且具有无调度开销的优点。