eprintid: 95
rev_number: 4
eprint_status: archive
userid: 5
dir: disk0/00/00/00/95
datestamp: 2007-02-15
lastmod: 2015-05-29 19:47:17
status_changed: 2009-04-08 16:54:04
type: report
metadata_visibility: show
item_issues_count: 0
creators_name: Brouwer, Rachel
creators_name: Brouwer, Thijs
creators_name: Hurkens, Cor
creators_name: van Manen, Martijn
creators_name: Montijn, Carolynne
creators_name: Schreuder, Jan
creators_name: Williams, JF
title: Magma Design Automation: Component placement on chips; 
the "holey cheese" problem.
ispublished: pub
subjects: telecom
studygroups: esgi42
companyname: Magma Design Automation
full_text_status: public
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 so-called 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 so-called 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 cut-max 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.
date: 2002-02-22
date_type: published
pages: 14
citation:   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]     
document_url: http://miis.maths.ox.ac.uk/miis/95/1/Magmaproc.pdf