专用片上网络设计方法：通信建模、拓扑构造与自动生成

论文摘要

随着特征尺寸进入纳米量级和芯片面积的不断扩大,全局连线的延时上升以至数倍于芯片时钟,传统的总线和端对端连接结构已经不能满足片上系统（System-on-Chip,SoC）的通信需求。片上网络（Network-on-Chip,NoC）使用基于数据包传输的方法,为模块之间的互联提供了高效、可靠、灵活的通信架构,成为解决片上系统通信问题最有潜力的方案之一。由于芯片面积、功耗和性能的限制,片上网络必须针对特定的应用专门定制;通过分析片上系统特定的通信需求,设计专用的片上网络是可行的。本文通过提取片上系统的通信特征,构造片上网络的拓扑结构,自动生成网络结构的源代码,给出了专用片上网络（application-specificNoC）设计的一般方法。本文定义了片上系统的对象消息级原型,使用面向对象的方法对系统进行建模,然后利用特定的规则把对象映射为硬件模块,把对象间的函数调用映射为网络上的消息传递,从而完成系统划分和通信特征提取。利用该原型开发的H.263系统原型验证了这种方法的可行性。本文将拓扑构造问题转化为离散平面上的模块布局与流量布线问题,在通信能量代价、时延代价和网络面积代价等方面进行了优化。本文讨论了用于片上网络拓扑构造的离散平面必要的性质,给出四种离散平面实例,总结了它们的几何性质。逐点分裂的模块布局算法使用演化的方法学习和适应系统与网络之间的耦合关系,与随机布局结果相比可以节省30%的能量代价和20%的时延代价。并行串行混合的流量布线算法使用最短路径连接通信模块,并优化网络面积代价,可节省10%–30%的离散平面布线通道。本文定义了基于源路由算法和虫孔交换策略的通信协议,可以适应不规则的拓扑结构,适宜设计简洁的路由器。本文设计了可配置的路由器模板,提供了巨大的片上网络设计空间,完成了网络硬件描述源代码的自动化生成。本文通过对一系列的路由器的逻辑综合结果进行线性拟合,确立了路由器代价与各配置参数之间的相关系数,可用于指导路由器的配置。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 片上网络概述
• 1.1.1 片上系统遇到新的设计挑战
• 1.1.1.1 来自芯片工艺的挑战
• 1.1.1.2 来自系统设计的挑战
• 1.1.1.3 已有的片上系统通信结构
• 1.1.2 片上网络：一种新的片上系统通信方案
• 1.1.2.1 片上网络的定义
• 1.1.2.2 片上网络的优点
• 1.1.3 片上网络的特点和设计要求
• 1.1.4 片上网络与片上系统的关系
• 1.2 片上网络研究进展
• 1.2.1 片上网络的发展历史
• 1.2.2 片上网络研究的关键问题
• 1.2.2.1 系统建模与通信模拟
• 1.2.2.2 片上网络拓扑结构的选择与综合
• 1.2.2.3 通信协议和网络组件
• 1.2.2.4 片上网络的设计自动化
• 1.2.2.5 片上网络的性能验证与测试
• 1.3 本文研究的主要内容和主要贡献
• 1.3.1 本文研究的主要内容
• 1.3.2 论文结构
• 第2章 片上系统的对象消息级建模
• 2.1 片上系统的自顶向下的建模与设计流程
• 2.1.1 处理核的综合
• 2.1.2 片上网络的综合
• 2.2 片上系统对象消息级原型
• 2.2.1 对计算与存储的抽象：对象
• 2.2.2 对通信的抽象：函数调用
• 2.2.3 处理并行性：消息的发射与返回
• 2.2.4 系统与对象的线程原型
• 2.2.4.1 系统线程原型
• 2.2.4.2 单线程对象与多线程对象
• 2.2.4.3 主动对象与被动对象
• 2.3 片上系统对象消息级原型的硬件实现
• 2.3.1 对象的硬件实现：处理核的综合
• 2.3.1.1 对象硬件实现的一般原型
• 2.3.1.2 主动对象的典型原型
• 2.3.1.3 被动对象的典型原型
• 2.3.2 函数调用的硬件实现：片上网络综合
• 2.3.2.1 网络接口和通信协议
• 2.3.2.2 网络拓扑综合与生成
• 2.4 片上系统对象消息级原型的软件实现与流量分析
• 2.4.1 构建系统原型的一般流程
• 2.4.2 采用System C 实现的模拟平台
• 2.4.2.1 片上网络的抽象
• 2.4.2.2 系统模块的抽象
• 2.4.2.3 成员函数与消息的抽象
• 2.4.3 片上系统通信流量的分析方法
• 2.5 H.263 实例分析
• 2.5.1 H.263 编解码器的对象原型
• 2.5.2 典型的设计模式分析
• 2.5.3 实验结果
• 2.5.4 片内通信流量特点分析
• 2.6 本章小结
• 第3章 用于片上网络拓扑构造的二维离散平面
• 3.1 使用二维离散平面的原因、定义和任务
• 3.1.1 使用二维离散平面的原因
• 3.1.2 二维离散平面的定义
• 3.1.3 二维离散平面的性质
• 3.1.3.1 表示方法
• 3.1.3.2 节点和边的密度
• 3.1.3.3 最短路径和拓扑距离
• 3.2 4 邻接网格和8 邻接网格
• 3.2.1 4 邻接网格
• 3.2.2 8 邻接网格
• 3.3 6 邻接网格和3 邻接网格
• 3.3.1 6 邻接网格
• 3.3.2 3 邻接网格
• 3.4 本章小结
• 3.4.1 四种离散平面的比较
• 3.4.2 其它的离散平面结构
• 第4章 片上网络拓扑构造的模块布局算法
• 4.1 系统模拟和模块布局并行的网络演化框架
• 4.1.1 片上网络的设计是一个演化过程
• 4.1.1.1 片上网络的通信时序分析是统计的
• 4.1.1.2 片上系统运行与片上网络通信是相互影响的
• 4.1.1.3 片上网络的拓扑结构优化应该是一个演化过程
• 4.1.2 网络演化的动力分析
• 4.1.2.1 网络收缩的动力分析
• 4.1.2.2 网络扩张的动力分析
• 4.1.3 系统运行和模块布局的相互作用的模拟框架
• 4.1.3.1 片上网络演化框架
• 4.1.3.2 基于TGFF 的随机系统模拟器
• 4.2 片上网络拓扑构造的分析
• 4.2.1 片上网络拓扑构造的形式化定义
• 4.2.2 对问题P1 的分析
• 4.3 基于组迁移逐点分裂的模块布局算法
• 4.3.1 模块布局问题的形式化定义
• 4.3.2 逐点分裂的模块布局算法
• 4.3.2.1 逐点分裂算法的一般形式
• 4.3.2.2 分裂点的选择
• 4.3.2.3 目标点的选择
• 4.3.2.4 确定划分的比例
• 4.3.2.5 组迁移划分算法
• 4.3.3 逐点分裂模块布局算法的实验结果
• 4.3.3.1 逐点分裂的典型过程
• 4.3.3.2 算法在四种离散平面的实验结果
• 4.3.3.3 算法的性能
• 4.4 本章小结
• 第5章 片上网络拓扑构造的流量布线算法
• 5.1 流量布线问题的定义与评价方法
• 5.1.1 流量布线问题的形式化定义
• 5.1.2 流量布线算法的评价方法
• 5.2 串行流量布线算法
• 5.2.1 算法描述
• 5.2.1.1 广度优先搜索算法
• 5.2.1.2 回溯算法
• 5.2.1.3 串行流量布线算法
• 5.2.2 适用条件和特殊情况的处理
• 5.2.3 算法在4 邻接网格上的典型过程
• 5.3 并行流量布线算法
• 5.3.1 算法描述
• 5.3.2 适用条件和特殊情况的处理
• 5.3.3 算法在4 邻接网格上的典型过程
• 5.4 先并行后串行的混合流量布线算法
• 5.5 三种流量布线算法的优化效果
• 5.5.1 三种流量布线算法在四种离散平面的实验结果
• 5.5.2 混合算法与串行、并行算法之间的关系
• 5.6 离散平面上模块布局和流量布线算法（FRoD）分析
• 5.7 本章小结
• 第6章 专用片上网络的通信协议
• 6.1 任意网络拓扑结构的定义
• 6.1.1 路由器间的网络拓扑结构
• 6.1.2 路由器内部的拓扑结构
• 6.2 适合专用片上网络的通信协议：源路由和虫孔交换
• 6.2.1 基于源路由方式的路由协议设计
• 6.2.2 虫孔交换策略
• 6.2.3 拥塞控制
• 6.2.4 到达保证
• 6.2.5 源路由和虫孔交换的局限
• 6.3 源路由和虫孔交换的通信性能分析和实验结果
• 6.3.1 基于源路由和虫孔交换的通信协议时延分析
• 6.3.2 示例系统的模拟结果
• 6.4 本章小结
• 第7章 片上网络的自动化生成方法
• 7.1 基于源路由和虫孔交换方式的路由器模板设计
• 7.1.1 路由器的整体结构
• 7.1.2 输入端口的结构
• 7.1.3 输出端口的结构
• 7.1.4 单体路由器
• 7.2 自动化生成程序
• 7.2.1 网络配置空间
• 7.2.2 验证自动生成的网络源代码
• 7.3 路由器模板的逻辑综合分析
• 7.3.1 路由器系列和逻辑综合约束
• 7.3.2 面积与模板参数的关系
• 7.3.3 延时与模板参数的关系
• 7.3.4 功耗与模板参数的关系
• 7.3.5 片上网络设计中的路由器选择策略
• 7.3.6 与文献中路由器实例设计的比较
• 7.4 本章小结
• 第8章 结论
• 8.1 全文总结
• 8.2 进一步研究的考虑
• 参考文献
• 致谢
• 附录A TGFF生成的用于模块布局和流量分布的测试数据
• 个人简历、在学期间发表的学术论文与研究成果