太阳城集团

  • / 11
  • 下载费用:30 金币  

一种低功耗的片上网络任务映射方法.pdf

摘要
申请专利号:

太阳城集团CN201310710421.9

申请日:

2013.12.20

公开号:

CN103678245A

公开日:

2014.03.26

当前法律状态:

授权

有效性:

有权

法律详情: 授权|||实质审查的生效IPC(主分类):G06F 15/163申请日:20131220|||公开
IPC分类号: G06F15/163; G06F17/50 主分类号: G06F15/163
申请人: 武汉科技大学
发明人: 胡威; 邹代坤; 郭宏; 黎文飞; 张凯; 江若成; 李伟强; 谭练; 张若凡; 徐景
地址: 430081 湖北省武汉市和平大道947号
优先权:
专利代理机构: 杭州宇信知识产权代理事务所(普通合伙) 33231 代理人: 张宇娟
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201310710421.9

授权太阳城集团号:

||||||

法律状态太阳城集团日:

2017.04.19|||2014.06.18|||2014.03.26

法律状态类型:

太阳城集团授权|||实质审查的生效|||公开

摘要

本发明公开了一种低功耗的片上网络任务映射方法,包括如下步骤:S10:建立片上网络拓扑模型;S11:建立多任务模型;S12:确定约束条件;S13:建立映射集合;S14:进行任务与片上网络之间的映射。本发明一种低功耗的片上网络任务映射方法针对片上网络中多任务建立模型,分析多任务之间的关系,然后将任务在通信延迟和能耗的双重约束下进行映射,从而提高映射效率,降低映射功耗。

权利要求书

权利要求书
1.  一种低功耗的片上网络任务映射方法,其特征在于,包括如下步骤:
S10:建立片上网络拓扑模型;
S11:建立多任务模型;
S12:确定约束条件;
S13:建立映射集合;
S14:进行任务与片上网络之间的映射。

2.  如权利要求1所述低功耗的片上网络任务映射方法,其特征在于,步骤S14中,对任务集合T,按照任务的f值进行降序排序,如果两个或两个以上任务的f值相同,则按照任务的W值进行排序。

3.  如权利要求1所述低功耗的片上网络任务映射方法,其特征在于,步骤S14中,对处理器核集合C,按照处理器核的h值对处理器核进行降序排序。

4.  如权利要求3所述低功耗的片上网络任务映射方法,其特征在于,步骤S14中,从任务集合中取出第一个任务T0’,将其映射到所有处理器核中具有最大h值的处理器核。

说明书

说明书一种低功耗的片上网络任务映射方法
技术领域
本发明属于片上网络技术领域,涉及一种低功耗的片上网络任务映射方法。
背景技术
随着通用处理器的主频突破4GHz,人们发现单一提升主频的做法已经不能再有效地提高性能,反而却带来了功耗的急剧上涨,高频率的道路逐渐走到了尽头。于是对于计算机处理器的研究开始转向多处理核心的方向。早期的对称多处理器(SMP)多是采用在同一计算机上汇集一组CPU的方式,它们之间共享内存子系统以及总线结构。之后,由于纳米级制造工艺的引入,SMP开始转变为单芯片多处理器(Chip Multiprocessor,CMP),即在同一芯片上集成多个处理核心,形成了现在我们所说的多核处理器。处理器本身的结构关系到整个芯片的面积、功耗和性能。如何继承和发展传统处理器的成果直接影响到多核处理器的性能和实现周期。
多核处理器的各处理核执行的程序之间有时需要进行数据共享与同步,因此其硬件结构必须支持核间通信。高效的通信机制是多核处理器高性能的重要保障。目前片上高效通信机制通常有两种:基于共享总线的cache结构,基于片上网络的互连结构。基于共享总线的cache结构是指每个处理核拥有共享的二级或三级cache,用于保存比较常用的数据,并通过总线进行通信。这种系统的优点是结构简单,通信速度快;缺点是可扩展性差。
共享总线显然无法满足大规模系统的需要。把互连网络用于片上系统设计,解决片上组件之间的通讯问题,这就是片上网络。片上网络(-Network0n Chip,NoC)技术以其支持同时访问、可靠性高、可重用性高等特点被认为是更加理想 的大规模CMP互连技术,其克服了总线结构可扩展性差的缺点,为10亿晶体管时代提供了一种可行的片上系统通讯机制。
在片上网络中,如何将任务映射到片上网络的处理器核上是非常重要的问题。一方面需要满足任务之间的通信延迟的约束;另一方面,由于片上网络中通信能耗较高,需要尽可能的降低通信能耗。现有的映射方法往往采用复杂的方法来进行映射,需要耗费大量的太阳城集团来进行映射过程的计算,这在某种程度上也增加了能耗。
发明内容
为解决上述问题,本发明的目的在于提供一种低功耗的片上网络任务映射方法。
为实现上述目的,本发明的技术方案为:
一种低功耗的片上网络任务映射方法,包括如下步骤:
S10:建立片上网络拓扑模型;
S11:建立多任务模型;
S12:确定约束条件;
S13:建立映射集合;
S14:进行任务与片上网络之间的映射。
进一步地,步骤S14中,对任务集合T,按照任务的f值进行降序排序,如果两个或两个以上任务的f值相同,则按照任务的W值进行排序。
进一步地,步骤S14中,对处理器核集合C,按照处理器核的h值对处理器核进行降序排序。
进一步地,步骤S14中,从任务集合中取出第一个任务T0’,将其映射到所有处理器核中具有最大h值的处理器核。
相较于现有技术,本发明一种低功耗的片上网络任务映射方法针对片上网络中多任务建立模型,分析多任务之间的关系,然后将任务在通信延迟和能耗 的双重约束下进行映射,从而提高映射效率,降低映射功耗。
附图说明
图1是本发明的方法流程图示。
图2为本发明一实施例具有9个处理器核的片上网络的示意图。
图3为本发明一实施例对于6个任务的多任务模型通信关系图。
具体实施方式
为了使本发明的目的、技术方案及优点更加清楚明白,以下结合附图及实施例,对本发明进行进一步详细说明。应当理解,此处所描述的具体实施例仅仅用以解释本发明,并不用于限定本发明。
如图1所示,本发明一种低功耗的片上网络任务映射方法包括如下步骤:
S10:建立片上网络拓扑模型
对于片上网络,用N(C,P)表示,其中C是处理器核Cn的集合,P是通路Pij的集合;其中,Pij表示从处理器核Ci到处理器核Cj的一条通路。而s=|Ci→Cj|表示从处理器核Ci到处理器核Cj所经过的片上网络路由器的数量;Ebit表示1bit数据在两个相邻处理器核之间进行传输时的平均能耗;Er表示1bit数据在片上网络路由器上经过时的平均能耗;Lbit表示1bit数据在两个相邻处理器核之间进行传输时的平均延迟;Lr表示1bit数据在片上网络路由器上经过时的平均延迟;h(Ci)表示处理器核Ci在所有方向直接连接的处理器核的数量;C(Cj)表示与处理器核Ci具有直接连接的处理器核的集合。
则从处理器核Ci到处理器核Cj的能耗Eij为:
Eij=(s+1)*Ebit+s*Er      (1)
从处理器核Ci到处理器核Cj的延迟Lij为:
Lij=(s+1)*Lbit+s*Lr      (2)
S11:建立多任务模型
对于多个任务建立多任务模型,用U(T,Q)表示,其中T是任务Tm的集合; Q是qmn的集合,qmn表示任务Tm和Tn之间存在着通信关系;而L(qmn)表示任务Tm和Tn之间的通信延迟要求;fm表示与任务Tm存在通信关系的其他任务的数量;wij表示任务Tm和Tn之间的通信带宽;T(Tm)表示所有与任务Tm具有通信关系的任务的集合;W(Tm)表示任务Tm总的通信带宽。
S12:确定约束条件
对T中任务Tm和Tn,分别映射到片上网络的处理器核Ci和Cj,满足通信延迟的约束条件为:
Lij≤L(qmn)      (3)
所有任务都映射到片上网络后,所有已被映射的处理器核之间通信能耗为:
E=∑wij*Eij      (4)
则要使映射后的处理器核之间的通信能耗最小,即要使E最小;
S13:建立映射集合
为将要进行的映射,建立映射集合G,此时G中为空,为初始状态;
S14:进行任务与片上网络之间的映射
S140:对任务集合T,按照任务的f值进行降序排序,如果两个或两个以上任务的f值相同,则按照任务的W值进行排序;排序后新的任务集合为T’,T与T’之间的对应关系为Map(T←→T’);
S141:对处理器核集合C,按照处理器核的h值对处理器核进行降序排序;排序后新的任务集合为C’,C与C’之间的对应关系为Map(C←→C’);
S142:从T’中取出第一个任务T0’,将其映射到所有处理器核中具有最大的h值的处理器核Cx’上,并将(T0’,Cx’)加入到G中;
S143:从T’中取出第一个未被映射的任务Tm’,对于T(Tm’)中已被映射的任务所在的处理器核,计算将Tm’映射到这些处理器核中未被映射的直接连接的处理器核上的所有E值,去掉按照公式(3)不满足延迟的约束条件的E值;如果有两个或者两个以上相同的E值,则取min(E)为处理器核编号最小的处理器核Cmin’的E值,使用min(E)表示所有E值中最小的E值;计算将Tm’映射 到Cmin’上后,计算Cmin’和与其通信的处理器核的延迟,如果满足延迟的约束条件,进行映射,将(Tm’,Cmin’)加入到G中;如果不满足延迟的约束条件,则在去掉当前的min(E)的所有E值当中重新找到新的min(E);直到找到满足延迟的约束条件的Cmin’,进行映射,将(Tm’,Cmin’)加入到G中;如果T(Tm’)中不存在已被映射的任务,则从C’中选择第一个未被映射的处理器核Ck’进行映射,将(Tm’,Ck’)加入到G中;
S144:重复步骤S143,直到所有的任务均被映射到片上网络上;
S145:根据对应关系Map(T←→T’)和Map(C←→C’)将G中所有的映射对应到C和T上。
在本发明中,直接为片上网络和多任务建立模型,以更为简约的方式来进行映射,降低了映射方法的复杂性,提高了映射的速度;而通过任务之间的关系,来进行任务在片上网络中的映射,使得任务之间的通信延迟大大减少,从而有效的降低了片上网络的能耗。本发明适用于面向片上网络的任务映射,以片上网络的延迟为约束条件,将低功耗作为任务映射时的重要参数,既满足了片上网络对通信延迟的要求,又兼顾了通信时的功耗,从而在保证通信效率的情况下,降低了片上网络的功耗。
具体地,步骤S10中,以具有9个处理器核的片上网络为例进行说明。对于具有9个处理器核的片上网络,可表示为N(C,P),其中处理器核集合C中为:C0,C1,C2,C3,C4,C5,C6,C7,C8;而P如图2所示,处理器核之间可以通过连线进行通信。所有的s如下表所示:
sC0C1C2C3C4C5C6C7C8C0/01012123C10/0101212C210/210321C3012/01012C41010/0101C521010/210C6123012/01C72121010/0C832121010/
表1中“/”表示没有该项的值,如:C0和C0之间不存在使用路由器连接的情况。则:Ebit=1;Er=2;Lbit=1;Lr=2;h值如下表所示:
 C0C1C2C3C4C5C6C7C8h232243232
表2
所有的C(Cj)如下表所示:
 C(Cj)C0C1,C3C1C0,C2,C4C2C1,C5C3C0,C4,C6C4C1,C3,C5,C7C5C2,C4,C8C6C3,C7C7C4,C6,C8C8C5,C7
表3
能耗值如下表所示:
EijC0C1C2C3C4C5C6C7C8C0/141474710C11/1414747C241/2411074C3147/14147C44141/1414C574141/741C64710142/14C77474141/1C8107474141/
表4
延迟Lij如下表所示:
LijC0C1C2C3C4C5C6C7C8C0/141474710C11/1414747C241/2411074C3147/14147C44141/1414C574141/741C64710142/14C77474141/1C8107474141/
表5
步骤S11中,以6个任务为例进行说明,对于6个任务,建立多任务模型U(T,Q),其中T为:T0,T1,T2,T3,T4,T5;通信关系如图3所示。
通信延迟要求如下表所示:
L(qmn)T0T1T2T3T4T5T0/23334T12/1233T231/322T3323/23T43322/3T543233/
表6
f值如下表所示:
 T0T1T2T3T4T5f321213
表7
其中,w值如图3中连线上的数值。
T(Tm)如下表所示:
 T(Tm)T0T1,T3,T5T1T0,T5T2T4T3T0,T5T4T2T5T0,T1,T3
表8
W(Tm)如下表所示:
 T0T1T2T3T4T5W(Tm)8725210
表9
则对于具有9个核的片上网络和6个待映射任务,有如下过程:
(1)对T={T0,T1,T2,T3,T4,T5},排序结果为{T5,T0,T1,T3,T2,T4},则T’={T0’,T1’,T2’,T3’,T4’,T5’}。T与T’之间的对应关系为Map(T←→T’)如下表所示:
TT0T1T2T3T4T5T’T1’T2’T4’T3’T5’T0’
(2)C={C0,C1,C2,C3,C4,C5,C6,C7,C8},排序后为{C4,C1,C5,C7,C0,C2,C3,C6,C8};C’={C0’,C1’,C2’,C3’,C4’,C5’,C6’,C7’,C8’},C与C’之间的对应关系为Map(C←→C’)如下表所示:

(3)从T’中取出第一个任务T0’,将其映射到所有处理器核中具有最大的h值的处理器核C0’上,并将(T0’,C0’)加入到G中;此时G={(T0’,C0’)};
(4)从T’中取出第一个未被映射的任务,为T1’,T(T1’)中已被映射的任务所在的处理器核为C0’;
计算T1’映射到C0’上的未被映射的直接连接的处理器核上的所有E值,可映射的处理器核共有四个,分别为C1’,C2’,C3’,C6’;E值分别为:
映射到C1’:1
映射到C2’:1
映射到C3’:1
映射到C6’:1
由于E值均相等,则取处理器核编号最小的C1’,计算出C1’到C0’的通信延迟为1,满足延迟的约束条件;将(T1’,C1’)加入到G中,此时G={(T0’,C0’),(T1’,C1’)};
再从T’中取出第一个未被映射的任务,为T2’,T(T2’)中无已被映射的任务;则从C’中选择的第一个未被映射的处理器核为C2’,将(T2’,C2’)加入到G中;此时G={(T0’,C0’),(T1’,C1’),(T2’,C2’)};
再从T’中取出第一个未被映射的任务,为T3’,T(T3’)中已被映射的任 务所在的处理器核为C0’;C0’直接连接而未被映射的处理器核为C3’,C4’,C5’和C6’;E值分别为:
映射到C3’:5
映射到C4’:5
映射到C5’:5
映射到C6’:5
由于E值均相等,则取处理器核编号最小的C3’,计算出C3’到C0’的通信延迟为1,C3’到C1’的通信延迟为4,满足延迟的约束条件;将(T3’,C3’)加入到G中,此时G={(T0’,C0’),(T1’,C1’),(T2’,C2’),(T3’,C3’)};
再从T’中取出第一个未被映射的任务,为T4’,T(T4’)中已被映射的任务所在的处理器核为C2’;C2’直接连接而未被映射的处理器核为C5’和C8’;E值分别为:
映射到C5’:1
映射到C8’:1
由于E值均相等,则取处理器核编号最小的C5’,计算出C5’到C2’的通信延迟为1,满足延迟的约束条件,将(T4’,C5’)加入到G中;此时G={(T0’,C0’),(T1’,C1’),(T2’,C2’),(T3’,C3’),(T4’,C5’)};
再从T’中取出第一个未被映射的任务,为T5’,T(T5’)中已被映射的任务所在的处理器核为C0’和C1’;C0’和C1’直接连接而未被映射的处理器核为C4’和C6’;E值分别为:
映射到C4’:5
映射到C6’:5
由于E值均相等,则取处理器核编号最小的C4’,计算出C4’到C1’的通信延迟为1,计算出C4’到C0’的通信延迟为4,满足延迟的约束条件,将(T4’,C4’)加入到G中;此时G={(T0’,C0’),(T1’,C1’),(T2’,C2’),(T3’,C3’),(T4’,C4’)};
再从T’中取出第一个未被映射的任务,为T5’,T(T5’)中已被映射的任务所在的处理器核为C0’和C4’;C0’和C4’直接连接而未被映射的处理器核 为C6’;E值为:
映射到C6’:5
此时,计算计算出C6’到C4’的通信延迟为1,计算出C6’到C1’的通信延迟为4,满足延迟的约束条件,将(T5’,C6’)加入到G中;此时G={(T0’,C0’),(T1’,C1’),(T2’,C2’),(T3’,C3’),(T4’,C4’),(T5’,C6’)};
(6)根据对应关系Map(T←→T’)和Map(C←→C’)将G中所有的映射对应到C和T上,则为:
G={(T5,C4),(T0,C1),(T1,C5),(T3,C7),(T2,C0),(T4,C3)}
本具体实施方式将任务之间的通信延迟作为约束条件,既满足了片上网络对通信延迟的要求,又兼顾了通信时的功耗,从而在保证通信效率的情况下,实现了面向片上网络的低功耗任务映射。。
以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等,均应包含在本发明的保护范围之内。

关 键 词:
一种 功耗 网络 任务 映射 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种低功耗的片上网络任务映射方法.pdf
链接地址:http://zh228.com/p-6180578.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');