International Research Journal of Commerce , Arts and Science

 ( Online- ISSN 2319 - 9202 )     New DOI : 10.32804/CASIRJ

Impact Factor* - 6.2311


**Need Help in Content editing, Data Analysis.

Research Gateway

Adv For Editing Content

   No of Download : 40    Submit Your Rating     Cite This   Download        Certificate

A SURVEY OF MULTIPROCESSORS TASKS SCHEDULING ALGORITHMS

    1 Author(s):  JUGMENDRA SINGH

Vol -  7, Issue- 5 ,         Page(s) : 46 - 70  (2016 ) DOI : https://doi.org/10.32804/CASIRJ

Abstract

In this paper, we survey some representative algorithms for offline scheduling DAG type applications in a deterministic environment, where it is assumed that the prediction of task execution time and network bandwidth/latency is accurate. However, in a real world computing environment, the probability of a precomputed schedule being executed exactly as expected is low. Due to resource sharing among multiple users, the performance of resources is inherently variant. In a static scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP complete problem in general, researchers have resorted to devising efficient heuristics. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context.

  1. [Adam74]
  2. T. L. Adam, K. M. Chandy, and J. R. Dickson. A comparison of list schedules for parallel processing systems. Commun. ACM, 17(12):685–690, 1974.
  3. [Ahma94] I. Ahmad and Y.-K. Kwok. A new approach to scheduling parallel programs using task duplication. In Proc. Int’l Conf Parallel Processing, volume 2, pages 47–51, 1994.
  4. [Ahma98] I. Ahmad and Y.-K. Kwok. On exploiting task duplication in parallel program scheduling. IEEE Trans. Parallel Distrib. Syst, 9(9):872–892, 1998.
  5. [Ali94] S. Ali, S. M. Sait, and M. S.T. Benten. GSA: Scheduling and allocation using genetic algorithm. In Proceedings of the 1994 European Design Automation Con-ference, pages 84–89, Toronto, Canada, September 1994.
  6. [Brau98] J. T. D. Braun, H. J. Siegel, N. Beck, L. B¨ol¨oni, M. Maheswaran, A. I. Reuther,P. Robertson, M. D. Theys, and B. Yao. A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems. In Reliable Distributed Systems, 1998. Proceedings. Seventeenth IEEE Symposium on, pages 330–335, West Lafayette, IN, 1998.
  7. [Correa99] R.C. Corrˆea, A. Ferreira, and P. Rebreyend. Scheduling multiprocessor tasks with genetic algorithms. IEEE Transactions on Parallel and Distributed Systems, 10(8):825–837, 1999.
  8. [Coul05] G. Coulouris, J. Dollimore, and T. Kindberg. Distributed systems: concepts and design. Addison Wesley, Essex, England, 2005.
  9. [Darb97] S. Darbha and D. P. Agrawal. A task duplication based scalable scheduling algo-rithm for distributed memory systems. J. Parallel Distrib. Comput, 46(1):15–27, 1997.
  10. [Davi91] L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, NY, 1991.
  11. [Gema84] S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, 6(6):721–741, November 1984.
  12. [Gera92] A. Gerasoulis and T. Yang. A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors. Journal of Parallel and Distributed Computing, 16(4):276–291, December 1992.
  13. [Gold89] D. E. Goldberg. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, Massachusetts, 1989.
  14. [Holl92] J. H. Holland. Adaption in Natural and Artificial Systems. MIT Press, 1992.
  15. [Hou94] E. S. H. Hou, N. Ansari, and H. Ren. A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel Distrib. Syst., 5(2):113–120, 1994.
  16. [Hwan89] J.-J. Hwang, Y.-C. Chow, F. D. Anger, and C.-Y. Lee. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput., 18(2):244–257, 1989.
  17. [Jame99] H. A. James. Scheduling in Metacomputing Systems. PhD thesis, University of Adelaide, Adelaide,Australia, 1999.
  18. [Kim88] S. J. Kim and J. C. Browne. A general approach to mapping of parallel compu-tation upon multiprocessor architectures. In Proceedings of International Conf. Parallel Processing, volume 2, pages 1–8, 1988.
  19. [Krua88] B. Kruatrachue and T. Lewis.  Grain size determination for parallel processing.IEEE Softw., 5(1):23–32, 1988.
  20. [Kwak99(b)] Y.-K. Kwok and I. Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv., 31(4):406–471, 1999.
  21. [Kwok94] Y.-K. Kwok and I. Ahmad. Exploiting duplication to minimize the execution times of parallel programs on message-passing systems. In Proceedings of the 6th Symposium on Parallel and Distributed Processing, pages 426–433, Los Alamitos, CA, USA, October 1994. IEEE Computer Society Press.
  22. [Kwok96] Y.-K. Kwok and I. Ahmad. Dynamic critical-path scheduling: An e?ective tech-nique for allocating task graphs to multiprocessors. IEEE Trans. Parallel Distrib. Syst., 7(5):506–521, 1996.
  23. [Kwok99(a)] Y.-K. Kwok and I. Ahmad. Benchmarking and comparison of the task graph scheduling algorithms. J. Parallel Distrib. Comput., 59(3):381–422, 1999.
  24. [Laar92] P. J. M. van Laarhoven and E. H. L. Aarts. Simulated annealing: theory and applications. Kluwer, Dordrecht, 1992.
  25. [Park97] G.-L. Park, B. Shirazi, and J. Marquis. DFRN: A new approach for duplication based scheduling for distributed memory multiprocessor systems. In IPPS ’97: Proceedings of the 11th International Symposium on Parallel Processing, pages 157–166, Washington, 
  26. DC, USA, 1997. IEEE Computer Society.
  27. [Radu00] A. Radulescu and A. J. C. Van Gemund. Fast and e?ective task scheduling in heterogeneous systems. In HCW ’00: Proceedings of the 9th Heterogeneous Computing Workshop, page 229, Washington, DC, USA, 2000. IEEE Computer Society.
  28. [Rana00(a)] S. Ranaweera and D. Agrawal. A scalable task duplication based scheduling algo-rithm for heterogeneous systems. In Proceedings of 2000 International Conference on Parallel Processing (29th ICPP’00), Toronto, Canada, August 2000. Ohio State Univ.
  29. [Rana00(b)] S. Ranaweera and D. P. Agrawal. A task duplication based scheduling algorithm for heterogeneous systems. In 14th International Parallel and Distributed Pro-cessing Symposium (SPDP’2000), pages 445–450, Washington - Brussels - Tokyo, May 2000. IEEE.
  30. [Revi90] H. El-Rewini and T. G. Lewis. Scheduling parallel program tasks onto arbitrary target machines. J. Parallel Distrib. Comput., 9(2):138–153, 1990.
  31. [Sark89] V. Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press, Cambridge, Massachusetts, 1989.
  32. [Sih93] G. C. Sih and E. A. Lee. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel Distrib. Syst., 4(2):175–187, 1993.
  33. [Sing96] H. Singh and A. Youssef. Mapping and scheduling heterogeneous task graphs using genetic algorithms. In Proc. Heterogeneous Computing Workshop, pages 86–97, 1996.
  34. [Topc02] H. Topcuoglu, S. Hariri, and M.-Y. Wu. Performance-e?ective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst., 13(3):260–274, 2002.
  35. [Wang97] L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. Journal of Parallel and Distributed Computing, 47(1):8–22, November 1997.
  36. [Wu04] A. S. Wu, H. Yu, S. Jin, K.-C. Lin, and G. Schiavone. An incremental genetic  algorithm approach to multiprocessor scheduling. IEEE Transactions on Parallel and Distributed Systems, 15(9):824–834, 2004.
  37. [Wu90] M. Y. Wu and D. D. Gajski. Hypertool: A programming aid for message-passing systems. IEEE Trans. Parallel Distrib. Syst., 1(3):330–343, 1990.
  38. [Yang94] T. Yang and A. Gerasoulis. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst., 5(9):951–967, 1994.
  39. [Zhao03] H. Zhao and R. Sakellariou. An experimental investigation into the rank function of the heterogeneous earliest finish time scheduling algorithm. In Proceedings of 9th International Euro-Par Conference. Springer-Verlag, 2003.
  40. [Zoma99] A. Y. Zomaya, C. Ward, and B. Macey. Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed Systems, 10(8):795–812, 1999.

*Contents are provided by Authors of articles. Please contact us if you having any query.






Bank Details