Please wait a minute...
FITEE
Frontiers of Information Technology & Electronic Engineering  2017, Vol. 18 Issue (4): 498-510    DOI: 10.1631/FITEE.1500394
Regular Paper     
基于渐进式蚁群优化的多处理器任务分配
Hamid Reza Boveiri
An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling
Hamid Reza Boveiri
Sama Technical and Vocational Training College, Islamic Azad University, Shoushtar Branch, Shoushtar, Iran
 全文: PDF 
摘要： 概要：任务调度优化是多处理器环境（如并行和分布式系统）取得良好性能所面临的最重要挑战之一。目前大多数任务调度算法基于列表调度法，该方法的基本思路是，以列表的形式准备一系列待调度的节点，赋予这些节点不同优先级，然后不断去除列表中优先级最高的节点，并将其分配给具有最早开始时间（Earliest start ime,EST）的处理器。由此可见，该算法的完成时间主要由两大因素决定：（1）任务分配顺序的选择（次序子问题）；（2）选定顺序的任务如何分配给处理器（分配子问题）。已有文献提出了许多解决次序子问题的好办法，但分配子问题少有人涉及。本文研究结果显示：传统的按照最早开始时间分配任务的方法并非最优；基于蚁群优化算法，得到一种新的方法，可以获得高效得多的调度方案。
关键词： 蚁群优化;  列表调度;  多处理器任务图调度;  并行与分布式系统    
Abstract: Optimized task scheduling is one of the most important challenges to achieve high performance in multiprocessor environments such as parallel and distributed systems. Most introduced task-scheduling algorithms are based on the so-called list scheduling technique. The basic idea behind list scheduling is to prepare a sequence of nodes in the form of a list for scheduling by assigning them some priority measurements, and then repeatedly removing the node with the highest priority from the list and allocating it to the processor providing the earliest start time (EST). Therefore, it can be inferred that the makespans obtained are dominated by two major factors: (1) which order of tasks should be selected (sequence subproblem); (2) how the selected order should be assigned to the processors (assignment subproblem). A number of good approaches for overcoming the task sequence dilemma have been proposed in the literature, while the task assignment problem has not been studied much. The results of this study prove that assigning tasks to the processors using the traditional EST method is not optimum; in addition, a novel approach based on the ant colony optimization algorithm is introduced, which can find far better solutions.
Key words: Ant colony optimization    List scheduling    Multiprocessor task graph scheduling    Parallel and distributed systems
收稿日期: 2015-11-10 出版日期: 2017-04-12
CLC:  TP301  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Hamid Reza Boveiri

引用本文:

Hamid Reza Boveiri. An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 498-510.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1500394    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2017/V18/I4/498

1 Adam, T.L., Chandy, K.M., Dickson, J., 1974. A comparison of list scheduling for parallel processing systems. Commun. ACM, 17(12):685-700.
doi: 10.1145/361604.361619
2 Al-Maasarani, A., 1993. Priority-Based Scheduling and Evaluation of Precedence Graphs with Communication Times. MS Thesis, King Fahd University of Petroleum and Minerals, Saudi Arabia.
3 Al-Mouhamed, M.A., 1990. Lower bound on the number of processors and time for scheduling precedence graphs with communication costs. IEEE Trans. Softw. Eng., 16(12):1390-1401.
doi: 10.1109/32.62447
4 Baxter, J., Patel, J.H., 1989. The LAST algorithm: a heuristic-based static task allocation algorithm. Proc. Int. Conf. on Parallel Processing, p.217-222.
5 Boveiri, H.R., 2010. ACO-MTS: a new approach for multiprocessor task scheduling based on ant colony optimization. Proc. IEEE Int. Conf. on Intelligent and Advanced Systems, p.1-5.
doi: 10.1109/ICIAS.2010.5716203
6 Boveiri, H.R., 2014. Assigning tasks to the processors for task-graph scheduling in parallel systems using learning and cellular learning automata. Proc. 1st National Conf. on Computer Engineering and Information Technology, p.1-8 (in Farsi).
7 Boveiri, H.R., 2015. Multiprocessor task graph scheduling using a novel graph-like learning automata. Int. J. Grid Distr. Comput., 8(1):41-54.
doi: 10.14257/ijgdc.2015.8.1.05
8 Chrétienne, P., Coffman, E.G., Lenstra, J.K., et al., 1995. Scheduling Theory and Its Application. John Wiley & Sons, New York.
9 Dorigo, M., Maniezzo, V., Colorni, A., 1991. Positive Feedback as a Search Strategy. Technical Report No. 91-016, Politecnico di Milano, Milan, Italy.
10 Dorigo, M., di Caro, G., Gambardella, L., 1999. Ant algorithm for discrete optimization. Artif. Life, 5(2):137-172.
doi: 10.1162/106454699568728
11 Hwang, J.J., Chow, Y.C., Anger, F.D., et al., 1989. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput., 18(2):244-257.
doi: 10.1137/0218016
12 Hwang, R., Gen, M., Katayama, H., 2008. A comparison of multiprocessor task scheduling algorithms with communication costs. Comput. Oper. Res., 35(3):976-993.
doi: 10.1016/j.cor.2006.05.013
13 Kruatrachue, B., Lewis, T.G., 1987. Duplication Scheduling Heuristics (DSH): a New Precedence Task Scheduler for Parallel Processor Systems. Technical Report No. OR 97331, Oregon State University, Corvallis.
14 Kwok, Y., Ahmad, I., 1998. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv., 31(4):406-471.
doi: 10.1145/344588.344618
15 McCreary, C., Gill, H., 1989. Automatic determination of grain size for efficient parallel processing. Commun. ACM, 32(9):1073-1078.
doi: 10.1145/66451.66454
16 Meybodi, M.R., Beigy, H., Taherkhani, M., 2004. Cellular learning automata and its applications. J. Sci. Technol. Sharif Univ., 25:54-77 (in Farsi).
17 Narendra, K.S., Thathachar, M.A.L., 1974. Learning automata: a survey. IEEE Trans. Syst. Man Cybern., SMC-4(4): 323-334.
doi: 10.1109/TSMC.1974.5408453
18 Sih, G.C., Lee, E.A., 1993. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parall. Distr. Syst., 4(2):175-187.
doi: 10.1109/71.207593
19 Wolfram, S., 1983. Cellular automata. Los Alamos Sci., 9:2-27.
[1] Juan Yu, Pei-zhong Lu. AGCD：一种基于最大公因子逼近的鲁棒周期分析方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(6): 466-473.
[2] Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz. 非结构化异构多处理器系统中的动态任务调度建模[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(6): 423-434.
[3] Saeid Arish, Ali Amiri, Khadije Noori. FICA: fuzzy imperialist competitive algorithm[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(5): 363-371.
[4] Li-wei Huang, Gui-sheng Chen, Yu-chao Liu, De-yi Li. Enhancing recommender systems by incorporating social information[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(9): 711-721.
[5] Reza Rezaei, Thiam-kian Chiew, Sai-peck Lee. A review of interoperability assessment models[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(9): 663-681.
[6] Jorge A. Ruiz-Vanoye, Joaquín Pérez-Ortega, Rodolfo A. Pazos Rangel, Ocotlán Díaz-Parra, Héctor J. Fraire-Huacuja, Juan Frausto-Solís, Gerardo Reyes-Salgado, Laura Cruz-Reyes. Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(8): 623-633.
[7] Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song. A membrane-inspired algorithm with a memory mechanism for knapsack problems[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(8): 612-622.
[8] Mo-fei Song, Zheng-xing Sun, Yan Zhang, Fei-qian Zhang. Synthesis of 3D models by Petri net[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(7): 521-529.
[9] Suiang-Shyan Lee, Ja-Chen Lin. An accelerated K-means clustering algorithm using selection and erasure rules[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(10): 761-768.
[10] Ommolbanin Yousefi, Mirbahadorgholi Aryanezhad, Seyed Jafar Sadjadi, Arash Shahin. Developing a multi-objective, multi-item inventory model and three algorithms for its solution[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(8): 601-612.
[11] Alireza Askarzadeh, Alireza Rezazadeh. [J]. Frontiers of Information Technology & Electronic Engineering, 2011, 12(8): 638-646.
[12] Wei Wang, Peng-tao Zhang, Ying Tan, Xin-gui He. An immune local concentration based virus detection approach[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(6): 443-454.
[13] Xi-chuan Zhou, Hai-bin Shen, Jie-ping Ye. Integrating outlier filtering in large margin training[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(5): 362-370.