moder circuit placement.pdf-资料库

y1302185-10794678-16359647499419447469.pdf-第1页.png

第1页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第2页.png

第2页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第3页.png

第3页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第4页.png

第4页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第5页.png

第5页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第6页.png

第6页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第7页.png

第7页 / 共330页

y1302185-10794678-16359647499419447469.pdf-第8页.png

第8页 / 共330页

Modern Circuit Placement Best Practices and Results

Series on Integrated Circuits and Systems Series Editor: Anantha Chandrakasan Massachusetts Institute of Technology Cambridge, Massachusetts Modern Circuit Placement: Best Practices and Results Gi-Joon Nam and Jason Cong ISBN 978-0-387-36837-5 CMOS Biotechnology Hakho Lee, Donhee Ham and Robert M. Westervelt ISBN 978-0-387-36836-8 SAT-Based Scalable Formal Verification Solutions Malay Ganai and Aarti Gupta ISBN 978-0-387-69166-4, 2007 Ultra-Low Voltage Nano-Scale Memories Kiyoo Itoh, Masashi Horiguchi and Hitoshi Tanaka ISBN 978-0-387-33398-4, 2007 Routing Congestion in VLSI Circuits: Estimation and Optimization Prashant Saxena, Rupesh S. Shelar, Sachin Sapatnekar ISBN 978-0-387-30037-5, 2007 Ultra-Low Power Wireless Technologies for Sensor Networks Brian Otis and Jan Rabaey ISBN 978-0-387-30930-9, 2007 Sub-Threshold Design for Ultra Low-Power Systems Alice Wang, Benton H. Calhoun and Anantha Chandrakasan ISBN 978-0-387-33515-5, 2006 High Performance Energy Efficient Microprocessor Design Vojin Oklibdzija and Ram Krishnamurthy (Eds.) ISBN 978-0-387-28594-8, 2006 Abstraction Refinement for Large Scale Model Checking Chao Wang, Gary D. Hachtel, and Fabio Somenzi ISBN 978-0-387-28594-2, 2006 A Practical Introduction to PSL Cindy Eisner and Dana Fisman ISBN 978-0-387-35313-5, 2006 Thermal and Power Management of Integrated Systems Arman Vassighi and Manoj Sachdev ISBN 978-0-387-25762-4, 2006 Leakage in Nanometer CMOS Technologies Siva G. Narendra and Anantha Chandrakasan ISBN 978-0-387-25737-2, 2005 Statistical Analysis and Optimization for VLSI: Timing and Power Ashish Srivastava, Dennis Sylvester, and David Blaauw ISBN 978-0-387-26049-9, 2005

Gi-Joon Nam Jason Cong Modern Circuit Placement Best Practices and Results 123

Editors: Gi-Joon Nam IBM Austin Research Laboratory Austin, TX USA Jason Cong University of California, Los Angeles Los Angeles, CA USA Series Editor: Anantha Chandrakasan Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 USA Library of Congress Control Number: 2007926182 ISBN 978-0-387-36837-5 e-ISBN 978-0-387-68739-1 Printed on acid-free paper. 2007 Springer Science+Business Media, LLC All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. 9 8 7 6 5 4 3 2 1 springer.com

Dedicated to VLSI circuit placement researchers and practitioners whose creative and persistent efforts made it possible for us to handle the exponential increase of circuit placement complexity in the past four decades. –Gi-Joon & Jason

Contents Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Part I Benchmarks 1 2 ISPD 2005/2006 Placement Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 ISPD 2005 Placement Contest and Benchmark . . . . . . . . . . . . . . . . . . 1.2 1.3 ISPD 2006 Placement Contest and Benchmark . . . . . . . . . . . . . . . . . . 1.4 ISPD Placement Contest Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Locality and Utilization in Placement Suboptimality . . . . . . . . . . . . . . . 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Peko-MC Benchmark Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Monotone Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 The Peko-MC Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Peko-MS Benchmark Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Nonlocal Nets (Peko-MC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Parametrized White Space (Peko-MS) . . . . . . . . . . . . . . . . . . . 2.4.3 Suboptimality Under Both Parametrized White Space and Nonlocal Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4 Suboptimality of Detailed Placement . . . . . . . . . . . . . . . . . . . . 2.4.5 HPWL Suboptimality Comparison of Leading Academic Tools on Peko-MS 2005 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.6 Suboptimality of Routability-Aware Placement . . . . . . . . . . . 2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 4 7 8 11 13 13 15 15 16 17 22 23 25 25 27 29 31 34 35

viii Contents References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Part II Flat Placement Techniques 3 DPlace: Anchor Cell-Based Quadratic Placement with Linear Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Preliminaries and the Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Quadratic Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Force-Directed Quadratic Placement . . . . . . . . . . . . . . . . . . . . 3.2.3 The Proposed Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Global Placement in DPlace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Diffusion Preplacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Anchor Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Unconstrained Wire Length Minimization . . . . . . . . . . . . . . . 3.3.4 HPWL Transformation in a Quadratic System . . . . . . . . . . . . 3.3.5 Fixed Blockages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.6 Wire Length Improvement Heuristics . . . . . . . . . . . . . . . . . . . 3.4 Legalization and Detailed Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Overall Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1 Advantages of our New Formulation . . . . . . . . . . . . . . . . . . . . 3.6.2 ISPD Placement Contest Benchmarks . . . . . . . . . . . . . . . . . . . 3.6.3 PEKO-MS Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Kraftwerk: A Fast and Robust Quadratic Placer Using an Exact Linear Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Clique Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 BoundingBox Net Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Advantages of the BoundingBox Net Model . . . . . . . . . . . . . . 4.3 Quadratic Placement Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Additional Forces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Proof of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Engineering Change Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Quality Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 Spring Constants of the Target Points . . . . . . . . . . . . . . . . . . . 4.4.4 Convergence Plot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.5 Control of the Module Density . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 39 39 41 41 42 44 45 45 46 48 50 51 52 53 53 53 53 55 55 56 57 59 59 62 63 65 66 67 68 71 72 72 74 75 76 78 81

资料库

moder circuit placement.pdf

相关推荐

课程资源

热门标签

最新资料