Flow-based partitioning and fast global placement in chip design [Elektronische Ressource] / vorgelegt von Markus Struzyna

Flow-based Partitioning andFast Global Placementin Chip DesignDissertationzur Erlangung des Doktorgrades (Dr. rer. nat.)der Mathematisch-Naturwissenschaftlichen Fakult¨atder Rheinischen Friedrich-Wilhelms-Universit¨at Bonnvorgelegt vonMarkus StruzynaausTychy/PolenBonn, Juli 2010Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen Fakult¨at derRheinischen Friedrich-Wilhelms-Universit¨at BonnErstgutachter: Prof. Dr. Jens VygenZweitgutachter: Prof. Dr. Dr. h.c. Bernhard KorteTag der Promotion: 30. September 2010Erscheinungsjahr: 2010Contents1 Introduction 72 Preliminaries 112.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 The Placement Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.1 Net Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.2 Placement and Density . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.3 Other Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3 Complexity Issues in Placement . . . . . . . . . . . . . . . . . . . . . . . . 202.4 Global Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 Global Placement Algorithms 233.1 Non-analytic Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Analytic Netlength Minimization . . . . . . . . . . . . . . . . . . . . . . . 243.2.1 Non-linear Non-quadratic Net Models . . . . . . . . . . . . . . . . . 243.2.