IIIT Hyderabad Publications |
|||||||||
|
Parallel Frameworks for Locality Based Dynamic Programming Problems.Author: rajesh.kumar Date: 2017-07-21 Report no: IIIT/TH/2017/62 Advisor:Kishore Kothapalli AbstractDynamic Programming(DP) is a powerful technique used for efficiently solving a vast set of complex optimization problems. It is widely used in areas of scheduling, string editing, packaging, bioinformatics, and inventory management [17]. Because of its impact and applicability across a wide range of domains, it is believed that DP will retain its importance in the future for science and engineering. This importance makes it one of the Berkeley 13 dwarfs [6]. It is thus not surprising that a lot of research attention is devoted in parallelizing DP problems. There are many classes of dynamic programming problems [11]. One of the important class is LDDP (Local Dependency Dynamic Programming). LDDP problems are ones in which update to an entry in the DP table is determined by the contents of neighboring cells [11]. Many non DP problems also mimic local dependency nature of LDDP problems. We collectively classify these local dependency problems (DP and non DP) as LDDP-Plus Problems. One more class of dynamic programming problems which is based on locality is HLDP (Horizontally Local Dynamic programming). HLDP class represents problems in which the contents of the cells from the immediately previous row/column decide the update to an entry in the DP table. Examples of both these classes of problems are common in many domains like speech processing (Dynamic Time Warping Algorithm [5], Non-Segmental Dynamic Time Warping [29]), bioinformatics (longest common subsequence, pairwise sequence alignment with affine gap cost [11]), image (Floyd-Steinberg dithering [15]) and the like. Many classical problems like 0/1 knapsack problem and checkerboard problem are also examples of these classes. Many other DP problems can also be modeled as LDDP / HLDP problems. Therefore, efficient parallel solutions to these two classes of problems is of immense research interest. While problem specific solutions are best way to achieve performance, generic solutions/frameworks enable the programmers and domain experts to extract reasonably good performance with little effort. This also enables them to take advantage of high performance computing platforms such as multi-core CPUs and GPGPUs with lesser effort. So it is meaningful to create generic parallel frameworks for solving a class of problems. The current architectural trend in parallel computing is towards a heterogeneous collection of devices involving CPUs and accelerators such as GPUs and Intel Xeon-Phi. Hence, the design and development of heterogeneous algorithms aimed at commodity heterogeneous computing platforms are of immense research interest. Heterogeneous algorithms for a variety of problems from domains such as sorting [7], graph algorithms [8] [16], sparse matrix computations [21], are reported in recent literature. In this thesis, we categorize LDDP and HLDP problems into various categories. We design and implement pure/heterogeneous algorithms for each of these categories of problems as a complete framework. Our framework can act as a software tool that can enhance the productivity of programming modern heterogeneous systems. Using our framework, users can readily create solutions for problems that follow LDDP or HLDP approach by just providing the function that dictates the dependency pattern. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |