對至少一個獨佔資源的使用進行調度的數據處理系統和方法
2023-09-23 18:38:35
專利名稱：對至少一個獨佔資源的使用進行調度的數據處理系統和方法
技術領域：
本發明涉及一種在數據處理系統中對至少一個獨佔資源的使用 進行調度的方法，所述方法包括為至少兩個任務流預留時間的步驟， 所述任務流由所述至少一個獨佔資源來執行。
本發明還涉及一種包括至少一個獨佔資源的數據處理系統，所述 數據處理系統被設置來為至少兩個任務流的時間，其中所述至少一個 獨佔資源被設置為執行所述任務流。
背景技術：
信號(例如視頻信號)處理典型地包括按照指定序列執行的多個 任務。圖l示出了該任務序列的示例。圖l中所示的矩形表示對每一個 輸入信號(例如針對每一個輸入視頻幀)需要執行的任務。這些任務 可以由若干個處理器來執行。 一些處理器可以執行針對同一輸入信號 的多個任務。典型地，該處理器從存儲器中讀取輸入信號，執行某些 處理並將信號寫回存儲器。圖1中的箭頭通常以存儲緩衝器來實現。
任務序列也被稱作流或任務流。例如，電視接收機中存在主視頻
流。主視頻流包括例如任務t0、 tl、 t2、 t10、 t20、 t31和t32。任務 tlO把輸入信號(視頻幀)寫入存儲器，t0、 tl和t2執行圖像縮放，t20 執行降噪，t32把計算出的視頻幀輸出至顯示屏，而t31把視頻幀輸出 至輔助輸出。在這個示例中，任務tO由處理器pO來執行，任務tl和t2 由處理器pl來執行，任務tl0由處理器pl0來執行，任務t20由處理器p20 來執行，任務t31由處理器p31來執行，而任務t32由處理器p32來執行。 優選地，利用靜態周期性調度來實現流。周期性的含義是，針對 每一個輸入信號，重複相同的任務定時順序。該周期性取決於數據處 理系統的實現，例如可以針對每一個視頻幀或場而重複任務的定時順序。靜態的含義是，該調度是在運行時間之前已設計好的。靜態調度 允許實現對例如流的端對端延遲等重要參數的優化和控制。
圖2示出了對一個輸入信號(以灰色示出)的調度的示例，該信 號周圍環繞著對在前和在後的輸入信號的相同調度的周期性迭代
(iteration)。箭頭示出了哪些任務屬於同一迭代。通常，數據處理 系統中有多個處理器是獨佔資源。獨佔資源被定義為在一個時刻僅能 夠由一個任務使用的資源。在圖2中可以看出，pl在一個時刻不能用於 多個任務，既不能在一次迭代中用於多個任務，也不能在多次迭代之 間用於多個任務。
當構建調度時，也需要對照系統的可使用限制來檢查所使用的共 享資源(例如存儲器帶寬、共享處理器的處理器周期)。用於構建該調 度的方法和工具已經在如下文獻中得以描述"Philips Nexperia Digital Video Platform ，， , by Maurice Penners and Hans van Antwerpen，at the Design,Automation and Test in Europe(DATE) conference in Paris, 2004 February 16-20。
在數據處理系統中，可能存在多個流以及這些流的變量
(variant),例如主流的變量和一個或更多個子流的變量。依據輸入 信號的格式，例如壓縮的或未壓縮的視頻、標準清晰度或高清晰度、 隔行掃描或逐行掃描等，在流中執行不同的任務。依據環境，還會存 在需要合併的多個流。例如在圖3中，fO表示圖l中所示的主視頻流， 而fl表示子視頻流，其中第二視頻輸入由pll置於存儲器中，由p0和pl 進行縮放，並由p32置於主顯示輸出的小窗口中。可能存在若干個其他 流，例如針對圖形和VBI (垂直消隱信息)的流。此外，依據輸入信號 的格式，子流具有若干變量。所以，必須能夠對主流、子流以及可能 的其他流的獨立變量進行合併。
簡言之，必須能夠利用靜態周期性調度對多個流進行調度，以便 對流的性能參數進行優化和控制。這些流可以是流的變量，例如主視 頻流的變量或子視頻流的變量。
發明內容
本發明的目的是改進多任務數據處理系統的性能，該系統中至少 一個獨佔資源用於執行至少兩個任務流。這個目的通過提供一種以權 利要求l的特徵部分為特徵的方法而實現，以及通過提供一種以權利要 求7的特徵部分為特徵的數據處理系統而實現。
根據本發明的方法通過使用所謂的主調度而實現了這個目的，主 調度用作用於構建對單獨任務流的調度的模板。術語主調度是指針對 任務流的獨佔資源的預留集合。
根據本發明的方面，如權利要求2中所述，第一固定時間單元和 第二固定時間單元包括在主調度中，所述主調度用於管理對所述任務 流的預留的調度。
根據本發明的另一方面，如權利要求3中所述，所述任務流由多
個獨佔資源來執行。
根據本發明的另一方法，如權利要求4中所述，所述主調度通過
如下步驟來構建
-針對每一個獨佔資源，計算所述任務流中需要所述獨佔資源的
最大時間量；
-檢查在所述計算步驟中計算出的最大值之和是否在與一個調度 周期相對應的時間內；
_使用所述最大值作為分配給所述任務流的固定時段的持續時間 的下界；
-針對最關鍵的任務流，對所述固定時段進行調整；
-針對較不關鍵的任務流，重複所述調整步驟。
根據本發明的另一方面，如權利要求5中所述，第一任務流是主 任務流，而第二任務流是子任務流。
根據本發明的另一方面，如權利要求6中所述，主任務流是主視 頻流，而子任務流是子視頻流。
參考附圖對本發明進行更為詳細的描述，其中 圖l示出了數據處理系統中任務流的示例；圖2示出了靜態周期性調度的示例；
圖3示出了數據處理系統中多個任務流的示例；
圖4示出了根據本發明的主調度的示例；
圖5示出了所產生的主調度以及由主調度所管理的周期性調度的 迭代的示例；
圖6示出了用於執行視頻處理的典型數據處理系統的示例；
圖7示出了視頻輸入的第一主流變量；
圖8示出了視頻輸入的第二主流變量；
圖9示出了視頻輸入的第一子流變量；
圖10示出了視頻輸入的第二子流變量；
圖11A、 11B和11C示出了由圖6中所示的數據處理系統中的獨佔資
源執行的任務所需的時鐘周期；
圖12A、 12B和12C示出了由圖6中所示的數據處理系統中的獨佔資
源執行的任務的迭代；
圖13示出了第一主流變量的靜態周期性調度； 圖14示出了第二主流變量的靜態周期性調度； 圖15示出了第一子流變量的靜態周期性調度； 圖16示出了第二子流變量的靜態周期性調度。
具體實施例方式
圖l示出了數據處理系統中的任務流的示例，例如電視接收機中的 主視頻流，其中任務tlO把輸入信號(視頻幀)寫入存儲器，t0、 tl 和t2執行圖像縮放，t20執行降噪，t32把計算出的視頻幀輸出至顯示 屏，而t31把視頻幀輸出至輔助輸出。在這個示例中，任務tO由處理器 pO來執行，任務tl和t2由處理器pl來執行，任務tlO由處理器plO來執 行，任務t20由處理器p20來執行，任務t31由處理器p31來執行，而任 務t32由處理器p32來執行。
圖2示出了靜態周期性調度的示例。周期性的含義是，針對每一個 輸入信號，重複相同的任務定時順序。靜態的含義是，該調度在運行 時之前已被設計好。靜態調度允許實現對例如流的端對端延遲等重要
參數的優化和控制。圖2示出了針對一個輸入信號(灰色)的調度的示 例，該信號調度周圍環繞著對於在前和在後的輸入信號進行相同調度 的周期性迭代。箭頭用於表示哪些任務屬於同一迭代。數據處理系統 中有多個處理器可以是獨佔資源它們在一個時刻僅能夠用於一個任 務。在圖2中可以看出，pl在一個時刻不能用於多於一個的任務，既不 能在一次迭代中用於多於一個的任務，也不能在多次迭代之間用於多 於一個的任務。
圖3示出了數據處理系統中多個任務流的示例。在圖3中，f0表示
圖l中所示的主視頻流，而fl表示子視頻流，其中第二視頻輸入由pll
置於存儲器中，由pO和pl進行縮放，並由p32置於主顯示輸出的小窗口中。
己經發現，構建針對多任務流的靜態周期性調度是困難的事情， 特別是在任務流必須遵守特定性能規則的情況下，例如遵守最大端對 端延遲。根據本發明的方法通過使用所謂的主調度而實現了該目標， 其中主調度用作用於構建對單獨任務流的調度的模板。
圖4示出了根據本發明的主調度的示例。術語主調度是指針對任務 流的獨佔資源預留集合。例如在圖4中，將獨佔資源pO和pl在任務流f0
和n之間劃分。
主調度的構建以多個步驟完成
-檢查所有的流或流變量，並對於每一個獨佔資源，計算在流或流
變量中需要該資源的最大時間量；
-對於每一個獨佔資源，檢査先前步驟的最大值之和是否在與一個 調度周期相對應的時間內；然後，將這些最大值用作預留的持續時間 的下界；
-對於最關鍵的流或流變量(例如對端對端延遲的要求最嚴格的 流)，對獨佔資源的預留進行調整，以滿足其調度要求；針對其他流重 復這個步驟，每次都從剩餘流中最關鍵的流開始。
主調度用於構建對單獨的流或流變量的調度
-對於每一個流或流變量，構建調度，該調度使用主調度中針對該 流的預留；-對於流或流變量的每一個允許的合併，檢査所使用的共享資源 (例如存儲器帶寬)低於系統限制。
如果步驟失敗，則需要改變先前步驟中的設計決策，或在更早的 步驟中遞歸地改變。
注意，在一些數據處理系統中，獨佔資源的時鐘頻率可以改變。 這在構建主調度的前兩個步驟中提供了額外的自由。在第一步驟中， 可以計算流或流變量中需要每一個獨佔資源的最大時鐘周期數。在第 二步驟中，選擇足夠高的獨佔資源時鐘頻率，以使預留符合與一個調 度周期相對應的時間。
圖5示出了所產生的主調度以及由主調度所管理的周期性調度的 迭代的示例。圖5下半部分示出了示例性主調度，具有針對流fO和fl 的獨佔資源pO和pl的預留。圖中上半部分示出了流fO的變量和流fl的 變量的周期性調度的一次迭代。作為示例，在針對所示的流fO的變量 的調度中，pl使用了兩次。對pl的這兩次使用均落入針對fO的pl的預 留內。
作為用於構建主調度的方法的變化形式，如果獨佔資源用於流變 量中的多個任務，則可以把針對流的獨佔資源預留分為多個非相鄰部 分。在這種情況下，針對這些任務中的每一個任務，執行用於構建主 調度的步驟。作為示例在圖5中，在流fO的變量中對pl的兩次使用中， 每一次使用都具有分離的預留，假定這符合同一fO的其他變量。預留 的粒度越細，越有助於滿足嚴格的調度要求(例如，端對端延遲)，但 是這減小了有關流中對有關獨佔資源的調度自由。
圖6示出了用於執行視頻處理的典型數據處理系統的示例。其給出
了申請人開發的集成電路的一部分的示意表示，即飛利浦半導體公司 的集成電路PNX8550。該集成電路特別包含執行視頻處理或視頻解壓縮
的多個協處理器。這些協處理器中的兩個用作靜態周期性調度中的獨 佔資源
-MBS-1 (基於存儲器的縮放器)從存儲器MEM0RY-1中讀取視頻場 或幀，對水平和垂直視頻解析度執行放大或縮小，並把所產生的視頻 場或幀寫回存儲器。在去隔行的情況下，其可以執行額外的濾波。對
一個輸入場或幀的這些操作在一個任務中執行。
-QTNR (品質時間降噪器)從存儲器中讀取當前和先前的視頻場或 幀，通過對先前的場或幀進行加權平均而降低當前場或幀中的噪聲， 並把結果寫回存儲器。針對一個當前輸入場或幀的這些操作在一個任 務中執行。
相伴的飛利浦半導體公司的集成電路PNX2015也包含用於視頻處
理和視頻解壓縮的協處理器。這些協處理器當中，基於存儲器的縮放 器MBS-3用作靜態周期性調度中的獨佔資源。MBS-3能夠訪問MEM0RY-2。
MBS-3還能夠通過由器件t 1和t2所示的隧道連接而訪問MEMORY-1 。集成 電路PNX8550還包括型號為Trimedia TM3260的可編程處理器TM-1 。可 編程處理器TM-l具體運行運行時間調度程序軟體，該調度程序把靜態 調度的任務分派給PNX8550和PNX2015上的協處理器。
下文描述兩個主流變量和兩個子流變量。隨後，描述用於構建主 調度的步驟以及針對單獨的流變量的調度。
圖7示出了視頻輸入的第一主流變量。其示出了流變量 main—A麗一480i，即具有格式72O480i的經HDMI的視頻輸入的主流變 量。任務ip把輸入視頻場置於存儲器中的中間場緩衝器。任務scale3 和scale一vcr使用獨佔資源MBS-3和MBS-l執行縮放。在這個流變量中， 任務scale3和scale—vcr縮放100。/。，但對於流變量main—ANH—1080i (稍 後描述)，該任務使用不同的縮放因子。任務nr使用獨佔資源QTNR執行 降噪。任務mc執行運動補償。任務scalel使用獨佔資源MBS-l執行縮放 (包括去隔行)。任務scale一gfx執行針對OSD (在屏顯示)的圖形信息 片的縮放。
任務opl把主流、子流和圖形的視頻層進行合併，並產生其定時特 性適於LCD顯示器或等離子顯示器的輸出信號。任務opl的持續時間是
輸出視頻幀的完整周期。
任務scale2也執行縮放。執行任務scale2和opl的協處理器是直接 連結的(不需要MEM0RY-1中的中間緩衝器)。這意味著scale2的持續時 間也是完整的幀周期，與opl相同。所以，執行scale2的協處理器不會 用於其他任務，而且其不會用作靜態周期性調度中的獨佔資源。
執行任務opl的協處理器在其輸出處包含針對當前視頻行的計數
器。這個協處理器能夠在與周期性靜態調度中有關的行編號處產生中
斷。(這個調度將在後文描述)。運行在可編程處理器TM-l上的調度程
序使用這些中斷，在調度時刻把任務分派給有關協處理器。
圖8示出了視頻輸入的第二主流變量。其描述了main一ANH一1080i， 即具有格式1920W080i的經HDMI的視頻輸入的主流變量。其示出了當 全屏顯示主流時所使用的最大解析度。這用於單窗口模式中。其還用 於子流顯示為小PIP (畫中畫)時的背景窗口。當主流在DW (雙窗口) 模式下顯示在屏幕左半部分中時，解析度較低。這個實施例中的主調 度用於PIP模式和DW模式兩者，因此下文的計算基於最大解析度。
圖9示出了視頻輸入的第一子流變量，其描述了sub—ANA—480i，即 具有格式720*4801的經模擬調諧器的視頻輸入的子流變量。示出了當 子流以DW (雙窗口)模式顯示在屏幕的右半部分中時所使用的最大分 辨率。當子流以P工P (畫中畫)模式顯示在小窗口中時，解析度較低。 這個實施例中的主調度用於PIP模式和DW模式兩者，因此下文的計算基 於最大解析度。
圖10示出了視頻輸入的第二子流變量，其描述了sub—MP—1080i， 即具有格式1920H4080i的MPEG-2視頻輸入的子流變量。任務mp以水平 解析度的一半執行解壓縮。
該圖示出了當子流以匿(雙窗口)模式顯示在屏幕右半部分中時 所用的最大解析度。當子流以PIP (畫中畫)模式顯示在小窗口中時， 解析度較低。這個實施例中的主調度用於PIP模式和DW模式兩者，因此 下文的計算基於最大解析度。
圖11A、 11B和11C示出了由圖6中所示的數據處理系統中的獨佔資 源執行的任務所需的時鐘周期。這個計算與用於構建主調度的方法的 第一步相對應，即對所有的流或流變量進行檢査，並針對每一個獨佔 資源，計算流或流變量中需要這個資源的最大時間量。
圖11A示出了主流和子流變量中對於獨佔資源MBS-3的任務所需周 期。任務的周期數等於該任務的輸入和輸出視頻場或幀的最大寬度 乘以該任務的輸入和輸出視頻場或幀的最大高度。
圖11B示出了主流和子流變量中對於獨佔資源QTNR的任務所需周 期。任務的周期數等於該任務的輸出場或幀中的像素數乘以2。
圖11C示出了主流和子流變量中對於獨佔資源MBS-l的任務所需周
期。任務的周期數等於該任務的輸入和輸出視頻場或幀的最大寬度 乘以該任務的輸入和輸出視頻場或幀的最大高度。
圖12A、 12B和12C示出了由圖6中所示的數據處理系統中的獨佔資
源所執行的任務的迭代。這對應於用於構建主調度的方法的第二步， 即對於每一個獨佔資源，檢査先前步驟中的最大值之和是否在與一個
調度周期相對應的時間內；然後，將這些最大值用作預留的持續時間。
圖12A示出了以10腦Hz運行的MBS-3所執行的任務的持續時間。對 於獨佔資源MBS-3，處理器頻率具體可以被設置為108MHz。對於這個頻 率，MBS-3表中的1,589， 760個周期需要1,589,760/ 108,000, 000s=14.72ms。這在60Hz調度的周期16. 67ms內。
圖12B示出了以173MHz運行的QTNR的每一個任務的持續時間。對於 獨佔資源QTNR，處理器頻率具體可以被設置為173MHz。對於這個頻率， QTNR表中的691， 200個周期需要691, 200/173, 000, 000s二4ms。這在60Hz 調度的周期16.67ms內。
圖12C示出了以123MHz運行的MBS-l的每一個任務的持續時間。對 於獨佔資源鵬S-1，處理器頻率具體可以被設置為123MHz。對於這個頻 率，MBS-1表中的1,275,240個周期需要1,275,240/ 123， 000, OOOs二lO. 37ms。這在60Hz調度的周期16. 67ms內。
用於構建主調度的第三步是對於最關鍵的流或流變量(例如對 端對端延遲的要求最嚴格的流)，對獨佔資源的預留進行調整，使得其 調度要求得以滿足；針對其他流迭代這個步驟，每次都從剩餘流中最 關鍵的流開始。參考下文討論中的優選實施例來描述這個步驟。
主流變量的端對端延遲被限制為37nis。對子流變量沒有嚴格的端 對端延遲要求。實現這個延遲對於main_ANH_1080i來說比 main—ANH—480i要容易。後者具有需要依次執行的大量任務。
圖13示出了實現37ms的端對端延遲的main—AML480i的靜態周期 性調度。MBS-3行中的名稱"3"表示任務scale3。 QTNR行中的名稱"n"
表示任務nr。 MBS-l行中的名稱"g"、 "v"和"1"分別表示任務 scale—gfx、 scale一vcr禾口scalel。
灰色的任務描述了對一個輸入視頻場執行的視頻處理的一次迭 代。連續的迭代發生交疊。
一次迭代中的一些任務也發生交疊。作為示例，任務ip、 scale3 和nr中的每一個都從頂視頻行到底視頻行依次執行視頻處理。這些任 務可以發生交疊，但是它們不會彼此趕超(overtake)。圖中的靜態周 期性調度遵從多個額外的約束。作為示例，MEMORY-l的可用帶寬禁止 任務nr (QTNR上)和scalel (MBS-l上)的任務之間發生交疊，即使它
們處於不同的迭代中。
圖13中的靜態周期性調度示出了獨佔資源MBS-3、 QTNR和MBS-l沒 有用於流變量main一ANH一480i的時亥lj。圖中的點線框表示對子流的預留 可能存在的位置。對於子流變量中的任務來說，點線框的持續時間要 足夠長。QTNR的點線框的持續時間甚至是子流變量中針對任務nr所計 算的持續時間的兩倍QTNR具有針對存儲器訪問的低優先級，所以其 任務可能會慢下來。所示的預留的位置不僅適合流變量 main—ANH一480i，而且還適合所有較不關鍵的流變量。所示的位置是已 經針對所有餘下的流完成步驟3後的結果。
所產生的主調度是
-在1.30至6.42ms之間，MBS-3被預留用於子流變量中的任務。 -在1.37和5.37ms之間，QTNR被預留用於子流變量中的任務。 -在5. 56和8.93ms之間，MBS-1被預留用於子流變量中的任務。 -在餘下的時間中，MBS-3、 QTNR和MBS-l被預留用於主流變量中的 任務。
主調度用於構建針對單獨的流或流變量的調度
-對於每一個流或流變量，構建調度，該調度使用主調度中針對該
流的預留；
-對於流或流變量的每一個允許的合併，檢查所使用的共享資源 (例如存儲器帶寬)低於系統限制。
圖13、圖14、圖15和圖16示出了使用主調度而構建的靜態周期性
調度。圖13示出了針對main—ANH—480i的實現了37ms端對端延遲的靜態 周期性調度。圖14示出了遵守主調度的針對main—ANH一1080i的靜態周 期性調度，端對端延遲是37ms (與main—ANH一480i的相同)。圖15示出 了遵守主調度的針對siib—ANA—480i的靜態周期性調度。圖16示出了遵 守主調度的針對sub—MP—1080i的靜態周期性調度。
對於最後的步驟，即對於流或流變量的每一個允許的合併，檢查 所使用的共享資源(例如存儲器帶寬)低於系統限制，如下內容需要 注意。上圖中的靜態周期性調度是多個設計迭代的結果。利用這些產 生的調度，對於主流變量和子流變量的所有可允許的合併，使用獨佔 資源的任務和產品中的所有其他任務都在可用的存儲器帶寬內。此外， QTNR上的任務(具有針對存儲器訪問的低優先級)的持續時間的增加 是小到足以包括到這些產生的調度中。
注意，本發明的保護範圍不限於上述實施例。而且本發明的保護 範圍也不受到權利要求中的附圖標記的限制。詞"包括"不排除權利 要求中提到的部分之外的部分。元件前的詞"一"不排除多個該元件。 形成本發明的部分的裝置可以以專用硬體或可編程的通用處理器的形 式來實現。本發明存在於每一個新特徵或特徵的組合中。
權利要求
1.一種在數據處理系統中對至少一個獨佔資源的使用進行調度的方法，所述方法包括為至少兩個任務流預留時間的步驟，所述任務流由所述至少一個獨佔資源執行，所述方法的特徵在於，所述為任務流預留時間的步驟包括-把至少一個調度周期中的第一固定時間單元分配給第一任務流；以及，-把所述至少一個調度周期中的第二固定時間單元分配給第二任務流。
2. 根據權利要求1所述的方法，其中，第一固定時間單元和第二 固定時間單元包括在主調度中，所述主調度用於管理對所述任務流的 預留的調度。
3. 根據權利要求1或2所述的方法，其中，所述任務流由多個獨 佔資源執行。
4. 根據權利要求3所述的方法，其中，所述主調度通過如下步驟 來構建-針對每一個獨佔資源，計算所述任務流中需要所述獨佔資源的 最大時間量；_檢查在所述計算步驟中計算出的最大值之和是否在與一個調度 周期相對應的時間內；_使用所述最大值作為分配給所述任務流的固定時段的持續時間 的下界；-針對最關鍵的任務流，對所述固定時段進行調整； -針對較不關鍵的任務流，重複所述調整步驟。
5. 根據權利要求1所述的方法，其中，第一任務流是主任務流， 第二任務流是子任務流。
6. 根據權利要求5所述的方法，其中，主任務流是主視頻流，子 任務流是子視頻流。
7. —種包括至少一個獨佔資源的數據處理系統，所述數據處理系統被設置為給至少兩個任務流預留時間，其中，所述至少一個獨佔資 源被設置為執行所述任務流，其特徵在於，所述數據處理系統被設置為通過如下步驟而預留時間-把至少一個調度周期中的第一固定時間單元分配給第一任務 流；以及，-把所述至少一個調度周期中的第二固定時間單元分配給第二任 務流。
全文摘要
本發明的目的是改進多任務數據處理系統的性能，該系統中至少一個獨佔資源用於執行至少兩個任務流。根據本發明的方法通過使用所謂的主調度而實現了這個目的，主調度用作構建對單獨任務流進行調度的模板。術語主調度是指針對任務流的獨佔資源的預留集合。
文檔編號G06F9/46GK101189580SQ200680019523
公開日2008年5月28日 申請日期2006年5月31日 優先權日2005年6月3日
發明者亨德裡克·戴克斯特拉, 埃裡克·卡特曼 申請人:Nxp股份有限公司