30815

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

دكتري تخصصي (PhD)

مهندسي برق- الكترونيك

1393

1402/12/14

هادي شهريار شاه حسيني

ندارم

مهندسي برق

با افزايش نيازهاي محاسباتي در بسياري از كاربردهاي امروزي، استفاده از معماري هاي پيشرفته مبتني بر پردازشگر‌هاي قابل بازپيكره بندي به‌شدت احساس مي شود. اين پردازشگرها علاوه بر ايجاد تسريع محاسباتي با اجراي برنامه ها به‌صورت سخت افزاري، امكان استفاده مؤثر از منابع را با قابليت بازپيكره بندي مجدد فراهم مي كنند. يكي از اصلي ترين چالش‌ها در ناكارآمدي اين پردازشگرها زمان هاي بسيار طولاني مراحل آماده سازي برنامه ها جهت اجرا روي بلوك هاي سخت افزاري است. اين عامل باعث مي شود كه برخي از برنامه هاي ورودي (خصوصاً برنامه هاي بزرگ مقياس) قابليت اجرا روي پردازشگرهاي قابل بازپيكره بندي را از دست بدهند و سهم بالايي از منابع در رسيدن به بهره وري كامل هدر برود. مهم ترين بخش در مراحل آماده سازي برنامه، نگاشت به منابع است. اين مرحله تأثير مستقيمي روي زمان آماده‌سازي برنامه ورودي و جنبه هاي متفاوتي از جمله مقياس پذيري و انعطاف پذيري خواهد داشت. در اين رساله راه‌كار هاي اولويت‌بندي منابع و مدل مفهومي برداري براي توليد نگاشت‌هاي معتبر مستقل از اندازه برنامه‌ ورودي ارائه مي‌شود تا برپايه مدل‌هايي براساس ساختارهاي نوين ماتريسي نيازهاي آماده‌سازي برنامه‌هاي امروزي را در سامانه‌هاي قابل‌بازپيكره‌بندي برآورده سازد. ازطرفي‌ديگر براي مديريت مناسب‌تر منابع در اجراي همزمان برنامه‌ها سازوكاري براي استخراج ويژگي از نسخه‌هاي اجرايي نگاشت‌شده ارائه مي‌گردد تا براساس ميزان تطابق بين ساختار‌ برنامه ورودي و ساختار منابع، امكان بهره‌وري حداكثري از منابع را فراهم سازد. با ايجاد اولويت‌بندي در منابع و برحسب اندازه ورودي، امكان شناسايي بين 16 تا 33 درصد از جواب‌هاي ضعيف بوجود آمد كه اين امر با افزايش كيفيت نگاشت در مقايسه با ديگر روش‌ها به‌طور ميانگين 6/47 درصد اندازه بافر بلوك‌هاي سخت‌افزاري را كاهش داده است. افزايش 8/5 برابري معيار شايستگي متناظر با سربارزماني و كيفيت نگاشت در مدل مفهومي برداري در مقايسه با ديگر روش‌ها نيز باعث شد تا آماده‌سازي برنامه‌هاي بزرگ‌مقياس و استفاده در كاربردهاي بلادرنگ امكان‌پذير باشد. درنهايت با استفاده از نسخه‌هاي اجرايي متنوع براي جايابي و زمان‌بندي برنامه‌ها، بهره‌وري از منابع در شرايط باركاري سنگين تا 96 درصد افزايش پيدا كرد.

1403/02/17

Application Graph Mapping and Scheduling in Reconfigurable Processing Systems

1/1/1900 12:00:00 AM

With the increasing computational demands in many modern applications, the use of advanced architectures based on configurable processors is strongly felt. These processors, in addition to accelerating computations by executing programs in hardware, provide effective resource utilization with reconfigurability. One of the main obstacles to the inefficiency of these processors is the very long compilation times for applications to run on hardware blocks. This results in a significant increase in reconfiguration overheads and loss of scalability in input application size. The lack of flexibility in creating different executable versions that conform to intra-program communication structures is also another obstacle in the application compilation process. These factors ultimately result in some input application (especially large-scale application) losing the ability to run on configurable processors, and a high share of resources being wasted in achieving full efficiency. The most important part of the program preparation process is resource mapping, where a one-to-one correspondence between each hardware block and computational node will be established. This stage will have a direct impact on input program preparation time and various aspects such as scalability and flexibility. In this thesis, solution spaces seperation, rewriting problem vectors, and decomposing input programs are presented to improve these issues. In the first solution, resource and input graph labeling were analyzed to identify areas containing weak and potential solutions and increase the speed of reaching the final solution. In the second solution, a new scaling formula was presented for the mapping problem using proven mathematical lemmas in this thesis to use vector variables instead of matrix variables to simplify solution space. Finally, in the third solution, flexible mapping operations were performed based on the grouped application graph to extract various executable versions and use them to improve scheduling and placement operations. The solution spaces seperation approach identified analytically up to 33% areas containing weak solutions, leading to increased convergence speed and improved mapping quality. The use of vector variables reduced the time required to solve the mapping problem up to 66% compared to lightweight methods, resulting in an almost scalable mapping method. Finally, generating diverse executable versions for application placement and scheduling increased resource utilization and usage in heavy load conditions up to 96%.

معماري هاي محاسباتي كارآمد , پردازش قابل بازپيكره بندي , شبكه هاي ميان ارتباطي , پردازش گراف

High Performance Computing , Reconfigurable Computing , interconnection networks , Graph Computing

Mehdi Mohtavapoor

Dr. Hadi Shahriar Shah Hosseini