On-line Scheduling for Multi-processor Fault-tolerance Systems with Multimedia Applications

多核心系統上的線上排程與多媒體應用及容錯問題研究

陳燕萩(Yen-Chiu Chen)

指導教授 ： 石維寬

國立清華大學/電機資訊學院/資訊工程學系/博士(2010年)

摘要

With the popularity of consumer digital products in video, games, and multimedia, the trend toward the multiprocessor architecture in embedded applications has received more and more attention. Most multimedia devices support the main stream of image and audio codec such as H.264, AAC, MPEG-4, VC1, and MP3. System-on-chip (SoC) with integration ability is applied on the mobile media device extensively to solve the complicated situation between the goals of minimizing size and providing portability when each of these technologies is designed individually. To provide more effective integration of hardware and software, Khronos group proposes a unified standard, called OpenMAX which provides flexible layers to cross platforms and accelerate the performance of hardware when the programmers process multimedia codec. In the rst part of this thesis, we implement multimedia codec adopted H.264 decoder by following OpenMAX DL standard on PACDSP platform which is a heterogeneous multiprocessor platform developed by STC/ITRI organization in Taiwan. By following OpenMAX DL Standard, users may easily invoke libraries with regular APIs. In contrast, a multi-threading parallel framework for H.264/AVC video decoder is implemented on ARM11 MPCore which is a homogeneous architecture with single-core to quad-core to express more scalability on multiprocessing platform. This framework can fully utilize resources of a MPCore hardware and achieve the demand of high performance and low power when processing H.264 decoding and has good portability since the parallel decoder is implemented in high-level C code. The experimental result shows that the performance is improved about 3.5 times as compared with the reference software JM15.1 on average.
For the real-time multimedia applications in a distributed environment, each device may contain a part of multimedia information and users can get information processed by another multimedia device by networks. For k kinds of devices (denoted as k partitions) which are classified by the contents of multimedia applications in a distributed environment, the mobile multimedia devices in a distributed environment is illustrated as a graph G = (V,E) and can be reduced to the augmentation problem of an undirected graph with k partitions of its vertices if there are more than two paths between each application pair to pass the distinct decoded information (i.e., decoded information in dierent partition ) for each other. We propose a simple linear-time algorithm to add a set of edges and maintain the original partition constraint, and then we get a 2-edge-connected graph for the given distributed environment.
Finally, a power-aware real-time issue for real-time multimedia applications in a distributed environment is addressed in the third part of this thesis. For a set of real-time multimedia applications in a distributed environment, a periodic application (denoted as a periodic task) has two-level computation time with respect to dierent voltages. We provide a schedulability bound of the RM schedulability test when given a task T, the utilization of the lowest priority task, and the maximum utilization of all tasks, T is schedulable upon m processors if the total utilization of T does not exceed u_n+(2-sqr(2u_max+2))*m. If the corresponding utilization is less than or equal to u_n+(2-sqr(2u_max+2))*m, the low-level voltage model is chosen and this model can be adequately analysis the scheduling problems with energy and real-time issues for developing the applications on modern embedded SoCs.

關鍵字

即時系統 ； 線上排程演算法 ； 多核心系統 ； 多媒體應用

並列摘要

有鑒於近年來影音、遊戲及多媒體應用軟體的發展快速及盛行，分散式多核心平台所提供的多核心處理已蔚為一風尚。現存的行動多媒體裝置大多結合較主流的影像和音訊編解碼標像是H.264, AAC, MPEG-4, VC1, 及MP3，及在多媒體裝置平台上加入GSM、GPRS、3G或WiMAX等通訊標準以達到分散式環境中資訊的互相傳輸與聯繫。然而，不管是多媒體的編解碼或通訊協定上的技術，皆需要多種處理能力及複雜的電路設計，因此整合各種多媒體解碼能力的SoC被廣泛應用在行動多媒體裝置，以達到體積小、攜帶方便的目標。
有別於單核心架構，多核心平台的行為更為複雜。為提供更具彈性的軟體與硬體的整合，Khronos group 提出了一個整合軟體與硬體層級標準，稱之為OpenMAX 。本論文的第一個部分即在工研院所研發的PACDSP異質多核心平台上，實作遵循OpenMAX DL標準的H.264解碼器，提供應用軟體開發者及多媒體編解碼使用者可藉由呼叫設計出來的函式庫，更方便的與底層的硬體平台溝通，並且讓硬體效能發揮的更好及提高系統開發的移植性。在同質多核心平台的架構下，本論文另提出一個利用多執行緒 (multi-threading) 方式將H.264解碼於四顆核心的ARM 11 MPCore平台上做一平行解碼。此平台可以有效的運用多核心硬體上的資源，並得到一個高效能及低電能的需求，並且最終可得到一個良好解碼速度結果。
在行動多媒體裝置功能越來越強大的趨勢下，如何提供兩兩多媒體裝置間不同編解碼的資訊，以減少編解碼資訊的重複計算與系統負擔，本論文提供一個多核心環境中的容錯機制，其利用將不同編解碼資訊的做一分類，將問題專注在如何在不同分類的裝置間，加入最少的連線數目，使得多媒體裝置A到多媒體裝置B之間一條路徑損壞時，仍有一條以上的其他路徑可由多媒體裝置A到達多媒體裝置B以分享不同的編解碼結果。
最後，以整體系統的觀點，本論文提出一個效能 (utilization) 為基礎的系統預測，提供在即時行動多媒體裝置系統下，動態調整系統電壓的機制，以達到省電的功能。利用基本但必要執行時間 (mandatory computation time) 相對應高電壓、而優化但非必要執行時間(optional computation time)相對應低電壓的多層級對應概念，藉由提出一個通用性的線上排程，稱為一leading schedule，以Rate-Monotonic (RM) 演算法為一個例子，計算出在給定的一組任務群組下，若此任務群組的效能總量小於U(T)<=u_min+(2-sqr(2u_max+2))*m，則判斷此任務群組可利用RM演算法被排程於多核心處理器上，並更進一步提供系統使用較低電壓的預測判斷，其中U(T)代表所給定的任務群組的效能總量，u_n為該任務群組中優先權最小的效能，u_max為該任務群組中最大的效能，m代表處理器的個數。藉由此系統預測機制，動態調整系統電壓的機制，以達到系統省電之功能。

並列關鍵字

real-time system ； on-line scheduling algorithm ； multiprocessor system ； Multimedia Applications

參考文獻

[3] Nabil R. Adam and John C. Worthmann. Security-control methods for statistical databases: a comparative study. ACM Computing Surveys, 21(4):515-556,1989.

[5] Theodore P. Baker. An analysis of xed-priority schedulability on a multiprocessor. Real-Time System, 32(1-2):49-71, 2006.

[6] JOrgen Bang-Jensen, Harold N. Gabow, and Tibor Jordan. Edge-connectivity augmentation with partition constraints. SIAM Journal on Discrete Mathematics, 12(2):160-207, 1999.

[7] Sanjoy K. Baruah. Scheduling periodic tasks on uniform multiprocessors. Information Processing Letters, 80(2):97-104, 2001.

[8] Sanjoy K. Baruah and Joel Goossens. Rate-monotonic scheduling on uniform multiprocessors. IEEE Transactions on Computers, 52(7):966{970, 2003.