More Web Proxy on the site http://driver.im/

article

A new strategy for multiprocessor scheduling of cyclic task graphs

Authors:

Frode E. Sandnes,

Oliver SinnenAuthors Info & Claims

International Journal of High Performance Computing and Networking, Volume 3, Issue 1

Pages 62 - 71

https://doi.org/10.1504/IJHPCN.2005.007868

Published: 01 September 2005 Publication History

Abstract

A modular strategy for scheduling iterative computations is proposed. Iterative computations are represented using cyclic task graphs that are transformed into acyclic task graphs. These acyclic task graphs are subsequently scheduled using one of the many well known and high quality static scheduling strategies from the literature. Graph unfolding is not employed and the generated schedules therefore require less memory than schedules generated through graph unfolding. Further, the number of iterations does not need to be known at compile time. The paper experimentally quantifies how the task transformation affects the make span of the schedules and the effectiveness of the approach is compared to other methods including a graph unfolding strategy. A new more intuitive graph unfolding formulation is also presented.

References

[1]

Ahmad, L. and Dhodhi, M.K. (1996) 'Multiprocessor scheduling in a genetic paradigm', Parallel Computing, Vol. 22, pp. 395-406.

Digital Library

[2]

Allan, V.H., Jones, R.B., Lee, R.M. and Allan, S.J. (1995) 'Software pipelining', ACM Computing Surveys, Vol. 27, No. 3, pp. 367-432.

Digital Library

[3]

Calland, P.Y., Darte, A. and Robert, Y. (1998) 'Circuit retiming applied to decomposed software pipelining', IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 1, pp. 24-35.

[4]

Chao, L.F. and Sha, E.H.M. (1997) 'Scheduling data-flow graphs via retiming and unfolding', IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 12, pp. 1259-1267.

Digital Library

[5]

Cormen, T.H., Leiserson, C.E. and Rivest, R.L. (1990) Introduction to algorithms, MIT Press, pp. 477-483.

Digital Library

[6]

Correa, R.C., Ferreira, A. and Rebreyend, P. (1999) 'Scheduling multiprocessor tasks with genetic algorithms', IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 8, pp. 825-837.

Digital Library

[7]

Hanen, C. and Munier, A. (1994) 'Cyclic scheduling on parallel processors: an overview', in Chr'etienne, P., Coffman, E.G., Lenstra, J.K. and Liu, Z. (Eds.): Scheduling Theory and its Applications, John Wiley & Sons Ltd, New Jersey, USA, pp. 193-226.

[8]

Jeng, L.G. and Chen, L.G (1992) 'Rate-optimal static scheduling for recursive DSP algorithms by retiming and unforlding', International Journal of Electronics, Vol. 73, No. 4, pp. 687-701.

[9]

Kasahara, H. and Narita, S. (1985) 'Parallel processing of robot-arm control computation on a multiprocessor system', IEEE Journal of Robotics and Automation, Vol. RA-1, No. 2, pp. 104-113.

[10]

Knijnenburg, P.M.W., Kisuki, T. and O'Boyle, M.F.P. (2003) 'Combined selection of tile sizes and unroll factors using iterative compilation', Journal of Supercomputing, Vol. 24, No. 1, pp. 43-67.

[11]

Kohler, W.H. (1975) 'A preliminary evaluation of the critical path method for scheduling tasks on multiprocessor systems', IEEE Transactions on Computers, Vol. C-24, pp. 1235-1238.

[12]

Kung, S.Y. (1988) VLSI Array Processors, Prentice Hall, Information and System Sciences Series.

[13]

Kwok, Y.C. and Ahmad, I. (1996) 'Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors', IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 5, pp. 506-521.

Digital Library

[14]

Lam, M. (1988) 'Software pipelining: an effective scheduling technique for VLIW machines', In Proc. of the 8th Int. Conf. on Programming Languages, Design and Implementation, pp. 258-267.

[15]

Lucke, L.E. and Parhi, K.K. (1993) 'Data-flow transformations for critical path time reduction in highlevel DSP synthesis', IEEE Transactions on Computer-Aided Design, Vol. 12, No. 7, pp. 1063-1068.

Digital Library

[16]

Manoharan, S. (2001) 'Effect of task duplication on the assignment of dependency graphs', Parallel Computing, Vol. 27, No. 3, pp. 257-268.

Digital Library

[17]

Parhi, K.K. and Messerschmitt, D.G. (1991) 'Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding', IEEE Transactions on Computing, Vol. 40, No. 2, pp. 178-195.

[18]

Piriyakumar, D.A.L., Levi, P. and Murthy, C.S.R. (1999) 'Optimal scheduling of iterative data-flow programs onto multiprocessors with non-negligible interprocessor communication', Proceedings of HPCN Europe, pp. 732-743.

[19]

Reiter, R. (1968) 'Scheduling parallel computations', Journal of the ACM, Vol. 15, No. 4, pp. 590-599.

Digital Library

[20]

Sandnes, F.E. (2003) 'Secure distributed configuration management with randomised scheduling of system-administration tasks', IEICE Transactions on Information and Systems, Vol. E86-D, No. 9, pp. 1601-1610.

[21]

Sandnes, F.E. and Megson, G.M. (1998) 'Improved static multiprocessor scheduling using cyclic task graphs: a genetic approach', Parallel Computing: Fundamentals, Applications and New Directions, North-Holland, Vol. 12, pp. 703-710.

[22]

Shukla, S.B. and Agrawal, D.P. (1994) 'A framework for mapping periodic real-time applications on multicomputers', IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 7, pp. 778-784.

Digital Library

[23]

Sinnen, O. and Sousa, L. (2003) 'Experimental evaluation of task scheduling accuracy: implications for the scheduling model', IEICE Transactions on Information and Systems, Vol. E86-D, No. 9, pp. 1620-1627.

[24]

Tongsima, S., O'Neil, T.W., Chantrapornchai, C. and Sha, E.H.M (2000) 'Properties and algorithms for unfolding of probabilistic data-flow graphs', Journal of VLSI Signal Processing Systems for Signal Image and Video Technology, Vol. 25, No. 3, pp. 215-233.

Digital Library

[25]

Wang, C.Y. and Parhi, K.K. (1995) 'High-level DSP Synthesis using Concurrent transformations, scheduling and allocation', IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Vol. 14, No. 3, pp. 274-295.

Digital Library

[26]

Wang, D.J. and Hu, Y.H. (1994) 'Fully static multiprocessor array realizability criteria for real-time recurrent DSP applications', IEEE Transactions on Signal Processing, Vol. 42, No. 5, pp. 1288-1292.

Digital Library

[27]

Weinblatt, H. (1972) 'A new algorithm for finding the simple cycles of a finite directed graph', Journal of the ACM, Vol. 19, No. 1, pp. 45-56.

Digital Library

[28]

Yang, T. and Fu, C. (1997) 'Heuristic algorithms for scheduling iterative task computations on distributed memory machines', IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 6, pp. 608-622.

Digital Library

Cited By

(2019)A novel rural microcredit decision model and solving via binary differential evolution algorithmInternational Journal of Computational Science and Engineering10.5555/3337494.333749918:3(252-260)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3337494.3337499
DAB ASlama YGuan S(2018)Optimized approach based on time prediction and space chunking for polyhedron programs parallelization on multicoresProceedings of the 2nd International Conference on High Performance Compilation, Computing and Communications10.1145/3195612.3195615(22-26)Online publication date: 15-Mar-2018
https://dl.acm.org/doi/10.1145/3195612.3195615
Sandnes FEika EMedola F(2018)Towards a Framework for the Design of Quantitative Experiments: Human-Computer Interaction and Accessibility ResearchUniversal Access in Human-Computer Interaction. Methods, Technologies, and Users10.1007/978-3-319-92049-8_8(107-120)Online publication date: 15-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-92049-8_8
Show More Cited By

A new strategy for multiprocessor scheduling of cyclic task graphs

Recommendations

Online Scheduling of Dynamic Task Graphs with Communication and Contention for Multiprocessors

This paper presents an online scheduling methodology for task graphs with communication edges for multiprocessor embedded systems. The proposed methodology is designed for task graphs which are dynamic in nature either due to the presence of conditional ...
Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling

In this paper, we extend Liu and Layland’s utilization bound for fixed priority scheduling on uniprocessors to homogeneous multiprocessor systems under a partitioning strategy. Assuming that tasks are pre-emptively scheduled on each processor according ...
Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of High Performance Computing and Networking

International Journal of High Performance Computing and Networking Volume 3, Issue 1

September 2005

78 pages

ISSN:1740-0562

EISSN:1740-0570

Issue’s Table of Contents

Publisher

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Published: 01 September 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2019)A novel rural microcredit decision model and solving via binary differential evolution algorithmInternational Journal of Computational Science and Engineering10.5555/3337494.333749918:3(252-260)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3337494.3337499
DAB ASlama YGuan S(2018)Optimized approach based on time prediction and space chunking for polyhedron programs parallelization on multicoresProceedings of the 2nd International Conference on High Performance Compilation, Computing and Communications10.1145/3195612.3195615(22-26)Online publication date: 15-Mar-2018
https://dl.acm.org/doi/10.1145/3195612.3195615
Sandnes FEika EMedola F(2018)Towards a Framework for the Design of Quantitative Experiments: Human-Computer Interaction and Accessibility ResearchUniversal Access in Human-Computer Interaction. Methods, Technologies, and Users10.1007/978-3-319-92049-8_8(107-120)Online publication date: 15-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-92049-8_8
Cao FZhu M(2015)Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environmentInternational Journal of High Performance Computing and Networking10.1504/IJHPCN.2015.0727838:4(324-336)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1504/IJHPCN.2015.072783
Belaid IMuller FBenjemaa M(2011)Static scheduling of periodic hardware tasks with precedence and deadline constraints on reconfigurable hardware devicesInternational Journal of Reconfigurable Computing10.5555/1972694.20433332011(9-9)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/1972694.2043333
Ferrandi FPilato CSciuto DTumeo ALin Y(2010)Mapping and scheduling of parallel C applications with ant colony optimization onto heterogeneous reconfigurable MPSoCsProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899904(799-804)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1899721.1899904
Lam YCoutinho JHo CLeong PLuk W(2010)Multiloop parallelisation using unrolling and fissionInternational Journal of Reconfigurable Computing10.1155/2010/4756202010(1-1)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1155/2010/475620
Burgess MSandnes F(2006)A promise theory approach to collaborative power reduction in a pervasive computing environmentProceedings of the Third international conference on Ubiquitous Intelligence and Computing10.1007/11833529_63(615-624)Online publication date: 3-Sep-2006
https://dl.acm.org/doi/10.1007/11833529_63

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents