西电数模选修作业.doc

《数学模型》 2017年期末考试大作业 选题:校赛A题 学院： 学号： 姓名 时间：2017年4月27日----2017年5月4日 NOC 结构的研究 摘要 片上网络作为一种新的片上系统通信架构， 在多核处理器方面得到广泛应用。 本文针对片上网络映射时的不同拓扑结构， 分别设计了考虑能耗、 链路带宽、芯片温度时， 所对应的最优映射方案。 针对问题一， 在 2D Mesh 拓扑结构和 2D Torus 拓扑结构中引 入曼哈顿距离来计算 IP 核之间传递信息所经过的链路数， 由此得出传递信息经过的路由器数。考虑到曼哈顿距离在高维的局限性， 在超立方拓扑结构中， 引 入用 0, 1 赋值的四维向量来表示 IP 核在拓扑图中的位置， 进而计算出链路数与路由器数， 建立单目 标无约束优化模型， 利用遗传算法求出体系能耗最低的映射方案。 针对问题二， 对于链路选择问题， 通过在链路表示上引 入高维向量， 将 2DMesh， 2D Torus 和超立方体拓扑结构中的链路分别限制在 2*4*3, 2*4*4 和4*2*2*2 向量矩阵以实现链路的具体表达， 在 the west-first and odd-even 路由算法的启发下提出了方向限定， 对于 2D Mesh, 2D Torus 模型， 限定路径按向下， 向右两个次序选取， 对于超立方体模型， 限定路径按单立方体向右， 向下，向里， 以及外立方体向内四个次序选取。 将带宽放在目 标函数层考虑， 结合能耗最低， 建立线性加权多目 标优化模型， 利用问题一的方法进行求解。 针对问题三， 通过定义两个 IP 核之间的热转移关系即热阻?来得到 IP 核温度求解公式， 结合第一问的能耗最低模型， 利用 IP 核的功耗求解得到 IP 核的温度， 并将 IP 核温度之间的标准差作为目 标优化函数， 利用遗传算法进行单目 标优化问题求解， 得到温度分布较为均衡的映射方案。综上所述， 本文讨论了 NOC 影响因素功耗， 功耗以及带宽， 以及温度对映射的影响， 最后对所建立的模型及算法进行了评价。 关键词： 片上网络 曼哈顿距离 遗传算法 线性加权多目 标优化 热分布 一、 问题重述1 .1 .问题的背景处理器逐渐步入多核时代， 人们日 常使用的手机已经是四核甚至八核。 英特尔公司面向高性能计算推出了 48 核的商用芯片。 芯片上每一个核都可以独立的执行不同的任务， 有效的提升了处理器的计算能力。 随着芯片上集成的IP 核数目 不断增加， 传统总线结构资源利用率低、 可扩展性差、 可重用性差等缺点也越发的突出。 为了克服总线结构的不足， 一种新的片上系统通信架构——片上网络(NoC) 应运而生。片上网络映射， 是指在给定任务核图和拓扑结构的基础上， 针对特定设计目标和约束条件， 决定每个IP核在片上网络拓扑结构上的位置， 使映射之后的系统达到较高的网络性能。 对于既定的片上网络拓扑结构， 映射性能的好坏决定着网络最终实现后的整体性能， 不同的映射匹配结果会导致网络性能差异较大。 映射的目 的就是要找到尽可能优的分配方案， 使系统的性能达到最优。 衡量映射方案性能好坏的主要指标有能耗、 时延、 吞吐、 热量均衡以及服务质量以及算法的时间复杂度等。IP核在运行过程中会产生热量， 当大量IP核集成在芯片上时， 运行过程中芯片的温度将迅速升高， 而过高的芯片温度会影响系统的性能。 而当系统到达稳定状态时， 每个IP核的温度取决于IP核的功耗和IP核之间的热阻。1 .2.问题的提出（1） 以题目 所给的任务图为例， 针对每种拓扑结构建立映射优化模型， 并采用优化算法求解最低能耗开销。 已知信息传播过程中的能耗主要考虑路由器和链路上的能耗开销， 1bit信息在链路和路由器的能耗分别为 5. 445pJ和 0. 43pJ。（2） 全网路由器之间的链路带宽是一个定值（例如 500Mbps） ， 如果在一条链路上传输的信息量之和超过这一定值， 则该段链路会出现阻塞。 在问题 1的基础上， 建立多目 标优化模型实现低能耗开销的无阻塞映射方案。（3） 请查找资料对参数进行合理假设， 针对每种拓扑结构设计相应的映射方案使得片上网络中IP核的温度分布较为均衡。 二、 问题分析2.1 .问题一的分析问题一要求在信息传播过程中仅考虑路由器和链路上的能耗开销时， 针对不同的拓扑结构寻找一种IP核到片上网络节点的一对一的映射关系， 使得信息传播过程中的能耗开销最小。要在给定核图和拓扑图的情况下求解最小