19385

۱۹۳۸۵

زمان بندي ساختار-آگاه گردش كار و تدارك منابع براي رايانش ابري

دكتري تخصصي

الكترونيك

مهر ۱۳۹۰

۱۳۹۷/۰۲/۰۴

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

برق

گردش كارهاي علمي به عنوان ابزاري براي خودكار كردن و بهينه سازي فرآيندهاي پيچيده و بزرگ-مقياس علمي، امكان تحليل داده ها را به گونه اي توزيع شده و ساختاريافته فراهم مي نمايند و در اين ميان، الگوريتم هاي زمان بندي نقشي اساسي در اجراي كارآمد اين كاربردهاي بزرگ مقياس بر روي محيط هاي رايانشي توزيع شده ايفا مي نمايند. ظهور الگوي اخير سامانه هاي رايانشي توزيع شده، يعني رايانش ابري، فرصت هاي فراواني را براي اجراي گردش كارها با هزينه اي اندك و بدون نياز به خريداري زيرساخت به همراه داشته است. فراهم كنندگان ابر، با فراهم ساختن امكان دسترسي به مخزني عظيم از منابع مجازي سازي شده كه مي توانند براساس نياز، در اختيار گرفته شده و يا آزاد گردند و صرفا برمبناي ميزان استفاده هزينه دريافت كنند، زيرساختي كشسان و به آساني دسترس پذير جهت اجراي اين نوع كاربردها ارائه مي كنند. در اين پايان¬نامه، به ارائه ي روش هايي براي زمان بندي و تدارك منابع جهت اجراي كاربردهاي از نوع گردش كار بر روي ابرهاي زيرساخت پرداخته شده است. به طور مشخص، به دليل امكان رشد غيرمعمول زمان مورد نياز براي توليد پاسخ هاي زماني به هنگام افزايش ابعاد يك گردش¬كار با ساختار مشخص، سعي شده است از دو رويكرد مختلف، روش هاي زمان بندي مقياس پذير ارائه شوند. در رويكرد اول كه دگرگوني نام دارد، مسئلهي اصلي به مسئله اي جديد تبديل مي¬شود، به گونه اي كه مجموع حجم محاسبات لازم براي انجام آن تبديل به علاو ي حجم محاسبات لازم براي حل مسئله¬ي جديد متناسب با بزرگ شدن اندازه مسئله اوليه افزايش يابند. در رويكرد دوم، كه جستجوي محدود شده نام دارد، با ارائه دو روش مختلف كه يكي از آن ها مبتني بر الگوريتم ژنتيك و ديگري مكاشفه اي است، به حل مسئله اوليه و جستجوي پاسخ مطلوب در فضاي پاسخ هاي مسئله اصلي پرداخته مي شود، به گونه اي كه با جستجو در بخش هايي محدود از اين فضا كه احتمال وجود پاسخ(هاي) مطلوب در آن ها بيشتر است، حجم محاسبات لازم و در نتيجه زمان مورد نياز براي رسيدن به پاسخ نهايي را متناسب با بزرگ شدن ابعاد مسئله كاهش داد. نتايج ارزيابي ها و شبيه سازي ها حاكي از آن است كه روش هاي پيشنهادي نام برده شده، از لحاظ كيفيت پاسخ هاي توليدي در روش ارائه شده براي رويكرد دگرگوني به طور متوسط 11.2% برتر از روش-هاي مورد مقايسه است و داراي پيچيدگي محاسباتي آن كه بيانگر مقياس پذيري اين روش مي باشد به صورت خطي افزايش مي يابد. براي دو روش پيشنهادي در بخش رويكرد جستجوي محدود شده نيز بهبود كيفيت پاسخ ها در مقايسه با روش هاي مورد مقايسه به ترتيب برابر با 46% و 35% است و همچنين درجه پيچيدگي محاسباتي آن ها نيز از مرتبه دو مي باشد.

1397/06/31

Software-aware workflow scheduling and resource provisioning for cloud computing

9/22/2018 12:00:00 AM

Workflows as tools for automating and optimizing large-scale scientific problems enable the analysis of data in a structured and distributed manner. Their importance is intensified in today's big data era as they become a compelling mean to process and extract knowledge from the ever-growing data produced by increasingly powerful tools such as telescopes and particle accelerators. The scheduling algorithms are key to efficiently automate the execution of these large-scale applications in distributed environments, and as a result, to facilitate and accelerate the pace of scientific progress, especially the e-science. The emergence of the latest distributed system paradigm, cloud computing, brings with it tremendous opportunities to run workflows at low costs without the need of owning any infrastructure. In particular, Infrastructure as a Service (IaaS) clouds, offer an easily accessible, flexible, and scalable infrastructure for the deployment of these scientific applications by providing access to a virtually infinite pool of resources that can be acquired, configured, and used as needed and are charged on a pay-per-use basis. This thesis investigates novel resource provisioning and scheduling approaches for scientific workflows in IaaS clouds. In particular, due to the unusual growth of the time needed to produce solutions for larger workflows, in this thesis tried to providing scalable scheduling algorithms from two different perspectives. In the first perspective, the main problem is converted into a new one so that the sum of the computation needed to perform the transformation and solving the new problem grow proportional to the growth of the problem size. In the second perspective which includes two different approaches, by using innovative mechanisms it is tried to only search in the promising limited parts of the search space so that the required computation time grow proportional to the problem size. The results obtained from the evaluations and simulations show that the proposed methods in comparison to others provide better solutions in terms of scalability and the quality of the solutions.