臺灣博碩士論文加值系統

現今多核心系統內的應用程式需要存取多顆核心與外部裝置，因此在系統內常配備有匯流排裝置及直接存取記憶體控制器去管理傳輸任務。然而，由於工作具有優先順序的限制以及傳輸衝突的情況，如何針對匯流排與直接存取記憶體控制器進行適當的優先權配置是極具挑戰的問題。本研究提出兩項優先權配置演算法分別可用於靜態仲裁器與動態仲裁器，並提出工作分配演算法去降低傳輸的工作量，還提出一個可排程性測試演算法用以測試具有先後順序限制的工作在系統中的可排程性。本研究的效能分析結果顯示提出的演算法能有效提高系統匯流排使用率與可排程性。

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.