現時嵌入式應用系統之開發方法，大多採用軟硬體共同設計法 (codesign)來進行。此方法在系統設計上，先具體描述系統規格(system specification)，再依系統的需求，將功能指定劃分為由軟體或由硬體來加以實現 (hardware/software partitioning)。在軟硬體劃分過程中，由於軟體與硬體在效能及可程式化的程度上有其不同的差異性，因此如何針對系統功能做劃分，使得最後的結果能滿足不同且甚至互相衝突的系統需求，是一個值得深入探討的問題。
　　本論文在軟硬體共同設計上所探討之軟硬體劃分及管線排程演算法，其目的是如何設計符合生產量限制(throughput constraint)及面積限制(area constraint)的多處理器嵌入式系統。本論文利用一個系統描述之系統功能圖(task graph)，先估算系統功能相關之各種因素來做軟硬體劃分，再採用串列排程演算法(list scheduling algorithm)來實現系統功能之管線排程，以達到提升系統效能的目的。在軟硬體重新劃分過程中，考慮了1.系統功能的執行時間，2.系統功能由硬體實現時所佔據面積(area)的大小，以及3.系統功能間通訊時間(communication time)的三項因素，做為軟硬體劃分的依據。而在管線排程中，則將系統功能分配至管線階段中，因此可有效地改善系統效能，且考慮如何將由軟體實現的系統功能，分配至合適的處理器，以達到減少系統成本之目的。
　　實驗結果顯示，本論文所提出的軟硬體劃分及管線排程演算法，應用在設計有生產量需求限制的多處理器嵌入式系統上，的確可以有效地提升系統中處理器之使用率，改善系統效能並減少系統成本之目的。

　In this thesis, we address a codesign approach for throughput-constrained systems which uses iterative partitioning and pipelined scheduling to obtain a high throughput implementation. Given a specification of a throughput-constrained 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 hardware areas and the data communication time. 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 CPUs, and it can improve the processor utilization effectively. The partitioning and pipelined scheduling are executed iteratively 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 to either use faster processors or increase the number of processors when the area constraint is violated.
　We evaluate our solution quality by comparing it with an existing technique. We also conduct a case study of JPEG2000 image compression algorithm to establish the effectiveness of our approach.

[1] G. De Micheli, “Computer-aided hardware-software codesign,” IEEE
Micro, vol. 14, no. 4, pp. 10-16, Aug. 1994.
[2] M. Dorfman and R. H. Thayer, Standards, Guidelines,and Examples on System and Software Requirements Engineering, IEEE Computer Society Press, 1990.
[3] R. Ernst, J. Henkel, and T. Benner, “Hardware-software cosynthesis
for microcontrollers,” IEEE Design & Test of Computers, vol. 10,
no. 4, pp. 64-75, Dec. 1993.
[4] 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.
[5] S. Berger, Embedded Systems Design: An Introduction to Processes,
Tools and Techniques, CMP Books, 2002, ISBN: 1578200733.
[6] A. M. Davis, Software Requirements: Analysis and Specification,
Prentice-Hall, Englewood Cliffs, New Jersey, 1990, ISBN: 0138248141.
[7] J. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt, “Ptolemy: A
framework for simulating and prototyping heterogeneous systems,” Int. J. Computer Simulation, vol. 4, no. 2, pp. 155-182, Apr. 1994.
[8] P. Chou, R. B. Ortega, and G. Borriello, "The chinook hardware/software co-synthesis system," in Proc. Int. Symp. System Synthesis, pp. 22-27, Sept. 1995.
[9] R. K. Gupta and G. D. Micheli, “Hardware-software cosynthesis for
digital systems,” IEEE Design & Test of Computers, vol. 10,
no. 3, pp. 29-41, Sept. 1993.
[10] J. Madsen, J. Grode, P. V. Knudsen, M. E. Petersen, and A.
Haxthausen, ”LYCOS: The Lyngby Co-synthesis System,” J. Design
Automation for Embedded Systems, vol. 2, no. 2, pp. 195-235, Mar. 1997.
[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] 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.

[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] W. H. Wolf, “Hardware-software co-design of embedded systems,”
Proceedings of the IEEE, vol. 82, no. 7, pp. 967-989, July 1994.
[18] 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.
[19] T. C. Hu, “Parallel sequencing and assembly line problems,”
Operations Research, vol. 19, no. 6, pp. 841-848, Apr. 1961.
[20] G. De Micheli, Synthesis and Optimization of Digital Circuits,
McGraw-Hill, New York, 1994, ISBN: 0070163332.
[21] A. Kalavade and P. A. Subrahmanyam, “Hardware/Software
Partitioning for Multifunction Systems,” IEEE Trans.
Computer-Aided Design, vol. 17, no. 9, pp. 819-837, Sept. 1998.
[22] L. Q. Ke, “Hardware-software partitioning in multimedia
applications,” Master thesis, Department of Electrical Engineering,
National Taiwan University, June 2002.