ارائه یک روش سلسله مراتبی برای تخمین طول نت در طراحی مدار بر روی FPGA

فرآیند جایابی یکی از مهمترین مراحل طراحی م دارهای مجتمع پر تراکم میباشد . افزارههای برنامهپذیر، امکان طراحی مدار را به شکل سادهتر برای کاربر فراهم می کنند و لی در هر حال بایستی فرآیند جایابی در این نوع طراحی نیز انجام شود . تخمین طول نت بوسیله معیار نصف محیط که در فاز جایابی برای برآورد هزینه مورد نیاز میباشد، برای نتهایی که تعداد ترمینالهای زیادی دارند به اندازه کافی دقیق نیست . از این رو لازم است که از روشه ای دیگری برای تخمین دقیق تر نت های چند ترمینالی استفاده شود . یکی از روشهایی که مطرح شده است، درخت steiner میباشد . پیدا کردن یک درخت steiner برای نقاط داده شده، بصورت یک مسأله NP-Complete می باشد . اغلب روش هایی که برای حل این مسأله ارائه شدهاند، مبتنی بر درخت پوشای مینیمم هستند . در این مقاله یک روش سلسله مراتبی برای حل این مسأله ارائه شده است . در این روش زیر درخت های بهینه در ابتدای کار به وجود آمده و سپس در ادامه کار مرحله ادغام دوبدوی آنها انجام می شود تا درخت steiner ن هایی حاصل شود . از مزایای این روش امکان موازی سازی آن و نیز امکان انتخاب زیر درختهای متفاوتی است که دارای هزینه یکسان بوده و در مراحل اولیه به وجود می آیند . انتخاب این زیردرختها در مراحل بالاتر، موجب میشود که ادغام زیر درخت - ها به شکل بهینهتری انجام شود . همچنین، این روش در زمان قابل قبولی نسبت به روشهای موجود قابل اجرا میباشد

Keywords:

طراحی مدارهای مجتمع , FPGA , مسیریابی , جایابی , مستطیل نصف محیط , درخت پوشای مینیمم , درخت مینیمم Steiner