Parallel algorithms for personalized communication and sorting with an experimental study (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel algorithms for personalized communication and sorting with an experimental study (extended abstract)

Full text

Pdf (1.12 MB)

Source

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

Padua, Italy

Pages: 211 - 222

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

David R. Helman	Institute for Advanced Computer Studies and Department of Electrical Engineering, University of Maryland, College Park, MD
David A. Bader	Institute for Advanced Computer Studies and Department of Electrical Engineering, University of Maryland, College Park, MD
Joseph JáJá	Institute for Advanced Computer Studies and Department of Electrical Engineering, University of Maryland, College Park, MD

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): 3, Downloads (12 Months): 34, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

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/237502.237558 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	Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
	2	Remzi H. Arpaci , David E. Culler , Arvind Krishnamurthy , Steve G. Steinberg , Katherine Yelick, Empirical evaluation of the CRAY-T3D: a compiler perspective, Proceedings of the 22nd annual international symposium on Computer architecture, p.320-331, June 22-24, 1995, S. Margherita Ligure, Italy
	3	D. Bader. Randomized and Deterministic Routing Algorithms for h-Relations. ENEE 648X Class Report, April 1, 1994.
	4	David A. Bader , David R. Helman , Joseph JáJá, Practical parallel algorithms for personalized communication and integer sorting, University of Maryland at College Park, College Park, MD, 1995
	5	David A. Bader , Joseph JáJá, Parallel algorithms for image histogramming and connected components with an experimental study, Journal of Parallel and Distributed Computing, v.35 n.2, p.173-190, June 15, 1996 [doi>10.1006/jpdc.1996.0079]
	6	David A. Bader , Joseph JáJá, Practical parallel algorithms for dynamic data redistribution, median finding, and selection (preliminary draft), University of Maryland at College Park, College Park, MD, 1995
	7	Vasanth Bala , Jehoshua Bruck , Robert Cypher , Pablo Elustando , Alex Ho , Ching-Tien Ho , Shlomo Kipnis , Marc Snir, CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.154-164, February 1995 [doi>10.1109/71.342126]
	8	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
	9	W.W. Carlson and J.M. Draper. AC for the T3D. Technical Report SRC-TR-95-141, Supercomputing Research Center, Bowie, MD, February 1995.
	10	Cray Research, Inc. SHMEM Techn,cal Note for C, October 1994. Revision 2.3.
	11	D.E. Culler, A. Dusseau, S.C. Goldstein, A. Krishnamurthy, S. Lumetta, S. Luna, T. von Eicken, and K. Yelick. Introduction to Split-C. Computer Science Division- EECS, University of California, Berkeley, version 1.0 edition, March 6, 1994.
	12	D.E. Culler, A.C. Dusseau, R.P. Martin, #nd K.E. Schauser. Fast Parallel Sorting Under LogP: From Theory to Practice. In Portability and Performance for Parallel Processing, chapter 4, pages 71-98. John Wiley & Sons, 1993.
	13	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	14	D.R. Helman, D.A. Bader, and J. JgJg. A Parallel Sorting Algorithm With an Experimental Study. Technical Report CS-TR-3549 and UMIACS-TR-95-102, UMI- ACS and Electrical Engineering, University of Maryland, College Park, MD, December 1995.
	15	D.R. Helman, D.A. Bader, and J. J~J#. A Parallel Regular Sorting Algorithm With an Experimental Study. Technical report, UMIACS and Electrical Engineering, University of Maryland, College Park, MD, June 1996. In Preparation.
	16	J.S. Huang and Y.C. Chow. Parallel Sorting and Data Partitioning by Sampling. In Proceedings of the 7th Computer Software and Applications Conference, pages 627-631, November 1983.
	17	Joseph F. JáJá , Kwan Woo Ryu, The Block Distributed Memory Model, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.830-840, August 1996 [doi>10.1109/71.532114]
	18	Michael Kaufmann , Jop F. Sibeyn , Torsten Suel, Derandomizing algorithms for routing and sorting on meshes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.669-679, January 23-25, 1994, Arlington, Virginia, United States
	19	Xiaobo Li , Paul Lu , Jonathan Schaeffer , John Shillington , Pok Sze Wong , Hanmao Shi, On the versatility of parallel sorting by regular sampling, Parallel Computing, v.19 n.10, p.1079-1103, Oct. 1993 [doi>10.1016/0167-8191(93)90019-H]
	20	Me#age Pa#ing Interface Forum. MPI: A Message- Passing Interface Standard. Technical report, University of Tennessee, Knoxville, TN, June 1995. Version 1.1.
	21	S. Ranka , R. V. Shankar , K. A. Alsabti, Many-to-many personalized communication with bounded traffic, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.20, February 06-09, 1995
	22	Satish Rao , Torsten Suel , Thanasis Tsantilas , Mark Goudreau, Efficient communication using total-exchange, Proceedings of the 9th International Symposium on Parallel Processing, p.544-550, April 25-28, 1995
	23	Hanmao Shi , Jonathan Schaeffer, Parallel sorting by regular sampling, Journal of Parallel and Distributed Computing, v.14 n.4, p.361-372, April 1992 [doi>10.1016/0743-7315(92)90075-X]
	24	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

CITED BY 13

	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	Hongzhang Shan , Jaswinder Pal Singh, Parallel sorting on cache-coherent DSM multiprocessors, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.40-es, November 14-19, 1999, Portland, Oregon, United States
	Daniel Jiménez-González , Josep-L. Larriba-Pey , Juan J. Navarro, Communication conscious radix sort, Proceedings of the 13th international conference on Supercomputing, p.76-82, June 20-25, 1999, Rhodes, Greece
	Daniel Jiménez-González , Juan J. Navarro , Josep-L. Larrba-Pey, Fast parallel in-memory 64-bit sorting, Proceedings of the 15th international conference on Supercomputing, p.114-122, June 2001, Sorrento, Italy
	Shin-Jae Lee , Minsoo Jeon , Dongseung Kim , Andrew Sohn, Partitioned parallel radix sort, Journal of Parallel and Distributed Computing, v.62 n.4, p.656-668, April 2002
	Pat Morin, Coarse grained parallel computing on heterogeneous systems, Proceedings of the 1998 ACM symposium on Applied Computing, p.628-634, February 27-March 01, 1998, Atlanta, Georgia, United States
	Andrew Sohn , Yuetsu Kodama, Load balanced parallel radix sort, Proceedings of the 12th international conference on Supercomputing, p.305-312, July 1998, Melbourne, Australia
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	David A. Bader , Bernard M. E. Moret , Peter Sanders, Algorithm engineering for parallel computation, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Miltos D. Grammatikakis , Stefan Liesche, Priority Queues and Sorting Methods for Parallel Simulation, IEEE Transactions on Software Engineering, v.26 n.5, p.401-422, May 2000
	Hongzhang Shan , Erich Strohmaier , Ji Qiang , David H. Bailey , Kathy Yelick, Particles and contiuum---Performance modeling and optimization of a high energy colliding beam simulation code, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
	Jing-Chao Chen, Efficient sample sort and the average case analysis or PEsort, Theoretical Computer Science, v.369 n.1, p.44-66, 15 December 2006
	Minsoo Jeon , Dongseung Kim, High-speed parallel external sorting of data with arbitrary distribution, International Journal of High Performance Computing and Networking, v.2 n.1, p.36-44, March 2004