Solving Dynamic Programming Problem by Pipeline Implementation on GPU
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2018, Vol 9, Issue 12
Abstract
In this paper, we show the effectiveness of a pipeline implementation of Dynamic Programming (DP) on GPU. As an example, we explain how to solve a matrix-chain multiplication (MCM) problem by DP on GPU. This problem can be sequentially solved in O(n3) steps by DP where n is the number of matrices, because its solution table is of size n × n and each element of the table can be computed in O(n) steps. A typical speedup strategy for this is to parallelize the O(n) step computation of each element, which can be easily achieved by parallel prefix computation, i.e., an O(log n) step computation with n threads in a tournament fashion. By such a standard parallelizing method, we can solve the MCM problem in O(n2 log n) steps with n threads. In our approach, we solve the MCM problem on GPU in a pipeline fashion, i.e., we use GPU cores for supporting pipeline-stages so that many elements of the solution table are partially computed in parallel at one time. Our implementation determines one output value per one computational step with n threads in a pipeline fashion and constructs the solution table totally in O(n2) steps with n threads.
Authors and Affiliations
Susumu Matsumae, Makoto Miyazaki
Keywords
Related Articles
- EP ID EP429234
- DOI 10.14569/IJACSA.2018.091272
- Views 63
- Downloads 0
Muscle Electro Stimulator for the Reduction of Stretch Marks
The problem of stretch marks is generated because the skin stretches abruptly in a short time; this change causes the skin to deform and widen, forming a roughness. This roughness is what is known as stretch marks. This...
Area and Energy Efficient Viterbi Accelerator for Embedded Processor Datapaths
Viterbi algorithm is widely used in communication systems to efficiently decode the convolutional codes. This algorithm is used in many applications including cellular and satellite communication systems. Moreover, Seria...
Surface Texture Synthesis and Mixing Using Differential Colors
In neighborhood-based texture synthesis, adjacent local regions need to satisfy color continuity constraints in order to avoid visible seams. Such continuity constraints seriously restrict the variability of synthesized...
Improving Vertical Handoffs Using Mobility Prediction
The recent advances in wireless communications require integration of multiple network technologies in order to satisfy the increasing demand of mobile users. Mobility in such a heterogeneous environment entails that use...
A Reversible Data Hiding Scheme for BTC-Compressed Images
This paper proposes a reversible data hiding scheme for BTC-compressed images. A block in the BTC-compressed image consists of a larger block-mean pixel and a smaller block-mean pixel. Two message bits are embedded into...