روشی بهبود یافته برای جایابی سلول های استاندارد در مدارات مجتمع پرتراکم با ترکیب روش های تصادفی و تکنیک های بهینه سازی ریاضی

در سالیان اخیر بدلیل بالا رفتن ارزش منابع مورد استفاده و نیز بزرگ شدن اندازه مسایل، بهینه سازی ریاضی بعنوان یک نیاز جدی در صنایع مطرح شده است و روش های بهینه سازی ریاضی در بسیاری از کاربردهای نظری و کاربردی جایگاه مهمی یافته اند. مساله جایابی در طراحی مدارهای مجتمع دیجیتال عبارت است از یافتن بهترین محل برای قرار دادن اجزای الکترونیکی روی یک تراشه بنحوی که یک یا ترکیبی از چند معیار در قالب یک تابع هدف حداقل شوند. جایابی بروش سلول استاندارد نوع خاصی از جایابی است که در آن ارتفاع سلول ها ثابت بوده و سلول ها در سطرهای مجزا جایابی می شوند و هر سلول را نمی توان بهرصورتی, در هرجای دلخواه و با هر چرخش دلخواه جایابی نمود. با توجه به بزرگی ابعاد مسایل جایابی در VLSI استفاده از روش های تحلیلی ناممکن است و عمدتا از روشهای تقریبی و ابتکاری برای حل این مسایل استفاده میگردد که کیفیت پاسخ آنها از روش های ریاضی کمتر است. در این مقاله روشی مرکب از روشهای تحلیلی با استفاده از بهینه‎سازی ریاضی و روش‎های تقریبی برای این مساله ارایه شده است. نتایج نشان می دهد که کیفیت جواب بهتر از روش های کاملا تقریبی است و افزایش زمان محاسبات هم در حد قابل قبولی است. چنانکه در آزمایشات انجام شده دیده می شود با استفاده از روش ارایه شده مجموع طول سیم بطور متوسط 28/6% کاهش داشته و زمان محاسبات نیز با نسبت بسیار کمی (بطور متوسط 1/2%) افزایش یافته است.