• / 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://www.pqsozv.live/p-6180578.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
钻石光影