امروز: پنجشنبه 22 آذر 1397
دسته بندی محصولات
بخش همکاران
بلوک کد اختصاصی

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

دانلود مقاله ترجمه شده سورت بهینه با الگوریتمهای ژنتیک دسته: کامپیوتر و IT
بازدید: 2 بار
فرمت فایل: pdf
حجم فایل: 2240 کیلوبایت
تعداد صفحات فایل: 31

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

قیمت فایل فقط 16,500 تومان

خرید

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

چکیده
رشد پیچیدگی پردازش های مدرن تولید كد موثر مناسب را بصورت افزایشی سخت ساخته است. تولید كد به صورت دستی بسیار زمان صرف كننده می باشد اما آن بارها انتخاب میشوند به طوریكه كد تولید شده بوسیله تكنولو‍‍‍‍ژی كامپایلرهای امروزی بارها اجرای پایین تری نسبت به بهترین كدهای آماده شده دستی دارند. یك نولید از استراتژی تولید كد انجام گرفته شده بوسیله سیستم های شبیه ATLAS,FFTW و SPIRAL كه جستجوی تجربی را برای پیدا كردن مقادیر پارامتر از کارایی را استفاده كرده است به طوریكه اندازه تیله و زمانبندی آموزش كه تحویل انجام بهینه برای یك ماشین مخصوص می باشد. به هر حال این دیدگاه دارد به تنهایی به طور كامل ثابت میكند در كدهای علمی اجرا به داده ورودی وابسته نیست. در این مقاله ما مطالعه میكنیم تكنیكهای یادگیری ماشین را برای توسعه جستجوی ترتیبی برای تولیدی از روتینهای سورت كردن كه اجرا در مشخصات ورودی و معماری از ماشین هدف وابسته است. ما ساختیم در مطالعه قبلی كه یك الگوریتم سورت خالص در اغازی از محاسبات مثل تابعی از انحراف معیار انتخاب کنیم. دیدگاهی که بحث میكنیم در این مقاله الگوریتمهای ژنتیك و یك سیستم طبقه بندی با ساختار بصورت سلسله مراتبی ساخته شده الگوریتمهای سورت تلفیقی توانا از تبدیل كردن داده ورودی استفاده میكند. نتایج ما نشان میدهد كه الگوریتمهای تولید شده با استفاده از دیدگاه ارائه شده در این مقاله هستند سرع و موثر در گرفتن داخل اكانت اثرات متقابل پیچیده ما بین معماری و مشخصات داده ورودی و كد نتیجه بسیار مهم بهتر از اجراعات سورت مرسوم و كد تولید شده با مطالعه اسان ما اجرا میكند. به ویژه روتینهای تولید شده با دیدگاه ما اجرا میكند بهتر از تمام كتابخانه های تجاری كه ما ازمایش كردیم مثل IBM ESSL,INTEL MKL و C++ STL. بهترین الگوریتم ما دارد توانایی تولید ای در معدل 26% و 62% سریعتر از IBM ESSL در یك IBM PAWER 3 و IBM PAWER 4 بترتیب را دارد.
1 مقدمه
اگر چه تكنولوژی كامپایلر فوق العاده در پردازش خودكاراز بهینه سازی برنامه كامل شده است و بیشتر مداخلات انسانی هنوز هست برای تامین كد بسیار سریع لازم شده است. یك دلیل اینكه ناجوری از اجراعات كامپایلر وجود دارد. اینها كامپایلرهای بیهنه عالی برای بعضی پلاتفرمها هستند اما كامپایلرهای موجود برای بعضی پلاتفرمهای دیگر بسیاری خواسته ها را ترك میكنند. دومین دلیل و شاید بسیار مهم این هست که كامپایلرهای مرسوم كه فاقد اطلاعات معنایی هستند و بنابراین محدود شده اند به قدرت دگرگونییا تغییر. یك دیدگاه ایجاد شده كه دارد ثابت شده بكلی موثر در چیره شدن به هر دوی این محدودیتها استفاده نمودن تولید كننده های كتابخانه میباشد. این سیستمها استفاده معنایی در اطلاعات برای بكار بردن دگرگون سازی در تمام سطوح از تجرید مهیا میسازند. بیشتر تولیدات كتابخانه قدرتمند نیستند فقط بهینه ساز برنامه همان سیستمهای طراحی الگوریتم هستند.
ATLAS[21],PHiPAC[2],FFTW[7],SPIRAL[23] در طول بهترین تولید كننده های كتابخانه دانسته شده میباشند. ATLAS ,PHiPAC تولید میكنند روتینهای جبری خطی را و پردازش بهینه را در پیاده سازی از ضرب ماتریس در ماتریس فوكس میكنند. در مدت نصب مقادیر پارامتر از یك پیاده سازی ضرب یك ماتریس بطوریكه اندازه تیله و مقداری از حلقه باز شده كه تحویل میدهد بهترین انجام معین كننده هویت استفاده جستجوی تجربی. این جستجو پردازش میشود با تولید كردن ورژنهای گوناگون از ضرب ماتریسی كه تنها اختلاف دارند در مقدار پارامتر كه هست شروع به جستجو. در تقریب جستجوی گسترده هست استفاده شده برای پیدا كردن بهترین مقادیر پارامتر. دو سیستم دیگر اشاره دارند روی SPIRAL,FFTW تولید میكنند كتابخانه های پردازش كننده تنها را. فضای جستجو در SPIRAL,FFTW هست همچنین بزرگتر برای جستجوی گسترده برای ممكن شدن. بنابراین این سیستمها جستجو میكنند با استفاده هیوریستیك مثل برنامه نویسی داینامیك [7,12] یا الگوریتمهای ژنتیك [19].
در این مقاله ما مرور میكنیم مسئله از تولید كردن روتینهای سورت سرعت بالا را. یك تفاوت ما بین سورت كردن و پیاده سازی الگوریتم پیاده سازی شده بوسیله بوسیله تولیدات كتابخانه ای فقط اشاره كرده هست این اجرا از الگوریتمها انها انجام ابزار هست به طور كامل تعیین شده بوسیله مشخصاتی از ماشین هدف و اندازه ای از داده ورودی اما نیست بوسیله دیگر مشخصات از داده ورودی. به هر حال در حالتی از سورت اجرا همچنین وابسته است در دیگر فاكتورهای مثل توزیع داده برای سورت شدن. در حقیقت بحث پایین سورت مرج چند راهی را اجرا میكند بسیار خوب در بعضی كلاسهایی ازمجموعه های داده ورودی كه radix سورت اجرا میكند بطور غیر كافی در این مجموعه. برای دیگر كلاسهای مجموعه داده ما رعایت میكنیم موقعیت معكوس را. بنابراین دیدگاه تولید كننده های امروزی هست مفید برای بهینه سازی مقادیر پارامتر از الگوریتمهای سورت اما نیست برای انتخاب بهترین الگوریتم برای گرفتن ورودی. برای تبدیل به مشخصات از مجموعه ورودی در [14] ما استفاده كردیم توزیع ای از داده ورودی برای انتخاب الگوریتم سورت. اگر چه این دیدگاه هست ثابت شده كه بكلی موثر است اجرای اخر هست محدود شده با اجرایی از الگوریتمهای سورت مثل سورت مرج چند راهی وسورت سریع و سورت radix هستند انتخاب شده در [14] كه میتواند انتخاب شده باشد در زمان اجرا.
در این مقاله ما ادامه میدهیم و عمومیت میدهیم به دیدگاه سادهترمان[14] . تولید كتابخانه جدید ما تولید میكند اجرایی از الگوریتمهای سورت مركب رادر فرمی از یك سلسله مراتبی از سورتهای اولیه كه مخصوص شكل نهایی توسعه شده در چهره سلسله مرتبی از ماشین هدف و مشخصات داده ورودی. درك مستقیم باقی كار این است كه الگوریتمهای سورت مختلف اجرا میكنند به صورت متفاوت توسعه دادن را در مشخصات ای از هر بخش و مثل یك نتیجه و الگوریتم سورت بهینه می بایستی باشد تركیبی از این الگوریتمهای سورت مختلف. گذشته از این سورتهای اولیه تولید كردند كد شامل انتخاب اولیه كه به صورت داینامیك انتخاب میكند مخلوط الگوریتم مثل یك تابع از مشخصات ای از داده در هر بخش را. در مدت زمان نصب دیدگاه كتابخانه جدید ما جستجو میكند برای تابعی كه نگاشت میكند مشخصات ای از ورودی را برای بهترین الگوریتمهای سورت با استفاده از الگوریتمهای ژنتیك [3,8,16,22]. الگوریتمهای ژنتیك استفاده شده اند برای جستجو برای اختصاص دادن فرمول در SPIRAL[19] و برای بهینه سازی كامپایلر رسمی [4,6,20].
نتایج ما نشان میدهد كه دیدگاهمان هست بسیار موثر. بهترین الگوریتم ما داریم تولید شده هست در معدل 36% سریعتر از بهترین روتین سورت خالص و شروع با 45% سریعتر. روتین سورت ما اجرا میكند یهتر از تمام كتابخانه های تجاری كه ما سعی میكنیم شامل IBM ESSL,INTEL MKL و STL از C++. در معدل روتینهای تولید شده 26% و62% سریعتر از IBM ESSL در یك IBM PAWR3 و IBM POWER 4 به ترتیب.
نتیجه از این مقاله سازمان دهی شده مثل زیر. بخش 2 بحث میكند اولیه ای كه ما استفاده كردیم برای ساختن الگوریتمهای سورت. بخش 3 مرور میكند چرا ما اتنخاب كردیم الگوریتمهای ژنتیك را برای جستجو و مرور بعضی جزییات از الگوریتم ای كه ما انجام دادیم. بخش 4 نشان میدهد نتایج اجرا شده را. بخش 5 خلاصه مطالب چگونگی استفاده الگوریتمهای ژنتیك را برای تولید یك سیستم طبقه بندی برای روتینهای سورت میباشد و سرانجام بخش 6 ارائه میكند نتایجمان را.
2 سورت اولیه
در این بخش ما توضیح میدهیم بلوكهای ساخته شده از الگوریتمهای سورت تركیبییمان را. این اولییه ها انتخاب شده اند بر مبنای ازمایش با الگوریتمهای سورت مختلف و مطالعه ای از فاكتورهای كه اثر میكنند به اجرایشان. یك خلاصه از نتایج این ازمایشات در شكل 1 ارائه شده است كه كشیده شده زمان اجرا از سه الگوریتم سورت در برابر انحراف معیار از كلیدهای سورت شده.

نتایج نشان داده شده برای SUN ULTRASPARC III و برای دو اندازه از مجموعه داده 2 میلیون و 16 میلیون. سه الگوریتم هستند: QUICKSORT [10,17] و CACHE-CONSCIOUS RADIX SORT (CC-RADIX)[11] و MULTIWAY MERG SORT[13]. شكل 1 نشان میدهد كه برای 2M ركورد بهترین الگوریتم سورت هست QUICKSORT یا CC-RADIX زمانی كه برای 16M ركورد MULTIWAY MERGE SORT یا CC-RADIX هستند بهترین االگوریتم. مشخصات ورودی كه تعیین شده زمانی كه CC-RADIX هست بهترین الگوریتم هست انحراف معیار از ركوردها برای سورت شدن. CC-RADIX هست بهتر زمانی كه انحراف معیار از ركوردها هست بالا برای اینكه اگر مقادیر از عناصر در داده ورودی هست متمركز شده اند گرداگرد بعضی مقادیر ان هست بسیار شبیه به اینكه بیشتر عناصر در بعضی از BUCKET ها باشند . بنابراین بیشتر پارتیشنها سبقت میگیرند برای بكار بردن قبل از BUCKET های مناسب داخل كش و بنابراین بیشتر كش های فاقد هستند موجب شده در مدت پارتیشن بندی. نتایج اجرا در دیگر پلتفرمها نشان میدهد كه تمایل عمومی از الگوریتمها هست همیشه یكسان اما نقطه متقاطع اجرا اتفاق می افتد در نقاط مختلف در پلت فرمهای مختلف.
ان میفهماند برای بسیاری سالها كه اجرا QUICKSORT میتواند بهبود شود زمانی كه تركیب شده با دیگر الگوریتمها [17]. ما تایید میكنیم به صورت ازمایشی كه وقتی پارتیشن هست كوچكتر از یك استانه خوب (كه مقدار وابسته است در پلتفرم هدف) ان هست بهترین برای استفاده INSERTION SORT یا ذخیره داده در رجیسترها و سورت بوسیله تعویض مقادیر ما بین ریجسترها [14] به جای ادامه دادن به صورت بازگشتی بكار بردن quicksort. Register sort هست یك الگوریتم كد مستقیم كه اجرا میكند مقایسه-و-تعویض از مقادیر سورت شده در رجیسترهای پروسسور [13].
Darlington [5] معرفی كرده ایده ای از سورتهای اولیه و تشخیص merge sort و quicksort مثل دو الگوریتم اولیه. در این مقاله ما جستجو كیكنیم برای یك الگوریتم بهینه بوسیله ساختن الگوریتمهای سورت تركیبی. ما استفاده كردیم دو نوع از اولیه برای ساختن الگوریتمهای سورت تازه: سورت كردن و انتخاب اولیه. سورتهای اولیه ارائه میكنند یك الگوریتم سورت خالص را كه شامال پارتیشن بندی داده است به طوریكه مثل radix sort و merge sort و quicksort. انتخاب اولیه ارائه میكند یك پروسه برای اجرا شدنه در زمان اجرای كه به صورت داینامیك تصمیم میگیرد كه الگوریتم سورت را برای بكار بردن.
الگوریتمهای سورت تركیبی مطرح میكنند در این مقاله فرض شده است كه داده هست سورت شده در پی در پی حافظه محلی. داده هست به صورت بازگشتی پارتیشن شده بوسیله یكی از 4 متدهای پارتیشن بندی. پارتیشن بندی بازگشتی خاتمه میدهد زمانی كه یك الگوریتم سورت شكل گرفت هست بكار میرود در پارتیشن. ما الان توضیح میدهیم 4 پارتیشن بندی اولیه را در زیر بوسیله یك توضیح از دو سورت اولیه شكل گرفته. برای هر اولیه ما همچنین تشخیص میدهیم مقادیر پارامتری كه باید باشد جستجو شده با تولیدات كتابخانه.

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

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. 1 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’05) 0-7695-2298-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].

قیمت فایل فقط 16,500 تومان

خرید

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

نظرات کاربران در مورد این کالا
تا کنون هیچ نظری درباره این کالا ثبت نگردیده است.
ارسال نظر