现代密码学理论和实践之五.pptVIP

Overview;;矩阵乘法并行实现方法;简单并行分块乘法;Cannon乘法;Cannon乘法;Cannon乘法;Fox乘法;Fox乘法;DNS乘法;;示例 C00=1×(-5)+2×7=9 C01=1×(-6)+2×8=10 C10=3×(-5)+4×7=13 C11=3×(-6)+4×8=14 ;算法描述: //令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 //按k维复制A, m=0 for all r in {p, rm= r2q+m} par-do //r0=r2的r Ar(m) ? Ar //A(001)?A(000),A(100)?A(101) endfor //A(011)?A(010),A(110)?A(111) endfor;Overview;十二、并行程序设计基础;教学和考核要点;并行程序设计基础;并行程序设计概述;1 并行程序设计难的原因;并行程序开发策略;2 并行语言的构造方法;;3 并行性问题;并行块 parbegin S1 S2 S3 …….Sn parend S1 S2 S3 …….Sn可以是不同的代码 并行循环: 当并行块中所有进程共享相同代码时 parbegin S1 S2 S3 …….Sn parend S1 S2 S3 …….Sn是相同代码 简化为 parfor (i=1; i=n, i++) S(i);用单代码方法说明SPMD 要说明以下SPMD程序: parfor (i=0; i=N, i++) foo(i) 用户需写一个以下程序: pid=my_process_id(); numproc=number_of _processes(); parfor (i=pid; i=N, i=i+numproc) foo(i) 此程序经编译后生成可执行程序A, 用shell脚本将它加载到N个处理结点上: run A –numnodes N;用SPMD伪造MPMD 要说明以下MPMD程序: parbegin S1 S2 S3 parend 可以用以下SPMD程序: parfor (i=0; i3, i++) { if (i=0) S1 if (i=1) S2 if (i=2) S3 } 因此, 对于可扩展并行机来说, 只要支持SPMD就足够了;3.2 静态和动态并行性 程序的结构: 由它的组成部分构成程序的方法;Process A: begin Z:=1 fork(B); T:=foo(3); end;3.3 进程编组 目的:支持进程间的交互,常把需要交互的进程调度在同一组中 一个进程组成员由：组标识符+ 成员序号 唯一确定. 3.4 划???与分配 原则: 使系统大部分时间忙于计算, 而不是闲置或忙于交互; 同时不牺牲并行性(度). 划分: 切割数据和工作负载 分配：将划分好的数据和工作负载映射到计算结点(处理器)上 分配方式 显式分配: 由用户指定数据和负载如何加载 隐式分配：由编译器和运行时支持系统决定 就近分配原则：进程所需的数据靠近使用它的进程代码;并行度(Degree of Parallelism, DOP):同时执行的分进程数. 并行粒度(Granularity): 两次并行或交互操作之间所执行的计算负载. 指令级并行 块级并行 进程级并行 任务级并行 并行度与并行粒度大小常互为倒数: 增大粒度会减小并行度. 增加并行度会增加系统(同步)开销 ;并行层次与代码粒度;并行层次;4 交互／通信问题;同步：导致进程间相互