[發明專利]多級共享高速緩沖存儲器架構下的任務分配方法和系統

有效

• 申請號: 201711298943.7
• 申請日: 2017-12-08
• 公開（公告）號: CN108132834B
• 公開（公告）日: 2020-08-18
• 發明（設計）人: 伍衛國;劉松;謝驍;崔元楨;鄒年俊
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06F15/78
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

本發明提供了一種多級共享高速緩沖存儲器架構下的任務分配方法和系統，屬于多核/眾核處理器任務分配領域。本發明引入footprint值與地址序列長度值的比值作為局部性參數，其并通過將程序局部性原理應用到程序分配中，有效的提高片上存儲器的利用率從而提高系統性能，且操作性良好。本發明通過枚舉務分配方式，并尋找局部性參數最小的任務分配方式，并據此進行任務分配；或者通過最小化擁有相同共享Cache的程序簇之間的局部性差異，使任務分配局部性盡可能均勻，在犧牲少量精度的情況下，減少了尋找最佳任務分配方式的時間，提高了任務分配效率。

技術領域

本發明屬于多核/眾核處理器任務分配領域，特別涉及一種多級共享高速緩沖存儲器架構下的任務分配方法和系統。

背景技術

隨著半導體技術的發展，同時為了追求更高的處理器性能，越來越多的計算機核心(core)被集成到一個模具上。這些核心通常共享著高級別的高速緩沖存儲器(cache)，以此減少片外存儲器訪問帶來的性能損耗。然而，隨著核心數量的增長，并行計算任務對片上共享資源，特別是高速緩沖存儲器的爭奪日益加劇，這可能導致頻繁的cache失效，降低并行處理的性能。由于不同的任務需要不同的共享資源，因此不同的并行任務組合將占用不同數量的共享高速緩存。所以，針對片上多處理器(CMP)的任務調度分配研究對提高片上存儲器的利用率從而提高系統性能具有重要意義。

對于多核/眾核任務調度分配算法(task scheduling on multi-coreprocessors)的研究已有多年歷史?，F在主流的研究是real-time scheduling，可以大體分為以下三個方面：

全局調度(global scheduling)：每個任務可以在任何可用的處理器上執行。全局調度中所有符合條件的任務都存儲在一個單優先級有序隊列中，全局調度程序選擇隊列中最高優先級任務分配處理器。全局調度相對于分區調度能很好地利用計算資源，并對定時誤差有好的容忍性。全局調度更適合于開放式系統，當任務集發生變化時，不需要運行任務分配算法。但同時使用這種方法和單處理器調度優化算法可能導致多處理器系統中處理器利用率降低。

分區調度(partitioned scheduling)。每個任務預先分配給處理器，并且在運行時只能在這個特定的處理器上執行。分區調度不允許動態負載平衡，但擁有實現容易的好處。一旦系統被劃分成子系統，單處理器實時調度和分析技術便可以應用到每個子系統。但分區調度的挑戰是如何將系統工作負載分配給單個處理器，從而使得利用率最大化。同時分區調度使用每個處理器單獨運行隊列，而不是單個全局隊列。對于大型系統，操作單一全局隊列的開銷可能變得過高。

基于緩存感知調度(cache-aware scheduling)。多核體系結構通過使用共享緩存來提高平均性能，但來自不同核的共享緩存訪問會互相干擾。要精確地預測每個任務的執行時間，需要考慮所有共同執行任務的相關信息，而這些任務組合又取決于任務調度。N.Guan提出了一種高速緩存分區任務分配方法，通過將緩存空間分區，使每個任務占有固定的緩存大小。但如果平均分配緩存空間，會對緩存需求大的任務不公平。本發明通過對任務進行局部性原理分析，能很好地解決這種不公平現象。

發明內容

本發明的目的在于提供一種多級共享高速緩沖存儲器架構下的任務分配方法和系統，其能夠有效的提高片上存儲器的利用率從而提高系統性能，同時具有好的可操作性。

本發明是通過以下技術方案來實現：

一種多級共享高速緩沖存儲器架構下的任務分配方法，其中，所述共享高速緩沖存儲器均在同一層級且數量大于2，每個共享高速緩沖存儲器均連接相同數量的核心，每個核心只能分配一個任務；該方法包括步驟：

1)提取任務數、與單個共享高速緩沖存儲器相連的核心的數量、共享高速緩沖存儲器的個數；每個任務對應一個程序，對于待分配的每一個程序通過離線分析計算對應的footprint值和地址序列長度值；