23481

ارائه الگوريتم زمان‌بندي با استفاده از روش بخش‌بندي گراف در سامانه‌هاي قابل بازپيكربندي جزئي و پويا

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

مهندسي برق

1397

1399/11/12

جناب آقاي دكتر هادي شهريار شاه حسيني

مهندسي برق

براي محاسبات با كارايي بالا (HPC) هدف اين است، كه از تركيب دو نوع سخت‌افزار، پردازنده‌هاي همه‌منظوره و اف.پي.جي.اي‌ها استفاده شود، بطوري‌كه با تقسيم وظايف بين آن‌ها به بيشترين كارايي ممكن دست پيدا كرد. وظايفي كه به صورت ذاتي متوالي هستند، و يا جريان كنترل گسترده‌اي دارند، روي پردازنده‌هاي همه‌منظوره و وظايفي كه ذاتا ساختار موازي دارند، روي اف.پي.جي.اي ها با كارايي مناسب‌تري اجرا مي‌شوند. اف.پي.جي.اي به عنوان يك تراشه جهت انجام محاسبات سخت‌افزاري به دو صورت جزئي و كلي قابل استفاده مي‌باشد. برخلاف بازپيكربندي كلي، كه اف.پي.جي.اي قبل از شروع اجراي برنامه‌ها پيكربندي مي‌شود، در بازپيكربندي جزئي هر بخش، به صورت جداگانه قابل برنامه‌ريزي و اجرا مي‌باشد. اين مشخصه باعث شده است، اين تراشه به يك سخت‌افزار معمول، جهت اجراي برنامه‌ها تبديل شود. ازآنجايي‌كه واحد زمان‌بندي، وظيفه مديريت اجراي برنامه‌ها در زمان مناسب را به عهده دارد، الگوريتم‌هاي فراواني براي كاهش پيچيدگي زمان‌بندي و بهبود عملكرد آن معرفي، و مورد استفاده قرار گرفته است. در اين پژوهش براي كاهش پيچيدگي زمان‌بندي، از يك روش بخش‌بندي گراف برنامه، به زيرگراف‌هاي كوچك‌تر استفاده شده است. از طرفي يك زمان‌بندي مؤثر، به دنبال نگاشت خوب، اتفاق مي‌افتد، كه در اين پژوهش سعي شده با معرفي يك روش محاسباتي، ميزان تأثيرپذيري الگوريتم زمان‌بندي، از الگوريتم‌هاي نگاشت را كاهش داد. در آخر يك الگوريتم زمان‌بندي همه‌جانبه معرفي مي‌گردد، كه با استفاده از اطلاعات به دست آمده از واحد بخش‌بندي و نگاشت، به كاهش زمان اجراي هر برنامه بپردازد. واژه‌هاي كليدي: سامانه‌هاي قابل بازپيكربندي جزئي و كلي / الگوريتم بخش‌بندي/ واحد نگاشت / واحد زمان‌بندي / الگوريتم زمان‌بندي

1400/02/13

A Comprehensive Scheduling Algorithm based on the graph partitioning in partially reconfigurable computing systems

3/20/2022 12:00:00 AM

Abstract: FPGA can be programed in both fully and partially type. Despite fully reconfiguration which programed FPGA once at the initialization time, dynamically reconfigurable logic, refers to designs that can be reconfigured on the fly, while remaining resident in the system. This feature causes to implement a lot of real applications in RC systems. Since the scheduling unit identifies each application should be execute where and when, a lot of algorithms have been promoted. In this paper the BDK-means algorithm is used to partition AGs in to some applicable subgraphs to reduce the complexity of scheduling. With the purpose of reducing the mapping effects on scheduling, approximate execution times is assigned to all possible shape of executing each subgraph. At last a comprehensive scheduler manages tasks implementation so that the make span is reduced. To compare the proposed scheduling approach with others, Extensive experiments with benchmark graphs have been carried out. The results showed improved 7.7%, 79.32% and 67.98% make span in comparison with MSHA, RDSN and CMILP, methods respectively. Other achievements have been investigated, too. Keywords: Reconfigurable computing system; Dynamic Reconfiguration; Graph partitioning; Application scheduling

سامانه‌هاي قابل بازپيكربندي جزئي و كلي , الگوريتم بخش‌بندي , واحد نگاشت , واحد زمان‌بندي , الگوريتم زمان‌بندي

Reconfigurable computing system , Dynamic Reconfiguration , Graph partitioning , Application scheduling