{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T23:23:08Z","timestamp":1777332188184,"version":"3.51.4"},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":407,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>The top\u2010down \u201cquadratic placement\u201d methodology is rooted in such works as [36, 9, 32]\nand is reputedly the basis of commercial and in\u2010house VLSI placement tools. This\nmethodology iterates between two basic steps: solving sparse systems of linear equations\nto achieve a continuous placement solution, and \u201clegalization\u201d of the placement by\ntransportation or partitioning. Our work, which extends [5], studies implementation\nchoices and underlying motivations for the quadratic placement methodology. We first\nrecall some observations from [5], <jats:italic>e.g.<\/jats:italic>, that (i) Krylov subspace engines for solving\nsparse linear systems are more effective than traditional successive over\u2010relaxation\n(SOR) engines [33] and (ii) that <jats:italic>correlation convergence<\/jats:italic> criteria can maintain solution\nquality while using substantially fewer solver iterations. The focus of our investigation is\nthe coupling of numerical solvers to iterative partitioners that is a hallmark of the\nquadratic placement methodology. We provide evidence that this coupling may have\nhistorically been motivated by the pre\u20101990\u2019s weakness of min\u2010cut partitioners, <jats:italic>i.e.<\/jats:italic>,\nnumerical engines were <jats:italic>needed<\/jats:italic> to provide helpful hints to weak min\u2010cut partitioners. In\nparticular, we show that a modern multilevel FM implementation [2] derives no benefit\nfrom such coupling. We also show that most insights obtained from study of individual\nmin\u2010cut partitioning instances (within the top\u2010down placement) also hold within the\noverall context of a complete top\u2010down placer implementation.<\/jats:p>","DOI":"10.1155\/1999\/93607","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:58:37Z","timestamp":1190120317000},"page":"99-116","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Analytical Engines are Unnecessary in Top\u2010down Partitioning\u2010based Placement"],"prefix":"10.1155","volume":"10","author":[{"given":"C. J.","family":"Alpert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. E.","family":"Caldwell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. F.","family":"Chan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. J.-H.","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. B.","family":"Kahng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. L.","family":"Markov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Moroz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[1998,11,20]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1999\/093607.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/vlsi\/1999\/093607.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1999\/93607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T15:17:49Z","timestamp":1723216669000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1999\/93607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,11,20]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1155\/1999\/93607"],"URL":"https:\/\/doi.org\/10.1155\/1999\/93607","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"value":"1065-514X","type":"print"},{"value":"1563-5171","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,11,20]]},"assertion":[{"value":"1998-09-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"1998-11-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"1998-11-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}