用於在消息之間進行仲裁的數據處理裝置和方法

2023-06-10 23:45:56 1

專利名稱：用於在消息之間進行仲裁的數據處理裝置和方法
技術領域：
本發明涉及用於在通過通信信道路由(route)的消息之間進行仲裁 的數據處理裝置和方法，特別是涉及用於通過在多個處理元件之間共 享的通信信道路由的消息之間進行仲裁的數據處理裝置和方法。
背景技術：
存在多個處理元件之中共享通信信道的許多系統，其中的各個處 理元件通過通信信道向接收元件發出消息。通信信道可採取用於將多 個主裝置與晶片中的多個從裝置、如晶片上系統(SoC)裝置連接、或者 連接多晶片模塊中的各個晶片或者實際上互連印刷電路板結構中的各 個^^莫塊的總線互連電路的形式。在更大規才莫上，通信信道可通過互連 多個計算機的網絡或者用於互連多個裝置的共享無線電鏈路來構成。對於任何通信信道，存在對那個信道的信息承載(carry)容量的限 制，並且還存在與通信信道相關聯的等待時間。存在使信道容量和等 待時間能夠改變的體系結構選擇，例如使用並行化技術和增加的工作 頻率。但是，這類技術具有複雜度、功率和區域方面的費用，它們需 要對於所需性能進行折衷。在通信信道在多個處理元件之間共享的任何系統中，其中那些處 理元件需要在運行進程時通過通信信道發出消息，通信信道神皮共享的 事實迫使進行關於通過通信信道處理消息的順序的判定，並且這個判 定通過使用仲裁技術來進行。考慮SoC的實例，消息可採取主裝置在 事務期間發出的信號的形式，具體來說，主裝置通常通過將指定與事 務關聯的從裝置的訪問請求發布到通信信道上，來發起事務。在這個 特定領域中已知的是，事務的某種排序產生比其它排序更低的總等待時間，這是裝置、如存儲控制器通常專用的區域。但是，仲裁判定必 然增加其消息因仲裁判定而被阻止的進程所遇到的等待時間。因此，進行這個仲裁判定的方式對系統的整體性能具有顯著影響。基本仲裁方案使用採取固定優先級或循環(公平共享)技術的算法。這類方案限制到逐個消息進行仲裁判定，並且有限地考慮以前進 行的選擇。循環方案的例外情況是當前優先級取決於先前的優先級。 但是，兩種方案都遇到問題它們基於逐個消息而不是在發出消息的 各個進程之間分配通過通信信道所產生的附加等待時間。因此，在通 信信道中具有高訪問等級的消息因通信信道中進行的仲裁判定而經歷 高等級的附加等待時間。主要為網絡開發的備選技術是服務質量(QoS)技術，它通過設法確保進程具有所需帶寬和可控等待時間特性來進行基於時間的觀測。因此，這類QoS方案考慮每個進程，並將通信信道的一部分帶寬分配給 那個進程，其中具有對施加到各事務或消息的等待時間的某種控制。 但是，已知QoS方案的限制在於，每個進程的特性被假定為在運行那 些進程時發生的實際數據流量之前是已知的，並且還需要某種高級協 議來管理那種信息。因此，這類QoS方案對於帶寬和等待時間特性的 變化是不靈活的，需要預先知道這些特徵，並且需要高級協議來配置 通信信道的操作以便向進程提供必要的特性。因此，現有QoS方案以 通信信道提供性能的假設開始，並按照來自進程的預定要求來分配這 個性能。這可能使具有比預計更低的帶寬要求的進程得到不公平性能， 而超過其預定特性的其它進程則缺乏性能。雖然這些已知QoS方案的一部分可在網絡環境中的工作是可接受 的，但是，在其它類型的系統、如SoC中，通過共享通信信道發生的 數據流量可能是隨機的(例如從高速緩存未命中等產生)並且動態可變 的，因此不適合於現有QoS方案。因此，希望提供一種用於在通過共享通信信道路由的消息之間進 行仲裁的改進技術。發明內容從第 一方面來看，本發明提供一種用於在通過通信信道路由的消息之間進行仲裁的數據處理裝置，包括多個處理元件，各處理元件 用於運行需要向接收元件發出消息的進程；在多個處理元件之間共享 的通信信道，通過所述信道路由消息；仲裁電路，用於執行在通過通 信信道路由的多個消息之間進行仲裁的仲裁過程；各處理元件設置成 發出在那個處理元件上運行的進程的進度(progress)數據，進度數據指 示進程的等待時間暗示(implication);以及仲裁控制電路，響應來自各 處理元件的進度數據，在考慮了進度數據所指示的各進程的等待時間 暗示的情況下執行優先級排序過程，以便生成優先級排序數據，並將 優先級排序數據輸出到仲裁電路，以便控制仲裁過程。根據本發明，每個處理元件設置成發出在那個處理元件上運行的 進程的進度數據，其中的進度數據指示該進程的等待時間暗示。最後， 當等待時間增加到特定等級時，將導致進程停止(stall),但這不會立即 發生，因為可存在充分的緩衝或者可首先運行的其它計算。另外，停 止對進程的影響根據那個進程而改變，在一些情況下可能是災難性的， 而對於其它進程，停止的影響可能不那麼重要，並且可能只是延長完 成進程所需的時間。因此，大家會理解，等待時間的暗示根據進程而 改變，因此，相對於各運行進程發出的進度數據指示那個進程特定的 等待時間暗示。此外，根據本發明提供仲裁控制電路，它響應來自各處理元件的 進度數據而在考慮了進度數據所指示的等待時間暗示的情況下執行優 先級排序過程。由於這個過程，生成優先級排序數據，以及這個優先 級排序數據輸出到數據處理裝置所提供的仲裁電路，以便控制那個仲 裁電路所執行的仲裁過程。仲裁電路的設置取決於通信信道的結構。在通信信道中通常存在 需要執行仲裁的多個點，因此，仲裁電路分布於通信信道，以便使仲 裁能夠在那些點的每一個上執行。在每個這樣的點上，仲裁控制電路 輸出的優先級排序數據用於在通信信道的那個點上出現的多個消息之間進行仲裁。通過利用本發明，可在考慮了各個進程的要求時執行仲裁，因此採用QoS樣式的仲裁，但與已知QoS方案相反，該QoS在進程之間 自動確定和分配，因而消除了預先知道這些要求的需要。另外，本發 明的QoS機制動態適合於進程之間的通信的變化。具體來說，當來自 各個進程的進度數據改變時，這將影響仲裁控制電路所產生的優先級 排序數據，它轉而影響數據處理裝置的仲裁電路所執行的仲裁。共享通信信道的處理元件可採取各種形式。但是，在一個實施例 中，每個處理元件是連接到通信信道的主裝置。通過通信信道向接收 元件發送消息的裝置通常是從裝置，以及各個事務由主裝置在其中運 行進程時發出，以便使多個讀或寫傳輸在主裝置與從裝置之間經由通 信信道發生。在這類實施例中，每個消息可採取主裝置之一發出的訪 問請求以便發起事務的形式。但是，消息的準確形式取決於通信信道 上使用的協議。對於例如ARM Limited(Cambridge， United Kingdom)開 發的AXI(高級可擴展接口)協議等總線協議，讀和寫數據構成事務所 指定的地址轉換(transfer)中描述的消息的一部分，而在分包系統中， 請求和數據可構成組成消息的單個分組的 一部分。各個處理元件運行的各個進程可採取各種形式。但是，在一個實 施例中，各進程是程序線程，以及各處理元件運行單個程序線程。在 這類實施例中，逐個線程地提供進度數據。在一個備選實施例中，至少一個處理元件包括多個處理單元，其 中各處理單元運行一個程序線程。在這個實施例中，處理元件是多核 處理器，以及進度數據對其發出的"進程"由那個處理元件的各個處 理單元上運行的所有各種程序線程組成。配置這樣一種多核處理器的 另 一種方式是將多核處理器中的各個處理單元設置成分別^皮看作處理 元件，使得多核處理器中的各處理單元輸出它自己的、與那個處理單 元上運行的程序線程相關的進度數據。數據處理裝置可採取各種形式，但在一個實施例中採取SoC的形 式。本發明的技術在SoC裝置中極為有益，因為通過通信信道發生的各種數據流可能是隨機並且動態可變的。當各種進程的要求改變時， 本發明的實施例的技術足夠靈活地管理各種進程的帶寬和等待時間。進度數據可採取各種形式。在一個實施例中，進度數據確定關聯 進程是實時進程還是非實時進程，對於實時進程，進度數據還確定指示處理那個實時進程發出的消息剩餘的時間的至少 一個鬆弛(slack)值，對於非實時進程，進度數據還確定指示對於預定時間與那個進程 關聯的等待時間的至少 一個等待時間值。為了便於進行描述，實時進程可看作是停止對那個進程的影響邱皮 認為是災難性、因而是不可接受的任何進程。 一個實例可能是正生成 用於在屏幕上顯示的視頻的進程，其中，所顯示視頻的中斷可^皮認為 是不可接受的。相反，本申請的上下文中的非實時進程表示停止可能 是可接受的、因而停止的影響不是那麼重要但引起完成進程所需的時 間延長的任何進程。除了關於進程是實時進程還是非實時進程的指示 之外，對於實時進程，進度數據還確定指示用於處理那個實時進程發 出的消息剩餘的時間(在進程停止之前還有多少時間)的鬆弛值。相反， 對於非實時進程，進度數據還確定指示對於預定時間與那個進程關聯 的等待時間的至少 一個等待時間值。預定時間是可根據實現進行改變 的設計參數。預定時間越長，則在產生等待時間值時要考慮的歷史信 息量越大，而預定時間越短，則等待時間值更快地響應最近變化而改 變，因此，仲裁控制電路生成的優先級排序數據更快地應來自特定進 程的需求的最近變化。通過將上述信息結合到進度數據中，仲裁控制電路可確保充分優 先地考慮實時進程，以確保它們不會停止，但在與實時進程關聯的松 弛值允許的情況下，為了減小那個非實時進程遇到的等待時間，非實 時進程可優先於實時進程。通過將對於每個非實時進程所確定的等待 時間值設置成指示在預定時間上與那個進程相關聯的等待時間，這使 整體等待時間能夠在非實時進程之間公平分配。提供用於產生與每個非實時進程關聯的等待時間值的電路可採取 各種形式。例如，對於各進程，可保存帶符號二進位值，其中，負值指示可增加而不會停止進程的等待時間，而正值則計算已經對進程增加的等待時間。在對傳送(transfer)增加等待時間的每一個周期，這個 二進位計數器可遞增，以及當二進位值為正時，這指示線程已經停止。 這個停止時間則可在積分器中累計(因為積分器值隨時間變為無窮大， 可提供定期從所有積分器中減去某個值的機制)。因此，積分器輸出的 等待時間值提供關於可由仲裁控制電路在生成優先級排序數據時使用 的線程之間的停止時間的差異的信息。作為使用積分器的一個備選方 案，濾波器電路可與運行非實時進程的各處理元件相關聯，其中的濾 波器電路產生每個單位時間的等待時間的形式的等待時間值。因此， 在這類實施例中，簡單的低通濾波器可用來跟蹤累計停止時間，以及 來自各濾波器的輸出與平均停止率、即線程停止的周期數量對於形成 參考時間段的預定時間成正比。在一個實施例中，可公平處理所有非實時進程，其中，在進度數 據中包含的等待時間值用於設法在非實時進程之間均勻分配等待時間 的影響。但是，在一個備選實施例中，至少一個非實時進程具有與其 關聯的加權，並且在產生那個非實時進程的等待時間值時考慮那個加 權。每個這樣的進程的加權可在設計時固定，或者可能是可編程的， 但通常不會動態改變。在使用濾波器電路的實施例中，每個非實時進 程的加權可通過將不同的加權應用於這種濾波器電路所應用的濾波算 法來實現。因此，高加權可應用於某些非實時進程，而低加權則應用 於其它實時進程，使得在優先級排序過程由仲裁控制電路執行時，某 些非實時進程(即具有較高加權的非實時進程)可優選其它非實時進 程。作為一個實例，如果由於那個進程的停止而令音頻極偶然被中斷 是可接受的，則這可允許產生音頻流的進程被認為是非實時進程，但 是為了然後相對那個進程應用高加權，使得相對那個進程輸出的等待 時間值與其它較不重要的非實時進程相比更為迅速地增加，因而在仲 裁控制電路中執行優先級排序過程時，使那個音頻流進程優先於較低 優先級的非實時進程。在一個實施例中，數據處理裝置還包括與運行實時進程的各處理元件關聯的計數器電路，計數器電路產生所述鬆弛值。因此，在一個 實施例中，當消息由那個進程輸出(例如事務開始)時，計數器電路可 將計數器設置為特定值，其中，那個計數器值然後在每個時鐘周期遞 減，使得鬆弛值隨時間減小。當鬆弛值較高時，仲裁控制電路執行的 優先級排序過程可以使某些非實時進程優先於實時進程，但是，存在 ^^弛值下降到低於某個等級的點，使得優先級排序過程然後使實時進 程優先於這類非實時進程。在一個實施例中，對於非實時進程，進度數據還確定用於確定那 個進程是否停止的停止值。在一個具體實施例中，這可採取單個位值 的形式，其中， 一個值指示進程^皮停止，而另一個值則指示進程沒有 停止。在一個具體實施例中，這個停止值還可用作對用於產生等待時 間值的濾波器電路的輸入。在一個實施例中，對於非實時進程，進度數據還確定指示用於在 進程停止之前處理那個進程發出的消息剩餘的時間的鬆弛值。因此， 在非實時進程提前發起事務(即進程在需要那個事務的結果之前仍然 能夠繼續進行某個時間段)的情況下，鬆弛值可包含在進度數據中確定 進程停止之前剩餘的時間，並且這個信息可由仲裁控制電路在執行優 先級排序過程時進行考慮。優先級排序過程可通過各種方式來設置。但是，在一個實施例中， 如果某個實時進程的t〉弛值指示用於處理由那個實時進程發出的消息 剩餘的時間大於預定閾值，則優先級排序過程對非實時進程提供優先 於那個實時進程的優先級。因此，在實時進程的鬆弛允許時，非實時 進程可優先於實時進程，以便減少那些非實時進程遇到的等待時間， 並且沒有對實時進程的任何實際影響。在一個實施例中，優先級排序過程對具有較高等待時間值的非實 時進程提供比具有較低等待時間值的非實時進程高的優先級。因為這 些等待時間值指示在預定時間上與進程關聯的等待時間，所以這實現 對於非實時進程的等待時間的公平分配。在一個實施例中，對於具有不同停止值的兩個非實時進程，優先級排序過程比將優先級提供給具有較高等待時間值的進程更優先地將 優先級提供給停止值指示那個進程^皮停止的非實時進程。因此，這種 方法試圖減少停止任何非實時進程的時間。在一個實施例中，對於具有不同鬆弛值的兩個非實時進程，優先 級排序過程比將優先級提供給具有較高等待時間值的進程更優先地將 優先級提供給具有最小鬆弛的非實時進程。這種方法試圖在可能的情 況下降低非實時進程停止的可能性。雖然各處理元件所產生的進度數據的主要目標是使服務質量考慮 因素能夠由仲裁控制電路在執行優先級排序過程時進行考慮，但是還 發現，進度數據的一部分可在數據處理裝置的其它部分中再使用。例 如，已知的是提供一種數據處理裝置，其中具有能量管理電路來控制裝置的各種組件進行操作的性能等級(level)。這種數據處理裝置通常可在運行時在不同工作性能之間轉換。在運行輕工作負荷時選擇較低性 能等級，以便節省能量(功耗)，而對於處理更為密集的工作負荷則選 擇較高性能等級。當數據處理裝置中的處理元件通過互補金屬氧化物半導體(CMOS)技術來實現時，較低的性能等級表示較低的頻率和工作 電壓設定。在數據處理裝置包括這種能量管理電路的一個實施例中，能量管 理電路設置成在確定一個或多個處理元件的工作性能等級時，考慮那 些處理元件發出的進度數據的至少一部分。在一個具體實施例中，能 量管理電路考慮運行非實時進程的一個或多個處理元件輸出的等待時 間值。從第二方面來看，本發明提供一種在通過具有多個處理元件的數 據處理裝置的通信信道路由的消息之間進行仲裁的方法，其中各處理 元件運行需要向接收元件發出消息的進程，以及通信信道在多個處理 元件之間共享，消息通過通信信道路由，該方法包括/人各處理元件 發出在那個處理元件上運行的進程的進度數據，進度數據指示進程的 等待時間暗示；響應來自各處理元件的進度數據，在考慮了由進度數 據所指示的各進程的等待時間暗示的情況下執行優先級排序過程，以便生成優先級排序數據；以及執行在通過通信信道路由的多個消息之間進行仲裁的仲裁過程，優先級排序數據用來控制仲裁過程。 從第三方面來看，本發明提供用於數據處理裝置的仲裁控制電路，數據處理裝置包括多個處理元件，各處理元件運行需要向接收元件 發出消息的進程；在多個處理元件之間共享的通信信道，消息通過通 信信道路由；以及仲裁電路，用於執行在通過通信信道路由的多個消 息之間進行仲裁的仲裁過程，仲裁電路包括輸入接口，用於從各處 理元件接收在那個處理元件上運行的進程的進度數據，進度數據指示 進程的等待時間暗示；優先級排序電路，響應來自各處理元件的進度 數據，在考慮了由進度數據所指示的各進程的等待時間暗示的情況下 執行優先級排序過程，以便生成優先級排序數據；以及輸出接口，用 於向仲裁電路輸出優先級排序數據，以便控制仲裁過程。


僅作為實例、參照附圖所示的本發明的實施例來進一步描述本發明，附圖包括圖l是根據本發明的一個實施例的數據處理裝置的框圖；圖2A是示出一種用於在圖1的數據處理裝置中提供多核處理器的方法的框圖；圖2B是示出在圖1的數據處理裝置中提供多核處理器的一種備 選方式的框圖；圖3A是示意性說明不同類型的非實時進程的等待時間成本相對 時間的圖表；圖3B是示出對於圖3A所示的三個不同進程、根據本發明的一個實施例發出的停止位的值的圖表；圖4是示出實時進程的等待時間成本相對於時間的圖表；圖5示出根據本發明的一個實施例、由每個主裝置向圖1的仲裁控制電路發出的進度信息的各種部分(component);圖6示出根據本發明的一個實施例、可在圖1的仲裁控制電路中保存的數據結構；圖7示意性說明根據本發明的一個實施例、由圖1的仲裁控制電 路對於兩個線程所應用的排序過程；圖8是示出根據本發明的一個實施例、由圖1的仲裁控制電路所 應用的優先級排序過程的流程圖；圖9是更詳細地表示根據本發明的一個實施例、對所選線程對應 用排序過程所執行的步驟的流程圖；以及圖IO是示出還可如何將圖1的各種主裝置發出的進度數據的至少 一部分路由到數據處理裝置中的能量管理控制電路的^f匡圖。
具體實施方式
圖1是根據本發明的一個實施例的數據處理裝置的框圖。在這個 實施例中，數據處理裝置採取SoC的形式，其中包括經由通信信道40 與多個從裝置50、 60、 70耦合的多個主裝置10、 20、 30。雖然為了 論述本發明的一個實施例而考慮這樣一種SoC裝置，但是本領域的技 術人員會理解，本發明的實施例的技術可適用於在多個處理元件之間 共享通信信道的大量不同系統。考慮圖1的SoC實例，通信信道40通常採取互連塊的形式，其 中包括多個互連總線，為SoC中的多個總線主裝置10、 20、 30和總 線從裝置50、 60、 70的互連提供連接矩陣。組成通信信道的總線通常按照規定的總線協議進行操作，因而例 如可按照ARM Limited開發的"高級微控制器總線體系結構"(AMBA)Mr範進行操作。因此大家會理解，通信信道40由各個主裝置與從裝置之間的互連 的複雜布置組成。在通信信道中的各個點上，需要提供在爭用特定通 路的多個消息之間進行仲裁的仲裁電路。主裝置IO、 20、 30的每一個通常運行進程，在此期間通過通信信 道40發起各種事務。這類事務使數據能夠從主裝置路由到從裝置(在寫事務的情況下)或者自從裝置路由到主裝置(在讀事務的情況下)，其 中各事務通過主裝置將訪問請求發布到通信信道上發起。各訪問請求 可被認為是組成消息，以及通信信道中的仲裁電路需要在總線基礎設 施中多個消息可爭用特定通路的任何點上執行仲裁。因此，仲裁電路可^皮認為是由散布於通信信道上的多個仲裁元件 組成，其中的每個這樣的仲裁元件執行在多個消息之間進行仲裁的仲 裁過程。根據本發明的實施例，各仲裁元件所執行的仲裁過程由仲裁控制電路80來確定，仲裁控制電路80設置成在輸入接口 82上接收各 個主裝置10、 20、 30分別通過相應通路12、 22、 32輸出的進度信息。 稍後更詳細地進行描述，這個進度數據指示每個主裝置上運行的進程 的等待時間暗示，並且將那個進度數據轉發給仲裁控制電路中的優先 級排序電路84，其中，在考慮了那個進度數據的情況下執行優先級排 序過程，以便生成優先級排序數據。那個優先級排序數據則經由輸出 接口 86作為進程的優先級排序列表輸出，其中將那個列表路由到通信 信道中的所有仲裁元件(本文中又稱作仲裁器)。存在可傳播這個優先 級排序列表的各種方式。在一個實施例中，這個排序列表可通過與用 於路由消息相同的通路來傳播，而在一個備選實施例中，它可通過單 獨的專用總線結構來傳播。每個仲裁則根據所提供的優先級排序列表 來執行仲裁過程。仲裁控制電路80可設置成以預定間隔更新這個優先級排序列表。 一般來說，每當對仲裁控制電路的任何輸入改變時，應當更新優先級 排序列表。這通常引起在每個時鐘周期更新該列表，除非有極少或者 沒有事務正在進行。圖2A是示出一種可在圖1的數據處理裝置中提供多核處理器100 的方法的框圖。多核心處理器IOO具有經由處理器100中的內部通信 信道150互連的多個處理器核心110、 120、 130、 140。多核處理器IOO 則連接到外部通信信道160，經由外部通信信道160可與各個,人裝置 50、 60、 70進行通信。在一個實施例中，圖1的通信信道40可^皮認 為包含多核處理器10的內部通信信道150以及多核處理器外部的通信信道160,使得處理器核心IIO、 120、 130、 140的每一個實際上可被 認為組成獨立的主裝置，其中的每一個向仲裁控制電路80發出它們自 己的進度信息。在一個實施例中，各個這樣的核心110、 120、 130、 140運行獨立的程序線程，因此，從任何特定核心輸出的進度信息指 示關聯線程的等待時間暗示。在一個備選實施例中，如圖2B所示，多核處理器的內部構件對 仲裁控制電路隱藏，而多核處理器的整體看作是單個主裝置，在這個 實例中為主裝置10。因此，在主裝置10是多核處理器的情況下，通 過通路12輸出到仲裁控制電路的進度信息提供多核處理器所執行的 "進程"的總體等待時間暗示，因此沒有直接提供各個單獨核心110、 120、 130、 140運行的各個單獨線程的等待時間暗示。圖3A是示出各種類型的非實時進程的等待時間成本相對時間的 圖表。線條"a" 200示出當處理元件運行在需要時請求數據的進程時 發生的等待時間成本的形式，但是在通過通信信道40發出任何訪問請 求之前發生內部延遲。例如，這可能是主裝置是具有內部高速緩存、 黑盒系統等處理器的情況。考慮具有高速緩存的處理器的實例，當訪 問請求由處理器發出時，首先在高速緩存中執行查找，以便判定訪問 請求的對象的數據是否在高速緩存中。如果不是，則發生高速緩存未 命中，以及訪問請求然後通過通信信道40出現。如圖3A中與線條200 關聯的虛線所示，非實時進程觀測到的等待時間在任何訪問請求出現 於通信信道40之前已經增加，使得在時間零，訪問請求出現在通信信 道上，等待時間成本已經處於正值。相比之下，線條"b" 210示出對於其進程在需要時請求數據的處 理元件所觀測的線條類型，並且請求立即出現在通信信道40上。這樣 一個處理元件的實例例如可以是直接存儲器存取(DMA)控制器。線條"c" 220示出對於其進程提前請求數據的處理元件所觀測的 線條類型。因此，在這個實例中，請求在時間零出現於通信信道40， 但在到達時間h之前，不存在正的等待時間成本，因為該進程能夠進 行其它有效工作。因此，僅在時間tl5進程才實際停止。相比之下，對於與線條210關聯的進程，該進程在時間零停止，以及對於與線條200關聯的進程，該進程甚至在請求在時間零出現於通信信道40之前 停止。因此可以看到，與線條200和210關聯的進程沒有鬆弛時間，但 是與線條220關聯的進程具有某個鬆弛時間，在該鬆弛時間中，可處 理由那個進程發布到通信信道40上的消息，而那個進程不會停止。根據本發明的一個實施例，由運行非實時進程的任何主裝置發出 的進度信息的一部分是停止位，它在進程^皮停止時設置，而在進程沒 有一皮停止時重置。圖3B示出圖3A的三個示例線條的這個停止位的剖 面。在這個實例中，假定設置條件由邏輯值一表示，而重置條件則由 邏輯值零表示。從圖3B可以看到，與線條a關聯的進程在點205停止， 因此在那個點設置停止位。類似地，與線條b關聯的進程在點215停 止，以及與線條c關聯的進程在點225停止，因此停止位分別在點215、 225轉變。考慮與線條a關聯的進程，有可能的是，可在處理元件中內部為 請求提供服務，而無需通過通信信道40發出請求。例如，考慮前面所 述的具有高速緩存的處理器的實例，如果高速緩存命中發生，則相對 於高速緩存繼續進行訪問，而無需將訪問請求通過通信信道40傳播。 因此，如虛線207所示，在這類情況下，停止位在205轉變為邏輯值 一，但在已經為訪問請求提供服務時，又轉變為邏輯零電平。在一個 實施例中，不管是否將任何特定訪問請求發布到通信信道40,停止位 仍然作為進度信息的一部分^f皮輸出，以及在一個實施例中實際上用作 對於用來生成那個進程的等待時間信息的濾波器的輸入。因此，這為 仲裁控制電路80提供與任何特定主裝置的進程被停止的時間比率 (proportion)有關的信息，而不管那個停止的原因，具體來說，不是僅 限於由於通過通信信道40所引起的等待時間而發生停止的情況。圖4是與圖3A相似的簡圖，但示出實時進程的等待時間成本。 如前面所述，為了便於說明本申請，實時進程是"停止"對於那個進 程是不可接受的進程，與進程的某種停止是可接受的非實時進程相反。因此，假若不允許實時進程停止，則實時進程通常提前請求數據，因 此，雖然曲線沿著通路250,但存在與那個實時進程關聯的鬆弛時間。 但是，在這種情況下，鬆弛時間指示用於處理那個實時進程發出的消 息剩餘的時間，以及如果鬆弛時間耗盡，則等待時間成本變為無窮大，如垂直線260所示。圖5示出根據本發明的一個實施例、由主裝置IO、 20、 30發出的 進度信息的各種部分。具體來說，在圖5的實例中，假定主裝置10正 運行非實時線程，主裝置20正運行非實時線程，但主裝置30正運行 實時線程。在一個實施例中，運行非實時線程的每個主裝置設置成發 出四個部分以構成進度信息。具體來說，實時位信號通過通路200、 220發出，確定該進程是非實時線程。在這個實例中，這通過將實時 位設置為零來表示。此外，鬆弛值通過通路205、 225輸出，確定與非 實時線程關聯的任何鬆弛時間。對於圖3A的等待時間成本圖表，大 家會理解，這個鬆弛值可通過任何負等待時間成本值來表示。具體來 說，考慮線條c220，可以看到，負等待時間成本的幅度在時間零以特 定值開始，然後在與那個進程相關聯的鬆弛時間中逐漸減小到零，使 得它在時間h達到零值。此外，在圖5所示的實施例中，停止位通過通路210、 230輸出， 確定關聯進程在當前時間是否停止。這個停止位還輸入到低通濾波器 215、 235,以便使等待時間值淨皮生成並通過通路220、 240輸出，這個 等待時間值表示每個單位時間的延遲。在一個實施例中，每個低通濾 波器215、 235是跟蹤累計停止時間的簡單的單極低通濾波器。具體來 說，在一個實施例中，低通濾波器可實現以下等式以便產生等待時間 值y:yk = a.yk_i+xk(l畫a)式中，y是等待時間值，cc是所選常數，k是時間點，以及x是停 止位值。因此，等待時間值y與平均停止率、即對於參考時間段停止線程的周期數量成正比，其中，那個參考時間段取決於常數ot的選擇。 對於實時線程，進度信息同樣包含通過通路250輸出的實時位，在這個情況下實時位設置為邏輯值一，以指示線程是實時線程，並且還包含通過通路260從計數器255輸出的鬆弛值。具體來說，當實時 線程輸出訪問請求時，計數器255設置成表示允許響應那個訪問請求 的時鐘周期數量的某個預定值，然後隨著每個時鐘周期的過去，計數 器遞減，由此使鬆弛值隨時間減少。根據圖5所示的各種進度信息， 一個實施例的仲裁控制電路80則 保存各線程的數據結構的表300,如圖6所示。對於在欄位305輸入 的線程ID所表示的每個線程，實時位、停止位的值、濾波器輸出和松 弛值分別存儲在欄位310、 315、 320、 325中。如果對於特定線程僅提 供信息的子集，則欄位的一個或多個保留為空。例如，考慮實時線程， 不存在停止位或濾波器輸出。仲裁控制電路80則使用優先級排序電路84、在考慮了與各線程 相關聯的數據結構的情況下生成進程的優先級排序列表。本領域的技 術人員會理解，存在許多已知技術用於在^支提供一系列數據結構時形 成排序列表，並且這些進程往往包含迭代執行所選數據結構對的比較 過程。 一種這樣的機制是公知的"冒泡排序"機制，它通過重複對於 要排序的列表進行步進(stepping)、在某個時間比較兩個數據結構並在 它們處於錯誤順序時進行交換來進行工作。通過列表的傳遞(pass)步驟 重複進行，直到不需要交換為止，這表示列表^皮排序。圖7示意表示如何比較所選線程對(這裡標記為線程X和Y)的數 據結構，以便判定哪一個線程具有優先於另一個的優先級。因此，如 圖7所示，如果對於兩個線程設置了實時位(即兩個線程均為實時線 程)，則將優先級提供給具有最小鬆弛的線程，即，將優先級提供給具 有最早截止期限的線程，這樣一種優先化^支術往往稱作"最早截止期 限優先"的優先化。但是，如果線程X是非實時線程而線程Y是實時 線程，則如圖7的右上角所示，如果線程Y的鬆弛時間大於預定值N, 則將優先級提供給線程X。因此，大家會看到，不是將優先級自動提供給實時線程，而是在實時線程的爭>弛時間比較大時，將優先級提供 給非實時線程，以便設法減少那個非實時線程的等待時間。il^j"於實 時線程沒有不利影響，因為只要在鬆弛時間到期之前為實時線程提供 服務，就不會出現不利結果。類似地，如果線程Y是非實時線程而線程X是實時線程，則如圖7的左下側所示，如果線程X的鬆弛時間大於預定值N，則將優先級 提供給線程Y。如果兩個線程均為非實時線程，則判定過程如圖7的右下側所示。 具體來說，首先考慮兩個實時線程的停止位。如果兩個線程的停止位 均為零，指示沒有停止任一個線程，則將優先級提供給具有最小鬆弛 的線程，即提供給最快停止的線程。如果一個線程設置了停止位，而 另一個沒有設置，則將優先級提供給設置了停止位的線程，即，將優 先級提供給已經停止的線程。最後，如果兩個線程都設置了停止位，則將優先級提供給具有最高濾波器輸出的線程，即對於參考時間段具 有較高平均停止率的線程。在一些實施例中，不需要讓前面參照圖5所述的進度信息的所有 項全部出現。例如，在一些實施例中，鬆弛值對於非實時線程可能不 可用。在那種情況下，如果考慮兩個非實時線程，並且兩個非實時線 程都將停止位設置為等於零，則將優先級提供給具有最高濾波器輸出 的線程，即，如兩個線程都將停止位設置為等於一時所應用的那樣應 用相同的優先化。在一個實施例中，如果某些線程沒有提供停止位，則4叚定設置了 停止位，即具有邏輯值一。圖8示出根據一個實施例、由圖1的仲裁控制電路80所執行的產 生優先級排序列表的一般過程。在步驟400，準備線程的初始排序。 在第一迭代中，這可以是任意排序，^f旦是對於後續迭代，則初始排序 很可能是該過程所產生的前一個排序。此後，該過程進入步驟405, 在其中，選擇一對線程，此後在步驟410,應用排序過程，稍後參照 圖9更詳細地進行描述。排序過程實現前面參照圖7示意表示的優先化方案。此後，在步驟415,根據排序過程的結果來修正線程的排序，此後在步驟420,判定是否存在應當應用排序過程的更多線程對。在通 過該過程的第一迭代中，情況通常是，線程對的每一個組合都需要經 過排序過程。但是，在後續迭代中，根據進度信息的哪些特徵已經改 變以及哪些線程的進度信息已經改變，可以僅需要對所有可能的線程 對的子集應用排序過程。如果在步驟420判定存在至少還有一對線程 需要應用排序過程，則該過程返回到步驟405，而如果判定沒有更多 對需要經過排序過程，則該過程進入步驟425，在其中，將線程的修 正排序作為優先級排序列表輸出到通信信道40中的所有仲裁器。應當注意，雖然為了便於說明而依次示出步驟405、 410、 415和 420，但是，這些步驟實際上可並行執行，使得確定需要經過排序過程 的所有對，然後並行應用排序過程，以便產生線程的修正排序。圖9是示出根據本發明的一個實施例、在圖8的步驟410所執行 的步驟的流程圖。在步驟500，確定兩個線程是否為實時線程，如果 是，則在步驟505按照最早截止期限優先的原則對線程確定優先順序。如果在步驟500確定兩個線程均不是實時的，則在步驟410確定 線程之一是否為實時線程，以及如果是，則過程進入步驟515，在其 中，如果實時線程的鬆弛大於預定值N,則將優先級提供給非實時線 程。否則，實時線程優先。如果在步驟510確定沒有任一個線程是實時線程，則該過程進入 步驟520，在其中，確定兩個線程的停止位是否等於零，即，兩個線 程是否仍然剩餘某個鬆弛。假定兩個線程仍然具有某個松他，則該過 程進入步驟525，在其中，確定鬆弛值是否可用，如果是，則該過程 進入步驟530，在其中，按照最早截止期限優先的原則對線程確定優 先順序，即，將優先級提供給具有最小鬆弛的線程。但是，如果在步 驟525確定鬆弛值不可用，則該過程進入步驟535，在其中，將優先 級提供給具有最高濾波器輸出的線程。如果在步驟520確定兩個線程的停止位不等於零，則在步驟540確定線程之一的停止位是否等於零，即一個線程具有鬆弛。如果是，則該過程進入步驟545，在其中，將優先級提供給沒有鬆弛的線程(即停止位等於一的線程)。如果在步驟540確定沒有任一個鬆弛值設置為零，即兩個線程均 被停止，則該過程進入步驟550，在其中，將優先級提供給具有最高 濾波器輸出的線程。從圖9的以上描述中，大家會看到，圖9的過程實現圖7示意性 說明的選擇標準。在一個實施例中，通過將不同加權分配(attribute)給某些非實時線 程，可優先於其它非實時線程來處理那些線程。實際上，可由對於運 行非實時線程的各處理元件所提供的關聯低通濾波器215 、 235來應用 這些加權。因此，對於具有較高加權的進程，每當設置了停止位時， 來自關聯低通濾波器的輸出等待時間值將比對於較低加權進程的情況 增加更大數量。因此，如果在應用參照圖7示意性說明的選擇標準時， 確定應當將優先級提供給具有最高濾波器輸出的線程，則所有方面都 相等，具有較高加權的線程將具有較高濾波器輸出，並且優先於具有 較低加權的線程。因此，通過對來自濾波器的輸出進行加權，這提供 了用於處理各種非實時線程的優先級的另 一個靈活性。大家會理解，本發明的實施例的上述技術設法減少施加到運行於 主裝置的各個線程的最大等待時間。這又成比例地增加各進程可進行 有效工作的有用時鐘周期的數量。因此，如果這提供比實際所需的更好的性能，則通過降低主裝置或者由那些主裝置共享的通信信道的工 作性能等級，就有可能增加總等待時間。具體來說，許多現代系統提供能量管理技術，它們通常通過改變 系統中某些組件的頻率和/或工作電壓，可改變那些組件的性能等級。 這種性能等級設定通常由系統中的能量管理控制器執行。給定上述觀測，在本發明的一個實施例中，各個主裝置輸出的進 度數據的某些方面還作為輸入^皮路由到這種能量管理控制器。圖10示 意表示這樣一種實施例，並且從圖10可看到，通過通路12、 22、 32輸出的進度數據一部分還可作為輸入分別通過通路602、 604、 606尋皮 路由到能量管理控制器600。在一個具體實施例中，將任何非實時線 程輸出的等待時間值路由到能量管理控制器600。可通過各種方式來 使用這種信息。例如，如果特定主裝置的工作頻率為每毫秒一千個周期，則等待 時間值指示每毫秒存在一百個停止周期，則這表示主裝置具有每毫秒 九百個有效周期。如果那個主裝置實際上僅需要每毫秒六百個有效周 期就能符合要求地運行其進程，則提供給那個主裝置的頻率和/或工作 電壓可減小以節省能量，同時仍然提供那個主裝置所需的每毫秒六百 個有效周期。根據可改變性能等級的粒度，這個過程可單獨對於每個 主裝置依次執行。作為備選或附加的方案，如果通信信道40的性能等級可由能量管 理控制器來改變，則能量管理控制器600可選擇從各個主裝置接收的 最高等待時間值，並且在已經考慮那個最高值的情況下調整通信信道 的性能等級。例如，這可使通信信道的工作頻率能夠減小，同時仍然 確保在各個主裝置上運行的進程可繼續符合要求地工作。本質上，能 量管理控制器可調整通信信道的時鐘速度，以便力求達到系統以及其 中運行的應用程式可接受的參考線程停止率。本發明的上述實施例使QoS能夠被自動確定並在線程之間分配， 從而消除了預先知道要求的需要，其中的QoS動態適應線程之間的通 信的變化。本發明的實施例的QoS方案還可用於為通信信道實現提供參考性 能等級。具體來說，它允許在組件、如存儲控制器的體系結構中進行 比較，其中，添加流水線級(stage)以實現這種類型的仲裁方案的成本 可與訪問存儲控制器的所有線程的等待時間的附加周期的成本進行比較。雖然本文描述了一個具體實施例，但是大家會理解，本發明不限 於此，而且在本發明的範圍之內可對它進行許多》務改和添加。例如， 可在不背離本發明的範圍的前提下，進行以下從屬權利要求的特徵與獨立權利要求的特徵的各種組合。
權利要求
1.一種用於在通過通信信道路由的消息之間進行仲裁的數據處理裝置，包括多個處理元件，每個處理元件用於運行需要向接收元件發出消息的進程；在所述多個處理元件之間共享的通信信道，所述消息通過所述通信信道路由；仲裁電路，用於執行在通過所述通信信道路由的多個消息之間進行仲裁的仲裁過程；每個處理元件設置成發出在那個處理元件上運行的所述進程的進度數據，所述進度數據指示所述進程的等待時間暗示；以及仲裁控制電路，響應來自每個處理元件的所述進度數據，在考慮了所述進度數據所指示的各進程的所述等待時間暗示的情況下執行優先級排序過程以便生成優先級排序數據，並將所述優先級排序數據輸出給所述仲裁電路，以便控制所述仲裁過程。
2. 如權利要求1所述的數據處理裝置，其中，每個處理元件是連 接到所述通信信道的主裝置。
3. 如權利要求2所述的數據處理裝置，其中，每個消息是所述主 裝置其中之一發出的訪問請求。
4. 如權利要求1所述的數據處理裝置，其中，各進程是程序線程， 以及各處理元件運行單個程序線程。
5. 如權利要求1所述的數據處理裝置，其中，至少一個處理元件 包括多個處理單元，每個處理單元運行一個程序線程。
6. 如權利要求1所述的數據處理裝置，其中，所述數據處理裝置 是晶片上系統。
7. 如權利要求l所述的數據處理裝置，其中，所述進度數據確定 所述關聯進程是實時進程還是非實時進程，對於實時進程，所述進度 數據還確定指示處理那個實時進程發出的消息剩餘的時間的至少 一個鬆弛值，對於非實時進程，所述進度數據還確定指示對於預定時間與 那個進程關聯的等待時間的至少一個等待時間值。
8. 如權利要求7所述的數據處理裝置，還包括與運行非實時進程 的各處理元件相關聯的濾波器電路，所述濾波器電路以每個單位時間 的等待時間的形式產生所述等待時間值。
9. 如權利要求7所述的數據處理裝置，其中，至少一個非實時進 程具有與其關聯的加權，並且在產生那個非實時進程的所述等待時間值時考慮那個加權。
10. 如權利要求7所述的數據處理裝置，還包括與運行實時進程 的各處理元件關聯的計數器電路，所述計數器電路產生所述鬆弛值。
11. 如權利要求7所述的數據處理裝置，其中，對於非實時進程， 所述進度數據還確定用於確定那個進程是否停止的停止值。
12. 如權利要求7所述的數據處理裝置，其中，對於非實時進程， 所述進度數據還確定指示用於在所述進程停止之前處理由那個進程發 出的消息剩餘的時間的;^弛值。
13. 如權利要求7所述的數據處理裝置，其中，如果某個實時進 程的所述鬆弛值指示用於處理由那個實時進程發出的消息剩餘的時間 大於預定閾值，則所述優先級排序過程對非實時進程提供優先於那個 實時進程的優先級。
14. 如權利要求7所述的數據處理裝置，其中，所述優先級排序 過程對具有較高等待時間值的非實時進程提供比具有較低等待時間值 的非實時進程高的優先級。
15. 如權利要求14所述的數據處理裝置，其中，對於非實時進程， 所述進度數據還確定用於確定那個進程是否停止的停止值，其中，對 於具有不同停止值的兩個非實時進程，所述優先級排序過程比將優先 級提供給具有較高等待時間值的所述進程更優先地將優先級提供^亭 止值指示那個進程糹皮停止的所述非實時進程。
16. 如權利要求14所述的數據處理裝置，其中，對於非實時進程， 所述進度數據還確定指示用於在所述進程停止之前處理由那個進程發出的消息剩餘的時間的鬆弛值，其中，對於具有不同鬆弛值的兩個非 實時進程，所述優先級排序過程比將優先級提供給具有較高等待時間 值的所述進程更優先地將優先級提供給具有最小鬆弛的所述非實時進 程。
17. 如權利要求1所述的數據處理裝置，還包括 能量管理電路，用於控制所述多個處理元件的一個或多個處理元件的工作性能等級，所述能量管理電路可用於在確定所述工作性能等 級時考慮那一個或多個處理元件發出的所述進度數據的至少一部分。
18. 如權利要求17所述的數據處理裝置，其中，所述進度數據確 定所述關聯進程是實時進程還是非實時進程，對於實時進程，所述進 度數據還確定指示處理由那個實時進程發出的消息剩餘的時間的至少 一個鬆弛值，對於非實時進程，所述進度數據還確定指示對於預定時 間與那個進程關聯的等待時間的至少一個等待時間值，其中，所述進 度數據的至少一部分包括由運行非實時進程的一個或多個處理元件輸 出的所述等待時間值。
19. 一種在通過具有多個處理元件的數據處理裝置的通信信道路 由的消息之間進行仲裁的方法，各處理元件運行需要向接收元件發出 消息的進程，以及所述通信信道在所述多個處理元件之間共享，所述 消息通過所述通信信道路由，所述方法包括據，所述進度數據指示所述進程的等待時間暗示；響應來自各處理元件的所述進度數據，在考慮了所述進度數據所 指示的各進程的所述等待時間暗示的情況下執行優先級排序過程，以 便生成優先級排序數據；以及執行在通過所述通信信道路由的多個消息之間進行仲裁的仲裁過 程，所述優先級排序數據用來控制所述仲裁過程。
20. —種用於數據處理裝置的仲裁控制電路，所述數據處理裝置 包括多個處理元件，各處理元件運行需要向接收元件發出消息的進 程；在所述多個處理元件之間共享的通信信道,所述消息通過所述通信信道路由；以及仲裁電路，用於執行在通過所述通信信道路由的多 個消息之間進行仲裁的仲裁過程，所述仲裁電路包括輸入接口 ，用於從每個處理元件接收在那個處理元件上運行的所 述進程的進度數據，所述進度數據指示所述進程的等待時間暗示；優先級排序電路，響應來自各處理元件的所述進度數據，在考慮 了所述進度數據所指示的各進程的所述等待時間暗示的情況下執行優 先級排序過程，以便生成優先級排序數據；以及輸出接口，用於將所述優先級排序數據輸出給所述仲裁電路，以 便控制所述仲裁過程。
全文摘要
本發明公開一種用於在消息之間進行仲裁的數據處理裝置和方法。提供用於在通過通信信道路由的消息之間進行仲裁的數據處理裝置和方法。數據處理裝置包括多個處理元件；在處理元件之間共享的通信信道，消息通過通信信道路由。仲裁電路執行仲裁過程。每個處理元件發出在其上運行的進程的進度數據，進度數據指示進程的等待時間暗示。仲裁控制電路則響應進度數據，在考慮了進度數據指示的各進程的等待時間暗示的情況下執行優先級排序過程以生成優先級排序數據。然後將優先級排序數據輸出給仲裁電路以控制仲裁過程。這使服務質量能夠被自動確定並在各個進程之間分配，而無需預先知道進程的要求，並且優先化機制動態適應進程之間的通信的變化。
文檔編號G06F15/16GK101271438SQ20081008737
公開日2008年9月24日 申請日期2008年3月20日 優先權日2007年3月22日
發明者T·C·梅斯 申請人:Arm有限公司