Chulalongkorn University Theses and Dissertations (Chula ETD)

การพัฒนาโปรแกรมของขั้นตอนวิธีอุบัติการณ์ร่วมกันบนตัวประมวลผลหลายแกน

Other Title (Parallel Title in Other Language of ETD)

An implementation of coincidence algorithm on multi-core processors

Year (A.D.)

2011

Document Type

Thesis

First Advisor

ประภาส จงสถิตย์วัฒนา

Faculty/College

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

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2011.1383

Abstract

งานวิจัยชิ้นนี้นำเสนอ การแก้ปัญหาการเดินทางของผู้ขายสินค้า (Traveling Salesman Problem) ซึ่งอยู่ในกลุ่มของปัญหาเชิงวิวัฒนาการ โดยใช้ขั้นตอนวิธีอุบัติการณ์ร่วมกัน (Coincidence Algorithm) แก้ปัญหา โดยให้มีการทำงานแบบขนานเพื่อลดเวลาการประมวลผลในการหาคำตอบ ปัญหาที่นำมาทดสอบในงานวิจัยจำนวน 5 ปัญหา ที่มีจำนวนเมืองในการเดินทางไม่เกิน 200 เมือง พัฒนาโดยใช้ภาษา C++ ร่วมกับตัวบริการ Intel Threading Building Blocks และให้ทำงานบนเครื่องคอมพิวเตอร์ที่มีตัวประมวลผลกลางแบบ 4 แกน เปรียบเทียบกับการทำงานแบบลำดับ ผลการวิจัยที่ได้สามารถเพิ่มความเร็วในการประมวลผลได้จริง เมื่อวิเคราะห์วิธีการแก้ปัญหา โดยแบ่งงานในขั้นตอนของวิธีการแก้ปัญหาให้ทำงานไปพร้อมๆกัน สามารถทำความเร็วได้มากกว่าแบบลำดับถึง 3 เท่า

Other Abstract (Other language abstract of ETD)

This research presents an evolutionary algorithm to solve Traveling Salesman Problem using Coincidence Algorithm. A parallel processing is implemented to reduce the execution time. Five problems which the number of cities is less than 200 are used to test the implementation. The parallel program is written in C++ language with Intel Threading Building Block tool. The test was conducted on a quad-core processor and the runtime is compared to a sequential program. The result shows that by divide the computation task and run them in parallel the speed up over the sequential program is up to 3 times.

Link to Full Text

Share

COinS