Scheduling trees using FIFO queues

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scheduling trees using FIFO queues: a control-memory tradeoff

Full text

Pdf (830 KB)

Source

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

Cape May, New Jersey, United States

Pages: 85 - 93

Year of Publication: 1994

ISBN:0-89791-671-9

Authors

Sandeep Bhatt	Bellcore, Morristown, NJ
Fan Chung	Bellcore, Morristown, NJ
Tom Leighton	Massachusetts Institute of Technology, Cambridge
Arnold Rosenberg	Univ. of Massachusetts, Amherst

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 21, Citation Count: 0

Additional Information:

references 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/181014.181048 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	A. Gerasoulis and T. Yang (1992)" A comparison of clustering heuristics for scheduling dags on multiprocessors. J. Parallel and Distr. Comput.
	2	A. Gerasoulis and T. Yang (1992)" Scheduling program task graphs on MIMD architectures. Typescript, Rutgers Univ.
	3	Apostolos Gerasoulis , Tao Yang, Static Scheduling of Parallel Programs for Message Passing Architectures, Proceedings of the Second Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.601-612, September 01-04, 1992
	4	Lenwood S. Heath , Frank Thomson Leighton , Arnold L. Rosenberg, Comparing queues and stacks as mechanisms for laying out graphs, SIAM Journal on Discrete Mathematics, v.5 n.3, p.398-412, Aug. 1992 [doi>10.1137/0405031]
	5	Lenwood S. Heath , Sriram V. Pemmaraju, Stack and Queue Layouts of Posets, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1992
	6	L.S. Heath, S.V. Pemmaraju, A. Trenk (1993)" Stack and queue layouts of directed acyclic graphs, in Planar Graphs (W.T. Trotter, ed.), American Mathematical Society, Providence, R.I.# 5-11.
	7	Lenwood S. Heath , Arnold L. Rosenberg, Laying out graphs using queues, SIAM Journal on Computing, v.21 n.5, p.927-958, Oct. 1992 [doi>10.1137/0221055]
	8	S.J. Kim and J.C. Browne (1988): A general approach to mapping of parallel computations upon multiprocessor architectures, intl. Conf. on Parallel Processing 3, 1-8.
	9	M. Litzkow, M. Livny, M. Matka (1988): Condor- A hunter of idle workstations. 8th Ann. Intl. Conf. on Distributed Computing Systems.
	10	David A. Nichols , James H. Morris, Multiprocessing in a network of workstations, 1989
	11	Christos H. Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, SIAM Journal on Computing, v.19 n.2, p.322-328, April 1990 [doi>10.1137/0219021]
	12	M.S. Paterson and C.E. Hewitt (1970): Comparative schematology. Project MAC Conf. on Concurrent Systems and Parallel Computation, ACM Press, 119-128.
	13	Sriram Venkata Pemmarju, Exploring the powers of stacks and queues via graph layouts, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1992
	14	Arnold L. Rosenberg, Encoding Data Structures in Trees, Journal of the ACM (JACM), v.26 n.4, p.668-689, Oct. 1979 [doi>10.1145/322154.322160]
	15	S.W. White and D.C. Torney (1993): Use of a workstation cluster for the physical mapping of chromosomes. SIAM NEWS, March, 1993, 14-17.
	16	J. Yang, L. Bic, A. Nicolau (1991): A mapping strategy for MIMD computers. Intl. Con/. on Parallel Processing 1, 102-109.
	17	Tao Yang , Apostolos Gerasoulis, A fast static scheduling algorithm for DAGs on an unbounded number of processors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.633-642, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126138]
	18	Tao Yang , Apostolos Gerasoulis, PYRROS: static task scheduling and code generation for message passing multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.428-437, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143446]

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sequencing and scheduling

G. Mathematics of Computing
G.m MISCELLANEOUS
Subjects: Queueing theory**

General Terms:
Performance, Theory

REVIEW

"Sam Kim : Reviewer"

Tight upper and lower bounds on the queue capacity of algorithms for scheduling parallel tree-structured computations are presented. Actually, the paper deals with the fundamental question in a tradeoff between two major resources of a class o more...

Collaborative Colleagues:

Sandeep Bhatt: colleagues

Fan Chung: colleagues

Tom Leighton: colleagues

Arnold Rosenberg: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player