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

logo-4

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

 

عنوان فارسی مقاله: سورت بهینه با الگوریتمهای ژنتیک
عنوان انگلیسی مقاله: Optimizing Sorting with Genetic Algorithms
رشته های مرتبط: مهندسی کامپیوتر، مهندسی نرم افزار
 فرمت مقالات رایگان مقالات انگلیسی و ترجمه های فارسی رایگان با فرمت PDF میباشند
 کیفیت ترجمه کیفیت ترجمه این مقاله خوب میباشد 
کد محصول F14

 مقاله انگلیسی رایگان

دانلود رایگان مقاله انگلیسی

ترجمه فارسی رایگان 

دانلود رایگان ترجمه مقاله
جستجوی ترجمه مقالات جستجوی ترجمه مقالات کامپیوتر

 

بخشی از ترجمه فارسی:

چکیده
رشد پيچيدگي پردازش های مدرن توليد كد موثر مناسب را بصورت افزايشي سخت ساخته است. توليد كد به صورت دستي بسيار زمان صرف كننده می باشد اما آن بارها انتخاب میشوند به طوريكه كد توليد شده بوسيله تكنولو‍‍‍‍ژي كامپايلرهاي امروزي بارها اجراي پايين تری نسبت به بهترين كدهاي آماده شده دستي دارند. يك نوليد از استراتژي توليد كد انجام گرفته شده بوسيله سيستم هاي شبيه ATLAS,FFTW و SPIRAL كه جستجوي تجربي را براي پيدا كردن مقادير پارامتر از کارایی را استفاده كرده است به طوريكه اندازه تيله و زمانبندي آموزش كه تحويل انجام بهينه براي يك ماشين مخصوص می باشد. به هر حال اين ديدگاه دارد به تنهایی به طور كامل ثابت ميكند در كدهاي علمي اجرا به داده ورودي وابسته نيست. در اين مقاله ما مطالعه ميكنيم تكنيكهاي يادگيري ماشين را براي توسعه جستجوي ترتيبي براي توليدي از روتينهاي سورت كردن كه اجرا در مشخصات ورودي و معماري از ماشين هدف وابسته است. ما ساختيم در مطالعه قبلي كه يك الگوريتم سورت خالص در اغازي از محاسبات مثل تابعي از انحراف معيار انتخاب کنیم. ديدگاهی که بحث ميكنیم در اين مقاله الگوريتمهاي ژنتيك و يك سيستم طبقه بندي با ساختار بصورت سلسله مراتبي ساخته شده الگوريتمهاي سورت تلفيقي توانا از تبديل كردن داده ورودي استفاده ميكند. نتايج ما نشان ميدهد كه الگوريتمهاي توليد شده با استفاده از ديدگاه ارائه شده در اين مقاله هستند سرع و موثر در گرفتن داخل اكانت اثرات متقابل پيچيده ما بين معماري و مشخصات داده ورودي و كد نتيجه بسيار مهم بهتر از اجراعات سورت مرسوم و كد توليد شده با مطالعه اسان ما اجرا ميكند. به ويژه روتينهاي توليد شده با ديدگاه ما اجرا ميكند بهتر از تمام كتابخانه هاي تجاري كه ما ازمايش كرديم مثل IBM ESSL,INTEL MKL و C++ STL. بهترين الگوريتم ما دارد توانايي توليد ای در معدل ۲۶% و ۶۲% سريعتر از IBM ESSL در يك IBM PAWER 3 و IBM PAWER 4 بترتيب را دارد.
۱ مقدمه
اگر چه تكنولوژي كامپايلر فوق العاده در پردازش خودكاراز بهينه سازي برنامه كامل شده است و بيشتر مداخلات انساني هنوز هست براي تامين كد بسيار سريع لازم شده است. يك دليل اينكه ناجوري از اجراعات كامپايلر وجود دارد. اينها كامپايلرهاي بيهنه عالي براي بعضي پلاتفرمها هستند اما كامپايلرهاي موجود براي بعضي پلاتفرمهاي ديگر بسياري خواسته ها را ترك ميكنند. دومين دليل و شايد بسيار مهم اين هست که كامپايلرهاي مرسوم كه فاقد اطلاعات معنايي هستند و بنابراين محدود شده اند به قدرت دگرگونييا تغيير. يك ديدگاه ايجاد شده كه دارد ثابت شده بكلي موثر در چيره شدن به هر دوي اين محدوديتها استفاده نمودن توليد كننده هاي كتابخانه میباشد. اين سيستمها استفاده معنايي در اطلاعات براي بكار بردن دگرگون سازي در تمام سطوح از تجريد مهیا ميسازند. بيشتر توليدات كتابخانه قدرتمند نيستند فقط بهينه ساز برنامه همان سيستمهاي طراحي الگوريتم هستند.
ATLAS[21],PHiPAC[2],FFTW[7],SPIRAL[23] در طول بهترين توليد كننده هاي كتابخانه دانسته شده میباشند. ATLAS ,PHiPAC توليد ميكنند روتينهاي جبري خطي را و پردازش بهينه را در پياده سازي از ضرب ماتريس در ماتريس فوكس ميكنند. در مدت نصب مقادير پارامتر از يك پياده سازي ضرب يك ماتريس بطوريكه اندازه تيله و مقداري از حلقه باز شده كه تحويل ميدهد بهترين انجام معين كننده هويت استفاده جستجوي تجربي. اين جستجو پردازش ميشود با توليد كردن ورژنهاي گوناگون از ضرب ماتريسي كه تنها اختلاف دارند در مقدار پارامتر كه هست شروع به جستجو. در تقريب جستجوي گسترده هست استفاده شده براي پيدا كردن بهترين مقادير پارامتر. دو سيستم ديگر اشاره دارند روي SPIRAL,FFTW توليد ميكنند كتابخانه هاي پردازش كننده تنها را. فضاي جستجو در SPIRAL,FFTW هست همچنين بزرگتر براي جستجوي گسترده براي ممكن شدن. بنابراين اين سيستمها جستجو ميكنند با استفاده هيوريستيك مثل برنامه نويسي دايناميك [۷,۱۲] يا الگوريتمهاي ژنتيك [۱۹].
در اين مقاله ما مرور ميكنيم مسئله از توليد كردن روتينهاي سورت سرعت بالا را. يك تفاوت ما بين سورت كردن و پياده سازي الگوريتم پياده سازي شده بوسيله بوسيله توليدات كتابخانه اي فقط اشاره كرده هست اين اجرا از الگوريتمها انها انجام ابزار هست به طور كامل تعيين شده بوسيله مشخصاتي از ماشين هدف و اندازه اي از داده ورودي اما نيست بوسيله ديگر مشخصات از داده ورودي. به هر حال در حالتي از سورت اجرا همچنين وابسته است در ديگر فاكتورهاي مثل توزيع داده براي سورت شدن. در حقيقت بحث پايين سورت مرج چند راهي را اجرا ميكند بسيار خوب در بعضي كلاسهايي ازمجموعه هاي داده ورودي كه radix سورت اجرا ميكند بطور غير كافي در اين مجموعه. براي ديگر كلاسهاي مجموعه داده ما رعايت ميكنيم موقعيت معكوس را. بنابراين ديدگاه توليد كننده هاي امروزي هست مفيد براي بهينه سازي مقادير پارامتر از الگوريتمهاي سورت اما نيست براي انتخاب بهترين الگوريتم براي گرفتن ورودي. براي تبديل به مشخصات از مجموعه ورودي در [۱۴] ما استفاده كرديم توزيع اي از داده ورودي براي انتخاب الگوريتم سورت. اگر چه اين ديدگاه هست ثابت شده كه بكلي موثر است اجراي اخر هست محدود شده با اجرايي از الگوريتمهاي سورت مثل سورت مرج چند راهي وسورت سريع و سورت radix هستند انتخاب شده در [۱۴] كه ميتواند انتخاب شده باشد در زمان اجرا.
در اين مقاله ما ادامه ميدهيم و عموميت ميدهيم به ديدگاه سادهترمان[۱۴] . توليد كتابخانه جديد ما توليد ميكند اجرايي از الگوريتمهاي سورت مركب رادر فرمي از يك سلسله مراتبي از سورتهاي اوليه كه مخصوص شكل نهايي توسعه شده در چهره سلسله مرتبي از ماشين هدف و مشخصات داده ورودي. درك مستقيم باقي كار اين است كه الگوريتمهاي سورت مختلف اجرا ميكنند به صورت متفاوت توسعه دادن را در مشخصات اي از هر بخش و مثل يك نتيجه و الگوريتم سورت بهينه مي بايستي باشد تركيبي از اين الگوريتمهاي سورت مختلف. گذشته از اين سورتهاي اوليه توليد كردند كد شامل انتخاب اوليه كه به صورت دايناميك انتخاب ميكند مخلوط الگوريتم مثل يك تابع از مشخصات اي از داده در هر بخش را. در مدت زمان نصب ديدگاه كتابخانه جديد ما جستجو ميكند براي تابعي كه نگاشت ميكند مشخصات اي از ورودي را براي بهترين الگوريتمهاي سورت با استفاده از الگوريتمهاي ژنتيك [۳,۸,۱۶,۲۲]. الگوريتمهاي ژنتيك استفاده شده اند براي جستجو براي اختصاص دادن فرمول در SPIRAL[19] و براي بهينه سازي كامپايلر رسمي [۴,۶,۲۰].

بخشی از مقاله انگلیسی:

Abstract

The growing complexity of modern processors has made the generation of highly efficient code increasingly difficult. Manual code generation is very time consuming, but it is often the only choice since the code generated by today’s compiler technology often has much lower performance than the best hand-tuned codes. A promising code generation strategy, implemented by systems like ATLAS, FFTW, and SPIRAL, uses empirical search to find the parameter values of the implementation, such as the tile size and instruction schedules, that deliver near-optimal performance for a particular machine. However, this approach has only proven successful on scientific codes whose performance does not depend on the input data. In this paper we study machine learning techniques to extend empirical search to the generation of sorting routines, whose performance depends on the input characteristics and the architecture of the target machine.

We build on a previous study that selects a ”pure” sorting algorithm at the outset of the computation as a function of the standard deviation. The approach discussed in this paper uses genetic algorithms and a classifier system to build hierarchically-organized hybrid sorting algorithms capable of adapting to the input data. Our results show that such algorithms generated using the approach presented in this paper are quite effective at taking into account the complex interactions between architectural and input data characteristics and that the resulting code performs significantly better than conventional sorting implementations and the code generated by our earlier study. In particular, the routines generated using our approach perform better than all the commercial libraries that we tried including IBM ESSL, INTEL MKL and the C++ STL. The best algorithm we have been able to generate is on the average 26% and 62% faster than the IBM ESSL in an IBM Power 3 and IBM Power 4, respectively. ∗This work was supported in part by the National Science Foundation under grant CCR 01-21401 ITR; by DARPA under contract NBCH30390004; and by gifts from INTEL and IBM. This work is not necessarily representative of the positions or policies of the Army or Government.

۱ Introduction

Although compiler technology has been extraordinarily successful at automating the process of program optimization, much human intervention is still needed to obtain highquality code. One reason is the unevenness of compiler implementations. There are excellent optimizing compilers for some platforms, but the compilers available for some other platforms leave much to be desired. A second, and perhaps more important, reason is that conventional compilers lack semantic information and, therefore, have limited transformation power. An emerging approach that has proven quite effective in overcoming both of these limitations is to use library generators. These systems make use of semantic information to apply transformations at all levels of abstractions. The most powerful library generators are not just program optimizers, but true algorithm design systems.

ATLAS [21], PHiPAC [2], FFTW [7] and SPIRAL [23] are among the best known library generators. ATLAS and PHiPAC generate linear algebra routines and focus the optimization process on the implementation of matrix-matrix multiplication. During the installation, the parameter values of a matrix multiplication implementation, such as tile size and amount of loop unrolling, that deliver the best performance are identified using empirical search. This search proceeds by generating different versions of matrix multiplication that only differ in the parameter value that is being sought. An almost exhaustive search is used to find the best parameter values. The other two systems mentioned above, SPIRAL and FFTW, generate signal processing libraries. The search space in SPIRAL or FFTW is too large for exhaustive search to be possible. Thus, these systems search using heuristics such as dynamic programming [7, 12], or genetic algorithms [19].

In this paper, we explore the problem of generating highquality sorting routines. A difference between sorting and the algorithms implemented by the library generators just mentioned is that the performance of the algorithms they implement is completely determined by the characteristics of the target machine and the size of the input data, but not by other characteristics of the input data. However, in the case of sorting, performance also depends on other factors such as the distribution of the data to be sorted. In fact, as discussed below, multiway merge sort performs very well on some classes of input data sets while radix sort performs 1 Proceedings of the International Symposium on Code Generation and Optimization (CGO’۰۵) ۰-۷۶۹۵-۲۲۹۸-X/05 $ 20.00 IEEE poorly on these sets. For other data set classes we observe the reverse situation. Thus, the approach of today’s generators is useful to optimize the parameter values of a sorting algorithm, but not to select the best sorting algorithm for a given input. To adapt to the characteristics of the input set, in [14] we used the distribution of the input data to select a sorting algorithm. Although this approach has proven quite effective, the final performance is limited by the performance of the sorting algorithms – multiway merge sort, quicksort and radix sort are the choices in [14] – that can be selected at run time.

In this paper, we extend and generalize our earlier approach [14]. Our new library generator produces implementations of composite sorting algorithms in the form of a hierarchy of sorting primitives whose particular shape ultimately depends on the architectural features of the target machine and the characteristics of the input data. The intuition behind this is that different sorting algorithms perform differently depending on the characteristic of each partition and as a result, the optimal sorting algorithm should be the composition of these different sorting algorithms. Besides the sorting primitives, the generated code contains selection primitives that dynamically select the composite algorithm as a function of the characteristics of the data in each partition. During the installation time, our new library approach searches for the function that maps the characteristics of the input to the best sorting algorithms using genetic algorithms [3, 8, 16, 22]. Genetic algorithms have also been used to search for the appropriate formula in SPIRAL [19] and for traditional compiler optimizations [4, 6, 20].

 

ارسال دیدگاه

نشانی ایمیل شما منتشر نخواهد شد.