رهیافتی ترکیبی مبتنی بر الگوریتم بهینه‌سازی کلونی مورچه‌ها و اتوماتای یادگیر سلولی در حل مساله زمانبندی ایستای کارها در سیستم‌های چندپردازنده‌ای همگن

نویسنده

آموزشکده فنی و حرفه ای سما، دانشگاه آزاد اسلامی، واحد شوشتر، شوشتر، ایران

چکیده

زمان­بندی کارها یکی از بزرگترین چالش‌ها در سیستم‌های چندپردازنده‌ای مانند سیستم‌های موازی و توزیع‌شده است. در این­گونه سیستم‌ها هر برنامه حین کامپایل به قطعات کوچکتری به نام کار شکسته می‌شود. کارها مستقل نیستند و قیود اولویت (تقدم و تاخر) بین آنها جریان دارد. بدین ترتیب، زمان لازم جهت اجرای کارها، قیود اولویت بین کارها و هزینه‌های ارتباطی بین آنها با استفاده از یک گراف جهت‌دار غیرحلقوی به نام گراف وظایف مدلسازی می‌شود. کارهای یک برنامه باید به تعداد از پیش مشخصی پردازنده به گونه‌ای نگاشت شوند که قیود اولویت بین کارها رعایت شده و زمان اتمام کل کارها (خاتمه برنامه) حداقل شود. این مساله از جمله مسایل بغرنج زمانی (NP-hard) بوده و به­دست آوردن بهترین زمان­بندی ممکن با افزایش ابعاد مساله عموماً غیرممکن است؛ لذا اعمال روش‌های اکتشافی و فوق‌اکتشافی مختلف جهت حل این مساله و در راستایِ یافتن جواب­های شبه­بهینه منطقی است.  دو فاکتور اصلی، طول زمان­بندی به­دست‌آمده از رهیافت‌های مختلف ارائه­شده جهت حل این مساله را تحت شعاع قرار می‌دهد. اول اینکه کارها به چه ترتیبی جهت اجرا انتخاب شوند (زیرمساله ترتیب) و دوم اینکه ترتیب انتخاب‌شده چگونه بر روی پردازنده‌ها پخش شود (زیرمساله انتساب). در رهیافت پیشنهادی، الگوریتم بهینه­سازی کلونی مورچه‌ها ترتیب اجرای کارها را مشخص کرده و اتوماتای یادگیر سلولی، ترتیب مشخص‌شده را روی پردازنده‌ها نگاشت می‌کند. جهت ارزیابی قسمت اول الگوریتم از شش گراف وظایف از برنامه­های واقعی استفاده می­شود که الگوریتم بهینه­سازی کلونی مورچه‌ها در تمامی موارد قادر به یافتن ترتیب اجرای بهینه­تری نسبت به روش­های سنتی موجود است. در قسمت دوم الگوریتم نیز نتایج به­دست‌آمده از اتوماتای یادگیر سلولی بهبود محسوسی نسبت به تنها رقیب سنتی خود یعنی روش کمترین زمان شروع ممکن (EST) دارد. در نهایت جهت ارزیابی عادلانه از 125 گراف وظایف تصادفی با پارامترهای ساختاری مختلف استفاده شده که نتایج حاکی از آن است که رهیافت پیشنهادی از نظر عملکرد در هر دو زمینه بسیار موفق‌تر از الگوریتم‌های سنتیِ موجود بوده و در نهایت از این روش‌ها پیشی می‌گیرد.   

کلیدواژه‌ها


[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.