Chulalongkorn University Theses and Dissertations (Chula ETD)

Application of genetic algorithm to high-level circuit synthesis

Other Title (Parallel Title in Other Language of ETD)

การประยุกต์ขั้นตอนวิธีเชิงพันธุกรรมกับการสังเคราะห์วงจรขั้นสูง

Year (A.D.)

1998

Document Type

Thesis

First Advisor

Chidchanok Lursinsap

Faculty/College

Graduate School (บัณฑิตวิทยาลัย)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Computational Science

DOI

10.58837/CHULA.THE.1998.1129

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 (Other language abstract of ETD)

การสังเคราะห์การย้อนกลับระยะสั้นด้วยตัวเอง (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 ซึ่งถูกจำกัดด้วยจำนวนหน่วยหน้าที่ จำนวนขั้นบังคับ จำนวนจุดตรวจสอบและพื้นที่ของหน่วยหน้าที่

Link to Full Text

Share

COinS