Data dependency reduction in dynamic programming matrix

• Main Author: Delgado, Guillermo (Author)
• Other Authors: Chatchawit Aporntewan (Contributor), Chulalongkorn University. Faculty of Science (Contributor)
• Format: Book
• Published: Chulalongkorn University, 2013-07-02T06:17:51Z.
• Subjects: Thesis
• Online Access: http://cuir.car.chula.ac.th/handle/123456789/32713

Summary

Thesis (M.Sc.)--Chulalongkorn University, 2011
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.
กำหนดการพลวัตมีบทบาทสำคัญในการแก้ปัญหาเชิงคำนวณจำนวนมาก ในขณะที่จำนวนคอร์ต่อโปรเซสเซอร์กำลังเพิ่มขึ้นอย่างรวดเร็ว ซอฟต์แวร์ใหม่ๆ ต้องสามารถใช้ประโยชน์จากข้อดีของสถาปัตยกรรมแบบมัลติคอร์ได้ โดยปกติกำหนดการพลวัตเริ่มจากการสร้างเมทริกซ์และคำนวณค่าในเมทริกซ์ไปทีละค่า การทำงานแบบขนานจะสร้างเธรดหนึ่งเธรดต่อหนึ่งแถว และรักษาการพึ่งพิงกันของข้อมูลด้วยการประสานเวลาของเธรด อย่างไรก็ตามเมื่อจำนวนเธรดเพิ่มขึ้นสมรรถนะจะลดลงเนื่องจากการพึ่งพิงกันของข้อมูล ในที่นี้เราเสนอวิธีใหม่สำหรับการคำนวณเมทริกซ์แบบขนาน ซึ่งตรงข้ามกับวิธีมาตรฐานที่คำนวณจากบนลงล่างและจากซ้ายไปขวาเท่านั้น วิธีที่เราเสนอนั้นทำในหลายทิศทาง ดังนั้นจะลดเวลาที่ใช้รอการพึ่งพิงกันของข้อมูลได้มาก เพื่อสาธิตการทำงานของวิธีที่เรานำเสนอ เราเลือกขั้นตอนวิธีการปรับแนวลำดับเฉพาะที่ แบบที่เรียกว่า สมิธ-วอเตอร์แมน ซึ่งเป็นปัญหากำหนดการพลวัตแบบหนึ่ง อย่างไรก็ตามวิธีของเราไม่ได้จำกัดแค่ขั้นตอนวิธีสมิธวอเตอร์แมน แต่ใช้กับปัญหากำหนดการพลวัตอื่นๆ ที่มีรูปแบบคล้ายกันได้ด้วย การเปรียบเทียบกับวิธีมาตรฐานบนสถานีงาน HP Z800 ที่มี 8 คอร์แสดงให้เห็นว่าวิธีที่เรานำเสนอทำงานได้เร็วกว่าอย่างมีนัยยะสำคัญ

Item Description

http://cuir.car.chula.ac.th/handle/123456789/32713