第6章系统的互联和千兆位网络-第4节--并行处理与体系结构教学课件.ppt
《第6章系统的互联和千兆位网络-第4节--并行处理与体系结构教学课件.ppt》由会员分享,可在线阅读,更多相关《第6章系统的互联和千兆位网络-第4节--并行处理与体系结构教学课件.ppt(70页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、并行处理与体系结构并行处理与体系结构第第6 6章系统的互联和千兆位网络章系统的互联和千兆位网络n 1 1 互连网络基础互连网络基础n 2 2 静态连接网络静态连接网络n 3 3 动态连接网络动态连接网络n 4 4 消息传递机制消息传递机制n 5 5 千兆位网络技术千兆位网络技术n 6 ATM6 ATM交换器和网络交换器和网络哈尔滨工业大学计算机科学与技术学院 4 4 消息传递机制消息传递机制n主要研究:主要研究:q存储转发;存储转发;q虫蚀寻径方法;虫蚀寻径方法;q它们的通信时延问题;它们的通信时延问题;q针对无死锁的消息寻径确定的寻针对无死锁的消息寻径确定的寻径算法和自适应两种寻径算法。径算
2、法和自适应两种寻径算法。哈尔滨工业大学计算机科学与技术学院n一、一、消息寻径方式消息寻径方式n1.1.消息的格式消息的格式(1 1)消息)消息(message)(message)q是结点间通信的逻辑单位,它常常由任意数是结点间通信的逻辑单位,它常常由任意数目的长度固定的包组成,因此它的长度是可目的长度固定的包组成,因此它的长度是可变的。变的。n在消息传递网络中通信的信息单位是:消在消息传递网络中通信的信息单位是:消息、包和片的格式。息、包和片的格式。n消息寻径中的信息单位如下图所示。消息寻径中的信息单位如下图所示。哈尔滨工业大学计算机科学与技术学院(2 2)包)包(packet)(packet
3、)n是含寻径目的地址的基本单位;是含寻径目的地址的基本单位;n每个包需要一个序号;每个包需要一个序号;q不同的包可能异步地到达目的结点,不同的包可能异步地到达目的结点,以便把传送的消息重新装配起来。以便把传送的消息重新装配起来。n在采用在采用存储转发寻径方式存储转发寻径方式的多计算的多计算机系统中,包是信息传送的最小单机系统中,包是信息传送的最小单位。位。哈尔滨工业大学计算机科学与技术学院n包的长度取决于寻径方式和网络的实包的长度取决于寻径方式和网络的实现方法。现方法。n典型的包长度为典型的包长度为64-51264-512位。序号可位。序号可能占用能占用1-21-2个片,取决于消息的长度。个片
4、,取决于消息的长度。n包和片的大小还与通道频宽、寻径器包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关。设计以及网络流量密度等有关。哈尔滨工业大学计算机科学与技术学院n(3 3)片:)片:n包可分成一些固定长度的数据片。包可分成一些固定长度的数据片。寻径信息寻径信息(目的地址目的地址)和序号形成头和序号形成头片,其余的片是数据。片,其余的片是数据。n在采用虫蚀寻径网络的多计算机中,在采用虫蚀寻径网络的多计算机中,包可进一步分成片。包可进一步分成片。n片的长度往往受网络大小的影响,片的长度往往受网络大小的影响,256256个结点的网络需要片长为个结点的网络需要片长为8 8位。位。哈尔滨
5、工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院n3.3.虫蚀寻径虫蚀寻径 n新型的计算机系统都采用虫蚀寻径新型的计算机系统都采用虫蚀寻径方式,把包进一步分成更小的片;方式,把包进一步分成更小的片;n与结点相连的硬件寻径器中有片缓与结点相连的硬件寻径器中有片缓冲区。消息从源结点传送到目的结冲区。消息从源结点传送到目的结点要经过一系列寻径器。点要经过一系列寻径器。n同一个包中所有的片,象同一个包中所有的片,象不可分离不可分离的同伴一样以流水方式顺序地传送。的同伴一样以流水方式顺序地传送。哈尔滨工业大学计算机科学与技术学院n特点:特点:n所有数据片必须跟着头片。不同的包所有数据片必须
6、跟着头片。不同的包可交替地传送,但不同包的片不能交可交替地传送,但不同包的片不能交叉。否则它们可能被送到错误的目的叉。否则它们可能被送到错误的目的地。地。n虫蚀寻径的时延几乎与源和目的之间虫蚀寻径的时延几乎与源和目的之间的距离无关。的距离无关。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院n存储寻径网络的通信时延存储寻径网络的通信时延T TSFSF可表示为:可表示为:nT TSFSFL LW(D+1)W(D+1)n虫蚀寻径虫蚀寻径T TWHWH:T TWHWH L LW+
7、FW+FW DW Dn显然:显然:qT TSFSF与与D D成正比;成正比;q如果如果L LF F,那么,那么T TWHWH=L=LW W,距离,距离D D对寻径延时的影响可忽略不计。对寻径延时的影响可忽略不计。哈尔滨工业大学计算机科学与技术学院n典型的典型的T TSFSF值约在值约在20002000至至60006000 s s之间,之间,而典型的而典型的T TWHWH值只有值只有5 5 s s或者更小。或者更小。n存储转发寻径往往由软件控制,而存储转发寻径往往由软件控制,而虫蚀寻径则完全用硬件寻径器以流虫蚀寻径则完全用硬件寻径器以流水方式工作水方式工作。哈尔滨工业大学计算机科学与技术学院n二
8、、死锁和虚拟通道二、死锁和虚拟通道n1.1.虚拟通道虚拟通道 n虚拟通道是两个结点间的逻辑链,虚拟通道是两个结点间的逻辑链,它由源结点的片缓冲区、结点间的它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区物理通道以及接收结点的片缓冲区组成。组成。n下图说明了四条虚拟通道共享一条下图说明了四条虚拟通道共享一条物理通道的概念。物理通道的概念。哈尔滨工业大学计算机科学与技术学院n通道的特点:通道的特点:n两个端点增加了缓冲区和用来控制虚拟通两个端点增加了缓冲区和用来控制虚拟通道状态的道状态的R RA A线。实现虚拟通道需要用交线。实现虚拟通道需要用交叉开关控制、多路选择器和多路分配器。叉开
9、关控制、多路选择器和多路分配器。n物理通道由所有的虚拟通道分时地共享。物理通道由所有的虚拟通道分时地共享。以片传递为基础的分时方法可使一组虚拟以片传递为基础的分时方法可使一组虚拟通道共享一条物理通道。通道共享一条物理通道。n用某些通道状态用某些通道状态(如如R RA A信号信号)来表示不同来表示不同的虚拟通道,控制源缓冲区存放等待使用的虚拟通道,控制源缓冲区存放等待使用通道片。通道片。n通道通道(电缆或光纤电缆或光纤)是它们之间的通信媒介是它们之间的通信媒介哈尔滨工业大学计算机科学与技术学院n例题例题 通道上的循环等待引起的死锁通道上的循环等待引起的死锁n如下图所示,有两类死锁是由缓冲如下图所
10、示,有两类死锁是由缓冲区或通道上的循环等待引起的。区或通道上的循环等待引起的。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院n2.2.死锁的避免死锁的避免 n通过增加两条虚拟通道通过增加两条虚拟通道V3V3和和V4V4,可以,可以打破死锁循环。打破死锁循环。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院n双向通道与单项通道的实现比较双向通道与单项通道的实现比较n虚拟通道可以用单向通道或者双向通道实现。虚拟通道可以用单向通道或者双向通道实现。把两条单向通道组合可以构成一条双向通道;把两条单向通道组合可以构成一条双向通道
11、;n双向通道中的仲裁要复杂一点。双向通道中的仲裁要复杂一点。n单向通道相比较,双向通道由于要做方向仲裁,单向通道相比较,双向通道由于要做方向仲裁,因而增加了延迟,又由于控制复杂,因而还增因而增加了延迟,又由于控制复杂,因而还增加了成本。加了成本。n网络的流量不大时,双向通道效率比较高。网络的流量不大时,双向通道效率比较高。n确定虚拟通道数目时,需要对网络吞吐量和通确定虚拟通道数目时,需要对网络吞吐量和通信时延折衷考虑。实现数目很大的虚拟通道需信时延折衷考虑。实现数目很大的虚拟通道需要用高速的多路选择开关。要用高速的多路选择开关。哈尔滨工业大学计算机科学与技术学院n三、流控制策略三、流控制策略n
12、1.1.问题的提出:问题的提出:n当两个或更多的包在某个结点为竞争当两个或更多的包在某个结点为竞争缓冲区或通道资源而发生冲突时,必缓冲区或通道资源而发生冲突时,必须确定如何解决冲突的策略。须确定如何解决冲突的策略。q针对一对一通信寻径算法和自适应针对一对一通信寻径算法和自适应寻径算法进行讨论。寻径算法进行讨论。哈尔滨工业大学计算机科学与技术学院n2.2.包冲突的解决包冲突的解决 n必须具备三个条件:必须具备三个条件:q(1)(1)源缓冲区已存有该片;源缓冲区已存有该片;q(2)(2)通道已分配好;通道已分配好;q(3)(3)接收缓冲区准备接收该片接收缓冲区准备接收该片哈尔滨工业大学计算机科学与
13、技术学院n另外还存在:另外还存在:n当两个包到达同一个结点时,它们可当两个包到达同一个结点时,它们可能会请求用同一个接收缓冲区或者要能会请求用同一个接收缓冲区或者要用同一个输出通道,因此必须对两个用同一个输出通道,因此必须对两个问题做出仲裁:问题做出仲裁:n(1)(1)把通道分配给哪个包把通道分配给哪个包?n(2)(2)没有分配到通道的包做什么事没有分配到通道的包做什么事?哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院n3.3.两个包争用的解决方法:两个包争用的解决方法:n提出了一种虚拟直通寻径缓冲方法。提出了一种虚拟直通寻径缓冲方法。n
14、虚拟直通方法是存储转发和虫蚀两种寻径方法虚拟直通方法是存储转发和虫蚀两种寻径方法的折衷。当不发生冲突时,就如同虫蚀寻径方的折衷。当不发生冲突时,就如同虫蚀寻径方法一样工作。法一样工作。n最坏情况下,效果与存储转发寻径方法相同。最坏情况下,效果与存储转发寻径方法相同。n虫蚀寻径在出现冲突时就采用阻塞策略。虫蚀寻径在出现冲突时就采用阻塞策略。n第第2 2个包被阻塞不再前进,但并没有被扬弃。个包被阻塞不再前进,但并没有被扬弃。n某些多计算机网络综合了以上某些流控制策略某些多计算机网络综合了以上某些流控制策略的优点,采用混合策略。的优点,采用混合策略。哈尔滨工业大学计算机科学与技术学院n4.4.维序寻
15、径维序寻径 n包寻径可以归结为确定和自适应两类。包寻径可以归结为确定和自适应两类。n确定寻径确定寻径q通信路径完全由源和目的地址确定。通信路径完全由源和目的地址确定。n维序寻径维序寻径q需要一种按照多维网络维序的特定顺序来选需要一种按照多维网络维序的特定顺序来选择后继通道。在二维网格网络中称为择后继通道。在二维网格网络中称为XYXY寻寻径,首先沿着径,首先沿着X X维方向确定路径,然后沿着维方向确定路径,然后沿着Y Y维方向选择路径。维方向选择路径。n代表是代表是E E立方体寻径立方体寻径(Ecube routing)(Ecube routing)方方法法哈尔滨工业大学计算机科学与技术学院n超
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 系统 千兆 网络 并行 处理 体系结构 教学 课件
限制150内