IEEE Transactions on Parallel and Distributed Systems
IEEE Transactions on Parallel and Distributed Systems (TPDS) is a scholarly archival journal published monthly. Parallelism and distributed computing are foundational research and technology to rapidly advance computer systems and their applications. Read the full scope of TPDS
IEEE Transactions on Parallel and Distributed Systems (TPDS) has moved to the OnlinePlus publication model.
From the August 2015 Issue
Exploiting Massive Parallelism for Indexing Multi-Dimensional Datasets on the GPU
By Jinwoong Kim, Won-Ki Jeong, and Beomseok Nam
Inherently multi-dimensional n-ary indexing structures such as R-trees are not well suited for the GPU because of their irregular memory access patterns and recursive back-tracking function calls. It has been known that traversing hierarchical tree structures in an irregular manner makes it difficult to exploit parallelism and to maximize the utilization of GPU processing units. Moreover, the recursive tree search algorithms often fail with large indexes because of the GPU’s tiny runtime stack size. In this paper, we propose a novel parallel tree traversal algorithm—massively parallel restart scanning (MPRS) for multi-dimensional range queries that avoids recursion and irregular memory access. The proposed MPRS algorithm traverses hierarchical tree structures with mostly contiguous memory access patterns without recursion, which offers more chances to optimize the parallel SIMD algorithm. We implemented the proposed MPRS range query processing algorithm on n-ary bounding volume hierarchies including R-trees and evaluated its performance using real scientific datasets on an NVIDIA Tesla M2090 GPU. Our experiments show braided parallel SIMD friendly MPRS range query algorithm achieves at least 80 percent warp execution efficiency while task parallel tree traversal algorithm shows only 9-15 percent efficiency. Moreover, braided parallel MPRS algorithm accesses 7-20 times less amount of global memory than task parallel parent link algorithm by virtue of minimal warp divergence.
Editorials and Announcements
- According to Thomson Reuters' 2013 Journal Citation Report, TPDS has an impact factor of 2.173.
- TPDS celebrates its 25th Anniversary. Editor-in-Chief David A. Bader says, "Congratulations to TPDS on its Silver Jubilee! For 25 years, TPDS has been the parallel and distributed computing community's flagship journal for research breakthroughs!"
- Get Your Journals as eBooks for Free
- Editor's Note (Jan 2015)
- State of the Journal (Jan 2014)
- Editor's Note: EIC Farewell and New EIC Introduction (Dec 2013)
- Editor's Note (Nov 2013)
- Editor's Note (Jan 2013)
- Editor's Note (April 2012)
- Editor's Note (January 2012)
- Editorial: Media Center (November 2011)
- Editor's Note: How to Write Research Articles in Computing and Engineering Disciplines by Ivan Stojmenovic
- Full Supplemental PDF of Editor's Note: How to Write Research Articles in Computing and Engineering Disciplines by Ivan Stojmenovic and Veljko Milutinovic (PDF)
- Special Issue on Trust, Security, and Privacy in Parallel and Distributed Systems (Feb 2014)
- Special Issue on Cloud Computing (June 2013)
- Special Issue on Cyber-Physical Systems (CPS) (Sept 2012)
- Special Section on Many-Task Computing (June 2011)
Access recently published TPDS articles
Subscribe to the RSS feed of latest TPDS content added to the digital library.
Sign up for the Transactions Connection newsletter.
Listen to the OnlinePlus Podcast: Computer Society Publishing—two more titles migrate to OnlinePlus™ in 2012.
In this podcast, VP of Publications, David Alan Grier talks about Transactions on Mobile Computing and Transactions on Parallel and Distributed Systems migrating to OnlinePlus™.
TPDS is indexed in ISI