Parallel Prefix Computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel Prefix Computation

Full text

Pdf (389 KB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 4 (October 1980) table of contents

Pages: 831 - 838

Year of Publication: 1980

ISSN:0004-5411

Authors

Richard E. Ladner	Department of Computer Science, FR-35, University of Washington, Seattle, Washington
Michael J. Fischer	Department of Computer Science, FR-35, University of Washington, Seattle, Washington

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 35, Downloads (12 Months): 287, Citation Count: 154

Additional Information:

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

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	BOOTH, T.L. Sequential Machines and Automata Theory. Wdey, New York, 1967.
	2	BRENT, R. On the addiuon ofbmary numbers. IEEE Trans. Comput. C-19, 8 (1970), 758-759
	3	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	4	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	5	KRAPCHENKO, V.M. Asymptotic estimation of addition time of a parallel adder Syst. Theory Res. 19 (1970), 105-122 {Probl Kibern. 19, 107-122 (Russ.)}.
	6	OFMAN, Yu. On the algorithmic complexity of discrete functions. Soy Phys Dokl 7 (1963), 589-591
	7	PATERSON, M S An introduction to Boolean function complexity. Soodtd Math de France Astdnsque 38-39 1976, 183-201 Also Tech. Rep STAN-CS-76-557, Computer Science Department, Stanford Umv, Stanford, Cahf, August 1976
	8	John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
	9	SCHONHAGE, A A lower bound for the length of addition chains. Theor Comput. Sct 1 (1975), 1-12
	10	TUNG, C Anthmettc In Computer Sctence, A F Cardenas, L. Presser, and M A Marm, Eds, Wdeylnterscience, New York, 1972

CITED BY 154

	O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States
	O. Egecioglu , C. K. Koc , A. J. Laub, Prefix algorithms for tridiagonal systems on hypercube multiprocessors, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1539-1545, January 1989, Pasadena, California, United States
	M.-Y. Kao , P. N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.181-192, May 13-17, 1990, Baltimore, Maryland, United States
	Gurindar S. Sohi , James E. Smith , James R. Goodman, Restricted Fetch and Φ operations for parallel processing, Proceedings of the 3rd international conference on Supercomputing, p.410-416, June 05-09, 1989, Crete, Greece
	Gloria Kissin, Upper and lower bounds on switching energy in VLSI, Journal of the ACM (JACM), v.38 n.1, p.222-254, Jan. 1991
	Jain J. Wang , Marc Abrams, Approximate time-parallel simulation of queueing systems with losses, Proceedings of the 24th conference on Winter simulation, p.700-708, December 13-16, 1992, Arlington, Virginia, United States
	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
	Siddhartha Chatterjee, Compiling nested data-parallel programs for shared-memory multiprocessors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.400-462, July 1993
	Michael T. Goodrich , Steven B. Shauck , Sumanta Guha, Parallel methods for visibility and shortest path problems in simple polygons (preliminary version), Proceedings of the sixth annual symposium on Computational geometry, p.73-82, June 07-09, 1990, Berkley, California, United States
	Arnold L. Rosenberg, Thoughts on parallelism and concurrency in compiling curricula, ACM Computing Surveys (CSUR), v.27 n.2, p.280-283, June 1995
	Harry F. Jordan, Performance measurements on HEP - a pipelined MIMD computer, ACM SIGARCH Computer Architecture News, v.11 n.3, p.207-212, June 1983
	B. Becker , J. Hartmann, Optimal-time multipliers and C-testability, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.146-154, July 02-06, 1990, Island of Crete, Greece
	Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations for network and reliability problems, Proceedings of the 22nd conference on Winter simulation, p.731-733, December 09-12, 1990, New Orleans, Louisiana, United States
	Avinoam Bilgory , Daniel D. Gajski, Automatic generation of cells for recurrence structures, Proceedings of the 18th conference on Design automation, p.306-313, June 29-July 01, 1981, Nashville, Tennessee, United States
	M. J. Atallah , D. Z. Chen, Optimal parallel algorithm for visibility of a simple polygon from a point, Proceedings of the fifth annual symposium on Computational geometry, p.114-123, June 05-07, 1989, Saarbruchen, West Germany
	Ashok K. Chandra , Steven Fortune , Richard Lipton, Unbounded fan-in circuits and associative functions, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.52-60, December 1983
	Alexandru Nicolau , Haigeng Wang, Optimal schedules for parallel prefix computation with bounded resources, ACM SIGPLAN Notices, v.26 n.7, p.1-10, July 1991
	Utpal Banerjee , Daniel D. Gajski, Fast execution of loops with if statements, ACM SIGARCH Computer Architecture News, v.12 n.3, p.126-132, June 1984
	Haigeng Wang , Alexandru Nicolau, Speedup of band linear recurrences in the presence of resource constraints, Proceedings of the 6th international conference on Supercomputing, p.466-477, July 19-24, 1992, Washington, D. C., United States
	Danny Z. Chen, An optimal parallel algorithm for detecting weak visibility of a simple polygon, Proceedings of the eighth annual symposium on Computational geometry, p.63-72, June 10-12, 1992, Berlin, Germany
	J. P. Fishburn, LATTIS: an iterative speedup heuristic for mapped logic, Proceedings of the 29th ACM/IEEE conference on Design automation, p.488-491, June 08-12, 1992, Anaheim, California, United States
	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
	Ross Paterson, A new notation for arrows, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Martin Fürer , Xin He , Ming-Yang Kao , Balaji Raghavachari, O(nlog log n)-work parallel algorithms for straight-line grid embeddings of planar graphs, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.410-419, June 29-July 01, 1992, San Diego, California, United States
	Zvi Galil , Wolfgang J. Paul, An Efficient General-Purpose Parallel Computer, Journal of the ACM (JACM), v.30 n.2, p.360-387, April 1983
	Richard E. Ladner , Jordan Lampe , Richard Rogers, Vector prefix addition on sub-bus mesh computers, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.387-396, June 30-July 02, 1993, Velen, Germany
	Amir M. Ben-Amram , Omer Berkman , Costas S. Iliopoulos , Kunsoo Park, The subtree max gap problem with application to parallel string covering, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.501-510, January 23-25, 1994, Arlington, Virginia, United States
	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States
	Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States
	Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States
	Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Superfast parallel discrete event simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.2, p.107-136, April 1996
	Clyde P Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.218-228, August 11-13, 1986, Calgary, Alberta, Canada
	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	John H. Reif , Stephen R. Tate, Dynamic algebraic algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.290-301, January 23-25, 1994, Arlington, Virginia, United States
	Jayadev Misra, Powerlist: a structure for parallel recursion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1737-1767, Nov. 1994
	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
	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
	U. Vishkin, Deterministic sampling—a new technique for fast pattern matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.170-180, May 13-17, 1990, Baltimore, Maryland, United States
	G. Bilardi , F. P. Preparata, Size-time complexity of Boolean networks for prefix computations, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.436-442, January 1987, New York, New York, United States
	Shlomit S. Pinter , Ron Y. Pinter, Program optimization and parallelization using idioms, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.79-92, January 21-23, 1991, Orlando, Florida, United States
	R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Faith E. Fich, New bounds for parallel prefix circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.100-109, December 1983
	C. Rhee , S. K. Dhall , S. Lakshmivarahan, An optimal parallel algorithm for the maximal element problem (abstract), Proceedings of the 1990 ACM annual conference on Cooperation, p.435, February 20-22, 1990, Washington, D.C., United States
	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
	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
	Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Algorithms for unboundedly parallel simulations, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.201-221, Aug. 1991
	Mikhail J. Atallah , Michael T. Goodrich , S. Rao Kosaraju, Parallel algorithms for evaluating sequences of set-manipulation operations, Journal of the ACM (JACM), v.41 n.6, p.1049-1088, Nov. 1994
	G. Bilardi , F. P. Preparata, Size-time complexity of Boolean networks for prefix computations, Journal of the ACM (JACM), v.36 n.2, p.362-382, April 1989
	Mikhail J. Atallah , Hubert Wagener , Danny Z. Chen, An optimal parallel algorithm for the visibility of a simple polygon from a point, Journal of the ACM (JACM), v.38 n.3, p.515-532, July 1991
	Clyde P. Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.579-601, Oct. 1988
	Bernd Becker , Rolf Drechsler, A time optimal robust path-delay-fault self-testable adder, Proceedings of the conference on European design automation, p.376-381, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Edmund Clarke , Yulin Feng, Escher—a geometrical layout system for recursively defined circuits, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.650-653, July 1986, Las Vegas, Nevada, United States
	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
	Rajit Manohar , José A. Tierno, Asynchronous Parallel Prefix Computation, IEEE Transactions on Computers, v.47 n.11, p.1244-1252, November 1998
	Zvi Galil , Wolfgang J. Paul, An efficient general purpose parallel computer, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.247-262, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Raffaele Giancarlo , Roberto Grossi, Parallel construction and query of suffix trees for two-dimensional matrices, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.86-97, June 30-July 02, 1993, Velen, Germany
	Albert G. Greenberg , Boris D. Lubachevsky , Li-C. Wang, Experience in massively parallel discrete event simulation, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.193-202, June 30-July 02, 1993, Velen, Germany
	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
	Narayan C. Debnath, A study of control flow and data dependency interface (abstract), Proceedings of the 1990 ACM annual conference on Cooperation, p.435, February 20-22, 1990, Washington, D.C., United States
	Siddhartha Chatterjee , Guy E. Blelloch , Marco Zagha, Scan primitives for vector computers, Proceedings of the 1990 conference on Supercomputing, p.666-675, October 1990, New York, New York, United States
	A. S. McGough , I. Mitrani, Efficient parallel simulation of a sliding window protocol, Performance Evaluation, v.48 n.1-4, p.237-246, May 2002
	Shlomit S. Pinter , Ron Y. Pinter, Program optimization and parallelization using idioms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.305-327, May 1994
	Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.1-12, May 1990
	Haridimos T. Vergos , Costas Efstathiou , Dimitris Nikolos, Diminished-One Modulo 2^n +1 Adder Design, IEEE Transactions on Computers, v.51 n.12, p.1389-1399, December 2002
	Eric Schenk, Parallel dynamic lowest common ancestors, Nordic Journal of Computing, v.1 n.4, p.402-432, Winter 1994
	Siddhartha Chatterjee , Guy E. Blelloch , Allan L. Fisher, Size and access inference for data-parallel programs, ACM SIGPLAN Notices, v.26 n.6, p.130-144, June 1991
	Eunice E. Santos, Optimal and efficient algorithms for summing and prefix summing on parallel machines, Journal of Parallel and Distributed Computing, v.62 n.4, p.517-543, April 2002
	Yen-Chun Lin , Yao-Hsien Hsu , Chun-Keng Liu, Constructing H4, a Fast Depth-Size Optimal Parallel Prefix Circuit, The Journal of Supercomputing, v.24 n.3, p.279-304, March 2003
	Prasanta K. Jana , B. Damodara Naidu , Shailendra Kumar , Monish Arora , Bhabani P. Sinha, Parallel prefix computation on extended multi-mesh network, Information Processing Letters, v.84 n.6, p.295-303, 31 December 2002
	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
	Yen-Chun Lin , Chao-Cheng Shih, A New Class of Depth-Size Optimal Parallel Prefix Circuits, The Journal of Supercomputing, v.14 n.1, p.39-52, July 1999
	Yen-Chun Lin , Jian-Nan Chen, Z4: a new depth-size optimal parallel prefix circuit with small depth, Neural, Parallel & Scientific Computations, v.11 n.3, p.221-236, September 2003
	Alan A. Bertossi , Alessandro Mei, Time and work optimal simulation of basic reconfigurable meshes on hypercubes, Journal of Parallel and Distributed Computing, v.64 n.1, p.173-180, January 2004
	Hans Stadtherr, Scheduling interval orders with communication delays in parallel, Journal of Parallel and Distributed Computing, v.64 n.1, p.1-15, January 2004
	Danny Z. Chen, Efficient Geometric Algorithms on the EREW PRAM, IEEE Transactions on Parallel and Distributed Systems, v.6 n.1, p.41-47, January 1995
	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
	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
	Guy E. Blelloch , Gary L. Miller , Dafna Talmor, Developing a practical projection-based parallel Delaunay algorithm, Proceedings of the twelfth annual symposium on Computational geometry, p.186-195, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	John P. Fishburn, A depth-decreasing heuristic for combinational logic: or how to convert a ripple-carry adder into a carry-lookahead adder or anything in-between, Proceedings of the 27th ACM/IEEE conference on Design automation, p.361-364, June 24-27, 1990, Orlando, Florida, United States
	M. Takesue, A Family of Parallel Prefix Algorithms Embedded in Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.10, p.1179-1184, October 1993
	Alvin R. Lebeck , Gurindar S. Sohi, Request Combining in Multiprocessors with Arbitrary Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.11, p.1140-1155, November 1994
	Andreas Jakoby , Rüdiger Reischuk , Christian Schindelhauer, Circuit complexity: from the worst case to the average case, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.58-67, May 23-25, 1994, Montreal, Quebec, Canada
	Amihood Amir , Gary Benson, Two-dimensional periodicity and its applications, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.440-452, September 1992, Orlando, Florida, United States
	Costas Efstathiou , Haridimos T. Vergos , Dimitris Nikolos, Modulo 2n ± 1 Adder Design Using Select-Prefix Blocks, IEEE Transactions on Computers, v.52 n.11, p.1399-1406, November 2003
	Lampros Kalampoukas , Dimitris Nikolos , Costas Efstathiou , Haridimos T. Vergos , John Kalamatianos, High-Speed Parallel-Prefix Modulo 2n - 1 Adders, IEEE Transactions on Computers, v.49 n.7, p.673-680, July 2000
	Fadi A. Aloul , Arathi Ramani , Igor L. Markov , Karem A. Sakallah, Generic ILP versus specialized 0-1 ILP: an update, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.450-457, November 10-14, 2002, San Jose, California
	Christoph A. Herrmann , Christian Lengauer, Transforming rapid prototypes to efficient parallel programs, Patterns and skeletons for parallel and distributed computing, Springer-Verlag, London, 2003
	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
	Kai-Yeung Siu , Vwani P. Roychowdhury , Thomas Kailath, Depth-Size Tradeoffs for Neural Computation, IEEE Transactions on Computers, v.40 n.12, p.1402-1412, December 1991
	D. A. Carlson, Modified-Mesh Connected Parallel Computers, IEEE Transactions on Computers, v.37 n.10, p.1315-1321, October 1988
	D. M. Nicol , A. G. Greenberg , B. D. Lubachevsky, Massively Parallel Algorithms for Trace-Driven Cache Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.849-859, August 1994
	P. Kornerup, Digit-Set Conversions: Generalizations and Applications, IEEE Transactions on Computers, v.43 n.5, p.622-629, May 1994
	Giorgos Dimitrakopoulos , Dimitris Nikolos, High-Speed Parallel-Prefix VLSI Ling Adders, IEEE Transactions on Computers, v.54 n.2, p.225-231, February 2005
	Gyungho Lee, Parallelizing Iterative Loops with Conditional Branching, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.185-189, February 1995
	Nicholas Pippenger, The complexity of computations by networks, IBM Journal of Research and Development, v.31 n.2, p.235-243, March 1987
	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
	Dong-U Lee , Wayne Luk , John D. Villasenor , Peter Y. K. Cheung, A Gaussian Noise Generator for Hardware-Based Simulations, IEEE Transactions on Computers, v.53 n.12, p.1523-1534, December 2004
	R. Lin , K. Nakano , S. Olariu , M. C. Pinotti , J. L. Schwing , A. Y. Zomaya, Scalable Hardware-Algorithms for Binary Prefix Sums, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.838-850, August 2000
	A. Youssef, A Parallel Algorithm for Random Walk Construction with Application to the Monte Carlo Solution of Partial Differential Equations, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.355-360, March 1993
	Russ Miller , V. K. Prasanna-Kumar , Dionisios I. Reisis , Quentin F. Stout, Parallel Computations on Reconfigurable Meshes, IEEE Transactions on Computers, v.42 n.6, p.678-692, June 1993
	Haigeng Wang , Alexandru Nicolau , Stephen Keung , Kai-Yeung Sunny Siu, Computing Programs Containing Band Linear Recurrences on Vector Supercomputers, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.769-782, August 1996
	René Schott , Jean-Claude Spehner, Two optimal parallel algorithms on the commutation class of a word, Theoretical Computer Science, v.324 n.1, p.107-131, 16 September 2004
	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
	Kemal Efe , Antonio Fernández, Mesh-Connected Trees: A Bridge Between Grids and Meshes of Trees, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1281-1291, December 1996
	G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989
	Haigeng Wang , Alexandru Nicolau , Kai-Yeng S. Siu, The Strict Time Lower Bound and Optimal Schedules for Parallel Prefix with Resource Constraints, IEEE Transactions on Computers, v.45 n.11, p.1257-1271, November 1996
	Costas Efstathiou , Haridimos T. Vergos , Dimitris Nikolos, Fast Parallel-Prefix Modulo 2^n+1 Adders, IEEE Transactions on Computers, v.53 n.9, p.1211-1216, September 2004
	S. K. Prasad , S. K. Das , C. C. Y. Chen, Efficient EREW PRAM Algorithms for Parentheses-Matching, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.995-1008, September 1994
	Yen-Chun Lin , Jun-Wei Hsiao, A new approach to constructing optimal parallel prefix circuits with small depth, Journal of Parallel and Distributed Computing, v.64 n.1, p.97-107, January 2004
	Neil Burgess, New Models of Prefix Adder Topologies, Journal of VLSI Signal Processing Systems, v.40 n.1, p.125-141, May 2005
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu , Yitong Yin, Fast construction of overlay networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	M-Tahar Kechadi , Ilias K. Savvas, Dynamic task scheduling for irregular network topologies, Parallel Computing, v.31 n.7, p.757-776, July 2005
	Barry S. Fagin, Fast Addition of Large Integers, IEEE Transactions on Computers, v.41 n.9, p.1069-1077, September 1992
	David B. Skillicorn, Architecture-Independent Parallel Computation, Computer, v.23 n.12, p.38-50, December 1990
	S. B. Akers , B. Krishnamurthy, A Group-Theoretic Model for Symmetric Interconnection Networks, IEEE Transactions on Computers, v.38 n.4, p.555-566, April 1989
	D. Bakalis , K. D. Adaos , D. Lymperopoulos , M. Bellos , H. T. Vergos , G. Ph. Alexiou , D. Nikolos, A core generator for arithmetic cores and testing structures with a network interface, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.1, p.1-12, January 2006
	Yen-Chun Lin , Chin-Yu Su, Faster optimal parallel prefix circuits: new algorithmic construction, Journal of Parallel and Distributed Computing, v.65 n.12, p.1585-1595, December 2005
	Haikun Zhu , Chung-Kuan Cheng , Ronald Graham, On the construction of zero-deficiency parallel prefix circuits with minimum depth, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.387-409, April 2006
	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990
	Binay Sugla , David A. Carlson, Extreme Area-Time Tradeoffs in VLSI, IEEE Transactions on Computers, v.39 n.2, p.251-257, February 1990
	Belle W. Wei , Clark D. Thompson, Area-Time Optimal Adder Design, IEEE Transactions on Computers, v.39 n.5, p.666-675, May 1990
	Neil Burgess, The Flagged Prefix Adder and its Applications in Integer Arithmetic, Journal of VLSI Signal Processing Systems, v.31 n.3, p.263-271, July 2002
	Jin Hwan Park , H. K. Dai, Reconfigurable hardware solution to parallel prefix computation, The Journal of Supercomputing, v.43 n.1, p.43-58, January 2008
	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
	Pankaj K. Agarwal , Boris Aronov , Micha Sharir , Subhash Suri, Selecting distances in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.321-331, June 07-09, 1990, Berkley, California, United States
	Dieter Rautenbach , Christian Szegedy , Jürgen Werber, Delay optimization of linear depth boolean circuits with prescribed input arrival times, Journal of Discrete Algorithms, v.4 n.4, p.526-537, December, 2006
	Guodong Rong , Tiow-Seng Tan, Utilizing jump flooding in image-based soft shadows, Proceedings of the ACM symposium on Virtual reality software and technology, November 01-03, 2006, Limassol, Cyprus
	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
	T. C. E. Cheng , Liying Kang , C. T. Ng, An improved algorithm for the p-center problem on interval graphs with unit lengths, Computers and Operations Research, v.34 n.8, p.2215-2222, August, 2007
	John Kim , William J. Dally , Dennis Abts, Flattened butterfly: a cost-efficient topology for high-radix networks, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
	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
	Douglas Stott Parker, Jr. , Eric Simon , Patrick Valduriez, SVP: A Model Capturing Sets, Lists, Streams, and Parallelism, Proceedings of the 18th International Conference on Very Large Data Bases, p.115-126, August 23-27, 1992
	John T. O'donnell , Gudula Rünger, Derivation of a logarithmic time carry lookahead addition circuit, Journal of Functional Programming, v.14 n.6, p.697-713, November 2004
	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
	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
	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
	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
	Matthew M. Ziegler , Mircea R. Stan, A Unified Design Space for Regular Parallel Prefix Adders, Proceedings of the conference on Design, automation and test in Europe, p.21386, February 16-20, 2004
	Dirceu Cavendish , K. Selçuk Candan, Distributed XML processing: Theory and applications, Journal of Parallel and Distributed Computing, v.68 n.8, p.1054-1069, August, 2008
	Chin-Hsiung Wu , Shi-Jinn Horng , Ching-Feng Wen , Yuh-Rau Wang, Fast and scalable computations of 2D image moments, Image and Vision Computing, v.26 n.6, p.799-811, June, 2008
	Janis Voigtländer, Much ado about two (pearl): a pearl on parallel prefix computation, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, v.51 n.1, January 2008
	Robert R. Roxas , Nikolay N. Mirenkov, A visual environment for specifying global reduction operations, International Journal of High Performance Computing and Networking, v.1 n.1-3, p.100-116, August 2004
	John O'Donnell, Supporting tasks with adaptive groups in data parallel programming, International Journal of Computational Science and Engineering, v.1 n.2-4, p.86-98, May 2005
	Riyaz A. Patel , Mohammed Benaissa , Said Boussakta, Fast Parallel-Prefix Architectures for Modulo 2n-1 Addition with a Single Representation of Zero, IEEE Transactions on Computers, v.56 n.11, p.1484-1492, November 2007
	R. A. Patel , M. Benaissa , S. Boussakta, Fast Modulo 2^{n} - (2^{n - 2} + 1) Addition: A New Class of Adder for RNS, IEEE Transactions on Computers, v.56 n.4, p.572-576, April 2007
	Eunhui Park , Kunsoo Park, An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite Graph, Fundamenta Informaticae, v.84 n.1, p.81-97, August 2008
	Li-Ling Hung , Yen-Chun Lin, Parallel prefix algorithms on the multicomputer, WSEAS Transactions on Computer Research, v.3 n.4, p.213-223, April 2008
	Fadi A. Aloul , Arathi Ramani , Karem A. Sakallah , Igor L. Markov, Solution and Optimization of Systems of Pseudo-Boolean Constraints, IEEE Transactions on Computers, v.56 n.10, p.1415-1424, October 2007
	Yen-Chun Lin, Computation-efficient parallel prefix, Proceedings of the 6th WSEAS International Conference on Applied Informatics and Communications, p.280-285, August 18-20, 2006, Elounda, Greece
	Yen-Chun Lin , Li-Ling Hung, Fast problem-size-independent parallel prefix circuits, Journal of Parallel and Distributed Computing, v.69 n.4, p.382-388, April, 2009
	Yen-Chun Lin , Li-Ling Hung, Straightforward construction of depth-size optimal, parallel prefix circuits with fan-out 2, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.1, p.1-13, January 2009
	Alexander Gamkrelidze, Parallel adder with low costs and depth, Proceedings of the 3rd international conference on European computing conference, p.233-238, June 26-28, 2009, Tbilisi, Georgia
	Yen-Chun Lin , Li-Ling Hung, New parallel prefix algorithms, Proceedings of the 9th WSEAS international conference on Applied informatics and communications, p.204-209, August 20-22, 2009, Moscow, Russia