簡易檢索 / 詳目顯示

回結果列表
研究生： 吳旻修
Min-shiou Wu
論文名稱： 多核心匯流排最佳化配置與即時排程合成
Real-time Task Allocation and Scheduler Synthesis for Multi-core Bus Systems
指導教授： 陳雅淑
Ya-Shu Chen
口試委員: 張立平
Li-Pin Chang
張原豪
Yuan-Hao Chang
謝仁偉
Jen-Wei Hsieh
學位類別： 碩士
Master
系所名稱： 電資學院 - 電機工程系
Department of Electrical Engineering
論文出版年： 2011
畢業學年度： 99
語文別： 中文
論文頁數： 41
中文關鍵詞： 嵌入式多核心系統 、匯流排傳輸成本 、優先順序限制 、最佳化配置 、優先權設定
外文關鍵詞： Embedded multi-core system, Bus communication cost, Precedence constraint, Allocation, Prioirty setting
相關次數： 點閱：240  下載：4 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 目前的嵌入式系統大多實現為多核心系統，多核心透過匯流排傳遞訊息與資料，造成匯流排成為效能瓶頸。然而，空間成本的考量下，匯流排在系統中的個數不可太多；為了減少匯流排上的傳輸成本，本論文針對多核心相依行程提出了最佳化配置方法，使用CUS (Constant Utilization Server)解決優先順序限制的問題，並發表相對應的可排程測試，最後利用模擬退火演算法，透過實驗數據得知本論文所提出的方法可以有效地減少在匯流排上的傳輸成本 。

    Many embedded systems are equipped with multi-cores to serve multiple applications with real-time constraints. Cores are communicated with each other by bus, and thus, bus becomes the performance bottleneck for such system. We propose an optimal task allocation to reduce the communication cost among cores. The constant utilization server is used to schedule tasks with precedence constraints between cores to meet the timing constraint. The scheudulability test and priority setting to co-schedule task executions and communications are also presented in this paper. A simulated annealing algorithm is proposed for task allocation and compared with heuristics-based algorithms to provide further insights for system designers. The capability of the proposed methodology is evaluated by a series of experiments, for which encouraging results were presented.

    1 緒論 1 1.1 研究動機與目的 1 1.2 研究背景 1 1.3 論文架構 2 2 相關研究 3 3 理論模型 6 3.1 硬體架構 6 3.2 軟體架構與行程模型 6 3.3 問題定義 8 4 排程演算法 10 4.1 問題描述 10 4.2 CUS設定 11 4.3 排程演算法 12 4.4 模擬退火法 17 5 實驗結果 20 5.1 實驗環境 20 5.1.1 TGFF 20 5.1.2 排程方法實作 22 5.2 實驗設定 23 5.3 實驗結果 25 5.3.1 時間比較 25 5.3.2 Degree變異 26 5.3.3 Chain實驗 32 5.3.4 迭代實驗 33 5.3.5 可排程測試實驗 35 5.3.6 總結 36 6 結論與未來展望 38

    [1] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol. 20, pp. 46–61, January 1973.
    [2] Y.-S. Chen, H.-L. Tsai, and S.-W. Lo, “Multi-layer bus minimization for soc,” J. Syst. Softw., vol. 83, January 2010.
    [3] H. Aydin and Q. Yang, “Energy-aware partitioning for multiprocessor real-time systems,” in Proceedings of the 17th International Symposium on Parallel and Distributed Processing, IPDPS ’03, (Washington, DC, USA), pp. 113.2–, IEEE Computer Society, 2003.
    [4] J. Yu, Q. Zhou, and J. Bian, “Peak temperature control in thermal-aware behavioral synthesis through allocating the number of resources,” in Proceedings of the 2009 Asia and South Pacific Design Automation Conference, ASP-DAC ’09, (Piscataway, NJ, USA), pp. 85–90, IEEE Press, 2009.
    [5] W. Zhang, G.-M. Du, Y. Xu, M.-L. Gao, L.-F. Geng, B. Zhang, Z.-Y. Jiang, N. Hou, and Y.-H. Tang, “Design of a hierarchy-bus based mpsoc on fpga,” in ICSICT’06. 8th International Conference on Solid-State and Integrated Circuit Technology, pp. 1966–1968, 2006.
    [6] ARM, http://www.arm.com, AMBATM Specification, ver2.0 ed., 1999.
    [7] IBM, http://www.ibm.com, TheCoreConnect
    TM Bus Architecture, 1999.
    [8] D.W. Engels, J. Feldman, D. R. Karger, andM. Ruhl, “Parallel processor scheduling with delay constraints,” in Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, (Philadelphia, PA, USA), pp. 577–585, Society for Industrial and Applied Mathematics, 2001.
    [9] T. A. Varvarigou, V. P. Roychowdhury, T. Kailath, and E. Lawler, “Scheduling in and out forests in the presence of communication delays,” IEEE Trans. Parallel Distrib. Syst., vol. 7, pp. 1065–1074, October 1996.
    [10] J. Verriet, “The complexity of scheduling graphs of bounded width subject to nonzero communication delays,” 1997.
    [11] T. Yang and A. Gerasoulis, “Dsc: scheduling parallel tasks on an unbounded number of processors,” IEEE Transactions on Parallel and Distributed Systems,, vol. 5, pp. 951–967, sep 1994.
    [12] C. Philippe, C. Edward, L. J. Karel, and L. Zhen, “Scheduling theory and its applications,” pp. xv, 365 p. :, John Wiley & Sons Ltd., 1995.
    [13] N. Guan, M. Stigge, W. Yi, and G. Yu, “Fixed-priority multiprocessor scheduling with liu and layland’s utilization bound,” in Proceedings of the 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS ’10, (Washington, DC, USA), pp. 165–174, IEEE Computer Society, 2010.
    [14] X. Qi, D. Zhu, and H. Aydin, “A study of utilization bound and run-time overhead for cluster scheduling in multiprocessor real-time systems,” in Embedded and Real-Time Computing Systems and Applications (RTCSA), 2010 IEEE 16th International Conference on, pp. 3 –12, aug. 2010.
    [15] J. Lopez, M. Garcia, J. Diaz, and D. Garcia, “Worst-case utilization bound for edf scheduling on real-time multiprocessor systems,” Euromicro Conference on Real-Time Systems, vol. 0, p. 25, 2000.
    [16] Y. Oh and S. H. Son, “Allocating fixed-priority periodic tasks on multiprocessor systems,” Real-Time Syst., vol. 9, pp. 207–239, November 1995.
    [17] O. U. P. Zapata and P. M. Alvarez, “Edf and rm multiprocessor scheduling algorithms: Survey and performance evaluation,” September 2004.
    [18] R. Davis and A. Burns, “Priority assignment for global fixed priority preemptive scheduling in multiprocessor real-time systems,” in Real-Time Systems Symposium, RTSS 2009. 30th IEEE, pp. 398–409, dec. 2009.
    [19] G. Buttazzo, E. Bini, and Y. Wu, “Partitioning parallel applications on multiprocessor reservations,” in Euromicro Conference on Real-Time Systems (ECRTS), 2010 22nd, pp. 24–33, july 2010.
    [20] X. Qi, D. Zhu, and H. Aydin, “A study of utilization bound and run-time overhead for cluster scheduling in multiprocessor real-time systems,” in Proceedings of the 2010 IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA ’10, (Washington, DC, USA), pp. 3–12, IEEE Computer Society, 2010.
    [21] B. D. Bui, R. Pellizzoni, D. K. Chivukula, and M. Caccamo, “Real-time communication for multicore systems with multi-domain ring buses,” in Proceedings of the 2010 IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA ’10, (Washington, DC, USA), pp. 23–32, IEEE Computer Society, 2010.
    [22] P.-C. Hsiu, D.-N. Lee, and T.-W. Kuo, “Multi-layer bus optimization for real-time task scheduling with chain-based precedence constraints,” in Real-Time Systems Symposium, 2009, RTSS 2009. 30th IEEE, pp. 479–488, dec. 2009.
    [23] R. Dick, D. Rhodes, and W. Wolf, “Tgff: task graphs for free,” in Proceedings of the Sixth International Workshop on Hardware/Software Codesign, 1998. (CODES/CASHE ’98), pp. 97–101, mar 1998.
    [24] Y.-S. Chen, S.-J. Tang, and S.-W. Lo, “A priority assignment strategy of processing elements over an on-chip bus,” in Proceedings of the 2007 ACM symposium on Applied computing, SAC ’07, (New York, NY, USA), pp. 1176–1180, ACM, 2007.
    [25] M. Spuri and G. C. Buttazzo, “Scheduling aperiodic tasks in dynamic priority systems.,” Real-Time Systems.
    [26] E. L. Johnson, A. Mehrotra, and G. L. Nemhauser, “Min-cut clustering,” Mathematical Programming, vol. 62, no. 1-3, pp. 133–151, 1993.
    [27] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.

    QR CODE