JUMPING JACK A Parallel Algorithm for Non-Monotonic Stream Compaction

• Type: Article in International Conference Proceedings Book
• Date: 2009

Authors

moreira, pm (Author) Other; reis, lp (Author) FEUP; de sousa, aa (Author) FEUP

Conference proceedings International

Title: GRAPP 2009: PROCEEDINGS OF THE FOURTH INTERNATIONAL CONFERENCE ON COMPUTER GRAPHICS THEORY AND APPLICATIONS

Pages: 137-146

4th International Conference on Computer Vision Theory and Applications4th International Conference on Computer Graphics Theory and Applications

Lisbon, PORTUGALLisbon, PORTUGAL, FEB 05-08, 2009FEB 05-08, 2009

Indexing

ISI Proceedings

ISI Web of Knowledge - 0 Citations

Scopus - 2 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-Q6X

Abstract (EN): Stream Compaction is an important task to perform in the context of data parallel computing, useful for many applications in Computer Graphics as well as for general purpose computation on graphics hardware. Given a data stream containing irrelevant elements, stream compaction outputs a stream comprised by the relevant elements, discarding the rest. The compaction mechanism has the potential to enable savings on further processing, memory storage and communication bandwidth. Traditionally, stream compaction is defined as a monotonic (or stable) operation in the sense that it preserves the relative order of the data. This is not a full requirement for many applications, therefore we distinguish between monotonic and non-monotonic algorithms. The latter motivated us to introduce the Jumping Jack algorithm as a new algorithm for non-monotonic compaction. In this paper, experimental results are presented and discussed showing that, although simple, the algorithm has interesting properties that enable it to perform faster than existent state-of-the-art algorithms, in many circumstances.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 10