Data dependency reduction in dynamic programming matrix

Thesis (M.Sc.)--Chulalongkorn University, 2011

Saved in:

Bibliographic Details
Main Author:	Delgado, Guillermo
Other Authors:	Chatchawit Aporntewan
Format:	Theses and Dissertations
Language:	English
Published:	Chulalongkorn University 2013
Subjects:	Dynamic programming Computer arithmetic การโปรแกรมพลศาสตร์ การคำนวณของคอมพิวเตอร์
Online Access:	http://cuir.car.chula.ac.th/handle/123456789/32713 http://doi.org/10.14457/CU.the.2011.1362
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Chulalongkorn University
Language:	English

id	th-cuir.32713
record_format	dspace
spelling	th-cuir.327132019-10-11T07:50:22Z Data dependency reduction in dynamic programming matrix การลดการพึ่งพิงกันของข้อมูลในเมทริกซ์กำหนดการพลวัต Delgado, Guillermo Chatchawit Aporntewan Chulalongkorn University. Faculty of Science Dynamic programming Computer arithmetic การโปรแกรมพลศาสตร์ การคำนวณของคอมพิวเตอร์ 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 คอร์แสดงให้เห็นว่าวิธีที่เรานำเสนอทำงานได้เร็วกว่าอย่างมีนัยยะสำคัญ 2013-07-02T06:17:51Z 2013-07-02T06:17:51Z 2011 Thesis http://cuir.car.chula.ac.th/handle/123456789/32713 10.14457/CU.the.2011.1362 en http://doi.org/10.14457/CU.the.2011.1362 Chulalongkorn University application/pdf Chulalongkorn University
institution	Chulalongkorn University
building	Chulalongkorn University Library
continent	Asia
country	Thailand Thailand
content_provider	Chulalongkorn University Library
collection	Chulalongkorn University Intellectual Repository
language	English
topic	Dynamic programming Computer arithmetic การโปรแกรมพลศาสตร์ การคำนวณของคอมพิวเตอร์
spellingShingle	Dynamic programming Computer arithmetic การโปรแกรมพลศาสตร์ การคำนวณของคอมพิวเตอร์ Delgado, Guillermo Data dependency reduction in dynamic programming matrix
description	Thesis (M.Sc.)--Chulalongkorn University, 2011
author2	Chatchawit Aporntewan
author_facet	Chatchawit Aporntewan Delgado, Guillermo
format	Theses and Dissertations
author	Delgado, Guillermo
author_sort	Delgado, Guillermo
title	Data dependency reduction in dynamic programming matrix
title_short	Data dependency reduction in dynamic programming matrix
title_full	Data dependency reduction in dynamic programming matrix
title_fullStr	Data dependency reduction in dynamic programming matrix
title_full_unstemmed	Data dependency reduction in dynamic programming matrix
title_sort	data dependency reduction in dynamic programming matrix
publisher	Chulalongkorn University
publishDate	2013
url	http://cuir.car.chula.ac.th/handle/123456789/32713 http://doi.org/10.14457/CU.the.2011.1362
_version_	1724630111473369088

Data dependency reduction in dynamic programming matrix

Similar Items