Optimal dynamic scheduling of task tree on constant-dimensional architectures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal dynamic scheduling of task tree on constant-dimensional architectures

Full text

Pdf (835 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, United States

Pages: 138 - 146

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Xiangdong Yu
Dipak Ghosal

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references 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/140901.140916 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	F. Afrati, C.H. Papadimitrou and G. Papageorgiou, Scheduling DAGS to Minimize time and communication, Technical Report, National Technical University of Athens, Athens, Greece, 1985.
	2	S. Bhatt and J. Cai, "Take a walk, Grow a Tree", FOCS, 1988, pp. 469-478.
	3	S. Bhatt, F. Chung, T.Leighton, and A. Rosenberg, Optimal Simulations of Tree Machines, FOCS, 1986, pp. 274-282.
	4	Sandeep Bhatt , David Greenberg , Tom Leighton , Pangfeng Liu, Tight bounds for on-line tree embeddings, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.344-350, January 28-30, 1991, San Francisco, California, United States
	5	S. Bhatt, and I. Ipsen, Embedding Trees in the Hypercube, YALE University Research Report nn- S (1985).
	6	Mee Yee Chan, Embedding of grids into optimal hypercubes, SIAM Journal on Computing, v.20 n.5, p.834-864, Oct. 1991 [doi>10.1137/0220052]
	7	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	8	Allan L. Fisher , H. T. Kung, Synchronizing large VLSI processor arrays, Proceedings of the 10th annual international symposium on Computer architecture, p.54-58, June 13-17, 1983, Stockholm, Sweden
	9	Anja Feldmann , Jiří Sgall , Shang-Hua Teng, Dynamic scheduling on parallel machines, Proceedings of the 32nd annual symposium on Foundations of computer science, p.111-120, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185355]
	10	D. Ghosal, A. Mukherjee, R. Thurimella, and Y. Yesha, Mapping Task Trees onto a Linear Array, 1991 Int'l Conference on Parallel Processing, August 1991.
	11	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	12	Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
	13	W. D. 1-Iillis, The Connection Machine, MIT Press, Cambridge, Mass., 1985.
	14	Jia-Wei Hong , Kurt Mehlhorn , Arnold L. Rosenberg, Cost Trade-offs in Graph Embeddings, with Applications, Journal of the ACM (JACM), v.30 n.4, p.709-728, Oct. 1983 [doi>10.1145/2157.322401]
	15	T. C. Hu. Parallel Sequencing and Assembly Line Problem, Operations ttesearch, Vol. 9, Nov. 1961, pp. 841-848.
	16	S. R. Kosaraju , A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	17	R. Koch , T. Leighton , B. Maggs , S. Rao, Work-preserving emulations of fixed-connection networks, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.227-240, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73029]
	18	H. Kasahara and S. Narit, Practical Multiprocc~or Scheduling Algorit~hm~ for Efficient Parallel Processing, IEEE Transactions on Computers, c-a3(11), Nov. 1984, pp. 1023-1029.
	19	MASPAR- The massively parallel architecture, MASPAR Inc. 1990.
	20	G.L. Miller and J.H.Reif, Parallel Tree Contraction and its Application, Proc. of 26~h IEEE Symposium on Foundations of Computer Science, 1985, pp.478-489.
	21	Christos H. Papadimitriou , Jeffrey D. Ullman, A communication-time tradeoff, SIAM Journal on Computing, v.16 n.4, p.639-646, Aug. 1987 [doi>10.1137/0216044]
	22	C. C. Shen and W. H. Tsai, A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minmax Criterion, IEEE Transactions on Computers, c-34(3), March 1985, pp. 197-203.
	23	David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]
	24	A. Wagner, Embedding arbitrary binary trees in a Hypercube, J. of Parallel and Distributed Computing, 7, 1989, pp. 503-520.
	25	I-Chen Wu , H. T. Kung, Communication complexity for parallel divide-and-conquer, Proceedings of the 32nd annual symposium on Foundations of computer science, p.151-162, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185364]