Magma Design Automation: Component placement op chips

Het gatenkaasprobleem
Een van de stappen in het ontwerpprocess van chips is het bepalen van een positie van elk van de onderdelen, `cells', op de chip, ook wel het `plaatsen' genoemd. De cellen zijn onderling verbonden door draadjes: het bedradingsschema ligt vast, en in deze fase van het ontwerpproces moet de ruimtelijke plaatsing van de verschillende cellen op de chip bepaald worden. Sommige (relatief weinig) cellen hebben een voorgeschreven vaste positie.

Voor het klassieke plaatsingsprobleem beschouwen we de chip als een twee-dimensionaal vlak; de cellen worden voorgesteld door rechthoeken van verschillende afmetingen. Het plaatsen van de cellen moet zodanig gebeuren dat

de cellen alle binnen een bepaalde rechthoek (`core area') liggen,
de cellen elkaar niet overlappen, en
de totale draadlengte geminimaliseerd wordt.

Voor dit probleem zijn al vele algoritmen bekend, alle met hun specifieke voor- en nadelen.

Het probleem wordt in toenemende mate bemoeilijkt wanneer grote delen van de core area uitgesloten worden van plaatsing, meestal doordat hier voorgeplaatste grote functionele blokken liggen (denk aan geheugens en blokken die extern ontworpen worden). De uiteindelijke `vrije ruimte' binnen de core area is doorgaans vergelijkbaar met een kaas vol gaten. Vanzelfsprekend mogen cellen niet op deze blokken (`blockages') geplaatst worden, en het is deze extra eis die het plaatsingsprobleem wezenlijk moeilijker maakt.

Hierboven staat een voorbeeld van een typische `gatenkaas'. De groene gebieden zijn toegestaan, de witte geblokkeerd. (De `ruis' in de groene gebieden heeft niets te maken met de vrije ruimte). Merk op dat de vrije ruimte sterk onsamenhangend is.

De huidige algoritmes van Magma DA werken goed in het geval van grofweg convexe gebieden; in `gatenkazen' blijken ze echter gemakkelijk terecht te komen in locale minima die sterk suboptimaal zijn.

Vraag:
Hoe kan Magma DA ook in het geval van gatenkazen goede oplossingen vinden?