A fast static scheduling algorithm for DAGs on an unbounded number of processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast static scheduling algorithm for DAGs on an unbounded number of processors

Full text

Pdf (1.02 MB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1991 ACM/IEEE conference on Supercomputing table of contents

Albuquerque, New Mexico, United States

Pages: 633 - 642

Year of Publication: 1991

ISBN:0-89791-459-7

Authors

Tao Yang	Department of Computer Science, Rutgers University, New Brunswick, NJ
Apostolos Gerasoulis	Department of Computer Science, Rutgers University, New Brunswick, NJ

Sponsors

IEEE : Institute of Electrical and Electronics Engineers
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 34, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/125826.126138 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	Frank D. Anger , Jing-Jang Hwang , Yuan-Chieh Chow, Scheduling with sufficient loosely coupled processors, Journal of Parallel and Distributed Computing, v.9 n.1, p.87-92, May 1990 [doi>10.1016/0743-7315(90)90116-7]
	2	Fh. Chretienne, "Task Scheduling over Distributed Memory Machines," Proceedings of lhe International Workshop on Parallel and Dis- ~ributed Algorithms, North Holland, 1989.
	3	P h. Chretienne, " A Polynomial Algorithm to Optimally Schedule Tasks over an ideal Distributed System under Tree-like Precedence Constraints," European Journal of Operational Research, Vol. 2:43, pp. 225-230, 1989.
	4	Ph. Chretienne, Complexity of Tree Scheduling with Interprocessor Communication Delays, tLeport, M.A.S.I. 90.5, Universite Pierre et Marie Curie, 1990.
	5	J. Y. Colin and Ph. Chretienne, C.P.M. Scheduling wi~h Small Communication Delays and Task Duplicagion, Report, M.A.S.I. 90.1, Universite Pierre et Marie Curie, 1990.
	6	M. Cosnard, M. Marrakchi, Y. Robert, and D. Trystram, " Parallel Gaussian Elimination on an MIMD Computer," Parallel Compuging, Vol. 6, pp. 275-296, 1988.
	7	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
	8	G. A. Geist and M.T. Heath, " Matrix Factorization on a Hypercube Multiprocessor," Hypercube Multiprocessors, SIAM, pp. 161-180, 1986.
	9	A. Gerasoulis and I. Nelken, "Static Scheduling for Linear Algebra DAGs," Proceedings of $he Fourth Conference on Hypercubes, Monterey, Vol. 1, pp. 671-674, 1989.
	10	Apostolos Gerasoulis , Sesh Venugopal , Tao Yang, Clustering task graphs for message passing architectures, Proceedings of the 4th international conference on Supercomputing, p.447-456, June 11-15, 1990, Amsterdam, The Netherlands
	11	A. Gerasoulis and T. Yang, On ghe Granularity and Clustering of Directed Acyclic Task Graphs, TIL-153, Dept. of Computer Science, tLutgers Univ., 1990.
	12	A. Gerasoulis and T. Yang, A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessors, Report, Dept. of Computer Science, Rutgers Univ., August 1991.
	13	M. Girkar , C. Polychronopoulos, Partitioning programs for parallel execution, Proceedings of the 2nd international conference on Supercomputing, p.216-229, June 1988, St. Malo, France [doi>10.1145/55364.55386]
	14	R. L. Graham, " Bounds on Multiprocessing Timing Anomalies," SIAM J. Appl. Ma~h., vol. 17, pp. 416-429, 1969.
	15	J. K. Lenstra and A. H. G. tLinnooy Kan, " Complexity of Scheduling under Precedence Constraints," Operation Research, Vol. 26:1, 1978.
	16	H. Kasahara and S. Narita. " Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing," IEEE Trans. on Computers, Vol. C-33, pp. 1023-1029, 1984.
	17	Sung J Kim, A General Approach to Multiprocessor Scheduling, University of Texas at Austin, Austin, TX, 1988
	18	S. J. Kim and 3.C Browne, "A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures," International Conference on Parallel Processing, vol 3, pp. 1-8, 1988.
	19	Boontee Kruatrachue , Ted Lewis, Grain Size Determination for Parallel Processing, IEEE Software, v.5 n.1, p.23-32, January 1988 [doi>10.1109/52.1991]
	20	S. Y. Kung, VLSI array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
	21	J. M. Ortega, Introduction to Parallel & Vector Solution of Linear Systems, Plenum Press, New York, NY, 1988
	22	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]
	23	C. Picouleau, Two new NP-Complete Scheduling Problems with Communication Delays and Unlimited Number of Processors, M.A.S.I, Universite Pierre et Marie Curie Tour 45-46 B314, 4, place 3ussieu, 75252 Paris Cedex 05, France, 1991.
	24	Y. Saad, Gaussian elimination on hypercubes, Proceedings of the international workshop on Parallel algorithms & architectures, p.5-17, November 1986, Luminy, France
	25	Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
	26	Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
	27	T. Yang and A. Gerasoulis, Dominant Sequence Clustering Heuristic Algorithm for Scheduling DA Gs on Multiprocessor, Report, Dept. of Computer Science, Rutgers Univ., 1991.
	28	Min-You Wu and D. Gajski, "A Programming Aid for Hypcrcubc Architectures," The Journal of Supercomputing, Vol. 2, pp. 349-372, 1988.

CITED BY 16

	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
	G. Srinivasa N. Prasanna, Compilation of parallel multimedia computations—extending retiming theory and Amdahl's law, ACM SIGPLAN Notices, v.32 n.7, p.180-192, July 1997
	T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994
	Sandeep Bhatt , Fan Chung , Tom Leighton , Arnold Rosenberg, Scheduling trees using FIFO queues: a control-memory tradeoff, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.85-93, June 27-29, 1994, Cape May, New Jersey, United States
	Dinesh Kadamuddi , Jeffrey J. P. Tsai, Clustering Algorithm for Parallelizing Software Systems in Multiprocessors Environment, IEEE Transactions on Software Engineering, v.26 n.4, p.340-361, April 2000
	G. N. Srinivasa Prasanna , A. Agrawal , B. R. Musicus, Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.720-736, July 1994
	A. Gerasoulis , T. Yang, On the Granularity and Clustering of Directed Acyclic Task Graphs, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.686-701, June 1993
	G. N. Srinivasa Prasanna , B. R. Musicus, Generalized Multiprocessor Scheduling and Applications to Matrix Computations, IEEE Transactions on Parallel and Distributed Systems, v.7 n.6, p.650-664, June 1996
	Joseph C. Jacob , Soo-Young Lee, Task Spreading and Shrinking on Multiprocessor Systems and Networks of Workstations, IEEE Transactions on Parallel and Distributed Systems, v.10 n.10, p.1082-1101, October 1999
	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
	Shankar Ramaswamy , Sachin Sapatnekar , Prithviraj Banerjee, A Framework for Exploiting Task and Data Parallelism on Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.8 n.11, p.1098-1116, November 1997
	Pieter Bellens , Josep M. Perez , Rosa M. Badia , Jesus Labarta, Memory---CellSs: a programming model for the cell BE architecture, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
	J. P. Perez , P. Bellens , R. M. Badia , J. Labarta, CellSs: making it easier to program the cell broadband engine processor, IBM Journal of Research and Development, v.51 n.5, p.593-604, September 2007
	Alan Sheahan , Conor Ryan, A transformation-based approach to static multiprocessor scheduling, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Bastian Ristau , Torsten Limberg , Gerhard Fettweis, A mapping framework for guided design space exploration of heterogeneous MP-SoCs, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	Pieter Bellens , Josep M. Perez , Felipe Cabarcas , Alex Ramirez , Rosa M. Badia , Jesus Labarta, CellSs: Scheduling techniques to better exploit memory hierarchy, Scientific Programming, v.17 n.1-2, p.77-95, January 2009