现代密码学理论与实践之五.ppt

现代密码学理论与实践之五 Overview Review Of Last Session 并行程序设计基础 9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 DNS乘法 矩阵乘法并行实现方法 计算结构：二维阵列 空间对准(元素已加载到阵列中） Cannon’s , Fox’s，DNS 时间对准(元素未加载到阵列中） Systolic(心动阵列) 简单并行分块乘法 分块: A、B和C分成 的方块阵Ai,j、Bi,j和Ci,j, 大小均为 p个处理器编号为 , Pi,j存放Ai,j、Bi,j和Ci,j。 算法: ①通讯:每行处理器进行A矩阵块的多到多播送(得到Ai,k, k=0~ ) 每列处理器进行B矩阵块的多到多播送(得到Bk,j, k=0~ ) ②乘-加运算: Pi,j做 运行时间 (1)超立方连接： ①的时间 ②的时间 Cannon乘法 示例： A4×4， B4×4, p=16 Cannon乘法 示例： A4×4， B4×4, p=16 Cannon乘法 示例： A4×4， B4×4, p=16 Fox乘法 示例： A4×4， B4×4, p=16 (a) (b) Fox乘法 示例： A4×4， B4×4, p=16 (c) (d) DNS乘法 背景: 由Dekel、Nassimi和Sahni提出的SIMD-CC上的矩阵乘法, 处理器数目为n3, 运行时间为O(logn), 是一种速度很快的算法。 处理器编号: 处理器数p=n3= (2q)3=23q, 处理器Pr位于位置(i,j,k), 这里r=in2+jn+k, (0≤i, j, k≤n-1)。位于(i,j,k)的处理器Pr的三个寄存器Ar,Br,Cr分别表示为A[i,j,k], B[i,j,k]和C[i,j,k], 初始时均为0。 基本思想: 通过一到一和一到多的播送办法，使得处理器(i,j,k)拥有aji和bik,进行本地相乘,再沿i方向进行单点积累求和,结果存储在处理器(0,j,k)中。 算法: 初始时ajk和bjk存储于寄存器A[0,j,k]和B[0,j,k]; ①数据复制:A,B同时在i维复制(一到一播送)； A在k维复制(一到多播送); B在j维复制(一到 多播送); ②相乘运算:所有处理器的A、B寄存器两两相乘; ③求和运算:沿k方向进行单点积累求和; 示例 C00=1×(-5)+2×7=9 C01=1×(-6)+2×8=10 C10=3×(-5)+4×7=13 C11=3×(-6)+4×8=14 DNS乘法 算法描述: //令r(m)表示r的第m位取反； //{p, rm=d}表示r(0≤r≤p-1)的集合, 这里r的二 //进制第m位为d; //输入: An×n, Bn×n; 输出: Cn×n Begin //以n=2, p=8=23举例, q=1, r=(r2r1r0)2 (1)for m=3q-1 to 2q do //按i维复制A,B, m=2 for all r in {p, rm=0} par-do //r2=0的r (1.1) Ar(m) ? Ar //A(100)?A(000)等 (1.2) Br(m) ? Br //B(100)?B(000)等 endfor endfor (2)for m=q-1 to 0 do