Better trade-offs for parallel list ranking

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Better trade-offs for parallel list ranking

Full text

Pdf (1.31 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures table of contents

Newport, Rhode Island, United States

Pages: 221 - 230

Year of Publication: 1997

ISBN:0-89791-890-8

Author

Jop F. Sibeyn

Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 15, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258492.258514 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Anderson, R.J., G.L. Miller, 'Deterministic Parallel List Ranking,' Algorithmica, 6, pp. 859-868, 199I.
	2	Armin Bäumker , Wolfgang Dittrich , Friedhelm Meyer auf der Heide, Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model, Selected papers from the third European symposium on Algorithms, p.175-203, August 1998, Courfu, Greece
	3	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	4	Alan Gibbons , Wojciech Rytter, Efficient parallel algorithms, Cambridge University Press, New York, NY, 1988
	5	W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
	6	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	7	Margaret Reid-Miller, List ranking and list scan on the Cray C-90, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.104-113, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181049]
	8	Jop F. Sibeyn, List Ranking on Interconnection Networks, Proceedings of the Second International Euro-Par Conference on Parallel Processing, p.799-808, August 26-29, 1996
	9	Jop F. Sibeyn , Frank Guillaume , Tillmann Seidel, Practical Parallel List Ranking, Proceedings of the 4th International Symposium on Solving Irregularly Structured Problems in Parallel, p.25-36, June 12-13, 1997

CITED BY 3

	Isabelle Guérin Lassous , Jens Gustedt, Portable list ranking: an experimental study, Journal of Experimental Algorithmics (JEA), 7, p.7, 2002
	Jop F. Sibeyn, Solving Fundamental Problems on Sparse-Meshes, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1324-1332, December 2000
	Dascal Vishkin , Uzi Vishkin, Experiments with list ranking for explicit multi-threaded (XMT) instruction parallelism, Journal of Experimental Algorithmics (JEA), 5, p.10-es, 2000

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.2 Modes of Computation
Subjects: Parallelism and concurrency

Additional Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Lists, stacks, and queues

G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.0 General
Subjects: Parallel algorithms
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory, Verification

Collaborative Colleagues:

Jop F. Sibeyn: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player