臺灣博碩士論文加值系統

雖然在異質嵌入式平台上，多核心硬體已經逐漸普以支援運算量增長的應用軟體，但是仍缺乏有效率的系統軟體用於協助開發人員平行化單執行序程式，尤其是平行運算的執行單元間資料傳輸與溝通向來是個難解的議題。因此，建立於主從式程式開發架構下並引進資料串流的概念，提出名為「遠端串流程序呼叫」的資料溝通機制用來描述運行於不同執行單元上程式區塊串流資料之溝通行為。但是遠端串流程序呼叫的主要技術為提供資料緩衝區，因此系統可供使用的記憶體資源變成為影響其便利性與效能的重要因素。運行系統可以負擔的串流管道數將會被硬體架構的特性所侷限，這將會造成預料外的開發限制，並且在處理需要超過限定的串流管道以在平行程式間傳輸資料具有複雜行為的程式，也會提高平行此類應用程式的困難度。
在這篇論文中，建立在遠端串流程序呼叫機制上提出並虛擬通道的概念，用於增加其適用性與機動性和減少使用此多核心程式開發模型時的限制。為消除嵌入式系統所能提供的記憶體資源限制，虛擬通道有別於原先的串流通道與物理資源不再是單一對應關係，取而代之的則是多對一的運作模式。因此支援虛擬通道機制須在原先的軟體架構上新增資源分配元件，達到在串流通到間資源共享的目的；資源分配元件會依據不同目的所設計之調度演算法以滿足虛擬通道需要傳送串流資料時的需求。此份研究報告中將詳細描述虛擬通道的實作，以及在開發過程中所遭遇的困難；並且闡述根據不同需求，例如：延遲時間、系統效率個別設計的演算法，以便於資源分配元件能根據不同的需求回復請求。在TI OMAP5912異質雙核心平台上實驗設計的演算法，並經由實驗結果展示採用不同演算法時虛擬通道的行為的差異性。

Although hardware support for parallel computation is increasingly available in heterogeneous embedded platforms,
there is a distinct lack of effective system software support. One of the most significant challenges is communication between various computing elements for parallel implementation. Therefore, a data communication mechanism called streaming RPC was proposed to provide a system for modeling data streaming based on the client-server programming paradigm. As streaming RPC is based on the technique of buffering, the memory sub-system becomes a key factor affecting the facilities and performance. Because the number of streaming channels that a system can sustain are constrained by the architecture characteristics, this sets a limitation and raises difficulty when developing complex applications that need the amounts of channel over the bound to transmit data between program partitions.

In this thesis, a concept of virtual streaming channels is proposed to increase the applicability and flexibility of streaming RPC. To eliminate the limitation caused by physcial resources, a block of memory called partition is shared by several virtual channels for transmition. The implementation of virtual channels mechanism is explained.
The partition scheduler aims to schedule the arrived requirement of virtual channels with efficient policies respecting to response time requirements, and channel throughput. Therefore the dispatching strategis, latency-aware and throughput-aware scheduling is designed to satisfy different requirements. Furthermore, the partition scheduler applies different scheduling algorithms based on various concerns is also discussed. Finally, experimental results demonstrates the usage of the proposed methodology actually increases the flexibility of modified streaming RPC. Additionally, comparison results illustrating the differences between proposed scheduling policies and are given of each designed experiments. According to experiments, the latency-aware scheduling dispatchs the physcial partitoin with shortest response time. Moreovers, throughput-aware scheduling balances between latency and performance effectively.

Abstract
Contents
List of Figures
List of Tables
1 Introduction
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 System Overview
2.1 Dual-Core Programming Model . . . . . . . . . . . . . . . . . 6
2.2 An Micro Operating System: pCore . . . . . . . . . . . . . . . 8
2.3 Communication Libraries: pCore Bridge . . . . . . . . . . . . 8
2.4 Streaming RPC . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Virtual Streaming Channel
3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Modi‾ed Software Frameworks . . . . . . . . . . . . . . . . . . 14
3.3 Implementation of Virtual Channels . . . . . . . . . . . . . . . 17
3.3.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . 17
3.3.2 Implementation and Execution Flow . . . . . . . . . . 18
4 Scheduling Policies of Scheduler
4.1 Priority-aware handoff scheduling . . . . . . . . . . . . . . . . 23
4.2 Latency-aware handoff scheduling . . . . . . . . . . . . . . . . 25
4.3 Throughput-aware handoff scheduling . . . . . . . . . . . . . . 27
5 Experiments
5.1 Results of Response-Time Aware Schedulings . . . . . . . . . 30
5.2 Executed outcome of Throughput-Aware Policies . . . . . . . 32
5.3 Parameter Analysis of TaH Scheudling . . . . . . . . . . . . . 35
6 Conclusion
6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Bibliography

[1] Ian Buck, Tim Foley, Daniel Horn, Jeremy Sugerman, Kayvon Fatahalian, Mike Houston, and Pat Hanrahan. Brook for gpus: Stream computing on graphics hardware. ACM Transactions on Graphics, 23(3):777{786, 2004.
[2] Shane Ryoo, Christopher I. Rodrigues, Sara S. Baghsorkhi, Sam S. Stone, David B. Kirk, and Wen-mei W. Hwu. Optimization principles and application performance evaluation of a multithreaded gpu using cuda. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pages 73{82, New York, NY, USA, 2008. ACM.
[3] Kayvon Fatahalian, Timothy J. Knight, Mike Houston, Mattan Erez, Daniel Reiter Horn, Larkhoon Leem, Ji Young Park, Manman Ren, Alex Aiken, William J. Dally, and Pat Hanrahan. Sequoia: Programming the memory hierarchy. In Supercomputing, 2006. SC '06. Proceedings of the ACM/IEEE SC 2006 Conference, pages 4{4, Nov. 2006.
[4] Ana Varbanescu, Maik Nijhuis, Arturo Gonzalez-Escribano, Henk Sips, Herbert Bos, and Henri Bal. Sp@ce - an sp-based programming model for consumer electronics streaming applications. In Languages and Compilers for Parallel Computing, pages 33{48. 2007.
[5] William Thies, Michal Karczmarek, and Saman Amarasinghe. Streamit: A language for streaming applications. In Proceedings of Computational Complexity, pages 179{196, 2002.
[6] Chih-Chieh Yang, Chung-Kai Chen, Yu-Hao Chang, Kai-Hsin Chung, and Jenq-Kuen Lee. Streaming support for Java RMI in distributed environment. In Proceedings of ACM International Conference on Principles and Practices of Programming In Java, pages 53{61, 2006.
[7] Jayanth Gummaraju, Joel Coburn, Yoshio Turner, and Mendel Rosenblum. Streamware: Programming general-purpose multicore processors using streams. In Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems Architectural Support for Programming Languages and Operating Systems,pages 297{307, 208.
[8] Kun-Yuan Hsieh, Yen-Chih Liu, Po-Wen Wu, Shou-Wei Chang, and Jenq Kuen Lee;. Enabling streaming remoting on embedded dual-core processors. In 37th International Conference on Parallel Processing, pages 35{42, 2008.
[9] Kun-Yuan Hsieh, Yen-Chih Liu, Chi-Hua Lai, and Jenq Kuen Lee. The
support of software design patterns for streaming rpc on embedded mulicore processors. In Proceedings of the 2008 IEEE Workshop on Signal
Processing Systems, 2008.
[10] Texas Instruments. Omap5912 multimedia processor direct memory access (dma) support reference guide.
[11] Nir Shavit and Dan Touitou. Software transactional memory. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 204{213, 1995.
[12] Dave Dice and Nir Shavit. Understanding tradeo®s in software transactional memory. In Proceddings of Internet Symposium on Code Generation and Optimization 2007, pages 21{33, 2007.
[13] David L. Black. Scheduling support for concurrency and in the Mach
operating system. Computer, 23(5):35{43, May 1990.
[14] Texas Instruments. Omap5912 applications processor data manual.