بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
پیادهسازی الگوریتم بهینه سازی کلنی مورچه با CUDA1
چکیده
مورچه ها در طبیعت برای یافتن غذا با یکدیگر از طریق جاگذاری فرومون3 به عنوان راهنمایی به سمت منبع غذایی همکاری میکنند. الگوریتم بهینه سازی کلنی مورچه ها بر اساس همین اصل کار میکند. در این الگوریتم مورچههای شبیه سازی شده، راه حلی را برای جواب مسئله می سازند و مقادیر فرومون برای دستیابی به جواب بهتر بروزرسانی میشوند.
ما این الگوریتم را برای مسئله فروشنده دوره گرد4 بهکار میگیریم. در این مسئله هدف پیدا کردن کوتاه ترین مسیر بین یک مجموعه از شهرها است، به گونه ای که از هر شهر باید دقیقاَ یک بار عبور کرد. الگوریتم بهینه سازی کلنی مورچه برای این مسئله با توجه به فضای بزرگ جستجوی آن بسیار مناسب است. به عنوان مثال با وجود مسئله ای با تعداد 50
شهر تعداد مسیرهای ممکن بیشتر از تعداد اتمهای کشف شده در جهان میباشد.
ما الگوریتم بهینه سازی کلنی مورچه را با استفاده از Nvidia CUDA اجرا میکنیم. تا بتوانیم از مزایای واحدهای پردازش گرافیکی5 در اجرای موازی الگوریتم بهرهمند شویم. GPU ها اجازه میدهند که چندین نخ اجرایی به صورت موازی اجرا شوند و این نخها در داخل بلوکهای نخ سازماندهی میشوند. به ازای هر مورچهای که مسئول نگهداری اطلاعات حالت و وضعیت تولید کننده مسیر است یک بلوک نخ ایجاد میکنیم. تعداد نخهای موجود در هر بلوک نخ یک فاکتور حیاتی میباشد . به عنوان مثال تعداد 64 نخ در هر بلوک نسبت به 32 نخ در کاربردهای CUDA بهتر عمل میکند. برای مسئلهای با حدود 1291 شهر، بیش از ده فاکتور برای سرعت عملکرد و تسریع وجود دارد.
.1 مقدمه
الگوریتم بهینه سازی کلنی مورچه (ACO) برای مدلسازی یک کلنی از مورچهها که میتواند مسائل محاسباتی که در سطح پیدا کردن مسیر بهینه در گراف است را حل کند، استفاده می شود. مانند عملیات پیدا کردن غذا توسط مورچه ها، که این عملیات از طریق جاگذاری اثر فرومون بر روی مسیر توسط مورچهها و پیگیری مسیری که بیشترین حجم فرومون را دارد صورت میگیرد.از الگوریتم ACO برای بهبود تصمیم گیری در مورد این مسئله استفاده میشود. این الگوریتم برای اولین بار توسط مارکو دارگین6 و در پایاننامه دکترایش مطرح شد. آزمایشی معروف به پل دوگانه7 در کلنی از مورچه ها به نام مورچههای ارژانتینی استفاده میشد که در آن مورچه ها بوسیله پلهایی با طول یکسان به منبع غذایی دسترسی پیدا میکردند. در این آزماش مورچه ها جستجوی اطراف منبع غذا را تا زمانی که بوسیله هر دو پل به غذا دسترسی داشته باشند، ادامه میدهند. وقتی که مورچه ها منبع غذایی را یافتند، اثر فرومون را در مسیر های منتهی به منبع قرار میدهند.در زمان برخورد با دو پل، مورچه ها به صورت تصادفی یکی از پلها را انتخاب میکنند. با گذشت زمان در اثر انتخابهای تصادفی یکی از پلها غلظت فرومون بیشتری را خواهد داشت. نتیجه این امر این خواهد بود که با گذشت زمان کل مورچهها به سمت همین پل همگرا خواهند شد. این مکانیسم میتواند به عنوان راه حلی برای پیدا کردن کوتاه ترین مسیر به سمت منبع غذا به کار گرفته شود.
نوع دیگری از آزمایش پل دوگانه نیز توسط گوس8 ارائه شده است که در آن یکی از پلها به میزان قابل توجهی از دیگری کوتاه تر است. در این روش مورچههایی که پل کوتاه تر را انتخاب میکنند زودتر به منبع غذایی دسترسی پیدا میکنند و به لانه برمیگردند و فرومون را زودتر از مورچههایی که پل بزرگتر را انتخاب میکنند بر جا میگذارند. این امر شانس رسیدن به غذا توسط مورچههایی که پل کوتاهتر را انتخاب میکنند، بیشتر میکند. و چون غلظت فرومون مسیر کوتاه تر بیشتر است، بنابر این با گذشت زمان کل کلنی به سمت منبع غذایی با استفاده از پل کوتاه تر همگرا میشوند.
.2 کارهای مرتبط
.1-2 استفاده از ACO برای مسئله فروشنده دوره گرد
مسئله فروشنده دورهگرد شامل مجموعهای از شهرها با فواصل معین بین آنها است. هدف پیدا کردن کوتاه ترین مسیری است که از همه شهر ها دقیقاَ یک بار عبور کند. ACO میتواند برای پیدا کردن راه حل بهینه برای این مسئله استفاده شود. مجموعه شهرها را میتوان به عنوان یک گراف در نظر گرفت که در ان هر شهر را میتوان بوسیله یک گره نشان داد و وزن هر لبه معرف فاصله بین دو شهر است. هر لبه همچنین شامل اطلاعاتی در مورد سطح فرومون آن مسیر است. این روش شامل یک شبیه سازی به تعدادی مورچه مصنوعی است که یک دنباله ای از جستجوهای توزیع شده را در گراف انجام میدهند. مورچههایی که به طور تصادفی در شهر شروع قرار میگیرند، یک مسیر را با گذر از همه شهرها طی میکنند. در این گذر دو اصل باید مورد توجه قرار گیرد:
اول اینکه از هر شهر باید دقیقاَ یک بار گذر شود و دوم اینکه میزان فرومون موجود در یک لبه بر احتمال وجود داشتن آن لبه در مسیر مورد نظر تأثیر میگذارد. بعد از اینکه مورچهها مسیر خود را کامل کردند، سطح فرومون موجود در هر لبه برای هر مورچه به صورت مستقل بروزرسانی میشود و لبههای طی شده میزان فرومون خود را افزایش میدهند. این روش از یک مکانیسم انتخاب لبه اکتشافی9 پیروی میکند که مبتنی است بر فاصله بین دو شهر و سطح فرومون. چنین راه حلی به سمت یک راه حل بهینه متمایل است. این روش با یک فرایند تبخیر فرومون نیز همراه است تا فرایند جستجو در یک محل را به حداقل برساند.این هدف با کاهش میزان فرومون مسیر همه لبه هایی که در یک سفر(تور) کامل وجود داشتند، بعد از کامل شدن مسیر به دست میآید.
هر چه مسیری بهتر باشد میزان فرومون بیشتری در آن ذخیره میشود و این باعث میشود که مورچهها در تکرارهای بعدی مسیری مشابه با مسیر بهینه قبلی بسازند. الگوریتم ACO ثابت کرده است که در پیدا کردن راه حل بهینه برای انواع مسائل TSP مؤثر است. ما برای بهینه سازی زمان اجرای الگوریتم ACO از واحد های پردازش گرافیکی استفاده میکنیم تا بتوانیم از مزایای اجرای موازی الگوریتم و معماری سخت افزار بهرهمند شویم.
.2-2 بررسی واحدهای پردازش گرافیکی
طراحی فیزیکی واحدهای پردازش گرافیکی خیلی متفاوت از واحدهای پردازش محاسباتی10 است. GPU ها به گونهای طراحی شدهاند که بیشتر ترانزیستور ها به جای ذخیره سازی داده ها و کنترل جریان به پردازش داده ها اختصاص داده میشوند. همانطور که در شکل 1 نشان داده شده است. بنابراین GPU ها برای محاسباتی که به شدت به موازی سازی نیاز دارند اختصاص داده میشوند.
مسائلی که میتوانند به عنوان داده ها و محاسبات موازی بیان شوند بسیار مناسبتر است که روی GPU اجرا شوند تا روی . CPU در الگوریتم ACO فاز ساخت و ساز مسیر به عنوان یک زیر مسئله، این قابلیت را دارد که به صورت موازی توسط واحد های پردازش گرافیکی اجرا شود.
در این الگوریتم هر مورچه میتواند به عنوان یک عامل مستقل تصور شود و کل کلنی مورچه ها میتوانند مسیرها را به صورت موازی و بدون تکیه و اطلاع از اطلاعات یکدیگر بسازند. تنها تبادل اطلاعات اتفاق می افتد و بروزرسانی فرومون بعد از اینکه همه مورچهها یک راه حل را ساختند انجام میشود
.3-2 محصول CUDA کمپانی سازنده کارت های گرافیکی در کالیفرنیا11
CUDA در سال 2006 توسط NVIDIA منتشر شد. این موتور محاسباتی روی واحد های پردازش گرافیکی این شرکت موجود است. CUDA به توسعه دهندگان نرمافزار این اجازه را میدهد که با دستگاههای GPU ارتباط برقرار کنند و برنامههایی بنویسند که به طور مستقیم روی آنها از طریق توسعه به زبان های برنامه نویسی مختلفی از قبیل C، پرل، فرترن و جاوا اجرا شوند.
.4-2 تعریف هسته12
CUDA به برنامه نویسان این اجازه را میدهد که توابعی را ایجاد کنند به نام هسته که بتوانند روی واحد های پردازش گرافیکی اجرا شوند. علاوه براین برخلاف توابع معمولی که تنها یک بار در هر فراخوانی اجرا میشوند، هستهها این قابلیت را دارند که n بار به صورت موازی بوسیله n نخ CUDA متفاوت اجرا شوند که مقدار n بوسیله برنامه نویس تعریف میشود. هر یک از نخهایی که در هسته اجرا میشوند یک مقدار ID نخ منحصر بفردی دارند که در داخل هسته قابل دسترسی است. به عنوان مثال یک برنامه ساده ای که دو بردار A و B به طول n را با هم جمع میکند و حاصل را در بردار C به طول n ذخیره میکند را در نظر بگیرید. این عمل میتواند با یک هسته با n نخ تعریف شود که در آن هر نخ با ID منحصر بفردش مسئول یک موقعیت در بردارهای تعریف شده میباشد. بنابراین اولین نخی که مقدار اولین خانه در بردارهای A و B را میخواند، آنها را جمع میکند و حاصل را در اولین خانه در بردار C ذخیره میکند. در هر صورت اجرای این عملیات از طریق CPU یا GPU به n جمع نیاز دارد. با این تفاوت که اجرای این n جمع با CPU به صورت ترتیبی، ولی با GPU به صورت موازی میباشد.
.5-2 بلوکهای نخ13
نخها میتوانند برای ایجاد بلوکهای نخ با هم همگروه شوند. نخها میتوانند به صورت بلوکهای نخ یک، دو یا سه بعدی سازماندهی شوند. به عنوان مثال برای جمع دو ماتریس به سایز n*n، باید مشابه جمع برداری یک هسته با استفاده از یک بلوک نخ n*n فراخوانی شود.
یک محدودیت برای تعداد نخ های موجود در هر بلوک وجود دارد. زیرا همه نخ ها باید روی همان هسته پردازنده مستقر شوند و باید منابع محدود آن هسته را به اشتراک بگذارند. در حال حاضر دستگاههایی با توان محاسباتی 2 و بالاتر، 1024 نخ در هر بلوک را پشتیبانی میکنند. همچنین ممکن است که چندین نوع هسته با بلوکهای نخ همشکل را اجرا کند و اجازه دهد که کل تعداد نخ ها یکباره اجرا شوند تا زمان اجرای عملیات به حداقل برسد.
.6-2 سلسله مراتب حافظه14
دستگاههای پردازنده گرافیکی شامل انواع متعددی از حافظه با سطح دسترسی مختلفی میباشند. هر نخ به حافظه محلی خودش و نیز به حافظه اشتراکی که در همه نخهای همان بلوک قابل دسترسی است، دسترسی دارند. حافظه سراسری برای همه نخ ها برای عملیات های خواندن و نوشتن قابل دسترسی است. این بزرگترین منبع ذخیره سازی میباشد.(در حدود چند گیگا بایت) ولی دارای کندترین زمان دسترسی است.حافظه ثابت شبیه حافظه سراسری است با این تفاوت که فقط قابل خواندن است و از نظر اندازه نیز خیلی کوچک است.
هر دادهای که بوسیله GPU استفاده میشود، باید ابتدا بر روی میزبان یعنی CPU کپی شود. هم بر روی حافظه سراسری و هم بر روی حافظه ثابت. هر داده ای که میزبان بخواهد از دستگاه((GPU بازیابی کند باید روی حافظه سراسری مستقر شود. حافظه مشترک(داخلی) نوع سریعتری است و همراه حافظه ثابت است.حافظه محلی با این حافظه ها متفاوت است. آنها به صورت بهینه در ثبات ها ذخیره میشوند. اما اگر یک نخ نیاز به حافظه محلی بیشتر از حداکثر منبع فیزیکی یک چیپ داشته باشد، آن نخ به حافظه سراسری منتقل میشود.بنابراین ملاحضات زیادی برای یک طرح بندی حافظه بهینه وجود دارد که میتواند برای زمان اجرای یک برنامه مؤثر باشد.
.3 روش تحقیق
.1-3 الگوریتم ACO فوق ابتکاری15
ایده اصلی این الگوریتم این است که به مورچه های مصنوعی این اجازه را بدهیم که راه حل مورد نظر را بوسیله دنباله ای از تصمیمات احتمالی بسازند. این امر بوسیله یک فرایند تکراری انجام میشود. برای رسیدن به این هدف، وقتی مورچهای در یک مرحله به یک راه حل بهینه دست می یابد، باید سایر مورچه های موجود در کلنی را بوسیله بروزرسانی مقادیر فرومون موجود در آن مسیر به سمت مسیر بهینه هدایت کند. این روند تا زمانی که معیار توقف برآورده شود ادامه مییابد. معیار توقف را میتوان تعداد تکرارها یا کیفیت راه حل دانست. الگوریتم را میتوان به صورت زیر توصیف کرد:
الگوریتم :1
ACO Meta-heuristic: Initialize parameters, variables, and pheromone values while termination condition is not met do for each Ant Construct a solution end for
Update pheromone values end while
وقتی الگوریتم ACO برا مسئله TSP به کار گرفت میشود، ما مجموعه ای از n شهر با فواصل dij بین هر جفت از شهرهای i و j درنظر میگیریم. مقادیر فرومون به صورت یک ماتریس n*n سازماندهی میشوند که Tij مقدار فرومون مسیر بین شهر های i وj میباشد. از آنجایی که هر شهر تنها یک بار میتواند انتخاب شود، ما S را مجموعه ای از شهرهای قابل انتخاب باقی مانده معرفی میکنیم. بنابراین احتمال انتخاب شهر j بعد از شهر i به صورت زیر تعریف میشود:
فرمول فوق تنها مقادیر فرومون را در نظر میگیرد. در صورتی که اطلاعات زیادی وجود دارد که میتواند به هدایت مورچه های مصنوعی در ساختن یک مسیر مناسب کمک کند . یکی از این اطلاعات اکتشافی فواصل بین شهرها میباشد که با Nij مشخص میشود. با ترکیب و تخصیص مقادیر α و β که به ترتیب متناظر هستند با اثرات نسبی فرومون و مقادیر اکتشافی(فاصله بین شهرها)، ما میتوانیم احتمال انتخاب شهر j بعد از شهر i را به صورت زیر توصیف کنیم:
فرض کنید که m مورچه وجود دارد.بعد از یک تکرار m راه حل ساخته شده وجود خواهد داشت.
گام بعدی بروزرسانی مقادیر فرومون میباشد که این مرحله در دو گام انجام میشود. گام اول تبخیر فرومون است که در این گام مقادیر فرومون با یک ثابت p که معرف نرخ تبخیر میباشد کاهش پیدا میکند:
گام دوم بروزرسانی مقادیر فرومون بر اساس راه حل ساخته شده است. مقدار فرومون هر لبه به صورت زیر افزایش پیدا میکند:
