An Efficient Hybrid Approach Based on the ACO and CLA for Static Task-Graph Scheduling in Homogeneous Multiprocessor Environments

Author

Sama Technical and Vocational College, Islamic Azad University, Shoushtar Branch, Shoushtar, Iran

Abstract

Task scheduling has been so far of important challenges in high-performance computers e.g. parallel and distributed systems. Using such architectures during compiling, each application program is divided to some tasks. Because of data-flow among the tasks, they may be dependent to one another; hence, there will be precedence constraints and communication delays among them so that each application with its corresponding tasks can be modeled using a Directed Acyclic Graph (DAG) named task graph. In static task-graph scheduling in homogeneous multiprocessor environments, tasks in the given task graph should be mapped to a predefined number of identical processing elements regarding the precedence constraints and communication delays so that the program’s completion time (finish time) is minimized, and this is an NP-hard problem form the time-complexity perspective. Actually, the achieved results are dominated by two different-in-nature factors: 1) which topological order of tasks should be considered? (sequencing subproblem), and 2) how should the extracted order be distributed over the processors? (assigning subproblem). In this paper, an efficient hybrid approach is proposed in which the Ant Colony Optimization (ACO) determines the order of tasks, and a Cellular Learning Automata (CLA) machine tackles with the assigning subproblem, and maps the task order derived by ACO to the existing processors. 125 randomly-generated task graphs with different shape parameters such as size, Communication-to-Computation Ratio (CCR), and parallelism are used for the comparison study, and the results shows that the proposed approach is more successful than the traditional counterparts from the performance point of view, and eventually outperforms them.

Keywords

References

[1]. س. پارسا، ش. لطفی و ن. لطفی، «رویکردی مبتنی بر پردازش تکاملی برای زمانبندی گراف وظایف در معماری چندپردازنده‌ای»، یازدهمین کنفرانس بین‌المللی کامپیوتر ایران، صفحات 627-634، تهران، 1384.
[2]. م. سلمانی، م. زالی و م. مقیمی، «زمانبندی وظایف سیستم‌های چندپردازنده‌ای با کمک یادگیری تقویتی و الگوریتم ژنتیک»، دوازدهمین کنفرانس بین‌المللی کامپیوتر ایران، صفحات 1948-1951، تهران، 1385.
[3]. م. عبدیزدان و ا. رحمانی، «زمانبندی کارها در سیستم‌های چندپردازنده‌ای با استفاده از یک الگوریتم جدید اولویت بر اساس تعداد فرزندان»، سیزدهمین کنفرانس بین‌المللی کامپیوتر ایران، کیش، 1386.
[4]. مصطفی ماهی و پریسا امین نژاد، «الگوریتم ژنتیک ترکیبی زمانبندی گراف وظایف در معماری چند پردازنده ای»، چهارمین کنفرانس مهندسی برق و الکترونیک ایران، گناباد، دانشگاه آزاد اسلامی واحد گناباد، ۱۳۹۱.
[5]. هادی لطفی و بابک آقامحمدی، «زمانبندی گراف وظایف در سامانه های چند پردازنده ای ناهمگن با استفاده از الگوریتم ژنتیک دانه درشت»، همایش مشترک مهندسی کامپیوتر و مکانیک، میاندوآب، دانشگاه جامع علمی و کاربردی مرکز میاندوآب، ۱۳۹۲.
[6].    P. Chretienne and et al., Scheduling Theory and Its Application, Wiley, New York, 1995.
[7].    Y. Kwok and I. Ahmad, Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors, Final report, Hong Kong Research Grants Council, Report No.: HKUST 734/96E and HKUST 6076/97E, Hong Kong, 1998.
[8].    I. Ahmad and Y. Kwok, “On Parallelizing the Multiprocessor Scheduling Problem,” IEEE Trans. Parallel Distrib. Syst., vol. 10, no. 8, pp. 795-18, 1999.
[9].    CH. Papadimitriou and M. Yannakakis, “Scheduling Interval-Ordered Tasks,” SIAM J. Computing, vol. 8, pp. 405-5, 1979.
[10]. B. Kruatrachue and TG. Lewis, Duplication Scheduling Heuristics (DSH): A New Precedence Task Scheduler for Parallel Processor Systems, Final report, Oregon State University, Report No.: OR 97331, Corvallis, 1987.
[11]. JY. Colin and P. Chretienne, “C.P.M. Scheduling with Small Computation Delays and Task Duplication,” Operations Research, vol. 39, no. 4, pp. 680-5, 1991.
[12]. YC. Chung and S. Ranka “Application and Performance Analysis of a Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed-Memory Multiprocessors,” In: Proceeding of the IEEE/ACM conference on Supercomputing, pp. 512-10, Nov. 1992.
[13]. H. Chen, B. Shirazi and J. Marquis, “Performance Evaluation of A Novel Scheduling Method: Linear Clustering with Task Duplication,” In: Proceeding of the Int’l Conf. Parallel and Distributed Systems, pp. 270-6, Dec. 1993.
[14]. I. Ahmad and YK. Kwok, “On Exploiting Task Duplication in Parallel Program Scheduling,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 9, pp. 872-21, 1998.
[15]. MA. Palis, JC. Liou and DSL. Wei, “Task Clustering and Scheduling for Distributed Memory Parallel Architectures,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 1, pp. 46-10, 1996.
[16]. GL. Park, B. Shirazi and J. Marquis, “DFRN: A New Approach for Duplication Based Scheduling for Distributed Memory Multiprocessor Systems,” In: Proceeding of the 11th Int’l IEEE Symposium on Parallel Processing, pp. 157-10, Apr. 1997.
[17]. SJ. Kim and JC. Browne, “A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures,” In: Proceeding of the 1988 Int’l Conference on Parallel Processing, vol. 2, pp. 1-8, Aug. 1988.
[18]. V. Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge (MA), 1989.
[19]. MY. Wu and DD. Gajski, “Hypertool: A Programming Aid for Message-Passing Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 1, no. 3, pp. 330-14, Jul. 1990.
[20]. T. Yang and A. Gerasoulis, “List Scheduling with and without Communication Delays,” Parallel Computing, vol. 19, pp. 1321-24, 1993.
[21]. YK. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 5, pp. 506-16, May 1996.
[22]. TL. Adam, KM. Chandy and J. Dickson, “A Comparison of List Scheduling for Parallel Processing Systems,” Comm. ACM, vol. 17, no. 12, pp. 685-16, Dec. 1974.
[23]. C. McCreary and H. Gill, “Automatic Determination of Grain Size for Efficient Parallel Processing,” Comm. ACM, vol. 32, pp. 1073-6, Sep. 1989.
[24]. J. Baxter and JH. Patel, “The LAST Algorithm: A Heuristic-Based Static Task Allocation Algorithm.,” In: Proceeding of the 1989 Int’l Conf. Parallel Processing, vol. II, pp. 217-6, Aug. 1989.
[25]. JJ. Hwang and et al., “Scheduling Precedence Graphs in Systems with Interprocessor Communication Times,” SIAM J. Computing, vol. 18, no. 2, pp. 244-14, 1989.
[26]. GC. Sih and EA. Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures,” IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 2, pp. 75-13, 1993.
[27]. R. Hwang, M. Gen and H. A. Katayama, “Comparison of multiprocessor task scheduling algorithms with communication costs,” Computer & Operations Research, vol. 35, pp. 976-18, 2008.
[28]. M. Dorigo, G. DiCaro and L. Gambardella, “Ant Algorithm for Discrete Optimization,” Artificial Life, vol. 5, no. 2, pp. 137-36, 1999.
[29]. S. Wolfram, “Cellular Automata,” Los Alamos Science, vol. 9, pp. 2-21, 1983.
[30]. K. S. Narendra and M. A. L. Thathachar, “Learning Automata: A Survey,” IEEE Trans. Syst., Man, Cybern., vol. SMC-14, pp. 323–12, 1974.
[31]. M. A. L. Thathachar and P. S. Sastry, “Varieties of Learning Automata: An Overview,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 32, no. 6, pp. 711–12, Dec. 2002.
[32]. M. R. Meybodi, H. Beigy and M. Taherkhani, “Cellular Learning Automata and Its Applications,” Journal of Science and Technology of Sharif University, vol. 25, pp. 54-24, 2004.
[33]. H. Beigy and M. R. Meybodi, “Cellular Learning Automata With Multiple Learning Automata in Each Cell and Its Applications,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 40, no. 1, pp. 54-12, Feb. 2010.
[34]. M. Asnaashari and M. R. Meybodi, “Irregular Cellular Learning Automata and Its Application to Clustering in Cellular Networks,” In: Proc. 15th Conf. on Electrical Engineering, vol. on Communication, pp. 14-15, Tehran, May 2007.
[35]. MA. Al-Mouhamed, “Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs,” IEEE Trans. Software Engineering, vol. 16, no. 12, pp. 1390-12, Dec. 1990.
[36]. A. Al-Maasarani, Priority-Based Scheduling and Evaluation of Precedence Graphs with Communication Times, M.S. Thesis, King Fahd University of Petroleum and Minerals, Saudi Arabia, 1993.
[37]. H. R. Boveiri, “Task Assigning Techniques for List-Scheduling in Homogeneous Multiprocessor Environments: A Survey,” International Journal of Software Engineering and Its Applications (IJSEIA), vol. 9, no. 12, pp. 303-10, Dec. 2015.
[38]. H. R. Boveiri, “An Efficient Task Priority Measurement for List-Scheduling in Multiprocessor Environments,” International Journal of Software Engineering and Its Applications (IJSEIA), vol. 9, no. 5, pp. 233-14, May 2015.
Journal of Soft Computing and Information Technology
Volume 5, Issue 3 - Serial Number 3
January 2017
Pages 35-54

Files

Share

How to cite

Statistics