دانلود مقاله ISI انگلیسی شماره 7844 + ترجمه فارسی
ترجمه فارسی عنوان مقاله

افزایش موازات داده ها برای بهینه سازی مومیایی مورچه در پردازنده های گرافیکی

عنوان انگلیسی
Enhancing data parallelism for Ant Colony Optimization on GPUs
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی ترجمه فارسی
7844 2013 10 صفحه PDF 22 صفحه WORD
دانلود فوری مقاله + ترجمه آماده
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Parallel and Distributed Computing, Volume 73, Issue 1, January 2013, Pages 42–51

فهرست مطالب ترجمه فارسی
چکیده

کلمات کلیدی

1.مقدمه

2. زمینه

2.1. بهینه سازی مومیای مورچه برای مشکل فروشنده مسافرتی

2.2.مدل برنامه نویسیCUDA

3. تکنیک های میزان سازی و طراحی کد

الگوریتم 1 نسخه ترتیبیAS برایTSP 

3.1. پیشنهادهای قبلی ساخت تور

3.1.1. پایهCPU

3.2.رویکرد ساخت و ساز تور ما براساس موازات داده است

شکل2. رویکرد موازی داده در هسته ساخت تور

3.2.1محاسبه ماتریسselection_info رویGPU

3.2.2رویکرد موازی داده

3.2.3 :I-Roulette.یک روش انتخاب جایگزین

شکل3. یک روش جایگزین برای افزایش موازی در فرآیند انتخاب.

الگوریتم 3 روش I-Roulette. فرض بر این است که این کد توسط موضوعات به عنوان بسیاری ازشهرها انجام می شود. یک شماره تصادفی برای هر گره ارسال کنید. 

شکل4. تجمع فرومون با دستورالعمل اتمی 

3.3مرحله به روز رسانی فرومون

شکل5. پراکندگی برای جمع آوری تحول برای سپرده فرومون.

جدول1. ویژگی های سخت افزاری برای پردازنده اینتل Xeon و پردازنده گرافیکی Nvidia Tesla C2050 ما برای اجرای آزمایشات ما استفاده شده است.

جدول2 . خلاصه ای از ویژگی های اصلی در نمونه های معیار ما از کتابخانه TSPLIB.  شهرهای  تعداد شهرستانها در نمودار است، و  طول  بهترین طول تور است، یعنی حداقل راه حل بر اساس فاصله دوبعدی اقلیدسی است.

4.1. معیارسنجی

5. سنجش عملکرد

5.1 ارزیابی مرحله ساخت تور

5.1.1 ارزیابی هسته انتخاب-اطلاعات

شکل6. هنگام استفاده از دستورالعمل CUDA powf و __powf از عملیات نقطه شناور Giga در هر ثانیه (GFLOPS) در سیستم Tesla C2050 GPU برای هسته انتخاب-اطلاعات.

5.1.2 تنظیم رویکرد موازی داده ما

جدول3.زمان اجرای (ms) در2050 Tesla C. ما تعداد مورچه های کارگر و نمونه های معیار را تعدیل می کنیم (به این معنی که به علت محدودیت های ثبت نام در دسترس نیست).

شکل7. فاکتور فوری در سکوهای مختلف سخت افزاری (CPU vs. GPU) و فعال کردن روشهای مختلف GPU برای هسته ساخت تور (RW برای چرخش رولت، IR برای رولت مستقل) است.

5.2 ارزیابی هسته به روز رسانی فرومون

5.2.1. ارزیابی استراتژی های مختلف الگوریتم GPU

جدول4. زمان اجرا (ms.) در Tesla C2050 برای پیاده سازی به روز رسانی فرومون.

5.2.2. GPU در مقابل CPU 

شکل8. زمان اجرا (ms) بر روی یک پردازنده Intel Xeon E5620 و گرافیک Nvidia Tesla C2050 برای مرحله به روز رسانی فرومون. ما نمونه معیار TSPLIB را برای افزایش تعداد شهرهای (IR برای مستقل رولت) تعدیل می کنیم.

5.3 کیفیت راه حل

شکل9. دقت راه حل (به طور متوسط بیش از 1000 تکرار). فاصله اطمینان 95٪ در بالای میله ها نشان داده شده است (RW برای رولت چرخ، IR برای مستقل رولت).

6. کار مرتبط

6.1 پیاده سازی موازی

6.2. پیاده سازی GPU

6.2.1. Cg

6.2.2 CUDA 

7. نتیجه گیری و کار آینده
ترجمه کلمات کلیدی
متا اکتشافی - برنامه نویسی - بهینه سازی کلونی مورچه - تجزیه و تحلیل عملکرد
کلمات کلیدی انگلیسی
ترجمه چکیده
واحد پردازش گرافیکی (GPU) ها طی پنج سال گذشته به معماری بسیار موازی و کاملا برنامه ریزی شده تبدیل شده است و ظهور CUDA کاربرد آنها را در بسیاری از برنامه های کاربردی دنیای واقعی تسهیل کرده است. در این مقاله ما با استفاده از یک GPU بهینه سازی مورچه Colony (ACO)، یک روش بهینه سازی جمعیتی که شامل دو مرحله عمده است: ساخت تور و به روز رسانی فروم است. به دلیل ماهیت ذاتی آن، ACO برای اجرای GPU بسیار مناسب است، اما با توجه به الگوهای دسترسی نامنظم حافظه، چالش های مهمی نیز ایجاد می کند. سهم ما در این زمینه سه برابر است: (1) یک طرح همپوشانی داده برای ساخت تور در قالب پردازنده های گرافیکی، (2) استراتژی های برنامه ریزی گرافیکی جدید برای مرحله به روز رسانی فرومون و (3) یک مکانیزم جدید به نام I-Roulette برای تکرار چرخش کلاسیک در حالی که بهبود موازی GPU. پیاده سازی ما منجر به افزایش کارایی بیش از 20x برای هر یک از دو مرحله الگوریتم ACO به عنوان TSP در مقایسه با نسخه همپوشانی پس از آن در حال اجرا بر روی یک CPU بالا پایان تک رشته مشابه است. علاوه بر این، بحث گسترده ای که در مورد راه های مختلف پیاده سازی در GPU ها متمرکز شده است نشان می دهد که راه برای مقابله با اجزای وابسته به گراف موازی شده است. این به نوبه خود، یک منطقه گسترده تر از تحقیق را پیشنهاد می دهد، که در آن طراحان الگوریتمی ممکن است یاد بگیرند که روش های مشابه بهینه سازی را برای معماری GPU سازگار کنند.
ترجمه مقدمه
بهینه سازی مجتمع مورچه ](ACO)12[ روش جستجوی مبتنی بر جمعیت است که القاء رفتار مورچه های واقعی است. این ممکن است به طیف گسترده ای از مشاغل [8،2] اعمال شود، که بسیاری از آنها طبیعت گرافی است. این نخستین بار توسط Dorigo و همکاران در مورد مشکل فروشندگان مسافرتی (TSP) [19] مورد استفاده قرار گرفت. [10،11]. در واقع، مورچه های شبیه سازی شده، راه حل هایی برای TSP در قالب تورها ایجاد می کنند. مورچه های مصنوعی عوامل ساده ای هستند که تور را به صورت موازی و احتمالا ساخته می شوند. آنها در این کار با مسیرهای شبیه سازی شده و اطلاعات اکتشافی هدایت می شوند. آنها در این کار با مسیرهای فرومون (یک ماده شیمیایی که توسط حیوانات تولید می شود) شبیه سازی شده و اطلاعات اکتشافی هدایت می شوند. مسیرهای فرومون یک جزء اساسی الگوریتم هستند، زیرا آنها ارتباطات غیرمستقیم میان عوامل را از طریق محیط زیست خود، یک فرآیند شناخته شده به عنوان فاجعه گرایی تسهیل می کنند [9]. برای جزئیات بیشتر در مورد این فرایندها، خواننده را به [12] ارجاع می دهیم. الگوریتم ACO مبتنی بر جمعیت است، یعنی مجموعه ای از عوامل همکاری برای یافتن راه حل بهینه (یا حداقل رضایت بخش). چنین رویکردهایی برای پردازش موازی مناسب هستند، اما موفقیت آنها به شدت به ماهیت خاص بستگی دارد مشکلات و سخت افزار موجود در دسترس است. چند راهبرد حل جدول برای الگوریتم ACO در معماری مشترک و توزیع شده حافظه [28،18،21] ارائه شده است. واحد پردازش گرافیکی (GPU) موضوع مورد قابل توجه در محاسبات با کارایی بالا است. برای برنامه های کاربردی با همبستگی فراوان، پردازنده های گرافیکی بالاتر از پردازنده های محاسباتی بالاتر از پردازنده های تاخیری گرا را ارائه می دهند، بنابراین افزایش کارایی بالقوه در مواقع مساوی موثر است [14]. ارتباط خاصی با ما در تلاش است تا الگوریتم ACO را بر روی پردازنده های گرافیکی به صورت موازی بسازد. تا کنون، این رویکردها بر تسریع ساخت ساخت تور، گامی که توسط هر مورچه انجام شده است، با استفاده از رویکرد موازی کاری مبتنی بر کار، با قرار دادن فرومون بر روی CPU] 13،3،20] متمرکز شده است. در این مقاله، اولین الگوریتم ACO به طور کامل توسعه یافته برای مشکل فروشندگان مسافرتی (TSP) در GPU ها ارائه شده است، که هر دو مراحل به صورت موازی شده اند: ساخت تور و به روز رسانی فرومون. یک رویکرد همپوشانی داده که بهتر برای مدل موازی GPU مناسب است، برای افزایش عملکرد در مرحله اول مورد استفاده قرار می گیرد و چندین الگوهای طراحی GPU برای موازی سازی مرحله دوم مورد ارزیابی قرار می گیرند. مشارکت عمده ما عبارتند از: 1. برای اطلاعات بیشتر ما، این اولین طرح داده موازی در GPU ها برای مرحله ساخت ACO تور است. طراحی ما دو نوع مختلف مورچه های مجازی را پیشنهاد می کند: ملکه مورچه (در ارتباط با بلوک موضوعات CUDA ) و مورچه های کارگر (مرتبط با موضوعات CUDA). 2. ما روش I-Roulette (مستقل رولت) را برای تکرار انتخاب رول کلاسیک در حالی که بهبود موازی گرافیکی را معرفی می کنیم معرفی می کنیم. 3. ما در مورد اجرای مرحله به روز رسانی فرومون در GPU ها، با استفاده از عملیات اتمی یا سایر گزینه های GPU صحبت می کنیم. 4. ما یک تحلیل عمیق از هر دو مرحله الگوریتم ACO برای نمونه های مختلفی از مشکل TSP ارائه می دهیم. چند پارامتر GPU برای رسیدن به یک عامل سرعت بالا تا 21 × برای مرحله ساخت تور و یک عامل افزایش سرعت 20 × برای مرحله به روز رسانی فرومون تنظیم شده است. 5. دقت راه حل به دست آمده توسط الگوریتم های GPU ما با کد تکراری که در [12] ارائه شده است و با استفاده از TSPLIB مقایسه می شود. بقیه مقاله به شرح زیر است: ما به طور خلاصه بهینه سازی مومیایی Colony برای TSP و محاسبه معماری یکپارچه دستگاه (CUDA) را از NVIDIA در بخش 2 معرفی می کنیم. در بخش 3 ما طرح های GPU را برای مراحل اصلی الگوریتم ACO ارائه می کنیم. روش تجربی ما در بخش 4 قبل از توصیف ارزیابی عملکرد الگوریتم ما در بخش 5 مشخص شده است. دیگر راهبردهای الگوریتم برای الگوریتم ACO در بخش 6 توضیح داده شده است، قبل از اینکه ما یافته های خود را خلاصه کنیم و با پیشنهادات برای کارهای آینده نتیجه گیری کنیم.
پیش نمایش مقاله
پیش نمایش مقاله افزایش موازات داده ها برای بهینه سازی مومیایی مورچه در پردازنده های گرافیکی

چکیده انگلیسی

Graphics Processing Units (GPUs) have evolved into highly parallel and fully programmable architecture over the past five years, and the advent of CUDA has facilitated their application to many real-world applications. In this paper, we deal with a GPU implementation of Ant Colony Optimization (ACO), a population-based optimization method which comprises two major stages: tour construction and pheromone update. Because of its inherently parallel nature, ACO is well-suited to GPU implementation, but it also poses significant challenges due to irregular memory access patterns. Our contribution within this context is threefold: (1) a data parallelism scheme for tour construction tailored to GPUs, (2) novel GPU programming strategies for the pheromone update stage, and (3) a new mechanism called I-Roulette to replicate the classic roulette wheel while improving GPU parallelism. Our implementation leads to factor gains exceeding 20x for any of the two stages of the ACO algorithm as applied to the TSP when compared to its sequential counterpart version running on a similar single-threaded high-end CPU. Moreover, an extensive discussion focused on different implementation paths on GPUs shows the way to deal with parallel graph connected components. This, in turn, suggests a broader area of inquiry, where algorithm designers may learn to adapt similar optimization methods to GPU architecture.

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

Ant Colony Optimization (ACO) [12] is a population-based search method inspired by the behavior of real ants. It may be applied to a wide range of problems [8] and [2], many of which are graph-theoretic in nature. It was first applied to the Traveling Salesman Problem (TSP) [19] by Dorigo et al. [10] and [11]. In essence, simulated ants construct solutions to the TSP in the form of tours. The artificial ants are simple agents which construct tours in a parallel, probabilistic fashion. They are guided in this task by simulated pheromone trails and heuristic information. Pheromone trails are a fundamental component of the algorithm, since they facilitate indirect communication between agents via their environment, a process known as stigmergy [9]. For additional details about these processes, we refer the reader to [12]. ACO algorithms are population-based, that is, a collection of agents “collaborates” to find an optimal (or at least satisfactory) solution. Such approaches are suited to parallel processing, but their success strongly depends on the nature of the particular problem and the underlying hardware available. Several parallelization strategies have been proposed for the ACO algorithm on shared and distributed memory architecture [28], [18] and [21]. The Graphics Processing Unit (GPU) is a topic of significant interest in high performance computing. For applications with abundant parallelism, GPUs deliver higher peak computational throughput than latency-oriented CPUs, thus offering a tremendous potential performance uplift on massively parallel problems [14]. Of particular relevance to us are attempts to parallelize the ACO algorithm on GPUs. Until now, these approaches have focused on accelerating the tour construction, step performed by each ant by taking a task-based parallelism approach, with pheromone deposition on the CPU [13], [3] and [20]. In this paper, we present the first fully developed ACO algorithm for the Traveling Salesman Problem (TSP) on GPUs, where both stages are parallelized: tour construction and pheromone update. A data parallelism approach, which is better suited to the GPU parallelism model, is used to enhance performance on the first stage, and several GPU design patterns are evaluated for the parallelization of the second stage. Our major contributions include the following: 1. To the best of our knowledge, this is the first data-parallelism scheme on GPUs for the ACO tour construction stage. Our design proposes two different types of virtual ants: Queen ants (associated with CUDA thread-blocks), and worker ants (associated with CUDA threads). 2. We introduce an I-Roulette method (Independent Roulette) to replicate the classic roulette wheel selection while improving GPU parallelism. 3. We discuss the implementation of the pheromone update stage on GPUs, using either atomic operations or other GPU alternatives. 4. We offer an in-depth analysis of both stages of the ACO algorithm for different instances of the TSP problem. Several GPU parameters are tuned to reach a speed-up factor of up to 21× for the tour construction stage, and a 20× speed-up factor for the pheromone update stage. 5. The solution accuracy obtained by our GPU algorithms is compared to that of the sequential code given in [12] and extended using TSPLIB. The rest of the paper is organized as follows. We briefly introduce Ant Colony Optimization for the TSP and Compute Unified Device Architecture (CUDA) from NVIDIA in Section 2. In Section 3 we present GPU designs for the main stages of the ACO algorithm. Our experimental methodology is outlined in Section 4 before we describe the performance evaluation of our algorithm in Section 5. Other parallelization strategies for the ACO algorithm are described in Section 6, before we summarize our findings and conclude with suggestions for future work.

نتیجه گیری انگلیسی

Ant Colony Optimization (ACO) belongs to the family of population-based metaheuristics that has been successfully applied to many NP-complete problems. We have demonstrated that task parallelism used by previous implementation efforts does not fit well on GPU architecture, and, to overcome this issue, an alternative approach based in CUDA and data parallelism is provided. This approach enhances the GPU performance by increasing parallelism and avoiding warp divergence, and, combined with an alternative selection procedure that fits better to GPUs, leads to performance gains of more than 20× compared to sequential CPU code executed on a multicore machine. For the pheromone update stage, we are the first to present a complete GPU implementation, including a set of strategies oriented to avoid atomic instructions. We identify potential tradeoffs and investigate several alternatives to sustain gains over 20× in this stage as well. An extensive validation process is also carried out to guarantee the quality of the solution provided by the GPU, and accuracy issues concerning floating-point precision are also investigated. ACO on GPUs is still at a relatively early stage, and we acknowledge that we have tested a relatively simple variant of the algorithm. But, with many other types of ACO algorithm still to be explored, this field seems to offer a promising and potentially fruitful area of research. On the hardware side, it is expected to get even higher accelerations on GPUs whenever the problem size keeps growing and larger device memory space is available. Moreover, we may anticipate that the benefits of our approach would also increase when using future GPU generations endowed with thousands of cores and eventually grouped into GPU clusters to lift performance into unprecedented gains where parallelism is called to play a decisive role.

دانلود فوری مقاله + ترجمه آماده
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.