本論文設計並實作一執行於多處理器核心(Multicore)中特殊處理器(Specific Purpose Processor)上之資料流架構核心(Data Architecture Monolithic Kernel)，並且分析此架構下多媒體應用程式達到服務品質(Quality of Service, QoS)需求之適用性，目的為提供多媒體資料流應用程式適合的作業環境。資料流架構適合應用於裝置控制與多媒體串流的應用程式，此架構下，每一個行程皆為元件導向，並具有可重複使用、以資料驅動的方式工作等特徵。應用程式之功能可以由一個或是數個以上的資料流行程組成，經由資料流的順序不同產生多樣化應用之效果。
本資料流核心設計一個與任務結合的封閉式單體核心，提供基於資料驅動為概念的先進先服務(First Come First Serve)排程之作業環境，採取對稱式訊息傳遞與管理機制，幫助資料流核心與其他處理器核心通訊、分享資料。本資料流核心實作於工業技術研究院(Industrial Technology Research Institute)所開發的PAC Duo異質多處理器核心之PACDSP處理器。資料流核心實現資料流之排程與服務使用者行程，同時建立與其他處理器核心之行程訊息溝通機制(Inter-Process Communication)，使資料流核心與其他處理器核心互相合作。本論文並使用排隊理論分析異質性多處理器核心架構下資料流核心滿足多媒體應用服務品質需求之條件，並利用LabVIEW撰寫此架構之模擬，驗證分析之結果。
本論文設計之架構，主要改變過去特殊處理器只被應用為單一功能之周邊裝置之方式，使其可同時適用多種應用需求，並與其他處理器核心配合，有效提升系統效率與應用範疇。本論文將資料流核心實作於PAC Duo異質多處理器核心平台，讓使用者更方便地開發多媒體應用程式於異質多處理器核心，並經由分析與模擬之結果顯示，資料流核心可適用於其DSP端，提供系統應用開發之另一選擇。

This thesis presents the design and implementation of a monolithic dataflow kernel on a heterogeneous multi-core platform to help provide a simplified execution environment for multimedia applications. Dataflow kernel supports the software architecture of which application control is composed of elementary control objects and data channels, and works in a fire-on-input manner. An application composed of more than one dataflow process might produce variable results while the dataflow changes. In addition to being data-driven, dataflow processes are component-oriented and reusable. When working cooperatively with other system kernel running on a chip-level multiprocessor or multi-core platform, a dataflow kernel can help achieve modularity, flexibility, parallelism, and transparent distributed processing.
The design of this dataflow kernel includes a kernel supporting dataflow architecture and inter-processor communication mechanism. The kernel assumes as its primary functions task scheduling and message passing. Tasks are scheduled to run in the first-come-first-serve manner according to the order of data arrival. There is no preemption on the running task because the notion of priority is not adopted. Message passing is achieved via the inter-processor communication mechanism which provides a symmetric architecture of passing messages and exchanging data across processor boundaries. The target hardware platform used of this implementation is PAC Duo which is developed by Industrial Technology Research Institute (ITRI) for multimedia applications. In this implementation, the dataflow kernel situates on PACDSP core and is responsible for dispatching arriving messages and waking up tasks to execute. For multimedia applications, the conditions of achieving required quality of service (QoS) are analyzed using queuing model. The results are verified by a simulator implemented using LabVIEW.
Dataflow architecture is suitable for applications of control and “data stream”. With this dataflow kernel, software developers are provided more options as well as flexibility. Multimedia applications can be developed in heterogeneous multi-core environment flexibly, effectively, and easily.

[1] Alezander Maxiaguine, Simon Kunzli, Lothar Thiele, and Samarjit Chakraborty, “Evaluating Schedulers for Multimedia Processing on Buffer-Constrained SoC Platforms”, Design and Test of Computers, IEEE, 2004.
[2] Andrew S. Tanenbaum, “Modern Operating System”, 2nd edition, Prentice Hall, 2001, ISBN 0130926418.
[3] Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, “Operating System Principles”, 7th edition, John Wiley & Sons. Inc, 2003, ISBN 0-471-26272-2.
[4] Barry Kauler, “A Tiny Microcontroller Dataflow Kernel”, Microprocessors and Microsystems, Vol. 20, No. 2, 1996, pp. 105-110.
[5] Bishnupriya Bhattacharya and Shuvra S. Bhattacharyya“, Parameterrized Dataflow Modeling for DSP Systems“, IEEE Journals, Vol. 49, Issue 10, 2001.
[6] C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-time Environment”, Journal of the ACM, Vol. 20, No. 1, pp.46-61.
[7] Dataflow, http://en.wikipedia.org/wiki/Dataflow/.
[8] David Reinhardt and Robert C. Maher, “A Real-time DSP Kernel for Concurrent Audio Tasks”, The 105th AES convention, 1998.
[9] Guan-Ying Huang, “The Design and Implementation of Symmetric Message Passing and Massagement Mechanism in Heterogeneous Multi-Core Architecture”, Master’s Thesis, Institute of Computer and Communication Engineering, National Cheng Kung University, July, 2010.
[10] I. Adan and J. Resing. “Queueing Theory”, Lecture notes, Eindhoven University of Technology, Department of Mathematics and Computing Science, Eindhoven,
The Netherlands, 2001.
[11] Industrial Technology Research Institute, “PACDSP V3 Compiler User Guide”, 2008.
[12] Industrial Technology Research Institute, “PACDSP V3 Software Developer’s Manual: Instruction Set Manual”, 2009.
[13] Industrial Technology Research Institute, “PACDSP V3 Software Developer’s Manual: Processor Architecture”, 2009.
[14] Industrial Technology Research Institute, “PACDSP V3 Software Developer’s Manual: Programming Guide”, 2009.
[15] Industrial Technology Research Institute, “PAC Duo Programming’s Reference Guide”, 2009.
[16] Iok-Kong Ao, “The Design and Implementation of a Dataflow Kernel in Heterogeneous Multiprocessor Environment”, Master Thesis, Electrical Engineering, National Cheng Kung University, June, 2005.
[17] Jack B. Dennis, “Data Flow Supercomputers”, IEEE, 1980.
[18] Jean J. Labrosse, “MicroC/OS-II: The Real-time Kernel”, 2nd edition, CMP Books, ISBN 1578201039, 2002.
[19] J. Guo, S. Edwards, and D. Boroyevich, “Elementary Control Object: Toward a Dataflow Architecture for Power Electronics Control Software”, In Proc. IEEE 33rd Annual Power Electronics Specialists Conf. (PESC 2001), June 2002.
[20] Jian-Hong Liu, “A Micro-Kernel for Embedded System with Heterogeneous Multiprocessors”, Master Thesis, National Cheng Kung University, 2004.
[21] Jochen Liedtke, “Toward Real Micro-Kernels”, Communications of ACM, Vol.39, issue 9, p.70-p.77, September, 1996.

[22] Jochen Liedtke, “Micro-Kernels Must and Can Be Small”, 5th IEEE International Workshop on Object-Orientation in Operating Systems, pp. 152-155, October, 1996.
[23] John D. C. Little, “A Proof For The Queuing Formula: L=λW”, Operations Research, Vol. 9, No. 3, pp. 383-387, 1961.
[24] John L. Hennessy, David A. Petterson, “Computer Architecture”, Third edition, Morgan Kaufmann, ISBN 1-55860-596-7, 2003.
[25] Kahn Process Networks, http://en.wikipedia.org/wiki/Kahn_process_networks/.
[26] Kun-Yuan Hsieh, Shou-Wei Chang, Yen-Chih Liu, and Jenq Kuen Lee, “pCore: A Runtime Kernel Design for SPU on Dual-core Processors”, in Proceedings of Workshop on Compiler Techniques for High Performance Computing (CTHPC), 2008.
[27] Kun-Yuan Hsieh, Yung-Chia Lin, and Jenq Kuen Lee, “Enhancing Microkernel Performance on VLIW DSP Processors via Multiset Context Switch”, Journal of VLSI Signal Processing Systems, Special Issue on Design and Programming Signal Processors for Multimedia, 2008.
[28] Kung-Ming Chi, Kuo-Cheng Lee, Pao-Jui Huang, Chou-Kun Lin, “System Interconnect Bandwidth Analysis of PAC Duo SoC”, SoC Technical Journal, 2008.
[29] Kuljeet Singh, “Design and Evaluation of an Embedded Real-time Micro-kernel”, Master Thesis, Computer Science and Applications, Virginia Polytechnic Institute and State University, 2002.
[30] Little’s Law, http://en.wikipedia.org/wiki/Little's_law/.

[31] Luca Abeni, Giorgio Buttazzo, Scuola Superiore, S. Anna, “Integrating Multimedia Applications in Hard Real-Time Systems”, IEEE Real-Time Systems Symposium, 1998.
[32] M. Spuri and G. Buttazzo, “Scheduling Aperiodic Tasks in Dynamic Priority Systems”, Real-Time Systems, 1996.
[33] Queuing Theory, http://en.wikipedia.org/wiki/Queueing_theory/.
[34] Queuing Theory for Embedded Systems Designers, http://www. kalinskyassociates.com/Wpaper5.html/.
[35] Sholin kyo, Satoshi Sekiguchi and Mitsuhisa Sato, “Data Stream Control Optimization in Dataflow Architectures”, ACM Proceedings of the 7th International Conference on Supercomputing, 1993.
[36] Texas Instruments, “DSP/BIOS Technical Overview”, Literature Number: SPRU369, November 1999.
[37] Wen-Bin Hong, “Design and Implementation of Embedded Micro-Kernel System”, Master’s Thesis, Electrical Engineering, National Cheng Kung University, June, 2005.
[38] Yi-Hsiu Liu, “An Adaptive Scheduling Framework for Real-time Operating System to support Tasks with Diverse Time Constraints”, Master Thesis, Department of Computer Science and Information Engineering, National Chung Kung University, July, 2003.