دانلود رایگان مقاله انگلیسی سورت بهینه با الگوریتمهای ژنتیک به همراه ترجمه فارسی
| عنوان فارسی مقاله: | سورت بهینه با الگوریتمهای ژنتیک |
| عنوان انگلیسی مقاله: | Optimizing Sorting with Genetic Algorithms |
| رشته های مرتبط: | مهندسی کامپیوتر، مهندسی نرم افزار، مهندسی الگوریتم ها و محاسبات |
| فرمت مقالات رایگان | مقالات انگلیسی و ترجمه های فارسی رایگان با فرمت PDF میباشند |
| کیفیت ترجمه | کیفیت ترجمه این مقاله خوب میباشد |
| کد محصول | F14 |
|
مقاله انگلیسی رایگان |
دانلود رایگان مقاله انگلیسی |
|
ترجمه فارسی رایگان |
دانلود رایگان ترجمه مقاله |
| جستجوی ترجمه مقالات | جستجوی ترجمه مقالات کامپیوتر |
|
بخشی از ترجمه فارسی: چکیده |
|
بخشی از مقاله انگلیسی: 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]. |