学位论文 > 优秀研究生学位论文题录展示

基于二维Mesh网络的片上组播通信关键技术研究

作　者: 胡文敏
导　师: 刘衡竹
学　校: 国防科学技术大学
专　业: 电子科学与技术
关键词: 组播同构众核处理器片上网络分布式共享存储死锁路由算法
分类号: TN47
类　型: 博士论文
年　份: 2012年
下　载: 44次
引　用: 0次
阅　读: 论文下载

内容摘要

随着集成电路技术的飞速发展和高性能计算需求的强力推动，片上系统遵循着如下发展趋势：从多核到众核，从总线到网络，从集中存储到分布式存储，从二维集成到三维集成。片上网络因高带宽、低功耗、易扩展特点成为众核系统的理想互联架构。大规模并行计算基本处理单元也由处理器转变为计算核，程序的并行性很大程度上受核间通信能力的制约。组播作为一种典型的通信模式广泛存在于大规模并行计算中，并成为影响同构众核处理器并行性能的关键要素。传统单播路由器对组播只能提供软件级的支持，严重影响大规模并行计算的性能，因此高效的组播路由器体系结构成为片上通信领域的重要课题。本文立足于二维mesh网络架构的CMP处理器平台，从组播路由算法与机制、组播死锁避免机制，组播通信加速方面展开研究工作，并进行了详细的评测与性能分析。本文的主要研究成果和创新性体现在以下几个方面：1）提出一种二阶段增量式组播路径构建方法（TPSS），实现了对组播树形多样化支持，从而能够在底层支持多种组播算法。在TPSS中，第一阶段单播设置包路由到一个预定的中间节点，然后更改目标节点；第二阶段，单播设置包路由到新目标节点的过程中同步更新路由表，写入路由信息。一个单播设置包建立一条分支路径，多个累加形成组播树。基于该机制，提出三种组播树搜索算法：1.OPT，在west-first转向模型指导下构建高带宽效率组播树，该算法针对所有组播目标节点执行全局优化，尽可能生成功耗高效、带宽高效组播树，使得所用链路最少；2.LXYROPT，这是一种部分优化算法，同样满足死锁避免的west-first转向模型。该算法对覆盖位于源节点右边区域目标节点的组播路径实行优化，剩余区域采用XY组播树路由算法，该算法中所有目标节点到源节点都是最短路径，在保证了组播性能同时降低了功耗。3.CFG，通过缩放因子控制组播树的最长路径，在其约束下，得到功耗高效、带宽高效组播树。缩放因子可以改变组播树形，其性能、功耗介于OPT与LXYROPT之间。所提算法均是离线算法，可在编译期间生成，适用于组播通信模式相对固定的应用，通信模式的获取可以采用全系统模拟方式。针对组播通信模式不确定的应用，TPSS俱备实时动态构建组播树功能，具体实现上，通过禁止构建过程的第一阶段，以第二阶段的形式实现XY组播路由算法。硬件综合结果表明，所提机制硬件开销极小。评测结果表明，所提算法根据应用目的不同，获得不同的功耗带宽节省。2）针对单播设置包增量建立组播树机制，提出集成清除功能的组播路径建立方法和利用现有树构建新树策略。基于路由表的组播机制中，若能复用查找表项，清除过期信息，建立新组播树，无疑能够节省硬件资源。本文提出一种内建清除机制的组播树建立方式，该方式通过判断设置包是否在本组播树已建路径上来选择操作策略：若是，则将路由结果添加到表项中；若不是，则先清除表项原有内容后再添加。与ID机制相比，该方式不仅打破了重用次数的限制，而且不需要在表中保留ID位，节省了面积开销。同时为进一步减少组播树建立延迟，本文提出一套借用旧组播树建立新组播树机制，实验表明，当符合重用条件时，其能够有效减少建立延迟。3）针对组播并发通信引起的交叉依赖型死锁，在分析CMP多线程并行测试程序通信记录前提下，提出一种混合机制预防死锁，并在片上网络级对虚拟化提供支持。本文针对负载控制命令的短报文，采用整包缓存，多读指针异步复制；针对负载数据的长报文，采用集中式仲裁控制并发组播数量。混合机制实现简单，硬件开销小。考虑到基于目录协议的CMP多线程并行应用程序通信记录中组播报文占比很小，长报文组播更甚，该机制对性能影响极其低微，实验结果也予以证实。针对NoC级虚拟化支持所需的通信隔离问题，该混合机制允许集中时仲裁器分别控制不同子网的长报文组播并发数量，提高了整个CMP所支持的长报文组播并发数。4）为了降低通信中跳步延迟，提出一种自选择伪电路机制（SP）。SP根据开关仲裁历史信息旁路开关请求，减少流水线级数，提高通信性能。通过分析片上并行程序通信记录发现，网络通信局部性使得路由器某个输入端口高概率重复使用，而输出端口则变化频繁，已有的伪电路机制不能很好适应这种变化。SP允许多个输出端口对同一个输入端口保留连接，为避免报文误送，路由信息用来选择所使用的连接。为进一步消除虚通道匹配给伪电路复用率的影响，本文选择无虚通道虫孔直通路由器XHINoC，将SP的复用条件放宽为：同一个输入端口和输出端口是保留连接输出端口的子集。实验结果表明，SP能够明显提高性能。此外，本文采用位串地址编码，使得组播报文的路由计算可以在一个时钟周期内完成，提升了组播通信性能；单微片报文的支持，使得报文不需要ID槽记录路由信息以指导后续微片路由，减少了路由器中的ID槽需求数量，节省了硬件开销。

全文目录

摘要  10-12
Abstract  12-15
第一章绪论  15-33
  1.1 研究背景  15-22
    1.1.1 多核系统的发展  15-17
    1.1.2 片上网络的发展  17-19
    1.1.3 并行计算中的组播需求  19-21
    1.1.4 路由器体系结构面临的挑战  21-22
  1.2 相关研究工作  22-32
    1.2.1 组播路由算法  22-24
    1.2.2 组播死锁避免  24-26
    1.2.3 路由机制  26-27
    1.2.4 组播地址编码  27-28
    1.2.5 路由器加速  28-30
    1.2.6 本文主要工作  30-32
  1.3 论文结构  32-33
第二章二阶段增量式组播路径建立及路由算法研究  33-59
  2.1 引言  33
  2.2 二阶段增量式组播路径建立机制  33-40
    2.2.1 协议  33-36
    2.2.2 网络接口控制器  36
    2.2.3 路由器结构  36-37
    2.2.4 报文转换逻辑  37-39
    2.2.5 二阶段增量式组播路径建立实例  39-40
  2.3 带宽、功耗高效组播路由算法  40-47
    2.3.1 死锁避免  40-42
    2.3.2 OPT组播路由算法  42-43
    2.3.3 LXYROPT组播路由算法  43
    2.3.4 CFG组播路由算法  43-47
    2.3.5 XY组播树支持  47
  2.4 硬件开销估计  47
  2.5 实验与结论  47-56
    2.5.1 组播树开销  47-51
    2.5.2 纯组播通信模式性能评估  51-52
    2.5.3 混合通信模式性能评估  52-55
    2.5.4 长报文性能评估  55-56
    2.5.5 功耗评估  56
  2.6 本章小结  56-59
第三章集成清除功能低延迟组播建立方式  59-70
  3.1 引言  59
  3.2 现有方法局限性  59-63
    3.2.1 基于ID组播树清除方法的局限  59-62
    3.2.2 组播清除报文方法局限  62-63
  3.3 集成清除功能的低延迟组播树建立机制  63-67
    3.3.1 集成清除功能的组播树建立机制  63-65
    3.3.2 利用旧树建新树的低延迟建立方法  65-67
  3.4 面积评估  67
  3.5 建立延迟评估  67-69
  3.6 小结  69-70
第四章一种预防死锁的混合机制  70-81
  4.1 引言  70-71
  4.2 整包缓冲异步复制机制  71-73
    4.2.1 两种机制结合  71
    4.2.2 实现  71-73
  4.3 集中式控制并发长报文组播数量机制  73-77
    4.3.1 应用需求  73-74
    4.3.2 集中式分配算法  74-76
    4.3.3 集中式分配器实现  76
    4.3.4 死锁避免示例  76-77
  4.4 实验与结果分析  77-80
    4.4.1 CA对性能的影响  77-78
    4.4.2 面积开销  78-80
  4.5 小结  80-81
第五章自选择伪电路  81-108
  5.1 引言  81-82
  5.2 路由器体系结构  82-87
    5.2.1 报文格式和地址编码  82-83
    5.2.2 路由算法实现机制  83-84
    5.2.3 基于ID的路由机制  84-85
    5.2.4 局部ID管理  85-86
    5.2.5 混插路由示例  86-87
  5.3 伪电路复用  87-89
    5.3.1 伪电路  87-88
    5.3.2 伪电路变体  88-89
  5.4 自选择伪电路  89-93
    5.4.1 比较逻辑  89-90
    5.4.2 自选择逻辑  90-91
    5.4.3 自选择伪电路示例  91-93
  5.5 实验与结果分析  93-100
    5.5.1 方法  93-95
    5.5.2 结果分析  95-100
  5.6 功耗面积分析  100-105
    5.6.1 ID槽保留量  100-103
    5.6.2 面积开销  103-105
    5.6.3 功耗开销  105
  5.7 讨论  105-106
    5.7.1 VP与虫孔路由中的伪电路比较  105
    5.7.2 扩展SP到虫孔路由器  105-106
  5.8 本章小结  106-108
第六章结束语  108-111
  6.1 论文工作总结  108-110
  6.2 课题研究展望  110-111
致谢  111-113
参考文献  113-124
作者在学期间取得的学术成果  124-125

基于二维Mesh网络的片上组播通信关键技术研究

内容摘要

全文目录

相似论文