Genetic Placement

ABSTRACT

A placement algorithm, Genie, is presented for the assignment of modules to locations on chips. Genie is an adaptation of the genetic algorithm technique that has traditionally been a tool of the artifcial intelligence community. The technique is a paradigm for examining a state space. It produces its solutions through the simultaneous consideration and manipulation of a set of possible solutions. The manipulations resemble the mechanics of natural evolution. For example, solutions are “mated” to produce “oﬀspring” solutions. Genie has been extensively run on a variety of small test instances. Its solutions were observed to be quite good and in several cases optimal.

INTRODUCTION

THE the design LAYOUT of VLSI PROBLEM chips. Because is a principal of its complexity, problem in it is often decomposed into several distinct subproblems: 1) Chip planning, 2) Partitioning, 3) Placement, 4) Routing. This paper investigates the placement problem-the assignment of circuit elements to locations on the chip. The input to our variant of the placement problem is a set of m circuit elements or modules, M = {el, • • • , em}, and a set of n signals or nets. N = {s\, . .. , s”}, where a net is a set of modules to be interconnected. We are also given as input a set of I chip locations or slots, L = {CI, . . . , c,}, where I ; m. The slots are organized as a matrix with r rows and c columns. The objective is to optimally assign each module to its own slot while satisfying electrical constraints, where optimality is measured in terms of the expected routability of the placement. Two components common to many routability measures are estimates of the amount of wire congestion, and the amount of wire required to route all interconnections. Minimizing the expected wire congestion is important as a feasible wiring is usually found more readily with less congestion;minimizing the expected amount of wire is important as the circuit’s signal propagation rate is typically inversely proportional to the amount of wire.

چکیده

الگوریتم قرار دادن، جن، برای تخصیص ماژول ها به مکان های روی تراشه ارائه شده است. Genie سازگاری با روش الگوریتم ژنتیکی است که به طور سنتی ابزار جامعه هوش مصنوعی است. این روش یک پارادایم برای بررسی یک فضای حالت است. این راه حل ها را از طریق بررسی و دستکاری همزمان مجموعه ای از راه حل های ممکن تولید می کند. دستکاریها به مکانیک تکامل طبیعی شباهت دارند. به عنوان مثال، راه حل ها برای تولید “بهار” به کار می روند. Genie به طور گسترده ای در انواع نمونه های کوچک آزمایش اجرا شده است. راه حل های آن کاملا خوب بود و در چند مورد بهینه بود.

مقدمه

طرح بندی چیپس PROLEM VLSI. از آنجا که یک اصلی از پیچیدگی آن است، مشکل در آن اغلب به چند زیرمجموعه متمایز تقسیم می شود: 1) برنامه ریزی تراشه، 2) پارتیشن بندی، 3) قرار دادن، 4) مسیریابی. در این مقاله مسئله قرار دادن، تعیین عناصر مدار به مکان های موجود بر روی تراشه مورد بررسی قرار می گیرد. ورودی به نوع ما از مسئله قرار دادن مجموعه ای از عناصر مدار و یا ماژول ها، M = {el، • •،، em} و مجموعه ای از سیگنال ها یا شبکه های n است. N = {s \،. ..، s “}، جایی که یک شبکه مجموعه ای از ماژول های متصل است. همچنین به عنوان ورودی مجموعه ای از نقاط I یا تراشه های I داده می شود، L = {CI، …، c،}، where I؛ m. اسلات ها به صورت ماتریس با ردیف های r و ستون c سازماندهی شده اند. هدف این است که به طور مطلوب هر یک از ماژول ها را به شکاف خود اختصاص دهیم در حالی که رضایت محدودیت های الکتریکی را تعیین می کنیم، جایی که بهینه بودن با توجه به روال پذیری احتمالی قرار دادن اندازه گیری می شود. به بسیاری از اندازه گیری های قابل اندازه گیری برآورد شده از میزان تراکم سیم و مقدار سیم مورد نیاز برای راه اندازی تمام اتصالات است. حداقل رسیدن به احتقان سیم سیمانی مهم است به عنوان یک سیم کشی قابل اجرا معمولا راحت تر با کم شدن تراکم یافت می شود، به حداقل رساندن مقدار مورد انتظار سیم مهم است به عنوان نرخ انتشار سیگنال مدار معمولا معکوس متناسب با مقدار سیم است.

Year: 1987

Publisher : IEEE

By : JAMES P, COHOON, MEMBER. IEEE, AND WILLIAM D. PARIS