?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.relation=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F95%2F&rft.title=Magma+Design+Automation%3A+Component+placement+on+chips%3B+%0Athe+%22holey+cheese%22+problem.&rft.creator=Brouwer%2C+Rachel&rft.creator=Brouwer%2C+Thijs&rft.creator=Hurkens%2C+Cor&rft.creator=van+Manen%2C+Martijn&rft.creator=Montijn%2C+Carolynne&rft.creator=Schreuder%2C+Jan&rft.creator=Williams%2C+JF&rft.subject=Information+and+communication+technology&rft.description=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%2C+i.e.+parts+of+the+chipthat+are+beforehand+excluded+from+positioning+by+for+example+some+other+functional+component%2C+and+holes%2C+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%2C+but+the+placement+problem+becomes+much+more+complex+when+the+free+area+is+not+a+simply+connected+domain+anymore%2C+forming++a+%60%60holey+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%2C+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%2C+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%2C+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.+%0A%0AIt+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%2C+but+nowadays+computational+possibilities+are+still+too+restrictive+to+find+an+optimal+solution+within+a+reasonable+amount+of+time+and+computational+memory.+however%2C+we+believe+it+is+possible+to+find+a+solution+that+leads+to+a+acceptable+local+minimum+of+the+costs.&rft.date=2002-02-22&rft.type=Study+Group+Report&rft.type=NonPeerReviewed&rft.format=application%2Fpdf&rft.language=en&rft.identifier=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F95%2F1%2FMagmaproc.pdf&rft.identifier=++Brouwer%2C+Rachel+and+Brouwer%2C+Thijs+and+Hurkens%2C+Cor+and+van+Manen%2C+Martijn+and+Montijn%2C+Carolynne+and+Schreuder%2C+Jan+and+Williams%2C+JF++(2002)+Magma+Design+Automation%3A+Component+placement+on+chips%3B+%0Athe+%22holey+cheese%22+problem.++%5BStudy+Group+Report%5D+++++