Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userScheduling independent Tasks on homogenous multiprocessors using Bees Algorithm
جدولة مهام مستقلة على معالجات متعددة متماثلة باستخدام خوارزمية النحل
2729
2 187
0
(
0
)
Created by
Shamra Editor
Ask ChatGPT about the research
تعتبر جدولة المهام على المعالجات-المتعددة من أهم المسائل المدروسة لجعل المعالجات تعمل من دون أزمنة تأخير، و بالتالي تقليل الزمن الكمي اللازم لإتمام المهام. هذا الأمر جعل الاهتمام يتركز على مسألة الجدولة و خوارزمياتها، و خاصة في أنظمة المعالجات المتعددة التي تحتاج لترتيب المهام عمليا من أجل تنفيذها بشكل أمثل. في هذا البحث، تمت دراسة مسألة الجدولة الستاتيكية لمهام المستقلة على نظام معالجات-متعدد متماثلة، و عرض خوارزمية اعتماداً على أمثة جماعة النحل، و حل مسألة الجدولة باستخدامها، و مقارنتها مع خوارزمية سابقة قد استوحيت من سلوك النحل لنفس الغرض و مع الحل الأمثل لمسألة الجدولة المعروضة. إن الهدف من الخوارزمية هو إيجاد حل مقبول ذي زمن أصغريّ من خلال خوارزمية جماعة النحل، و دراسة تأثير زيادة عدد المهام عند ثبات عدد المعالجات، و تأثير زيادة عدد هذه المعالجات-من أجل عدد من المهام-على ثبات الخوارزمية المعروضة. لقد أوضحت دراسة الخوارزمية المفروضة قدرتها على الحصول على قيمة مثلى لدالة الهدف في اختبارات مسائل جدولة ذات حجم صغير و متوسط. لقد بينت النتائج أن الخوارزمية المفروضة تنتج حلاً أمثل لمسألة الجدولة في أغلب الحالات، و تحسن الخوارزمية التقليدية لأمثلة جماعة النحل.
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.
References used
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
rate research
Read More
In this paper, 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
mentioned for the same purpose, and with the optimal solution for
the displayed scheduling Problem.
In this paper, we compare the performance of sporadic tasks scheduler algorithms on
a multi-core platform in order to determine the best algorithm in terms of a set of
parameters adopted by researchers in this field, which in turn gives us accurate
details
about the quality of such algorithms when applied to a set of sporadic tasks generated
according to uniformed Logarithmic probability distribution.
The simulation is done using Simso simulator, which proved the reliability of high
performance by the testimony of many researchers in this field, as it provides the
possibility of generating tasks according to specific probability distributions, and simulates
accurate details related to the characteristics of random tasks.
In this paper, we propose a new accurate and fast converging
independent component analysis algorithm.
Advanced Reservation (AR) is used to guarantee resource provisioning for many different types of
applications including workflows. This technique is still under a huge controversy in both Business and
Research communities because of its potentialit
y of reducing resource utilization. Most of the works
proposed in this domain suggest reservation for the whole workflow schedule, and on all available
resources at the same time, which worsen the problem of resource utilization.
Many solutions are introduced to improve resource utilization under advanced reservation through
generating relaxed and elastic reservation plans that local scheduling systems could modify to improve
utilization and decrease internal fragmentation. These solutions depend mainly on changing rigid AR,
which considered to be the most difficult kind of reservation, into relaxed and elastic ones through adding
extra time on the resulted schedule and then distributing it on all tasks of the workflow.
This paper presents a new autonomic algorithm (EWARP) for producing elastic reservation plans for
workflow applications which doesn’t add extra times. Instead, it depends on exploiting the timing gaps
produced by the different scheduling algorithms. The new algorithm use the technique of discovering
timing gaps, but modifies it, and adds to it to be used for producing an elastic reservation plan for
workflows. The results presented in this paper demonstrate how the proposed algorithm outperforms
existing works in the fields by a lower bound approximating 25%.This shows that (EWARP) algorithm
offer efficient and practical solutions for the problem of scheduling workflow applications under QoS
constrains.
The research presents molding and analytical study of several scheduling algorithms
types in real-time multiprocessor systems. The performance of three scheduling algorithms
have been analyzed : Earliest Deadline First Scheduling (EDF) , Least Laxi
ty First
Scheduling (LLF), and Earliest Deadline First until Zero Laxity Scheduling (EDZL). This
paper considers the scheduling of n periodic, independed, and preempted tasks with
implicit deadlines on a platform of m homogenous multiprocessor. It has compared in
terms of the load on the processor (processor's busyness) , the number of migrations, and
the number of preemptions and the number of times in which these algorithms did not
succeed in achieving the time limits for tasks where the latter is considered the most
important criterion in real time scheduling. It also considers scheduling growing task sets
of periodic tasks starting from 4 task set up to 64 task set, in order to study the effect of
increasing the number of tasks and processors also on the performance of the scheduling
algorithms. As a result of research, the strengths and weaknesses in the performance of
these three algorithms have presented. It is proposed the best type of real-time system to
apply each algorithm according to the strengths of its performance.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
