JUMPING JACK A Parallel Algorithm for Non-Monotonic Stream Compaction

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2009

Autores

moreira, pm (Autor) Outra; reis, lp (Autor) FEUP; de sousa, aa (Autor) FEUP

Ata de Conferência Internacional

Título: GRAPP 2009: PROCEEDINGS OF THE FOURTH INTERNATIONAL CONFERENCE ON COMPUTER GRAPHICS THEORY AND APPLICATIONS

Páginas: 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

Indexação

ISI Proceedings

ISI Web of Knowledge - 0 Citações

Scopus - 2 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 10