片上网络中交叉开关调度算法的设计与优化

摘要

随着集成电路和半导体技术的高速发展，片上网络(NoC，Network-on-Chip)这一全新架构的提出有效缓解了基于传统共享总线架构的系统芯片出现的无法解决的瓶颈。路由节点和交叉开关是NoC中集成高性能IP的核心，其相应的调度算法几乎影响了NoC所有性能指标。然而传统的调度算法等同看待每一个端口的特点会带来较大延时，尤其是在实际业务流如语音或流媒体业务传输对网络延时的要求较高的情况下，对吞吐率的要求相对延时而言较低一些，此时适当牺牲一部分吞吐率作为代价来提升延时性能就显得尤为重要。
　　本文结合路由节点和交叉开关的架构，分析了现有主流调度算法不考虑权重的缺陷，其中具体分析了原本应用于大规模交换网络的iSLIP算法的执行步骤。首先，根据一次迭代三个执行步骤中只有请求步骤不需要任何调度的特点，将仲裁加入输入端口请求中，从而消除了接受步骤而简化为一次迭代中请求和授权两个执行步骤。其次，分别设定优先级为虚通道中队列排队队长和首元等待时间两种方式作为基于优先级权重设定的算法。然后，在分析了两种不同优先级选择的性能优劣之后将简化迭代步骤和基于队长优先级的算法相结合对iSLIP算法实现了进一步的改进。最后，搭建了基于片上网络的仿真平台BookSim2.0，分析了模拟器的运行机制和模块化的参数配置，对提出的算法进行代码化实现。
　　本文采用仿真平台自带的合成流量进行性能评估，在延时饱和点处，基于队长优先级的简化迭代算法在均匀的uniform流量模式下，延时比PIM和iSLIP分别下降了15.3％和3.0％，吞吐率比iSLIP下降了9.5％。在非均匀的transpose和tornado流量模式下，延时比PIM和iSLIP分别下降了14.6％、14.1％和9.2％、2.7％，吞吐率比iSLIP分别下降了3.9％和3.0％。算法延时指标下降了10％以上，而吞吐率指标下降控制在10％以内，算法实现性能良好，具有一定实际应用价值。

目录

声明

摘要

第一章 绪论

1．1 课题背景与意义

1．1．1 片上网络技术

1．1．2 片上网络交换机制

1．2 国内外研究现状

1．3 研究内容与设计指标

1．3．1 研究内容

1．3．2 设计指标

1．4 论文结构

第二章 片上网络概述

2．1 片上网络的定义

2．2 片上网络拓扑结构

2．2．1 规则拓扑结构

2．2．2 非规则拓扑结构

2．3 流控制策略

2．3．1 数据单元

2．3．2 无缓冲流量控制

2．3．3 缓冲流量控制

2．4 基于虚通道的路由器

2．4．1 路由节点微架构

2．4．2 交叉开关架构

2．5 交叉开关调度算法

2．5．1 调度算法性能要求

2．5．2 并行迭代匹配算法

2．5．3 轮询匹配算法

2．5．4 多次迭代的滑动轮询匹配算法

2．5．5 最大权重匹配算法

2．5．6 调度算法分析与比较

2．6 本章小结

第三章 基于优先级的简化迭代算法的设计

3．1 iS LIP算法具体分析

3．2 基于iSLIP算法的迭代步骤简化

3．3 基于iSLIP算法的优先级选择算法设计

3．3．1 无优先级算法延时分析

3．3．2 基于队长的优先级选择

3．3．3 基于首元等待时间的优先级选择

3．4 基于优先级的简化迭代算法

3．4．1 算法具体描述

3．4．2 算法实现总体流程图

3．5 基于优先级的简化迭代算法的特点

3．6 本章小结

第四章 仿真平台搭建与实验结果分析

4．1 NoC仿真平台搭建

4．1．2 BookSim2.0各模块参数配置

4．2 改进算法在仿真平台中的实现

4．2．1 轮询仲裁功能

4．2．2 权重选择功能

4．2．3 三步调度执行功能

4．3 流量模型

4．3．1 均匀流量模式

4．3．2 突发流量模式

4．4 实验具体参数配置

4．5 NoC性能评估指标

4．5．1 平均延时

4．5．2 吞吐率

4．6 实验结果与分析

4．6．1 BookSim2．0模拟器仿真结果

4．6．2 基于队列长度优先级选择算法实验(length)

4．6．3 基于首元等待时间优先级选择算法实验(waiting)

4．6．4 基于队长优先级简化迭代算法实验(select)

4．7 本章小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

攻读硕士学位期间发表的论文