晶片匯流排上之處理元件優先權分配策略

A Priority Assignment Strategy of Processing Elements over an On-Chip Bus

唐松見(Song-Jian Tang)

指導教授 ： 郭大維

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

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

摘要

由於現今多媒體系統單晶片的應用程式數目不斷增加，再加上各應用程式對截限執行時間要求大不相同，如何分配優先權給晶片匯流排上的處理元件變成相當困難的問題。在本篇論文中，我們首先證明當每一個處理元件只能夠有一個優先權時，此優先權分配問題是NP-hard問題。當每一個匯流排資料傳遞單元可以有一個優先權，我們提出一個最佳的優先權分配方法。在處理元件的優先權分配問題上，我們提出一個以退火模擬為基礎的優先權分配策略，以最小化各處理元件上的優先權數目，並且維持所有應用程式的時間要求。藉由實驗的探討，我們提出的方法證明有很好的效能。

關鍵字

晶片匯流排 ； 優先權分配策略

並列摘要

The number of bus transactions in multimedia SoC grows significantly in recent years. Because of different timing requirements for different applications, how to find a proper priority assignment for processing elements (PEs) of SoC becomes very challenging. In this thesis, we first show that the priority assignment problem with one unique priority for each PE is NP-hard. When each bus transaction can have one unique priority, we propose an optimal priority assignment algorithm for a given bus transaction graph. We then propose a priority assignment strategy based on simulated annealing (SA) for PEs, where bus arbitration is done in a priority-driven fashion. The objective is to minimize the number of priorities needed for each PE and to satisfy the performance requirements of applications. The experimental results show some encouraging results in priority assignment.

並列關鍵字

on-chip bus ； priority assignment strategy

參考文獻

[4] L. Benini and G. D. Micheli. Networks on chips: A new soc paradigm. IEEE Computer, pages

for the synthesis of embedded systems. In Design, Automation and Test in Europe, Feb 1998.

[6] T. Givargis and F. Vahid. Platune: a tuning framework for system-on-a-chip platforms. IEEE

Trans. on CAD of Integrated Circuits and Systems, 21(11):1317–1327, 2002.

[8] K. Kettler, J. Lehoczky, and J. Strosnider. Modeling bus scheduling policies for real-time systems.