本論文設計並實作一個應用於多處理器系統的開發方法，在設計產品時通常可以分為軟體跟硬體兩大部分來考慮，由於硬體的成本較高，所以設計者通常會希望大部分的功能可以用軟體的方式來實現，只有那些比較耗費運算能力及具執行時間上限制的功能才由硬體實現。而在硬體架構上，目前則較傾向於使用異質多處理器(Heterogeneous Multiprocessor)來實現這些設計。本論文在應用系統設計上，先根據一具體描述應用系統功能圖(Task graph)，再依各系統功能的需求，將功能指定劃分至由主要處理器(Master Processor)所分派之副處理器(Slave Processor)來加以實行。
　　本論文利用一描述應用系統之系統功能圖(task graph)，先估算系統功能相關之各種因素來做軟硬體之劃分，再採用串列排程演算法(list scheduling algorithm)來實現各系統功能之管線排程，以達到實現應用系統效能的目的。而在軟硬體重新劃分過程中，考慮了1.系統功能的執行時間(executing time)，2.系統功能經由管線排程之多核處理器(Multi-core)(例如:ASIC or DSP等等)，以及3.系統功能間資料存取時間(Data Access time)的三項因素，做為劃分與實現的依據。實驗結果顯示，本論文所提出的應用系統功能分割及管線排程分配演算法，應用在設計異質多處理器之嵌入式應用系統上，可以設計出符合多數人在考慮較低代價的情況下所能得到得最接近之最佳解。

In this thesis, we present how to design a approach on a SOC of heterogeneous multiprocessors. Given a specification of a task-graph system, we synthesize a distributed multiprocessor architecture and allocate processes to the CPUs and ASIC such that the allocation and pipelined scheduling meet the throughput constraint, while the hardware area is minimized. The goal of our work is to minimize the hardware area and to reduce the system cost by increasing the processor utilization.
In the partitioning process, we partition the system functionality into software and hardware based on its three properties: the execution time, the data access time and the heterogeneous multiprocessor cost. In order to capture these three properties, we calculate a set of estimation functions. By following these functions, we generate a candidate partition. The candidate partition will be evaluated by generating its pipelined schedule. In the pipelined scheduling process, we use a list based scheduling algorithm to divide the design into concurrently executing stages. The pipelined scheduling increases the effective data rate of the system. In the scheduling, we address an approach for allocating the processes which are executed as software to the processors, and it can improve the processor utilization effectively. The partitioning and pipelined scheduling are executed repeatedly to obtain a system design that satisfies the throughput and area constraints. We also improve the system performance by modifying the processor allocation in the system instead of using faster processors or increase the number of processors, that can let us get the better performance with lower cost .

[1] B. P. Dave and N. K. Jha, “COHRA: Hardware-software co-synthesis of hierarchical heterogenous distributed embedded systems,” IEEE Trans. Computer-Aided Design, vol. 17, no. 10, pp. 900-919, Oct. 1998.
[2] D. D. Gajski, F. Vahid, S. Narayan, and J. Gong, Specification and Design of Embedded Systems, Prentice-Hall, Englewood Cliffs, New Jersey, 1994, ISBN: 0131507311.
[3] F. Balarin, L. Lavagno, P. Murthy, and A. Sangiovanni-Vincentelli, “Scheduling for embedded real-time systems,” IEEE Design & Test of Computers, vol. 15, no. 1, pp. 71-82, Jan. 1998.
[4] Hu Yue-li; Ding Qian;” Design of an architecture for multiprocessor system-on-chip (MPSoC)” High Density Microsystem Design and Packaging and Component Failure Analysis ,2006. HDP'06. Conference on 2006 Page(s):63 - 66 Digital Object Identifier 10.1109/HDP.2006.1707566
[5] Karam S. Chatha and Ranga Vemuri, “Hardware-software
partitioning and pipelined scheduling of transformative applications,” IEEE Trans. VLSI Systems, vol. 10, no. 3, pp. 193-208, June 2002.
[6] Kuang, J.B.; Buchholtz, T.C.; Dance, S.M.; Warnock, J.D.; Storino, S.N.; Wendel, D.; Bradley, D.H.; “The design and implementation of double-precision multiplier in a first-generation CELL processor” Integrated Circuit Design and Technology, 2005. ICICDT 2005. 2005 International Conference on 9-11 May 2005 Page(s):11 - 14 Digital Object Identifier 10.1109/ICICDT.2005.1502577
[7] Kumar, R.; Tullsen, D.M.; Jouppi, N.P.; Ranganathan, P.; ”Heterogeneous chip multiprocessors” Computer Volume 38, Issue 11 Nov. 2005 Page(s):32 - 38 Digital Object Identifier 10.1109/MC.2005.379
[8] Loukil, K.; Amor, N.B.; Aoudni, Y.; Abid, M.; “Design of Real Time Multiprocessor System on Chip” International Design and Test Workshop, 2007 2nd 16-18 Dec. 2007 Page(s):126 - 129Digital Object Identifier .1109/IDT.2007.4437444
[9] R. P. Dick and N. K. Jha, “MOGAC: A multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems,” IEEE Trans. Computer-Aided Design, vol. 17, no. 10, pp. 920-935, Oct. 1998.
[10] Salice, F. (Politecnico di Milano, DEI); Del Vecchio, L.; Pomante, L.; Fornaciari, W. “Partitioning of embedded applications onto heterogeneous multiprocessor architectures” Proceedings of the ACM Symposium on Applied Computing, 2003, p 661-665
[11] S. Prakash and A. C. Parker, ”SOS: Synthesis of application-specific heterogeneous multiprocessor systems,” J. Parallel and Distributed Computing, vol. 16, no. 4, pp. 338-351, Dec. 1992.
[12] S. Bakshi and D. D. Gajski, “Partitioning and pipelining for performance-constrained hardware/software systems,” IEEE Trans. VLSI Systems, vol. 7, no. 4, pp. 419-432, Dec. 1999.
[13] Seng Lin Shee; Parameswaran, S., “Design Methodology for Pipelined Heterogeneous Multiprocessor System” Design Automation Conference, 2007. DAC '07. 44th ACM/IEEE 4-8 June 2007 Page(s):811 - 816 Digital Object Identifier 10.1109/DAC.2007.375276
[14] Shiann-Rong Kuang; Chin-Yang Chen; Ren-Zheng Liao; ” Partitioning and pipelined scheduling of embedded system using integer linear programming”, Parallel and Distributed Systems, 2005. Proceedings. 11th International Conference on Volume 2, 20-22 July 2005 Page(s):37 - 41 Vol. 2
[15] Srinivasan, Krishnan；Chatha, Karam S. “Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints”Integration, the VLSI Journal, v 40, n 3, April, 2007, p 326-354
[16] Strik, M.T.J.; Timmer, A.H.; van Meerbergen, J.L.; van Rootselaar, G.-J.; “Heterogeneous multiprocessor for the management of real-time video and graphics streams” Solid-State Circuits, IEEE Journal of Volume 35, Issue 11, Nov. 2000 Page(s):1722 - 1731 Digital Object Identifier 10.1109/4.881220
[17] T. C. Hu, “Parallel sequencing and assembly line problems,” Operations Research, vol. 19, no. 6, pp. 841-848, Apr. 1961.
[18] Tanenbaum, A.S. ”Moden Operating Systems ”, 2nd edition, Prentice Hall ,2001, ISBN 0130926418
[19] W. H. Wolf, “Hardware-software co-design of embedded systems,”Proceedings of the IEEE, vol. 82, no. 7, pp. 967-989, July 1994.
[20] Y. Li and W. H. Wolf, “Hardware/software co-synthesis with memory hierarchies,” IEEE Trans. Computer-Aided Design, vol. 18, no. 10, pp. 1405-1417, Oct. 1999.