Task scheduling accuracy analysis in optical grid environments

详细信息    查看全文

• 作者：Wei Guo (1)
  Zhengyu Wang (1)
  Zhenyu Sun (1)
  Weiqiang Sun (1)
  Yaohui Jin (1)
  Weisheng Hu (1)
  Chunming Qiao (2)
  
• 关键词：Task scheduling ; Scheduling accuracy ; Accuracy deviation ; Optical grid environment
• 刊名：Photonic Network Communications
• 出版年：2009
• 出版时间：June 2009
• 年：2009
• 卷：17
• 期：3
• 页码：209-217
• 全文大小：590KB
• 参考文献：1. Simeonidou D., Nejabati C., Zervas G., Klonidis D., Tzanakaki A., O’Mahony M.J.: Dynamic optical network architectures and technologies for existing and emerging grid services. IEEE/OSA. J. Lightwave Technol. 23, 3347-357 (2005). doi:10.1109/JLT.2005.856254 CrossRef
  2. Jukan A., Karmous-Edwards G.: Optical control plane for the grid community. IEEE Commun. Surveys Tutorials 9(3), 30-4 (2007) CrossRef
  3. Wang Y. et al.: Joint scheduling for optical grid applications. J. Opt. Netw. 6(3), 304-18 (2007). doi:10.1364/JON.6.000304 CrossRef
  4. Liu, X., et al.: Task scheduling and lightpath establishment in optical grids. In: The 27th IEEE International Conference on Computer Communications, INFOCOM 2008, Arizona, USA pp. 1966-974, April 13-7, 2008
  5. Guo, W., et al.: Resource allocation strategies for data-intensive workflow-based applications in optical grids. In: Tenth IEEE International Conference on Communication Systems, ICCS 2006, Singapore, pp. 101-06, 30 Oct.- Nov. 2006
  6. Ahmad I., Kwok Y.-K.: On exploiting task duplication in parallel program scheduling. IEEE Trans. Parall. Distr. Syst. 9(8), 872-92 (1998). doi:10.1109/71.722221 CrossRef
  7. Ahmad, I., Kwok, Y.-K., Wu, M.-Y.: Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors. In: Proceedings of the Second International Symposium on Parallel Architectures, Algorithms, and Networks, pp. 207-13, June 1996
  8. Gerasoulis A., Yang T.: A comparison of clustering heuristics for scheduling DAGs on multiprocessors. J. Parall. Distr. Comput. 16(4), 276-91 (1992). doi:10.1016/0743-7315(92)90012-C CrossRef
  9. Hou E.S.H., Ansari N., Ren H.: Genetic algorithm for multiprocessor scheduling. IEEE Trans. Parall. Distr. Syst. 5(2), 113-20 (1994). doi:10.1109/71.265940 CrossRef
  10. Hwang J.J., Chow Y.C., Anger F.D., Lee C.Y.: Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18(2), 244-57 (1989). doi:10.1137/0218016 CrossRef
  11. Kalinowski T., Kort I., Trystram D.: List scheduling of general task graphs under LogP. Parall. Comput. 26, 1109-128 (2000). doi:10.1016/S0167-8191(00)00031-4 CrossRef
  12. Kruatrachue, B.: Static task scheduling and grain packing in parallel processing systems. Ph.D. thesis, Oregon State Univ. (1987)
  13. Kwok Y.-K., Ahmad I.: Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J. Parall. Distr. Comput. 47(1), 58-7 (1997). doi:10.1006/jpdc.1997.1395 CrossRef
  14. Kwok, Y.-K., Ahmad, I.: Benchmarking the task graph scheduling algorithms. In: Proceedings of the Symposium on Parallel and Distributed Processing, Florida, USA, pp. 531-37, March 30–Apr. 3, 1998
  15. Wu M.Y., Gajski D.D.: Hypertool: a programming aid for message-passing systems. IEEE Trans. Parall. Distr. Syst. 1(3), 330-43 (1990). doi:10.1109/71.80160 CrossRef
  16. Yang, T., Gerasoulis, A.: PYRROS: static scheduling and code generation for message passing multiprocessors. In: Sixth ACM International Conference on Supercomputing, Mannheim, Germany, pp. 428-37, Aug. 1992
  17. Sinnen O., Sousa L.A.: List scheduling: extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures. Parall. Comput. 30(1), 81-01 (2004). doi:10.1016/j.parco.2003.09.002 CrossRef
  18. Sinnen O., Sousa L.: Communication contention in task scheduling. IEEE Trans. Parall. Distr. Syst. 16(6), 503-15 (2005). doi:10.1109/TPDS.2005.64 CrossRef
  19. Sinnen O., Sousa L.: On task scheduling accuracy: evaluation methodology and results. J. Supercomput. 27(2), 177-94 (2004). doi:10.1023/B:SUPE.0000009321.92150.64 CrossRef
  20. Takefusa, A., et al.: A study of deadline scheduling for client-server systems on the computational grid. In: The 10th IEEE International Symposium on High Performance Distributed Computing, California, USA, pp. 406-15, Aug. 3-, 2001
  21. Afzal, A., et al.: QoS-Constrained stochastic workflow scheduling in enterprise and scientific grids. In: The 7th IEEE/ACM International Conference on Grid Computing, GRID 2006, Barcelona, Spain, Sep. 28-9, 2006
  22. Sinnen O., et al. Toward a realistic task scheduling model. IEEE Trans. Parall. Distr. Syst. 17(3), (2006). doi:10.1109/TPDS.2006.40
  23. Banerjee, A., et al.: Algorithms for integrated routing and scheduling for aggregating data from distributed resources on a lambda grid. IEEE Trans. Parall. Distr. Syst. 19(1), (2008). doi:10.1109/TPDS.2007.1112
  24. Guo, W., et al.: Distributed computing over optical network (invited paper). In: Optical Fiber Communication Conference, OFC 2008, Feb. 24-8, San Diego, California, USA
  25. Mannie, E., et al.: Generalized multi-protocol label switching (GMPLS) architecture. IETF 3945, 2001
  26. Wang, Z., et al.: Demonstration of a task-flow based aircraft collaborative design application in optical grid. In: 33th European Conference on Optical Communication, ECOC 2007, Sep. 16-0, Berlin, Germany
  27. Allcock, B., et al.: GridFTP: a data transfer protocol for the grid. Grid Forum Data Working Group on GridFTP, http://www.ggf.org
  28. Generalized Multi-Protocol Label Switching (GMPLS) Signaling Resource ReserVation Protocol-Traffic Engineering (RSVP-TE) Extensions. http://www.faqs.org/rfcs/rfc3473.html, RFC 3473 (2003)
  
• 作者单位：Wei Guo (1)
  Zhengyu Wang (1)
  Zhenyu Sun (1)
  Weiqiang Sun (1)
  Yaohui Jin (1)
  Weisheng Hu (1)
  Chunming Qiao (2)
  
  1. State Key Lab on Fiber-Optic Local Area Networks and Advanced Optical Communication Systems, Shanghai Jiao Tong University, Shanghai, 200240, People’s Republic of China
  2. Computer Science & Engineering, State University of New York at Buffalo, New York, NY, 14260, USA
  
• ISSN：1572-8188

文摘

Currently optical networks have been employed to meet the ever-increasing data transfer demands of grid applications and thus give rise to the concept of an “optical grid- Task scheduling is an important issue for an optical grid, for it optimally allocates both grid and optical network resources to accelerate application execution and increase the resource utilization ratio. However, most task scheduling algorithms based on theoretical models may generate accuracy deviations between the scheduled results and the actual finish time of the applications. Accuracy deviations may lead to inefficient resources utilization and unsatisfied Quality of Service (QoS). This paper aims to improve the accuracy of task scheduling algorithms in optical grid environments. We first propose the theoretical task scheduling algorithm and demonstrate that the scheduling result is deviated with actual finish time in the real optical grid environment. Then, we reveal several factors which are likely to influence scheduling accuracy and develop a realistic task scheduling algorithm. We evaluate the theoretical and realistic task scheduling algorithms in our optical grid testbed. The experimental result shows the scheduling accuracy can be improved significantly by the realistic task scheduling algorithm.