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
Using Artificial Neural Networks for Detecting Damage on Tobacco Leaves Caused by Blue Mold
Worldwide, the monitoring of pests and diseases plays a fundamental role in the agricultural sustainability; making necessary the development of new tools for early pest detection. In this sense, we present a software ap...
Quality of Service and Power Consumption Optimization on the IEEE 802.15.4 Pulse Sensor Node based on Internet of Things
The Purpose of this research is to determine the Quality of Service (QoS) Zigbee or IEEE 802.15.4 sensor Node use the indicators, i.e. the Receiver Signal Strength and PathLoss (attenuation (-dB)) at the time of communic...
A Fresnelet-Based Encryption of Medical Images using Arnold Transform
Medical images are commonly stored in digital media and transmitted via Internet for certain uses. If a medical information image alters, this can lead to a wrong diagnosis which may create a serious health problem. More...
: Optimized Min-Sum Decoding Algorithm for Low Density Parity Check Codes
Low Density Parity Check (LDPC) code approaches Shannon–limit performance for binary field and long code lengths. However, performance of binary LDPC code is degraded when the code word length is small. An op...
Estimating the Parameters of Software Reliability Growth Models Using the Grey Wolf Optimization Algorithm
In this age of technology, building quality software is essential to competing in the business market. One of the major principles required for any quality and business software product for value fulfillment is reliabili...