An Artificial Intelligence Approach to VLSI Routing

مسیریابی تراشه های VLSI یک مشکل مهم، زمان بر و دشوار است. دشواری مشکل به تعداد زیادی از عوامل اغلب متناقض نسبت داده می شود که بر کیفیت مسیریابی تأثیر می گذارد. تکنیک‌های سنتی با نادیده گرفتن برخی از این عوامل و تحمیل محدودیت‌های غیر ضروری به مسیریابی نزدیک شده‌اند. علاوه بر اعمال این محدودیت ها که مشکلات را تا حدی ساده می کند اما در عین حال کیفیت مسیریابی را کاهش می دهد، رویکردهای سنتی از نیروی بی رحم استفاده می کنند. آنها اغلب مسئله را به مسائل ریاضی یا نموداری تبدیل می کنند و دانش خاص در مورد وظیفه مسیریابی را که می تواند کمک زیادی به حل آن کند، کاملاً نادیده می گیرند. این پایان نامه بر برخی از مشکلات فوق غلبه می کند و سیستمی را ارائه می دهد که مسیریابی را نزدیک به آنچه طراحان انسانی انجام می دهند انجام می دهد. به عبارت دیگر، به شدت بر دانش تخصص انسانی در این زمینه سرمایه گذاری می کند، محدودیت های غیر ضروری را تحمیل نمی کند، تمام عوامل مختلفی را که بر کیفیت مسیریابی تأثیر می گذارند در نظر می گیرد، و مهمتر از همه اجازه می دهد تا تعامل ثابت کاربر در طول فرآیند مسیریابی وجود داشته باشد. برای دستیابی به موارد فوق، این پایان نامه پیشینه ای در مورد برخی از تکنیک های معرف مسیریابی ارائه می کند و ویژگی های آنها را خلاصه می کند. سپس عوامل مختلف (مانند حداقل مساحت، تعداد گذرگاه‌ها، طول سیم و غیره) را که بر کیفیت مسیریابی تأثیر می‌گذارند و معیارهای مختلف (مانند نمودار محدودیت عمودی/افقی، ادغام، حداقل درخت اشتاینر مستطیلی)، به طور دقیق مطالعه می‌کند. و غیره) که می تواند برای بهینه سازی این عوامل استفاده شود.

Routing of VLSI chips is an important, time consuming, and difficult problem. The difficulty of the problem is attributed to the large number of often conflicting factors that affect the routing quality. Traditional techniques have approached routing by ignoring some of these factors and imposing unnecessary constraints in order to make routing tractable. In addition to the imposition of these restrictions, which simplify the problems to a degree but at the same time reduce the routing quality, traditional approaches use brute force. They often transform the problem into mathematical or graph problems and completely ignore the specific knowledge about the routing task that can greatly help the solution. This thesis overcomes some of the above problems and presents a system that performs routing close to what human designers do. In other words it heavily capitalizes on the knowledge of human expertise in this area, it does not impose unnecessary constraints, it considers all the different factors that affect the routing quality, and most importantly it allows constant user interaction throughout the routing process. To achieve the above, this thesis presents background about some representative techniques for routing and summarizes their characteristics. It then studies in detail the different factors (such as minimum area, number of vias, wire length, etc.) that affect the routing quality, and the different criteria (such as vertical/horizontal constraint graph, merging, minimal rectilinear Steiner tree, etc.) that can be used to optimize these factors.