(3.238.130.97) 您好!臺灣時間:2021/05/14 19:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:余士鵬
研究生(外文):Shih-Peng Yu
論文名稱:多核心匯流排與直接存取記憶體之優先權配置
論文名稱(外文):Priority Assignment on the MPSoC with DMAC
指導教授:陳雅淑
指導教授(外文):Ya-Shu Chen
口試委員:陳雅淑
口試委員(外文):Ya-Shu Chen
口試日期:2013-10-03
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電機工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:102
語文別:英文
論文頁數:35
中文關鍵詞:即時系統優先權配置匯流排排程演算法直接存取記憶體控制器仲裁器。
外文關鍵詞:Real time systemPriority assignmentBus schedulingDirect memory ac- cessArbiter
相關次數:
  • 被引用被引用:0
  • 點閱點閱:85
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
現今多核心系統內的應用程式需要存取多顆核心與外部裝置,因此在系統內常配備有匯流排裝置及直接存取記憶體控制器去管理傳輸任務。然而,由於工作具有優先順序的限制以及傳輸衝突的情況,如何針對匯流排與直接存取記憶體控制器進行適當的優先權配置是極具挑戰的問題。本研究提出兩項優先權配置演算法分別可用於靜態仲裁器與動態仲裁器,並提出工作分配演算法去降低傳輸的工作量,還提出一個可排程性測試演算法用以測試具有先後順序限制的工作在系統中的可排程性。本研究的效能分析結果顯示提出的演算法能有效提高系統匯流排使用率與可排程性。
In current multi-core systems, an application is executed in several cores and requires peripheral devices. A system bus arbiter and a direct access memory controller are used for communication management. Because of the precedence constraint between functions and the communication contention between cores, how to find a proper priority assignment for cores and devices becomes challenging. In this work, we propose two priority assignment strategies for fixed-priority and dynamic priority arbiters, respectively. A partition algorithm and a schedulability test are also presented to deal with communication overhead minimization and precedence constraint scheduling. The experimental results
show encouraging results in priority assignment.
1 Introduction 1
2 System Model 3
3 Algorithm 6
3.1 Subtask Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Priority Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.1 Workload-based . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.2 Bandwidth-based . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Schedulability test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Simulated Annealing Algorithm . . . . . . . . . . . . . . . . . . . . . . 16
4 Experiment 18
4.1 Data Sets and Performance Metrics . . . . . . . . . . . . . . . . . . . . . 18
4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.1 Varied system setting . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.2 Varied workload . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2.3 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Conclusion 31
REFERENCES 32
[1] ARM, http://www.arm.com, AMBA AXI Protocol, ver1.0 ed., 2004.
[2] freescale, http://www.freescale.com/, DSP56300 Family Manual, April 2005.
[3] A. Srinivasan and S. Baruah, “Deadline-based scheduling of periodic task systems
on multiprocessors,” Information Processing Letters, pp. 93–98, 2002.
[4] S. Ramamurthy, “Scheduling periodic hard real-time tasks with arbitrary deadlines
on multiprocessors,” in Proceedings of the IEEE Real-Time Systems Symposium,
pp. 59–68, 2002.
[5] K. Kettler, J. Lehoczky, and J. Strosnider, “Modeling bus scheduling policies for
real-time systems,” in Proceedings of the IEEE Real-Time Systems Symposium,
pp. 245–253, 1995.
[6] Y. Wang, D. Liu, Z. Qin, and Z. Shao, “Memory-aware optimal scheduling with
communication overhead minimization for streaming applications on chip multipro-
cessors,” in Proceedings of the IEEE Real-Time Systems Symposium, pp. 350–359,
2010.
[7] D. W. Engels, J. Feldman, D. R. Karger, and M. Ruhl, “Parallel processor scheduling
with delay constraints,” in Proceedings of the twelfth annual ACM-SIAM symposium
on Discrete algorithms, pp. 577–585, 2001.
[8] T. Varvarigou, V. Roychowdhury, T. Kallath, and E. Lawler, “Scheduling in and out
forests in the presence of communication delays,” IEEE Transactions on Parallel
and Distributed Systems, pp. 175–181, July 2003.
[9] J. Verriet, “The complexity of scheduling graphs of bounded width subject to non-
zero communication delays,” IEEE Transactions on Parallel and Distributed Sys-
tems, July 1997.
[10] T. Yang and A. Gerasoulis, “Dsc: scheduling parallel tasks on an unbounded number
of processors,” IEEE Transactions on Parallel and Distributed Systems, pp. 951–
967, Aug. 1994.
[11] K. Guo, J. Li, S. Wu, X. Song, and X. Wu, “Dynamic priority scheduling algo-
rithm to improve real-time of can bus communication,” in Proceedings of the IEEE
Informatics and Management Science IV, pp. 261–268, 2013.
[12] K. Lahiri, A. Raghunathan, and S. Dey, “System-level performance analysis for
designing on-chip communication architectures,” IEEE Transactions on Computer-
Aided Design of Integrated Circuits and Systems, pp. 768–783, 2001.
[13] M. Gasteier and M. Glesner, “Bus-based communication synthesis on system-level,”
in Proceedings of the IEEE International Symposium on System Synthesis, pp. 65–
70, 1996.
[14] J. Baillieul and P. Antsaklis, “Control and communication challenges in networked
real-time systems,” in Proceedings of the IEEE Real-Time Systems Symposium,
pp. 9–28, 2007.
[15] L.-Y. Chiou, Y.-S. Chen, and C.-H. Lee, “System-level bus-based communication
architecture exploration using a pseudoparallel algorithm,” IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, pp. 1213–1223, 2009.
[16] K. Lahiri, A. Raghunathan, and G. Lakshminarayana, “Lotterybus: A new high-
performance communication architecture for system-on-chip designs,” in Proceed-
ings of the annual Design Automation Conference, pp. 15–20, 2001.
[17] P.-C. Hsiu, C.-K. Hsieh, D.-N. Lee, and T.-W. Kuo, “Multilayer bus optimization for
real-time embedded systems,” IEEE Transactions on Computers, pp. 1638–1650,
Sept. 2012.
[18] Y.-S. Chen, H.-L. Tsai, and S.-W. Lo, “Multi-layer bus minimization for soc,” J.
Syst. Softw, pp. 121–132, 2010.
[19] T. yi Huang and J. W. s. Liu, “Worst-case timing analysis of cycle-stealing dma i/o
tasks,” in Proceedings of the annual ACM/IEEE Design, pp. 285–298, 1996.
[20] C.-C. C. Tai-Yi Huang and P.-Y. Chen, “Bounding the execution times of dma i/o
tasks on hard-real-time embedded systems,” in Proceedings of the IEEE Real-Time
and Embedded Computing Systems and Applications, pp. 499–512, 2004.
[21] T.-Y. Huang, J. W. S. Liu, and J. Y. Chung, “Allowing cycle-stealing direct memory
access i/o concurrent with hard-real-time programs,” in Proceedings of the IEEE
Parallel and Distributed Systems, pp. 422–429, 1996.
[22] S. L. M. Joosun Hahn, Rhan Ha and J. W.-S. Liu, “Analysis of worst case dma re-
sponse time in a fixed-priority bus arbitration protocol,” Real-Time Systems, pp. 209
– 238, 2002.
[23] M.-Y. Nam, R. Pellizzoni, L. Sha, and R. Bradford, “Asiist: Application specific i/o
integration support tool for real-time bus architecture designs,” in Proceedings of the
IEEE on Engineering of Complex Computer Systems, pp. 11–22, 2009.
[24] R. Pellizzoni and M. Caccamo, “Impact of peripheral-processor interference on
wcet analysis of real-time embedded systems,” IEEE Transactions on Computers,
pp. 400–415, 2010.
[25] 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 ACM symposium on Applied
computing, pp. 1176–1180, 2007.
[26] C.-Y. Jheng and Y.-S. Chen, “On-line real-time task management for three-
dimensional network on chips,” in Proceedings of the IEEE Anti-Counterfeiting Se-
curity and Identification, pp. 1–5, 2012.
[27] K. Lakshmanan, R. Rajkumar, and J. Lehoczky, “Partitioned fixed-priority preemp-
tive scheduling for multi-core processors,” in Proceedings of the Euromicro Confer-
ence on Real-Time Systems, pp. 239–248, 2009.
[28] H. Chiueh, J. Draper, and J. Choma, Jr., “An efficient list scheduling algorithm for
time placement problem,” Computers and Electrical Engineering, pp. 285 – 298,
2007.
[29] B. Andersson, S. Baruah, and J. Jonsson, “Static-priority scheduling on multipro-
cessors,” in Proceedings of the IEEE Real-Time Systems Symposium, pp. 193–202,
2001.
[30] U. patent: 6157989A, Dynamic bus arbitration priority and task switching based on
shared memory fullness in a multi-processor system. 2000.
[31] U. patent: 6199121B1, High speed dynamic chaining of DMA operations without
suspending a DMA controller or incurring race conditions. 2001.
[32] M. Spuri, G. Buttazzo, and S. S. S. Anna, “Scheduling aperiodic tasks in dynamic
priority systems,” Real-Time Systems, vol. 10, pp. 179–210, 1996.
[33] Y.-S. Chen, C.-S. Shih, and T.-W. Kuo, “Processing element allocation and dynamic
scheduling codesign for multi-function socs,” Real-Time System, pp. 72–104, Mar.
2010.
[34] G. Buttazzo, “A general view,” in Hard Real-Time Computing Systems, vol. 24,
pp. 1–22, 2011.
[35] Y. Zhang and A. Srivastava, “Accurate temperature estimation using noisy thermal
sensors,” in Proceedings of the Annual Design Automation Conference, pp. 472–
477, 2009.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top