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

یکی از مراحل در تبدیل کد سخت افزاری به دنباله هایی از صفر و یک ها که به جریان بیتی معروف است، مرحله چینش است. چینش وقت گیر ترین مرحله در تبدیل می باشد و حدود نیمی از زمان کامپایل به آن اختصاص دارد. امروزه بیشتر برای چینش از الگوریتم شبیه سازی گداختگی فلزات استفاده می شود. این الگوریتم از لحاظ بهینه سازی خوب عمل می کند اما مدت زمان اجرای آن مخصوصا برای مدارهای بزرگ، زیاد است. در این مقاله از الگوریتم ژنتیک به دلیل خاصیت موازی که دارد برای چینش در fpga ها استفاده شده است. دو عملگر مهم در الگوریتم ژنتیک، عملگر ترکیب و عملگر جهش می باشد. برای آزمایش الگوریتم پیشنهادی از مجموعه داده mcnc استفاده شده است. نتایج پیاده سازی نشان می دهد که الگوریتم پیشنهادی برای پارامتر طول سیم به خوبی الگوریتم شبیه سازی گداختگی فلزات نیست اما زمان اجرای الگوریتم به صورت محسوسی کاهش یافته است. الگوریتم پیشنهادی از نظر طول سیم و زمان اجرا نسبت به الگوریتم های تکاملی مشابه، مانند csr بهتر عمل کرده است.