بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بررسي قابليت به کارگيري چارچوب MapReduce به منظور قابل حل نمودن محاسبات علمي
چکيده : حل برخي از مسائل علمي به دليل نياز به منابع پردازشي بالا حتي با سريع ترين کامپيوترها بسيار زمان گير و ناکارآمد است . يک راه حل براي اين مشکل مي تواند استفاده از سيستم هاي توزيع شده و انجام کارها به صورت موازي باشد. براي اين که اين مسائل برروي يک سيستم توزيع شده انجام شود و کارهاي موازي سازي ، کنترل و مديريت خطاها به صورت خودکار انجام شوند و برنامه نويسي به شکل ساده تري قابل انجام باشد بايد مسائل به يک چارچوب برنامه نويسي تبديل شوند. چارچوب MapReduce يکي از معروف ترين چارچوب هاي موجود است که تمام قابليت هاي بالا را داراست . اين مقاله با پياده سازي سه الگوريتم محاسبات علمي به بررسي بيشتر اين چارچوب و قابليت آن در حل مسائل علمي پرداخته است . سرعت اجراي اين الگوريتم ها نشان مي دهد اين چارچوب سرعت خوبي در حل مسائل علمي دارد و به خصوص در الگوريتم هاي کاملا موازي که کارها به طور کامل مستقل از هم انجام مي شوند؛ سرعتي در حد ايده آل دارد.
واژه هاي کليدي : مپ رديوس (MapReduce(، هدوپ (Hadoop)
١- مقدمه
همواره حل مسائل علمي با مدل ها و شبيه سازي هاي پيچيده به منابع پردازشي زيـادي نيـاز دارد. گـاهي حـل چنـين مسـائلي بـا سـريع تـرين کامپيوترها بسيار زمان گير است . سيستم هاي توزيع شده مي تواند يک راه حل مناسب براي حل اين گونه مسائل باشد زيرا با تقسيم محاسـبات بـرروي چند ماشين منابع بيشتري براي حل مسئله فراهم مي شود؛ همچنين با انجام کارها به صورت موازي سرعت پردازش نيز افزايش يابد. براي پياده سازي يک مسئله برروي يک سيستم توزيع شده بايد مسئله به يک چارچوب کاهش يابد تا امکان برنامه نويسي آسان تر و استفاده بهتر از منابع سيستم براي برنامه امکان پذير باشد. در اين مقاله چارچوب MapReduce مورد بررسي قرار گرفته که يکي از معروف ترين چارچوب هاي سيستم هاي توزيـع شـده است . اين چارچوب [۱] "يک مدل برنامه نويسي است که براي پردازش و توليد مجموعه هاي بزرگ داده مناسب است ". يکي از پياده سازي هاي معروف اين چارچوب هدوپ [۲] نام دارد که توسط بنياد نرم افزاري آپاچي به صورت متن باز پياده سازي شده است . برنامه هايي که به اين سبک نوشته مي - شوند به صورت خودکار توسط چارچوب MapReduce موازي سازي مي شوند و برروي خوشه هاي بزرگ از ماشين ها اجرا مي شوند. از جملـه وظـايف سيستم زمان اجرا مي توان به کنترل نحوه توزيع داده ، زمان بندي چندين تابع map و reduce براي اجراي موازي برروي مجموعـه اي از ماشـين هـا، اداره شکست ماشين ها و مديريت ارتباط هاي بين ماشين ها اشاره کرد. براي خلق يک کار، نياز به يک تابع map و يک تابع reduce است . تابع map
يک جفت کليد.مقدار را به عنوان ورودي گرفته و با پردازش آن يک جفت کليد.مقدار ديگر توليد مي نمايد. توابع map داده توزيع شده برروي خوشه را پردازش کرده و يک مجموعه از جفت هاي کليد.مقدار واسط را توليد مي کنند. تابع reduce همه مقاديري که داراي کليدي يکسان مي باشند را به عنوان ورودي گرفته و اين مقادير را با هم ادغام مي نمايد و نتيجه حاصل را به صورت جفت مرتب کليد.مقدار در خروجي مي نويسد.
٢- کارهاي مرتبط
تاکنون الگوريتم هايي از محاسبات علمي با استفاده از چارچوب MapReduce پياده سازي و اجرا شدند تا قابليت به کارگيري ايـن چـارچوب را مورد بررسي قرار دهند. يکي از آنها الگوريتم شبيه سازي پويا مولکولي [۳] است . شبيه سازي پويا مولکولي از کامپيوترها براي شـبيه سـازي حرکـات اتم ها و مولکول ها استفاده مي کند. اين الگوريتم به شدت محاسباتي است که مي توان آن را در محيط هاي توزيع شده بـه صـورت مـوازي اجـرا نمـود.
سرعت اين الگوريتم حدود ۵۰ درصد بهبود يافته است . يکي ديگر از الگوريتم هاي محاسبات علمي ، الگوريتم تبديل فوريه است که مـي توانـد بـراي حل معادلات ديفرانسيل با مشتق جزئي به کار رود. در مقاله [۴] زمان اجراي اين الگوريتم با افزايش سايز ورودي محاسبه شده است و زمان اجراي آن از (O(nlog n به (O(n کاهش يافته است .
٣- کاهش مسائل علمي به چارچوب MapReduce
تاکنون الگوريتم هايي از محاسبات علمي به چارچوب MapReduce تبديل شده اند اما هنوز نياز به بررسي بيشتر براي درک بهتر قابليت به - کارگيري اين چارچوب است . به منظور بررسي دقيق تر چارچوب MapReduce و قابليت اين روش در حل مسائل علمي ، الگوريتم هاي زير به اين چارچوب کاهش يافتند. هر يک از اين الگوريتم ها ابتدا برروي يک نود (حالت سري ) و سپس برروي دو، چهار و هشت نود (حالت هاي موازي ) از ابر آمازون اجرا شدند و زمان اجراي اين سه الگوريتم محاسبه گرديد. زمان اجراي اين الگوريتم ها در حالت هاي سري و موازي اندازه گيري و سرعت اين الگوريتم ها از طريق فرمول زير محاسبه گرديد.
T زمان اجراي الگوريتم در حالت سري و Tp زمان اجراي الگوريتم در حالت موازي است . p نشان دهنده تعداد پروسسورها در اجراي موازي است که براي p دو، چهار و هشت زمان Tp اندازه گرفته شد. در ادامه جزئيات اجراي اين سه الگوريتم توضيح داده خواهد شد:
٣-١ تعيين اعداد اول با استفاده از الگوريتم ميلر - رابين
الگوريتم ميلر - رابين [۵] يکي از الگوريتم هايي است که براساس قضيه فرما [۶] کار مي کند و در زمينه تست اعداد اول به کار مي رود. براي تجزيه عدد n ابتدا عدد ١-n به صورت نوشته مي شود سپس مراحل شبه کد زير k بار تکرار مي شود.
در مدل MapReduce اين کار در مرحله Map، هر تابع map يک بازه را براي بررسي اعداد اول موجود در آن به عنوان ورودي دريافت مي کند و تابع ميلر - رابين را براي تست اعداد اول بازه به کار مي بندد. تابع map در صورت احتمال اول بودن عدد مورد بررسي جفت (١ ,n) و در غيراين - صورت جفت (٠ ,n) را توليد مي کند. در مرحله Reduce، تابع Reduce مقادير توليد شده براي يک عدد را با هم جمع مي نمايد. اگر حاصل اين مقادير صفر باشد عدد اول بوده و در غيراين صورت عدد مرکب است . نمودار سرعت اين الگوريتم در شکل ۱ نشان داده شده است . اين الگوريتم نيز به خوبي به چارچوب MapReduce تبديل شده و سرعت خوبي را نشان مي دهد.
٣-٢ انتگرال گيري به روش Monte Carlo
در رياضيات ، انتگرال گيري مونت کارلو يک تکنيک براي انتگرال گيري عددي است که با استفاده از اعداد تصادفي يک انتگرال متناهي را به محاسبه مي نمايد [۷]. براي محاسبه انتگرال به روش مونت کارلو ابتدا نقاط به صورت تصادفي از دامنه انتگرال توليد و مقدار تابع به ازا اين نقاط محاسبه مي گردد. سپس با استفاده از فرمول زير مقدار تقريبي انتگرال محاسبه مي گردد.
در اين فرمول v حجم ناحيه اي است که توسط بازه انتگرال محدود شده است و n تعداد اعداد تصادفي توليد شده و مجموع مقادير تابع به ازا اعداد تصادفي است . براي افزايش دقت نتيجه مي توان به جاي اعداد تصادفي از دنباله شبه تصادفي استفاده نمود تا اعداد تصادفي توليد شده به صورت يکنواخت تري در دامنه انتگرال انتخاب شوند[۸].
در الگوريتم mapreduce اين مسئله ، در مرحله map ابتدا با توجه به تعداد توابع map ، توليد اعداد تصادفي بين اين توابع تقسيم مي شوند و هر تابع تعدادي از اين اعداد را توليد و براي توابع reduce ارسال مي نمايد. سپس در مرحله reduce، آرايه اي از اعداد تصادفي را به عنوان ورودي دريافت مي کند و مقدار تابع را به ازا اين اعداد محاسبه مي نمايد. خروجي اين تابع با توجه به فرمول (۲) حاصل انتگرال به ازا اين اعداد تصادفي است . شکل ۲ نمودار سرعت اين الگوريتم را با تعداد نودهاي مختلف نشان مي دهد. با توجه به شکل ۲ مي توان گفت چارچوب براي الگوريتم هايي که ماهيت موازي دارند و مي توان آن ها را به کارهاي کاملا مستقلي تقسيم نمود بسيار مناسب است و مي توان سرعتي در حد نرمال از اين چارچوب انتظار داشت .
٣-٣ الگوريتم غربال مربعي
تجزيه اعداد طبيعي به معني شکستن يک عدد مرکب به حاصل ضرب عوامل اول آن است . گاهي تجزيه عدد مرکب با الگوريتم هاي موجود حتي با سريع ترين کامپيوترها بسيار زمان بر و در عمل ناکارآمد است [۹]. الگوريتم هاي معتددي براي تجزيه اعداد طبيعي وجود دارد که الگوريتم غربال مربعي يکي از آنها است ؛ اين الگوريتم سريع ترين روش براي اعداد زير صد رقم دسيمال است [۱۰].
