دانلود مقاله کاربرد الگوریتم ژنتیک در مرتب سازی بهینه

چکیده

رشد پيچيدگي پردازشهاي مدرن توليد كد موثر مناسب را بصورت افزايشي سخت ساخته است. توليد كد به صورت دستي بسيار زمان صرف كننده می باشد اما ان بارها انتخاب میشوند به طوريكه كد توليد شده بوسيله تكنولو‍‍‍‍ژي كامپايلرهاي امروزي بارها اجراي پايين تری نسبت به بهترين كدهاي اماده شده دستي دارند. يك نوليد از استراتژي توليد كد انجام گرفته شده بوسيله سيستمهاي شبيه ATLAS,FFTW و SPIRAL كه جستجوي تجربي را براي پيدا كردن مقادير پارامتر از کارایی را استفاده كرده است به طوريكه اندازه تيله و زمانبندي آموزش كه تحويل انجام بهينه براي يك ماشين مخصوص میباشد. به هر حال اين ديدگاه دارد به تنهایی به طور كامل ثابت ميكند در كدهاي علمي اجرا به داده ورودي وابسته نيست. در اين مقاله ما مطالعه ميكنيم تكنيكهاي يادگيري ماشين را براي توسعه جستجوي ترتيبي براي توليدي از روتينهاي سورت كردن كه اجرا در مشخصات ورودي و معماري از ماشين هدف وابسته است. ما ساختيم در مطالعه قبلي كه يك الگوريتم سورت خالص در اغازي از محاسبات مثل تابعي از انحراف معيار انتخاب کنیم. ديدگاهی که بحث ميكنیم در اين مقاله الگوريتمهاي ژنتيك و يك سيستم طبقه بندي با ساختار بصورت سلسله مراتبي ساخته شده الگوريتمهاي سورت تلفيقي توانا از تبديل كردن داده ورودي استفاده ميكند. نتايج ما نشان ميدهد كه الگوريتمهاي توليد شده با استفاده از ديدگاه ارائه شده در اين مقاله هستند سرع و موثر در گرفتن داخل اكانت اثرات متقابل پيچيده ما بين معماري و مشخصات داده ورودي و كد نتيجه بسيار مهم بهتر از اجراعات سورت مرسوم و كد توليد شده با مطالعه اسان ما اجرا ميكند. به ويژه روتينهاي توليد شده با ديدگاه ما اجرا ميكند بهتر از تمام كتابخانه هاي تجاري كه ما ازمايش كرديم مثل IBM ESSL,INTEL MKL و C++ STL. بهترين الگوريتم ما دارد توانايي توليد ای در معدل 26% و 62% سريعتر از IBM ESSL در يك IBM PAWER 3 و IBM PAWER 4 بترتيب را دارد.

مقدمه

اگر چه تكنولوژي كامپايلر فوق العاده در پردازش خودكاراز بهينه سازي برنامه كامل شده است و بيشتر مداخلات انساني هنوز هست براي تامين كد بسيار سريع لازم شده است. يك دليل اينكه ناجوري از اجراعات كامپايلر وجود دارد. اينها كامپايلرهاي بيهنه عالي براي بعضي پلاتفرمها هستند اما كامپايلرهاي موجود براي بعضي پلاتفرمهاي ديگر بسياري خواسته ها را ترك ميكنند. دومين دليل و شايد بسيار مهم اين هست که كامپايلرهاي مرسوم كه فاقد اطلاعات معنايي هستند و بنابراين محدود شده اند به قدرت دگرگونييا تغيير. يك ديدگاه ايجاد شده كه دارد ثابت شده بكلي موثر در چيره شدن به هر دوي اين محدوديتها استفاده نمودن توليد كننده هاي كتابخانه میباشد. اين سيستمها استفاده معنايي در اطلاعات براي بكار بردن دگرگون سازي در تمام سطوح از تجريد مهیا ميسازند. بيشتر توليدات كتابخانه قدرتمند نيستند فقط بهينه ساز برنامه همان سيستمهاي طراحي الگوريتم هستند.

ATLAS[21],PHiPAC[2],FFTW[7],SPIRAL[23] در طول بهترين توليد كننده هاي كتابخانه دانسته شده میباشند. ATLAS ,PHiPAC توليد ميكنند روتينهاي جبري خطي را و پردازش بهينه را در پياده سازي از ضرب ماتريس در ماتريس فوكس ميكنند. در مدت نصب مقادير پارامتر از يك پياده سازي ضرب يك ماتريس بطوريكه اندازه تيله و مقداري از حلقه باز شده كه تحويل ميدهد بهترين انجام معين كننده هويت استفاده جستجوي تجربي. اين جستجو پردازش ميشود با توليد كردن ورژنهاي گوناگون از ضرب ماتريسي كه تنها اختلاف دارند در مقدار پارامتر كه هست شروع به جستجو. در تقريب جستجوي گسترده هست استفاده شده براي پيدا كردن بهترين مقادير پارامتر. دو سيستم ديگر اشاره دارند روي SPIRAL,FFTW توليد ميكنند كتابخانه هاي پردازش كننده تنها را. فضاي جستجو در SPIRAL,FFTW هست همچنين بزرگتر براي جستجوي گسترده براي ممكن شدن. بنابراين اين سيستمها جستجو ميكنند با استفاده هيوريستيك مثل برنامه نويسي دايناميك [7,12] يا الگوريتمهاي ژنتيك [19].