TWI541725B

TWI541725B - 用於管理多核心架構之資源的方法和設備

Info

Publication number: TWI541725B
Application number: TW102119397A
Authority: TW
Inventors: 立派特馬克大衛
Original assignee: 新思科技有限公司; 富士通半導體股份有限公司
Priority date: 2004-03-31
Filing date: 2005-03-31
Publication date: 2016-07-11
Also published as: JP2013211050A; JP6018021B2; TWI407373B; CN1993674A; JP5789072B2; TW200602981A; JP2007531137A; GB0407384D0; EP1730628B1; TW201337769A; KR101239082B1; JP2013061947A; EP1730628A1; KR20120106890A; KR20070022034A; TWI502511B; KR101258502B1; KR20120003014A; TW201337768A; CN100517219C

Description

用於管理多核心架構之資源的方法和設備

本發明大致是關於一用於管理多核心架構之資源的方法和設備。

今日，結合複雜而多樣的多核心架構之半導體裝置，已廣泛使用於各種系統及裝置中，從桌上型電腦至目前最新的電子裝置(如行動電話、個人數位助理，及高速電信或網路交換之設備)均可見到。

對於各種用途之電腦處理器，處理器製造商皆持續地致力於增加現有處理器的效能，以維持或降低其單位「成本」。

處理器之「成本」可使用各種參數加以測量。雖然在大多數的情形中，成本係單純的財務數字，但在許多應用，特別是嵌入式處理器(embedded processor)市場，對於成本的計算亦包含其他方面的考量，如：電力消耗、冷卻需求、效能及可上市的時間等。

處理器執行有用功能之絕對處理能力，可使用「每秒可執行完成多少百萬指令(MIPS)」加以衡量，而處理器之「價格-效能」比，可使用如「每秒可執行完成多少百萬指令/釐米平方(MIPS/mm2)」、「每秒可執行完成多少百萬指令/元(MIPS/$)」或「每秒可執行完成多少百萬指令/毫瓦特(MIPS/mW)」等比率加以衡量。

然而實際上，並非所有指令皆可完成相同數量的有用工作，所以僅以MIPS高低仍無法輕易地進行比較。例如，數位訊號處理器(DSP)適於在行動電話的無線介面邊進行密集的數學運算，但在執行電話螢幕上的網頁瀏覽器時反而效率不彰。這表示利用「應用程式(application available)」的價格-效能比評估該處理器效能更為有效。

此外，控制處理器以實施一特定應用程式所必需用到之程式(軟體)工具的不足之處也會削減有效效能。因此，處理器對於特定應用程式所能產生之最終效能等級，可視為可用之價格-效能等級或「可完成的應用程式」之價格-效能等級。

在半導體公司致力於改善處理器應用程式之價格-效能比時，新一代的處理器(即多核心裝置)已開發出。多核心裝置係高度整合之處理器，以各種不同之元件(核心)建立而成，為了對一可由處理器執行之特定態樣應用程式，提供最高等級之有用價格效能，每一元件(核心)可能經高度專業化設計。此種裝置可為「異構型(heterogeneous)」，即結合複數相異的核心，或是「同構型(homogenous)」，即結合複數相類似的核心。

幾乎所有的多核心裝置，皆可歸類為系統單晶片(SoC)裝置，因為其除了結合多處理核心外，也結合了記憶體、輸出/輸入及其他管理特定產品大部份(若非全部)硬體需求所需要的系統「核心」。雖然並非所有的系統單晶片裝置皆擁有多處理核心，但多核心與系統單晶片這兩個名詞常常是可以互換的。行動電話便是多核心系統單晶片很好的例子，在許多的行動電話中，我們可發現在行動電話中有單一的處理器，其包含了一或多個數位訊號處理器，用以執行無線介面(wireless interface)；以及一一般目的處理器以執行電話上的使用者應用程式。

摩爾定律讓多核心裝置的出現成為可能，該定律說明IC上的電晶體數量會因製程技術之演進，每18個月增加一倍。因此，摩爾定律係考量在矽晶片(silicon die)上之固定區域置入更多個別電晶體，使得就技術及經濟層面而言，在單一矽晶片上製造更為複雜之裝置成為可行。同時，減少電晶體的體積也可讓其變換(switched)速度更快。

到目前為止，摩爾定律驅使著我們藉由矽的應用，製造新一代更小、更快與更有成本效益的處理器，但對於其底層架構卻無任何重大的改變(意即：其改良的部分在於製程及裝置實體微架構的改良，而非裝置邏輯宏觀架構的改良)。

實際上，多核心/系統單晶片之發展趨勢，可視為宏觀架構已朝向更高階層的整合，起初將輸出入(通訊)功能置於矽晶片本身，現在則是輸出入、記憶體、多處理單元之功能、數位訊號處理器、及共同運作之處理器皆可整合至同一矽晶片。這些處理器針對特定種類之應用程式，提供最低成本、最高效能之處理器，以減少其終端產品之製造成本。此外，將大多數系統元件整合至單一處理器可減少零件之數量，進而增加穩定度並降低電力消耗。

但有項關鍵性的問題，即是如何將此多核心裝置之底層架構的使用最佳化，使其達到最高可能的「應用程式」價格-效能。

處理器及系統設計者可使用許多方法，在應用程式軟體內部進行平行處理(應用程式層級平行處理)，以及於指令流內部進行平行處理(指令層級平行處理)。當系統正執行/在「運轉」(動態系統)時，或當應用程式軟體正編譯/於編譯時期(靜態系統)時，各項表現會因平行處理於何處進行管理，以及是否進行管理而不同。實際上，並無法明確區別動態與靜態系統以及著重硬體(hardware intensive)與著重軟體(software intensive)解決方案，且來自其中一項專業之技術，亦常用在其他方面。

依照單一處理核心的標準，多線程處理器(multiple issue processors)之概念，或是來自單一流的許多指令平行處理之機器已經發展成熟。目前之發展有兩種基本類型：超純量(superscalar)及超長指令字組(Very Long Instruction Word，簡稱VLIW)處理器。超純量處理器於每一時脈發送出不同數量之指令，該時脈於執行時期(動態安排)或於編譯時期(靜態安排)確認。VLIW處理器發送固定數量由編譯器所定義之指令，形成一超長指令字組。典型而言，當系統之設計模型為一標準、單一之處理器抽象概念時，程式設計者絲毫不會察覺此過程。

超執行緒(Super-threading)及高速執行緒(Hyper-threading)兩者皆是藉由於多個虛擬處理器間，以多路傳輸多個執行緒而模擬多處理器之技術。典型而言，這些虛擬處理器共享某些資源，就統計而言，這些資源不會在所有時間由單一執行緒使用。超執行緒及高速執行緒架構，看起來即如同多個獨立處理器，因此為了有效率的運作，需要應用程式平行處理之標準。典型而言，處理器核心之硬體限制，將可被支援之執行緒數量大約限制在100以下。

此外，還有一些系統架構的選擇可讓許多應用程式利用內在平行(inherent parallelism)。在複合指令複合資料模式(Multiple Instruction Multiple Data，簡稱MIMD)機器中之每一處理器執行其自有之指令並在其自有的資料集上運作，並透過某些共享資源(例如：記憶體和/或互連介面)與其同位體(peers)共同運作，如此一來MIMD機器具有應付各種不同應用程式之能力，使之愈來愈受到歡迎。

隨著效能需求的增加，內嵌式系統亦增加多核心MIMD架構之使用，利用多個相異或相同之處理資源，達到所要求之矽效率(silicon efficiency)標準。典型而言，這些是一種MIMD機器，其被稱之為集中共享記憶體架構，亦即單一之定址空間(或其部分)係由數個處理資源所共享，然而，還有更多特殊應用混合架構也常見到。

雖然MIMD陣列中的每一處理資源，可利用指令層級平行(Instruction Level Parallelism，簡稱ILP)，MIMD機器亦可採用執行緒層級平行(Thread Level Parallelism，簡稱TLP)以發揮底層硬體(underlying hardware)之潛在效能。ILP於執行期間(由特定硬體)或編譯期間(由最佳化之編譯工具)識別，相較之下，TLP則於應用程式設計期間，由高階程式軟體定義。

軟體界將執行緒這種概念當成平行化的高階表示(a high level expression of parallelism)已行之有年。一執行緒會定義一工作獨立封包，其包含執行狀態、指令流及資料集，而且可與其他執行緒同時執行。指令流之複雜程度並不重要。從簡單的資料傳輸到複雜的數學轉換，執行緒皆可處理。

傳統上，作業系統會協助提供系統管理，包含執行緒分配功能，讓一應用程式可於一特定組態之多核心架構上執行，而軟體工程師無需對底層裝置架構有詳細的瞭解。然而，單核心裝置中現有的執行緒管理軟體技術，在多核心架構上卻無法以相同的方式輕易套用。目前之解決方案均係專屬且需根據設計準則加以設計，且典型而言會影響效能及延展性。

以往在異構型多核心系統(大體而言即系統具有相異之處理資源)之情形下，會使用許多不同方法讓不同的處理資源得以共同運作。然而，廣泛的說這些可劃分為兩類，即為「代理主機(proxy host)」及「共同運作(co-operative)」(也就是所熟知的「點對點(peer to peer)」)。以前者而言，一指定的一般用途主處理器(在以匯流排為基礎之系統中通常稱為中央處理單元)會安排系統之工作，並將資源(如記憶體及裝置)之存取同步化。此系統管理典型而言會在作業系統核心中運作，並與系統應用程式及主處理器上非同步事件之處理競相爭取時間片段(slices of time)。換句話說，此一般用途之處理器，必須對於多核心裝置上之所有處理資源，扮演集中化代理執行緒管理員之角色，而且還要作為關鍵應用程式處理器。

當一般處理器應用在此組態中時，必須根據預先定義之排程方法(即執行緒之優先權)，維護已就緒好利用每一處理資源執行之執行緒佇列(queues)(即分配或就緒佇列)，並且在執行緒本身可開始執行之前，必須維護等候一些事件(或另一執行緒結果回傳)之執行緒佇列(即未決和時序佇列)。這些都還要加上其他的系統負擔，例如執行執行緒前的處理器分配。

每當一般用途處理器將其處理時間自目前執行之執行緒，轉移至系統管理(包含執行緒管理)時，例如：執行緒執行結束(會釋放剛完成該執行緒之處理資源)而發出中斷(interrupt)，則該處理器就必需改變控制程式(context)。

控制程式之改變包含儲存將執行緒暫停並進入記憶體的目前進度、取得指令(該指令與服務其他執行緒/處理資源之管理程序相關)，接著完成這些指令，包含任何組態需求。另外還需進行更進一步的控制程式改變，以返回原來暫停的執行緒。這些控制程式的改變，典型而言係於接收中斷時執行，且於內嵌式系統中，在一般用途處理器上執行應用程式碼時，這些中斷往往是頻繁且非同步的。因此整體而言，系統呈現明顯的效能低落。控制程式的轉換對於主處理器快取之有效性亦有負面的影響(即所謂的「冷快取(cold-cache)」效應)。

於一共同運作系統中，每一處理資源會執行作業系統中之個別的執行個體(instance)，部份能允許內部資源相互交流。由於同位體間特定的中斷選擇途徑(routing)，因此此分配具有相當精確之架構分區方法(architectural partitioning)。雖然此類型之系統提供製作應用程式所需之基本單元(primitives，以下簡稱基元)，但該實施例的效能仍因為作業系統核心活動所造成之控制程式頻繁轉換，而受到傷害。

總結而言，目前用於實施傳統架構(一般用途處理器、軟體等)系統管理的設計及方法，並不適用於複雜異構型多核心架構之系統及執行緒管理。而一般用途處理器亦的確在微(指令集)及巨(快取、註冊檔管理)架構層級，皆無法達到最佳化。雖然多核心處理器之內部連結提供一實體媒體，可讓個別處理資源間進行內部交互運作，但卻無所有處理資源所共享之泛系統工作管理(system wide task management)及通訊層，以利用一致的方法進行系統管理。最糟的情形是，這可能導致每個處理資源間各種可能通訊管道，都會產生其個別之問題，而每個個別問題，都必須以特殊的方式在軟體中分別解決。

因此，我們需要一項有效率之方法，對這些非常複雜之多核心架構進行系統管理。僅有軟體抽象概念(software abstraction)並無法提供複雜多核心架構所需的效能水準。

根據本發明之第一種態樣，其針對專利申請範圍第1項中定義之多核心處理器，提供一資源管理及工作分配之控制器。

在較佳之實施例中，專利申請範圍第1項之控制器，係專用於資源管理及工作分配，且無法提供更多之處理資源。

在本發明之實施例中，該「傳統」的主要處理單元(即一般用途處理資源，其缺乏本發明之資源管理及工作分配控制器，但可進行工作分配並作為其中一可用的處理資源)可於系統啟動時扮演主控者，具有資源管理及工作分配控制器，該控制器在初始化之過程中從微處理器取得主狀態(master status)。

在本發明之實施例中，提供給異構型多核心處理器之功能為讓其對處理資源進行工作分配，否則在處理一特定工作時，處理資源的使用會被忽略。如此一來，本發明之控制器即可更為有效率地使用可用的資源。

本發明藉由提供個別資源管理及工作分配之控制器，提供多核心處理器一改良之工作分配及管理系統，使其於可用處理資源間之工作分配更有效率。該控制器將系統管理及例外管理之元件變為一專用、有效率、硬式編碼之實施例。

本發明實施例運用控制器客戶端(controllar clients) 以及控制器，而非執行「代理伺服器(proxy agent)」之功能。該控制器客戶端可使用硬體或軟體實施。這樣的安排可有有效率地掌控底層系統於「執行期間(run-time)」之活動。特定言之，該控制器持續地根據預先定義的分配參數之範圍，維持系統執行緒狀態及排程決策之正確性。

就所有組成元件及個別處理資源主體(autonomy)間之工作分配而言，無論其複雜性如何，該較佳實施例之架構提供了顯著的效益。所有處理資源皆成為從屬裝置(slave device)，其預設是「等候(lazy)」，亦即等候資源管理及工作分配控制器，經由專屬之中斷(在較佳實施例中)，對其下達明確之指令後方執行工作。相同地，在其他實施例中，資源管理及工作分配控制器以及處理資源間，可使用輪詢的方式溝通(poll based communication)。

於使用本發明控制器之系統中，其所有非同步之事件會優先繞送至該控制器，這些事件皆係由該架構之外部所驅動，無論是直接地透過針腳(pin)，或間接地透過其中一處理資源(即一輸出入裝置)之外部操作；而該控制器會利用一系列排程方法(於「啟動期間」設定)將這些非同步事件與目標處理資源上目前正執行之工作相比較。只有在與外部事件相關之中斷服務執行緒(interrupt service thread，簡稱IST)負責目前正在執行的交易(執行緒或工作)時，處理資源才會被中斷，如此可避免於任何處理資源內進行不必要之控制程式交換，而這正是此技術領域所遭遇之問題。此外，於較佳實施例中之控制器客戶端，可使任何複雜度之處理資源，於共享資源及該控制器本身上執行基本系統管理作業(建立執行緒、發送同步化基元、刪除執行緒及記憶體複製等)，以避免需要以指令集為基礎之機器才能由代理主機(proxy)執行這些工作。

於本發明更進一步之態樣中，提供至少包含此一控制器之一多核心處理器。

本發明亦揭露專利申請範圍第40項所定義之多核心處理器控制及分配資源的方法。

更多的優點與特色將於後續詳述。

10‧‧‧系統架構

20‧‧‧管理系統

100‧‧‧輸入介面

110‧‧‧輸出介面

115‧‧‧連接介面

120‧‧‧系統管理控制器客戶端

120b‧‧‧代理硬體控制器客戶端

120c‧‧‧代理硬體控制器客戶端配接器

125‧‧‧控制器客戶端控制區塊

130‧‧‧系統管理控制器

135‧‧‧資料區塊

140‧‧‧系統記憶體

145‧‧‧處理資源指令區塊

145a‧‧‧處理資源型態1指令區塊

145b‧‧‧處理資源型態2指令區塊

150‧‧‧處理資源/複數處理資源/硬體處理資源

150a‧‧‧處理資源型態1

150b‧‧‧處理資源型態2

160‧‧‧系統連接介面

170‧‧‧連接介面代理程式

180‧‧‧緊密耦合記憶體介面群組

190‧‧‧專屬之緊密耦合記憶體

191‧‧‧記憶體位址匯流排

192‧‧‧記憶體讀取資料匯流排

193‧‧‧記憶體寫入資料匯流排

194‧‧‧記憶體寫入啟用

195‧‧‧控制器記憶體元件

196‧‧‧記憶體讀取啟用

200‧‧‧系統控制群組

210‧‧‧外部中斷群組

220‧‧‧內部控制群組

221‧‧‧中斷

230‧‧‧內部連結介面群組

300‧‧‧執行緒輸入管理器

310‧‧‧執行緒同步化管理器

320‧‧‧執行緒輸出管理器

330‧‧‧排程管理器/執行緒排程管理器

340‧‧‧執行緒記憶體管理器

350‧‧‧中斷管理器

360‧‧‧時序管理器

380‧‧‧系統介面

500‧‧‧控制器客戶端有限狀態機

510‧‧‧系統至處理資源之路徑

520‧‧‧處理資源至系統之路徑

530‧‧‧比較器(n<addr<m)

540‧‧‧比較位址暫存器

550‧‧‧減法器

560‧‧‧偏移位址暫存器

570‧‧‧比較器(EQ)

580‧‧‧觸發位址

第1圖顯示根據本發明一實施例之系統邏輯設計概要區塊圖，該系統包含一資源管理及工作分配控制器；第2圖顯示第1圖邏輯設計之例示實施方式，其中實施本發明之控制器與一專用記憶體裝置和一控制器客戶端，位於一一般用途、多核心處理器架構內；第3圖顯示一結合第2圖中元件、以匯流排為基礎之系統單晶片(SoC)架構之實施例；第4圖顯示第1、2和3圖中控制器外部連結的詳細視圖；第5圖顯示第2和3圖中記憶體裝置之詳細視圖；第6圖顯示第2、3和4圖中控制器內部組成之詳細視圖；第7a圖顯示第2及3圖中控制器客戶端之概要區塊圖；第7B圖顯示當單一控制器客戶端扮演複數處理資源之代理主機時，該系統之概要區塊圖；第8圖顯示硬體控制器客戶端較為詳細之概要區塊圖；第9a圖及第9b圖顯示一般的描述符及其相關欄位；第9c圖及第9d圖顯示執行緒之描述符及其相關欄位；第9e圖及第9f圖顯示調度程式層(scheduler tier)之描述符及其相關欄位；第9g圖及第9h圖顯示分配佇列之描述符及其相關欄位；第9i圖及第9j圖顯示未決佇列之描述符及其相關欄位；第9k圖及第9l圖顯示略過列表(skip list)之描述符及其相關欄位；第10圖顯示一執行緒描述符、該系統管理控制器、一處理資源及該共享之系統記憶體間典型之關係；第11圖說明第10圖分配中之間接性原理(the principle of indirection)，其中顯示二相異之處理資源；第12圖顯示第4圖控制器之執行緒管理概況；第13圖顯示一典型之未決佇列結構；第14圖顯示一典型之未決佇列略過列表；第15圖顯示一典型之計時器佇列；第16圖顯示一典型用於二處理資源之就緒佇列結構(Ready queue structure)；第17圖顯示一典型單一分配佇列結構之例示實施例；第18圖顯示一雙層排程層級(hierarchy)，包含執行緒束(thread bundling)；第19圖顯示一例示之簡化佇列結構，該結構通常可於一通訊系統中發現；

第1圖顯示一系統架構10之邏輯圖，該系統包含根據本發明一實施例之功能特徵。該架構10至少包含複數處理資源(processing resources)150，每一處理資源可能與其他處理資源150中之資源相似或相異，且每一處理資源可能有不同之複雜性(complexity)。每一處理資源可共同存取一共用系統記憶體(common system memory)140，其共享之資料係透過一連接介面(interconnect)160儲存。習知技藝者皆明瞭，並非所有系統記憶體140，皆須讓所有處理資源150共用。

根據本發明之一實施例，該系統架構亦至少包含一中央工作分配及管理系統20。該中央工作分配及管理系統20包含一系統管理控制器130及一專用之緊密耦合記憶體介面(dedicated tightly coupled memory interface)180，其與一專用耦合記憶體190緊密相連。每一處理資源150可透過一連接介面115存取該控制器130。習知技藝者皆明瞭，第1圖之實施例並不需要特定之連接策略(即該控制器130與每一處理資源150(反之亦然)通訊所需之配置方式，以及每一處理資源150與系統記憶體140通訊所需之配置方式)；特定言之，除了每一處理資源可直接或間接(即透過其他處理資源或其他方式)與該控制器130通訊外，還可利用點對點連結、集中系統匯流排或甚至管道(pipelined)架構。

第2圖顯示多核心處理器實施第1圖之邏輯配置，此亦僅為例示。第2圖之多核心處理器利用複數處理資源150，每一處理資源皆透過系統連接介面160相連。系統連接介面160可透過輸入介面100及輸出介面110，依次與系統管理控制器130通訊。在第2圖之實施例中，系統連接介面160係以傳統中央匯流排之方式呈現，其將每一處理資源150與其他處理資源、控制器130相連，並與共享之系統資源(如系統記憶體140)相連。利用目前許多可用的介面連接技術(interface technologies)可達到與記憶體140連結之目的。該記憶體可能由任何目前可用之電腦記憶體技術構成，舉例而言，靜態隨機存取記憶體(SRAM)、或雙倍資料速率隨機存取記憶體(DDR RAM)。

如第2圖中所示，每一處理資源150具有一相關之系統管理控制器客戶端120，其係用以自中央控制器130處接收控制資訊，並依所接收之控制資訊，管理處理資源150。控制器客戶端120之功能及目標將於第7a圖及第8圖詳述。每一處理資源亦具有一相關連接介面代理程式170，以透過系統連接介面160與控制器130通訊。連接介面代理程式170提供控制器客戶端120一一般介面，其獨立於使用在系統連接介面160上之底層連接通訊協定，換句話說，其會將系統連接介面160上所使用之通訊協定，及控制器客戶端120所使用之通訊協定間之協定轉譯。由於使用了連接介面代理程式170，本發明實施例之控制器客戶端120可與任何目前可用之系統連接通訊協定共同使用。

整體而言，多核心處理器係用以執行一目標應用程式，該目標應用程式可分散成許多個別之工作，也就是執行緒。每一處理資源150會根據多個參數，包含(但不限於)執行緒之優先權、每一處理資源150之可用性及特定處理資源對於執行特定執行緒之適當性，由控制器130分配一適當之執行緒。後續將作更詳盡的描述。

習知技藝者皆明瞭，增加系統管理控制器130及其專用記憶體190不需重新設計處理器10之佈局(layout)。

第3圖中顯示一特定之配置方式，其以區塊圖顯示一典型之系統單晶片(SoC)架構，並說明於實際應用程式中，可置於控制器130之資源管理下之各種不同處理資源。習知技藝者皆明瞭，處理資源可特指較一般性之功能，如數位訊號處理器(DSP)，或較侷限性之功能，如輸出入周邊設備。

系統管理控制器介面群組

第4圖顯示控制器130及其周邊之有關介面群組200-250。

系統控制群組200至少包含二系統輸入訊號，以確保系統管理控制器130之正確運作。該二系統輸入至少包含一連接至系統時脈之CLK輸入，及一RST輸入。所有來自系統管理控制器130之輸出信號與系統時脈同步，而所有輸入至系統管理控制器130之信號利用此時脈取樣。RST輸入係一同步重置信號(synchronous reset signal)，其用以重置該系統管理控制器130。

外部中斷群組210係由源自系統管理系統外部之同步外部中斷群組所組成。這些信號在連接至系統管理控制器130之周圍前，必需與CLK進行同步。外部中斷群組210內的信號，舉例而言，可由外部之輸入，或直接透過針腳(pin)由多核心處理器之外部驅動。外部中斷輸入之數量係於多核心處理器10之設計階段所定義。

內部控制群組220係由每一控制器客戶端120之單一同步中斷，及其相關處理資源150所組成。因此信號群組之數量典型而言與系統中之處理資源150數量相等，且將會在多核心處理器10之設計階段定義。該內部中斷信號表示一就緒執行之執行緒，且被分配給與控制器客戶端120相關之特定處理資源150。

緊密耦合記憶體介面群組180將系統管理控制器130連接至其專屬之緊密耦合記憶體資源190。第5圖中顯示一專屬緊密耦合記憶體190之典型架構。位址路徑(address path)及資料路徑(data path)之寬度，係於多核心處理器10之設計階段所定義。該專屬緊密耦合記憶體介面包含一記憶體位址匯流排191、一記憶體讀取資料匯流排192、一記憶體寫入資料匯流排193以及寫入194與讀取196之啟用信號(enable signals)。

該附加之記憶體假設為同步之靜態隨機存取記憶體(SRAM)。該專屬緊密耦合記憶體190包含一整數數量之控制器記憶體元件195，其係根據目標應用程式之需求，於多核心處理器10之設計階段定義。在較佳之實施例中，每一控制器記憶體元件195皆佔用256位元的記憶體空間。於同樣的較佳實施例中，該控制器最多支援65536個控制器記憶體元件(即16Mb記憶體)。雖然佇列描述符(queue descriptors)會佔用控制器記憶體元件195，但在一典型系統中所需之控制器記憶體元件數量，將由執行緒支援需求所決定。舉例而言，在該系統管理控制器130中，一可同時支援400個執行緒之系統約需要128kb之附加記憶體。

第4圖中之連結介面群組230會符合使用於多核心處理器10和互連代理程式170中之互連協定，該互連協定係於多核心處理器之設計階段所定義。

控制器子區塊之說明及函式

第6圖顯示系統管理控制器130之主邏輯元件。控制器130之函式，可分為四個主要的內部平行處理子區塊，分別執行下列函式：

1.執行緒輸入管理器(Thread Input Manager，簡稱TSIM)300，係用以維護空閒控制器記憶體元件195(於專屬緊密耦合記憶體190中)之列表，並用以監看控制器記憶體元件195之回復(recovery)。

2.執行緒同步管理器(Thread Synchronisation Manager，簡稱TSPM)310，係用以維護未決列表(Pending lists)及專屬緊密耦合記憶體190內之計時器佇列(timer queue)並用以將執行緒同步化，並根據需求，將執行緒放入至專屬緊密耦合記憶體190內之就緒佇列架構。藉由對未決執行緒描述符(位於專屬緊密耦合記憶體190中)之插入及抽取，執行緒同步管理器310可維護未決及計時器佇列架構之完整性。

3.執行緒輸入管理器(Thread Output Manager，簡稱TSOM)320，係用以維護專屬緊密耦合記憶體190內之就緒佇列架構，以及專屬緊密耦合記憶體190中，每一處理資源150之分配佇列(Dispatch queues)。執行緒輸入管理器320更用以產生傳送至控制器客戶端120之中斷221。藉由插入和抽取控制器記憶體元件195內之執行緒描述符(位於專屬緊密耦合記憶體190中)，可維護就緒佇列架構之完整性。

4.執行緒排程管理器(Thread Schedule Manager，簡稱TSSM)330，係用以提供排程決策給就緒佇列結構(位於專屬緊密耦合記憶體190內)中之每一處理資源150。

此外，一些次要處理子區塊亦提供支援功能：

5.執行緒記憶體管理器(Thread Memory Manager，簡稱TSMM)340，係用以提供附加之專屬緊密耦合記憶體190聚合存取(aggregate access)，包含相互排斥及鎖定(mutual exclusivity and locking)。

6.中斷管理器(Interrupt Manager，簡稱TSIC)350，係用以將來自外部系統之中斷，轉換為內部同步化基元(internal synchronisation primitives)。

7.時序管理器(Time Manager，簡稱TSTC)360，係用以提供計時功能，以達成同步，並提供給每一處理資源150時序監視功能(watchdog timer functionality)。

8.系統介面(System Interface，簡稱TSIF)380，係用以提供與多核心處理資源150互連之介面及組態，並於執行期間存取多核心處理資源150。

上述系統管理控制器130中主要及次要的處理子區塊間的交互作用，將於後續詳述。

每一子區塊可提供一功能集(a set of functions)給其他子區塊，使每一子區塊可指示其同位體(peers)在他們所維護之結構(於專屬緊密耦合記憶體190中)上執行運作。當一相似之指令由一控制器軟體應用程式介面(API)接收時，一特定子區塊會呼叫函式。

執行緒輸入管理器函式：

執行緒輸入管理器300提供三個公用函式給系統管理控制器130內部之其他子區塊。

FreeListStatus函式可回傳控制器記憶體元件195空閒資源表(free list)中之標頭指標(head pointer)及元件數量。該空閒資源表為目前未使用之控制器記憶體元件195列表。當一相似之指令由控制器130軟體API接收時，該函式僅可由系統介面380呼叫。

PushFreeIndex函式係用以將已釋放之控制器記憶體元件195索引，推回至空閒資源表中。此函式僅可由執行緒排程管理器330呼叫。

PopFreeIndex函式用以自空閒資源表中，提取一空閒控制器記憶體元件195索引。典型而言，其係由系統介面380中之API呼叫服務常式呼叫。

執行緒同步管理器函式：執行緒同步管理器310提供七個公用函式給系統管理控制器130中之其他子區塊。

在控制器130軟體API接收到類似之指令後，下述的五個函式僅可由系統介面380呼叫。

PushPendingDescriptor函式係於開機過程中使用，將一未決佇列描述符加入至未決佇列描述符列表中。

PushThread函式係於執行期間使用，將一相依執行緒加入至一特定之未決佇列中。

SetTimerStatus函式可設定計時器佇列中之標頭指標及元件數量。

GetTimerStatus函式可回傳計時器佇列中之標頭指標及元件數量。

SetPendingStatus函式可設定未決佇列描述符列表之狀態。

GetPendingStatus函式可回傳未決描述符佇列中之標頭指標及元件數量。

SyncEvent函式係用以將一同步化基元發送至一特定之未決佇列。此函式係由執行緒中斷管理器350及系統管理控制器380所呼叫。

TimeEvent函式係用以將一以計時器為基礎之同步化基元發送至計時器佇列。此函式僅可由時序器管理器360 呼叫。

執行緒輸出管理器函式：

執行緒輸入管理器320提供五個公用函式給系統管理控制器130中的其他子區塊。

Push函式可將一執行緒描述符置入就緒佇列結構中。此方法可能會以高優先性呼叫，以加快處理速度(如：控制中斷)。其中，該執行緒為獨立者(立即就緒)，呼叫將由系統介面380產生，而執行緒描述符原本就有相依性者，則呼叫由執行緒同步化管理器310產生。

在控制器130軟體API接收到類似之指令後，下述三個函式僅可由系統介面380呼叫。

GetDispatchQueueStatus函式可回傳分配佇列列表中之標頭指標及元件數量。

SetDispatchQueueStatus函式可設定分配佇列列表中之標頭指標及元件數量。

DispatchQueuePop函式可自分配佇列之頭端(head)，提取一執行緒描述符。

DispatchWorkQueuePush函式可將一分配佇列推入(push)至執行緒輸入管理器320之工作佇列。此函式僅可由執行緒排程管理器330呼叫，其使用此函式以告知輸出管理器，分配佇列因排程更新所需進行之改變。

執行緒排程管理器函式：

執行緒排程管理器330提供三個公用函式給系統管理控制器130中之執行緒輸出管理器320及系統介面(TSIF) 380。

在執行緒輸出管理器320將一執行緒描述符加入至一就緒佇列結構中之後，PushPushWorkEvent函式隨即由執行緒輸出管理器320呼叫。

在執行緒輸出管理器320將一執行緒描述符從一就緒佇列結構中移除之後，PushPopWorkEven函式隨即由執行緒輸出管理器320呼叫。

FreeIndex函式能讓一控制器記憶體元件195釋放，以使其能適當地與執行緒排程管理器330中正進行之排程活動同步。在控制器130軟體API接收到類似之指令時，或因執行緒輸出管理器320之取出(pop)作業，該呼叫即有可能發出。

控制器客戶端

如前所述，該處理資源150之名稱適用於任何可執行指令之資源，無論該指令多簡單。因此具有固定函式之資源，如輸入/輸出模組，亦包含在內。根據處理資源150之類型，系統連接介面160及處理資源150間，通過系統管理核心客戶端120之連結可為單向或雙向。

第7a圖顯示一控制器客戶端120之例示概要區塊圖，其與系統管理控制器130一同使用。

利用合適之處理資源150，例如：一般目的處理器或數位信號處理器，該控制器客戶端120典型係在軟體內實施。然而，若該處理資源150僅具有有限之功能，則控制器客戶端120可能需要硬體元件。

當一硬體元件於系統連接介面160及處理資源150間使用時，控制器客戶端120仍使用相同介面與處理資源150進行溝通，也就是說，控制器客戶端提供給連接介面代理程式170之介面與處理資源150至控制器客戶端之介面完全相同。於某些情況下，可將進入處理資源之資料路徑與離開處理資源輸出之資料路徑視為相異，例如：輸出/輸入裝置。

除了主介面外，控制器客戶端120亦提供頻外介面(out of band interface)，當需要執行時期及偵錯事件之輸出時即可使用。假設這些事件是利用標準中斷、呼叫適當服務常式，則會利用一軟體控制器客戶端120。

控制器客戶端運作模式：

每一控制器客戶端120都完全以中斷驅動。當自控制器130接收一內部中斷時，控制器客戶端120自分配佇列頭端取出執行緒描述符，該分配佇列與專屬緊密耦合記憶體190所擁有之特定處理資源150相關聯。接著，該執行緒描述符中之唯一索引被用以自主記憶體資源140中讀取更多執行緒控制資訊，即執行緒控制區塊(Thread Control Block，簡稱TCB)。該TCB內所包含之資訊可能為：

1.控制器客戶端120組態內容。此資訊可用以設定控制器客戶端120系統資源使用管理、資料呈現模式等。

2.處理資源150組態內容。此為準備處理資源150以執行特定執行緒所需之資訊。此資訊可能包含此執行緒從先前部分執行之回復資料，或專業硬體加速器之組態，如聲音的音頻編解碼器(CODEC)。

3.指令內容。在一固定功能硬體加速器之例子中，目標硬體處理資源內會隱含「指令」，舉例而言，當該處理資源150為一輸出模組則會隱含一輸出指令，且任何所需之專門化或組態將包含在該組態資訊中。在一軟體控制器客戶端120之例子中，典型而言，此將會是指向與該執行緒相關聯之功能碼的指標。

4.資料內容。此內容可定義系統記憶體140之起始位址或多個位址，以及執行緒可作業之資料範圍。

5.控制器客戶端120後處理(post-processing)內容。此內容定義控制器客戶端120於執行緒執行完成後之動作。

控制器客戶端120之作業有三個不同之階段：

1.設定階段，於此階段內處理資源150及控制器客戶端已準備好執行一特定之執行緒。在最簡易的情形下，可以無設定階段。

2.執行階段，其此階段內執行緒正在執行，而控制器客戶端120可能正供應資料和/或監控資源使用情形。

3.完成階段。處理完成之結果可能是無作用、新增另一執行緒、發出同步化基元或新增執行緒與同步化基元之組合。此外，該控制器客戶端120可能也需要設定或更新調度程式度量資訊(scheduler metrics)及終止執行緒。在該執行緒執行期間，此事件需要額外之記憶體以儲存結果，該控制器客戶端120亦需執行此方法。

當一特有的個別硬體控制器客戶端120在其作用時期，佔用所有可用系統連接介面160之頻寬，則一最佳化之解決方案可讓一控制器客戶端120b作為複數硬體處理資源150之代理程式。此配置方式如第7B圖所示。如前例，該代理控制器客戶端120b係以中斷驅動(interrupt driven)，然而，於前例中，僅有一來自於該控制器130之中斷會被繞送，但在代理控制器客戶端之模式中，每一處理資源150皆有一中斷。根據從控制器130所接收之中斷索引，代理控制器客戶端120b在所識別之處理資源150上執行相同的步驟。在代理控制器客戶端之模式中，由於需要系統連接介面160之使用管理，一硬體配接器120c會保持在處理資源150及系統連接介面160之間。

如前所述，控制器客戶端120可在軟體中實施。此案例中控制器客戶端120之某些功能，如共享資源使用管理，典型而言將使用已於處理資源150硬體中存在之硬體元件(如：記憶體管理單元(MMU))。

因此，軟體控制器客戶端120之架構及實施例係特定之處理資源150。

硬體控制器客戶端120亦可能依據相關處理資源150之特性，而有專業的需求。以下即描述適用於大部分情形下之一般性架構。

硬體控制器客戶端之一般性實施例

硬體控制器客戶端120之基本結構如第8圖所示。該設計之中心為控制器客戶端之有限狀態機(Finite State Machine，簡稱FSM)500。有限狀態機500可能在三個階段皆可運作。控制器客戶端FSM 500係由該控制器130之中斷 221所啟動。

首先，控制器客戶端FSM 500掌控系統連接介面160，以從共享記憶體資源140讀取TCB，該TCB包含對其本身指令之索引。在設定階段之期間，該控制器客戶端120可掌控處理資源介面、解譯組態指令並將其轉換為發送至處理資源150之寫入過程(write cycles)。此外，該控制器客戶端120會設定其自身之資源管理。從設定狀態轉換至執行狀態需要特定處理資源150，但該過程可能由一明確之執行基元，或僅由一進入一資料轉換狀態之項目所標記。

從一控制器客戶端120之觀點，最簡易之架構在於處理資源150及系統端皆具有相同之介面協定。在此情況下，於執行階段期間，處理資源150的讀取及寫入過程只不過是對映至該系統介面，並檢查何處是適合對映之處。

該最簡易控制器客戶端120實施例在系統至處理資源510及處理資源至系統520之路徑，皆需一先進先出(FIFO)類型之介面。在此種控制器客戶端執行階段期間，利用訊息或資料流模式(message or streaming modes)，可將資料提供給處理資源150。在訊息模式下，整個資料集在處理前，會於控制器客戶端120內局部性地累積，而此模式會引起一較粗糙不均的互連狀態，使得需要更複雜的互連仲裁器(arbiters)。在資料流模式下，資料會直接從系統記憶體進入該處理資源150，此為一更有矽效率之解決方案，該方案必須更仔細的考慮信號交換(hand-shaking)和展現精細的互連交易以及與連結效能的緊密結合。

藉由測量提供至處理資源150之資料，或由處理資源150本身所明確發出的信號，可推斷出由執行階段轉變至完成階段。在完成階段期間，該控制器客戶端120再次執行由原始執行緒控制區塊所提供之指令集。

在某些情況下，可將進入處理資源150之資料路徑(如：輸入/輸出裝置)與從處理資源150輸出的資料路徑視為相異。相對而言，在某些情況下(如DSP之演算法加速器)，則會自然的在同樣的控制器客戶端120架構內連接消費者和資料製造者。

為了提供處理資源150及其他系統資源間之去耦(decoupling)層級，客戶端控制器120可提供許多額外之功能：

a)藉基址(base address)和偏移規定(offset definition)所定義之預期方式，利用一比較器(comparator)530和一比較位址暫存器540，可檢驗處理資源150所產生之位址。

b)利用一減法器550和偏移位址暫存器560，可將處理資源150所產生之位址偏移(offset)，讓處理資源150對任何特定執行緒能有一正規化的位址對映視圖，典型為正規化循環位址(normalised around address)0x0。

物件

系統管理控制器130中所使用的資料類型執行個體分為公共(可從整個系統見到及控制)及私用可見性(僅可在系統管理控制器130內見到，且僅可由系統管理控制器130 子區塊控制)。為確保多個終端應用程式設計之可攜性(portability)，所有執行緒、佇列及聚合佇列描述符，利用一通用基礎類別(common base class)，即控制器記憶體元件195，儲存在專屬緊密耦合記憶體190內。

控制器記憶體元件

每一控制器記憶體元件195可能表示七種描述符類型之任一種：

1.空閒資源表元件(Free List Element)。此元件可讓其他描述符類型使用，不需使用者初始化或執行期間之操作。

2.執行緒描述符(Thread descriptor，簡稱TD)。此為表示應用程式/作業系統執行緒之資料結構。此描述符可存在於專屬緊密耦合記憶體190內之未決佇列、就緒佇列或分配佇列之中。其不需使用者初始化，但需要執行期間之操作。

3.調度程式根描述符(Scheduler Root Descriptor，簡稱SRD)。此為調度程式層級之最上層描述符。其需要使用者初始化，但不需執行期間之操作。該根描述符無父代，但其子代可為SSTD、DSTD或TD之任一種。

4.靜態調度程式層級描述符(Static Scheduler Tier Descriptor，簡稱SSTD)。此為一靜態調度程式層級之描述符，其父代可能為SRD或另一SSTD。該SSTD之子代可為SSTD、DSTD或TD之任一種。

5.動態調度程式層級描述符號(Dynamic Scheduler Tier Descriptor，簡稱DSTD)。此為一動態調度程式層級之描述符。其不需使用者之初始化，但需要執行期間之操作。DSTS之父代可能為SRD或SSTD，但DSTD之子代僅可為TD。

6.分配佇列描述符(Dispatch Queue Descriptor)。此類型之描述符描述一執行緒描述符列表，該執行緒描述符會等候相關處理資源150之提取作業。其需要使用者之初始化，但不需執行期間之操作。

7.未決佇列描述符(Pending Queue Descriptor)。此類型之描述符描述一執行緒描述符列表，該執行緒描述符會等候一同步事件。其需要使用者之初始化，但不需執行期間之操作。

這些描述符將於後文詳述。

各種控制器記憶體元件195形式分別於第9a至9l圖顯示。

執行緒表示法(Thread representation)

當一描述符需要初始化或執行期間之操作時，則透過該控制器130API完成作業。該集中化之工作分配和管理系統會被仔細的設計，以確保能在一硬體實施例上合適/簡單的進行即時交易。

第10圖顯示執行緒描述符、系統管理控制器130、處理資源150及共享系統記憶體140間之典型關係。每一執行緒基元包含唯一之索引一pReference。此索引非由系統管理控制器130轉譯或修改。pReference提供一指向系統記憶體140內資料結構之指標，決定欲執行之工作。典型而言，此為控制器客戶端控制區塊125，並至少包含下列元件：一功能指標(如第10圖中所顯示之處理資源指令區塊145)、一堆疊指標及一引數指標(Argument Pointer)(如第10圖中所顯示之資料區塊135)。當然也可能決定其他提供共享系統資源參數設定(in-band configuration)或安全性之欄位(fields)。

然而，根據應用程式和/或目標處理資源150，控制器客戶端控制區塊125之複雜度可能相當多樣。特定言之，給定合適的「控制(control)」指令碼及相對應之「資料路徑(datapath)」碼，在特定之情況下，包含額外的間接層(levels of indirection)可讓不同的處理資源150在相同資料上執行相同之功能。

第11圖顯示一實施例，其中一排程層級負載可平衡橫跨兩相異(第11圖中之類型I及類型II)處理資源150a及150b之工作。該pReference欄位(位於執行緒描述符內，該描述符依序進入該層級中)索引一控制器客戶端控制區塊125，此外還有每一類型處理資源之指標，其會對應至每一相異指令集所要求之特定指令流。控制器客戶端120可根據控制器客戶端控制區塊125中之旗標，選擇適當之指令流(指令區塊145a或145b)。

舉例而言，在某些處理資源的省電(power-down)功能中，此特性便相當有用。在此例中，對一特定之工作而言，最佳化的處理器會暫時停止運作，而次佳的處理器則會執行該工作以避免高成本的重新開機程序。

此外，舉例而言，在異常負載下，可啟用一輕負載之一般目的處理器以減輕一DSP的高度負載。

當一處理資源150已就緒分配給執行緒時，其會自與該處理資源150唯一關聯之合適分配佇列取出。該取出作業會回傳一物件，該物件包含pReference、導致該排程事件之調度程式指標和一旗標集合，該旗標集合包含該執行緒是否因逾時或一同步化基元而已就緒之指示。該用於執行緒描述符之控制器記憶體元件195會自動返回空閒資源表，以待將來執行緒描述符之使用。

公用物件

此處說明系統透過控制器130API可見之物件。典型而言，這些物件係由集中式工作分配及管理系統(至少包含控制器130與客戶端120及與其相關之處理資源)於執行時期管控。

執行時期控制器130API，讓應用程式得以引入新執行緒、引入新動態調度程式元件、發出同步化基元、提取已排程執行緒、推入先佔執行緒(pre-empted thread)或移除執行緒。

第12圖顯示系統管理控制器130中執行緒管理之典型概況。

執行緒基元(Thread Primitives)

執行緒基元之格式如第9c圖及第9d圖所示。根據其相依性(dependency)，一執行緒描述符可置於未決佇列結構或直接置入就緒佇列結構中。若一執行緒要被放置於未決佇列結構中，則該應用程式必須定義該執行緒之相依性。依賴一外部事件表示將其本身視為一相依性索引。該控制器130並不會轉譯此相依性索引；其會繼續保持以比較進入之同步化基元，以決定何時該將執行緒描述符轉換至就緒佇列架構。

相依執行緒可能會被指定何時逾時，結合無效相依性索引，即可作為執行緒硬體時序之用。無論該相依性索引如何，逾時功能會讓該執行緒在一特定時間點排程。

執行緒會依據能讓其進入就緒佇列結構之同步化事件(計時器或基元)而被標記(tagged)。

同步化基元(Synchronisation Primitives)

同步化基元會與未決佇列溝通，並使一或多個執行緒描述符自未決佇列結構轉移至就緒佇列結構。

每一同步化基元包含唯一索引，其用以與相依索引相比較，該相依索引儲存於已識別未決佇列內之每一執行緒描述符中。該比較會依照執行緒基元所標明之優先權持續進行。

根據其類型，同步化可喚起符合最高優先權之執行緒描述符，或未決佇列中所有相符之執行緒描述符。此外，一特殊之廣播基元可喚起所有未決佇列內相符之執行緒描述符。

中斷處理

一中斷服務執行緒(Interrupt Service Thread，簡稱IST)之方法提供一有用的手段，即將非同步事件施加在處理資源150上之負擔最小化。此外，根據本發明，系統中之快速即時回應可讓系統僅小幅修正，即可讓ISTs更為廣泛地使用。

該控制器130可從控制器周邊之外部中斷輸入210，自動產生同步化基元。未決佇列內預先設定之中斷服務執行緒描述符，將會在接收這些中斷同步化基元後，進入就緒佇列結構。

應用程式通常於系統初始化時，設定與外部中斷210相關之執行緒描述符，並於相關中斷服務執行緒執行時再次設定。

此功能有效地去除系統內任何其他專屬中斷服務處理資源150之需求。此外，其透過同樣的優先性結構並根據使用於所有處理器工作之相同策略，處理這些外部中斷210，如此可避免在已執行更高優先權工作的處理資源內，進行控制程式轉換。任意數量之巢狀中斷係由利用一般先佔常式(pre-emption routines)將目前正執行的執行緒推回就緒佇列之能力所維持。

計時器類型之中斷(監視程式及週期性事件)係以類似之方法管理。計時器類型之工作(週期性或一次性)必需加入至計時器佇列，並以對具有逾時相依性(timeout dependency)之執行緒所採取之相類似方法管理。經由設計，此方法可避免無有益處理需求之時間例外(time based exceptions)。

為達到更快的回應時間，可設定中斷優先權，使中斷常式先佔目前正執行之工作。

私用物件

私用物件典型於開機時(即在停機過程後，系統初始化期間)設定。處理資源150極少於執行時期間直接與內部物件進行溝通。

內部物件主要為佇列結構。系統管理控制器130掌管四種主要類型之佇列：未決佇列、計時器佇列、就緒佇列及分配佇列。

其他次要佇列存在於系統管理控制器130內，以協助內部之運作。佇列間執行緒描述符的移動，僅會伴隨指標操作發生，而執行緒描述符無法被複製。

未決佇列結構

執行緒可自一未決佇列結構，透過一同步化事件或一計時器事件，進入至就緒佇列結構。此兩種方式可能對一執行緒皆有用，或是這些類型之事件僅有其中一種對其有用。在兩種方式對執行緒皆有用之情形下，執行緒會出現在未決佇列及計時器佇列兩者中。

未決佇列內含有等候一同步化事件之相依執行緒。執行緒透過一來自處理資源150之同步化基元，或由時序管理器360於內部產生之計時器事件，而從這些結構中移除。應用程式設計者使用可設定數量之未決佇列，支援多重爭用範圍(multiple contention scopes)及中斷服務執行緒；而每一未決佇列中之元件需根據其優先權處理。根據優先權處理有兩種方式：插入時排序(sort on insertion)和取出時排序(sort on extraction)。插入時排序的方法會定義一處理程序，在此程序中，一等候列表係以嚴格的優先權儲存，且新執行緒係根據其優先權插入列表中之某一位置。取出時排序之方法則是任意選擇插入一新執行緒之位置，並將有資格的執行緒描述符在同步化後執行優先權排序。本發明之較佳實施例使用插入時排序技術。

第13圖顯示一未決佇列之典型架構。每一項目皆以嚴格之優先權儲存。插入一新執行緒之速度可利用略過列表加快，而第14圖顯示一典型之未決佇列略過列表。

如前所述，執行緒可能被限制等候同步化或計時器事件。某些執行緒會專屬等候一同步化事件，同樣地，某些執行緒會專屬等候一計時器事件。在每一種情形下，該執行緒僅會於單一佇列中出現。每一執行緒包含兩組指標，通常皆與未決及計時器佇列相關聯。在這些情況之下，已提供給計時器佇列與未決佇列之指標是多餘的。略過列表可利用這些多餘的指標，舉例而言，若計時器佇列沒有執行緒，則這些指標可重新使用以顯示在未決佇列中可能的預先跳躍(jump)。如此，當為了一新的相依執行緒而不斷接近一正確的插入點的同時，可讓一不同之循序檢索跳過執行緒描述符區塊。

另一選擇為略過節點描述符(skip node descriptor)，其實施例如第9k圖所示，相關欄位則如第9l圖所示。該略過節點描述符可根據一預先定義之指標，週期性的插入未決與計時器佇列結構。略過節點描述符根據執行緒描述符之定義最大觀察數目(a defined maximum observed number)，插入至略過節點描述符或已參與執行緒描述符 (participating thread descriptors)之間。略過節點描述符可同時形成一未決佇列和一計時器佇列列表之一部份。

每一新相依執行緒必須根據其優先權插入。典型而言，該程序會從檢視該略過列表開始，直到該新執行緒的優先權高於略過列表節點之優先權。之後，該檢索會從該略過列表節點，在一執行緒描述符上以執行緒描述符之基準持續進行，直到發現正確之插入點。如此，當對一新相依執行緒尋找正確插入點時，可讓另一線性檢索略過未決執行緒之區塊。

同步化事件具有三種不同類型：

單點播送(Unicast)：該同步化事件在指定之未決佇列中所發現的第一(最高優先權)合適相依執行緒上觸發一狀態轉換。

多點播送(Multicast)：該同步化事件在指定之未決佇列中所發現的所有合適相依執行緒上觸發狀態轉換。

廣播(Broadcast)：該同步化事件在所有未決佇列中所發現的所有合適相依執行緒上觸發狀態轉換。

未決佇列由未決佇列描述符定義，如第9i和9j圖所示。未決佇列描述符在系統初始化期間會被設定一次，並且其佔用一控制器記憶體元件195。未決佇列只包含相依執行緒描述符和略過列表節點。

計時器佇列結構

一個別之泛系統計時器佇列會儲存等候一逾時事件之執行緒描述符。第15圖顯示一例示之計時器佇列實施例。

如前所述，亦可利用略過列表以加快執行緒插入至計時器佇列結構。然而，在此例中因略過列表而被使用之執行緒僅有短暫的相依性(若有的話)。

計時器佇列描述符儲存在暫存器內，如此讓計時器佇列的頭與目前時間能在同一時間進行比較，從而大大減少了計時器時間記號(timer tick)對於記憶體頻寬的衝擊。

就緒佇列結構

就緒佇列結構中包含已就緒執行之執行緒。這些執行緒係以獨立執行緒基元建立，或其為相依執行緒，則已接收到同步化基元。同步化之執行緒已事先從未決佇列結構轉換。

該就緒佇列結構可包含調度程式節點描述符，以及獨立和同步執行緒描述符。雖然執行緒描述符及動態調度程式階層描述符號可即時變化，但該結構大部分於系統初始化期間定義。

就緒佇列可將執行緒排程至一特定處理資源150，或一處理資源150集中區(pool)。在維持將特定工作對應至特定處理資源150(如：硬體加速器或輸出輸入裝置)之能力時，此方法可讓多處理資源150間之負載平衡。

第16圖顯示一典型之雙處理資源150就緒佇列結構。需注意兩個根調度程式階層皆可使用動態調度程式階層2。如此可讓系統管理控制器130載入位於根階層1及2相關聯處理資源150間之動態階層2下的平衡執行緒(balance threads)。

調度程式階層(Scheduler Tiers)

調度程式階層會定義用以排程執行緒描述符之層級(hierarchy)。每一調度程式階層典型而言會定義一排程演算法、一些用以決定排程決策之標準及子元件列表，該子元件可能是另一調度程式階層或執行緒描述符。有三種類型之調度程式階層描述符：根、靜態及動態。調度程式階層記憶體元件之格式如第9e圖及第9f圖所示。

根調度程式描述符與分配佇列有一對一的對映，他們表示就緒佇列結構中的終端節點(ultimate node)。調度程式根描述符於系統初始化時設定，且會一直存在。

靜態調度程式描述符存在於排程層級中之根節點下。靜態調度程式描述符之父代可為其他靜態調度程式描述符或根描述符，它們根據其父代所定義之調度程式演算法及其調度程式度量資訊(scheduler metrics)，與同層節點競爭。靜態調度程式描述符於系統初始化時設定，且會一直存在。於作業期間，該系統管理控制器130會根據所選擇之排程演算法(例如：依序循環排程(Round Robin scheduling))，維護調度程式度量資訊。

動態調度程式描述符存在於排程層級中之根節點下，並可能存在於靜態節點下。動態調度程式描述符之父代可為靜態調度程式描述符或根描述符，它們根據其父代所定義之調度程式演算法及其調度程式度量資訊，與同層節點競爭。動態調度程式描述符可於任何時間設定，且可於特定情形下被撤回。如此讓該系統所能支援的排程階層數量遠高於單純靜態所能提供之數；雖然在整個期間會利用到非常多數而多樣的執行緒和動態調度程式階層，但在有限的期間內，暫時性的需求較小，所以系統管理控制器130就利用這樣的可能性而達到上述目的。舉例而言，在一具有最多可支援4000個動態元件(執行緒和動態調度程式描述符)之記憶體的網路系統中，可能可以支援16000個即時連線，但在整體連線空間(connection space)中，只有其中一小部份的資料單位(dataunits)會駐留在該控制器中。為達到此彈性，必須損失一小部分的效能，因為若一動態調度程式描述符並未出現，則其必須在增加子執行緒描述符前產生。

於作業期間，系統管理控制器130可根據所選定之排程演算法，維護調度程式度量資訊。在某些特定情形下，動態調度程式描述符可被釋回至控制器記憶體元件195之空閒資源表，此係藉由儲存最後執行緒之pReference達成，該最後執行緒會在動態調度程式階層描述符內之階層內處理。該控制器130API支援控制器記憶體元件195之詢問(interrogation)功能，以確定一動態調度程式描述符是否持續在隨後之相似執行緒之間。

分配佇列(Dispatch Queues)

分配佇列將排程執行緒描述符放入一先進先出(FIFO)佇列，等候相關處理資源150之服務。於目前之較佳實施例中，最多可允許32個分配佇列。分配佇列係由分配佇列描述符所定義，如第9g圖及第9h圖所示。分配佇列描述符於系統初始化期間設定。

一執行緒描述符從一就緒佇列結構轉移至分配佇列結構之過程係於硬體中執行，且不需使用控制器130API進行溝通。

第17圖顯示一實施本發明特徵之典型單一分配佇列結構實施例。該分配佇列描述符定義一完整門檻值(full threshold)。在一分配佇列中，一執行緒束(thread bundle)正被排程或一先佔執行緒正推入(push)其中，該分配佇列之長度必須超過該完整門檻值。

一處理資源藉由控制器130API所呼叫之提取(pop)作業，將元件從該分配佇列移除。

分配佇列描述符包含一優先權欄位。當一執行緒從分配佇列中提取出來時，該優先權欄位將存入目前正執行的執行緒之優先權。為了避免優先權反轉(priority inversions)，一更進一步之API呼叫讓該正執行之處理器能重新設定優先權。優先權反轉涉及至少3個不同優先權的執行緒，且表示在同步化和排程需求間產生衝突。優先權反轉會讓一較低優先權之執行緒無限期的阻檔一較高優先權之執行緒。舉例而言，一低優先權執行緒鎖住一共享資源，之後一較高優先權執行緒先佔該低優先權執行緒，接著，該較高優先權執行緒會攔阻該低優先權執行緒所鎖住之資源。一般而言，若非與該被鎖住資源無關且目前可任意執行之第三方中間執行緒，該低優先權執行緒會繼續鎖住，因此，該低優先權執行緒毫無機會釋放該共享資源，而該高優先權執行緒則會被無限期的阻擋。「優先權限高(Priority ceiling)」協定表示當一執行緒擁有一共享資源時，其以一特定之優先權執行。如此當上述之「低」優先權執行緒擁有與該高優先權執行緒共享之資源時，能被擬制具有「高」優先權。

執行緒束描述一執行緒描述符群組，該執行緒描述符源於相同之調度程式階層。每一調度程式描述符皆有一參數，以定義執行緒之數目，該執行緒在排程決策被迫更新前，可能從就緒佇列之階層轉換至分配佇列。藉由此功能，及安排調度程式階層分享共用之成員，該處理資源150會被賦予多個展現高度局部性快取的執行緒區塊，如此可減少快取漏失(cache-misses)並增加系統效能。

根據本發明一實施例，第18圖顯示一例示之雙階層排程層級(hierarchy)，其包含執行緒束。該子階層最遠來自根階層，並使用一FIFO排程演算法。該根階層調度程式演算法為依序循環法(round robin)。在該實施例中，每一FIFO佇列中之元件顯示與相同佇列其他成員之高度局部性快取。

第18圖(a)顯示子階層執行緒束限制在1的排程結果，其完全交錯配置。此方式讓每一佇列都能有最小延遲；然而，此法卻最不考量記憶體(即很有可能展現較差的快取效能)。在每一排程執行緒後都需要進行控制程式轉換(context switches)。如果該根階層與一使用快取之處理\資源150相關聯，則強制性的快取漏失(compulsory cache misses)可能會影響系統效能。

第18圖(b)顯示子階層執行緒束限制在4的排程結果。該調度程式展示一較粗糙的更新特徵，其顯示出多個正排程的執行緒區塊，這些執行緒區塊來自相同佇列，並具有一由該執行緒束所限制之有限集合。雖然此集送式(bursty)的方式在某些情況下並不理想，但其展現極佳之快取效能，幾乎不需進行控制程式轉換。這樣的效果可模擬當維護該精密方法之高級程式化模型時，一粗糙多執行緒的優良快取績效。

當該系統與外界互動時，執行緒束的集送特性會非常不受歡迎。而執行緒束僅在目標處理資源150使用快取時才會產生效益，因此與外界互動之專門處理資源150，如IO裝置，因不可能使用快取技術，所以不會使用執行緒束。

回到第17圖，一處理資源150藉由控制器130API所呼叫之提取作業移除元件。元件可能在先佔的事件中會被推回到就緒佇列。

分配佇列描述符中包含一優先權欄位，使之能實施優先權限高協定，以避免因共享資料被鎖住產生優先權反轉。每一處理資源150具有唯一的分配佇列。

排程(Scheduling)

應用程式及系統之排程需求相當多樣，實際上只有在真實作業環境中測試後才可能變得清楚。因此，系統管理控制器130在排程策略及排程演算法保持彈性，這些策略及演算法在多核心處理器之設計階段中，都可加以修改或調整。

排程策略可分成三種類型：

1.一協同調度程式根據目前正執行之工作，在排程一新工作前釋放該處理資源150。雖然此類型之系統，能讓冷快取效應(例如，處理資源150附近之快取並未包含所需的指令，必須從一較低或較高階層之記憶體載入缺少的指令)及固定功能硬體加速器之數量降至最低，但其並不適用於更複雜的內嵌式應用程式。

2.為執行更合適之工作，一靜態演算法驅動調度程式(static algorithm-driven scheduler)可先佔目前正執行之工作。根據預先定義之排程參數及演算法，最合適之執行緒永遠是此系統中正執行的執行緒。任何確定工作之合適性在系統開始執行前即已固定。

3.一動態演算法驅動調度程式可於執行時期重新定義合適性。如前所述，目前正執行之程序仍具有最高的合適性，但合適性之標準會因工作開始執行而改變。系統管理控制器130經由適當的組態設定，及執行時期與目標應用程式之互動，提供此三種排程策略。

系統管理控制器130支援許多於作業系統及通訊社群中所見之排程演算法。例如：先進先出排程法、優先權排程法或加權公平排程法(weighted fair queuing)。選擇適當排程演算法有許多好處，尤其是牽涉到主觀品質標準。

執行緒描述號中提供兩種調度程式之度量資訊，以支援系統管理控制器130中之排程行為。第1種表示該執行緒在所有情況下的優先權，且用在未決佇列結構、優先權調度程式和分配佇列結構中。如果需要的話，第二種用以在個別執行緒及其同位體間作選擇。此外，任一種可用以更新父代描述符中的度量資訊。位於一執行緒描述符第二基元中之數值必須反映出在該執行緒描述符所在之調度程式層級中所面臨之排程類型。

這兩種調度程式度量資訊係用在調度程式描述符與執行緒描述符中。然而，雖然執行緒度量資訊於處理資源150內計算，卻無法在調度程式階層內計算。因此，必須有足夠的參數從一特定階層的排程執行緒傳出，讓該調度程式階層能更新其度量資訊。每一調度程式階層都會有一組指令定義度量資訊如何從子代傳至父代。

只要檢視整體調度程式層級，即可輕易產生複雜的調度程式演算法組合，以在應用系統中提供良好的流量和工作管理能力。

參數繼承實施例(Parameter Inheritance Example)

第19圖顯示一例示之簡化佇列結構，該結構通常可於一通訊系統中發現。該結構表示一IO裝置的輸出佇列。所有分享一FIFO佇列之執行緒都在同一連結，所以此為每一連線排程結構(per connection queuing structure)。在此實施例中，第二排程階層利用一加權公平排程法(WFQ)演算法。此演算法根據一確定工作之長度與加權因子，計算該工作之完成時間，然後選擇具有最早完成時間的封包(packet)。雖然WFQ需仰賴對該執行緒所表示之封包長度的瞭解，但初始FIFO佇列並不需此資訊。在此例中，應用程式設計人員必須確定該封包的長度出現在每一執行緒之調度程式度量資訊中。層級中較高的調度程式階層會繼承此一用在其所擁有排程演算法之參數。

WFQ需要下列變數：P - 分配給該連線之管道頻寬比例L - 封包之長度B - 全部管道頻寬C - 連線頻寬D - 調度程式階層截止期限

計算連線頻寬c之方程式為：P*B=c 若我們將通道之頻寬設為1，則P等於c。

封包處理的完成時間t為：接著需取得1/p和l。由於p原本即為分數，因此此兩數值(1/p及l)皆為整數。已排程之封包長度會由調度程式層級扣掉，以逐步更新該層級的截止期限。總之，每一次更新需計算：其中d和1/p(權值)儲存在調度程式層級描述符之中，而在一排程更新期間，會透過該層級傳送l。調度程式管理器330會執行此計算。

雖然已描述本發明之一特定實施例，但習知技藝者皆明瞭此僅為例示，可對其作各種修正。此外，任何裝置的一般性應用或利用一多核心處理器之應用皆可運用本發明，例如：行動電話或網際網路語音協定(VoIP)，但不僅限於此。因此，特定實施例並不得視為限制本發明範圍，實際保護範圍仍由申請專利範圍決定。

10‧‧‧架構