請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31414完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 施吉昇(Chi-Sheng Shih) | |
| dc.contributor.author | Yi-An Chen | en |
| dc.contributor.author | 陳奕安 | zh_TW |
| dc.date.accessioned | 2021-06-13T03:12:45Z | - |
| dc.date.available | 2007-09-20 | |
| dc.date.copyright | 2006-09-20 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-09-12 | |
| dc.identifier.citation | [1] “AMBA 2.0 specification.” http://www.arm.com/products/solutions/AMBAHomePage.
html. [2] P. H. Chou, R. B. Ortega, and G. Borriello, “The chinook hardware/software cosynthesis system,” in Eighth International Symposium on System Synthesis, IEEE, 1995. [3] R. J. Cloutier and D. E. Thomas, “The combination of scheduling, allocation, and mapping in a single algorithm,” in 27th ACM/IEEE conference on Design automation, pp. 71–76, 1991. [4] B. P. Dave, G. Lakshminarayana, and N. K. Jha, “COSYN: Hardware-software cosynthesis of embedded systems,” in Conference on Design Automation, pp. 703–708, IEEE, 1997. [5] R. Ernst, J. Henkel, and T. Benner, “Hardware-software cosynthesis for microcontrollers,”in The Morgan Kaufmann Systems On Silicon Series, pp. 18–29, IEEE, 2001. [6] R. K. Gupta and G. D. Micheu, “Hardware-software cosynthesis for digital systems,”in IEEE Design and Test of Computers, pp. 29–41, IEEE, 1993. [7] P. Prabhakaran and P. Banerjee, “Parallel algorithms for force directed scheduling of flattened and hierarchical signal flow graphs,” in International Conference on Computer Design, pp. 66–71, 1996. [8] W. Wolf, “An architectural co-synthesis algorithm for distributed, embedded computing systems,” IEEE Transactions on VLSI Systems, vol. 5, pp. 218–229, June 1997. [9] Y. Xie andW.Wolf, “Allocation and scheduling of conditional task graph in hardware/software co-synthesis,” in Design, Automation and Test in Europe, pp. 620–625, 2001. [10] R. J. M. Rim and R. D. Leone, “Optimal allocation and binding in high-level synthesis,”in 29th ACM/IEEE Conference on Design Automation, pp. 120–123, 1992. [11] P. Paulin and J. Knight, “Force-directed scheduling for the behavioral synthesis of ASIC’s,” IEEE Transactions on CAD/ICAS, vol. 8, pp. 661–679, July 1989. [12] C. Mandal, P. Chakrabarti, and S. Ghose, “Gabind: a ga approach to allocation and binding for the high-level synthesis of data paths,” in Very Large Scale Integration (VLSI) Systems, IEEE Transactions, vol. 8, pp. 747-750, 2000. [13] M.Balakrishnan, “Rt-level synthesis based on integrated scheduling and binding,”in Tech. Report 8813, Institut fur Informatik. der Universitat Kiel, pp. 40 – 60, 1988. [14] H. Schmit, L. Amstein, D. Thomas, and E. Lagnese, “Behavioral synthesis for fpga-based computing,” in FPGAs for Custom Computing Machines. Proceedings., 1994. [15] Y. Xie and W. Wolf, “Asicosyn: Co-synthesis of conditional task graphs with custom asics,” in ASIC, 2001. Proceedings. 4th International Conference, pp. 130–135, 2001. [16] Y. Xie and W. Wolf, “Co-synthesis with custom asics,” in 2000 Conference on Asia South Pacific Design Automation, pp. 129–134, 2000. [17] K. Chatha and R. Vemuri, “Hardware-software partitioning and pipelined scheduling of transformative applications,” in Very Large Scale Integration (VLSI) Systems, IEEE Transactions, vol. 10, pp. 193–208, Jun 2002. [18] A. Azzedine, J.-P. Diguet, and J.-L. Pillippe, “Large exploration for hw/sw partitioning of multirate and aperiodic real-time systems,” in Hardware/Software Codesign, 2002. CODES 2002. Proceedings of the Tenth International Symposium, pp. 85–90, 2002. [19] R. Dick and N. Jha, “Mogac: A multiobjective genetic algorithm for hardwaresoftware cosynthesis of distributed embedded systems,” in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions, pp. 920–935, 1998. [20] C. L. Liu and J. Layland, “Scheduling algorithms for multiprogramming in a hard real-time environment,” Journal of the ACM, vol. 20, no. 1, pp. 46–61, 1973. [21] Hsiao-Lan Fang, P. Ross, and D. Corne, “A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems,” in Proc. of the Fifth International Conference on Genetic lgorithms, (San Diego, CA USA), pp. 375 – 382, Evolutionary Programming Society, 1992. [22] R. Dick, D. Rhondes, andW.Wolf, “TGFF: Task graphs for free,” inWorkshop Hardware/Software Codesign, 1998. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31414 | - |
| dc.description.abstract | 系統晶片的主要元件常常由處理器、特殊應用積體電路、矽智財等構成。使用哪些元件去整合成一個系統晶片對於該系統晶片的價錢、效能有非常大的影響。隨著製程不斷地進步，如何在系統層級決定一個系統晶片上的元件變成一個最重要的議題。以往的論文在運算層級討論整合演算法，在本篇論文中，我們在系統層級研究整合演算法，這些整合演算法決定了系統晶片上面硬體元件的配置、工作的分配，以及工作的排程。我們改良並比較了許多種類的整合演算法，包括指數式最佳演算法，重覆式演算法，建構式演算法，基因演算法等等。我們透過大量的模擬實驗呈現他們在不同的情況下各自的效能及結果。 | zh_TW |
| dc.description.abstract | System-on-a-Chips are usually synthesized by a number of ASICs, IPs, and (customized or general) microprocessors to reduce design overhead and manufacture cost. Which processing elements are chosen and how the chosen processing elements are assigned to complete the tasks have significant impacts on the cost and performance of the system. As the complexity of SoC increases, how to find an optimal system-level system architecture has became a critical issue for SoC design. Earlier researches focus on the system synthesis on operation level. In this thesis, we are concerned with system synthesis on system-level. The algorithms in this thesis determine the scheduling, allocating, and mapping on system-level. We compare the performance of several types of synthesis algorithms including exponential optimal algorithms, iterative heuristic algorithms, constructive heuristic algorithms, genetic-based algorithms. We shall present their performance for different task models. The result shows that the iterative heuristic algorithms can get the near optimal solution when there are not large number
of instances. As the number of instances increases, the genetic algorithm outperforms the other algorithms on cost, and its mean run-time overhead is still acceptable. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T03:12:45Z (GMT). No. of bitstreams: 1 ntu-95-R93922095-1.pdf: 343894 bytes, checksum: 260c919acfe1976ad6dd2d00c5d5fcbe (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objective and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chapter 2 RelatedWork and Formal Model . . . . . . . . . . . . . . . . . . . . 5 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Formal Model and Problem Definition . . . . . . . . . . . . . . . . . . . . 10 Chapter 3 Optimal Branch and Bound Algorithm . . . . . . . . . . . . . . . . . 16 3.1 Branch method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Bounding method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Chapter 4 Constructive Heuristic Algorithms . . . . . . . . . . . . . . . . . . . 20 4.1 Formal Model and Force Function . . . . . . . . . . . . . . . . . . . . . . 20 4.2 SAMT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Chapter 5 Iterative Heuristic Algorithms . . . . . . . . . . . . . . . . . . . . . . 25 5.1 HW-oriented Iterative Algorithm . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 SW-oriented Iterative Algorithm . . . . . . . . . . . . . . . . . . . . . . . 28 5.3 ISAMT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Chapter 6 Genetic Based Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.1 Genetic Algorithm for SAM . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Chromosome Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.3 Scheduling and Timing Constraint . . . . . . . . . . . . . . . . . . . . . . 37 6.4 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.5 Population Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Chapter 7 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Chapter 8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 | |
| dc.language.iso | en | |
| dc.title | 即時單晶片系統之系統架構及排程整合演算法 | zh_TW |
| dc.title | System-Level Synthesis Algorithms for Real-Time SoC Design | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 郭大維(Tei-Wei Kuo),楊佳玲(Chia-Lin Yang),薛智文(Chih-Wen Hsueh),黃俊銘(Jun-Ming Huang) | |
| dc.subject.keyword | 即時,單晶片,排程,軟硬體協同設計, | zh_TW |
| dc.subject.keyword | real-time,SoC,scheduling,synthesis,system-level, | en |
| dc.relation.page | 49 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-09-13 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 目前未授權公開取用 | 335.83 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。