Chulalongkorn University Theses and Dissertations (Chula ETD)

High-level circuit synthesis by evolutionary algorithms

Other Title (Parallel Title in Other Language of ETD)

การสังเคราะห์วงจรขั้นสูงโดยขั้นตอนวิธีเชิงวิวัฒน์

Year (A.D.)

2002

Document Type

Thesis

First Advisor

Prabhas Chongstitvatana

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2002.1557

Abstract

In this research an algorithm based on Ant Colony Optimization techniques called Ants on a Tree (AOT) is proposed. This algorithm can integrate many algorithms together to solve a single problem. The strength of AOT is demonstrated by solving a High-Level Synthesis problem. A High-Level Synthesis problem consists of many design steps and many algorithms to solve each of them. AOT can easily integrate these algorithms to limit the search space and use them as heuristic weights to guide the search. During the search, AOT generates a dynamic decision tree. A boosting technique similar to branch and bound algorithms is applied to guide the search in the decision tree. The storage explosion problem is eliminated by the evaporation of pheromone trail generated by ants the inherent property of our search algorithm. The algorithm was tested with the Elliptical Wave Filter (EWF) benchmark, and found that it is practically to be used. By allocating the resources at the early design state, the Fixed-resource Mobility could be integrated to further improve the performance of the algorithm

Other Abstract (Other language abstract of ETD)

ในการวิจัยนี้ได้เสนอขั้นตอนวิธีแบบใหม่ที่ม่ชื่อว่า Ants on a Tree (AOT) ซึ่งมีพื้นฐานมาจากขั้นตอนวิธีแบบ Ant Colony Optimization โดยขั้นตอนวิธีแบบนี้สามารถเชื่อมโยงขั้นตอนวิธีหลายอย่างเข้าด้วยกันเพื่อช่วยแก้ปัญหาเดียวกันได้ ความสามารถของขั้นตอนวิธีนี้จะถูกสาธิตโดยการนำมาใช้แก้ปัญหาการสังเคราะห์วงจรระดับสูง การสังเคราะห์วงจรระดับสูงประกอบด้วยขั้นตอนการออกแบบหลายขั้นตอน และขั้นตอนวิธีหลายชนิดเพื่อแก้ปัญหาในแต่ละขั้น ขั้นตอนวิธี AOT สามารถที่จะนำขั้นตอนวิธีต่าง ๆ มาช่วยในการกำหนดขอบเขตของการค้นหาคำตอบ และแปลงเป็นค่าถ่วงน้ำหนักเพื่อช่วยนำทางในการค้นหาคำตอบ ในระหว่างที่ทำการค้นหาคำตอบขั้นตอนวิธี AOT จะสร้างต้นไม้การตัดสินใจแบบพลวัตเพื่อช่วยในการค้นหา เทคนิคที่ใช้ในขั้นตอนวิธีแบบกลวิธีขยายและจำกัดเขตถูกนำมาช่วยในการค้นหาคำตอบ ปัญหาเกี่ยวกับขนาดของหน่วยเก็บข้อมูลจะไม่เกิดขึ้นในขั้นตอนวิธีแบบนี้ เนื่องจากขนาดของหน่วยเก็บข้อมูลจำกัดโดยการระเหิดของ pheromone ที่สร้างขึ้นโดยมด ซึ่งเป็นคุณสมบัติอย่างหนึ่งของขั้นตอนวิธีนี้ ขั้นตอนวิธี AOT ได้ถูกทดสอบโดยการนำไปใช้สังเคราะห์วงจรกรองคลื่นความถี่แบบ Elliptic และผลจากการทดสอบแสดงว่าขั้นตอนวิธี AOT สามารถนำไปใช้ในทางปฏิบัติได้ โดยการกำหนดปริมาณทรัพยากรในขั้นต้นของการออกแบบ ทำให้สามารถใช้ Fixed-resource Mobility เพื่อช่วยปรับให้ขั้นตอนวิธี AOT มีประสิทธิภาพมากยิ่งขึ้น

Link to Full Text

Share

COinS