Please use this identifier to cite or link to this item: http://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 SizeFormat 
Kingkarn_So_front.pdf918.83 kBAdobe PDFView/Open
Kingkarn_So_ch1.pdf813.79 kBAdobe PDFView/Open
Kingkarn_So_ch2.pdf766.76 kBAdobe PDFView/Open
Kingkarn_So_ch3.pdf1.05 MBAdobe PDFView/Open
Kingkarn_So_ch4.pdf1.24 MBAdobe PDFView/Open
Kingkarn_So_ch5.pdf1.47 MBAdobe PDFView/Open
Kingkarn_So_ch6.pdf710.36 kBAdobe PDFView/Open
Kingkarn_So_back.pdf788.23 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.