Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/32713
Title: Data dependency reduction in dynamic programming matrix
Other Titles: การลดการพึ่งพิงกันของข้อมูลในเมทริกซ์กำหนดการพลวัต
Authors: Delgado, Guillermo
Advisors: Chatchawit Aporntewan
Other author: Chulalongkorn University. Faculty of Science
Advisor's Email: Chatchawit.A@Chula.ac.th
Subjects: Dynamic programming
Computer arithmetic
การโปรแกรมพลศาสตร์
การคำนวณของคอมพิวเตอร์
Issue Date: 2011
Publisher: Chulalongkorn University
Abstract: Dynamic Programming (DP) plays an important role in solving a large number of computational problems. As the number of cores per processor is increasing rapidly, new software must be capable of exploiting the advantages of multi-core architectures. A typical DP begins with constructing a matrix, and then calculating each element one by one. The standard parallelization spawns multiple threads, one for each row, while maintains the data dependency via thread synchronization. However, as the number of threads increase, the performance degrades due to data dependency. Herein, we proposed a novel method for calculating a DP matrix in parallel. In contrast to the standard method that always calculates from up to down and left to right, our method performs the calculation in multiple directions. Therefore, the wait time for data dependency is remarkably reduced. To demonstrate our method, a local sequence alignment algorithm called Smith-Waterman (SW) was chosen as an instance of DP. However, our method is not only limited to SW algorithm, but it is applicable to other DP problems that have similar patterns of data dependency. A comparison with the standard method was conducted on a HP Z800 workstation with a total of eight cores. The results show that our method performs significantly faster.
Other Abstract: กำหนดการพลวัตมีบทบาทสำคัญในการแก้ปัญหาเชิงคำนวณจำนวนมาก ในขณะที่จำนวนคอร์ต่อโปรเซสเซอร์กำลังเพิ่มขึ้นอย่างรวดเร็ว ซอฟต์แวร์ใหม่ๆ ต้องสามารถใช้ประโยชน์จากข้อดีของสถาปัตยกรรมแบบมัลติคอร์ได้ โดยปกติกำหนดการพลวัตเริ่มจากการสร้างเมทริกซ์และคำนวณค่าในเมทริกซ์ไปทีละค่า การทำงานแบบขนานจะสร้างเธรดหนึ่งเธรดต่อหนึ่งแถว และรักษาการพึ่งพิงกันของข้อมูลด้วยการประสานเวลาของเธรด อย่างไรก็ตามเมื่อจำนวนเธรดเพิ่มขึ้นสมรรถนะจะลดลงเนื่องจากการพึ่งพิงกันของข้อมูล ในที่นี้เราเสนอวิธีใหม่สำหรับการคำนวณเมทริกซ์แบบขนาน ซึ่งตรงข้ามกับวิธีมาตรฐานที่คำนวณจากบนลงล่างและจากซ้ายไปขวาเท่านั้น วิธีที่เราเสนอนั้นทำในหลายทิศทาง ดังนั้นจะลดเวลาที่ใช้รอการพึ่งพิงกันของข้อมูลได้มาก เพื่อสาธิตการทำงานของวิธีที่เรานำเสนอ เราเลือกขั้นตอนวิธีการปรับแนวลำดับเฉพาะที่ แบบที่เรียกว่า สมิธ-วอเตอร์แมน ซึ่งเป็นปัญหากำหนดการพลวัตแบบหนึ่ง อย่างไรก็ตามวิธีของเราไม่ได้จำกัดแค่ขั้นตอนวิธีสมิธวอเตอร์แมน แต่ใช้กับปัญหากำหนดการพลวัตอื่นๆ ที่มีรูปแบบคล้ายกันได้ด้วย การเปรียบเทียบกับวิธีมาตรฐานบนสถานีงาน HP Z800 ที่มี 8 คอร์แสดงให้เห็นว่าวิธีที่เรานำเสนอทำงานได้เร็วกว่าอย่างมีนัยยะสำคัญ
Description: Thesis (M.Sc.)--Chulalongkorn University, 2011
Degree Name: Master of Science
Degree Level: Master's Degree
Degree Discipline: Mathematics
URI: http://cuir.car.chula.ac.th/handle/123456789/32713
Type: Thesis
Appears in Collections:Sci - Theses

Files in This Item:
File Description SizeFormat 
guillermo_de.pdf3 MBAdobe PDFView/Open


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