搜索空間計算方法和裝置及自適應線程調度方法和系統的製作方法

2023-05-28 05:38:46

專利名稱：搜索空間計算方法和裝置及自適應線程調度方法和系統的製作方法
技術領域：
本發明總體上涉及多核計算機領域，並且尤其涉及如何在多核硬體平 臺上進行多個軟體線程的調度的線程調度技術。
背景技術：
自多核技術提出後，多核處理器已經成為大家公認的處理器設計趨 勢。而且，隨著多核晶片市場的^，出現了越來越多的基於多核的系統 (例如，伺服器和個人計算機)。這些基於多核的系統提供了多線程應用 可以同時運行許多線程這樣的能力。多線程應用總4一創建多個線程，並且 由於存在多個線程和多個核，因此需要將多個線程調度到不同的核上以^更 執行。線程在不同核上的運行方式將會在很大程度上影響到系統的性能。
多線程應用和多核技術對於如何將軟體線程調度到多個硬體核上提 出了新的挑戰。從軟體的角度來說，多線程應用是更加高速緩存敏感的 (即，在多個線程當中共享總的高速緩存大小)。而且，多線程應用的存 儲模型/編程模型決定了在不同線程之間有大量的共享資源(例如，全局 變量、原子變量、鎖機制等)，其中所述線程通常是基於要共享的高速緩
存、前端總線(FSB)或者計算單元的。而從硬體核的角度來說，多核服 務器通常具有分級高速緩存結構，例如，Ll高速緩存是專用的，L2高速 緩存由同 一處理器中的多個核共享，而L3高速緩存可由不同插座(socket) 上的處理器共享，等等。而且，多核處理器技術還提出了許多新的硬體線 程模型，例如，同步多線程(SMT)/片上多線程(CMT)/超線程(HT) 模型，它們是邏輯硬體線程而不是物理核，並且共享FSB的硬體資源、 計算單元等。由此，導致存在許多線程調度問題。例如，線程到核的不好
的調度會由於存在快取置換(cache thrashing)、資源竟爭等問題而導致 系統性能降低。而且，由於可能存在M個不同的軟體線程和N個硬體線 程(其中N和M為自然數)，而且N個硬體線程與複雜的硬體結構有關， 因此編程人員或者系統性能分析人員難以確定最優的線程調度方法。此外，在某一多線程應用已經在某一特定硬體平臺上適應得4艮好了的情況 下，如果想要把這個應用移植到另 一個與該特定平臺具有不同的硬體線程 類型/核/高速緩存結構的硬體平臺上，那麼將會是非常困難的。
目前已經提出了很多應用在多核環境下的線程調度方法和/或系統，例
如，可以參見美國專利US6779182B1和US4910660A， C. Severance和 R. Enbody所著的、題為"Automatic Self-allocating Thread (ASAT) on an SGI Challenge"的文章(參見Proceedings of 1996 International Conference on Parallel Processing (ICPP' 96)， Vol. 3,第III-132 ~ III-139 頁，1996年8月)，以及Bodhisattwa Mukherjee和Karsten Schwan所著 的、題為"Implementation of Scalable Blocking Locks Using an Adaptive Thread Scheduler"(參見Proceedings of the 10th International Parallel Processing Symposium (IPPS' 96)，第339 ~ 343頁，1996年)的文章等。 然而，這些已有的線程調度方法和/或系統都沒有充分考慮到不同線程之 間的交互和/或資源共享問題，因此存在諸如費時、無法資源共享等問題。
將多個線程調度到多個核上的過程就像是數學上的球盒(ball-box) 問題，因此，可以根據排列組合的原理計算所有可能的、包含多個線程與 多個核之間的映射關係的線程調度選擇。例如，在多線程應用可以生成M 個軟體線程且多核系統具有N個硬體核的情況下，對於從M到N的映射 關係，如果假設一個線程只能被調度給一個核，則總計可能存在NM種線 程調度選擇(在下文中將其稱為綁定選擇)，其中包含M個線程與N個 硬體的所有可能的映射關係，這時可以認為，包含所有從線程到核的綁定 選擇的、總的搜索空間大小為NM。在此，搜索空間表示應用程式(單線 程應用或多線程應用)在多核硬體平臺上的線程調度選擇或方案(即，綁 定選擇或方案)的組合空間。在這種情況下，例如，如果在4個核上有6 個軟體線程，則總計可能存在46 = 4096種綁定選擇。例如，如果針對每 種綁定選擇的性能測量需要l分鐘，則總的測量時間要接近3天，即使使 用比較好的、例如僅需要該時間的10%來得到搜索結果的搜索算法，也 仍然需要大約7個小時。也就是說，即使採用目前已知的最佳搜索算法從 這個搜索空間中查找最優的綁定選擇，這個搜索空間也太大了，所需要的 搜索時間也太長了。
因此，如何減小包含多個線程到多個核的所有綁定選擇的巨大的搜索 空間，以便從中快速地找到令人滿意的綁定方案，是當前迫切要解決的一 個重要問題。
7此外，還迫切需要一種設計良好的、用於將多個線程調度到多個核上 的線程調度方法，以確保多線程應用在多核硬體平臺上具有令人滿意的運 行性能。

發明內容
在下文中給出了關於本發明的簡要概述，以便提供關於本發明的某些 方面的基本理解。應當理解，這個概述並不是關於本發明的窮舉性概述。 它並不是意圖確定本發明的關鍵或重要部分，也不是意圖限定本發明的範 圍。其目的僅僅是以簡化的形式給出某些概念，以此作為稍後論述的更詳 細描述的前序。
為了解決現有技術中的上述問題，本發明的一個目的是，提供一種用 於計算可供在多核系統上對多線程應用進行線程調度時使用的線程調度 搜索空間的方法和/或裝置，其能夠基於多核系統的硬體結構，從所有可 能的綁定選擇中找出所有彼此相同或等效的綁定選擇，並且在所有可能的 綁定選擇中僅保留所有彼此相同或等效的綁定選擇其中之一 ，而除去其餘 彼此相同或等效的綁定選擇，以得到減小了的線程調度搜索空間。
在此，兩個綁定選擇等效，意味著多線程應用依據這兩種綁定選擇進
行線程調度時"預期"會產生相同的效果，例如，程序運行的iUL相同， CPU的利用率相同，內存佔用空間相同等。
本發明的另一個目的是，提供一種利用上述計算線程調度搜索空間的 方法和/或裝置進行自適應線程調度的方法和/或系統，其能夠在減小了的 線程調度搜索空間中模擬運行多線程應用，並M於多核系統的性能監視 結果從所述線程調度搜索空間中搜索並確定優選綁定方案，據此產生調度 執行計劃，並在真實環境下實際應用該調度執行計劃。
為了實現上述目的，根據本發明的一個方面，提供了一種用於計算可 供在多核系統上對多線程應用進行線程調度時使用的線程調度搜索空間 的方法，包括以下步驟獲取有關多線程應用和多核系統的硬體結構的信 息；通過參考所述有關信息，計算所有可能的、包含多個線程與多個核之 間的映射關係的綁定選擇；基於多核系統的硬體結構，從所有可能的綁定 選擇中找出所有彼此相同或等效的綁定選擇；以及在所有可能的綁定選擇 中，對於所有彼此相同或等效的綁定選擇，保留其中之一，而除去其餘彼 此相同或等效的綁定選擇，以得到可供線程調度時使用的搜索空間。根據本發明的另一個方面，還提供了一種用於計算可供在多核系統上
對多線程應用進行線程調度時使用的線程調度搜索空間的裝置，包括信 息獲取器，被配置用於獲取有關多線程應用以及多核系統的硬體結構的信 息；綁定選擇計算器，被配置用於通過參考所述有關信息，計算所有可能 的、包含多個線程與多個核之間的映射關係的綁定選擇;綁定選"^檢測器， 被配置用於基於多核系統的硬體結構，從所有可能的綁定選擇中找出所有 彼此相同或等效的綁定選擇，並保留所有彼此相同或等效的綁定選擇其中 之一，而除去其餘彼此相同或等效的綁定選擇；以及綁定選擇存儲器，用 於存儲可供線程調度時使用的線程調度搜索空間，該線程調度搜索空間是 在所有可能的綁定選擇中保留所有彼此相同或等效的綁定選擇其中之一 而除去其餘彼此相同或等效的綁定選擇而得到的。
根據本發明的另一個方面，還提供了一種使用上述計算線程調度搜索 空間的方法進行自適應線程調度的方法，包括以下步驟才艮據作為線程調 度優化目標的多線程應用和多核硬體平臺的有關信息，利用上述方法計算 可用的線程調度搜索空間；在所述多核硬體平臺上在所述線程調度搜索空 間中模擬運行所述多線程應用，並且基於模擬運行所述多線程應用時所述 多核硬體平臺的性能監視結果，從所述線程調度搜索空間中搜索並確定優 選的綁定選擇，作為優選綁定方案；以;SJL據所確定的優選綁定方案產生 調度執行計劃，並實際應用該調度執行計劃。
根據本發明還有的另一個方面，還提供了一種自適應線程調度系統， 包括作為優化目標對象的多線程應用和多核硬體平臺；上述計算線程調 度搜索空間的裝置，被配置用於根據多線程應用和多核硬體平臺的有關信 息計算可用的線程調度搜索空間；模擬運行控制器，被配置用於在所述多 核硬體平臺上在所述線程調度搜索空間中模擬運行所述多線程應用；以及 性能監視器，被配置用於記錄模擬運行所述多線程應用時所述多核硬體平 臺的性能監視結果，其中，所^擬運行控制器基於來自所述性能監視器 的性能監視結果，從所述線程調度搜索空間中搜索並確定優選的綁定選 擇，作為優選綁定方案，並根據所確定的優選綁定方案產生調度執行計劃， 並實際應用該調度執行計劃。
依據本發明的其它方面，還提供了相應的計算機可讀存儲介質和計算
秘序產 品。
本發明的一個優點在於，通過利用根據本發明實施例的計算搜索空間 的方法和/或裝置，可以較大程度地減小可供在多核系統上對多線程應用進行線程調度時使用的線程調度搜索空間。
本發明的另一個優點在於，通過利用本發明實施例的自適應線程調度 方法和/或系統，不管有多少不同的工作負荷或者多麼複雜的硬體平臺， 都可以自動地確定優選的綁定方案。
本發明的又一個優點在於，在根據本發明實施例的自適應線程調度方 法和/或系統中，由於利用了根據本發明實施例的計算搜索空間的方法和/ 或裝置而使得線程調度搜索空間被大大地減小了 ，而且該搜索空間是通過 保留所有彼此相同或等效的綁定選擇其中之一而除去其餘彼此相同或等 效的綁定選擇而得到的，因此不會與現有的任何優化的搜索方法相衝突， 使得可以使用任何已有的優選搜索方法，所以，可以使用自適應技術，並 且可以更快地找到優選的綁定方案。
本發明還有一個優點在於，在根據本發明實施例的自適應線程調度方 法和/或系統中，可以屏蔽不同硬體平臺間的差異，從而應用自動適應平 臺特徵。
通過以下結合附圖對本發明的最佳實施例的詳細說明，本發明的這些 以及其他優點將更加明顯。


本發明可以通過參考下文中結合附圖所給出的描述而得到更好的理
的部件。所述附圖連同下面的詳細說明一起包含在本說明書中並且形成本 說明書的一部分，而且用來進一步舉例說明本發明的優選實施例和解釋本
發明的原理和優點。在附圖中
圖l示出了現有Intel四核處理器的結構示意圖2示出了根據本發明的一個實施例的計算可用線程得到搜索空間的 方法的流程圖，其中該方法可以基於多核系統的體系拓樸結構，在所有可 能的綁定選擇中僅保留所有彼此相同或等效的綁定選擇其中之一，而除去 其餘彼此相同或等效的綁定選擇，使得搜索空間得以大幅度減小；
圖3示出了才艮據本發明的一個實施例的搜索空間計算裝置的結構示意 圖，其中該裝置可以基於多核系統的體系拓樸結構，通過在所有可能的綁 定選擇中僅保留所有彼此相同或等效的綁定選擇其中之一，而除去其餘彼此相同或等效的綁定選擇，來得到減小了的綁定選擇搜索空間；
圖4示出了根據本發明一個實施例的利用圖2所示的方法進行自適應線程調度的方法的流程圖5示出了根據本發明另一個實施例的自適應線程調度系統的方框圖，其中在該自適應線程調度系統中包括如圖3所示的搜索空間計算裝置，並且可以執行以上結合圖4所描述的自適應線程調度方法；以及
圖6示出了對根據本發明實施例的自適應線程調度方法和/或系統進
行測試的M發起協議(SIP)應用伺服器測試場景。
本領域技術人員應當理解，附圖中的元件僅僅是為了簡單和清ft^見而示出的，而且不一定是按比例繪製的。例如，附圖中某些元件的尺寸可能相對於其他元件放大了 ，以便有助於提高對本發明實施例的理解。
具體實施例方式
在下文中將結合附圖對本發明的示範性實施例進行描述。為了清楚和簡明起見，在說明書中並未描述實際實施方式的所有特徵。然而，應該了解，在開發任何這種實際實施例的過程中必須做出很多特定於實施方式的決定，以便實現開發人員的具體目標，例如，符合與系統及業務相關的那些限制條件，並且這些限制條件可能會隨著實施方式的不同而有所改變。此外，還應該了解，雖然開發工作有可能是非常複雜和費時的，但對得益於4^^開內容的本領域技術人員來說，這種開發工作僅僅是例行的任務。
在此，還需要說明的一點是，為了避免因不必要的細節而模糊了本發明，在附圖中僅僅示出了與根據本發明的方案密切相關的裝置結構和/或處理步驟，而省略了與本發明關係不大的其他細節。
為了更好地描述多核系統的體系拓樸結構，在此提出了一種公式化的描述方法，該>^式化的描述方法不僅可以包含處理器的體系結構信息，而且還可以用來在線程調度過程中減小搜索空間。該公式化的描述方法具有
如下所述的描述框架
(1)用於表示各個核之間的關係的符號集，其中包括如下符號S:自身；
Ll:共享L1高速緩存；
iiL2:共享L2高速緩存但不共享Ll高速緩存；D:在同一小片(die)內，但是排除L2和L1;C:在同一晶片/插座內，但是排除D;
顯然，可能還存在其他以上並未列出的符號定義或約束條件(例如，可能由於新的架構設計而帶來的新的共享或獨享約束等)。在此，需要注意的是，該符號集的定義必須是具有完備性的(MECE， MutuallyExclusive Collectively Exhaustive )，即，該符號集中各個符號代表的約A條件所表示的可能情況的總和包括了所有可能出現的情況，也就是說，各個符號的定義彼此相互之間是無交集的，而且所有符號合起來構成全集(即，包括所有可能出現的核與核之間的可能性的集合)。
(2)用於表明每一核對之間的關係的關聯矩陣IM (IncidenceMatrix):
假設在此用Xy表示關聯矩陣IM中第i行第j列上的元素，它的含義表示多核系統中第i個核和第j個核之間的關係，並且它的值來自於以上所定義的符號集。
例如，根據上述符號集定義和關聯矩陣定義，對於具有兩個Intel四核處理器(該Intel四核處理器的結構示意圖見圖1)的HS21刀片月艮務器而言，可以得出如下的關聯矩陣formula see original document page 12
而對於SunFire T1000伺服器(其中包含4個硬體核，但是每個硬體核上可並行運行4個線程，即，包含16個硬體線程Niagara),可以得出如下的關聯矩陣sLILIUL2L2L2L2L2L2L2L2L2
LISLIUL2L2L2L2L212L2L2
LILISLIL2L2L2L2L2L2L2L2L2L2
LILILISL2L2L2L2L2L212L2L2L2
L2L212SLIULIL2L212L2L2L2L2
L2L2IJSLILIL2L2L2L2
L2L2L2LIuSL2L2L2U
L2L2LILIUSL2L2L2L2L2L2L2
L2L2L2L2L212L2SLILIUL2L2L2
L2L2L2L2L2L2L2LISLILIL2UL2
L2L2L2L2L2L2LILISLIL2L2L2L2
L2L2L2L2L2LILISIL2
12L2L2L212L2L2L2L2L2SLIULI
L2L2L2L2L2L2L2L2L2L2LISLILI
L2L2L2L2L2L2L2L2LILISLI
L2L2L2L2L212L2L2LILIUS
需要說明的一點是，以上所給出的HS21刀片伺服器和SunFire T1000伺服器的關聯矩陣中所使用的符號集就目前現有的架構設計而言是具有完備性的.
由此，根據以上給出的包含上述符號集和關聯矩陣的描述框架，不管是同構的多核系統還是異構的多核系統(例如，IBM CELL),對於,多核系統的體系拓樸結構，都可以給出公式化的描述，即定義如上所述的關聯矩陣。
顯然也可以根據需要給出其他不同的符號集定義，只要所定義的符號集具有完備性這一特點即可，並且因此可以得到形式上有所不同的關聯矩陣來表示多核系統的體系拓樸結構。
下面將結合圖2所示的流程圖來具體描述根據本發明的實施例如何基於多核系統的體系拓樸結構來減小搜索空間的過程。
圖2示出了根據本發明的一個實施例的用於計算可用線程調度搜索空間的處理過程200的流程圖，其中該處理過程200能夠基於多核系統的體系拓樸結構，在所有可能的綁定選擇中僅保留所有彼i^目同或等效的綁定選捧其中之一，而除去其餘彼此相同或等效的可能綁定選擇，從而得到減小了的線程調度搜索空間。
如圖2所示，在步驟S210，獲取有關多核系統的體系拓樸結構以及多線程應用的信息，例如，核的數目，各個核之間的關係，線程的數目，各線程間的通信方式等。其中，有關多核系統的體系拓樸結構的信息可以從多核系統的硬體平臺手冊或使用規範中獲得，而有關多線程應用的信息
13可以從多線程應用獲得(其中該多線程應用是由用戶輸入的)。
然後，在步驟S220，參考步驟S210中所得到的信息，才艮據多個線程與多個核之間的可能的映射關係，計算線程調度過程中所有可能的綁定方案(即綁定選擇)。
在此，正如前面所提到的那樣，可以根據排列組合的原理計算所有可能的綁定選擇。以將6個線程(分別用Tl、 T2、 T3、 T4、 T5和T6表示)調度到4個核(分別用Cl、 C2、 C3和C4表示)上為例，如果假設在每種綁定方案中一個線程都只能被調度給一個核，那麼這樣可以得出共計有
46 = 4096種可能的綁定選擇(分別用Choice 1、 Choice 2........ Choice
4096表示)，其分別為
Choice 1: T1C1， T2C1， T3C1， T4C1， T5C1， T6C1;
Choice 2: T1C2， T2C1， T3C1， T4C1， T5C1， T6C1;
Choice 4096: T1C4， T2C4, T3C4， T4C4， T5C4, T6C4。
然而，實際上，在線程調度過程中一個線程往往可以被調度到一個以上的核，例如，線程Tl可以被調度到核C0和Cl (假設用T1(C0C1)來表示)，這樣可能的綁定選擇應當更多。例如，在將6個線程調度到4個核上的情況下，可能的綁定選擇的總數如下所示
接下來，在步猓S230,基於多核系統的體系拓樸結構，從所有可能
在>(^設每種綁定方案中 一個線程都只能被調度給一個核的情況下，判斷任何兩種綁定選擇是否相同的過程比較簡單。例如，對於以上給出的Choice l和Choice 2，不管採用何種方法，都可以4艮容易地確定出除第一項有所不同(它們的第一項分別為T1C1和T1C2)夕卜，其餘各項分別相同，因此，可以確定Choice 1和Choice 2不同。
但是，實際上一個線程往往不只是可以被^調度到一個核而是可以被調度到若干個核，在這種情況下，由於綁定方案中存在一個線程與若千個核的組合(即核子集)的較為複雜的映射關係，如何判斷任何兩種其中包含這種複雜映射關係的綁定選擇是否相同或等效，就變得複雜多了。例如，
C: + C42 + C43 + C44 = 156 = 11,390,625選擇。假設線程Tl可以被調度到核CO、 Cl和C2中的任意兩個核，這樣就可能存在如下三種可能的複雜映射關係T1(C0C1)， T1(C0C2)和T1(C1C2)。在下文中，為了簡單起見，將綁定選擇中的這種包含複雜映射關係的項稱為組合項。如何更加簡單和快捷地判斷這三種可能的複雜映射關係是否等效，也是本發明較為關注的問題之一。
在此，為了更好地比較任意兩種包含上述這種複雜映射關係的綁定選擇是否相同或等效，引入了如下幾個概念組合矢量CV (CombinationVector )，組合矩陣CM ( Combination Matrix),和標識因子IF (IdentityFactor )0
其中，組合矢量CV是表示在某一綁定方案中各個核是否被選中運行(即是否被分配有軟體線程)的布爾矢量，而組合矩陣CM是按照下述等式從組合矢量CV得到的矩陣
cm = Cxct (等式l)
例如，對於具有2個Intel四核處理器的HS21刀片伺服器(其中包含8個核)而言，假設核C2、 C4和C5在線程調度過程中被選中(即，
被分配有線程),則對於該伺服器的組合矢量cv可以a示為(0， 1， 0,1， 1,
O，O,O),並且因此可以得到如下所示的組合矩陣CM:
formula see original document page 15基於以上定義的組合矢量CV和組合矩陣CM，按照如下方式計算類似T(C2C4C5)這樣的組合項的標識周子IF:
/F二Ex[CM-iM]x57 -ExfCrrxCr-ZAnx^r (等式2 )
其中，5 = (1，1，...，1)，符號" "表示點積.
在此，按以上方式計算的標識因子IF表示了和多線程應用的線程相關的那些核之間的拓樸關係。
假設某一線程T可以被調度(或分配)給核子集Sl和核子集S2,而且多核系統的關聯矩陣為IM，核子集S1的組合矢量為CV1，核子集S2的組合矢量為CV2，那麼，只有當分別針對核子集Sl和核子集S2計算得到的組合項TS1和TS2的標識因子IF1和IF2相等、即滿足以下的等式3時，才認為線程T到核子集Sl的線程調度和線程T到核子集S2的線程調JLA等效的，即，所述線程T到核子集Sl和核子集S2的映射關係(即組合項TS1和TS2 )是等效的
五x[CF/ xCFj ，/M]x五r三五x[C「/ x CF2 /M]x ￡r (等式3 )
例如，以下述兩種綁定選擇為例來進行i兌明
Choice x: T1(C1C2C3)， T2C1, T3C1， T4C1， T5C1， T6C1;
Choice y: T1(C2C3C4)， T2C1， T3C1， T4C1， T5C1, T6C1。
通過對上述兩種綁定選擇進行比較不難看出，它們的第一項中都包含線程到核子集的複雜映射關係，而其餘各項均表示一個線程到一個核的映射，而且第2至6項分別相等，這時只需要判斷它們的第1項是否等效，即可以確定這兩種綁定選擇是否等效。
也就是說，當兩個綁定選擇中包含的非組合項彼此相同且組合項彼此等效時，兩個綁定選"^是等效的。而且，正如上文中所說明的那樣，兩個綁定選擇等效，意味著多線程應用依據這兩種綁定選擇進行線程調度時"預期"會產生相同的效果，例如，程序運行的速度相同，CPU的利用率相同，內存佔用空間相同等。
仍以HS21刀片伺服器為例，對於上述的Choice x和Choice y的第1項，它們的核子集分別是(C1， C2， C3)以及(C2， C3， C4}，即，CVx =(1,1,1， 0， 0,0， 0， 0)， CVy = (0,1,1,1， 0, 0, 0， 0)，
那麼，才艮據上述等式2可以得出
:(1，1，…，1)X[(l,l，l,O,O,O，O,Cx(l,l,l,0,0,0，0,0)"M]x(l,l，...(U，…,l)x[-1，1，1，0,0,0,0,0-l，l，l，O，O，O，O，O l,l，lO，O，O，O,O o，o,o，o，o,o，o —S,丄2,Z),D,C，C，C，C— 丄2，S,Z)，D,C，C,C,C D，化S，丄2，C,C,C，C Z)，化Z2，S，C,C,C,C]x—1 _ 1 1 1
16formula see original document page 17
由此，可以確定T1(C1C2C3)與T1(C2C3C4)是等效的，繼而可以確 定Choice x和Choice y是等效的。這一點從圖1中所示的Intel四核處理 器的結構中也可以得到證實。
對於任何一種其中至少有一項包含線程到核子集的複雜映射關係(即 組合項)的綁定選擇，都可以如上所述計算出該綁定選擇中的組合項的標 識因子IF，然後再比較該種綁定選擇與其他也包含組合項的綁定選擇是 否等效.
這樣，在圖2所示的步驟230中，從所有可能的綁定選擇中找出所有 彼此相同或等效的綁定選擇。
隨後，在步驟S240，在所有可能的綁定選擇中，對於所有彼此相同 或等效的綁定選擇，僅保留其中之一，而除去其餘彼此相同或等效的綁定 選擇(在下文中，為了簡明起見，將這些要除去的其餘彼此相同或等效的 綁定選擇稱為"多餘的綁定選擇")。
在找出了彼此相同或等效的綁定選擇之後，從所有可能的綁定選擇中 除去多餘的綁定選擇是非常方便的。也就是說，可以使用任何已有的方法 來遍歷整個線程調度搜索空間，保留所有彼此相同或等效的綁定選擇其中 之一而除去多餘的綁定選擇，從而可以大大地減小搜索空間。
以上結合圖2描述根據本發明實施例的方法時，基於多個線程彼此不 同這個假設，對如何判斷任意兩種綁定選擇是否相同或等效進行了說明， 但是，實際上，多線程應用創建的多個線程往往是相同的。針對其中所述 多個線程相同這樣一種特例，完全可以如上所述那樣來處理，因此，為了 簡明起見，在此就不再詳述了。在多個線程相同的這種情況下，例如對於
上面所提到的6線程應用，可以通過將Tl、 T2........ T6統一用T表
示，然後比較綁定選擇的各項的併集是否相同或等效，來判斷任意兩個綁 定選擇是否相同或等效，因此，可以對以上所描述的方法200進行筒化。圖3示出了根據本發明的一個實施例的搜索空間計算裝置300的結構 示意圖，其中該搜索空間計算裝置300可以基於多核系統的體系拓樸結 構，通過在所有可能的綁定選擇中保留所有彼此相同或等效的綁定選擇其 中之一，而除去其餘彼此相同或等效的綁定選擇(即，多餘的綁定選擇), 來得到減小了的線程調度搜索空間。
該搜索空間計算裝置300中可以執行如圖2所示的方法200，並且如 圖3所示，搜索空間計算裝置300包括信息獲取器310，綁定選擇計算 器320，綁定選擇檢測器330和綁定選擇存儲器340。
其中，信息獲取器310被配置用於獲取有關多核系統的體系拓樸結構 以及多線程應用的信息，例如，線程和核的數目，各線程間的通信方式， 各個核之間的關係等。
綁定選擇計算器320被配置用於通過參考信息獲取器310所獲取的信 息，根據線程與核之間的可能的映射關係，計算線程調度過程中所有可能 的綁定選擇，並將其存儲在綁定選擇存儲器340。
綁定選#^檢測器330被配置用於從所有可能的綁定選擇中檢測出所有 彼此具有相同或等效映射關係的相同或等效綁定選擇，並M儲在綁定選 擇存儲器340中的所有可能的綁定選擇中除去多餘的綁定選擇，即，在所 有可能的綁定選擇中保留所有彼此相同或等效的綁定選擇其中之一，而除 去其餘彼此相同或等效的綁定選擇。在此，綁定選^^檢測器330可以如以 上結合圖2所示的流程圖所描述的那樣，對於包含至少一個組合項的綁定 選擇計算組合項的標識因子，然後通過對所有可能的綁定選擇進行兩兩比 較，找出所有彼此相同或等效的綁定選擇。
綁定選擇存儲器340 ，被配置用於存儲可供線程調度過程中選用的綁 定選擇，其中所述可供選用的綁定選擇是從所有可能的綁定選擇中除去多 餘的綁定選擇後得到的。
通過閱讀以上結合圖2給出的、關於如何基於多核系統的體系拓樸結 構來計算線程調度搜索空間的處理過程的描述，搜索空間計算裝置300 的各個組成部件的功能如何實現就變得很清楚了 ，所以在此就不再贅述 了。
對於將6個相同的軟體線程調度到4個核上並且每個線程只能被調度 到一個核上的情況，通過利用以上結合圖2和/或3所描述的方法和/或裝 置，從所有可能的46=4096種綁定選擇中去除了多餘的綁定選擇後得到的
18搜索空間的大小為
formula see original document page 19
由此可以看出，通過利用以上所描述的根據本發明實施例的計算搜索 空間的方法和/或裝置，與已有技術相比，在很大程度上減小了線程調度 搜索空間。
在傳統的線程調度方法中，由於運行自適應技術需要花費大量的時 間，所以使得自適應技術不太適合於用在線程調度領域中。然而，由於根 據本發明線程調度搜索空間得到了大幅度的減小，所以在此可以將自適應 線程調度技術用來查找線程和核之間的優化的綁定方案。
為此，為了能夠更好地應用以上結合圖2和3所描述的方法和裝置， 以便在多核系統上更好地進行線程調度，##本發明的其他實施例，還提 供了一種自適應線程調度方法及系統，它們能夠利用圖2所述的方法和/ 或圖3所示的裝置，才艮據多線程應用和多核系統的硬體體系結構，自動地 確定優選的綁定方案。
下面首先結合圖4來描述根據本發明其他實施例的自適應線程調度方 法的處理過程。圖4示出了根據本發明一個實施例的、利用圖2所示的方 法200進行自適應線程調度的處理過程400的流程圖。
如圖4所示，為了有針對性地解決多線程應用在不同的多核硬體平臺 上的性能問題，在步驟S410，獲得J^行的多線程應用和要在其上進行
件平臺稱為線程調度優化目標)的有關信息，例如，有多少個軟體線程， 以及有多少個核和硬體平臺的存儲模型等體系拓樸結構信息等。
然後，在步驟S420，獲得測量條件和性能標準，以便明確什麼樣的 綁定選##^人為是優選的綁定方案。所述測量條件和性能標準可以是用戶 預先設置的並存儲在一個測量條件和性能標準儲存庫中.
例如，伺服器總是在每秒處理500條消息的工作負荷下運行，因此可 以將測量條件定義為這個工作負荷；或者，對於數學庫而言，可以將輸入 數據大小定義為測量M。而對於性能標準來說，例如，可以定義在一 定的工作負荷下，CPU利用率越低，伺服器的性能越好；而對於數學庫 來說，使用的時間越少，性能越好。接下來，在步驟S430,根據多線程應用和硬體平臺的體系拓樸結構， 計算可用的線程調度搜索空間。
正如前面所提及的那樣，在傳統的方法中，在有M個軟體線程和N 個核的情況下，總的線程調度搜索空間大小為NM (假設一個線程只能被 調度到一個核上)，但是這個搜索空間太大了。為此，在這一步驟中，執 行如圖2所示的處理過程，以便基於硬體體系結構從所有可能的綁定選擇 中除去多餘的那些綁定選擇，從而得到減小了的可用搜索空間.
然後，如圖4所示，在步驟S440，在步驟S430中所得到的可用搜索 空間中模擬運行所述多線程應用，並查找優選的綁定方案。
具體來說，在如上所述減小了搜索空間之後，將其中的每種綁定選擇 作為輸入，在多核硬體平臺上模擬運行多線程應用，並根據步驟S420中 所獲得的測量條件和性能標準，記錄性能監視輸出結果，然後從所有可用 綁定選擇中搜索並選擇出優選的那個綁定選擇，作為優選綁定方案。
在這個步驟中，可以使用任何已有的搜索算法，例如，模擬退火 (Simulated Annealing)、神經網絡(Neuron Network),最速下降方法 (Steepest Decent Method)、動態編程(Dynamic Programming)、遺傳 算法(GeneticAlgorithm)等，來加速搜索過程。
在找到了優選的綁定方案後，在步驟S450,根據所述優選的綁定方 案產生調度執行計劃，並在真實環境下實際應用該調度執行計劃，這個步 驟的處理也是相對簡單的，把所述優選綁定方案作為輸入，並按照該綁定 方案中定義的那樣將線程調度到相應的那些核即可。在實際的實現過程 中，這可以通過下述措施來實現修改多線程應用的原始碼，由多線程應 用的運行時環境進行調度，或者修改作業系統的調度程序。
在根據本發明實施例的這種自適應線程調度方法中，由於基於多核硬 件平臺的嚴格的體系拓樸結構定義，在所有可能的綁定選擇中僅僅保留所 有彼此相同或等效的綁定選擇其中之一，而除去其餘彼此相同或等效的綁 定選擇(即，多餘的那些綁定選擇)，以大大減小搜索空間，因此，可以 確保減小後的搜索空間仍然包含軟體線程到硬體核的映射關係的所有可 變性，也就是說，減小後的搜索空間並不會影響到自適應線程調度技術的 輸出。
而且，在根據本發明實施例的這種自適應線程調度方法中，先前所描 述的根據本發明實施例的減小搜索空間的方法可以在已有的優化的搜索
20方法之前使用，因此並不會與優化的搜索方法相衝突，而且可以使用優化
的搜索方法來加速搜索n從而減少自適應處理的時間，
以上結合圖4所描述的自適應線程調度方法可以以離線的方式或者以 在線的方式執行。例如，在離線的方式下，通過在圖4所示的步驟S410 中選擇作為線程調度優化目標的多線程應用和多核系統硬體平臺，可以自 動地獲知軟體線程和硬體平臺的有關信息，離線地在減小了的可用搜索空 間中進行搜索，選#^優選綁定方案，然後將其實際應用到真實的環境中； 而在在線的方式下，對於實際的多線程應用和多核系統硬體平臺，在線地 在所計算的可用搜索空間中執行搜索，同時在硬體平臺上執行性能採樣 (profile),並選擇當前優選的綁定方案予以應用。
顯然，可以根據實際需要對圖4所示的自適應線程調度方法的處理流 程進行適當的更改。例如，用戶可以在圖4所示的步驟S420中定義測量 條件和性能標準，或者也可以根據需要對預先定義的測量條件和性能標準 進行修改。而且，也可以對圖4所示的處理流程的執行順序進行調整，例 如，步驟S420的處理在採用系統默認的測量條件和性能標準的情況下不 是必需的，而且也可以根據情況在步驟S430的處理W執行。當然，可 能還存在其他的更改方式，在此就不——列舉了。
圖5示出了根據本發明另 一個實施例的自適應線程調度系統500的方 框圖，其中在該自適應線程調度系統500中可以執行以上結合圖4所描述 的自適應線程調度方法，並且包括如圖3所示的搜索空間計算裝置300.
如圖5所示，自適應線程調度系統500包括作為優化目標對象的多 線程應用510和多核硬體平臺520，如圖3所示的用於減小線程調度搜索 空間的搜索空間計算裝置300，模擬運行控制器530,性能監視器540和 測量M&性能標準儲存庫550。
其中，搜索空間計算裝置300根據多線程應用510和多核硬體平臺520 的有關信息，計算出可用的線程調度搜索空間，由模擬運行控制器530 控制在硬體平臺520上模擬運行所述多線程應用510，同時由性能監視器 540根據測量條件&性能標準儲存庫550中存儲的測量條件和性能標準， 對硬體平臺520的性能進行監視，並將性能監視結果傳送給模擬運行控制 器530，由模擬運行控制器530基於性能監視結果，從所述可用搜索空間 中查找優選的綁定方案，據此產生調度執行計劃並實際應用該調度執行計 劃。通過閱讀以上結合圖4所描述的處理過程400，自適應線程調度系統 500中的各個裝置如何實現其各自的功能就是很顯然的，因此，為了簡明 起見就不在此贅述了。
為了更好地說明根據本發明實施例的自適應線程調度方法和/或系統 在實際應用中帶來的優點，發明人對該自適應線程調度方法和/或系統進 行了如下測試。
測試實例l:科學計算
以執行矩陣加矩陣C=矩陣A+矩陣B為例，^Ri殳測試矩陣大 小為8192*16，有四個線程，而且測試用的硬體平臺為四核系統(其中具 有兩個處理器，且每個處理器有兩個核)。
以實際計算完成的時間為性能評價標準，在利用傳統的作業系統
(OS)調度方法時，耗時396749.9 us，而在利用根據本發明實施例的自 適應線程調度方法對線程調度進行優化後，耗時為326207.3 us，由此可 以看出，在利用本發明進行優化後性能提高了 21.6%。
測試實例2: ^^L^協議(SIP)應用伺服器測試
圖6示出了這種測試的場景，其中在SIP客戶端610發出請求後，等 待SIP伺服器620的響應。在SIP伺服器620端設有偵聽線程，它在收到 請求後將請求i^請求隊列，等待SIP堆棧派發，ii^派發隊列後， 線程池派發器，通過UDP發送器請求對應的響應。
為了便於測試，選擇簡單Invite作為測試場景，假設固定呑吐率為 1000，啟動4個主要的軟體線程(包括偵聽線程、SIP堆棧派發、線程池 派發器和UDP發送器)，測試平臺為四核系統(其中有兩個處理器，且每 個處理器有兩個核)。將性能評判標準設定為較少的CPU佔用率和上下文 切換次數，經試驗後得到的實驗數據如下
調度方法平均的CPU負載平均的上下文切換次lt/秒
OS調度方法14.7%23538
一一映射16.0%27719
自適應線程調度12.3%21456
從以上的測試數據中不難看出，根據本發明實施例的自適應線程調度
方法在CPU佔用率和上下文切換率上都要優於傳統的作業系統(OS )調
度方法和—映射的調度方法。
22通過利用根據本發明實施例的上述自適應線程調度方法和/或系統，可 以自動地確定優選的綁定方案(即，軟體線程與硬體核的優選的映射方 案)，而這在傳統的線程調度方法中是很難實現的。而且，不管有多少不 同的工作負荷或者多麼複雜的硬體平臺，都可以找到或確定優選的綁定方 案，而在傳統的線程調度方法中在不同的平臺中往往需要設置不同的算法 和/或參數。此外，由於其中利用了根據本發明的計算可用搜索空間的方 法和/或裝置，使得線程調度搜索空間被大大地減小了，而且可以使用現 有的任何優選的搜索方法，所以可以更快地找到優選的綁定方案。
此外，顯然，根據本發明的上述方法的各個操作過程也可以以存儲在 各種機器可讀的存儲介質中的計算機可執行程序的方式實現。
而且，本發明的目的也可以通過下述方式實現將存儲有上述可執行 程序代碼的存儲介質直接或者間接地提供給系統或設備，並且該系統或設 備中的計算機或者中央處理單元(CPU)讀出並執行上述程序代碼。
此時，只要該系統或者設備具有執#^序的功能，則本發明的實施方 式不局限於程序，並且該程序也可以;1任意的形式，例如，目標程序、解 釋器執行的程序或者提供給作業系統的腳4^序等。
上述這些機器可讀存儲介質包括但不限於各種存儲器和存儲單元， 半導體設備，磁碟單元例如光、磁和磁光碟，以及其它適於存儲信息的介 質等。
另夕卜通過連接到網際網路上的相應網站，並且將依據本發明的計算機 程序代碼下載和安裝到計算機中然後執行該程序，也可以實現本發明。
最後，還需要說明的是，術語"包括"、"包含"或者其任何其他變體 意在涵蓋非排他性的包含，從而使得包括一系列要素的過程、方法、物品 或者設備不僅包括那些要素，而且還包括沒有明確列出的其他要素，或者 是還包括為這種過程、方法、物品或者設備所固有的要素。此外，在沒有 更多限制的情況下，由語句"包括一個……"限定的要素，並不排除在包 括所述要素的過程、方法、物品或者設備中還存在另外的相同要素。
以上雖然結合附圖詳細描述了本發明的實施例，但是應當明白，上面所 描述的實施方式只是用於說明本發明，而並不構成對本發明的限制。對於本 領域的技術人員來說，可以對上述實施方式作出各種修改和變更而沒有背離 本發明的實質和範圍。因此，本發明的範圍僅由所附的權利要求及其等效含 義來限定。
權利要求
1.一種用於計算可供在多核系統上對多線程應用進行線程調度時使用的線程調度搜索空間的方法，包括以下步驟獲取有關多線程應用和多核系統的硬體結構的信息；通過參考所述有關多線程應用和多核系統的硬體結構的信息，計算所有可能的、包含多個線程與多個核之間的映射關係的綁定選擇；基於多核系統的硬體結構，從所有可能的綁定選擇中找出所有彼此相同或等效的綁定選擇；以及在所有可能的綁定選擇中，對於所有彼此相同或等效的綁定選擇，保留其中之一，而除去其餘彼此相同或等效的綁定選擇，以得到可供線程調度時使用的搜索空間。
2. 根據權利要求1所述的方法，其中，所述有關信息包括線程的 數目，各線程間的通信方式，以及有關多核系統的體系拓樸結構的、包括 核的數目和各個核之間的關係在內的信息。
3. 根據權利要求2所述的方法，其中，通il&於多核系統的體系拓 樸結構，比較兩個綁定選擇中包含的每個線程的線程與核之間的映射關 系，來判定所述兩個綁定選擇是否相同或等效。
4. 根據權利要求3所述的方法，其中，在綁定選擇中包含由一個線 程與若干個核的組合、即核子集的複雜映射關係構成的組合項的情況下，通過確定兩個組合項的標識因子IF是否相同，來判定兩個組合項是否等 效，其中標識因子IF利用下述等式計算得到=五x [crr x cr /M] x五7其中，CV是綁定選擇的組合矢量，其為表示在該綁定選擇中各個核 是否被分配有線程的布爾矢量，￡ = (1,1,...,1), " "表示點積，而IM為多核系統的關聯矩陣，所述關聯矩陣IM中的第i行第j列的元素Xy表示所述多核系統中第i個核和第j個核之間的關係，當兩個綁定選擇中包含的非組合項彼此相同且組合項彼此等效時，兩 個綁定選擇是等效的。
5. 根據權利要求4所述的方法，其中，對所述多個核中各個核之間 的關係的定義是具有完備性的。
6. 根據權利要求1至5中任何一項所述的方法，其中，所述多個線 程是彼此相同的線程。
7. —種用於計算可供在多核系統上對多線程應用進行線程調度時使 用的線程調度搜索空間的裝置，包括信息獲取器，被配置用於獲取有關多線程應用以及多核系統的硬體結 構的信息；綁定選擇計算器，被配置用於通過參考所述有關多線程應用以及多核 系統的硬體結構的信息，計算所有可能的、包含多個線程與多個核之間的 映射關係的綁定選擇；綁定選擇檢測器，被配置用於基於多核系統的硬體結構，從所有可能 的綁定選擇中找出所有彼此相同或等效的綁定選擇，並保留所有彼此相同 或等效的綁定選擇其中之一，而除去其餘彼此相同或等效的綁定選擇；以 及綁定選擇存儲器，用於存儲可供線程調度時使用的線程調度搜索空等效的綁定選擇其中之一而除去其餘彼此相同或等效的綁定選擇而得到 的。
8. 根據權利要求7所述的裝置，其中，所述信息獲取器獲取的所述 有關多線程應用以及多核系統的硬體結構的信息包括線程的數目，各線 程間的通信方式，以及有關多核系統的體系拓樸結構的、包括核數目和各 個核之間的關係在內的信息。
9. 根據權利要求8所述的裝置，其中，所述綁定選擇檢測器通it^ 於多核系統的體系拓樸結構，比較兩個綁定選擇中包含的每個線程的線程 與核之間的映射關係，來判定所述兩個綁定選擇是否相同或等效。
10. 根據權利要求9所述的裝置，其中，在綁定選擇中包含由一個線 程與若干個核的組合、即核子集的複雜映射關係構成的組合項的情況下， 所述等效綁定選擇檢測器通過確定兩個組合項的標識因子IF是否相同， 來判定兩個組合項是否等效，其中標識因子IF利用下述等式計算得到formula see original document page 3其中，cv是綁定選擇的組合矢量，其為表示在該綁定選擇中各個核是否被分配有線程的布爾矢量，￡ = (l,l，...,l), " "表示點積，而IM為多核系統的關聯矩陣，所述關聯矩陣IM中的第i行第j列的元素Xy表示所述多核系統中第i個核和第j個核之間的關係，當兩個綁定選擇中包含的非組合項彼此相同且組合項彼此等效時，兩 個綁定選擇是等效的。
11. 根據權利要求10所述的裝置，其中，對所述多個核中各個核之間的關係的定義是具有完備性的。
12. 根據權利要求7至11中任何一項所述的裝置，其中，所述多個 線程是彼此相同的線程。
13. —種使用根據權利要求1至6中任何一項所述的方法進行自適應 線程調度的方法，包括以下步驟根據作為線程調度優化目標的多線程應用和多核硬體平臺的有關信 息，利用根據權利要求1 - 6中任何一項所述的方法計算可用的線程調度 搜索空間；在所述多核硬體平臺上在所述線程調度搜索空間中模擬運行所述多 線程應用，並且基於模擬運行所述多線程應用時所述多核硬體平臺的性能 監視結果，從所述線程調度搜索空間中搜索並確定優選的綁定選擇，作為 優選綁定方案；以及才艮據所確定的優選綁定方案產生調度執行計劃，並實際應用該調度執 行計劃。
14. 根據權利要求13所述的自適應線程調度方法，其中，所述性能 監視結果是根據預先定義的測量條件和性能標準對所述多核硬體平臺進 行性能監視而得到的。
15. 根據權利要求13或14所述的自適應線程調度方法，其中，所述 自適應線程調度方法以離線方式或在線方式執行。
16. 根據權利要求13或14所述的自適應線程調度方法，其中，使用 下述搜索方法之一從所述線程調度搜索空間中搜索並確定優選的綁定選 擇模擬退火，神經網絡，最速下降方法，動態編程，和遺傳算法。
17. —種自適應線程調度系統，包括 作為優化目標對象的多線程應用和多核硬體平臺； 根據權利要求7至12中任何一項所述的裝置，被配置用於根據多線程應用和多核硬體平臺的有關信息計算可用的線程調度搜索空間；模擬運行控制器，被配置用於在所述多核硬體平臺上在所述線程調度 搜索空間中模擬運行所述多線程應用；以及性能監視器，被配置用於記M擬運行所述多線程應用時所述多核硬 件平臺的性能監視結果，其中，所述模擬運行控制器基於來自所述性能監視器的性能監視結 果，從所述線程調度搜索空間中搜索並確定優選的綁定選擇，作為優選綁 定方案，並才艮據所確定的優選綁定方案產生調度執行計劃，並實際應用該 調度執行計劃。
18. 根據權利要求17所述的自適應線程調度系統，進一步包括測 量條件和性能標準儲存庫，用於存儲預先定義的測量4Ht和性能標準，其中，所述性能監視器通過才艮據所述預先定義的測量條件和性能標準 對所述多核硬體平臺進行性能監視，而得到所述性能監視結果。
19. 根據權利要求17或18所述的自適應線程調度系統，其中，所述 模擬運行控制器使用下述搜索方法之一從所述線程調度搜索空間中搜索 並確定優選的綁定選擇模擬退火，神經網絡，最速下降方法，動態編程， 和遺傳算法。
全文摘要
本發明提供了用於計算可供在多核系統上對多線程應用進行線程調度時使用的線程調度搜索空間的方法和裝置，以及利用該方法和/或裝置進行自適應線程調度的方法和系統。所述計算搜索空間的方法包括獲取有關多線程應用和多核系統的硬體結構的信息；通過參考所述有關信息，計算所有可能的、包含多個線程與多個核之間的映射關係的綁定選擇；基於多核系統的硬體結構，從所有可能的綁定選擇中找出所有彼此相同或等效的綁定選擇；以及在所有可能的綁定選擇中，對於所有彼此相同或等效的綁定選擇，保留其中之一，而除去其餘彼此相同或等效的綁定選擇，以得到可供線程調度時使用的搜索空間。
文檔編號G06F9/48GK101634953SQ20081013325
公開日2010年1月27日 申請日期2008年7月22日 優先權日2008年7月22日
發明者嚴 李, 林海波, 王海川, 凱 鄭, 高志國 申請人:國際商業機器公司