[發明專利]一種基于連接特征的多任務集合劃分方法

有效

• 申請號: 201310692186.7
• 申請日: 2013-12-17
• 公開（公告）號: CN103631751A
• 公開（公告）日: 2014-03-12
• 發明（設計）人: 胡威;鄒代坤;黎文飛;張凱;郭宏;李偉強;張若凡;徐景;譚練;江若成
• 申請（專利權）人: 武漢科技大學
• 主分類號: G06F15/163
• 分類號: G06F15/163;G06F9/50
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 張火春

技術領域

本發明屬于片上網絡技術領域，特別是涉及一種基于連接特征的多任務集合劃分方法。

背景技術

根據摩爾定律，微處理器的速度以及單片集成度每18個月就會翻一番。半導體工業在近幾十年的發展中一直在追隨著摩爾定律的節奏，微處理器的頻率也不斷攀升。隨著通用處理器的主頻突破4GHz，人們發現單一提升主頻的做法已經不能再有效地提高性能，反而卻帶來了功耗的急劇上漲，高頻率的道路逐漸走到了盡頭。

于是對于計算機處理器的研究開始轉向多處理核心的方向。早期的對稱多處理器（SMP，Symmetric?Multi-Processor）多是采用在同一計算機上匯集一組CPU的方式，它們之間共享內存子系統以及總線結構。之后由于納米級制造工藝的引入，SMP開始轉變為單芯片多處理器（CMP，Chip?Multiprocessor），即在同一芯片上集成多個處理核心，形成了現在我們所說的多核處理器。多核心之間直接共享緩存以及總線結構，大大地降低了線延遲，顯著提高了通訊效率。

按處理核的對等與否，多核處理器可分為同構多核和異構多核。處理核相同、地位對等的稱為同構多核。現在市面上流行的Intel和AMD的多核處理器就是同構的多核處理器。處理核不同、地位不對等的稱為異構多核。異構多核一般采用“主處理器＋協處理器”的設計。IBM、索尼和東芝等聯手推出的Cell處理器正是這種異構架構的典范。處理器本身的結構關系到整個芯片的面積、功耗和性能。如何繼承和發展傳統處理器的成果直接影響到多核處理器的性能和實現周期。

多核處理器的各處理核執行的程序之間有時需要進行數據共享與同步，因此其硬件結構必須支持核間通信。高效的通信機制是多核處理器高性能的重要保障。目前片上高效通信機制通常有兩種：基于共享總線的cache結構，基于片上網絡的互連結構。基于共享總線的cache結構是指每個處理核擁有共享的二級或三級cache，用于保存比較常用的數據，并通過總線進行通信。這種系統的優點是結構簡單，通信速度快；缺點是可擴展性差。

共享總線顯然無法滿足大規模系統的需要。把互連網絡用于片上系統設計，解決片上組件之間的通訊問題，這就是片上網絡。片上網絡(-Network?On?Chip，NoC)技術以其支持同時訪問、可靠性高、可重用性高等特點被認為是更加理想的大規模CMP互連技術。片上網絡克服了總線結構可擴展性差的缺點，為10億晶體管時代提供了一種可行的片上系統通訊機制。片上網絡除了可以連接更多的IP組件，與總線結構相比，還有高可重用性等特點。

在片上系統設計中，可重用性是一個重要的設計原則。可重用性設計可以節省設計成本，提高設計的可靠性，縮短產品的上市周期。在基于總線的片上系統設計中，各個IP組件是重用的，但通訊結構卻無法重用。每個設計都需要重新設計通訊結構。在片上網絡中，除了各個組件是可重用的，片上通訊結構以及片上的通訊服務也是可重用的。設計新的系統時，在原有的系統上添加路由器和新的功能部件就可以了，以前的設計得到了重用，大大加快了設計的進度。同時，片上網絡還具有低功耗的特點，它采用全局異步、局部同步設計，端到端的通訊方式，只有參與通訊的組件是激活的，避免了總線結構中采用廣播方式進行通訊所造成的系統的功耗浪費，因此大大降低了系統的功耗。

在片上網絡中，提供了豐富的計算資源，實現多任務的并行，這就需要完成多任務的調度、管理，尤其是映射。如何將任務映射到片上網絡的處理器核上是非常重要的問題，而這首先取決于如何對多任務集合進行劃分。傳統上以劃分任務圖的方式來進行，非常耗時，且由于是NP完全問題，只能以復雜的算法尋求最優解。

發明內容

本發明旨在克服現有技術缺陷，目的在于提供一種基于連接特征的多任務集合劃分方法，該方法能夠提高多任務集合的劃分效率。

為實現上述目的，本發明采用的技術方案的步驟是：

步驟1、建立多任務模型

對于多任務，建立多任務模型G(T,P,Q)，其中：

T為任務的集合，T={t₀,t₁,…,t_m}。

P為p_ij的集合，p_ij=1表示任務t_i與任務t_j之間存在著通信關系，p_ij=0表示任務t_i與任務t_j之間不存在通信關系。