اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدجدولة مهام مستقلة على معالجات متعددة متماثلة باستخدام خوارزمية النحل
Scheduling independent Tasks on homogenous multiprocessors using Bees Algorithm
2725
2 187
0
(
0
)
تمت اﻹضافة من قبل
Shamra Editor
اسأل ChatGPT حول البحث
تعتبر جدولة المهام على المعالجات-المتعددة من أهم المسائل المدروسة لجعل المعالجات تعمل من دون أزمنة تأخير، و بالتالي تقليل الزمن الكمي اللازم لإتمام المهام. هذا الأمر جعل الاهتمام يتركز على مسألة الجدولة و خوارزمياتها، و خاصة في أنظمة المعالجات المتعددة التي تحتاج لترتيب المهام عمليا من أجل تنفيذها بشكل أمثل. في هذا البحث، تمت دراسة مسألة الجدولة الستاتيكية لمهام المستقلة على نظام معالجات-متعدد متماثلة، و عرض خوارزمية اعتماداً على أمثة جماعة النحل، و حل مسألة الجدولة باستخدامها، و مقارنتها مع خوارزمية سابقة قد استوحيت من سلوك النحل لنفس الغرض و مع الحل الأمثل لمسألة الجدولة المعروضة. إن الهدف من الخوارزمية هو إيجاد حل مقبول ذي زمن أصغريّ من خلال خوارزمية جماعة النحل، و دراسة تأثير زيادة عدد المهام عند ثبات عدد المعالجات، و تأثير زيادة عدد هذه المعالجات-من أجل عدد من المهام-على ثبات الخوارزمية المعروضة. لقد أوضحت دراسة الخوارزمية المفروضة قدرتها على الحصول على قيمة مثلى لدالة الهدف في اختبارات مسائل جدولة ذات حجم صغير و متوسط. لقد بينت النتائج أن الخوارزمية المفروضة تنتج حلاً أمثل لمسألة الجدولة في أغلب الحالات، و تحسن الخوارزمية التقليدية لأمثلة جماعة النحل.
Scheduling tasks on multiprocessors is considered one of the most important issues studied to make processors operate without inertia (idleness) and thus to reduce the total time of completion or makespan. This increased interest in studying scheduling and its algorithms, especially in multiprocessor systems that need to arrange the tasks to been optimally implemented. In this research, we study the static scheduling issue for the independent tasks on a homogenous multiprocessor system. In addition, we develop an algorithm based on Bees Colony Optimization to solve the scheduling Problem. Thereafter, our algorithm is compared with a previous one inspired also by the bees behavior for the same purpose, and the optimal solution for the displayed scheduling Problem. The aim of the algorithm is to find an acceptable solution with the best time through Bees Colony's algorithm. To evaluate our reach, we Study the effect of increasing the number of tasks when processors numbers are constant, and the impact of increasing the number of processors for a number of tasks on the stability of the presented algorithm. Our algorithm has shown the ability to obtain optimal value for the objective function in terms of scheduling tests for small and medium size. Our results shown that the imposed algorithm gives the best solution for the scheduling problem, in most cases, and improves the traditional BCO algorithm.
المراجع المستخدمة
G. BENI, 1988. “The concept of cellular robotic system,” in Proc. of the IEEE International Symposium on Intelligent Control, IEEE Computer Society Press, Los Alamitos, CA , pp. 57–62
G. BENI, AND J. WANG, 1989. “Swarm intelligence,” in Proc. of the Seventh Annual Meeting of the Robotics Society of Japan, RSJ Press, Tokyo, pp. 425–428
G. BENI, AND S. HACKWOOD, 1992. “Stationary waves in cyclic swarms,” in: Proc. of the International Symposium on Intelligent Control, IEEE Computer Society Press, Los Alamitos, CA, pp. 234–242
E. BONABEAU, M. DORIGO, AND G. THERAULAZ, 1997. Swarm intelligence. Oxford University Press, Oxford
S. CAMAZINE, AND J. SNEYD, 1991. “A model of collective nectar source by honey bees: self-organization through simple rules,” Journal of Theoretical Biology, vol. 149, pp. 547- 571
قيم البحث
اقرأ أيضاً
في هذا البحث، تمت دراسة مسألة الجدولة الستاتيكية للمهام المستقلة على نظام
معالجات-متعدد متماثلة، و عرض خوارزمية اعتماداً على أمثلة جماعة النحل، و حل
مسألة الجدولة باستخدامها، و مقارنتها مع خوارزمية سابقة قد استوحيت من سلوك النحل
لنفس الغرض و مع الحل الأمثل لمسألة الجدولة المعروضة.
تم في هذا البحث مقارنة أداء خوارزميات جدولة المهام العشوائية على منصة متعددة النوى بهدف تحديد الخوارزمية الأفضل من ناحية مجموعة من البارامترات المعتمدة من قبل الباحثين في هذا المجال و التي بدورها تعطينا تفاصيل دقيقة حول جودة مثل هذه الخوارزميات عند ت
طبيقها على مجموعة من المهام العشوائية المولدة وفق التوزع الاحتمالي اللوغاريتمي الموحد.
تمت عملية المحاكاة على البرنامج simso و الذي أثبت موثوقية أداء عالية بشهادة العديد من الباحثين في هذا المجال فضلاً عن كونه يقدم إمكانية توليد المهام وفق توزعات احتمالية معينة، و يحاكي تفاصيل دقيقة متعلقة بخصائص المهام العشوائية.
نقدم في هذه الورقة البحثية خوارزمية جديدة في تحليل المركبات المستقلة تتميز بدقتها في فصل المنابع إلى جانب تقاربها السريع.
تستخدم تقنية الحجز المسبق لضمان تزويد الموارد عند الطلب للأنواع المختلفة من التطبيقات و منها دفق الأعمال. ما زالت هذه التقنية مثار جدل واسع في المجتمع البحثي و الأعمال لإمكانيتها تخفيض استغلالية الموارد. قُدمت عدة حلول لتحسين استغلالية الموارد تحت ال
حجز المسبق عن طريق توليد حجوزات مرنة و قابلة للتعديل من قبل الإدارة المحلية للموارد، مما يمكنها من تحسين استغلالية مواردها و خفض التجزئة الداخلية فيها. تعمل موّلدات مخططات الحجز المرن على تحويل المهمات ذات الحجز المسبق
القاسي، التي تعد من أصعب أنواع الحجز، إلى مهمات ذات حجز مسبق مرتخ، أو مرن؛ و لكن تعتمد معظم الأعمال المقدمة في هذا المجال على إضافة زمن محدد إلى طول المجدول الناتج، و من ثم توزيع هذا الزمن على المهمات المشكلة للدفق.
تقدم هذه الورقة خوارزمية جديدة مستقلة لتوليد مخطط حجز مسبق مرن لمهمات دفق الأعمال دون أية إضافات زمنية؛ بل تعتمد على الاستغلال الأمثلي للفجوات الزمنية الموجودة في مجدولات دفق الأعمال. تستخدم هذه الخوارزمية تقنية استطلاع الفجوات الزمنية في المجدول الناتج، و لكنها تضيف إليها و تعدلها لتستعمل مع تخطيط الحجز المرن. أظهرت نتائج اختبار هذه الخوارزمية تقدمها على الخوارزميات الأخرى الموجودة في هذا المجال بمقدار حد أدنى يقارب 25 %؛ و هي تقدم بذلك حلولاً كفوءة و عملية لجدولة تطبيقات دفق الأعمال المتطلبة لقيود جودة الخدمة.
يقدم البحث نمذجة و تحليل أداء عدد من خوارزميات الجدولة في أنظمة الزمن الحقيقي متعددة المعالجات. حيث تم تحليل أداء كل من الخوارزميات الثلاث: خوارزمية الجدولة بالزمن الحرج الأقصر أولاً EDF ، و خوارزمية الجدولة بالزمن الأقل خمولاً أولاً LLF ، و خوارزمية
الجدولة بالزمن الحرج أولاً عند الخمول الصفري EDZL . شملت هذه الدراسة جدولة مهام دورية ذات قيود زمنية مساوية لدورها ، و مستقلة، و قابلة للمقاطعة على عدة معالجات متطابقة . تمت مقارنة الخوارزميات الثلاث من ناحية الحمل على المعالج (مشغولية المعالجات)، و من ناحية عدد الهجرات، و عدد المقاطعات، و عدد المرات التي لم تنجح فيها هذه الخوارزميات في تحقيق الحدود الزمنية للمهام، حيث يعتبر الأخير أهم معيار من معايير عملية الجدولة في الزمن الحقيقي. كما تضمنت الدراسة جدولة مجموعات متزايدة من المهام الدورية تبدأ من 4 مهام لتصل حتى 64 مهمة ، و ذلك لدراسة تأثير ازدياد عدد المهام و المعالجات على أداء خوارزميات الجدولة، و كنتيجة يقدم البحث نقاط القوة و الضعف في أداء هذه الخوارزميات و يقترح لكل خوارزمية - حسب نقاط القوة في أدائها- نوع منظومة الزمن الحقيقي التي من الأفضل تطبيقها فيها.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
