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

《中科大多核并行计算课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多核并行计算MulticoreParallelComputing主讲人徐云2021/7/291现代密码学理论与实践之五第三篇并行数值算法第八章基本通信操作第九章稠密矩阵运算第十章线性方程组的求解2021/7/292现代密码学理论与实践之五第八章基本通信操作8.0预备知识8.1选路方法与开关技术8.2单一信包一到一传输8.3一到多播送8.4多到多播送2021/7/293现代密码学理论与实践之五预备知识（1）选路(Routing)又称为选径或路由。产生消息从发源地到目的地所取的路径,要求具有较低通讯延迟、无

2、死锁和容错能力。应用于网络或并行机上的信息交换。消息、信包、片消息(Message)：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。包(Packet)：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。片(Flit)：片的长度固定，一般为8位。预备知识（2）消息、信包、片的相互关系包消息包据片头片尾片……顺序号数片bitbitbitbitbitbitbitbit预备知识（3）互连网络、传输节点结构(1)互连网络可以表示为一个图G(V

3、,E),V={switchesornodes},EÍV×V(2)描述:拓扑(Topology)、选路算法(Routing)、流控制(FlowControl)(3)两个重要指标:传输时延(TransmissionLatency)、吞吐量(Throughput)(4)节点(开关)结构:二维mesh为例预备知识（4）一些术语信道带宽b：每个信道有w位宽和信号传输率f=1/t(t是时钟周期),b=wfbits/sec节点和开关的度：与节点和开关相连的信道数目路径：信包在网络中走过的开关和链路(link)序列路由

4、长度或距离：路由路径中包括的链路(link)数目信包传输性能参数启动时间ts(startuptime)：准备信包头信息等节点延迟时间th(per-hoptime)：信包头穿越相邻节点的时间字传输时间tw(transfertime)：传输每个字的时间链路数l、信包大小m预备知识（5）选路算法的三种机制基于算术的:开关中具有简单的算术运算功能，如维序选路；基于源地址的:在源点时就将沿路径的各个开关的输出端口地址p0,p1,…,pn包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离；基于查表的:开关中

5、含有一个选路表，对信包头中的选路域查出输出端口地址。预备知识（6）选路方式第八章基本通信操作8.0预备知识8.1选路方法与开关技术8.1.1选路方法8.1.2开关技术8.2单一信包一到一传输8.3一到多播送8.4多到多播送2021/7/2910现代密码学理论与实践之五选路方法（1）分类最短路径/非最短路径(贪心选路/随机选路)，如维序选路是贪心的，二阶段维序选路是随机的确定选路/自适应选路(寻径确定/寻径视网络状况)维序选路(Dimension-OrderedRouting)：一种确定的最短路径选路二维

6、网孔中的维序选路:X-Y选路超立方中的维序选路:E-立方选路选路方法（2）X-Y选路算法算法8.1：二维网孔上的X-Y选路算法beginstep1:沿X方向将信包送至目的地处理器所在的列step2:沿Y方向将信包送至目的地处理器所在的行end选路方法（3）例8.1(P185)注：本例无链路与节点竞争和死锁现象选路方法（4）E-立方选路算法路由计算：sn-1sn-2…s1s0(源地址)异或dn-1dn-2…d1d0(目的地址)rn-1rn-2…r1r0(路由值)路由过程：sn-1sn-2…s1s0sn-

7、1sn-2…s1s0r0sn-1sn-2…s1s0r1…算法8.2：超立方网络上的E-立方选路算法(P185)选路方法（5）例8.2(P185)0110(S)1101(D)1011(R)第八章基本通信操作8.0预备知识8.1选路方法与开关技术8.1.1选路方法8.1.2开关技术8.2单一信包一到一传输8.3一到多播送8.4多到多播送2021/7/2916现代密码学理论与实践之五开关技术（1）存储转发(Store-and-Forward)选路消息被分成基本的传输单位----信包(Packet),每个信

8、包都含有寻径信息；当一个信包到达中间节点A时，A把整个信包放入其通信缓冲器中，然后在选路算法的控制下选择下一个相邻节点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把信包从A发向B；信包的传输时间:tcomm(SF)=ts+(mtw+th)l=O(ml)缺点：每个结点必须对整个消息和信包进行缓冲，缓冲器较大；网络时延与发送消息所经历的节点数成正比。开关技术（2）切通(CutThrough)选路在传递一个消息之前，就为它建立一条从源节点到