中国科技大学并行计算课件8并行数值算法
39页1、并 行 计 算 中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2004年12月Date1现代密码学理论与实践之五第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 Date2现代密码学理论与实践之五第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 Date3现代密码学理论与实践之五 预备知识 选路(Routing) 又称为选径或路由。产生消息从发源地到目的地所取的路径, 要求具有较低通讯延迟、无死锁和容错能力。应用于网络或并行机上的信息交换。 消息、信包、片 消息(Message):是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位,可由任意数量的包构成。 包(Packet):包的长度随协议不同而不同,它是信息传送的最小单位,64-512位。 片(Flit):片的长度固定,一般为8位。Date4现代密码学理论与实践之五预备知识 消息、信包、片的相互关系包消息包据片头片尾片 顺序号数片F F F
2、F F F F FDate5现代密码学理论与实践之五 预备知识 一些术语 信道带宽b:每个信道有w位宽和信号传输率f = 1/t (t是时钟周期), b = wf bits/sec 节点和开关的度:与节点和开关相连的信道数目 路径:信包在网络中走过的开关和链路(link)序列 路由长度或距离:路由路径中包括的链路(link)数目 信包传输性能参数 启动时间ts(startup time):准备包头信息等 节点延迟时间th(per-hop time):包头穿越相邻节点的时间 字传输时间tw(transfer time):传输每个字的时间 链路数l 、信包大小mDate6现代密码学理论与实践之五 预备知识 选路算法的三种机制 基于算术的: 开关中具有简单的算术运算功能,如维序选路; 基于源地址的: 在源点时就将沿路径的各个开关的输出端口地址p0,p1,pn包在信包的头部,每个开关只是对信包头的输出端口地址进行剥离; 基于查表的: 开关中含有一个选路表,对信包头中的选路域查出输出端口地址。Date7现代密码学理论与实践之五 预备知识 选路方式 Date8现代密码学理论与实践之五第八章 并行数
3、值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 Date9现代密码学理论与实践之五8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术Date10现代密码学理论与实践之五 选路方法 分类 最短路径/非最短路径(贪心选路/随机选路),如维序选路是贪心的,二阶段维序选路是随机的 确定选路/自适应选路(寻径确定/寻径视网络状况) 维序选路(Dimension-Ordered Routing): 一种确定的最短路径选路 二维网孔中的维序选路: X-Y选路 超立方中的维序选路: E-立方选路 Date11现代密码学理论与实践之五 选路方法 X-Y选路算法 算法8.1:二维网孔上的X-Y选路算法 begin step1: 沿X方向将信包送至目的地处理器所在的列 step2: 沿Y方向将信包送至目的地处理器所在的行 endDate12现代密码学理论与实践之五 选路方法 例8.1 (P186)Date13现代密码学理论与实践之五 选路方法 E-立方选路算法 路由计算: sn-1sn-2s1s0(源地址) 异或
4、dn-1dn-2d1d0(目的地址) rn-1 rn-2 r1 r0 (路由值) 路由过程: sn-1sn-2s1s0 sn-1sn-2s1s0 r0 sn-1sn-2s1s0 r1 算法8.2 :超立方网络上的E-立方选路算法(P186)Date14现代密码学理论与实践之五 选路方法 例8.2 (P187) 0110(S) 1101(D) 1011(R)Date15现代密码学理论与实践之五8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术Date16现代密码学理论与实践之五 开关技术 存储转发(Store-and-Forward)选路 消息被分成基本的传输单位-信包(Packet), 每个信包都含有寻径信息; 当一个信包到达中间节点A时,A把整个信包放入其通信缓冲器中,然后在选路算法的控制下选择下一个相邻节点B,当从A到B的通道空闲并且B的通信缓冲器可用时,把信包从A发向B; 信包的传输时间: tcomm (SF) = ts + (mtw + th)l=O(ml) 缺点: 每个结点必须对整个消息和信包进行缓冲,缓冲器较大; 网络时延与发送消息所经历的节点数成正比D
《中国科技大学并行计算课件8并行数值算法》由会员东***分享,可在线阅读,更多相关《中国科技大学并行计算课件8并行数值算法》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2022-03-29 50页
2022-03-24 45页
2022-03-24 14页
2022-03-24 37页
2022-03-24 17页
2021-11-22 77页
2021-11-22 68页
2021-11-22 55页
2021-11-22 96页