Article

Free access

Efficient parallel algorithms for some integer problems

Authors:

Weixiong Zhang,

Zhaofang WenAuthors Info & Claims

CSC '91: Proceedings of the 19th annual conference on Computer Science

Pages 11 - 20

https://doi.org/10.1145/327164.327169

Published: 01 April 1991 Publication History

PDF eReader

References

[1]

R.P. Brent, "The parallel evaluation of general arithmetic expressions," J. ACM, vol. 21, 1974, pp.201-206.

Digital Library

Google Scholar

[2]

R. Cole and U. Vishkin, "Approximate and exact parallel scheduling with application to list, tree and graph," Proc. 27-th Annual Syrup. on Foundations of Computer Science, 1986, pp.487-491.

Google Scholar

[3]

J. Gil, and L. Rudolph, "Counting and packing in parallel," Proc. 1986 Intern. Conf. on Parallel Processing, 1986, pp. 1000-1002.

Google Scholar

[4]

T. Hagemp, "Towards optimal parallel bucket sorting," Information and Computation, vol.75, 1987, pp.39-51.

Digital Library

Google Scholar

[5]

D.S. Hirschberg, "Fast parallel sorting algorithm," C. ACM, vol.21, no.8, 1978, pp.657-661.

Digital Library

Google Scholar

[6]

R.M. Karp, and V. Ramachanclran, "A survey of parallel algorithms for shared-memory machines," Rep. No. UCB/CSD 88/408, Computer Science Division, University of California, Berkeley, CA 94720, March, 1988.

Digital Library

Google Scholar

[7]

D.E. Knuth, The Art of Computer Programming, Vol.3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973.

Digital Library

Google Scholar

[8]

C.P. Kruskal, L. Rudolph, and M. Snir, "Efficient parallel algorithms for graph problems," Algorithmica, vol.5, 1990, pp.43-64.

Crossref

Google Scholar

[9]

J.H. Reif, "An optimal parallel algorithm for integer sorting," Proc. 26-th Annual Syrup. on foundations of Computer Science, 1985, pp.496- 503.

Google Scholar

[10]

A.C-C. Yao, "Lower bounds for algebraic computation trees with integer inputs," Proc. 30-th Annual Syrup. on foundations of Computer Science, 1989, pp.308-313.

Digital Library

Google Scholar

[11]

R.A. Wagner, and Y. Han, "Parallel algorithms for bucket sorting and the data dependent prefix problem," Proc. 1986 Intern. Conf. on Parallel Processing, 1986, pp.924-930.

Google Scholar

Efficient parallel algorithms for some integer problems
1. Computing methodologies
  1. Parallel computing methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
  2. Models of computation
    1. Concurrency

Recommendations

Parallel Self-Index Integer Sorting

We consider the problem of sorting n integers when the elements are drawn from the restricted domain [1… n ]. A new deterministic parallel algorithm for sorting n integers is obtained. Its running time is O(log n log( n /log n )) using n /...
Efficient Parallel Algorithms for Selection and Searching on Sorted Matrices
IPPS '92: Proceedings of the 6th International Parallel Processing Symposium

Parallel algorithms for more general versions of the well known selection and searching problems are formulated. The authors look at these problems when the set of elements can be represented as an n*n matrix with sorted rows and columns. The selection ...
A note on reducing parallel model simulations to integer sorting
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

We show that simulating a step of a FETCH&ADD PRAM model on an EREW PRAM model can be made as efficient as integer sorting. In particular, we present several efficient reductions of the simulation problem to various integer sorting problems. By using ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CSC '91: Proceedings of the 19th annual conference on Computer Science

April 1991

711 pages

ISBN:0897913825

DOI:10.1145/327164

Chairmen:
C. Jinshong (C. J.) Hwang
Southwest Texas State Univ., San Marcos
,
Richard Brice
MCC

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
778
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Recommendations

Parallel Self-Index Integer Sorting

Efficient Parallel Algorithms for Selection and Searching on Sorted Matrices

A note on reducing parallel model simulations to integer sorting