A comparison of list schedules for parallel processing systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A comparison of list schedules for parallel processing systems

Full text

Pdf (624 KB)

Source

Communications of the ACM archive
Volume 17 , Issue 12 (December 1974) table of contents

Pages: 685 - 690

Year of Publication: 1974

ISSN:0001-0782

Authors

Thomas L. Adam	Univ. of Texas at Austin, Austin
K. M. Chandy	Univ. of Texas at Austin, Austin
J. R. Dickson	Univ. of Texas at Austin, Austin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 30, Downloads (12 Months): 163, Citation Count: 75

Additional Information:

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

ABSTRACT

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented.

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	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	2	Ramamoorthy, C.V., Chandy, K.M., and Gonzalez, M.J. Jr. Optimal scheduling strategies in a multi-processor system. IEEETrans. Comp. C-21, 2 (Feb. 1972), 137-146.
	3	Ramamoorthy, C.V., and Gonzalez, M.J. Jr. A survey of techniques for recognizing parallel processable streams in computer programs. Proc. AFIPS 1969 FJCC, Vol. 35, AFIPS Press, Montvale, N.J., pp. 1-17.
	4	Fernandez, E.B., and Bussell, B. Bounds on the number of processors and time for multiprocessor optimal schedules. IEEE Trans. Comp., C-22, 8 (Aug. 1973), 745-751.
	5	Chandy, K.M., and Dickson, J.R. Scheduling unidentical processors in a stochastic environment. Proc. COMPCON '72, 1972, pp. 171-174.
	6	Coffman, E.G., and Graham, R.L. Optimal scheduling for two-processor systems. Acta Informatica, 1, 3 (1972), 200--213.
	7	Graham, R.L. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. (Nov. 1966), 1563-1581.
	8	Martin, D.F., and Estrin, G. Experiments on models of computations and systems. IEEE Trans. EC, EC-16, 1 (Feb. 1967), 59-69.
	9	Gonzalez, M.J. Jr. A decentralized parallel processor system. Ph.D. Diss. U. of Texas at Austin, 1971.
	10	Krone, M. Heuristic programming applied to scheduling models. Proc. Fifth Ann. Conf. on Inform. Sci. and Syst. Elec. Eng. Dep., Princeton U., (1971), pp. 841-848.
	11	G. K. Manacher, Production and Stabilization of Real-Time Task Schedules, Journal of the ACM (JACM), v.14 n.3, p.439-465, July 1967 [doi>10.1145/321406.321408]

CITED BY 75

	Mario J. Gonzalez, Jr., Deterministic Processor Scheduling, ACM Computing Surveys (CSUR), v.9 n.3, p.173-204, Sept. 1977
	K. M. Chandy , P. F. Reynolds, Scheduling partially ordered tasks with probabilistic execution times, ACM SIGOPS Operating Systems Review, v.9 n.5, p.169-177, November 1975
	Martin Grajcar, Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system, Proceedings of the 36th ACM/IEEE conference on Design automation, p.280-285, June 21-25, 1999, New Orleans, Louisiana, United States
	Xinan Tang , Guang R. Gao, How “hard” is thread partitioning and how “bad” is a list scheduling based partitioning algorithm?, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.130-139, June 28-July 02, 1998, Puerto Vallarta, Mexico
	T. M. Watts , M. L. Soffa , R. Gupta, Techniques for integrating parallelizing transformations and compiler-based scheduling methods, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.830-839, November 16-20, 1992, Minneapolis, Minnesota, United States
	F. Gasperoni , U. Schwiegelshohn , K. Ebcioğlu, On optimal loop parallelization, ACM SIGMICRO Newsletter, v.20 n.3, p.141-147, Sep. 1989
	B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, ACM SIGMICRO Newsletter, v.12 n.4, p.183-198, Dec. 1981
	M. C. Murphy , D. Rotem, Multiprocessor Join Scheduling, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.322-338, April 1993
	Dingchao Li , Yuji Iwahori , Naohiro Ishii, A recursive time estimation algorithm for program traces under resource constraints, Proceedings of the 1998 ACM symposium on Applied Computing, p.635-640, February 27-March 01, 1998, Atlanta, Georgia, United States
	Kunle A. Olukotun , Rachid Helaihel , Jeremy Levitt , Ricardo Ramirez, A Software-Hardware Cosynthesis Approach to Digital System Simulation, IEEE Micro, v.14 n.4, p.48-58, August 1994
	Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, ACM SIGOPS Operating Systems Review, v.27 n.5, p.203-216, Dec. 1993
	Y.-C. Chung , S. Ranka, Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.512-521, November 16-20, 1992, Minneapolis, Minnesota, United States
	Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999
	Mark Harris, Extending microcode compaction for real architectures, Proceedings of the 20th annual workshop on Microprogramming, p.40-53, December 01-04, 1987, Colorado Springs, Colorado, United States
	Mikhail Smelyanskiy , Scott A. Mahlke , Edward S. Davidson , Hsien-Hsin S. Lee, Predicate-aware scheduling: a technique for reducing resource constraints, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980
	Freddy Gabbay , Avi Mendelson, Using value prediction to increase the power of speculative execution hardware, ACM Transactions on Computer Systems (TOCS), v.16 n.3, p.234-270, Aug. 1998
	Ishfaq Ahmad , Yu-Kwong Kwok , Min-You Wu , Wei Shu, CASCH: A Tool for Computer-Aided Scheduling, IEEE Concurrency, v.8 n.4, p.21-33, October 2000
	Boontee Kruatrachue , Ted Lewis, Grain Size Determination for Parallel Processing, IEEE Software, v.5 n.1, p.23-32, January 1988
	Dingchao Li , Akira Mizuno , Yuji Iwahori , Naohiro Ishii, Booking heterogeneous processor resources to reduce communication overhead, Proceedings of the 1997 ACM symposium on Applied computing, p.354-360, April 1997, San Jose, California, United States
	E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994
	G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993
	C. Selvakumar , C. Siva Ram Murthy, Scheduling Precedence Constrained Task Graphs with Non-Negligible Intertask Communication onto Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.328-336, March 1994
	Muhammad K. Dhodhi , Imtiaz Ahmad , Anwar Yatama , Ishfaq Ahmad, An integrated technique for task matching and scheduling onto distributed heterogeneous computing systems, Journal of Parallel and Distributed Computing, v.62 n.9, p.1338-1361, September 2002
	Oliver Sinnen , Leonel Sousa, On Task Scheduling Accuracy: Evaluation Methodology and Results, The Journal of Supercomputing, v.27 n.2, p.177-194, February 2004
	John W. Chinneck , Vitoria Pureza , Rafik A. Goubran , Gerald M. Karam , Marco Lávoie, A fast task-to-processor assignment heuristic for real-time multiprocessor DSP applications, Computers and Operations Research, v.30 n.5, p.643-670, April 2003
	Shiv Prakash , Alice C. Parker, SOS: synthesis of application-specific heterogeneous multiprocessor systems, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Min-You Wu , Wei Shu , Jun Gu, Efficient Local Search for DAG Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.617-627, June 2001
	Andrei Radulescu , Arjan J. C. van Gemund, Low-Cost Task Scheduling for Distributed-Memory Machines, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.648-658, June 2002
	Oliver Sinnen , Leonel A. Sousa, Communication Contention in Task Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.503-515, June 2005
	Sekhar Darbha , Santosh Pande, A Robust Compile Time Method for SchedulingTask Parallelism on Distributed Memory Machines, The Journal of Supercomputing, v.12 n.4, p.325-347, October 1998
	Nadia Tawbi , Paul Feautrier, Processor allocation and loop scheduling on multiprocessor computers, Proceedings of the 6th international conference on Supercomputing, p.63-71, July 19-24, 1992, Washington, D. C., United States
	M. Al-Mouhamed, Analysis of Macro-Dataflow Dynamic Scheduling on Nonuniform Memory Access Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.875-888, August 1993
	Ishfaq Ahmad , Yu-Kwong Kwok, On Parallelizing the Multiprocessor Scheduling Problem, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.414-432, April 1999
	B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States
	S. Majumdar , D. L. Eager , R. B. Bunt, Scheduling in multiprogrammed parallel systems, ACM SIGMETRICS Performance Evaluation Review, v.16 n.1, p.104-113, May 1988
	Michael G. Norman , Peter Thanisch, Models of machines and computation for mapping in multicomputers, ACM Computing Surveys (CSUR), v.25 n.3, p.263-302, Sept. 1993
	Ted Lewis , Hesham El-Rewini, Parallax: A Tool for Parallel Program Scheduling, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.2, p.62-72, May 1993
	Sekhar Darbha , Dharma P. Agrawal, Optimal Scheduling Algorithm for Distributed-Memory Machines, IEEE Transactions on Parallel and Distributed Systems, v.9 n.1, p.87-95, January 1998
	Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996
	Min-You Wu , Wei Shu, On Parallelization of Static Scheduling Algorithms, IEEE Transactions on Software Engineering, v.23 n.8, p.517-528, August 1997
	Mayez Al-Mouhamed , Adel Al-Maasarani, Performance Evaluation of Scheduling Precedence-Constrained Computations on Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1317-1321, December 1994
	G. C. Sih , E. A. Lee, Declustering: A New Multiprocessor Scheduling Technique, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.625-637, June 1993
	M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990
	Mayez A. Al-Mouhamed, Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs, IEEE Transactions on Software Engineering, v.16 n.12, p.1390-1401, December 1990
	Andy Auyeung , Iker Gondra , H. K. Dai, Multi-heuristic list scheduling genetic algorithm for task scheduling, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Savina Bansal , Padam Kumar , Kuldip Singh, An Improved Duplication Strategy for Scheduling Precedence Constrained Graphs in Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.533-544, June 2003
	Gang Wang , Wenrui Gong , Ryan Kastner, Instruction scheduling using MAX-MIN ant system optimization, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Eric Anderson , Dirk Beyer , Kamalika Chaudhuri , Terence Kelly , Norman Salazar , Cipriano Santos , Ram Swaminathan , Robert Tarjan , Janet Wiener , Yunhong Zhou, Value-maximizing deadline scheduling and its application to animation rendering, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Nagarajan Kandasamy , John P. Hayes , Brian T. Murray, Time-Constrained Failure Diagnosis in Distributed Embedded Systems: Application to Actuator Diagnosis, IEEE Transactions on Parallel and Distributed Systems, v.16 n.3, p.258-270, March 2005
	Yoginder S. Dandass , Amit C. Bugde, Comparison of genetic representation schemes for scheduling soft real-time parallel applications, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
	Zhiao Shi , Jack J. Dongarra, Scheduling workflow applications on processors with different capabilities, Future Generation Computer Systems, v.22 n.6, p.665-675, May 2006
	Sanjeev Baskiyar , Christopher Dickinson, Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication, Journal of Parallel and Distributed Computing, v.65 n.8, p.911-921, August 2005
	J. C. Bier , E. E. Goei , W. H. Ho , P. D. Lapsley , M. P. O'Reilly , G. C. Sih , E. A. Lee, Gabriel: A Design Environment for DSP, IEEE Micro, v.10 n.5, p.28-45, September 1990
	Shiyuan Jin , Guy Schiavone , Damla Turgut, A performance study of multiprocessor task scheduling algorithms, The Journal of Supercomputing, v.43 n.1, p.77-97, January 2008
	Xinan Tang , J. Wang , Kevin B. Theobald , Guang R. Gao, Thread partitioning and scheduling based on cost model, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.272-281, June 23-25, 1997, Newport, Rhode Island, United States
	Nong Ye , Xueping Li , Toni Farley , Xiaoyun Xu, Job scheduling methods for reducing waiting time variance, Computers and Operations Research, v.34 n.10, p.3069-3083, October, 2007
	Wei-Hsuan Hung , Yi-Jung Chen , Chia-Lin Yang , Yen-Sheng Chang , Alan P. Su, An architectural co-synthesis algorithm for energy-aware network-on-chip design, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Abhishek Das , William J. Dally , Peter Mattson, Compiling for stream processing, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Shahaan Ayyub , David Abramson, GridRod: a dynamic runtime scheduler for grid workflows, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	Xiaojun Qi , Carson Jones , Scott Cannon, A simulation of power-aware scheduling of task graphs to multiple processors, Proceedings of the 18th conference on Proceedings of the 18th IASTED International Conference: modelling and simulation, p.233-238, May 30-June 01, 2007, Montreal, Canada
	Clayton S. Ferner , Robert G. Babb II, Automatic choice of scheduling heuristics for parallel/distributed computing, Scientific Programming, v.7 n.1, p.47-65, January 1999
	P. Bjorn-Jorgensen , J. Madsen, Critical path driven cosynthesis for heterogeneous target architectures, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.15, March 24-26, 1997
	Reakook Hwang , Mitsuo Gen , Hiroshi Katayama, A comparison of multiprocessor task scheduling algorithms with communication costs, Computers and Operations Research, v.35 n.3, p.976-993, March, 2008
	Haluk Topcuoglu , Salim Hariri , Dongmin Kim , Yoonhee Kim , Xue Bing , Baoqing Ye , Ilkyeun Ra , Jon Valente, The design and evaluation of a virtual distributed computing environment, Cluster Computing, v.1 n.1, p.81-93, 1998
	Oliver Sinnen , Leonel Augusto Sousa , Frode Eika Sandnes, Toward a Realistic Task Scheduling Model, IEEE Transactions on Parallel and Distributed Systems, v.17 n.3, p.263-275, March 2006
	Muthu Manikandan Baskaran , Nagavijayalakshmi Vydyanathan , Uday Kumar Reddy Bondhugula , J. Ramanujam , Atanas Rountev , P. Sadayappan, Compiler-assisted dynamic scheduling for effective parallelization of loop nests on multicore processors, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Aline P. Nascimento , Cristina Boeres , Vinod E. F. Rebello, Dynamic self-scheduling for parallel applications with task dependencies, Proceedings of the 6th international workshop on Middleware for grid computing, p.1-6, December 01-05, 2008, Leuven, Belgium
	Minh Quan Dang , Jorn Altmann, Resource allocation algorithm for light communication grid-based workflows within an SLA context, International Journal of Parallel, Emergent and Distributed Systems, v.24 n.1, p.31-48, February 2009
	Dang Minh Quan , D. Frank Hsu, Mapping Heavy Communication Grid-Based Workflows Onto Grid Resources Within an SLA Context Using Metaheuristics, International Journal of High Performance Computing Applications, v.22 n.3, p.330-346, August 2008
	Sang Cheol Kim , Sunggu Lee , Jaegyoon Hahm, Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.11, p.1489-1502, November 2007
	Andrei Tchernykh , Klaus Ecker, Worst Case Behavior of List Algorithms for Dynamic Scheduling of Non-unit Execution Time Tasks with Arbitrary Precedence Constrains, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.8, p.2277-2280, August 2008
	Yi-Jung Chen , Chia-Lin Yang , Yen-Sheng Chang, An architectural co-synthesis algorithm for energy-aware Network-on-Chip design, Journal of Systems Architecture: the EUROMICRO Journal, v.55 n.5-6, p.299-309, May, 2009
	Hui Jin , Xian-He Sun , Ziming Zheng , Zhiling Lan , Bing Xie, Performance under Failures of DAG-based Parallel Computing, Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, p.236-243, May 18-21, 2009
	Anurag Agarwal , Varghese S. Jacob , Hasan Pirkul, An Improved Augmented Neural-Network Approach for Scheduling Problems, INFORMS Journal on Computing, v.18 n.1, p.119-128, Winter 2006