علوم رایانش و فناوری اطلاعات
ارائه معماری یک شتاب‌دهنده الگوریتم ژنتیک پرسرعت، عام‌منظوره و مقیاس‌پذیر
نوع مقاله : مقاله پژوهشی
نویسندگان
دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی، تهران، ایران
چکیده
الگوریتم ژنتیک کاربرد فراوانی در حل مسائل بهینه‌سازی با فضای جستجوی گسترده، پیچیده و غیر خطی دارد. مهمترین خصوصیت ذاتی این الگوریتم، نیاز به انجام عملیات ساده و تکراری برای تعداد زیادی ژنوم و در نسل‌های فراوان است که امکان بالقوه اجرای موازی عملیات و پیاده‌سازی سخت‌افزاری الگوریتم را مهیا می سازد. مهمترین چالش پیاده سازی سخت افزاری یک پردازنده عام‌منظوره الگوریتم ژنتیک، به بخش محاسبه مقدار برازندگی ژنوم‌ها بر می‌گردد که برای هر مساله به صورت اختصاصی تعریف می‌شود و امکان پیاده‌سازی آن به‌صورت عام‌منظوره و با راندنمان بالا وجود ندارد. در این مقاله، با بهره گیری از طراحی توأمان سخت افزار-نرم افزار، به توسعه معماری یک پردازنده عام منظوره و در عین حال پرسرعت الگوریتم ژنتیک پرداخته شده است. در معماری پیشنهادی، واحد محاسبه مقدار برازندگی از بخش‌های سخت‌افزاری پردازنده خارج شده، امکان پیاده سازی آن در خارج از هسته و با بهره‌گیری از هر تعداد موتور محاسباتی و با خصوصیات متناسب با هر کاربرد فراهم شده است. با اینکار، ضمن حفظ عام منظوره بودن معماری هسته پردازنده، امکان پیاده سازی پرسرعت آن فراهم شده است. از طرف دیگر ، انتقال بخش محاسبه مقدار برازندگی که معمولا پرمحاسبه‌تر و کندتر از بخش‌های دیگر است به خارج از تراشه، موجب کندی بیشتر این بخش و بی نتیجه کردن سرعت بالای بخش‌های داخل هسته خواهد شد. برای رفع این مشکل و افزایش متناسب سرعت محاسبه مقادیر برازندگی در هنگام حل مسائل مختلف متناسب با سرعت هسته، هسته معماری پیشنهادی به نوعی طراحی شده است که امکان ارسال و دریافت موازی و همزمان ژنوم‌ها به تعداد دلخواهی از واحدهای محاسبه مقدار برازندگی به صورت ناهمگام را دارا است. نکته قابل توجه دیگر این است که در معماری پیشنهادی لزومی به یکدست بودن واحدهای محاسبه مقدار برازندگی نیست، و هسته پردازنده، قابلیت تعامل با واحدهای ناهمگون از لحاظ سرعت و ساختار را نیز دارا است. عملکرد معماری پیشنهادی در مقایسه با کارهای قبلی در حل مسئله فروشنده دوره‌گرد به ازای پارامترهای مختلف از ۳۳٪ تا ۷۱٪ برای زمان اجرا و تعداد کلاک هر نسل بهبود داشته است.
کلیدواژه‌ها
)