Source author record

Susumu Matsumae

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

2works
2topics
1close collaborators

Published work

2 publications

preprint2020arXiv

Solving Dynamic Programming Problem by Pipeline Implementation on GPU

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)O(n^3) steps by DP where nn is the number of matrices, because its solution table is of size n×nn \times n and each element of the table can be computed in O(n)O(n) steps. A typical speedup strategy for this is to parallelize the O(n)O(n) step computation of each element, which can be easily achieved by parallel prefix computation, i.e., an O(log⁡n)O(\log n) step computation with nn threads in a tournament fashion. By such a standard parallelizing method, we can solve the MCM problem in O(n2log⁡n)O(n^2 \log n) steps with nn 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 nn threads in a pipeline fashion and constructs the solution table totally in O(n2)O(n^2) steps with nn threads.

preprint2013arXiv

Energy-Efficient Cell Partition of 3D Space for Sensor Networks with Location Information

In the wireless sensor networks composed of battery-powered sensor nodes, one of the main issues is how to save power consumption on each node. The usual approach to this problem is to activate only necessary nodes (e.g., those nodes which compose a backbone network), and to put other nodes to sleep. One such algorithm using location information is GAF (Geographical Adaptive Fidelity), and GAF is enhanced to HGAF (Hierarchical Geographical Adaptive Fidelity). In this paper, we study the energy-efficient partition of a 3 dimensional sensor field into cells. Further, we give a theoretical upper bound on cell size for this problem.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.