Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/10328
Title: | Application of genetic algorithm to high-level circuit synthesis |
Other Titles: | การประยุกต์ขั้นตอนวิธีเชิงพันธุกรรมกับการสังเคราะห์วงจรขั้นสูง |
Authors: | Kingkarn Sookhanaphibarn |
Advisors: | Chidchanok Lursinsap |
Other author: | Chulalongkorn University. Graduate School |
Advisor's Email: | lchidcha@chula.ac.th |
Subjects: | Genetic algorithms Self recovery micro-rollback |
Issue Date: | 1998 |
Publisher: | Chulalongkorn University |
Abstract: | Self-recovery Micro-rollback Synthesis (SMS) has currently become an important issue in the high-level circuit synthesis. The problem of SMS combines the problem of functional unit scheduling and assignment with the problem of cheekpoint insertion and microprogram optimization. It has been shown that these problems are NP-complete. The most studied problem is the functional units scheduling and assignment. Several heuristic techniques, including as soon as possible (ASAP), as last as possible (ALAP), integer programming, spring elasticity model, graph-based mobility model, and genetic algorithm, are proposed. However, few studies are on the self-recovery microrollback synthesis and the technique of solution space searching by genetic algorithm is not attempted. In this thesis, we study the feasibility of genetic algorithm to the problem of SMS constrained only on the number of functional units, number of control steps, number of checkpoints and the functional unit areas. |
Other Abstract: | การสังเคราะห์การย้อนกลับระยะสั้นด้วยตัวเอง (Self-recovery Micro-vollback Synthesis) เรียกสั้นๆ ว่า SMS ได้กลายมาเป็นเรื่องสำคัญในการสังเคราะห์วงจรขั้นสูง ปัญหาของ SMS ประกอบไปด้วยปัญหาของการจัดตารางและการกำหนดหน่วยหน้าที่ ปัญหาการใส่จุดตรวจสอบและปัญหาการหาไมโครโปรแกรมที่เหมาะสม ซึ่งเป็นปัญหาประเภทเอ็นพีสมบูรณ์ (NP-complete) ปัญหาที่มีผู้ศึกษามากที่สุดคือ การจัดตารางและการกำหนดหน่วยหน้าที่ เทคนิคแบบฮิวอิสติด (heuristic technique) มากมายได้ถูกเสนอขึ้นมาอันได้แก่ as soon as possible (ASAP), as last as possible (ASAP), integer programming, spring elasticity made), graph-based mobility model และการประยุกต์ขั้นตอนวิธีเชิงพันธุกรรม อย่างไรก็ตามยังมีการศึกษาเกี่ยวกับ SMS น้อยมาก และไม่มีใครลองใช้เทคนิคการค้นหาในปริภูมิของคำตอบโดยการประยุกต์ขั้นตอนวิธีเชิงพันธุกรรม ในวิทยานิพนธ์นี้เป็นการศึกษาความเป็นไปได้ของการใช้การประยุกต์ขั้นตอนวิธีเชิงพันธุกรรมกับปัญหา SMS ซึ่งถูกจำกัดด้วยจำนวนหน่วยหน้าที่ จำนวนขั้นบังคับ จำนวนจุดตรวจสอบและพื้นที่ของหน่วยหน้าที่ |
Description: | Thesis (M.Sc.)--Chulalongkorn University, 1998 |
Degree Name: | Master of Science |
Degree Level: | Master's Degree |
Degree Discipline: | Computational Science |
URI: | http://cuir.car.chula.ac.th/handle/123456789/10328 |
ISBN: | 9743325522 |
Type: | Thesis |
Appears in Collections: | Grad - Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Kingkarn_So_front.pdf | 918.83 kB | Adobe PDF | View/Open | |
Kingkarn_So_ch1.pdf | 813.79 kB | Adobe PDF | View/Open | |
Kingkarn_So_ch2.pdf | 766.76 kB | Adobe PDF | View/Open | |
Kingkarn_So_ch3.pdf | 1.05 MB | Adobe PDF | View/Open | |
Kingkarn_So_ch4.pdf | 1.24 MB | Adobe PDF | View/Open | |
Kingkarn_So_ch5.pdf | 1.47 MB | Adobe PDF | View/Open | |
Kingkarn_So_ch6.pdf | 710.36 kB | Adobe PDF | View/Open | |
Kingkarn_So_back.pdf | 788.23 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.