中科大多核并行计算课件3789593.ppt

现代密码学理论与实践之五 多核并行计算Multicore Parallel Computing 主讲人 徐 云 第三篇 并行数值算法 第八章 基本通信操作 第九章 稠密矩阵运算 第十章 线性方程组的求解  第八章 基本通信操作 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 预备知识（1） 选路(Routing) 又称为选径或路由。产生消息从发源地到目的地所取的路径, 要求具有较低通讯延迟、无死锁和容错能力。应用于网络或并行机上的信息交换。 消息、信包、片 消息(Message)：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。 包(Packet)：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。 片(Flit)：片的长度固定，一般为8位。 预备知识（2） 消息、信包、片的相互关系 预备知识（3） 互连网络、传输节点结构 (1)互连网络可以表示为一个图G(V,E), V={switches or nodes}, E í V×V (2)描述: 拓扑(Topology)、选路算法(Routing)、流控制(Flow Control) (3)两个重要指标:传输时延(Transmission Latency)、吞吐量(Throughput) (4)节点(开关)结构:二维mesh为例 预备知识（4） 一些术语 信道带宽b：每个信道有w位宽和信号传输率f = 1/t (t是时钟周期), b = wf bits/sec 节点和开关的度：与节点和开关相连的信道数目 路径：信包在网络中走过的开关和链路(link)序列 路由长度或距离：路由路径中包括的链路(link)数目 信包传输性能参数 启动时间ts(startup time)：准备信包头信息等 节点延迟时间th(per-hop time)：信包头穿越相邻节点的时间 字传输时间tw(transfer time)：传输每个字的时间 链路数l 、信包大小m 预备知识（5） 选路算法的三种机制 基于算术的: 开关中具有简单的算术运算功能，如维序选路； 基于源地址的: 在源点时就将沿路径的各个开关的输出端口地址p0,p1,…,pn包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离； 基于查表的: 开关中含有一个选路表，对信包头中的选路域查出输出端口地址。 预备知识（6） 选路方式 第八章 基本通信操作 8.0 预备知识 8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 选路方法（1） 分类 最短路径/非最短路径(贪心选路/随机选路)， 如维序选路是贪心的，二阶段维序选路是随机的 确定选路/自适应选路(寻径确定/寻径视网络状况) 维序选路(Dimension-Ordered Routing)： 一种确定的最短路径选路 二维网孔中的维序选路: X-Y选路 超立方中的维序选路: E-立方选路 选路方法（2） X-Y选路算法 算法8.1：二维网孔上的X-Y选路算法 begin step1: 沿X方向将信包送至目的地处理器所在的列 step2: 沿Y方向将信包送至目的地处理器所在的行 end 选路方法（3） 例8.1 (P185) 注：本例无链 路与节点竞争 和死锁现象 选路方法（4） E-立方选路算法 路由计算： sn-1sn-2…s1s0(源地址) 异或 dn-1dn-2…d1d0(目的地址) rn-1 rn-2 …r1 r0 (路由值) 路由过程： sn-1sn-2…s1s0 ? sn-1sn-2…s1s0 r0 ? sn-1sn-2…s1s0 r1 ? … 算法8.2 ：超立方网络上的E-立方选路算法(P185) 选路方法（5） 例8.2 (P185) 0110(S) 1101(D) 1011(R) 第八章 基本通信操作 8.0 预备知识 8.1 选路方法与开关技术 8.1.