@article { author = {Boveiri, Hamid Reza}, title = {An Efficient Hybrid Approach Based on the ACO and CLA for Static Task-Graph Scheduling in Homogeneous Multiprocessor Environments}, journal = {Journal of Soft Computing and Information Technology}, volume = {5}, number = {3}, pages = {35-54}, year = {2016}, publisher = {Babol Noshirvani University of Technology}, issn = {2383-1006}, eissn = {2588-4913}, doi = {}, 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 = {Ant colony optimization (ACO),cellular learning automata (CLA),Meta-heuristics,multiprocessor task-graph scheduling,parallel and distributed systems}, title_fa = {رهیافتی ترکیبی مبتنی بر الگوریتم بهینه‌سازی کلونی مورچه‌ها و اتوماتای یادگیر سلولی در حل مساله زمانبندی ایستای کارها در سیستم‌های چندپردازنده‌ای همگن}, abstract_fa = {زمان­بندی کارها یکی از بزرگترین چالش‌ها در سیستم‌های چندپردازنده‌ای مانند سیستم‌های موازی و توزیع‌شده است. در این­گونه سیستم‌ها هر برنامه حین کامپایل به قطعات کوچکتری به نام کار شکسته می‌شود. کارها مستقل نیستند و قیود اولویت (تقدم و تاخر) بین آنها جریان دارد. بدین ترتیب، زمان لازم جهت اجرای کارها، قیود اولویت بین کارها و هزینه‌های ارتباطی بین آنها با استفاده از یک گراف جهت‌دار غیرحلقوی به نام گراف وظایف مدلسازی می‌شود. کارهای یک برنامه باید به تعداد از پیش مشخصی پردازنده به گونه‌ای نگاشت شوند که قیود اولویت بین کارها رعایت شده و زمان اتمام کل کارها (خاتمه برنامه) حداقل شود. این مساله از جمله مسایل بغرنج زمانی (NP-hard) بوده و به­دست آوردن بهترین زمان­بندی ممکن با افزایش ابعاد مساله عموماً غیرممکن است؛ لذا اعمال روش‌های اکتشافی و فوق‌اکتشافی مختلف جهت حل این مساله و در راستایِ یافتن جواب­های شبه­بهینه منطقی است.  دو فاکتور اصلی، طول زمان­بندی به­دست‌آمده از رهیافت‌های مختلف ارائه­شده جهت حل این مساله را تحت شعاع قرار می‌دهد. اول اینکه کارها به چه ترتیبی جهت اجرا انتخاب شوند (زیرمساله ترتیب) و دوم اینکه ترتیب انتخاب‌شده چگونه بر روی پردازنده‌ها پخش شود (زیرمساله انتساب). در رهیافت پیشنهادی، الگوریتم بهینه­سازی کلونی مورچه‌ها ترتیب اجرای کارها را مشخص کرده و اتوماتای یادگیر سلولی، ترتیب مشخص‌شده را روی پردازنده‌ها نگاشت می‌کند. جهت ارزیابی قسمت اول الگوریتم از شش گراف وظایف از برنامه­های واقعی استفاده می­شود که الگوریتم بهینه­سازی کلونی مورچه‌ها در تمامی موارد قادر به یافتن ترتیب اجرای بهینه­تری نسبت به روش­های سنتی موجود است. در قسمت دوم الگوریتم نیز نتایج به­دست‌آمده از اتوماتای یادگیر سلولی بهبود محسوسی نسبت به تنها رقیب سنتی خود یعنی روش کمترین زمان شروع ممکن (EST) دارد. در نهایت جهت ارزیابی عادلانه از 125 گراف وظایف تصادفی با پارامترهای ساختاری مختلف استفاده شده که نتایج حاکی از آن است که رهیافت پیشنهادی از نظر عملکرد در هر دو زمینه بسیار موفق‌تر از الگوریتم‌های سنتیِ موجود بوده و در نهایت از این روش‌ها پیشی می‌گیرد.   }, keywords_fa = {زمان‌بندی ایستای کارها,سیستم‌های موازی و توزیع‌شده,گراف وظایف,الگوریتم بهینه‌سازی کلونی مورچه‌ها,اتوماتای یادگیر سلولی}, url = {https://jscit.nit.ac.ir/article_51678.html}, eprint = {https://jscit.nit.ac.ir/article_51678_8315f33960e4205abe3270476bab83cd.pdf} }