多媒體嵌入式系統之並行排程與成本最佳化設計

Allocation Cost Minimization and Pipelined Scheduling for Multimedia Embedded System Design

鄧智鴻(Chih-Hung Teng)

指導教授 ： 施吉昇

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00603

摘要

多媒體消費性電子產品非常普及，多數的嵌入式系統都有多媒體工作在其上運行。因此如何做出具有足夠的運算能力且低成本的多媒體嵌入式系統是非常重要的議題。由於不同運算單元擅長執行的項目不同，現在的趨勢是使用多種不同的運算單元來組成嵌入式系統。然而在異質多運算單元的考量下，設計多媒體嵌入式系統並且讓成本最佳化是非常困難的問題。過去的研究有發明一些方法來解決這個問題並且有不錯的表現，但它們並沒有考慮管線設計的可能性。本篇研究提出了一個演算法，它將管線設計列入考量，設計出低成本且有足夠運算能力的多媒體嵌入式系統設。管線設計的概念是使獨立的工作平行地的運作，這放寬了每一個工作的回應時間的限制，並且使得成本可以更進一步地降低。我們做了各種模擬實驗，結果數據都顯示出我們所提供的設計方法可以得出相當好的系統設計。同時顯示了，比起不考量管線設計，將管線設計列入考量確實在各方面都有更進一步的改善。

關鍵字

軟硬體分割 ； 硬體成本最佳化 ； 管線設計 ； 多媒體 ； 嵌入式系統

並列摘要

Multimedia electronic products are very popular now, and most of the embedded systems run multimedia tasks. Designing multimedia embedded systems with sufficient processing power and low allocation cost in hardware/software co-design flow is important to designers. It is a trend to use multi-PE for a multimedia task, because different PEs are good at executing different functionalities. However, allocation cost minimization problem for multimedia tasks in heterogeneous multi-PE embedded systems is a NP-hard problem. Previous work achieve good performance in this problem under consideration of sequential execution. However, we propose a approach to solve this problem under consideration of pipelined schedule, which can be used to exploit the benefit of parallel execution to relax the constraint of the response time and further reduce the allocation cost. The experimental results show that our approach could derive solutions with allocation costs close to those of optimal solutions. Moreover, our approach achieves lower cost and can handle all legal input instances than those who only consider sequential execution, because the pipelined schedule is taken into consideration.

並列關鍵字

HW/SW partition ； allocation cost minimization ； pipelined schedule ； multimedia task ； embedded system

參考文獻

[1] R. J. M. Rim and R. D. Leone, “Optimal allocation and binding in high-level synthesis,”

[2] J. G. DAmbrosio and X. Hu, “Configuration-level hardware/software partitioning

for real-time systems,” in Proc. Int. Workshop Hardware-Software Co-Design,

pp. 34–41, 1994.

IEEE, 1997.