A bridging model for parallel computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A bridging model for parallel computation

Full text

Pdf (1.10 MB)

Source

Communications of the ACM archive
Volume 33 , Issue 8 (August 1990) table of contents

Pages: 103 - 111

Year of Publication: 1990

ISSN:0001-0782

Author

Leslie G. Valiant

Harvard Univ., Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 48, Downloads (12 Months): 362, Citation Count: 242

Additional Information:

abstract references cited by index terms review 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/79173.79181 What is a DOI?

ABSTRACT

The success of the von Neumann model of sequential computation is attributable to the fact that it is an efficient bridge between software and hardware: high-level languages can be efficiently compiled on to this model; yet it can be effeciently implemented in hardware. The author argues that an analogous bridge between software and hardware in required for parallel computation if that is to become as widely used. This article introduces the bulk-synchronous parallel (BSP) model as a candidate for this role, and gives results quantifying its efficiency both in implementing high-level language features and algorithms, as well as in being implemented in hardware.

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	Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
	2	Aiello, B., Leighton, FT., Maggs, B., and Neumann, M. Fast algorithms for bit-serial routing on a hypercube. Manuscript, 1990.
	3	Anderson, R.J. and Miller, G.L. Optical communication for pointer based algorithms. Tech. Pep. CRI 88-14, Computer Science Dept~, Univ. of Southern California, 1988.
	4	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	5	Carter, J.L. and Wegman, M.N. Universal classes of hash functions. J. Comput. Syst. Sci. 18 (1979) 143-154.
	6	David Eppstein , Zvi Galil, Parallel algorithmic techniques for combinatorial computation, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
	7	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72953]
	8	Gottlieb, A. et al. The NYU ultracomputer-- Designing an MIMD shared memory parallel computer. IEEE 7~ans. Comput. 32, 2 (1983) 175-189.
	9	Hoeffding, W. Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J. 58 (1963) 13-30.
	10	Anna R. Karlin , Eli Upfal, Parallel hashing: an efficient implementation of shared memory, Journal of the ACM (JACM), v.35 n.4, p.876-892, Oct. 1988 [doi>10.1145/48014.350550]
	11	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	12	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
	13	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	14	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	15	Nick Littlestone, From on-line to batch learning, Proceedings of the second annual workshop on Computational learning theory, p.269-284, December 1989, Santa Cruz, California, United States
	16	Maniloff, E.S.,Johnson, K.M., and Reif, J.H. Holographic routing network for parallel processing machines. Society of Photo Optical Instrumentation Engineers (SPIE), Paris, France 1989, V 1136, Holographic Optics II, Principles and Applications, 283-289.
	17	Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
	18	Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
	19	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	20	Ranade, A.G. How to emulate shared memory. In Proceedings of the Twenty-eighth IEEE Symposium on Foundations of Computer Science (1987) pp. 185-194.
	21	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
	22	Siegel, A. On universal classes of fast high performance hash functions. In Proceedings of the Thirtieth IEEE Symposium on Foundations of Computer Science (1989).
	23	Lawrence Snyder, Type architectures, shared memory, and the corollary of modest potential, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
	24	Turing, A.M. On computable numbers with an application to the Entscheidungs problem. In Proceedings of the London Mathematical Society 42 2 (1936) 230-265; correction, ibidem 43 (1937) 544-546.
	25	Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
	26	Valiant, L.G. A scheme for fast parallel communication. SIAM jr. Comput. 11 (1982) 350-361.
	27	Valiant, L.G. Optimally universal parallel computers. Phil. Trans. R. Soc. Lond. A326 (1988) 373-376.
	28	Valiant, L.G. Bulk-synchronous parallel computers. In Parallel Processing and Artificial Intelligence, M. Reeve and S.E. Zenith, Eds., Wiley, 1989 15-22.
	29	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	30	D. W. Walker, Portable programming within a message-passing model: the FFT as an example, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1438-1450, January 1989, Pasadena, California, United States [doi>10.1145/63047.63100]

CITED BY 242

	Uzi Vishkin , Shlomit Dascal , Efraim Berkovich , Joseph Nuzman, Explicit multi-threading (XMT) bridging models for instruction parallelism (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.140-151, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	J.-M. Jézéquel, An object-oriented framework for data parallelism, ACM Computing Surveys (CSUR), v.32 n.1es, March 2000
	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, 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
	Voon-Yee Vee , Wen-Jing Hsu, Locality-preserving load-balancing mechanisms for synchronous simulations on shared-memory multiprocessors, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.131-138, May 28-31, 2000, Bologna, Italy
	Adnan Agbaria , Yosi Ben-Asher , Ilan Newman, Communication-processor tradeoffs in limited resources PRAM, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.74-82, June 27-30, 1999, Saint Malo, France
	Adnan Agbaria , Yosi Ben-Asher , Ilan Newman, Communication-processor tradeoffs in limited resources PRAM, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.74-82, June 27-30, 1999, Saint Malo, France
	Chun-Hsi Huang , Xin He, Finding a Hamiltonian paths in tournaments on clusters - a provably communication-efficient approach, Proceedings of the 2001 ACM symposium on Applied computing, p.549-553, March 2001, Las Vegas, Nevada, United States
	ChiShih Chang , Victor L. Wallace, Multiple feedback queue as a model of general purpose multiprocessor systems, Proceedings of the 1992 ACM annual conference on Communications, p.493-500, March 03-05, 1992, Kansas City, Missouri, United States
	Jesper Larsson Traff , Hubert Ritzdorf , Rolf Hempel, The implementation of MPI-2 one-sided communication for the NEC SX-5, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.1-es, November 04-10, 2000, Dallas, Texas, United States
	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
	Mark M. Mathis , Nancy M. Amato , Marvin L. Adams, A general performance model for parallel sweeps on orthogonal grids for particle transport calculations, Proceedings of the 14th international conference on Supercomputing, p.255-263, May 08-11, 2000, Santa Fe, New Mexico, United States
	Philip D. MacKenzie , Vijaya Ramachandran, Computational bounds for fundamental problems on general-purpose parallel models, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.152-163, June 28-July 02, 1998, Puerto Vallarta, Mexico
	David B. Skillicorn , Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys (CSUR), v.30 n.2, p.123-169, June 1998
	Xiaoyu Zhang , Chandrajit Bajaj , William Blanke, Scalable isosurface visualization of massive datasets on COTS clusters, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
	Matthew I. Frank , Anant Agarwal , Mary K. Vernon, LoPC: modeling contention in parallel algorithms, ACM SIGPLAN Notices, v.32 n.7, p.276-287, July 1997
	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Phillip B. Gibbons , Michael Merritt, Specifying non-blocking shared memories (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.306-315, June 29-July 01, 1992, San Diego, California, United States
	Chun-Hsi Huang, Grid-enabled parallel divide-and-conquer: theory and practice, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Lars S. Nyland , Jan F. Prins , Allen Goldberg , Peter H. Mills, A Design Methodology for Data-Parallel Applications, IEEE Transactions on Software Engineering, v.26 n.4, p.293-314, April 2000
	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP, and LogP: a framework for general-purpose parallel algorithm design, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.957-958, January 17-19, 1999, Baltimore, Maryland, United States
	Olaf Bonorden , Joachim von zur Gathen , Jürgen Gerhard , Olaf Müller, Factoring a binary polynomial of degree over one million, ACM SIGSAM Bulletin, v.35 n.1, p.16-18, March 2001
	A. Cavarra , E. Riccobene , A. Zavanella, A formal model for the parallel semantics of P3L, Proceedings of the 2000 ACM symposium on Applied computing, p.804-812, March 2000, Como, Italy
	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
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Efficient low-contention parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.236-247, June 27-29, 1994, Cape May, New Jersey, United States
	Peter Ladkin , Barbara Simons, Compile-time analysis of communicating processes, Proceedings of the 6th international conference on Supercomputing, p.248-259, July 19-24, 1992, Washington, D. C., United States
	Mauricio Marín, Billiards and related systems on the bulk-synchronous parallel model, ACM SIGSIM Simulation Digest, v.27 n.1, p.164-171, July 1997
	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, 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
	William E. Cohen , David W. Hyde , Rhonda K. Gaede, An Optical Bus-Based Distributed Dynamic Barrier Mechanism, IEEE Transactions on Computers, v.49 n.12, p.1354-1365, December 2000
	Guy E. Blelloch , Perry Cheng , Phillip B. Gibbons, Room synchronizations, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.122-133, July 2001, Crete Island, Greece
	Uzi Vishkin, From algorithm parallelism to instruction-level parallelism: an encode-decode chain using prefix-sum, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.260-271, June 23-25, 1997, Newport, Rhode Island, United States
	Xiaotie Deng , Nian Gu , Tim Brecht , KaiCheng Lu, Preemptive scheduling of parallel jobs on multiprocessors, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.159-167, January 28-30, 1996, Atlanta, Georgia, United States
	David F. Hegarty , M. T. Kechadi, Topology preserving dynamic load balancing for parallel molecular simulations, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-19, November 15-21, 1997, San Jose, CA
	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
	Jörg Henrichs, Optimizing and load balancing metacomputing applications, Proceedings of the 12th international conference on Supercomputing, p.165-171, July 1998, Melbourne, Australia
	Michael T. Goodrich, Communication-efficient parallel sorting (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.247-256, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Matthew Andrews , Tom Leighton , P. Takis Metaxas , Lisa Zhang, Automatic methods for hiding latency in high bandwidth networks (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.257-265, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Tim Purcell, Parallel ray tracing on a chip, Practical parallel rendering, A. K. Peters, Ltd., Natick, MA, 2002
	Mark W. Goudreau , Kevin Lang , Girija Narlikar , Satish B. Rao, BOS is boss: a case for bulk-synchronous object systems, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.115-125, June 27-30, 1999, Saint Malo, France
	Mihály Geréb-Graus , Thanasis Tsantilas, Efficient optical communication in parallel computers, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.41-48, June 29-July 01, 1992, San Diego, California, United States
	Gregory V. Wilson, A Glossary of Parallel Computing Terminology, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.1, p.52-67, February 1993
	Spyros C. Kontogiannis , Grammati E. Pantziou , Paul G. Spirakis , Moti Yung, “Dynamic-fault-prone BSP”: a paradigm for robust computations in changing environments, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.37-46, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Alfredo Goldman , Gregory Mounie , Denis Trystram, 1-Optimality of static BSP computations: scheduling independent chains as a case study, Theoretical Computer Science, v.290 n.3, p.1331-1359, 3 January 2003
	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
	Naohito Sato , Satoshi Matsuoka , Jean-Marc Jézéquel , Akinori Yonezawa, A methodology for specifying data distribution using only standard object-oriented features, Proceedings of the 11th international conference on Supercomputing, p.116-123, July 07-11, 1997, Vienna, Austria
	C. E. R. Alves , E. N. Cáceres , F. Dehne, Parallel dynamic programming for solving the string editing problem on a CGM/BSP, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	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
	Armin Baumker , Wolfgang Dittrich, Fully dynamic search trees for an extension of the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.233-242, June 24-26, 1996, Padua, Italy
	Manfred R. Jobmann , Johann Schumann, Performance analysis of a parallel theorem prover, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.259-260, June 1992
	Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, ACM SIGPLAN Notices, v.33 n.5, p.212-223, May 1998
	Malcolm Yoke Hean Low, Parallel and distributed simulation: managing external workload with BSP time warp, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	Frank Dehne , Wolfgang Dittrich , David Hutchinson, Efficient external memory algorithms by simulating coarse-grained parallel algorithms, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.106-115, June 23-25, 1997, Newport, Rhode Island, United States
	Michael Nöcker, Some remarks on parallel exponentiation (extended abstract), Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.250-257, July 2000, St. Andrews, Scotland
	Susumu Shibusawa , Hiroyuki Makino , Shigeki Nimiya , Jun-ichi Hatta, Scatter and gather operations on an asynchronous communication model, Proceedings of the 2000 ACM symposium on Applied computing, p.685-691, March 2000, Como, Italy
	F. J. Seinstra , D. Koelma, P-3PC: A Point-to-Point Communication Model for Automatic and Optimal Decomposition of Regular Domain Problems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.7, p.758-768, July 2002
	B. H. H. Juurlink , H. A. G. Wijshoff, Experiences with a model for parallel computation, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.87-96, August 15-18, 1993, Ithaca, New York, United States
	Bruce M. Maggs , Berthold Vöcking, Improved routing and sorting on multibutterflies, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.517-530, May 04-06, 1997, El Paso, Texas, United States
	Mark Goudreau , Kevin Lang , Satish Rao , Torsten Suel , Thanasis Tsantilas, Towards efficiency and portability: programming with the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.1-12, 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
	R. Andonov , S. Balev , S. Rajopadhye , N. Yanev, Optimal semi-oblique tiling, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.153-162, July 2001, Crete Island, Greece
	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany
	Matthew Andrews , Tom Leighton , P. Takis Metaxas , Lisa Zhang, Improved methods for hiding latency in high bandwidth networks (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.52-61, June 24-26, 1996, Padua, Italy
	Gianfranco Bilardi , Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci , Paul Spirakis, BSP vs LogP, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.25-32, June 24-26, 1996, Padua, Italy
	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
	Michael C. Loui, Strategic directions in research in theory of computing, ACM Computing Surveys (CSUR), v.28 n.4, p.575-590, Dec. 1996
	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
	Francisco Almeida , Rumen Andonov , Daniel Gonzalez , Luz M. Moreno , Vincent Poirriez , Casiano Rodriguez, Optimal tiling for the RNA base pairing problem, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	Guy E. Blelloch , Margaret Reid-Miller, Pipelining with futures, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.249-259, June 23-25, 1997, Newport, Rhode Island, United States
	Thomas H. Cormen , Michael T. Goodrich, A bridging model for parallel computation, communication, and I/O, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	Thomas Rauber , Gudula Rünger, Performance predictions for parallel diagonal-implicitly iterated Runge-Kutta methods, ACM SIGSIM Simulation Digest, v.25 n.1, p.21-28, July 1995
	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
	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
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
	David R. Helman , David A. Bader , Joseph JáJá, Parallel algorithms for personalized communication and sorting with an experimental study (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.211-222, June 24-26, 1996, Padua, Italy
	Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy
	Robert D. Blumofe , Charles E. Leiserson, Space-efficient scheduling of multithreaded computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.362-371, May 16-18, 1993, San Diego, California, United States
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Deterministic sorting and randomized median finding on the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.223-232, June 24-26, 1996, Padua, Italy
	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
	Domenico Talia, Parallel computation still not ready for the mainstream, Communications of the ACM, v.40 n.7, p.98-99, July 1997
	Yonatan Aumann , Michael Ben-Or, Computing with faulty arrays, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.162-169, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	Jens Gustedt, Randomized permutations in a coarse grained parallel environment, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Alexey Lastovetsky, Adaptive parallel computing on heterogeneous networks with mpC, Parallel Computing, v.28 n.10, p.1369-1407, October 2002
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Architecture independent parallel selection with applications to parallel priority queues, Theoretical Computer Science, v.301 n.1-3, p.119-142, 14 May 2003
	A. van Heukelum , G. T. Barkema , R. H. Bisseling, DNA electrophoresis studied with the cage model, Journal of Computational Physics, v.180 n.1, p.313-326, July 20, 2002
	Scott B. Baden , Stephen J. Fink, Communication overlap in multi-tier parallel algorithms, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 07-13, 1998, San Jose, CA
	Ville Leppänen , Martti Penttonen, Work-optimal simulation of PRAM models on meshes, Nordic Journal of Computing, v.2 n.1, p.51-69, March 1995
	Jop F. Sibeyn, List-ranking on interconnection networks, Information and Computation, v.181 n.2, p.75-87, March 15, 2003
	Alexandros V. Gerbessiotis, Architecture independent parallel binomial tree option price valuations, Parallel Computing, v.30 n.2, p.301-316, February 2004
	L. A. Laranjeira , M. Malek , R. Jenevein, Nest: A Nested-Predicate Scheme for Fault Tolerance, IEEE Transactions on Computers, v.42 n.11, p.1303-1324, November 1993
	Mark Lanthier , Doron Nussbaum , Jörg-Rüdiger Sack, Parallel implementation of geometric shortest path algorithms, Parallel Computing, v.29 n.10, p.1445-1479, October 2003
	F. J. Seinstra , D. Koelma, Incorporating memory layout in the modeling of message passing programs, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.3, p.109-121, August 2003
	Ben Juurlink , Petr Kolman , Friedhelm Meyer auf der Heide , Ingo Rieping, Optimal broadcast on parallel locality models, Journal of Discrete Algorithms, v.1 n.2, p.151-166, April 2003
	Yifeng Chen, A fixpoint theory for non-monotonic parallelism, Theoretical Computer Science, v.308 n.1-3, p.367-392, 3 November 2003
	M. Cemil Azizoglu , Ömer Egecioglu, Lower Bounds on Communication Loads and Optimal Placements in Torus Networks, IEEE Transactions on Computers, v.49 n.3, p.259-266, March 2000
	David Blackston , Torsten Suel, Highly portable and efficient implementations of parallel adaptive N-body methods, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 15-21, 1997, San Jose, CA
	James Cheetham , Frank Dehne , Andrew Rau-Chaplin , Ulrike Stege , Peter J. Taillon, Solving large FPT problems on coarse-grained parallel machines, Journal of Computer and System Sciences, v.67 n.4, p.691-706, December 2003
	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
	Marcus Peinado , Thomas Lengauer, Parallel 'go with the winners' algorithms in distributed memory models, Journal of Parallel and Distributed Computing, v.63 n.9, p.801-814, September 2003
	Arjan J. C. van Gemund, Symbolic Performance Modeling of Parallel Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.2, p.154-165, February 2003
	Michael T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.767-776, January 05-07, 1997, New Orleans, Louisiana, United States
	Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	Isabelle Guérin Lassous , Jens Gustedt, Portable list ranking: an experimental study, Journal of Experimental Algorithmics (JEA), 7, p.7, 2002
	Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
	G. A. Alverson , D. Notkin, Program Structuring for Effective Parallel Portability, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1041-1059, September 1993
	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for memory bank contention and delay in high-bandwidth multiprocessors, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.84-94, June 24-26, 1995, Santa Barbara, California, United States
	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States
	Spyros C. Kontogiannis , Grammati E. Pantziou , Paul G. Spirakis, Efficient computations on fault-prone BSP machines, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.84-93, June 23-25, 1997, Newport, Rhode Island, United States
	F. Dehne , W. Dittrich , D. Hutchinson , A. Maheshwari, Parallel virtual memory, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.889-890, January 17-19, 1999, Baltimore, Maryland, United States
	Olaf Bonorden , Ben Juurlink , Ingo von Otte , Ingo Rieping, The Paderborn University BSP (PUB) library, Parallel Computing, v.29 n.2, p.187-207, February 2003
	Mostafa Bamha , Gaétan Hains, Frequency-adaptive join for shared nothing machines, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	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
	Kai Hwang , Cho-Li Wang , Choming Wang , Zhiwei Xu, Resource Scaling Effects on MPP Performance: The STAP Benchmark Implications, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.509-527, May 1999
	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
	Charles M. Fiduccia , Paul J. Hedrick, Edge Congestion of Shortest Path Systems for All-to-All Communication, IEEE Transactions on Parallel and Distributed Systems, v.8 n.10, p.1043-1054, October 1997
	David R. Helman , Joseph JáJá , David A. Bader, A new deterministic parallel sorting algorithm with an experimental evaluation, Journal of Experimental Algorithmics (JEA), 3, p.4-es, 1998
	Renzo Davoli , Luigi-Alberto Giachini , Özalp Babaoğlu , Alessandro Amoroso , Lorenzo Alvisi, Parallel Computing in Networks of Workstations with Paralex, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.371-384, April 1996
	Douglas Gregor , Andrew Lumsdaine, Lifting sequential graph algorithms for distributed-memory parallel computation, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Hojung Cha , Dongho Lee, H-BSP: A Hierarchical BSP Computation Model, The Journal of Supercomputing, v.18 n.2, p.179-200, Feb. 1, 2001
	Kai Kwang , Masahiro Arakawa, Benchmark Evaluation of the IBM SP2 for Parallel Signal Processing, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.522-536, May 1996
	Tianruo Yang , Hai-Xiang Linh, Parallel Performance Analysis of the Improved Quasi-Minimal Residual Method on Bulk Synchronous Parallel Architectures, The Journal of Supercomputing, v.13 n.2, p.191-210, March/April 1999
	Jehoshua Bruck , Ching-Tien Ho , Eli Upfal , Shlomo Kipnis , Derrick Weathersby, Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.8 n.11, p.1143-1156, November 1997
	Bogdan S. Chlebus , Leszek Gasieniec , Andrzej Pelc, Deterministic computations on a PRAM with static processor and memory faults, Fundamenta Informaticae, v.55 n.3-4, p.285-306, June 2003
	Fan Chung , Ronald Graham , George Varghese, Parallelism versus memory allocation in pipelined router forwarding engines, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Jinsheng Xu , Moon Jung Chung, Predicting the Performance of Synchronous Discrete Event Simulation, IEEE Transactions on Parallel and Distributed Systems, v.15 n.12, p.1130-1137, December 2004
	Laurence Boxer , Russ Miller, Coarse grained gather and scatter operations with applications, Journal of Parallel and Distributed Computing, v.64 n.11, p.1297-1310, November 2004
	David J. Kuck, Productivity in High Performance Computing, International Journal of High Performance Computing Applications, v.18 n.4, p.489-504, November 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
	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
	Christoph W. Keßler, NestStep: Nested Parallelism and Virtual Shared Memory for the BSP Model, The Journal of Supercomputing, v.17 n.3, p.245-262, Nov. 2000
	Afonso Ferreira , Stéphane Ubéda, Computing the Medial Axis Transform in Parallel With Eight Scan Operations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.3, p.277-282, March 1999
	Lixin Gao , Arnold L. Rosenberg , Ramesh K. Sitaraman, Optimal Clustering of Tree-Sweep Computations for High-Latency Parallel Environments, IEEE Transactions on Parallel and Distributed Systems, v.10 n.8, p.813-824, August 1999
	David A. Bader , David R. Helman , Joseph JáJá, Practical parallel algorithms for personalized communication and integer sorting, Journal of Experimental Algorithmics (JEA), 1, p.3-es, 1996
	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
	Chengzhong Xu , Francis C. M. Lau, Efficient Termination Detection for Loosely Synchronous Applications in Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.537-544, May 1996
	Tsan-Sheng Hsu , Joseph C. Lee , Dian Rae Lopez , William A. Royce, Task Allocation on a Network of Processors, IEEE Transactions on Computers, v.49 n.12, p.1339-1353, December 2000
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999
	Ronald I. Greenberg , Hyeong-Cheol Oh, Universal Wormhole Routing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.3, p.254-262, March 1997
	Thomas Rauber , Gudula Rünger, A Transformation Approach to Derive Efficient Parallel Implementations, IEEE Transactions on Software Engineering, v.26 n.4, p.315-339, April 2000
	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
	Ka-Po Chow , Yu-Kwong Kwok, On Load Balancing for Distributed Multiagent Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.8, p.787-801, August 2002
	Alexey Lastovetsky , Ravi Reddy, On performance analysis of heterogeneous parallel algorithms, Parallel Computing, v.30 n.11, p.1195-1216, November 2004
	Alessio Bechini , Cosimo Antonio Prete, Performance-steered design of software architectures for embedded multicore systems, Software—Practice & Experience, v.32 n.12, p.1155-1173, October 2002
	Gianfranco Bilardi , Kieran Herley , Andrea Pietracaprina , Geppino Pucci, On stalling in LogP, Journal of Parallel and Distributed Computing, v.65 n.3, p.307-312, March 2005
	V. Blanco , J. A. González , C. León , C. Rodríguez , G. Rodríguez , M. Printista, Predicting the performance of parallel programs, Parallel Computing, v.30 n.3, p.337-356, March 2004
	Jinsheng Xu , Moon Jung Chung, Predicting the performance of synchronous discrete event simulation systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	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
	Raphael Y. de Camargo , Andrei Goldchleger , Fabio Kon , Alfredo Goldman, Checkpointing-based rollback recovery for parallel applications on the InteGrade grid middleware, Proceedings of the 2nd workshop on Middleware for grid computing, p.35-40, October 18-22, 2004, Toronto, Ontario, Canada
	Thierry Garcia , David Semé, A Coarse-Grained multicomputer algorithm for the detection of repetitions, Information Processing Letters, v.93 n.6, p.307-313, 31 March 2005
	Y. C. Tay , W. Tim Loke, On deadlocks of exclusive AND-requests for resources, Distributed Computing, v.9 n.2, p.77-94, October 1995
	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
	Andrei Goldchleger , Alfredo Goldman , Ulisses Hayashida , Fabio Kon, The implementation of the BSP parallel computing model on the InteGrade Grid middleware, Proceedings of the 3rd international workshop on Middleware for grid computing, p.1-6, November 28-December 02, 2005, Grenoble, France
	Eitan Frachtenberg , Dror G. Feitelson , Fabrizio Petrini , Juan Fernandez, Adaptive Parallel Job Scheduling with Flexible Coscheduling, IEEE Transactions on Parallel and Distributed Systems, v.16 n.11, p.1066-1077, November 2005
	F. Gava , F. Loulergue, A static analysis for bulk synchronous parallel ML to avoid parallel nesting, Future Generation Computer Systems, v.21 n.5, p.665-671, May 2005
	Ravi Iyer , Jack Perdue , Lawrence Rauchwerger , Nancy M. Amato , Laxmi Bhuyan, An experimental evaluation of the HP V-class and SGI origin 2000 multiprocessors using microbenchmarks and scientific applications, International Journal of Parallel Programming, v.33 n.4, p.307-350, August 2005
	Alessio Bechini , Pierfrancesco Foglia , Cosimo Antonio Prete, Use of a CORBA/RMI gateway: characterization of communication overhead, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy
	Andreas Savva , Takashi Nanya, A Gracefully Degrading Massively Parallel System Using the BSP Model, and Its Evaluation, IEEE Transactions on Computers, v.48 n.1, p.38-52, January 1999
	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
	David B. Skillicorn, Architecture-Independent Parallel Computation, Computer, v.23 n.12, p.38-50, December 1990
	Gail A. Alverson , William G. Griswold , Calvin Lin , David Notkin , Lawrence Snyder, Abstractions for Portable, Scalable Parallel Programming, IEEE Transactions on Parallel and Distributed Systems, v.9 n.1, p.71-86, January 1998
	Paulius Micikevicius , Narsingh Deo, Cluster Computing for Determining Three-Dimensional Protein Structure, The Journal of Supercomputing, v.34 n.3, p.243-271, December 2005
	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP and LogP: a framework for general-purpose parallel algorithm design, Journal of Parallel and Distributed Computing, v.63 n.12, p.1175-1192, December 2003
	Chun-Hsi Huang , Xin He , Min Qian, Communication-optimal parallel parenthesis matching, Parallel Computing, v.32 n.1, p.14-23, January 2006
	Alfredo Goldman , Joseph G. Peters , Denis Trystram, Exchanging messages of different sizes, Journal of Parallel and Distributed Computing, v.66 n.1, p.1-18, January 2006
	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
	Carlo Fantozzi , Andrea Pietracaprina , Geppino Pucci, Translating submachine locality into locality of reference, Journal of Parallel and Distributed Computing, v.66 n.5, p.633-646, May 2006
	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
	Edson Toshimi Midorikawa , Helio Marci de Oliveira , Jean Marcos Laine, PEMPIs: a new methodology of modeling and prediction of MPI programs performance, International Journal of Parallel Programming, v.33 n.5, p.499-527, October 2005
	Christos Kaklamanis , Danny Krizanc , Manuela Montangero , Giuseppe Persiano, Efficient automatic simulation of parallel computation on networks of workstations, Discrete Applied Mathematics, v.154 n.10, p.1500-1509, 15 June 2006
	Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
	Ahmed Sameh , Tarek El-Ghazawi , Yesha Yacoov, Modeling contention of sparse-matrix-vector multiplication (SMV) in three parallel programming paradigms, Proceedings of the 6th international workshop on Software and performance, February 05-08, 2007, Buenes Aires, Argentina
	Martti J. Forsell, Are multiport memories physically feasible?, ACM SIGARCH Computer Architecture News, v.22 n.5, p.3-10, Dec. 1994
	Lakshminarayanan Renganarayana , Sanjay Rajopadhye, A Geometric Programming Framework for Optimal Multi-Level Tiling, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.18, November 06-12, 2004
	Martti J. Forsell, Are multiport memories physically feasible?, ACM SIGARCH Computer Architecture News, v.22 n.4, p.47-54, Sept. 1994
	Christof Krick , Friedhelm Meyer auf der Heide , Harald Räcke , Berthold Vöcking , Matthias Westermann, Data management in networks: experimental evaluation of a provably good strategy, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.165-174, June 27-30, 1999, Saint Malo, France
	Lei Ni , Aaron Harwood , Peter J. Stuckey, Realizing the e-science desktop peer using a peer-to-peer distributed virtual machine middleware, Proceedings of the 4th international workshop on Middleware for grid computing, November 27-December 01, 2006, Melbourne, Australia
	Juha Kärkkäinen , Peter Sanders , Stefan Burkhardt, Linear work suffix array construction, Journal of the ACM (JACM), v.53 n.6, p.918-936, November 2006
	Frédéric Loulergue, Editorial: Introduction to the special issue on semantics and costs models for high-level parallel programming, Computer Languages, Systems and Structures, v.33 n.3-4, p.79-81, October, 2007
	Song Fu , Cheng-Zhong Xu, Stochastic modeling and analysis of hybrid mobility in reconfigurable distributed virtual machines, Journal of Parallel and Distributed Computing, v.66 n.11, p.1442-1454, November 2006
	Rob H. Bisseling , Ildikó Flesch, Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Lanczos algorithm: a case study, Parallel Computing, v.32 n.7, p.551-567, September 2006
	Alexander Tiskin, Communication-efficient parallel generic pairwise elimination, Future Generation Computer Systems, v.23 n.2, p.179-188, February 2007
	Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
	Armelle Merlin , Gaétan Hains, A bulk-synchronous parallel process algebra, Computer Languages, Systems and Structures, v.33 n.3-4, p.111-133, October, 2007
	Ahmed Sameh , Tarek El-Ghazawi , Yesha Yacoov, Modeling contention of giga-updates per second (GUPs) in three parallel programming paradigms, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.115-120, February 13-15, 2007, Innsbruck, Austria
	Jirada Kuntraruk , William M. Pottenger , Andrew M. Ross, Application Resource Requirement Estimation in a Parallel-Pipeline Model of Execution, IEEE Transactions on Parallel and Distributed Systems, v.16 n.12, p.1154-1165, December 2005
	Bradley J. Barnes , Barry Rountree , David K. Lowenthal , Jaxk Reeves , Bronis de Supinski , Martin Schulz, A regression-based approach to scalability prediction, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Sotirios G. Ziavras , Alexandros V. Gerbessiotis , Rohan Bafna, Coprocessor design to support MPI primitives in configurable multiprocessors, Integration, the VLSI Journal, v.40 n.3, p.235-252, April, 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
	Tony Hey , Juri Papay, Performance engineering, PSEs and the GRID, Scientific Programming, v.10 n.1, p.3-17, January 2002
	Mario Nakazawa , David K. Lowenthal , Wendou Zhou, The MHETA Execution Model for Heterogeneous Clusters, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.7, November 12-18, 2005
	J. A. González , C. Rodríguez , G. Rodríguez , F. de Sande , M. Printista, A tool for performance modeling of parallel programs, Scientific Programming, v.11 n.3, p.191-198, August 2003
	Alexandros V. Gerbessiotis , Seung-Yeop Lee, Remote memory access: A case for portable, efficient and library independent parallel programming, Scientific Programming, v.12 n.3, p.169-183, August 2004
	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
	Juan Fernandez , Eitan Frachtenberg , Fabrizio Petrini, BCS-MPI: A New Approach in the System Software Design for Large-Scale Parallel Computers, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.57, November 15-21, 2003
	Anthony T. C. Tam , Cho-Li Wang, Contention-Aware Communication Schedule for High-Speed Communication, Cluster Computing, v.6 n.4, p.339-353, October 2003
	Stéphane Vialle , Thierry Cornu , Yannick Lallement, ParCeL-1: a parallel programming language based on autonomous and synchronous actors, ACM SIGPLAN Notices, v.31 n.8, p.43-51, August 1996
	David A. Bader , Virat Agarwal , Kamesh Madduri , Seunghwa Kang, High performance combinatorial algorithm design on the Cell Broadband Engine processor, Parallel Computing, v.33 n.10-11, p.720-740, November, 2007
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	Edward A. Luke , Thomas George, Loci: a rule-based framework for parallel multi-disciplinary simulation synthesis, Journal of Functional Programming, v.15 n.3, p.477-502, May 2005
	P. W. Trinder , H.-W. Loidl , R. F. Pointon, Parallel and Distributed Haskells, Journal of Functional Programming, v.12 n.5, p.469-510, July 2002
	Fatima K. Abu Salem , Laurence T. Yang, Parallel methods for absolute irreducibility testing, The Journal of Supercomputing, v.46 n.3, p.181-212, December 2008
	Zheng Wang , Michael F.P. O'Boyle, Mapping parallelism to multi-cores: a machine learning based approach, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Veronica Gil-Costa , Mauricio Marin , Nora Reyes, Parallel query processing on distributed clustering indexes, Journal of Discrete Algorithms, v.7 n.1, p.3-17, March, 2009
	Lars Arge , Michael T. Goodrich , Michael Nelson , Nodari Sitchinava, Fundamental parallel algorithms for private-cache chip multiprocessors, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-efficient dynamic programming algorithms for multicores, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Milind Kulkarni , Keshav Pingali , Ganesh Ramanarayanan , Bruce Walter , Kavita Bala , L. Paul Chew, Optimistic parallelism benefits from data partitioning, ACM SIGARCH Computer Architecture News, v.36 n.1, March 2008
	Mauricio Marin , Veronica Gil-Costa, High-performance distributed inverted files, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Jens Gustedt, Efficient sampling of random permutations, Journal of Discrete Algorithms, v.6 n.1, p.125-139, March, 2008
	N. Botta , C. Ionescu, Relation-based computations in a monadic BSP model, Parallel Computing, v.33 n.12, p.795-821, December, 2007
	Doruk Bozdağ , Assefaw H. Gebremedhin , Fredrik Manne , Erik G. Boman , Umit V. Catalyurek, A framework for scalable greedy coloring on distributed-memory parallel computers, Journal of Parallel and Distributed Computing, v.68 n.4, p.515-535, April, 2008
	Mauricio Marin , Carlos Gomez, Load balancing distributed inverted files, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal
	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
	Albert Chan , Frank Dehne , Prosenjit Bose , Markus Latzel, Coarse grained parallel algorithms for graph matching, Parallel Computing, v.34 n.1, p.47-62, January, 2008
	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
	Bin Lin , Ananth I. Sundararaj , Peter A. Dinda, Time-sharing parallel applications through performance-targeted feedback-controlled real-time scheduling, Cluster Computing, v.11 n.3, p.273-285, September 2008
	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
	Luiz Angelo Steffenel , Grégory Mounié, A framework for adaptive collective communications for heterogeneous hierarchical computing systems, Journal of Computer and System Sciences, v.74 n.6, p.1082-1093, September, 2008
	Konrad Hinsen, Parallel Scripting with Python, Computing in Science and Engineering, v.9 n.6, p.82-89, November 2007
	Xiaoyu Zhang , Chandrajit Bajaj, Scalable isosurface visualization of massive datasets on commodity off-the-shelf clusters, Journal of Parallel and Distributed Computing, v.69 n.1, p.39-53, January, 2009
	Mauricio Marin , Rodrigo Paredes , Carolina Bonacic, High-performance priority queues for parallel crawlers, Proceeding of the 10th ACM workshop on Web information and data management, October 30-30, 2008, Napa Valley, California, USA
	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
	Georgios Tournavitis , Zheng Wang , Björn Franke , Michael F.P. O'Boyle, Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Michael J. Quinn , Russ Miller , Russ Miller , Michael J. Quinn, Parallel processing, Encyclopedia of Computer Science, 4th edition, John Wiley and Sons Ltd., Chichester, 2003
	Avi Wigderson, The work of Leslie Valiant, Proceedings of the 41st annual ACM symposium on Theory of computing, p.1-2, May 31-June 02, 2009, Bethesda, MD, USA
	Kunsoo Park , Heejin Park , Woo-Chul Jeun , Soonhoi Ha, Boolean circuit programming: A new paradigm to design parallel algorithms, Journal of Discrete Algorithms, v.7 n.2, p.267-277, June, 2009
	Brian J. D'Auriol, The systems edge of the Parameterized Linear Array with a Reconfigurable Pipelined Bus System (LARPBS(p)) optical bus parallel computing model, The Journal of Supercomputing, v.48 n.2, p.183-209, May 2009
	Dimitris C. Dracopoulos , Simon Kent, Speeding up genetic programming: a parallel BSP implementation, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
	Charalampos Konstantopoulos , Basilis Mamalis , Grammati Pantziou , Damianos Gavalas, Efficient parallel Text Retrieval techniques on Bulk Synchronous Parallel (BSP)/Coarse Grained Multicomputers (CGM), The Journal of Supercomputing, v.48 n.3, p.286-318, June 2009
	Ami Marowka, Bsp2omp: A Compiler For Translating Bsp Programs To Openmp, International Journal of Parallel, Emergent and Distributed Systems, v.24 n.4, p.293-310, August 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
	John H. Kelm , Daniel R. Johnson , Matthew R. Johnson , Neal C. Crago , William Tuohy , Aqeel Mahesri , Steven S. Lumetta , Matthew I. Frank , Sanjay J. Patel, Rigel: an architecture and scalable programming interface for a 1000-core accelerator, ACM SIGARCH Computer Architecture News, v.37 n.3, June 2009

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:
C. Computer Systems Organization
C.0 GENERAL
Subjects: Hardware/software interfaces
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**

F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Languages, Performance, Theory

REVIEW

"Ronald J. Watro : Reviewer"

Valiant observes that parallel processing has not made the expected progress in displacing sequential processing in computationally intensive domains. He attributes this failure to the lack of an appropriate bridging model for parallel computa more...

Collaborative Colleagues:

Leslie G. Valiant: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player