Article

Free access

Parallelism in random access machines

Authors:

Steven Fortune,

James WyllieAuthors Info & Claims

STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computing

Pages 114 - 118

https://doi.org/10.1145/800133.804339

Published: 01 May 1978 Publication History

PDF eReader

Abstract

A model of computation based on random access machines operating in parallel and sharing a common memory is presented. The computational power of this model is related to that of traditional models. In particular, deterministic parallel RAM's can accept in polynomial time exactly the sets accepted by polynomial tape bounded Turing machines; nondeterministic RAM's can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded Turing machines. Similar results hold for other classes. The effect of limiting the size of the common memory is also considered.

References

[1]

Barnes, G.H., et.al. "The ILLIAC IV Computer", IEEE Trans. Computers. C-17 (Aug. 1968), pp. 746-757.

Digital Library

Google Scholar

[2]

Chandra, A.K. and L.J. Stockmeyer. "Alteration", Proc. of the 17th Annual IEEE Symposium on Foundations of Computer Science, Houston, Texas, Oct. 1976, pp. 98-108.

Google Scholar

[3]

Cook, S.A. and R.A. Reckhow. "Time Bounded Random Access Machines", JCSS 7 (1973),pp. 354-375.

Digital Library

Google Scholar

[4]

Csanky, L. "Fast Parallel Matrix Inversion Algorithms", Proc. of the 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, Oct. 1975, pp. 11-12.

Google Scholar

[5]

Hartmanis, J. and J. Simon. "On the Power of Multiplication in Random Access Machines", Proc. of the 15th Annual IEEE Symposium on Switching and Automata Theory, New Orleans, Oct. 1974, pp. 13-23.

Digital Library

Google Scholar

[6]

Hirschberg, D.S. "Parallel Algorithms for the Transitive Closure and the Connected Component Problems", Proc. of the 8th Annual ACM Symposium on Theory of Computing, Hershey, Penn., May 1976, pp. 55-57.

Digital Library

Google Scholar

[7]

Kogge, P.M. "Parallel Solution of Recurrence Problems", IBM J. Res. Develop. 18 (March 1974), pp. 138-148.

Digital Library

Google Scholar

[8]

Kozen, D. "On Parallelism in Turing Machines", Proc. of the 17th Annual IEEE Symposium on Foundations of Computer Science, Houston, Texas, Oct. 1976, pp. 89-97.

Google Scholar

[9]

Pratt, V.R. and L.J. Stockmeyer. "A Characterization of the Power of Vector Machines", JCSS 12 (1976), pp. 198-221.

Digital Library

Google Scholar

[10]

Savitch, W.J. "Relationships between Non-deterministic and Deterministic Tape Complexities", JCSS 4 (1970), pp. 177-192.

Digital Library

Google Scholar

[11]

Savitch, W.J. and M.J. Stimson. "Time Bounded Random Access Machines with Parallel Processing", Sept. 1976, (revised Aug. 1977)., technical report, Dept. APIS, University of California, San Diego, 78-CS-011.

Google Scholar

[12]

Savitch, W.J. "Parallel and Nondeterministic Time Complexity Classes", November 1977, technical report, Dept. APIS, University of California, San Diego, 78-CS-012.

Google Scholar

Cited By

View all

Šmelko AKratochvíl MBarillot ENoël V(2024)Maboss for HPC environments: implementations of the continuous time Boolean model simulator for large CPU clusters and GPU acceleratorsBMC Bioinformatics10.1186/s12859-024-05815-525:1Online publication date: 24-May-2024
https://doi.org/10.1186/s12859-024-05815-5
Anderson DBlelloch GAgrawal KPetrank E(2024)Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic TreesProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659976(247-258)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659976
Afek YGiladi GPatt-Shamir B(2024)Distributed computing with the cloudDistributed Computing10.1007/s00446-024-00460-w37:1(1-18)Online publication date: 1-Feb-2024
https://doi.org/10.1007/s00446-024-00460-w
Show More Cited By

Index Terms

Parallelism in random access machines
1. Theory of computation
  1. Models of computation
    1. Computability
      1. Turing machines
    2. Concurrency
      1. Parallel computing models

Recommendations

Parallelism in Random Access Machines
On Parallelism in Turing Machines
Reversal-bounded multipushdown machines

Several representations of the recursively enumerable (r.e.) sets are presented. The first states that every r.e. set is the homomorphic image of the intersection of two linear context-free languages. The second states that every r.e. set is accepted by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computing

May 1978

342 pages

ISBN:9781450374378

DOI:10.1145/800133

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 May 1978

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 80 of 270 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

535
Total Citations
View Citations
591
Total Downloads

Downloads (Last 12 months)211
Downloads (Last 6 weeks)23

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Šmelko AKratochvíl MBarillot ENoël V(2024)Maboss for HPC environments: implementations of the continuous time Boolean model simulator for large CPU clusters and GPU acceleratorsBMC Bioinformatics10.1186/s12859-024-05815-525:1Online publication date: 24-May-2024
https://doi.org/10.1186/s12859-024-05815-5
Anderson DBlelloch GAgrawal KPetrank E(2024)Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic TreesProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659976(247-258)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659976
Afek YGiladi GPatt-Shamir B(2024)Distributed computing with the cloudDistributed Computing10.1007/s00446-024-00460-w37:1(1-18)Online publication date: 1-Feb-2024
https://doi.org/10.1007/s00446-024-00460-w
Middelburg C(2024)Imperative Process Algebra and Models of Parallel ComputationTheory of Computing Systems10.1007/s00224-024-10164-068:3(529-570)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00224-024-10164-0
Middelburg C(2024)On the Formalization of the Notion of an AlgorithmThe Practice of Formal Methods10.1007/978-3-031-66673-5_2(23-44)Online publication date: 4-Sep-2024
https://doi.org/10.1007/978-3-031-66673-5_2
Tian W(2023)Research on Curriculum Design Method of Teaching Resource Library based on Deep Learning TechnologyHighlights in Science, Engineering and Technology10.54097/hset.v35i.704835(157-161)Online publication date: 11-Apr-2023
https://doi.org/10.54097/hset.v35i.7048
Cook S(2023)Towards a Complexity Theory of Synchronous Parallel ComputationLogic, Automata, and Computational Complexity10.1145/3588287.3588301(219-244)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3588287.3588301
Forsell MRoivainen JLeppänen VTräff J(2023)Preliminary Performance and Memory Access Scalability Study of Thick Control Flow Processors2023 IEEE Nordic Circuits and Systems Conference (NorCAS)10.1109/NorCAS58970.2023.10305463(1-7)Online publication date: 31-Oct-2023
https://doi.org/10.1109/NorCAS58970.2023.10305463
Sharif MHines TGhafoor SMorales-Hernández MDullo TKalyanapu A(2023)A Performance Prediction Model for Structured Grid Based Applications in HPC Environments2023 22nd International Symposium on Parallel and Distributed Computing (ISPDC)10.1109/ISPDC59212.2023.00016(77-84)Online publication date: Jul-2023
https://doi.org/10.1109/ISPDC59212.2023.00016
Fraccaroli LGiugno RCancellieri SBusato FBombieri N(2023)FAST-CON: a Multi-source Approach for Efficient S- T Connectivity on Sparse Graphs2023 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC58863.2023.10363544(1-6)Online publication date: 25-Sep-2023
https://doi.org/10.1109/HPEC58863.2023.10363544
Show More Cited By

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.

Cited By

Index Terms

Recommendations

Parallelism in Random Access Machines

On Parallelism in Turing Machines

Reversal-bounded multipushdown machines