Solving Dynamic Programming Problem by Pipeline Implementation on GPU

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

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...

Download PDF file
  • EP ID EP429234
  • DOI 10.14569/IJACSA.2018.091272
  • Views 96
  • Downloads 0

How To Cite

Susumu Matsumae, Makoto Miyazaki (2018). Solving Dynamic Programming Problem by Pipeline Implementation on GPU. International Journal of Advanced Computer Science & Applications, 9(12), 518-523. https://europub.co.uk/articles/-A-429234