Parallelism in random access machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallelism in random access machines

Full text

Pdf (459 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the tenth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 114 - 118

Year of Publication: 1978

Authors

Steven Fortune
James Wyllie

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 101, Citation Count: 110

Additional Information:

abstract 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/800133.804339 What is a DOI?

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

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	Barnes, G.H., et.al. "The ILLIAC IV Computer", IEEE Trans. Computers. C-17 (Aug. 1968), pp. 746-757.
	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.
	3	Cook, S.A. and R.A. Reckhow. "Time Bounded Random Access Machines", JCSS 7 (1973),pp. 354-375.
	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.
	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.
	6	D. S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.55-57, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803631]
	7	Kogge, P.M. "Parallel Solution of Recurrence Problems", IBM J. Res. Develop. 18 (March 1974), pp. 138-148.
	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.
	9	Pratt, V.R. and L.J. Stockmeyer. "A Characterization of the Power of Vector Machines", JCSS 12 (1976), pp. 198-221.
	10	Savitch, W.J. "Relationships between Non-deterministic and Deterministic Tape Complexities", JCSS 4 (1970), pp. 177-192.
	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.
	12	Savitch, W.J. "Parallel and Nondeterministic Time Complexity Classes", November 1977, technical report, Dept. APIS, University of California, San Diego, 78-CS-012.

CITED BY 110

	Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States
	Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada
	Patrick W. Dymond , Walter L. Ruzzo, Parallel RAMs with owned global memory and deterministic context-free language recognition, Journal of the ACM (JACM), v.47 n.1, p.16-45, Jan. 2000
	David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996
	Yosee Feldman , Ehud Shapiro, Spatial machines: a more realistic approach to parallel computation, Communications of the ACM, v.35 n.10, p.60-73, Oct. 1992
	Lasse Natvig, Logarithmic time cost optimal parallel sorting is not yet fast in practice!, Proceedings of the 1990 conference on Supercomputing, p.486-494, October 1990, New York, New York, United States
	Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
	M Ben-Or , E Feig , D Kozen , P Tiwari, A fast parallel algorithm for determining all roots of a polynomial with real roots, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.340-349, May 28-30, 1986, Berkeley, California, United States
	Martin Reiman , Paul E. Wright, Performance analysis of concurrent-read exclusive-write, ACM SIGMETRICS Performance Evaluation Review, v.19 n.1, p.168-177, May 1991
	Paul Cull , Tai Hsu, Improved parallel and sequential walking tree methods for biological string alignments, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.51-es, November 14-19, 1999, Portland, Oregon, United States
	Rüdiger Reischuk, Simultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functions, Journal of the ACM (JACM), v.34 n.1, p.163-178, Jan. 1987
	Divyakant Agrawal , Manhoi Choy , Hong Va Leong , Ambuj K. Singh, Maya: a simulation platform for distributed shared memories, ACM SIGSIM Simulation Digest, v.24 n.1, p.151-155, July 1994
	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, ACM SIGPLAN Notices, v.28 n.7, p.1-12, July 1993
	Divyakant Agrawal , Manhoi Choy , Hong Va Leong , Ambuj K. Singh, Mixed consistency: a model for parallel programming (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 14-17, 1994, Los Angeles, California, United States
	Gruia-Catalin Roman , Kenneth C. Cox, Declarative visualization in the shared dataspace paradigm, Proceedings of the 11th international conference on Software engineering, p.34-43, May 1989, Pittsburgh, Pennsylvania, United States
	P. C. Kanellakis , A. A. Shvartsman, Efficient parallel algorithms can be made robust, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.211-219, June 1989, Edmonton, Alberta, Canada
	Paris C. Kanellakis , Dimitrios Michailidis , Alex Allister Shvartsman, Controlling memory access concurrency in efficient fault-tolerant parallel algorithms, Nordic Journal of Computing, v.2 n.2, p.146-180, Summer 1995
	Gary Lewandowski , Anne Condon , Eric Bach, Asynchronous Analysis of Parallel Dynamic Programming Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.425-438, April 1996
	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.13-24, June 24-26, 1996, Padua, Italy
	Bogdan S. Chlebus , Stefan Dobrev , Dariusz R. Kowalski , Grzegorz Malewicz , Alex Shvartsman , Imrich Vrto, Towards practical deteministic write-all algorithms, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.271-280, July 2001, Crete Island, Greece
	A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States
	F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States
	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States
	Xinping Zhu , Sharad Malik, A hierarchical modeling framework for on-chip communication architectures, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.663-671, November 10-14, 2002, San Jose, California
	Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, ACM SIGARCH Computer Architecture News, v.23 n.2, p.24-36, May 1995
	Z. M. Kedem , K. V. Palem , P. G. Spirakis, Efficient robust parallel computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.138-148, May 13-17, 1990, Baltimore, Maryland, United States
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms on restartable fail-stop processors, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.23-36, August 19-21, 1991, Montreal, Quebec, Canada
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	Jaswinder Pal Singh , Edward Rothberg , Anoop Gupta, Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.189-199, June 27-29, 1994, Cape May, New Jersey, United States
	John H. Reif, Symmetric complementation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.201-214, May 05-07, 1982, San Francisco, California, United States
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can shared-memory model serve as a bridging model for parallel computation?, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.72-83, June 23-25, 1997, Newport, Rhode Island, United States
	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
	A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States
	Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany
	John H. Reif, Symmetric Complementation, Journal of the ACM (JACM), v.31 n.2, p.401-421, April 1984
	Klaus Kühnle , Ernst W. Mayr, Exponential space computation of Gröbner bases, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.63-71, July 24-26, 1996, Zurich, Switzerland
	S. Lakshmivarahan , Sudarshan K. Dhall, A new class of parallel algorithms for solving linear tridiagonal systems, Proceedings of 1986 ACM Fall joint computer conference, p.315-324, November 1986, Dallas, Texas, United States
	Eugene Ageenko , Martti Forsell , Pasi Fränti, Context-based compression of binary images in parallel, Software—Practice & Experience, v.32 n.13, p.1223-1237, 10 November 2002
	Yonatan Aumann , Michael A. Bender , Lisa Zhang, Efficient execution of nondeterministic parallel programs on asynchronous systems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.270-276, June 24-26, 1996, Padua, Italy
	Cyrus Shahabi , Farnoush Banaei-Kashani, Decentralized Resource Management for a Distributed Continuous Media Server, IEEE Transactions on Parallel and Distributed Systems, v.13 n.7, p.710-727, July 2002
	Martti J. Forsell, Architectural differences of efficient sequential and parallel computers, Journal of Systems Architecture: the EUROMICRO Journal, v.47 n.13, p.1017-1041, July 2002
	L. Fava Lindon , S. G. Akl, An Optimal Implementation of Broadcasting with Selective Reduction, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.256-269, March 1993
	Z. M. Kedem , K. V. Palem , A. Raghunathan , P. G. Spirakis, Combining tentative and definite executions for very fast dependable parallel computing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.381-390, May 05-08, 1991, New Orleans, Louisiana, United States
	Martti Forsell, A Scalable High-Performance Computing Solution for Networks on Chips, IEEE Micro, v.22 n.5, p.46-55, September 2002
	Alexey Lastovetsky, Adaptive parallel computing on heterogeneous networks with mpC, Parallel Computing, v.28 n.10, p.1369-1407, October 2002
	Thomas Erlebach , Peter Rossmanith , Hans Stadtherr , Agelika Steger , Thomas Zeugmann, Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries, Theoretical Computer Science, v.261 n.1, p.119-156, 06/17/2001
	Yifeng Chen, A fixpoint theory for non-monotonic parallelism, Theoretical Computer Science, v.308 n.1-3, p.367-392, 3 November 2003
	Eric Freudenthal , Allan Gottlieb, Process coordination with fetch-and-increment, ACM SIGPLAN Notices, v.26 n.4, p.260-268, Apr. 1991
	Pao-Ann Hsiung, CMAPS: a cosynthesis methodology for application-oriented parallel systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.1, p.51-81, Jan. 2000
	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, ACM Transactions on Computer Systems (TOCS), v.16 n.3, p.271-318, Aug. 1998
	A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States
	Haim Gaifman , Michael J. Maher , Ehud Shapiro, Replay, recovery, replication, and snapshots of nondeterministic concurrent programs, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.241-255, August 19-21, 1991, Montreal, Quebec, Canada
	John H. Reif, Parallel molecular computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.213-223, June 24-26, 1995, Santa Barbara, California, United States
	Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States
	Gary Lewandowski , Anne Condon , Eric Bach, Asynchronous analysis of parallel dynamic programming, ACM SIGMETRICS Performance Evaluation Review, v.21 n.1, p.268-269, June 1993
	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988
	Ulla Koppenhagen , Ernst W. Mayr, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.55-62, July 24-26, 1996, Zurich, Switzerland
	Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996
	Bradford L. Chamberlain , Sung-Eun Choi , E. Christopher Lewis , Calvin Lin , Lawrence Snyder , W. Derrick Weathersby, ZPL: A Machine Independent Programming Language for Parallel Computers, IEEE Transactions on Software Engineering, v.26 n.3, p.197-211, March 2000
	Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, The complexity of synchronous iterative Do-All with crashes, Distributed Computing, v.17 n.1, p.47-63, February 2004
	C.-W. Ho , R. C. T. Lee, A Parallel Algorithm for Solving Sparse Triangular Systems, IEEE Transactions on Computers, v.39 n.6, p.848-852, June 1990
	G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989
	Yifeng Chen , J. W. Sanders, Logic of global synchrony, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.221-262, March 2004
	Assefaw Hadish Gebremedhin , Isabelle Guérin Lassous , Jens Gustedt , Jan Arne Telle, Graph coloring on coarse grained multicomputers, Discrete Applied Mathematics, v.131 n.1, p.179-198, 6 September 2003
	Jeffrey Scott Vitter , Roger A. Simons, Parallel algorithms for unification and other complete problems in p, Proceedings of the 1984 annual conference of the ACM on The fifth generation challenge, p.75-84, January 1984
	Thomas Grün , Thomas Rauber , Jochen Röhrig, Support for Efficient Programming on the SB-PRAM, International Journal of Parallel Programming, v.26 n.3, p.209-240, June 1998
	Martti Forsell, A parallel computer as a NOC region, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
	J. J. Little , G. E. Blelloch , T. A. Cass, Algorithmic Techniques for Computer Vision on a Fine-Grained Parallel Machine, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.3, p.244-257, March 1989
	Alexey Lastovetsky , Ravi Reddy, On performance analysis of heterogeneous parallel algorithms, Parallel Computing, v.30 n.11, p.1195-1216, November 2004
	Patrick W. Dymond , Martin Tompa, Speedups of deterministic machines by synchronous parallel machines, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.336-343, December 1983
	D. C. R. Ju , C. L. Wu , P. Carini, The Classification, Fusion, and Parallelization of Array Language Primitives, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1113-1120, October 1994
	Cyrus Shahabi , Farnoush Banaei-Kashani, Decentralized Resource Management for a Distributed Continuous Media Server, IEEE Transactions on Parallel and Distributed Systems, v.13 n.11, p.1183-1200, November 2002
	Yan Tang , Tao Wang , Xiaoming Li, The design and implementation of LilyTask in shared memory, ACM SIGOPS Operating Systems Review, v.39 n.3, p.52-63, July 2005
	S. A. Jarvis , J. M. D. Hill , C. J. Siniolakis , V. P. Vasilev, Portable and architecture independent parallel performance tuning using BSP, Parallel Computing, v.28 n.11, p.1587-1609, November 2002
	Thierry Gautier , Hamid-Reza Hamidi, Automatic re-scheduling of dependencies in a RPC-based grid, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Haim Kaplan , Elad Verbin, Sorting signed permutations by reversals, revisited, Journal of Computer and System Sciences, v.70 n.3, p.321-341, May 2005
	Grzegorz Malewicz, A tight analysis and near-optimal instances of the algorithm of Anderson and Woll, Theoretical Computer Science, v.329 n.1-3, p.285-301, 13 December 2004
	D. A. Grove , P. D. Coddington, Communication Benchmarking and Performance Modelling of MPI Programs on Cluster Computers, The Journal of Supercomputing, v.34 n.2, p.201-217, November 2005
	Martha Mercaldi , Steven Swanson , Andrew Petersen , Andrew Putnam , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Modeling instruction placement on a spatial architecture, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Matteo Frigo , Volker Strumpen, The cache complexity of multithreaded cache oblivious algorithms, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	A. Dal Palú , E. Pontelli , D. Ranjan, Sequential and parallel algorithms for the NCA problem on pure pointer machines, Theoretical Computer Science, v.352 n.1, p.108-135, 7 March 2006
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, v.5 n.4, p.201-217, April 1992
	Martti J. Forsell, Are multiport memories physically feasible?, ACM SIGARCH Computer Architecture News, v.22 n.5, p.3-10, Dec. 1994
	Henk Alblas , Rieks op den Akker , Paul Oude Luttighuis , Klaas Sikkel, A bibliography on parallel parsing, ACM SIGPLAN Notices, v.29 n.1, p.54-65, Jan. 1994
	Martti J. Forsell, Are multiport memories physically feasible?, ACM SIGARCH Computer Architecture News, v.22 n.4, p.47-54, Sept. 1994
	Mark D. Hill, What is scalability?, ACM SIGARCH Computer Architecture News, v.18 n.4, p.18-21, Dec. 1990
	Thierry Gautier , Hamid-Reza Hamidi, Re-scheduling invocations of services for RPC grids, Computer Languages, Systems and Structures, v.33 n.3-4, p.168-178, October, 2007
	Assefaw Hadish Gebremedhin , Mohamed Essaïdi , Isabelle Guérin Lassous , Jens Gustedt , Jan Arne Telle, PRO: a model for the design and analysis of efficient and scalable parallel algorithms, Nordic Journal of Computing, v.13 n.4, p.215-239, December 2006
	Jan Edler , Allan Gottlieb , Clyde P. Kruskal , Kevin P. McAuliffe , Larry Rudolph , Marc Snir , Patricia J. Teller , James Wilson, Issues related to MIMD shared-memory computers: the NYU ultracomputer approach, ACM SIGARCH Computer Architecture News, v.13 n.3, p.126-135, June 1985
	Keqin Li , Yi Pan , Si Qing Zheng, Efficient Deterministic and Probabilistic Simulations of PRAMs on Linear Arrays with Reconfigurable Pipelined Bus Systems, The Journal of Supercomputing, v.15 n.2, p.163-181, Feb.1.2000
	Kirk W. Cameron , Rong Ge, Predicting and Evaluating Distributed Communication Performance, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.43, November 06-12, 2004
	Mark F. Adams , Harun H. Bayraktar , Tony M. Keaveny , Panayiotis Papadopoulos, Ultrascalable Implicit Finite Element Analyses in Solid Mechanics with over a Half a Billion Degrees of Freedom, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.34, November 06-12, 2004
	V. K. Prasanna Kumar , C. S. Raghavendra, Array processor with multiple broadcasting, ACM SIGARCH Computer Architecture News, v.13 n.3, p.2-10, June 1985
	M. Rasit Eskicioglu, A comprehensive bibliography of distributed shared memory, ACM SIGOPS Operating Systems Review, v.30 n.1, p.71-96, Jan. 1996
	I Parberry, Parallel speedup of sequential machines: a defense of parallel computation thesis, ACM SIGACT News, v.18 n.1, p.54-67, Summer 1986
	S. W. Hornick , F. P. Preparata, Deterministic P-RAM simulation with constant redundancy, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.103-109, June 18-21, 1989, Santa Fe, New Mexico, United States
	T. W. Lam , W. L. Ruzzo, The power of parallel pointer manipulation, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.92-102, June 18-21, 1989, Santa Fe, New Mexico, United States
	Lorin Hochstein , Victor R. Basili , Uzi Vishkin , John Gilbert, A pilot study to compare programming effort for two parallel programming models, Journal of Systems and Software, v.81 n.11, p.1920-1930, November, 2008
	Brian Holland , Karthik Nagarajan , Chris Conger , Adam Jacobs , Alan D. George, RAT: a methodology for predicting performance in application design migration to FPGAs, Proceedings of the 1st international workshop on High-performance reconfigurable computing technology and applications: held in conjunction with SC07, November 11-11, 2007, Reno, Nevada
	John H. Reif , Simon Kasif , Deepak Sherlekar, Formula dissection: A parallel algorithm for constraint satisfaction, Computers & Mathematics with Applications, v.55 n.6, p.1170-1177, March, 2008
	Xiangzhen Qiao , Shuqing Chen , Laurence Tianruo Yang, HPM: a hierarchical model for parallel computations, International Journal of High Performance Computing and Networking, v.1 n.1-3, p.117-127, August 2004
	Maurice Herlihy , Victor Luchangco, Distributed computing and the multicore revolution, ACM SIGACT News, v.39 n.1, March 2008
	Jose Luis Bosque , Luis Pastor, A Parallel Computational Model for Heterogeneous Clusters, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1390-1400, December 2006
	Wolf Zimmermann , Welf Lowe, Foundations for the integration of scheduling techniques into compilers for parallel languages, International Journal of Computational Science and Engineering, v.1 n.2-4, p.99-109, May 2005
	Reza Dorrigiv , Alejandro López-Ortiz , Alejandro Salinger, Optimal speedup on a low-degree multi-core parallel architecture (LoPRAM), Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Kirk W. Cameron , Rong Ge , Xian-He Sun, $\log_{\rm n}{\rm P}$ and $\log_{3}{\rm P}$: Accurate Analytical Models of Point-to-Point Communication in Distributed Systems, IEEE Transactions on Computers, v.56 n.3, p.314-327, March 2007
	John E. Savage , Mohammad Zubair, A unified model for multicore architectures, Proceedings of the 1st international forum on Next-generation multicore/manycore technologies, November 24-25, 2008, Cairo, Egypt
	Qiming Hou , Kun Zhou , Baining Guo, BSGP: bulk-synchronous GPU programming, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Brian Holland , Karthik Nagarajan , Alan D. George, RAT: RC Amenability Test for Rapid Performance Prediction, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.1 n.4, p.1-31, January 2009
	Martti Forsell, Configurable emulated shared memory architecture for general purpose MP-SOCs and NOC regions, Proceedings of the 2009 3rd ACM/IEEE International Symposium on Networks-on-Chip, p.163-172, May 10-13, 2009