Abstract
In this paper, we present a novel approach to designing cellular automata-based multiprocessor scheduling algorithms in which extracting knowledge about the scheduling process occurs. This knowledge can potentially be used while solving new instances of the scheduling problem. We consider the simplest case when a multiprocessor system is limited to two-processors, but we do not imply any limitations on the size and parameters of parallel programs. To design cellular automata corresponding to a given program graph, we propose a generic definition of program graph neighborhood, transparent to the various kinds, sizes, and shapes of program graphs. The cellular automata-based scheduler works in two modes. In learning mode we use a genetic algorithm to discover rules of cellular automata suitable for solving instances of a scheduling problem. In operation mode, discovered rules of cellular automata are able to automatically find an optimal or suboptimal solution of the scheduling problem for any initial allocation of a program graph in two-processor system graph. Discovered rules are typically suitable for sequential cellular automata working as a scheduler, while the most interesting and promising feature of cellular automata are their massive parallelism. To overcome difficulties in evolving parallel cellular automata rules, we propose using coevolutionary genetic algorithm. Discovered this way, rules enable us to design effective parallel schedulers. We present a number of experimental results for both sequential and parallel scheduling algorithms discovered in the context of a cellular automata-based scheduling system
چكيده
در اين مقاله، ما رويكرد جديدي براي طراحي ماشين‌هاي خودكار سلولي مبتني بر الگوريتم‌هاي زمان‌بندي چندپردازنده ارائه مي‌كنيم كه استخراج دانش در مورد فرايند زمان‌بندي رخ مي‌دهد. اين دانش به طول بالقوه مي‌تواند هنگام حل نمونه‌هاي جديد برنامه زمان‌بندي، مورد استفاده قرار گيرد. ما ساده‌ترين مورد را درنظر مي‌گيريم، هنگامي كه يك سيستم چندپردازنده به دو پردازنده محدود شده است، اما به هيچ گونه محدوديتي در خصوص اندازه و پارامترهاي برنامه هاي موازي، اشاره نمي‌كنيم. براي طراحي ماشين‌هاي خودكار سلولي متناظر با گراف برنامه موردنظر، ما تعريفي كلي از همسايگي گراف برنامه، شفاف براي انواع، اندازه‌ها و شكل‌هاي گراف‌هاي برنامه مختلف را درنظر مي‌گيريم. اين ماشين‌هاي خودكار سلولي مبتني بر زمان‌بند به دو روش كار مي‌كنند. در روش يادگيري ما از يك الگوريتم ژنتيكي براي كشف قوانين ماشين‌هاي خودكار سلولي مناسب چند حل نمونه‌هايي از برنامه زمان‌بندي، استفاده مي‌كنيم. در روش عملياتي، قوانين كشف شده ماشين‌هاي خودكار سلولي به طور اتوماتيك قادر يه يافتن راه‌حل بهينه يا زيربهينه مسئله زمان‌بندي براي هرگونه تخصيص اوليه يك گراف برنامه در گراف سيستم دوپردازنده‌اي، هستند. قوانين كشف شده به طور نوعي براي طرز كار ماشين‌هاي خودكار سلولي ترتيبي به عنوان زمان‌بند، مناسب هستند، درحالي كه جالب‌ترين و محتمل‌ترين ويژگي ماشين‌هاي خودكار سلولي، موازات بزرگ آنهاست. براي غلبه بر دشواري‌ها در استنتاج قوانين ماشين‌هاي خودكار موازي، ما استفاده از الگوريتم ژنتيك هم تكاملي را پيشنهاد مي‌كنيم. با كشف اين راه، قوانين ما را قادر به طراحي زمان‌بندهاي موازي مؤثر مي‌سازند. ما تعدادي از نتايج تجربي را براي الگوريتم‌هاي زمان‌بندي هم موازي و هم ترتيبي كه در زمينه ماشين خودكار سلولي مبتني بر سيستم زمان‌بندي كشف شده‌اند، ارائه مي‌كنيم.
عبارات كليدي:ماشين‌هاي خودكار سلولي، هم تكاملي، الگوريتم‌هاي ژنتيك، زمان‌بندي چندپردازنده، سيستم‌هاي دوپردازنده‌اي
1- مقدمه
تعداد زيادي از مسائل تحقيقاتي و كاربردهاي زندگي واقعي نياز به محاسبات موازي عظيمي دارند. هنوز مشخص نيست كه چگونه وسايل محاسباتي آينده ارائه كننده توان محاسباتي عظيم بالا، نگريسته خواهند شد. امروزه اميد بزرگ، تكنيك‌هاي محاسباتي غيراستاندارد بيوالقايي و طبيعي همچون، شبكه‌هاي عصبي، الگوريتم‌هاي ژنتيك يا گداختگي شبيه‌سازي شده، و ظهور پارادايم‌هاي (الگوهاي) محاسباتي جديد همچون، سيستم‌هاي ايمني، محاسبات مولكولي، محاسبه در ماشين‌هاي خودكار سلولي و محاسبات كوانتومي، هستند. مي‌توان به تعداد فزاينده انتشارات [7]، [14]، [19]، [37]، كارگاه‌ها و كنفرانس‌ها [4]، [8]، [11]، [24] اختصاص يافته به اين روش‌ها، توجه كرد.
جالب‌ترين يا نويدبخش ترين نجايت بدست آمده با استفاده از تكنيك‌هاي بيوالحاقي و گزارشات اخير، متعلق به كشف [3] قوانين مربوط به اكثريت مسئله دسته‌بندي است، كه بهتر از قوانين شناخته شده موجود انساني، در حل موفقيت‌آميز تعدادي از مسائل ارتباطاتي همچون كشف كلاهبرداري [5] در سيستم‌هاي موبايل- تلفن يا حمل مسائل مربوط به اقتصادهاي مالي همچون بهينه‌سازي مسئله سهام [16]، هستند. زمان‌بندي چندپردازنده متعلق به دسته ويژه‌اي از مسائل محاسباتي است. از يك طرف، رابطه نزديكي با موضوع عملكرد عملي كامپيوترهاي موجودي و آتي دارد. از طرف ديگر اين مسئله حتي محدود به ساده‌ترين مسئله مطرح شده در اين مقاله است، هنگامي كه ما بايد با سيستم دو پردازنده‌اي كار كنيم، اما هرگونه مسئله موازي، نمونه‌اي از دشواري محاسباتي يك مسئله تحقيقاتي حل نشده است كه به عنوان يك مسئله تكميل-NP شناخته شده است..