The Parallel Evaluation of General Arithmetic Expressions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Parallel Evaluation of General Arithmetic Expressions

Full text

Pdf (393 KB)

Source

Journal of the ACM (JACM) archive
Volume 21 , Issue 2 (April 1974) table of contents

Pages: 201 - 206

Year of Publication: 1974

ISSN:0004-5411

Author

Richard P. Brent

Computer Centre, Australian Nalional University, P.O. Box 4, Canberra, A.C.T. 2600, Australia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 70, Citation Count: 112

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log2n + 10(n - 1)/p using p ≥ 1 processors which can independently perform arithmetic operations in unit time. This bound is within a constant factor of the best possible. A sharper result is given for expressions without the division operation, and the question of numerical stability is discussed.

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	BAER, J. L., AND BOVET, D. P. Compilation of arithmetic expressions for parallel computations. Proc. IFIP Congr. 1968, North-Holland Pub. Co., Amsterdam, pp. 340-346.
	2	James C. Beatty, An axiomatic approach to code optimization for expressions, Journal of the ACM (JACM), v.19 n.4, p.613-640, Oct. 1972 [doi>10.1145/321724.321728]
	3	BRENT, R. P. On the addition of binary numbers. IEEE Trans. Comp. C-I9 (Aug. 1970), 758-759.
	4	BRENT, R. P. The parallel evaluation of arithmetic expressions in logarithmic time. Proc. Symposium on Complexity of Sequential and Parallel Numerical Algorithms (Carnegie-Mellon U., Pittsburgh, Pa., May 1973), Academic Press, New York, 1973, pp. 83-102.
	5	BRENT, R. P., KUCK, D. J., AND MARUYAMA, g. M. The parallel evaluation of arithmetic expressions without division. IEEE Trans. Comput. C-22 (May 1973), 532-534.
	6	HOBBS, L. C. (Ed.) Parallel processor systems, technologies and applications. Spartan Books, New York, 1970.
	7	KNUTH, D.E. An empirical study of FORTRAN programs. Software i (April 1971), 105-133.
	8	KoGo~, P.M. Parallel algorithms for the efficient solution of recurrence problems; the numerical stability of parallel algorithms for solving recurrence problems; and minimal parallelism in the solution of recurrence problems. Stanford Electronics Lab. Reps. 43-45, Sept. 1972.
	9	KOGGE, P. M., AND STON~, H. S. A parallel algorithm for the efficient solution of a general class of recurrence equations. Rep. CS-72-298, Comput. Sci. Dep., Stanford U., Stanford, Calif., March 1972.
	10	KVcK, D.J. Evaluating arithmetic expressions of natomsand k divisions in a(log2n ~- 2 log2k) ~- c steps. Manuscript, March 1973.
	11	KUCK, D.J. Parallelism in ordinary programs. Proc. Symposium on Complexity of Sequential and Parallel Numerical Algorithms (Carnegie-Mellon U., Pittsburgh, Pa., May 1973), Academic Press, New York, 1973, pp. 17-47.
	12	KucK, D. J., AND MARUYAMA, K. M. The parallel evaluation of. arithmetic expressions of special forms. Rep. RC 4276, IBM Res. Center, Yorktown Heights, N.Y., March 1973.
	13	KUCK, D. J., MURAOKA, Y., AND CHEN, S. On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speedup. IEEE Trans. Comput. C-21 (Dec. 1972), 1293-1310.
	14	MARUYAMA, K.M. On the parallel evaluation of polynomials. IEEE Trans. Comput C-~2 (jan. 1973), 2-5.
	15	MARUYAMA, K.M. Upper bounds on the time required to evaluate arithmetic expressions. Rep. RC 4260, IBM Res. Center, Yorktown Heights, N. Y., March 1973.
	16	MARUYAMA, K.M. The parallel evaluation of matrix expressions. Rep. RC 4380, iBM Res. Center, Yorktown Heights, N. Y., June 1973.
	17	MILLER, W. C. Numerical heuristics in computer-aided roundoff analysis. Rep. RC 4332, IBM Res. Center, Yorktown Heights, N. Y., May 1973.
	18	'MIRASKER, W. L. A survey of parallelism in numerical analysis. SIAM Rev. 13 (Oct. 1971), 524-547.
	19	MUNRO, I., AND PATERSON, M. Optimal algorithms for parallel polynomial evaluation. Proc. IEEE 12th Annual Symposium on Switching and Automata Theory (Oct. 1971), pp. 132-139.
	20	MURAOKA, Y. Parallelism exposure and exploitation in programs. Rep. 424, Dep. of Comput. Sci., U. of Illinois at Urbana-Champaign, Feb. 1971.

CITED BY 112

	R. Grossman , R. G. Larson, Labeled trees and the efficient computation of derivations, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.74-80, July 17-19, 1989, Portland, Oregon, United States
	E. F. Grove, Connected components and the interval graph, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.382-391, June 29-July 01, 1992, San Diego, California, United States
	Weixiong Zhang , Zhaofang Wen, Efficient parallel algorithms for some integer problems, Proceedings of the 19th annual conference on Computer Science, p.11-20, April 1991, San Antonio, Texas, United States
	Zia Iqbal , Miodrag Potkonjak , Sujit Dey , Alice Parker, Critical path minimization using retiming and algebraic speed-up, Proceedings of the 30th international conference on Design automation, p.573-577, June 14-18, 1993, Dallas, Texas, United States
	Zvi Galil, A constant-time optimal parallel string-matching algorithm, Journal of the ACM (JACM), v.42 n.4, p.908-918, July 1995
	Charles E. Leiserson , Keith H. Randall, Parallel algorithms for the circuit value update problem, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.13-20, June 24-26, 1995, Santa Barbara, California, United States
	Eliezer Dekel , Sartaj Sahni, Parallel Generation of Postfix and Tree Forms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.300-317, July 1983
	Hirotoshi Honma , Shigeru Masuyama, An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.383-391, January 2008
	W. Morven Gentleman, Some Complexity Results for Matrix Computations on Parallel Processors, Journal of the ACM (JACM), v.25 n.1, p.112-115, Jan. 1978
	Zvi Galil, A constant-time optimal parallel string-matching algorithm, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.69-76, May 04-06, 1992, Victoria, British Columbia, Canada
	Thomas H. Spencer, Time-work tradeoffs for parallel graph algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.425-432, January 28-30, 1991, San Francisco, California, United States
	Welf Löwe , Wolf Zimmermann, Upper time bounds for executing PRAM-programs on the LogP-machine, Proceedings of the 9th international conference on Supercomputing, p.41-50, July 03-07, 1995, Barcelona, Spain
	Yuri Gurevich , Larry Stockmeyer , Uzi Vishkin, Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems, Journal of the ACM (JACM), v.31 n.3, p.459-473, July 1984
	Ilan Bar-on , Uzi Vishkin, Optimal parallel generation of a computation tree form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.348-357, April 1985
	Thomas H. Spencer, More time-work tradeoffs for parallel graph algorithms, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.81-93, July 21-24, 1991, Hilton Head, South Carolina, United States
	L. Hyafil , H. T. Kung, The complexity of parallel evaluation of linear recurrence, Proceedings of seventh annual ACM symposium on Theory of computing, p.12-22, May 05-07, 1975, Albuquerque, New Mexico, United States
	G M Landau , U Vishkin, Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.220-230, May 28-30, 1986, Berkeley, California, United States
	S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States
	Jacques Cohen , Timothy Hickey , Joel Katcoff, Upper Bounds for Speedup in Parallel Parsing, Journal of the ACM (JACM), v.29 n.2, p.408-428, April 1982
	J. JáJá , K. W. Ryu, Optimal Algorithms on the Pipelined Hypercube and Related Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.582-591, May 1993
	Raja P. K. Banerjee , Vineet Goel , Amar Mukherjee, Efficient parallel evaluation of CSG tree using fixed number of processors, Proceedings on the second ACM symposium on Solid modeling and applications, p.137-146, May 19-21, 1993, Montreal, Quebec, Canada
	Basile Kamdoum, Speeding up the primal simplex algorithm on parallel computer, ACM SIGMAP Bulletin
	Ronald Scrofano , Ling Zhuo , Viktor K. Prasanna, Area-efficient arithmetic expression evaluation using deeply pipelined floating-point cores, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.2, p.167-176, February 2008
	Stefan D. Bruda , Selim G. Akl, On limits on the computational power of data-accumulating algorithms, Information Processing Letters, v.86 n.4, p.221-227, 31 May 2003
	L. Hyafil , H. T. Kung, The Complexity of Parallel Evaluation of Linear Recurrences, Journal of the ACM (JACM), v.24 n.3, p.513-521, July 1977
	Dieter Rautenbach , Christian Szegedy , Jürgen Werber, The delay of circuits whose inputs have specified arrival times, Discrete Applied Mathematics, v.155 n.10, p.1233-1243, May, 2007
	G. E. Shannon, Optimal on-line load balancing, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.235-245, June 18-21, 1989, Santa Fe, New Mexico, United States
	Michael T. Goodrich, Applying parallel processing techniques to classification problems in constructive solid geometry, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.118-128, January 22-24, 1990, San Francisco, California, United States
	Marcel van Lohuizen, A generic approach to parallel chart parsing with an application to LinGO, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.507-514, July 06-11, 2001, Toulouse, France
	Webb Miller, Software for Roundoff Analysis, ACM Transactions on Mathematical Software (TOMS), v.1 n.2, p.108-128, June 1975
	David J. Kolson , Alexandru Nicolau , Nikil Dutt, Integrating program transformations in the memory-based synthesis of image and video algorithms, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.27-30, November 06-10, 1994, San Jose, California, United States
	Weifa Liang , Richard P. Brent , Hong Shen, Fully Dynamic Maintenance of k-Connectivity in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.12 n.8, p.846-864, August 2001
	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States
	J. Ullman , M. Yannakakis, High-probability parallel transitive closure algorithms, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.200-209, July 02-06, 1990, Island of Crete, Greece
	David Nassimi , Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network, Journal of the ACM (JACM), v.29 n.3, p.642-667, July 1982
	Kemal Ebcioğlu , Erik R. Altman , Michael Gschwind , Sumedh Sathaye, Optimizations and oracle parallelism with dynamic translation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.284-295, November 16-18, 1999, Haifa, Israel
	Mark Goldberg , Thomas H. Spencer, An efficient parallel algorithm that finds independent sets of guaranteed size, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 22-24, 1990, San Francisco, California, United States
	Andrei Z. Broder , Anna Karlin , Prabhakar Raghavan , Eli Upfal, On the parallel complexity of evaluating game trees, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.404-413, January 28-30, 1991, San Francisco, California, United States
	John Greiner , Guy E. Blelloch, A provably time-efficient parallel implementation of full speculation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.309-321, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Torben Hagerup , H. Jung , E. Welzl, Efficient parallel computation of arrangements of hyperplanes in d dimensions, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.290-297, July 02-06, 1990, Island of Crete, Greece
	D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979
	Michael T. Goodrich, Planar separators and parallel polygon triangulation (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.507-516, May 04-06, 1992, Victoria, British Columbia, Canada
	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada
	Thomas H. Spencer, Time-work tradeoffs for parallel algorithms, Journal of the ACM (JACM), v.44 n.5, p.742-778, Sept. 1997
	M. Atallah , D. Chen, Parallel rectilinear shortest paths with rectangular obstacles, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.270-279, July 02-06, 1990, Island of Crete, Greece
	D. S. Hirschberg, Fast parallel sorting algorithms, Communications of the ACM, v.21 n.8, p.657-661, Aug. 1978
	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
	M. Lu , H. Lin, Parallel Algorithms for the Longest Common Subsequence Problem, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.835-848, August 1994
	Limin Xiang , Kazuo Ushijima, On Time Bounds, the Work-Time Scheduling Principle, and Optimality for BSR, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.912-921, September 2001
	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
	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
	Gianfranco Bilardi , Franco P. Preparata, Upper bounds to processor-time tradeoffs under bounded-speed message propagation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.185-194, June 24-26, 1995, Santa Barbara, California, United States
	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, ACM SIGPLAN Notices, v.30 n.8, p.207-216, Aug. 1995
	David Skillicorn , Susanna Pelagatti, Building programs in the network of tasks model, Proceedings of the 2000 ACM symposium on Applied computing, p.248-254, March 2000, Como, Italy
	Daniel Richardson , Ahmed El-Sonbaty, Use of algebraically independent numbers for zero recognition of polynomial terms, Journal of Complexity, v.19 n.5, p.631-637, October 2003
	N. Gupta , S. Chopra, Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel, Journal of Parallel and Distributed Computing, v.67 n.7, p.772-782, July, 2007
	Richard Cleve, Computing algebraic formulas with a constant number of registers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.254-257, May 02-04, 1988, Chicago, Illinois, United States
	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
	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
	Sanguthevar Rajasekaran , Insup Lee, Parallel Algorithms for Relational Coarsest Partition Problems, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.687-699, July 1998
	Danny Z. Chen, Efficient Parallel Binary Search on Sorted Arrays, with Applications, IEEE Transactions on Parallel and Distributed Systems, v.6 n.4, p.440-445, April 1995
	Georg Gottlob, NP trees and Carnap's modal logic, Journal of the ACM (JACM), v.42 n.2, p.421-457, March 1995
	Charles N. Fischer, On Parsing and Compiling Arithmetic Expressions on Vector Computers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.203-224, April 1980
	Marek Chrobak , David Eppstein , Giuseppe F. Italiano , Moti Yung, Efficient sequential and parallel algorithms for computing recovery points in trees and paths, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.158-167, January 28-30, 1991, San Francisco, California, United States
	Robert F. Cohen , Roberto Tamassia, Dynamic expression trees and their applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.52-61, January 28-30, 1991, San Francisco, California, United States
	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
	Anshul Gupta , Fred G. Gustavson , Mahesh Joshi , Sivan Toledo, The design, implementation, and evaluation of a symmetric banded linear solver for distributed-memory parallel computers, ACM Transactions on Mathematical Software (TOMS), v.24 n.1, p.74-101, March 1998
	Victor Y. Pan , Franco P. Preparata, Supereffective slow-down of parallel computations, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.402-409, June 29-July 01, 1992, San Diego, California, United States
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima, Journal of Parallel and Distributed Computing, v.63 n.4, p.488-500, April 2003
	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States
	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
	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
	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
	M. T. Goodrich, Intersecting line segments in parallel with an output-sensitive number of processors, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 18-21, 1989, Santa Fe, New Mexico, United States
	Nageswara S. V. Rao, On Parallel Algorithms for Single-Fault Diagnosis in Fault Propagation Graph Systems, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1217-1223, December 1996
	Eric Anderson , Dirk Beyer , Kamalika Chaudhuri , Terence Kelly , Norman Salazar , Cipriano Santos , Ram Swaminathan , Robert Tarjan , Janet Wiener , Yunhong Zhou, Value-maximizing deadline scheduling and its application to animation rendering, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Tatsuya Hayashi , Koji Nakano , Stephan Olariu, Work-Time Optimal k-Merge Algorithms on the PRAM, IEEE Transactions on Parallel and Distributed Systems, v.9 n.3, p.275-282, March 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
	Thomas Reps, Scan grammars: parallel attribute evaluation via data-parallelism, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.367-376, June 30-July 02, 1993, Velen, Germany
	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
	Prithviraj Banerjee , Jacob A. Abraham, Fault-secure algorithms for multiple-processor systems, ACM SIGARCH Computer Architecture News, v.12 n.3, p.279-287, June 1984
	M. Goodrich , M. Ghouse , J. Bright, Generalized sweep methods for parallel computational geometry, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.280-289, July 02-06, 1990, Island of Crete, Greece
	Guy E. Blelloch, Programming parallel algorithms, Communications of the ACM, v.39 n.3, p.85-97, March 1996
	S. Winograd, On the Parallel Evaluation of Certain Arithmetic Expressions, Journal of the ACM (JACM), v.22 n.4, p.477-492, Oct. 1975
	V. Y. Pan, Concurrent Iterative Algorithm for Toeplitz-like Linear Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.592-600, May 1993
	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
	Dario Bini , Victor Pan, Parallel complexity of tridiagonal symmetric Eigenvalue problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 28-30, 1991, San Francisco, California, United States
	Girija J. Narlikar, Scheduling threads for low space requirement and good locality, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.83-95, June 27-30, 1999, Saint Malo, France
	David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977
	Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States
	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
	Michael T. Goodrich, Constructing arrangements optimally in parallel (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.169-179, July 21-24, 1991, Hilton Head, South Carolina, United States
	Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States
	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States
	Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999
	A. Aggarwal , D. Kravets , J. Park , S. Sen, Parallel searching in generalized Monge arrays with applications, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.259-268, July 02-06, 1990, Island of Crete, Greece
	Michael A. Bender , Cynthia A. Phillips, Scheduling DAGs on asynchronous processors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, 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
	S. Muthukrishnan , K. Palem, Highly efficient dictionary matching in parallel, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.69-78, June 30-July 02, 1993, Velen, Germany
	Hirotoshi Honma , Shigeru Masuyama, An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.9, p.2296-2300, September 2008
	Kunal Agrawal , Yuxiong He , Wen Jing Hsu , Charles E. Leiserson, Adaptive scheduling with parallelism feedback, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	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
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	Guy E. Blelloch , Rezaul A. Chowdhury , Phillip B. Gibbons , Vijaya Ramachandran , Shimin Chen , Michael Kozuch, Provably good multicore cache performance for divide-and-conquer algorithms, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.501-510, January 20-22, 2008, San Francisco, California
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999
	Kunal Agrawal , Yuxiong He , Charles E. Leiserson, Adaptive work stealing with parallelism feedback, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Michael G. Norman , Peter Thanisch, Models of machines and computation for mapping in multicomputers, ACM Computing Surveys (CSUR), v.25 n.3, p.263-302, Sept. 1993
	Kunal Agrawal , Charles E. Leiserson , Yuxiong He , Wen Jing Hsu, Adaptive work-stealing with parallelism feedback, ACM Transactions on Computer Systems (TOCS), v.26 n.3, p.1-32, September 2008
	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
	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
	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980