22498

طراحي و شبيه‌سازي الگوريتم نگاشت و زمان‌بندي بهينه وظايف در سيستم‌هاي چند پردازنده‌اي

كارشناسي ارشد

سيستم‌هاي الكترونيك ديجيتال

1396

1399/06/12

دكتر ستار ميرزاكوچكي

برق

يكي از چالش‌هاي اصلي برنامه‌نويسي براي سيستم‌هاي چند پردازنده‌اي تصميم‌گيري درباره‌ي چگونگي توزيع بخش‌هاي مختلف يا همان وظايف يك برنامه بين پردازنده‌هاي موجود است. انتخاب مناسب‌ترين پردازنده براي اجراي يك وظيفه اصطلاحا نگاشت ناميده شده و تعيين زمان آغاز اجراي هر وظيفه نيز زمان‌بندي ناميده مي‌شود. در اين پايان‌نامه به بررسي مسئله‌ي نگاشت و زمان‌بندي ايستاي وظايف در سيستم‌هاي محاسباتي ناهمگن با هدف كمينه كردن زمان اجراي برنامه مي‌پردازيم و براي حل آن سه الگوريتم ابتكاري نوين از نوع الگوريتم‌هاي برنامه‌ريزي فهرستي با اولويت‌بندي ايستا پيشنهاد مي‌كنيم. نخستين الگوريتم ارائه شده در اين پايان‌نامه الگوريتم مسيرِ داراي ارتباطات شديد بر روي يك پردازنده نام دارد و انگيزه‌ي ارائه‌ي آن پيشنهاد راهكارهايي براي بهبود عملكرد الگوريتمي كلاسيك به نام الگوريتم مسير بحراني بر روي يك پردازنده است. تغييرات پيشنهادي با ايجاد هماهنگي بيشتر بين بخش‌هاي مختلف اين الگوريتم كيفيت برنامه‌ريزي‌هاي زماني حاصل را بهبود مي‌بخشند. دومين الگوريتم ارائه شده در اين پايان‌نامه الگوريتم زودترين زمان اتمام سودمند نام دارد و انگيزه‌ي ارائه‌ي آن پيشنهاد معياري پويا براي پيش‌بيني گلوگاه‌هاي پردازشي يك برنامه‌ي موازي است. بدين منظور ايده‌ي نوين ”زمان قابل صرفه‌جويي“ را ارائه كرده و آن را در قالب يك جدول فرموله مي‌كنيم. اين جدول در عين دارا بودن پيچيدگي زماني مرتبه‌ي دوم قابليت پيش‌بيني را فراهم مي‌كند اما يك ضعف ذاتي دارد و آن اين است كه در تشكيل آن، در دسترس بودن پردازنده‌ها در نظر گرفته نمي‌شود و در نتيجه ممكن است در مواقعي به پيش‌بيني‌هايي با دقت پايين بيانجامد. سومين الگوريتم ارائه شده در اين پايان‌نامه الگوريتم زودترين زمان اتمام سودمند وزن‌دهي شده نام دارد و انگيزه‌ي ارائه‌ي آن پيشنهاد راهكاري براي به حداقل رساندن اين ضعف است. اين الگوريتم مي‌كوشد تا با اختصاص وزن‌هايي گوناگون به وظايف، پيش‌بيني‌هايي كه احتمالا دقت پاييني دارند را تضعيف كند تا اثرگذاري آنها بر تصميمات الگوريتم كاهش يابد. پيچيدگي زماني هر سه الگوريتم پيشنهادي برابر با حداقل مرتبه‌ي پيچيدگي زماني در ميان الگوريتم‌هاي فهرستي شناخته شده است. شبيه‌سازي‌هايي متنوع تأثير مثبت پيشنهادات ارائه شده در نخستين الگوريتم را تأييد مي‌كنند. همچنين شبيه‌سازي‌هايي گسترده‌ برتري دومين و سومين الگوريتم‌ ارائه شده بر شناخته شده‌ترين الگوريتم‌هاي زمان‌بندي فهرستي را نشان مي‌دهند.

1399/07/06

Efficient Task Mapping and Scheduling in Multiprocessor Systems

9/3/2021 12:00:00 AM

In this thesis, we address the critical problem of compile-time task scheduling for heterogeneous computing systems aiming to minimize the overall execution time of a parallel application. We will propose three novel list-based heuristic algorithms, which consist of two main phases namely task prioritizing and processor selection, to tackle this NP-complete problem. In our first work, we present a critical path-oriented scheduling algorithm. It is a modification of the well-known Critical Path on a Processor (CPOP) algorithm that presented the idea of scheduling the most costly entry-exit path of tasks, commonly known as the critical path, on a single processor. Generally, this processor selection strategy has different potential impacts on computation and communication costs along a selected path in the produced schedule. However, these probably different effects are not considered in the common definition of a critical path. Differentiating between these two types of costs, we introduce a novel performance-effective definition for a critical path that is compatible with this processor selection strategy. The experimental studies prove our analysis. The recent trend in designing list-based scheduling heuristics is introducing look-ahead features using predict-tables. The main idea is trying to make globally efficient decisions while maintaining low complexity. However, related algorithms in the literature do not fully exploit the potential of this method since they define their predict-tables based on the static concept of cost (in terms of time). Such attributes do not provide information about ensuing variations in application execution time caused by a mapping decision, and as a result, are unable to properly predict the potential processing bottlenecks of a parallel application. Also, suggested predict-tables in the literature have an inherent weakness against task parallelism since they do not consider processor availability. In our second and third works, we introduce a novel concept called optimistic saved-time and we formulate it as a predict-table called optimistic saved-time table. We define our processor selection strategy based on combinations of this new concept and cost. In the processor selection phase, each task is assigned to a processor which not only provides an early finish time for that task but also its selection is likely to result in a great saved-time in the execution of the successor tasks. The proposed predict-table also contains a novel parallelism-aware weighing approach to maintain its performance against task parallelism. The comprehensive experiments based on a wide variety of randomly generated applications and some real-world applications demonstrate the notable performance improvement of the proposed algorithm over several state-of-the-art list-based scheduling heuristics.