|
دانلود مقاله ترجمه شده سورت بهینه با الگوریتمهای ژنتیک سورت بهینه با الگوریتمهای ژنتیک
|
 |
| دسته بندی | کامپیوتر و IT |
| فرمت فایل | |
| حجم فایل | 2240 کیلو بایت |
| تعداد صفحات فایل | 31 |
بخشی از ترجمه فارسی:
چکیده
رشد پیچیدگی پردازش های مدرن تولید کد موثر مناسب را بصورت افزایشی سخت ساخته است. تولید کد به صورت دستی بسیار زمان صرف کننده می باشد اما آن بارها انتخاب میشوند به طوریکه کد تولید شده بوسیله تکنولوژی کامپایلرهای امروزی بارها اجرای پایین تری نسبت به بهترین کدهای آماده شده دستی دارند. یک نولید از استراتژی تولید کد انجام گرفته شده بوسیله سیستم های شبیه 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].
