Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Effects Of Parallelism Of Branch and Bound Algorithms In Improving It's Performances
دراسة تأثير موازاة خوارزميات التفرع و الحد (Bound & Branch) في تحسين أدائها
1983
0 39
0
(
0
)
Created by
Shamra Editor
Ask ChatGPT about the research
تستخدم خوارزميات التفرع و الحد (Bound and Branch) التي يرمز لها بـ B&B في حل مـسائل الأمثلة (الاستمثال) التوافقية التي تصنف درجة تعقيدها في الفئة hard-NP . و على الرغم من فعالية هذه الخوارزميات فقد بقي حجم المسائل التي تتمكن من حلها و البرهان على أمثلة الحـل محـدوداً بـسبب محدودية قدرات الحواسيب رغم تطورها الكبير. و مع ظهور البرمجة المتوازية و الحواسيب متعددة المعالجات فكر الباحثون بالاستفادة من قدرات هذه التقانات و الأجهزة في زيادة حجم المسائل المحلولة إلا أنه نجم عن الموازاة ثلاثة أنـواع مختلفـة مـن الشذوذ. يهدف هذا البحث إلى تقديم نموذج جديد لخوارزمية التفرع و الحد المتوازية يسمح بتحليـل فعاليـات الخوارزمية و يستند هذا النموذج إلى قواعد جديدة للاختيار بين العقد المتساوية التقويم بعد أن ثبت عجز قاعدة اختيار العقدة ذات التقويم الأفضل، كما نقوم بحساب حدود محكمة لكل قاعدة من القواعد و نبـرهن على إمكانية بلوغها، كما نقدم الشروط اللازمة و الكافية لظهور كل حالة من حالات الشذوذ النـاجم عـن موازاة الخوارزمية. درسنا و قارنا في هذا البحث النتائج الناجمة عن تجاهل بعض الفرضيات المستخدمة في خوارزميـات التفرع و الحد، و اقترحنا فضلاً عن ذلك استخدام النماذج غير المتزامنة للاستفادة القصوى من الإمكانيـات التي تقدمها البرمجة المتوازية.
The Branch and Bound algorithms which are refereed to as B & B are commonly used to solve NP - hard combinatorial optimization problems. Although these algorithms were efficient, the size of problems which can solved and proved the optimality of solution by these algorithms was limited, because of the limitation of computers capabilities although of it’s highly development. When the parallel programming 46 and Multiprocessors computers were appeared, the researcher thought to use the capabilities of these techniques and machines to increase the size of solved problems. Three main anomalies may occur when the parallelism is used. This research aimed to design a new model of Branch and Bound algorithms in order to analyze the performance. This model based on a new rule to choose the best node among the equal evaluation node. Tight bounds of each rules were computed and proved the ability to achieve it. Sufficient and necessary condition anomalous are given regarding the predisposition for each of the three classes of behavior. In this research, we discussed and compared the results of further relaxations on the assumptions used in branch and bound algorithms. We suggested using the asynchronous models to have the utmost benefit of the capabilities of parallel programming.
Artificial intelligence review:
Research summary
تتناول هذه الورقة البحثية تأثير البرمجة المتوازية على تحسين أداء خوارزميات الفرع والتحديد (Branch and Bound)، والتي تُستخدم لحل مشاكل التحسين التوافقي الصعبة (NP-hard). على الرغم من كفاءة هذه الخوارزميات، إلا أن حجم المشاكل التي يمكن حلها وإثبات مثالية الحلول كان محدودًا بسبب قدرات الحواسيب. مع ظهور البرمجة المتوازية والحواسيب متعددة المعالجات، فكر الباحثون في استخدام هذه التقنيات لزيادة حجم المشاكل المحلولة. تهدف هذه الدراسة إلى تصميم نموذج جديد لخوارزميات الفرع والتحديد لتحليل الأداء، حيث يعتمد النموذج على قاعدة جديدة لاختيار أفضل عقدة بين العقد ذات التقييم المتساوي. تم حساب الحدود الضيقة لكل قاعدة وإثبات القدرة على تحقيقها. تم تقديم الشروط الكافية والضرورية للأنماط الشاذة المتعلقة بالتحيز لكل من الفئات الثلاث للسلوك. ناقشت الدراسة وقيّمت نتائج التخفيفات الإضافية على الافتراضات المستخدمة في خوارزميات الفرع والتحديد، واقترحت استخدام النماذج غير المتزامنة للاستفادة القصوى من قدرات البرمجة المتوازية.
Critical review
دراسة نقدية: تقدم هذه الورقة البحثية إسهامًا مهمًا في تحسين أداء خوارزميات الفرع والتحديد من خلال استخدام البرمجة المتوازية. ومع ذلك، يمكن ملاحظة بعض النقاط التي قد تحتاج إلى مزيد من التوضيح أو التحسين. على سبيل المثال، قد يكون من المفيد تقديم أمثلة عملية أو تجارب تطبيقية توضح كيفية تطبيق النموذج المقترح في حالات واقعية. بالإضافة إلى ذلك، قد يكون من المفيد توضيح كيفية التعامل مع الأنماط الشاذة بشكل أكثر تفصيلًا وتقديم حلول عملية للتحديات التي قد تواجهها الخوارزميات في بيئات مختلفة. بشكل عام، تعتبر الدراسة خطوة جيدة نحو تحسين أداء الخوارزميات، ولكنها قد تستفيد من مزيد من التفاصيل والتطبيقات العملية لتعزيز نتائجها.
Questions related to the research
-
ما هي الأهداف الرئيسية لهذه الدراسة؟
تهدف الدراسة إلى تصميم نموذج جديد لخوارزميات الفرع والتحديد لتحليل الأداء، واستخدام البرمجة المتوازية لزيادة حجم المشاكل المحلولة، وتقديم الشروط الكافية والضرورية للأنماط الشاذة المتعلقة بالتحيز لكل من الفئات الثلاث للسلوك.
-
ما هي الفوائد المتوقعة من استخدام البرمجة المتوازية في خوارزميات الفرع والتحديد؟
تساعد البرمجة المتوازية في زيادة حجم المشاكل التي يمكن حلها وإثبات مثالية الحلول، مما يعزز من كفاءة الخوارزميات ويتيح التعامل مع مشاكل أكبر وأكثر تعقيدًا.
-
ما هي الأنماط الشاذة التي قد تحدث عند استخدام البرمجة المتوازية؟
تحدث ثلاثة أنماط شاذة رئيسية عند استخدام البرمجة المتوازية، وقد قدمت الدراسة الشروط الكافية والضرورية للتعامل مع هذه الأنماط.
-
ما هي الاقتراحات التي قدمتها الدراسة لتحسين أداء خوارزميات الفرع والتحديد؟
اقترحت الدراسة استخدام النماذج غير المتزامنة للاستفادة القصوى من قدرات البرمجة المتوازية، بالإضافة إلى تقديم قواعد جديدة لاختيار أفضل عقدة بين العقد ذات التقييم المتساوي.
References used
AKL, S. G. (1997).'' Parallel Computation Models And Methods'', Prentice Hall
Almasi, G. S., Gottlieb, A. (1994). ''Highly Parallel Computing'', The Benjamin Cummings Publishing Company, Inc
Aorts, E., Lenstra, J. K. (2003). ''Local Search In Combinatorial Optimization'', Princeton University Press
rate research
Read More
في المشكلة التي نعالجها, تحتاج شركة اتصالات إلى بناء مجموعة من الأبراج الخلوية لتوفير خدمة الاتصالات الخليوية للسكان في منطقة جغرافية. تم تحديد عدد من المواقع المحتملة لبناء الأبراج. يعتم اختيار هذه المواقع على عدة عوامل ، بما في ذلك مدى اتساق البرج
مع البيئة المحيطة وارتفاع التضاريس, تتمتع الأبراج بمدى تغطية ثابت ، وبسبب قيود الميزانية ، لا يمكن بناء سوى عدد محدود منها . بالنظر إلى هذه القيود ، ترغب الشركة في توفير تغطية لأكبر قدر ممكن من السكان, والهدف هو اختيار في أي من المواقع المحتملة يجب أن تقوم الشركة ببناء الأبراج.
إن المشكلة التي شرحناها يمكن نمذجتها لتصبح أحد أمثلة مشكلة 0/1 knapsack الشهيرة لذلك شرحنا في الحلقة مفهوم مشكلة 0/1 Knapsack والطرق المستخدمة في الحل, وتوسعنا في الشرح عن خوارزمية Branch and Bound كونها تعتبر أفضلها.
Computer networks have evolved considerably in the past few years of big increases
in mutual amounts of data across the network hand because of the increasing number of
interconnected devices, which can exchange data as part of the network and this
is what led
to the emergence of what is known as the problems of congestion Studies showed about
some of these problems that the largest reason is involved in the implementation of the
transmission rules, and this led to the urgent of multiple types of protocols in the computer
networks that needs to deal with different computer and communication systems, and
many other applications, which often causes errors at the level of the bit and level of the
packets, missing packets, duplicate packets, randomly received packets, and most
importantly the appeared congestion in the network.
This research aims to determine how to improve the performance of the network to
get rid of the congestion by using advantages of the algorithms used to avoid congestion
that may occur in the networks that rely TCP protocol . The goals of these algorithms is to
reach stability in the network by working to achieve the principle of package saving.
Also within this scope it has been studied, and compared some of the algorithms that
used to avoid congestion in general, without relying on a specific protocol or specific
service category.
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.
The sound is an essential component of multimedia, and due to the needto be used in
many life applications such as television broadcasting andcommunication programs, so it
was necessary for the existence of audio signal processing techniquessuch as
compressing,
improving, and noisereduction.
Data compression process aims to reduce the bit rate used, by doing encoding
information using fewer bits than the original representation for transmitting and storing.
By this process,the unnecessary information is determined and removed, that means it
gives the compressed information for useable compression, which we need as a
fundamental, not the minutest details.
This research aims to study how to process sound and musical signal. It's a process
that consists of a wide range of applications like coding and digital compression for the
effective transport and storage on mobile phones and portable music players, modeling and
reproduction of the sound of musical instruments and music halls and the harmonics of
digital music, editing digital music, and classification of music content, and other things.
This paper presents parallel computers architectures especially Superscalar
processors and Vector processors, building a simulator depending on the basic
characteristics for each architecture, the simulator simulates their mechanism of work
progra
mmatically at the aim of comparing the performance of the two architectures in
executing Data Level Parallelism (DLP) and Instruction Level Parallelism ILP.
The results shows that the effectiveness of executing instructions in parallel depends
significantly on choosing the appropriate architecture for execution, according to the type
of parallelism that can be applied to instructions, and the vector features in the vector
architecture achieve remarkable improvement in performance that cannot be ignored in
execution of DLP, simplify the code and reduce the number of instruction. The provided
simulator is a good core that can be developed and modified especially in the field of
education for the students of Computer Science and Engineering and the research field.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
