Brouwer, Rachel and Brouwer, Thijs and Hurkens, Cor and van Manen, Martijn and Montijn, Carolynne and Schreuder, Jan and Williams, JF
(2002)
Magma Design Automation: Component placement on chips;
the "holey cheese" problem.
[Study Group Report]

PDF
338kB 
Abstract
The costs of the fabrication of a chip is partly determined by the wire length needed by the transistors to respect the wiring scheme. The transistors have to be placed without overlap into a prescribed configuration of blockades, i.e. parts of the chipthat are beforehand excluded from positioning by for example some other functional component, and holes, i.e. the remaining free area on the chip. A method to minimize the wire length when the free area is a simply connected domain has already been implemented by Magma, but the placement problem becomes much more complex when the free area is not a simply connected domain anymore, forming a ``holey cheese''. One of the approaches of the problem in this case is to first cluster the transistors into socalled macro's in such a way that closely interconnected transistors stay together, and that the macro's can be fit into the holes. One way to carry out the clustering is to use a graph clustering algorithm, the socalled Markov Cluster algorithm. Another way is to combine the placement method of Magma on a rectangular area of the same size as the total size of the holes, and a min cutmax flow algorithm to divide that rectangle into more or less rectangular macro's in such a way that as little wires as possible are cut.
It is now possible to formulate the Quadratic Assignment Problem that remains after clustering the original problem to one with 100 up to 1000 macros. There exists a lot of literature on finding the global minimum of the costs, but nowadays computational possibilities are still too restrictive to find an optimal solution within a reasonable amount of time and computational memory. however, we believe it is possible to find a solution that leads to a acceptable local minimum of the costs.
Item Type:  Study Group Report 

Problem Sectors:  Information and communication technology 
Study Groups:  European Study Group with Industry > ESGI 42 (Amsterdam, Netherlands, Feb 1822, 2002) 
Company Name:  Magma Design Automation 
ID Code:  95 
Deposited By:  Richard Booth 
Deposited On:  15 Feb 2007 
Last Modified:  29 May 2015 19:47 
Repository Staff Only: item control page