شماره ركورد كنفرانس :
4379
عنوان مقاله :
زمان‌بندي وظايف در سيستم هاي چندپردازنده اي با بهره گيري از الگوريتم جستجوي گردابي
پديدآورندگان :
زيادي مهرداد m.ziadi@qiau.ac.ir دانشگاه آزاد اسلامي، واحد قزوين، دانشكده مهندسي كامپيوتر و فناوري اطلاعات , ساجدي هديه hhsajedi@ut.ac.ir دانشكده رياضي آمار و علوم كامپيوتر، پرديس علوم دانشگاه تهران
كليدواژه :
الگوريتم جستجوي گردابي , زمان‌بندي وظايف , زودترين زمان شروع كارها , سيستم‌هاي چندپردازنده‌اي
عنوان كنفرانس :
هشتمين كنفرانس فناوري اطلاعات و دانش
چكيده فارسي :
امروزه سيستم هاي چندپردازنده اي كاربرد وسيعي در محاسبات موازي دارند. يك روش زمان‌بندي مناسب، در كاهش زمان اجراي وظايف و بهره وري منابع بسيار تأثيرگذار است. اين زمان‌بندي بايد به‌گونه‌اي انجام شود كه بتواند زمان لازم براي اجراي كل برنامه را با در نظر داشتن زمان اجراي وظايف و بيكاري پردازنده ها، كمينه نمايد. با توجه به NP كامل بودن مسئله زمان‌بندي گراف وظايف، رويكردهاي مبتني بر روش هاي قطعي در اين زمينه كارا نخواهد بود؛ بنابراين استفاده از الگوريتم هاي فرا مكاشفه‌اي و الگوريتم هاي تركيبي براي حل اين مسئله مؤثر خواهد بود لذا بهره گيري از الگوريتم جستجوي گردابي، روش مناسبي جهت زمان‌بندي در سيستم هاي چندپردازنده اي مي باشد. در اين مقاله، مسئله را به كمك روش تركيبي جديدي كه مبتني بر الگوريتم جستجوي گردابي است حل نموديم. روش تركيبي با در نظر گرفتن اولويت زمان‌بندي انجام كارها بر اساس زودترين زمان شروع كار و در نظر گرفتن اجراي والد خود و تركيب آن با الگوريتم جستجوي گردابي براي انتخاب بهترين جواب براي مسئله، مي تواند به‌طور مؤثري براي مسائل زمان‌بندي در اكثر محيط هاي موازي مورد استفاده قرار گيرد. نتايج حاصل شده نشان مي دهد الگوريتم پيشنهادي جواب بهينه ي زمان‌بندي را در مقايسه با ساير روش هاي متداول نتيجه مي دهد.
