透過您的圖書館登入
IP:18.219.123.84
  • 學位論文

系統晶片上之多層匯流排最佳化問題

Multilayer Bus Minimization Problems for SoC Systems

指導教授 : 郭大維

摘要


隨著市場需求及製程技術的進步,嵌入式系統開始整合數個處理單元於單一晶片中,當此架構被大量採用時,系統效能除了受限於處理器的計算能力之外,也受限於系統匯流排的資料傳輸能力。為了讓系統能同時滿足各工作時間上的限制,使用多層匯流排架構成為目前設計系統匯流排的主流趨勢,然而採用多層匯流排卻會增加系統成本;因此,如何配置系統匯流排成為學者們關注的研究議題。在本論文中,我們從各方面探索多層匯流排最佳化的相關問題,首先我們提出,在特定理想的假設前提下所存在的P-Time解法,之後證明這些問題在實際應用的限制下,會形成NP-Hard的問題。最後我們提出一個模擬退火的演算法,並設計實驗將其與一些常用的啟發式演算法進行比較,實驗中包含各種不同工作量的分析,以及一個實際系統的應用。本論文成果在多層匯流排最佳化的問題上,可提供系統開發者更進一步的認識及想法。

並列摘要


The deployment of multiple processing elements, such as a microprocessor or DSP's, in embedded systems often result in significant communication overheads. How to resolve the communication problems and, at the same time, satisfy the timing constraints in job executions is very challenging. In this paper, we explore multi-layer bus minimization problems by identifying factors that contribute to NP-hardness of the problems. We first present problems with efficient algorithms and then NP-Hard problems. A simulated annealing algorithm is also proposed to serve as a comparison with heuristics-based algorithm to provide insights in system designs. A series of extensive simulation experiments and a case study are presented to provide insights and comparisons among different approaches.

參考文獻


[5] M. Caldari, M. Conti, M. Coppola, P. Crippa, S. Orcioni, L. Pieralisi, and C. Turchetti. System-level power analysis methodology applied to the amba ahb bus. In DATE, pages 20032–20039, 2003.
[8] M. R. Garey and D. S. Johnson. Computers and Intractability : A Guide to the Theory of NP-Completeness. W. H. Freeman, January 1979.
[9] R. K. Gupta and G. D. Micheli. Hardware-software cosynthesis for digital systems. IEEE Design & Test of Computers, 10(3):29–41, 1993.
[10] T. C. Hu. Parallel sequencing and assembly line problems. Operations Research, 9(6):841–848, 1961.
on Asia South Pacific design automation, 2001.

延伸閱讀