Complexity Results for Permuting Data and Other Computations on Parallel Processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity Results for Permuting Data and Other Computations on Parallel Processors

Full text

Pdf (878 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 2 (April 1984) table of contents

Pages: 193 - 209

Year of Publication: 1984

ISSN:0004-5411

Authors

Allan Gottlieb	Courant Institute, New York University, 251 Mercer Street, New York, NY
Clyde P. Kruskal	Department of Computer Science, University of Illinois, 222 Digital Computer Laboratory, 1304 West Springfield, Urbana, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 3

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/62.322423 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	Gerard Maurice Baudet, The design and analysis of algorithms for asynchronous multiprocessors., 1978
	2	BAUDET, G., AND STEVENSON, D.Optimal sorting algorithms for parallel computers. IEEE Trans. Comput C.27 (1974), 84-87.
	3	BEnES, V.E.Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York, 1965.
	4	BERGr, C. Graphs and Hypergraphs. 2d ed. Elsevier North-Holland, New York, 1976.
	5	CLOS, C.A study of nonblocking switching networks. Bell Syst. Tech. J. 32 (t95J), 406-424.
	6	D}RAC, G.A.Some theorems on abstract graphs. Proc. London Math. Sac. (1952), 69-81.
	7	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	8	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 [doi>10.1145/322047.322057]
	9	L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
	10	GOTTLIEB, A., GRISHMAN, R., KRUSKAL, C.P, McAuuvrv, K.P., RUDOLPH, L., AND SN, R, M. The NYU ultracomputer~Designing an MIMD shared memory parallel computer, IEEE Trans. Comput 32 (Feb. 1983), 175-189.
	11	CrOTTLIEB, A., AND KRUSKAL, C.P. Supersaturated Ultracomputer Algorithms, Ultracomputer Note # 1 I, Coumnt Institute, New York Univ., New York, 1980.
	12	HARARY, F.Graph Theory. Addison.Wesley, Reading, Mass., 1972.
	13	Donald E. Knuth, Big Omicron and big Omega and big Theta, ACM SIGACT News, v.8 n.2, p.18-24, April-June 1976 [doi>10.1145/1008328.1008329]
	14	LAWmt/, D. Access and alignment of data in an array processor. IEEE Trans. Comput. 24 (1975), 1145-1155.
	15	LEV, G., PIPPENGER, N., AND VALIANT, L.G. A fast parallel algorithm for muting in permutation networks. IEEE Trans Comput (7.30 (1981), 93-100.
	16	MUNRO, I., AND PATERSON, M.Optimal algorithms for parallel polynomial evaluation, Z Comput. Syst. Sci. 7 (1973), 189-198.
	17	NASSIMt, D., AND SAHNI, S.Parallel algorithms to setup the benes permutation network. IEEE Trans. Comput. C-31 (1982), 148-154.
	18	OPWRM^N, D.C., ANO TSAO-WU, N.T.On a class of reawangeable switching networks. Bell System Tech. ~ 50(1971), 1579-1618.
	19	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]
	20	STONE, H.S.Parallel processing with the perfect shuffle. IEEE Tram. Comput. C.20 (1971), 153-161,
	21	VALIANT, L.G.Parallelism in comparison problems. SIAM J. Comput. 4 (1975), 348-355.
	22	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
	23	Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

CITED BY 3

	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
	Y. Han, An optimal linked list prefix algorithms on a local memory computer, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.278-286, February 21-23, 1989, Louisville, Kentucky
	Yijie Han, An Optimal Linked List Prefix Algorithm on a Local Memory Computer, IEEE Transactions on Computers, v.40 n.10, p.1149-1153, October 1991