رهيافتي تركيبي مبتني بر الگوريتم بهينهسازي كلوني مورچه ها و اتوماتاي يادگير سلولي در حل مساله زمان بندي ايستاي كارها در سيستم هاي چندپردازنده اي همگن

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

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

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