ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

Data dependency reduction in dynamic programming matrix

หน่วยงาน จุฬาลงกรณ์มหาวิทยาลัย

รายละเอียด

ชื่อเรื่อง : Data dependency reduction in dynamic programming matrix
นักวิจัย : Delgado, Guillermo
คำค้น : Dynamic programming , Computer arithmetic , การโปรแกรมพลศาสตร์ , การคำนวณของคอมพิวเตอร์
หน่วยงาน : จุฬาลงกรณ์มหาวิทยาลัย
ผู้ร่วมงาน : Chatchawit Aporntewan , Chulalongkorn University. Faculty of Science
ปีพิมพ์ : 2554
อ้างอิง : http://cuir.car.chula.ac.th/handle/123456789/32713
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : -
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

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.

บรรณานุกรม :
Delgado, Guillermo . (2554). Data dependency reduction in dynamic programming matrix.
    กรุงเทพมหานคร : จุฬาลงกรณ์มหาวิทยาลัย.
Delgado, Guillermo . 2554. "Data dependency reduction in dynamic programming matrix".
    กรุงเทพมหานคร : จุฬาลงกรณ์มหาวิทยาลัย.
Delgado, Guillermo . "Data dependency reduction in dynamic programming matrix."
    กรุงเทพมหานคร : จุฬาลงกรณ์มหาวิทยาลัย, 2554. Print.
Delgado, Guillermo . Data dependency reduction in dynamic programming matrix. กรุงเทพมหานคร : จุฬาลงกรณ์มหาวิทยาลัย; 2554.